автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Разработка программного инструментария управления маршрутизацией информационных потоков в корпоративных вычислительных сетях

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ УНИВЕРСИТЕТ

На правах рукописи

ЛАШТ Дмитрий Геннадьевич

УДК 658.52:681.326.3 (047)

РАЗРАБОТКА ПРОГРАММНОГО ИНСТРУМЕНТАРИЯ УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ ИНФОРМАЦИОННЫХ ПОТОКОВ В КОРПОРАТИВНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ

Специальность 05.13.06 "Автоматизированные системы управления'

Диссертация

На соискание учёной степени кандидата технических наук

Научный руководитель -профессор, доктор технических наук Федунец Н.И.

Москва 1998

Оглавление

ВВЕДЕНИЕ._____5

1. ИССЛЕДОВАНИЕ ИНФРАСТРУКТУРЫ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ._9

1.1 Основные концепции сетевых взаимодействий. 9

1.2 Использование технологии маршрутизации для построения

крупномасштабных вычислительных сетей. 17

1.3 Использование технологии коммутации для построения

крупномасштабных вычислительных сетей. 20

1.4 использование технологии коммутации 1Р-пакетов на канальном уровне

для построения крупномасштабных вычислительных сетей. 38

ВЫВОДЫ ПО ГЛАВЕ 1.__________45

2. МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ МАРШРУТИЗАЦИИ ИНФОРМАЦИОННЫХ ПОТОКОВ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ.__47

2.1 основные концепции маршрутной политики. 47

2.2 Организация процесса обмена маршрутной информацией между автономными системами на базе внешнего протокола маршрутизации BGP. 50

2.3 Организация процесса локальной маршрутизации на базе протокола RIP. 57

2.4 Организация процесса локальной маршрутизации на б азе протокола IGRP. 61

2.5 Организация процесса локальной маршрутизации на базе протокола OSPF. 69

ВЫВОДЫ ПО ГЛАВЕ 2._____________79

3. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ МОДЕЛИРОВАНИЯ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ._________80

3.1

3.2

Построение структурной схемы корпоративной вычислительной сети. Построение топологической базы данных корпоративной вычислительной сети.

80

3.3 Исследование связей элементов вычислительных сетей на базе связности компонентов графа состояния. 95

3.4 Исследования возможных методов представления результатов построения эффективных маршрутов в памяти ЭВМ. 101

3.5 Анализ алгоритмов поиска маршрутов на графах. 105

ВЫВОДЫ ПО ГЛАВЕ 3._______114

4. РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОЙ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ ИНФОРМАЦИОННЫХ ПОТОКОВ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ.____115

4.1 Создание эффективного подхода и методики динамической маршрутизации информационных потоков в корпоративных вычислительных сетях 115

4.2 Разработка алгоритма поиска на графе состояния вычислительной сети всех нетривиальных маршрутов представляющих собой ориентированные

простые цепи. 117

4.3 Анализ потребностей разработанного алгоритма к ресурсам

вычислительной системы. 119

4.4 Пример функционирования разработанного алгоритма. 128

4.5 Анализ преимуществ предложенного подхода к решению задачи маршрутизации. 132

4.6 Программный инструментарий построения оптимальных маршрутов. 145

ВЫВОДЫ ПО ГЛАВЕ 4._______148

ЗАКЛЮЧЕНИЕ______________149

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ__151

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ МОДУЛЯ РАСЧЁТА МАРШРУТОВ.

158

Введение.

Актуальность работы.

В настоящее время во всём мире вычислительные сети (Internet / Intranet) становятся неотъемлемой частью существования общества. Получают широкое распространение прикладные средства, использующие вычислительные сети в качестве транспортной среды для передачи огромных объёмов информации и требующие при этом гарантированного времени доставки (аудио / видео конференции, "аудио / видео по требованию", компьютерная телефония, ...).

Удовлетворение постоянно растущих потребностей прикладных средств в качестве обслуживания, предоставляемого вычислительными сетями, обеспечивается за счёт развития двух основных направлений в сетевых технологиях.

Первое направление, это увеличение пропускной способности каналов связи. Результатами его развития является внедрение всё более высокоскоростных стандартов передачи данных и ежегодное увеличение количества и пропускной способности каналов связи, объединяющих рабочие места, корпорации, города, страны и континенты.

Вторым направлением является развитее алгоритмического и программного обеспечения, реализующего механизм доставки информационных пакетов. Базовой частью данного обеспечения является модуль маршрутизации, осуществляющий поиск оптимального пути между источником информационных пакетов и их получателями. Улучшить качество маршрутизации в локальных сетях можно за счёт совершенствования принципов нахождения оптимальных маршрутов, учитывающих функциональные потребности современных инструментальных средств. Таким образом, разработка программного инструментария управления маршрутизацией информационных потоков в вычислительных сетях является актуальной научной задачей и соответствует современным тенденциям развития телекоммуникационных технологий.

Цель исследований.

Цель исследований настоящей работы заключается в разработке математического, алгоритмического и программного обеспечения оптимального управления процессом

маршрутизации информационных потоков в корпоративных вычислительных сетях. Задачи исследований.

Для достижения поставленной цели решаются следующие задачи:

• Исследование функциональных возможностей и внутренней архитектуры программных и технических средств межсетевого взаимодействия;

• Исследование современных технологий передачи данных с целью выявления недостатков существующих подходов и методов построения оптимальных маршрутов, снижающих эффективность использования коммуникационных ресурсов корпоративных вычислительных сетей.

• Создание методики построения оптимальных маршрутов для информационных потоков в вычислительных сетях, обеспечивающей эффективное использование коммуникационных ресурсов корпоративных вычислительных сетей.

• Разработка эффективного алгоритма внутренней динамической маршрутизации, увеличивающего функциональные возможности современных средств передачи данных.

• Разработка программного инструментария реализующего предложенную методику и алгоритм.

• Моделирование процесса внутренней динамической маршрутизации на основе разработанного алгоритма на примере спроектированной корпоративной вычислительной сети.

Идея работы.

Основная идея работы состоит в создание эффективного подхода к решению задачи динамической маршрутизации, заключающегося в том, что определение оптимальности того или иного маршрута выносится за рамки алгоритма поиска маршрутов графу. На основе не взвешенного графа состояния вычислительной сети строится полная база маршрутов, которая содержит все нециклические маршруты, соединяющие выбранный узел со всеми остальными узлами вычислительной сета. Определение оптимальности

того или иного маршрута осуществляется путём минимизации суммарной метрики. Методы исследования.

Поставленные в работе задачи решаются методами теории графов и теории открытых систем.

Научная новизна работы.

Научная новизна работы состоит в следующем:

Создан новый подход для построения оптимальных маршрутов информационных потоков в вычислительных сетях, принципиально меняющий методику поиска маршрутов и отличающийся от существующих тем, что определение эффективности того или иного маршрута выносится за рамки механизма поиска маршрутов и определяется на последующем этапе путём сравнения сумм метрик каналов связи, образующих исследуемый маршрут.

Разработан алгоритм поиска маршрутов, в отличие от существующих, позволяющий найти по графу состояния вычислительной сети все ориентированные простые маршруты, соединяющие выбранный узел с остальными узлами вычислительной сети.

Предложена формула динамического расчёта метрик состояния каналов связи, которая, в отличие от существующих, позволяет учитывать экономический фактор при формировании эффективных маршрутов.

Разработан программный инструментарий локальной динамической маршрутизации информационных потоков в вычислительных сетях, реализующий предложенную методику построения оптимальных маршрутов и основанный на предложенном алгоритме поиска маршрутов.

Практическая ценность.

В рамках работы на основе предложенной методики разработан программный инструментарий локальной динамической маршрутизации информационных потоков в вычислительных сетях, областью применения которого являются сложноструктурированные корпоративные вычислительные сети.

Внедрение результатов исследований.

Результаты диссертации в виде разработанных инструментальных средств локальной динамической маршрутизации, приняты к внедрению институтом "Гипроуглеавтоматизация" (Россия) и "Институтом развития измерительной техники" (Россия).

Апробация работы.

Основные положения диссертации докладывались на международном конгрессе microCAD'95 International Computer Science Conference (Miskolc-Egyetemvaros February 23, 1995); Международных симпозиумах: Proceedings of the Fourth International Symposium on Mine Planning and Equipment Selection 1995 (Calgary / Canada / 31 October - 3 November 1995), Третий международный симпозиум "Интеллектуальные системы" (Псков, 30 июня - 4 июля 1998г.); Научно-технической конференции "Диагностика, информатика и метрология - 95" (Санкт-Петербург 4-6 июля 1995 года);

Публикации.

По теме диссертации опубликовано б печатных работ. Объем и структура работы.

Диссертационная работа состоит из введения, четырех глав, заключения, изложенных на 163 стр. текста, включает 41 рисунок, 22 таблицы и список использованных источников из 100 наименований.

1. Исследование инфраструктуры вычислительных

сетей.

В данной главе рассматриваются основные концепции сетевых взаимодействий. Проводится детальный анализ эффективности и функциональных возможностей различных методов построения вычислительных сетей (маршрутизация сегментированных сетей и коммутация сетей с линейным адресным пространством). Исследуются возможности передовой технологии коммутации IP-пакетов на канальном уровне, на предмет целесообразности её применения для построения крупномасштабных вычислительных сетей.

11 Основные концепции сетевых взаимодействий.

Анализ состояния проблемы качества современного коммуникационного сервиса убедительно показывает перспективность решения проблемы увеличения функциональных возможностей и улучшения технических характеристик вычислительных сетей.

Вычислительная сеть представляет собой коммуникационную систему, связывающую между собой оконечные системы (end-systems). Оконечные системы часто называют host-компьютерами.

К сожалению, в теории вычислительных сетей формулировки основных понятий обладают большой степенью гибкости и в различных источниках могут существенно различаться.

Под локальной вычислительной сетью (ЛВС) (LAN - Local Area Network) мы будем понимать объединение компьютерных систем, расположенных недалеко друг от друга (обычно в одном здании). В настоящее время существует множество технологий объединения компьютеров в ЛВС: Token Ring Ethernet, Fast Ethernet, 100VG any LAN, FDDI, ... . В .ЛВС данные, передаются с высокой скоростью (например, в Ethernet скорость передачи составляет 10 Мбит в секунду).

Под глобальной вычислительной сетью (WAN - Wide Area Network) мы будем понимать

сеть, объединяющую между собой компьютеры, расположенные на значительном удалении друг от друга, например, в различных городах. Наиболее распространенными технологией объединения компьютеров в глобальную сеть являются Х.25, Frame Relay, ATM, ISDN, ...

Под межсетевыми связями (internet) мы будем понимать объединение между собой нескольких сетей таким образом, что компьютеры одной сети могут взаимодействовать с компьютерами, принадлежащими другой сети.

Рассмотрим программно-технические средства, позволяющие установить межсетевые связи [4]:

- Повторители. Функционируют на физическом уровне; предназначены для однотипных сетей.

- Мосты. Функционируют на канальном уровне и копируют кадры из одной сети в другую. Мосты часто содержат логику, что позволяет копировать не все кадры, а некоторое подмножество;

•■ Маршрутизаторы. Функционируют на сетевом уровне. Пакеты не только переносятся из одной сети в другую, но и принимается решения о маршруте движения пакетов.

- Шлюзы. Это наиболее общий термин, относящийся к объединению двух и более сетей. Например, в протоколе TCP/IP под шлюзом понимается маршрутизатор сетевого уровня. Иногда под шлюзом понимается программное обеспечение, выполняющее специфические преобразования на уровнях выше сетевого. Например, существуют различные почтовые шлюзы, преобразующие электронную почту из одного формата в другой.

Повторители представляют собой аппаратные устройства, а мосты и маршрутизаторы могут быть выполнены как программным, так и аппаратным способом. Маршрутизатор или мост обычно представляют собой компьютер, выполняющий только эту работу. Однако, почти все реализации операционной системы UNIX позволяют одновременно выступать в роли системы общего назначения и выполнять роль шлюза [56], [58].

Прикладной уровень

I

Уровень представления

4

Уровень сессии

"4

Транспортный уровень

I

Сетевой уровень

4

Канальный уровень

4

Физический уровень

Рис. 1.1 7-и уровневая модель 081.

Исследования методов взаимодействия компьютеров в вычислительных сетях показывает, что основой такого взаимодействия являются протоколы, представляют собой наборы правил и соглашений между участниками сетевого взаимодействия. Высокая сложность протоколов и, соответственно, их реализации привела к разбиению протоколов на уровни. На Рис. 1.1 приведена широко известная модель OSI (Open Systems Interconnections), отражающая состав и иерархию уровней. Модель OSI в литературе часто называют эталонной моделью архитектуры открытых систем. Эта модель была разработана в период с 1977 по 1984 гг. Большинство рассматриваемых в данной работе протоколов, были разработаны ранее этой модели, поэтому их уровни не в полной мере соотносятся с предложенными в модели. Данную модель следует рассматривать как руководство, а не как стандарт. Ближе к рассматриваемым протоколам упрощенная четырехуровневая модель, представленная на Рис. 1.2.

Для описания набора протоколов разных уровней, которые совместно формируют сетевое программное обеспечение одной сети, будем использовать такое понятие как "семейство протоколов". Например, семейство протоколов Internet или семейство протоколов XNS (Xerox Network Systems). В упрощенной четырехуровневой модели эти семейства протоколов занимают два средних прямоугольника (см. Рис. 1.2 ) - это транспортный и сетевой уровни. Такие семейства протоколов могут интегрироваться с различными средствами канального уровня, например Ethernet. В ряде случаев в семейства протоколов входят средства, относящиеся к уровню прикладных процессов, например, в семействе Internet к таким средствам относится элементарный протокол передачи файлов TFTP (Trivial File Transfer Protocol).

Исследования исторических аспектов возникновения семейства протоколов Internet показывают, что в конце 60-х и в 70-ые годы министерство обороны США финансировало разработку сети ARPANET [5]. ARPA - это подразделение министерства обороны Advanced Research Project Agency, именуемое также DARPA (первое "D" от Defence (оборона)). В начале 80-х годов на основе протоколов ARPANET был сформирован стандарт на семейство протоколов. Официальное название этого семейства - "DARPA Internet Protocol Suite" (семейство протоколов DARPA Internet). Часто его называют либо семейством протоколов Internet, либо семейством протоколов TCP/IP,

Прикладной процесс Л

Транспортный уровень А

Сетевой уровень А

Канальный уровень <

Физический уровень (сеть)

Прикладной процесс А

Транспортный уровень А

Сетевой уровень Л

>

1 > Канальный уровень

Рис. 1.2 Упрощенная четырехуровневая модель взаимодействия двух систем.

либо просто TCP/IP [48], [55]. В настоящее время это семейство протоколов применяется очень широко как в локальных, так и в глобальных вычислительных сетях. Существуют реализации этих протоколов практически для всех типов ЭВМ и операционных систем, начиная от персональных компьютеров до супер-ЭВМ. Сети на основе этих протоколов объединяют миллионы компьютеров во всем мире.

Следует подчеркнуть, что основными компонентами данного семейства являются:

TCP Transmission Control Protocol (протокол управления передачей). Протокол, ориентированный на соединения, который обеспечивает надежную полнодуплексную передачу потока байтов между пользовательскими процессами. Большинство прикладных программ в Internet, используют TCP. В связи с тем, что TCP использует при работе протокол IP, семейство протоколов часто называют TCP/IP.

UDP User Datagram Protocol (пользовательский дейтаграммный протокол). Протокол для пользовательских процессов, работающий без установления соединений. В отличие от TCP, который относится к "надежным" протоколам, нет никакой гарантии, что посланная UDP-дейтаграмма когда-нибудь достигнет своего адресата.

ICMP Internet Control Message Protocol (протокол управляющих сообщений Internet).

Протокол поддерживает передачу информации об ошибках и управляющей информации меж�