Содержание к диссертации
Введение
Глава 1 Современное состояние проблемы маршрутизации 11
1.1. Понятие алгоритма маршрутизации 11
1.2. Статическая маршрутизация 14
1.3. Динамическая маршрутизация 18
1.3.1. Дистанционно – векторный алгоритм 20
1.3.2. Алгоритм маршрутизации с учетом состояния каналов 21
1.3.3. Гибридный алгоритм 25
1.4. Маршрутизация на основе математического анализа 26
1.5. Методы на основе нечеткой логики 30
1.6. Современные методы маршрутизации. 32
Глава 2 Разработка интегрированной системы маршрутизации 37
2.1. Параметры алгоритмов маршрутизации 37
2.2 Нейронная сеть и нечеткая логика 40
2.3. Современные маршрутизаторы 45
2.3.1. Анализ архитектур маршрутизаторов 47
2.3.2 Интегрированная система маршрутизации 50
Глава 3 Исследование интегрированной системы маршрутизации 54
3.1 Исследование процесса маршрутизации известными 54
методами 54
3.2 Исследование сети с помощью ИСМ 69
Глава 4 Моделирование маршрутизации в компьютерных сетях с использованием ИСМ 83
4.1. Анализ работы ИСМ в компьютерной сети 83
4.2. Сравнение со стандартными протоколами RIP и OSPF 91
4.2.1. Внутренний протокол маршрутизации RIP 91
4.2.2. Протокол состояния связей OSPF 92
4.2.3. Сравнение протоколов – RIP и OSPF – по затратам – на широковещательный трафик 94
4.2.4. Сравнение работы простой сети и с применением ИСМ 96
4.3. Маршрутизация пакетов с учетом важности сообщений 103
4.4. Протокол РРР с использованием ИСМ 114
4.5. Применение ИСМ для распределения потока данных 118
Заключение 129
Список используемой литературы 132
- Динамическая маршрутизация
- Нейронная сеть и нечеткая логика
- Исследование сети с помощью ИСМ
- Сравнение протоколов – RIP и OSPF – по затратам – на широковещательный трафик
Введение к работе
Актуальность темы
Развитие компьютерных сетей приводит к усложнению их топологии. Эта тенденция ведет к необходимости разработки новых подходов к организации маршрутизации в компьютерных сетях
Главная задача маршрутизации - это повышение скорости передачи данных в компьютерных сетях. Наиболее часто критерием выбора маршрута является время передачи данных, которое зависит от многих факторов: пропускной способности каналов, интенсивности трафика, который может изменяться с течением времени, загрузки интерфейса буфера и.т.д. Сложность проблемы маршрутизации заключается в ее многофакторности. Учет всех факторов сводит задачу маршрутизации к решению задачи оптимального распределения ресурсов сети. Значительный вклад в решение проблемы маршрутизации внесли отечественные и зарубежные ученые: В.Г. Олифер, Н.А. Олифер, Брайн Хилл, Столингс В., Стивен Браун, Оливер Ибе, Лихтциндер Б.Я., Росляков А.В., Мэтт Хайден и другие.
Существующее методы выбора маршрута с помошью аналитических методов не всегда приводят к эффективному решению. В связи с этим одним из перспективных направлений в решении задачи маршрутизации является использование нечеткой логики и нейронных сетей. В настоящее время, очень много ученых работают в данной области это Дельгадо М., Стивен Дж., Малколм Сю,. Сотник С. Л., Макеев А.С. и другие.
Совместное использование нечеткой логики и нейронной сети в решении вопросов маршрутизации обеспечивает следующие преимущества: возможность нечеткой формализации критериев оценки и сравнения; проведение качественных оценок, как входных данных, так и выходных результатов; разрешает оперировать степенью достоверности данных с использованием их при распределении потока информации; позволяет проводить сравнительный анализ с заданной точностью; допускает быстрое моделирование заданных систем и автоматизацию процесса определения маршрута.
Актуальность данной работы связана с отсутствием эффективных методов поиска маршрутов в сложных компьютерных сетях и необходимостью разработки инструмента оперативного моделирования состояния каналов сети.
Работа соответствует паспорту специальности 05.13.15. «Вычислительные машины, комплексы и компьютерные сети» п. 2 «Теоретический анализ и экспериментальное исследование функционирования вычислительных машин, комплексов и компьютерных сетей с целью улучшения их технико-экономических и эксплуатационных характеристик».
Цель работы: разработка и исследование интегрированной системы маршрутизации (ИСМ), с совместным использованием нечеткой логики, нейронных сетей и стандартных маршрутизаторов для нахождения оптимальных маршрутов передачи пакетов в сложных компьютерных сетях.
Основные задачи исследования: анализ существующих алгоритмов маршрутизации в компьютерных сетях (КС) для решения задачи ускорения прохождения пакетов;
разработка современного подхода, основанного на методах интеллектуального анализа данных;
разработка интегрированной системы маршрутизации, с совместным использованием нечеткой логики (НЛ), нейронных сетей (НС) и стандартных маршрутизаторов для компьютерных сетей;
разработка и исследование методов моделирования маршрутизации в сетях различной топологии;
обоснование области эффективного применения предложенной ИСМ.
Методы исследования
В работе использовались теория графов, теория нечетких систем, методы имитационного моделирования, методы математической статистики, теория искусственных нейронных сетей, эволюционные алгоритмы. Исследование разработанных в работе алгоритмов обработки данных проводилось с использованием пакетов MATLAB, Statistica, OPNET и разработанного автором программного обеспечения.
Научная новизна заключается в том, что:
Предложена интегрированная система маршрутизации, отличающаяся совместным использованием стандартных маршрутизаторов, подсистемы нечеткой логики и нечеткого вывода, что позволяет находить оптимальные по критерию времени маршруты передачи пакетов в компьютерных сетях.
Предложено новое представление объема трафика в виде нечеткой величины и разработана формализованная модель сети, позволяющая оперировать прогнозируемыми данными о трафике и вычислительной загрузке сети.
Предложена методика исследования процессов маршрутизации в компьютерных сетях, отличающаяся совместным использованием нечеткой логики и нейронных сетей как инструмента моделирования.
Достоверность результатов работы
Достоверность научных положений рекомендаций и выводов подтверждена путем сравнения статистического материала, собранного в процессе мониторинга реальной сети, с результатами моделирования аналогичной сети в разработанной программной среде.
Личный вклад: предложена Интегральная система маршрутизации, теоретическое и практическое исследование процессов маршрутизации с помощью совместного использования нечеткой логики и нейронной сети, применение нечеткой логики и нейронной сети как инструмент для моделирования. Основные положения, выносимые на защиту
Интегрированная система маршрутизации, отличающаяся совместным использованием стандартных маршрутизаторов, подсистемы нечеткой логики и нечеткого вывода.
Новое представление объема трафика в виде нечеткой величины и формализованная модель сети, позволяющая оперировать прогнозируемыми данными о трафике и вычислительной загрузке сети.
3. Методика исследования процессов маршрутизации в компьютерных сетях, отличающаяся совместным использованием нечеткой логики и нейронных сетей как инструмента моделирования.
Практическая ценность работы:
разработана интегрированная система маршрутизации, которая обеспечивает ускорение процесса передачи данных в многосегментных компьютерных сетях;
предложенный метод маршрутизации в КС на основе ИСМ обеспечивает повышение эффективности доставки пакетов для сетей сложной конфигурации в условиях локальных перегрузок;
разработанные методы моделирования на основе нейронных сетей и нечеткой логики позволяют исследовать различные классы компьютерных сетей.
Реализация результатов работы
Основные результаты, полученные в ходе работы над диссертацией, использовались при создании компьютерных сетей ООО «Волготехпласт», 000 «Самара - Авиагаз», ОАО СЗ «Экран» для определения загруженности сети, управления трафиком и распределения данных по сети. Результаты исследований также используются в учебном процессе и подтверждены актами о внедрении. Апробация работы
Основные положения, теоретические выводы и практические рекомендации диссертационной работы докладывались и обсуждались на заседаниях кафедры «Информатика и вычислительная техника» ФГОБУ ВПО ПГУТИ, а также на конференциях и семинарах различного уровня:: XV Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара 2008; XVI Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара 2009; XVII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара 2010; XVIII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов Самара 2011; X Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения», Пенза 2009; XI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения», Пенза 2009; XII Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения», Пенза 2010,
Публикации
По теме диссертации опубликовано 14 печатных работ, в том числе 4 статьи в научных журналах, входящих в перечень ВАК РФ, 3 научных статьи на Международных конференциях, 7 тезисов и докладов.
Структура и объем диссертации. Диссертационная работа состоит из введения 4 глав и заключения, изложенных на 125 страницах машинописного текста, содержит 79 рисунков, 14 таблиц, список литературы из 105 наименований.
Динамическая маршрутизация
В литературе [52, 60, 67] рассматриваются протоколы маршрутизации. Протоколы маршрутизации генерируют для каждого маршрутизатора согласованные таблицы маршрутизации, такие, которые позволят обеспечить доставку пакета по рациональному маршруту от исходной сети в сеть назначения за конечное число шагов. Для этого маршрутизаторы сети обмениваются специальной информацией о топологии сети. Различают статистическую и адаптивную (динамическую) маршрутизацию.
Статическая маршрутизация основана на наблюдении, когда известны все сети, информация о которых сообщается маршрутизатору. Достаточно ввести все данных о конфигурации вручную. Метод статической маршрутизации довольно прост. Все записи в таблице имеют статус статических, т.е бесконечный срок жизни [67]. Неудобство состоит в том, что если меняется конфигурация сети, то необходимо срочно менять записи в таблице маршрутизации. Хотя метод прост, но передача данных остается слабым звеном. Для того, чтобы передача состоялась, необходимо добиться, чтобы в каждом маршрутизаторе имелись все данные о маршруте.
При статической маршрутизации вся известная системе маршрутная информация загружается в таблицу маршрутизации диспетчером [65]. При этом вводятся не все возможные пути, а только те, которые будут реально использоваться. Статическая маршрутизация выполняет функцию принятия решения в автономном режиме и использует протоколы маршрутизации для заполнения таблиц в каждой системе.
Используя статическую маршрутизацию, появляется возможность выполнять сложные автономные алгоритмы маршрутизации, поскольку при ретрансляции протокольных блоков сетевого уровня нет необходимости вычислять маршрут в реальном времени.
Во избежание возможных неполадок при реализации статической маршрутизации необходимо учитывать следующие вопросы.
Конфигурация периферийного маршрутизатора. Чтобы упростить конфигурацию, можно задать на периферийных маршрутизаторах маршрут по умолчанию, ведущий к соседствующему маршрутизатору. Периферийный маршрутизатор — это маршрутизатор, подключенный к нескольким сетям, лишь в одной из которых имеется соседствующий маршрутизатор. Маршруты по умолчанию и циклические маршруты.
Авторы [50-55, 60] рекомендуют не задавать на двух соседствующих маршрутизаторах маршруты по умолчанию друг к другу. Маршрут по умолчанию передает весь трафик, не предназначенный для непосредственно подключенной сети, на указанный маршрутизатор. Два маршрутизатора, заданные в маршрутах по умолчанию друг друга, могут образовывать циклы маршрутизации, делая невозможной доставку трафика узлам назначения.
Достоинства статической маршрутизации проявляются в полной мере в малых сетях. Она позволяет достаточно оперативно развернуть локальную сеть без затраты дополнительного времени на конфигурирование протоколов маршрутизации, а также снизить нагрузку на маршрутизатор за счет использования данных таблиц маршрутизации. Однако, при масштабировании или изменении топологии такой сети, могут возникнуть проблемы с ее администрированием. Проблемы возникают, потому что статические маршрутизаторы не обмениваются информацией друг с другом и не сообщают о наличии сбоя в каком-либо из маршрутизаторов или в канале связи. Внесение изменений в конфигурацию таблиц занимает много времени, что в разы снижает эффективность сети со статической маршрутизацией. [52]
Недостатками статической маршрутизации являются следующие показатели:
Отсутствие отказоустойчивости. Если в силу каких-либо причин один из маршрутизаторов выходит из строя или становится недоступным коммуникационный канал, статический маршрутизатор не сможет как-то отреагировать на неисправность. Более того, другие маршрутизаторы в сети не зная о неисправности, будут продолжать передавать данные по недоступному маршруту (статус down). В сетях малого офиса (например, с двумя маршрутизаторами и тремя сетями, соединенными в ЛВС) подобные ситуации могут решаться администратором оперативно. В крупных сетях более предпочтительным оказывается использование специальных протоколов маршрутизации;
Непроизводительные административные затраты. Если добавляется новая подсеть или удаляется из межсетевой среды существующая, маршруты к ней должны быть вручную добавлены или удалены. Если добавляется новый маршрутизатор, то он должен быть правильно сконфигурирован для маршрутизации в межсетевой среде.
Лёгкость отладки и конфигурирования в малых сетях. Очень плохое масштабирование (добавление N+1 сети потребует сделать 2 (N+1) записей о маршрутах, причём на большинстве маршрутизаторов таблица маршрутов будет различной, при N 3-4 процесс конфигурирования становится весьма трудоёмким).
Отсутствие дополнительных накладных расходов (из-за отсутствия протоколов маршрутизации). Низкая устойчивость к повреждениям линий связи (особенно, в ситуациях, когда обрыв происходит между устройствами второго уровня и порт маршрутизатора не получает статус down)
Низкая нагрузка на процессор маршрутизатора Отсутствие динамического балансирования нагрузки
Мгновенная готовность (не требуется интервал для конфигурирования/подстройки) Необходимость в ведении отдельной документации к маршрутам, проблема синхронизации документации и реальных маршрутов.
Предсказуемость в каждый момент времени Статически маршрутизируемая среда лучше всего подходит для небольшой сети с редко изменяющейся структурой, в которой отсутствуют альтернативные маршруты. Такая среда может применяться для сети малого предприятия, домашнего офиса или филиала с одной сетью.
В реальных условиях статическая маршрутизация используется в условиях наличия шлюза по умолчанию (узла, обладающего связностью с остальными узлами) и 1-2 сетями. Помимо этого статическая маршрутизация используется для "выравнивания" работы маршрутизирующих протоколов в условиях наличия туннеля (для того, чтобы маршрутизация трафика, создаваемого туннелем, не производилась через сам туннель).
Протоколы позволяют автоматически удалять из таблицы недействительные маршруты при возникновении отказа канала (прямого или непрямого). После получения информации о лучшем маршруте они автоматически вводят данные о нем в таблицу и устраняют маршрутные петли. Протокол динамической маршрутизации позволяет маршрутизатору через регулярные интервалы автоматически сообщать другим маршрутизаторам обо всех известных ему маршрутах. Применяемые при этом «информационные» пакеты именуются анонсами или обновлениями маршрутов, в зависимости от того, в каком конкретно протоколе они используются. Такие данные позволяют всем маршрутизаторам автоматически собирать сведения обо всех маршрутах (основных и резервных).
Вывод: динамические (адаптивные) алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в масштабе реального времени. Они выполняют это путем анализа поступающих сообщений об обновлении маршрутизации. Обеспечивают реакцию на неисправности и перегрузки. Достоинства:
Нейронная сеть и нечеткая логика
Надежность - определяется интенсивностью ошибок на каждом сетевом соединении. Важным фактором повышения надежности сетевого взаимодействия является наличие нескольких маршрутов с одним и тем же информационным ресурсом. В случае отказа одного из них можно использовать другие.
Нагрузка определяет объем трафика, проходящего в среднем по каналу с определенной пропускной способностью. Нагрузка позволяет определить, насколько недогружен или перезагружен канал. Пропускная способность определяет наименьшую номинальную пропускную способность протокола, которая используется по всему маршруту и обычно задается вручную.
IP маршрутизация это краеугольный камень, на котором держится функционирование систем, использующих TCP/IP, будь то хост или маршрутизатор [65, 66]. Записи в таблице маршрутизации довольно просты: до 5 флаговых битов, IP адрес назначения (хост, сеть или по умолчанию), IP адрес маршрутизатора следующей пересылки (для непрямого маршрута) или IP адрес локального интерфейса (для прямого маршрута) и указатель на используемый локальный интерфейс. Записи, соответствующие хостам, имеют более высокий приоритет, чем записи, соответствующие сетям, а оба типа записей имеют более высокий приоритет по сравнению с маршрутом по умолчанию.
Просмотр таблицы маршрутизации осуществляется для каждой IP дейтаграммы, которую система генерирует или пропускает через себя. Таблица маршрутизации может быть обновлена с помощью демона маршрутизации или ICMP (Internet Control Messaging Protocol – протокола управления сообщениями Internet) перенаправления. По умолчанию система никогда не пропустит через себя дейтаграмму, если система не сконфигурирована, как маршрутизатор.
Вопросы маршрутизации до сих пор остаются плодотворной почвой для исследований в области межсетевого взаимодействия. Поэтому выбрать, какой протокол маршрутизации необходимо использовать, и какой домен маршрутизации необходимо запустить, довольно сложно.
Исходя из выше изложенного, алгоритм выбора маршрута должен обладать следующими свойствами: правильностью, простотой, надежностью, устойчивостью, справедливостью и оптимальность. Правильность и простота – это очевидные факты, а вот надежность не столь очевидна. За период работы большой сети постоянно происходят различные отказы в оборудовании и изменения в самой сети. Алгоритм маршрутизации должен уметь справляться с такими изменениями без прекращения всех задач на всех оконечных системах и перезагрузки сети при каждом сбое аппаратуры. Поэтому применение нейронной сети в сочетании с нечеткой логикой является наиболее эффективным с точки зрения получения новых качеств маршрутизаторов. 2.2 Нейронная сеть и нечеткая логика
В литературе [16, 23, 24, 69] говорится, что нейронные сети хороши для распознавания образов, но весьма неудобны для выяснения вопросов, как они такое распознавание осуществляют. Они могут автоматически приобретать знания, но процесс их обучения весьма сложен и медленен.
Системы с нечеткой логикой напротив, хороши для объяснения полученного результата, но они не могут автоматически приобретать знания для использования их в механизмах вывода. Если рассматривать теоретические системы с нечеткой логикой и искусственные нейронные сети, то можно прийти к выводу, что они эквивалентны друг другу. Это соображение и легло в основу интегральной системы маршрутизации (ИСМ). В ИСМ выводы делаются с помощью нечеткой логики, а функции принадлежности подстраиваются с использованием алгоритмов обучения нейронных сетей.
Нейрокомпьютерные сети позволяют эффективно использовать аппарат, определяющий их аппроксимирующую способность. С помощью нейронных сетей можно выразить любую непрерывную функциональную зависимость без предварительной аналитической работы по выявлению правил зависимость выхода от входа. Недостатком является невозможность объяснить выходной результат, так как значения нейронов определены в виде коэффициентов весов.
В связи с этим применение нечетких интеллектуальных систем оправдано. Ассоциативному мышлению адекватны логические нейронные сети, создаваемые на основе логического описания системы управления или принятия решений в терминах алгебры высказываний. Если система принятия решений функционально полностью определена и может быть описана в терминах математической логики, то по этому описанию целесообразно строить нейронную сеть. С помощью логических построений легко построить объяснение результата в форме протокола рассуждений. Поэтому эти сети наиболее интересны в вопросах исследования. Они сочетают в себе преимущества нечетких систем и нейронных сетей. [5]
Примером таких технологий служит реализация системы нечетких правил на основе нейросети. Набор нечетких правил для двух входных и одной выходной переменных имеет следующую структуру [6]:
Один из способов представления нечеткого понятия в виде четких данных состоит в представлении нечеткого множества в виде – срезов (см. Рисунок 2.1). При этом использовании – срез представляется в виде подмножеств j где j – номер среза с двумя границами L и R, т.е. – срезы четко представляют непрерывную функцию принадлежности.
Подобные системы являются довольно эффективным средством системного моделирования и группового мониторинга. Наиболее подходящими для применения данных методов являются групповые процессы с сильной нелинейностью и сложным регулированием.
В настоящей работе предлагается построить ИСМ с совместным использованием трех подсистем: аналитической, нечеткой логики и нейронной сети. Использование такой структуры в решении вопросов маршрутизации обеспечивает следующие преимущества: возможность нечеткой формализации критериев оценки и сравнения; предусматривает проведение качественных оценок как входных данных, так и выходных результатов; разрешает оперировать степенью достоверности данных с использованием их при распределении потока информации; позволяет проводить сравнительный анализ с заданной точностью для построения систем; допускает быстрое моделирование заданных систем и автоматизацию процесса определения маршрута.
Работа нейронной сети (НС) построена на отказе от точных численных значений в пользу нечетких, но содержательных оценок, которые позволяют принять осмысленное решение. Если рассматривать функционирование НС как управление объектом, то инструментарий экспертизы можно использовать как управление объектом, и представить ее в виде структурной схемы (см. Рисунок 2. 2).
Исследование сети с помощью ИСМ
Каждое правило базы знаний представляется в виде последовательности горизонтально расположенных кривых. При этом первые две кривые отображают функции принадлежностей термов посылки правила (ЕСЛИ - часть правила), а последняя кривая соответствует функции принадлежности терма-следствия выходной переменной (ТО-часть правила). Пустой часть в визуализации второго правила означает, что в этом правиле посылка по переменной отсутствует. Желтая заливка графиков функций принадлежностей входных переменных указывает насколько значения входов, соответствуют термам данного правила. Заливка графика функции голубым цветом принадлежности выходной переменной представляет собой результат логического вывода в виде нечеткого множества по данному правилу. Результирующее нечеткое множество, соответствующее логическому выводу по всем правилам показано в нижнем прямоугольнике последнего столбца графического окна. В этом же прямоугольнике красная вертикальная линия соответствует четкому значению логического вывода, полученного в результате дефаззификации.
Поверхность «входы» и «выходы» для системы определяющие выбор маршрута в сети в зависимости от входных параметров По графику можно сделать вывод, что нечеткие правила достаточно хорошо описывают сложную нелинейную зависимость.
По данным полученным при расчете системы нечеткого логического вывода построим НС, которая – является адаптивной системой, состоящей из узлов и направленных связей. Часть или совокупность узлов являются адаптивными, что предполагает зависимость каждого выхода таких узлов от соответствующих параметров по правилам, определяющим изменение данных параметров, минимизирующих ошибки [84].
Для формирования заранее заданных входо-выходных пар система позволяет построить множество нечетких правил «если – то» с подходящими функциями принадлежности. На основе заданной системы осуществим оптимизацию функций принадлежности и системы логического вывода.
В нашем случае система состоит из четырех уровней. На первом уровне каждый узел оценивает степени принадлежности лингвистических переменных данным правилам на основе гауссовской функции Слой 1 (inputmf) представлен радиальными базисными нейронами и моделирует функции принадлежности Выходы узлов этого слоя представляют собой значения функции принадлежности при конкретных значения входов (х1, х2), терм множества (x1 К, КС, МК; x2 Т, ТС, МТ).
Количество элементов этого слоя определяется количеством нечетких правил. Значения с первого слоя поступают на входы скрытого второго слоя гибридной сети. Определение количества нейронов в скрытом слое является очень важной частью реализации общей структуры нейронной сети. На этом этапе рассчитывается нормированная сила правила (i) (3.12).
Загружаем все данные в сеть и протестируем их. При задании параметров посылок, общий выходной сигнал можно выразить в виде линейной комбинации параметров заключений. При обучении использован обучающий алгоритм, состоящий из прямого и обратного проходов. Во время прямого прохода функциональные сигналы проходят до уровня 4, а параметры заключения идентифицируются с помощью среднеквадратичной оценки (СКО). Во время обратного прохода оценки ошибок возвращаются, и осуществляется корректировка параметров посылок методом градиентного спуска.
Отображение результата нечеткого вывода В соответствии с правилами поменялась структура сети. Второй слой теперь состоит из 9 правил, соответственно увеличилось количество нейронов, которые управляют работой гибридной системой (см. Рисунок 3. 19). Рисунок 3. 19 Структура системы после обучения После обучения и преобразования система готова к работе. Результат решений в виде поверхностей входов и выходов (см. Рисунок 3. 20) позволяет выбрать оптимальный маршрут для прохождения пакетов по сети, согласно заданным условиям.
С помощью ИСМ для каждого типа событий есть возможность разработать алгоритм обработки, отражающий специфику реакции маршрутизатора на данное событие, изменение характеристик элементов сети и возникновение последующих событий, обусловленных данных. Время обработки таких событий можно подсчитать по формуле (3.15): среднее время настройки гибридной системы. Так как подобного оборудования пока в производстве нет, берем среднее время обработки данных компьютером последнего поколения, равное 65 мкс; 340 мкс- время, затраченное на продвижение пакета в одну сторону, полученное по расчетам сделанным с помощью ИСМ. Время обработки события в среднем будет равно, 851 мкс. Время обработки пакета сети с применением стандартного маршрутизатора (3.16) время, затраченное на продвижение пакета в одну сторону и полученное с помощью алгоритма Дейкстры, будет равен 1086 мкс. При этом выигрыш по времени в предложенной системе маршрутизации составляет 20 %.
Сравнение протоколов – RIP и OSPF – по затратам – на широковещательный трафик
Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы всем соседям -маршрутизаторам, с которыми связан непосредственно. Маршрутизатор -получатель просматривает таблицу. Если в таблице присутствует новый путь или сообщение о более коротком маршруте, или произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице. Протокол RIP должен быть способен обрабатывать три типа ошибок:
Несоответствие маршрутной таблицы реальной ситуации типично для RIP, т.к. информационные сообщения актуализации несут в себе только пары кодов: адрес места назначение и расстояние до него[19, 65].
Протокол OSPF (Open Shortest Path Firs) является реализацией алгоритма состояния связей (он принят в 1991 году) и обладает многими особенностями, ориентированными на применение в больших гетерогенных сетях. Протокол OSPF вычисляет маршруты в IP-сетях, сохраняя при этом другие протоколы обмена маршрутной информацией.
Непосредственно связанные маршрутизаторы называются "соседями". Каждый маршрутизатор хранит информацию о том, в каком состоянии, по его мнению, находится сосед. Маршрутизатор полагается на соседние маршрутизаторы и передает им пакеты данных только в том случае, если он уверен, что они полностью работоспособны. Для выяснения состояния связей маршрутизаторы-соседи достаточно часто обмениваются короткими сообщениями HELLO.
Для распространения по сети данных о состоянии связей маршрутизаторы обмениваются сообщениями другого типа. Эти сообщения называются router links advertisement - объявление о связях маршрутизатора (точнее, о состоянии связей). OSPF-маршрутизаторы обмениваются не только своими, но и чужими объявлениями о связях, получая в конце концов информацию о состоянии всех связей сети. Эта информация и образует граф связей сети, который, естественно, один и тот же для всех маршрутизаторов сети.
Кроме информации о соседях, маршрутизатор в своем объявлении перечисляет IP-подсети, с которыми он связан непосредственно, поэтому после получения информации о графе связей сети, вычисление маршрута до каждой сети производится непосредственно по этому графу по алгоритму Дэйкстры. Более точно, маршрутизатор вычисляет путь не до конкретной сети, а до маршрутизатора, к которому эта сеть подключена. Каждый маршрутизатор имеет уникальный идентификатор, который передается в объявлении о состояниях связей. Маршрутизатор вычисляет оптимальный маршрут до каждой адресуемой сети, но запоминает только первый промежуточный маршрутизатор из каждого маршрута. Таким образом, результатом вычислений оптимальных маршрутов является список строк, в которых указывается номер сети и идентификатор маршрутизатора, которому нужно переслать пакет для этой сети. Указанный список маршрутов и является маршрутной таблицей [50,66].
В сетях, где используется протокол RIP, накладные расходы на обмен маршрутной информацией строго фиксированы. Если в сети имеется определенное число маршрутизаторов, то трафик, создаваемый передаваемой маршрутной информацией, описываются формулой (4.1)): F = (число объявляемых маршрутов/25) x 528 (байтов в сообщении) x(число копий в единицу времени) x 8 (битов в байте) (4.1)
В сети с протоколом OSPF загрузка при неизменном состоянии линий связи создается сообщениями HELLO и обновленными объявлениями о состоянии связей, что описывается формулой (4.2):
Интенсивность посылки сообщений HELLO – каждые 10 секунд, объявлений о состоянии связей – каждые полчаса. По связям "точка-точка" или по широковещательным локальным сетям в единицу времени посылается только одна копия сообщения, по NBMA сетям типа frame relay каждому соседу посылается своя копия сообщения. В сети frame relay с 10 соседними маршрутизаторами и 100 маршрутами в сети (подразумевается, что каждый маршрут представляет собой отдельное OSPF – обобщение о сетевых связях и что RIP распространяет информацию о всех этих маршрутах) трафик маршрутной информации определяется соотношениями (4.3) и (4.4):
