Содержание к диссертации
Введение
Глава 1. Анализ существующих методов и алгоритмов распределения нформационных потоков 17
1.1 Промышленные протоколы маршрутизации- 17
1.111' Дистанционно-векторный протокол RIP 18
1.1.2 Протокол состояния связей OSPF 19
1.1.3 Протокол EIGRP 21
1.2 Графовые алгоритмы поиска оптимальных маршрутов 24
1.2.1 Алгоритм Дейкстры 26
1.2.2 Алгоритм Флойда 27
1.2.3 Поиск К-кратчайших путей (метод Дж.Иена) 28
1.2.4 Задача о максимальном потоке в сети 32
1.2.5 Задача нахождения потока наименьшей стоимости 35
1.3 Расчет маршрутов методами математического программирования 38
1.3.1 Формулирование сетевых задач в терминах связей и путей 38
1.3.2 Формулирование сетевых задач в терминах узлов и связей 40
1.3.3 Решение некоторых сетевых оптимизационных задач методом математического программирования 42
1.4 Методы реализации многопутевой маршрутизации. Технология MPLS 45
1.4.1 Протокол распространения меток LDP 46
1.4.2 Задача выбора оптимальных маршрутов 47
1.4.3 Технология Traffic Engineering 50
1.4.4 Механизмы MPLS, реализующие Traffic Engineering 54
1.5 Полнооптические сети с коммутацией каналов. Технология GMPLS 56
1.5.1 Сеть оптической коммутации блоков (OBS) 57
1.5.2 Технология DWDM 59
1.5.3 Архитектурные решения коммутационного устройства узла сети 60
1.5.4 Алгоритмы установления канала связи 65
1.5.5 Существующие методы распределения потоков в сети OBS-..'. 71
1.6 Постановка задачи поиска оптимальных маршрутов в полнооптических етях с канальной коммутацией 74
1.7 Выводы по главе 1 77
Глава 2. Разработка алгоритма оптимального распределения информации, сетях с канальной коммутацией 79
2.1 Формулирование оптимизационной-задачи 79
2.2 Решение оптимизационной задачи градиентным методом 86
2.3 Решение оптимизационной задачи симплекс-методом 94
2.4 Алгоритм поиска маршрутов из найденного вектора распределения сетевого трафика 96
2.5 Разработка алгоритма конроля девиации сетевого потока 99
2.6 Выводы по главе 2 104
Глава 3. Разработка модели алгоритма динамической маршрутизации в етях GMPLS с канальной коммутацией 106
3.1 Объекты сети оптической коммутации блоков 106
3.2 Протокол установления маршрутных туннелей CR-LDP 108
3.3 Алгоритм расчета текущей нагрузки вдоль MP-BGP-сессии 109
3.4 Повышение отказоустойчивости сети. Алгоритм расчета запасных маршрутов 114
3.5 Функциональная схема разработанной модели алгоритма динамической* многопутевой маршрутизации 118
3.6 Оптимизация распределения нагрузки городской сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком» 122
3.6.1 Постановка задачи оптимального распределения трафика 122
3.6.2 Модификация алгоритма расчета оптимальных маршрутов для сетей с пакетной коммутацией 126
3.7 Выводы по главе 3 128
Глава 4. Разработка имитационной модели сети GMPLS и моделирование разработанного алгоритма динамической маршрутизации 130
4.1 Разработка модели сети оптической коммутации блоков 130
4.1.1 Модуль протокола установления канала связи 131
4.1.2 Модуль оптической DWDM-линии 136
4.1.3 Модуль фотонного коммутатора, коммутационный алгоритм 137
4.1.4 Модуль имитации агента- источника блоков данных 139
4.1.5 Сбор статистики и формирование результатов моделирования 141
4.2 Имитационное моделирование сети оптической коммутации блоков 142
4.3 Оптимальное распределение трафика в сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком» 150
4.4 Выводы по главе 4 157
Заключение 159
Список использованной литературы 162
- Формулирование сетевых задач в терминах узлов и связей
- Постановка задачи поиска оптимальных маршрутов в полнооптических етях с канальной коммутацией
- Алгоритм поиска маршрутов из найденного вектора распределения сетевого трафика
- Функциональная схема разработанной модели алгоритма динамической* многопутевой маршрутизации
Введение к работе
Когда необходимо доставить сетевой трафик из точки-А в точку Б, ни
один способ не подойдет всем приложениям сразу. Голосовым и видеоприло
жениям требуется минимальная вариация задержки, в то время как критически
важным приложениям - жесткие гарантии предоставления сервиса и резервных
маршрутов: '
До сих пор необходимые многим приложениям дифференцированные услуги и гарантии предоставляли только сети с коммутацией каналов. Однако-с появлением технологии мультипротокольной коммутации с заменой* меток-(Multiprotocol' Label Switching, MPLS) ситуация изменилась. MPLS позволяет поддерживать все упомянутые приложения в сети IP без необходимости-вводить в значительных областях сети иные транспортные механизмы, протоколы маршрутизации и планы адресации.
Известно, что все протоколы маршрутизации — как дистанционно-векторные (например, RIP), так и состояния связей (OSPF и IS-IS), определяют для трафика, направленного в конкретную сеть, кратчайший маршрут в соответствии с некоторой метрикой. Выбранный путь может быть более рациональным, если в расчет принимается номинальная пропускная способность каналов связи или вносимые ими задержки, либо менее рациональным, если учитывается только количество промежуточных маршрутизаторов между исходной и конечной сетями, но в любом случае выбирается единственный* маршрут даже при наличии нескольких альтернативных.
В" противоположность этому технология MPLS с расширениями Traffic Engineering.(MPLS ТЕ) позволяет применить многопутевые методы маршрутизации, что дает возможность решать практически любые сетевые задачи (максимальное использование каналов, обеспечение качества обслуживания, резервирование, дизайн и т.п.).
Методы расчета многопутевых маршрутов были известны задолго до появления технологии MPLS (Клейнрокк Л., Jackson J.R., Little J.D.C.,
8 В.М.Вишневский, Е.В:Левнер; Е.В.Федотов и др.). Однако в промышленных сетях передачи данных многопутевое распределение трафика почти не применялось из-за сложностей ее практической реализации.
Для сетей пакетной коммутации наиболее известным методом расчета оптимальных многопутевых маршрутов является1 алгоритм, впервые предложенный в работе Л.Фратта, М.Герла и Л." Клейнрока [94]. Ими. была изучена модель сети пакетной коммутации в>виде сети массового обслуживания, в которых узльг описываются системой М/М/1/. Для данной модели была найдена взаимосвязь.между нагрузкой на сеть и величиной средней задержки пакетові в сети. Указанная взаимосвязь дала возможность сформулировать и решить .сетевую оптимизационную задачу, позволяющую найти между всеми парами источник/получатель такой набор многопутевых маршрутов, при котором суммарные задержки пакетов в сети были бы минимальны.
Однако в сетях с большим количеством альтернативных маршрутов при-использовании данного метода наблюдается неконтролируемая девиация (расщепление) потока между каждой парой источник/получатель вдоль множества найденных маршрутов, что объясняется отсутствием ограничения на количество используемых маршрутов. Этот эффект затрудняет реализацию метода в сетях MPLS/GMPLS, так как для каждой пары источник/получатель (которой является MP-BGP-сессия) в этом случае необходимо будет создать большое количество отдельных ЬБР'-туннелей (Label Switch Path - путь коммутации меток), что значительно усложняет управляемость сетью. Для устранения данной проблемы, необходима разработка алгоритма поиска оптимальных маршрутов, позволяющего ввести ограничение на число используемых параллельных маршрутов.
Упомянутая методика предназначена для работы исключительно в пакетных сетях. Что же касается сетей с канальной коммутацией, то величина задержки передаваемого в них трафика - фиксированная и определяется лишь конечной скоростью распространения информационного сигнала, а процессы
1 LSP-туннели являются способом задания многопутевых маршрутов в сетях MPLS
9 передачи трафика описываются многоканальными системами массового1 обслуживания, поэтому приведенная методика к ним неприменима. Для сетей с канальной коммутацией необходимы иные методы оптимальной маршрутизации.
Оптимизационные задачи, формулируемые для сетей с канальной коммутацией, в основном связаны с нахождением 1) минимально необходимого количества выходов коммутационной системы при заданной поступающей нагрузке, 2) емкости коммутационных устройств, а так же 3) оптимального распределения межстанционной нагрузки (метод эквивалентных замен, метод укрупнения, состояний пучков и т.п.), и носят довольно статичный характер. То есть после расчета оптимальных параметров коммутационной системы, рассчитанные* параметры остаются-.неизменными до тех пор, пока сеть не претерпит существенных изменений (напр. изменится емкость межстанционных связей или емкость самого коммутационного устройства). В современных сетях с канальной коммутацией в целях адекватного реагирования на изменения нагрузки в сети необходима разработка новых алгоритмов адаптивной маршрутизации, позволяющих адекватно и быстро реагировать на изменения нагрузки в сети и обеспечивать как надежность передачи информации, так и необходимую пропускную способность. При этом критерием оптимальности алгоритма маршрутизации для сетей с коммутацией каналов может служить величина потеры вызовов, а так же пропускная способность сети..
Успех MPLS дал толчок для создания универсальной технологии коммутации с использованием меток. Новая технология получила название Generalized MPLS (GMPLS - обобщенный MPLS). Она расширяет и унифицирует функции (маршрутизации и сигнализации) MPLS для любых транспортных технологий канального и физического уровней. В частности, появление технологии плотного волнового мультиплексирования (Dense Wavelength Division Multiplexing - DWDM) и технологий коммутации оптических сигналов предопределило появление концепций полнооптических сетей, в которых данные коммутируются' непосредственно в оптическом виде, без преобразования
10 сигнала в электронную форму [22]. Наиболее перспективной концепцией полнооптической сети многими исследователями признается сеть оптической коммутации блоков (OBS), которая может служить примером сети с коммутацией каналов следующего поколения (NGN - Next Generation Network^ В-сети 0BS управляющие сигналы обрабатываются электронно на каждом узле сети, в то время как блоки данных передаются в оптическом виде без О/Е/0-преобразований на промежуточных узлах. Технология^ GMPLS предназначена для'решения.вопросов маршрутизации в данной сети. Она наследует у технологии MPLS возможность многопутевой маршрутизации. В качестве меток GMPLS предусматривает использование длины оптической волны (иначе лямбды), канала DWDM. Таким образом сеть 0BS является сетью с коммутацией каналов, для которой, как упоминалось ранее, отсутствуют эффективные* методы динамической маршрутизации. В связи с этим необходима разработка модели алгоритма динамической маршрутизации для сетей с канальной; коммутацией, включающей в себя алгоритм расчета оптимальных маршрутов, которую, в частности, можно было бы применить для сети OBS. В то же время алгоритм поиска оптимальных маршрутов должен обеспечить контролируемость максимального числа разрешенных к использованию параллельных маршрутов.
В данной работе получена модель алгоритма динамической маршрутизации для сетей с канальной коммутацией, использующих технологию коммутации меток GMPLS, а так же разработана имитационная модель сети оптической коммутации блоков. В основе разработанной модели алгоритма динамической маршрутизации лежит алгоритм поиска оптимальных маршрутов по критерию минимизации потерь с ведением ограничения на максимальное число параллельных маршрутов.
Целью настоящей диссертационной работы является разработка модели эффективного алгоритма динамической многопутевой маршрутизации для сетей с канальной коммутацией. Под эффективностью понимается следующее: уменьшение вероятности потерь информации, повышение пропускной способ-
ности сети, повышение отказоустойчивости сети и возможность контроля-девиации (расщепления) сетевого потока. Для этого требуется провести анализ состояния проблемы и решить следующие основные задачи:
проанализировать существующие методы и алгоритмы оптимального распределения трафика в сетях передачи данных;
разработать математическую модель информационных потоков для сетей с канальной коммутацией и на его основе разработать алгоритм поиска оптимальных К-путевых маршрутов. Разрабатываемый алгоритм должен обеспечить контролируемость девиации сетевого потока (иначе говоря -позволяющий ввести ограничение на предельное количество разрешенных к использованию параллельных маршрутов);
модифицировать существующий алгоритм поиска оптимальных К-путевых маршрутов по критерию средних задержек для сетей с пакетной коммутацией, с целью реализации контроля девиации сетевого потока.
разработать модель алгоритма динамической маршрутизации для сетей GMPLS с канальной коммутацией, позволяющей применить как централизованный (на выделенном вычислителе), так и децентрализованный способ расчета оптимальных маршрутов, а так же обеспечивающий отказоустойчивость сети;
реализовать алгоритмы распределения информации в виде программ на ПЭВМ в среде MATLAB;
разработать имитационную модель сети GMPLS на примере сети оптической коммутации блоков (OBS) с использованием сетевого симулятора NS-2;
разработать модули к среде имитационного моделирования NS-2 на языках программирования C++ и Tel, реализующих разрабатываемый алгоритм распределения информации;
провести испытания (имитационное моделирование на ПЭВМ) и оценить эффективность разработанного алгоритма.
Методы исследования. Для решения перечисленных задач в работе использованы методы системного анализа, теории вероятностей, теории телетрафика, теории графов, а также имитационное моделирование и расчеты на ПЭВМ.
Научная новизна работы. В диссертации получены следующие новые научные и практические результаты:
разработан новый К-путевой алгоритм оптимального распределения информации для сетей с канальной коммутацией, позволяющий уменьшить вероятность потерь вызовов и увеличить пропускную способность сети;
разработан новый оптимизационный алгоритм, позволяющий при поиске оптимальных маршрутов в сетях с канальной и пакетной коммутацией ввести ограничение на максимальное число разрешенных к использованию параллельных маршрутов, т.е. сделать подконтрольным девиацию сетевого потока;
разработана имитационная модель полнооптической сети GMPLS, позволяющая использовать ее в качестве инструмента при проектировании новых сетей, либо модернизации существующих;
В первой главе на основе известных автору источников осуществлен анализ функционирования основных промышленных протоколов маршрутизации (RIP, OSPF, EIGRP). Сделан вывод о низкой эффективности классических алгоритмов маршрутизации в части оптимального распределения сетевых потоков.
Подробно рассмотрены существующие алгоритмы поиска оптимальных маршрутов графовыми итерационными методами, а так же методами математического программирования.
Сделан обзор современных технологий, позволяющих применить методы оптимального распределения трафика в сетях передачи данных (MPLS и GMPLS с расширениями Traffic Engineering).
Обозначены недостатки существующих алгоритмов поиска оптимальных маршрутов, затрудняющие их применение в сетях MPLS/GMPLS. Сделан вывод
13 об отсутствии эффективных алгоритмов динамической маршрутизации в, полнооптических сетях GMPLS.
Сформулированы основные задачи, которые необходимо решить для разработки окончательного и практически реализуемого алгоритма динамической маршрутизации в сетях GMPLS с канальной коммутацией.
Вторая глава посвящена разработке алгоритма многопутевого распределения сетевых потоков в сетях GMPLS с канальной коммутацией, основанном на решении задачи выбора оптимальных потоков по критерию минимизации* суммарных потерь в сети.
Сформулирована модель потока данных путем установления взаимосвязи между (приближенной) вероятностью потерь блоков и вектора потока данных. Получена целевая функция зависимости вероятности потерь данных от нагрузки и выработаны граничные условия оптимизационной задачи. Проведена оценка граничных условий и выработаны рекомендации по установке их значений для сетей с большим диаметром. Проанализированы существующие подходы и методы математического программирования, приводящие к решению поставленной оптимизационной задачи.
Поставленная оптимизационная задача решена одним из методов нелинейного программирования - методом проекции градиента. На основе анализа данного метода выработана рекомендация по увеличению скорости сходимости оптимизационного алгоритма за счет упрощения расчета первых частных производных целевой функции.
Воспользовавшись свойством выпуклых функций нелинейная оптимизационная задача сведена к линейной и решена симплекс-методом. Даны рекомендации по уменьшению ресурсоемкости разработанного алгоритма. Разработан алгоритм поиска маршрутов из найденного вектора распределения сетевой нагрузки.
При постановке задачи узловой коммутатор был принят полнодоступным и неблокирующим. В задачу внесена модификация, позволяющая учесть ограничение на количество одновременных соединений в узловом коммутаторе.
Вследствие появления эффекта сильного разветвления потоков по различным маршрутам в задачу внесено ограничение на максимальное количество используемых маршрутов, разрешенных к использованию каждой нагрузкой. Задача решена целочисленным программированием методом ветвей и границ путем введения дополнительных бинарных переменных.
Третья глава посвящена разработке модели алгоритма динамической маршрутизации для сетей GMPLS с канальной коммутацией. Модель включает в себя алгоритмы поиска оптимальных и запасных маршрутов. Показана применимость разработанного алгоритма динамической маршрутизации при двух вариантах управления сетевыми потоками: централизованным способом (на выделенном вычислителе) и децентрализованным.
Определены объекты сети, необходимые для функционирования разработанного алгоритма: граничные и транзитные узлы, узловые коммутационные устройства, вычислитель маршрутов. Определены условия и способ предоставления канала связи двум абонентам.
Определен способ установления оптимальных маршрутов - с помощью протокола CR-LDP, а так же принято ограничение на количество узлов сети, в которой может быть применен разрабатываемый алгоритм.
Разработан алгоритм сбора статистических данных о переданной нагрузке между приемником и получателем для их дальнейшей передачи в качестве исходных данных алгоритму расчета оптимальных маршрутов. Даны рекомендации по установке начальных параметров алгоритма для различных типов планирования распределения нагрузки (при стратегическом планировании и для случаев оперативного реагирования на изменения в сети).
Разработан алгоритм расчета величин нагрузок, удовлетворяющих двум условиям: 1) каждой нагрузке предоставлена минимальная гарантированная полоса пропускания, и 2) каждой нагрузке предоставлена максимальная полоса пропускания из условия равного приоритета всех нагрузок.
Разработан алгоритм расчета запасных маршрутов, позволяющий повысить отказоустойчивость сети.
Разработана функциональная схема полученной модели алгоритма динамической маршрутизации для полнооптических сетей GMPLS с канальной коммутацией.
В алгоритм расчета оптимальных маршрутов внесена модификация с целью возможности его применения в^городской сети IP-MPLS Вологодского филиала. ОАО «Северо-Западный Телеком». В соответствии с поставленной зада-чей изменен критерий оптимальности - распределение нагрузки по маршрутам, обеспечивающим минимальные задержки для пакетов.
Четвертая глава посвящена разработке имитационной модели сети GMPLS с канальной коммутацией на примере сети OBS и моделированию полученного алгоритма распределения информации. В качестве базового выбран популярный сетевой симулятор NS-2.
Для реализации модели исследуемой сети осуществлено ее разбиение на функциональные блоки, т.е. сделана декомпозиция исследуемого объекта, а затем на языках C++ и Tel разработаны соответствующие им модули. Верификация модели осуществлена путем отладки, контроля входных и выходных параметров, а так же визуального контроля анимации результатов прогона модели.
С помощью имитационного моделирования исследуемой сети осуществлено сравнение полученного алгоритма с двумя существующими алгоритмами многопутевой маршрутизации, основанным на решении задачи поиска оптимальных маршрутов по критериям: а) средней задержки блоков, б) ограничению на емкость каналов, а так же осуществлено сравнение с алгоритмом наикратчайших маршрутов.
Построены графики зависимости потерь блоков данных от суммарной нагрузки на сеть, из которых следует, что для сети оптической коммутации блоков разработанная методика эффективнее существующих методов распределения информации.
Для подтверждения эффективности модифицированной методики, оптимального распределения информации, предлагаемой к использованию в городской сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком»,
разработана имитационная модель указанной сети. При моделировании использованы маршруты, найденные модифицированным оптимизационным алгоритмом. Полученные результаты были сравнены с результатами прогона имитационной модели при работе алгоритма кратчайших маршрутов. Сравнительный анализ показал, что предлагаемая методика эффективнее существующего способа маршрутизации по кратчайшим маршрутам.
В Заключении сформулированы основные результаты работы.
Формулирование сетевых задач в терминах узлов и связей
Представленная задача относится к классу многопродуктовых задач. Термин «многопродуктовый поток» означает, что в сети имеется несколько нагрузок, причем каждый получатель может принять только предназначенную ему нагрузку. Иначе говоря сетевые потоки от разных источников не могут «смешиваться». Это значит, что для решения поставленной задачи не подходят итерационные методы, описанные в предыдущем разделе (алгоритм «беспорядка» Форда и Фалкерсона [46,47,49], алгоритм Клейна [50] и алгоритм Басакера и Гауэна [48]), допускающие смешивание потоков.
С точки зрения методов системного анализа представленная задача является задачей линейного программирования и может быть решена симплекс-методом [63, 65]. Формулировка задачи дана в терминах связей и путей, поскольку все маршруты движения сетевого потока заранее известны, а неизвестными величинами являются доли исходных нагрузок вдоль этих маршрутов.
Рассматриваемая сетевая оптимизационная проблема может быть сфор 41 мулирована в терминах узлов и связей. Предыдущая формулировка неудобна с той точки зрения, что маршруты движения трафика заранее могут быть неизвестны. Поэтому оптимизационную задачу необходимо сформулировать иначе. Возвращаясь к примеру трехузловой сети положим, что все линии связи состоят из двух встречно направленных дуг (приемный и передающий канал). В этом случае потоком из источника sd в сток td будем назвать множество неотрицательных чисел xed (каждое из которых поставлено в соответствие некоторой дуге е сети), если эти числа удовлетворяют следующим линейным ограничениям:
Заметим, что первое ограничение выражает тот факт, что в каждый узел (кроме источника и стока) приходит столько потока, сколько из него выходит (условие сохранения). Второе и третье ограничение означает, что сумма потоков xed по дуге ограничена пропускной способностью дуги yd.
Общая стоимость потока может быть выражена так:
Отметим, что в данной формулировке неизвестными величинами являются доли исходных потоков на дугах ориентированного графа. Оптимизационная задача минимизации стоимости сетевого потока, сформулированная в терминах узлов и связей в этом случае запишется так: минимизировать
Поскольку все ограничения и целевая функция являются линейными, то решение задачи так же может быть найдено симплекс-методом. Вектор Х={хе }, является искомым вектором сетевого потока
Постановка задачи поиска оптимальных маршрутов в полнооптических етях с канальной коммутацией
Как показал анализ материалов по исследуемой тематике, существующие однопутевые алгоритмы маршрутизации (RIP, OSPF, EIGRP и др.) не в состоянии обеспечить оптимальность распределения сетевого потока и предоставить дифференцированные услуги для различных типов трафика.
Появление технологии MPLS, точнее, стандарта Traffic Engineering в составе группы стандартов MPLS, позволяет применить методы оптимальной маршрутизации.
Наиболее известным алгоритмом расчета оптимальных К-путевых маршрутов для сетей с пакетной коммутацией является алгоритм, предложенный в работе Л.Фратта, М.Герла и Л. Клейнрока [94] (оптимизация по критерию средних задержек). Однако в сетях с большим количеством альтернативных маршрутов при использовании данного метода наблюдается неконтролируемая девиация (расщепление) потока между каждой парой источник/получатель вдоль множества найденных маршрутов, что объясняется отсутствием ограничения на количество используемых маршрутов. Этот эффект затрудняет реализацию метода в сетях IP-MPLS, так как для каждой пары источник/получатель в этом,случае необходимо будет создать большое количество отдельных LSP-туннелей (Label Switch Path - LSP), что значительно усложнит управляемость сетью. Для устранения этой проблемы необходимо внести в алгоритм модификацию, которая позволит ввести ограничение на число используемых параллельных маршрутов индивидуально для каждой нагрузки.
Для сетей с канальной коммутацией, а в частности для полнооптических сетей GMPLS, в настоящий момент отсутствуют эффективные методы динамической маршрутизации, которые бы использовали методы оптимального К-путевого распределения трафика. В связи с этим необходима разработка алгоритма поиска оптимальных маршрутов для сетей с канальной коммутацией. Для выработки критерия оптимальности разрабатываемого оптимизационного алгоритма целесообразно применить математический аппарат теории телетрафика, так как в нем хорошо изучены процессы передачи данных в сетях с коммутацией каналов. Разрабатываемый алгоритм так же должен обеспечить контролируемость девиации сетевого потока.
Кроме того, необходима разработка модели алгоритма динамической маршрутизации сетевых потоков для сети оптической коммутации блоков, позволяющего применить как централизованный (на выделенном вычислителе), так и децентрализованный способ расчета оптимальных маршрутов, а также позволяющего повысить отказоустойчивость сети.
Необходимо проверить эффективность разработанных алгоритмов путем их сравнения с существующими алгоритмами маршрутизации. Для этого представляется целесообразным применение имитационного моделирования. В настоящий момент существует достаточно много как коммерческого, так и бес 76 платного ПО моделирования сетей передачи данных. Наиболее развитым инструментом среди бесплатно распространяемых программных продуктов является среда имитационного моделирования NS-2, работающая под управлением UNIX-систем. В ней уже реализованы модели пакетных сетей, алгоритмы маршрутизации и базовые примитивы, позволяющие моделировать сеть IP-MPLS.
Эффективность разрабатываемого алгоритма динамической маршрутизации для полнооптических сетей OBS должна быть проверена в совокупности с алгоритмами, специфичными для данной сети. В частности - с алгоритмом установления канала связи ЛТ. Это связано с тем, что алгоритмы установления канала связи непосредственно влияют на величину пропускной способности каналов связи, которые будут являться одним из параметров алгоритма поиска оптимальных маршрутов. Поскольку аналитически связать оба названных алгоритма не представляется возможным, то необходимо создать модель сети оптической коммутации блоков, в том числе протокол установления канала связи ЛТ, и смоделировать функционирование этого алгоритма в совокупности с разрабатываемым алгоритмом оптимального распределения информации.
Основные задачи, которые необходимо решить в данной диссертации с целью разработки эффективной методики распределения сетевых потоков в сетях MPLS/GMPLS, могут быть сформулированы следующим образом:
1. разработать математическую модель информационных потоков для сетей с канальной коммутацией (на примере сети оптической коммутации блоков) и на его основе разработать алгоритм поиска оптимальных К-путевых маршрутов. Разрабатываемый алгоритм должен обеспечить контролируемость девиации сетевого потока (иначе говоря - позволяющий ввести ограничение на предельное количество разрешенных к использованию параллельных маршрутов);
2. модифицировать существующий алгоритм поиска оптимальных К-путевых маршрутов по критерию средних задержек для сетей с пакетной коммутацией, с целью реализации контроля девиации сетевого потока. 3. разработать модель алгоритма динамической маршрутизации для; сетей оптической коммутации блоков; позволяющего применить как централизованный (на выделенном вычислителе), так и децентрализованный способ расчета оптимальных маршрутов, а также повысить отказоустойчивость сети;
4. реализовать алгоритмы распределения информации в виде программ на ПЭВМ в среде MATLAB;
5. разработать имитационную модель сети GMPLS на примере сети г оптической, коммутации блоков (OBS) с использованием сетевого симулятора NS-2;
6. разработать модули к среде имитационного моделирования NS-2 на языках программирования C++ и Tel, реализующих разрабатываемый алгоритм распределения информации;
7. провести испытания (имитационное моделирование на ПЭВМ) и оценить эффективность разработанных алгоритмов.
Алгоритм поиска маршрутов из найденного вектора распределения сетевого трафика
Результатом работы всех представленных задач математического программирования является вектор сетевого трафика X = {xecj\, который выражает следующее: каждому трафику d на дуге е поставлено в соответствие некоторое число xed- часть исходной нагрузки.
Для нахождения маршрутов из вектора X необходимо разработать алгоритм, учитывающий возможность расщепления нагрузки на каком-либо узле. В общем случае оптимизационный алгоритм может распределить нагрузку между данным источником и получателем через различные маршруты, т.е. на каких-то узлах нагрузка может расщепиться, на последующих узлах вновь соединиться и т.д.. На Рис. 2.5(a) представлен один из таких случаев.
Как видно из Рис. 2.5(a), правило сохранения потока соблюдено. Поскольку оптимизационный алгоритм гарантирует отсутствие циклов в сети, то для поиска маршрутов удобнее всего воспользоваться рекурсивным методом.
Представим алгоритм поиска маршрутов из вектора сетевого трафика X. Следующие шаги производим для каждого трафика d. Перед началом считаем, что мы находимся в узле-источнике трафика (см. Рис. 2.5,а).
Шаг 1: Рекурсивно продвигаемся от текущего к следующим узлам. Перемещение из одного узла в другой возможно лишь при ненулевом значении переменной потока xed для данного трафика d. Поскольку в сети отсутствуют циклы, то в конечном итоге мы придем к узлу-получателю трафика.
Шаг 2: Если находимся в узле получателя, ищем наименьшее значение переменной хес/ вдоль найденного маршрута и вычитаем его значение из всех переменных потока вдоль маршрута. Тем самым обнуляем значение как минимум одной переменной на каком-то участке маршрута (см. Рис. 2.5,6).
Шаг 3: Запоминаем найденный маршрут и присваиваем ему интенсивность трафика, равную минимальному значению интенсивности, найденному на предыдущем шаге.
Шаг 4: Рекурсивно возвращаемся к узлу, до которого маршрут от источника не содержит нулевых значений переменных xed- В некоторых случаях происходит возврат к источнику трафика (см. Рис. 2.5,в). Переходим на Шаг 1.
Следует отметить тот факт, что при использовании нелинейного метода оптимизации алгоритм расчета вектора сетевого трафика может работать очень длительное время. Для сокращения этого времени, как отмечалось в предыдущих главах, необходим расчет градиента исследуемой функции, т.е. первых частных производных. Из за большой сложности получения аналитической формулы производной целевой функции применен приближенный численный метод расчета градиента. Вследствие этого оптимизационный алгоритм не может быть завершен самостоятельно, хотя целевая функция будет им оптимизирована более чем на 95%. В использованном инструментарии пакета MATLAB для останова оптимизационной- функции применено ограничение на количество итераций поискового алгоритма.
Как следствие, вектор сетевого трафика может содержать цикличные маршруты, вдоль которых интенсивность хоть и несущественно маленькая, но тем не менее отлична от нуля. Это обстоятельство сильно затрудняет поиск маршрутов (см. выше). Поэтому, в алгоритм поиска необходимо добавить до 99 полнительные шаги для разрыва циклов.
Шаг 1.1: Если текущий узел не входит в текущий маршрут, то продолжаем движение и переходим к следующему узлу. Иначе:
Шаг 1.2: Найден цикл. Находим в этом цикле наименьшее значение переменной хесі и уменьшаем все переменные в цикле на это значение. Тем самым мы разрываем цикл. Отметим, что условие сохранения потока полностью соблюдается.
Шаг 1.3: Рекурсивно возвращаемся в текущий узел.
Функциональная схема разработанной модели алгоритма динамической* многопутевой маршрутизации
В соответствии с разработанным алгоритмом расчета оптимальных маршрутов для полнооптических сетей GMPLS (см. главу 2) исходными данными являются:
1. топология сети;
2. канальная емкость DWDM-линий связи;
3. информация об источниках и получателях трафика;
4. средняя интенсивность формируемой источниками нагрузки;
5. предельное количество одновременных соединений в Р-маршрутизато-ре;
6. максимальное число маршрутов между парой источник/получатель, разрешенное для передачи трафика.
Информация о топологии, емкости DWDM-каналов связи и размере не 119 блокирующей матрицы узла могут быть доставлены протоколом OSPF. Информация об источниках, получателях трафика может быть получена из протокола BGP. Величины формируемой ими нагрузки должны быть вычислены в соответствии алгоритмом (Рис. 3.2). Централизованный способ расчета маршрутов предполагает наличие в сети одного или нескольких выделенных вычислителей, куда будет стекаться вся перечисленная информация. Обобщенная схема сети представлена на Рис. 3.6, где RC - выделенные вычислители.
Между выделенным вычислителем (RC-маршрутизатором) и каждым РЕ-маршрутизатором устанавливается MP-BGP-сессия, таким образом RC-маршрутизатор дополнительно может выступать в качестве BGP-отражателя. После расчета маршрутов, RC-маршрутизатор по протоколу BGP рассылает всем РЕ-маршрутизаторам вычисленные оптимальные маршруты. Следует отметить, что схема с выделенными вычислителями должна быть преимущественно применена в сетях, где требуется лишь стратегическое планирование распределения трафика.
При децентрализованном способе расчета маршрутов, распределение трафика в сети будет оптимальным только в том случае, если все РЕ-маршрутизаторы будут иметь идентичные входные данные алгоритма расчета оптимальных маршрутов (соответственно - идентичный набор маршрутов). Для достижения этой цели вводится механизм синхронизации времени очередного расчета оптимальных маршрутов.
Каждый узел сети должен быть оснащен агентом точного времени, использующем протокол NTP (Network Time Protocol - протокол сетевого времени). Далее административно задается интервал времени , по истечении которого все граничные узлы сети обязаны осуществить перерасчет маршрутов (например, каждые 10 минут, начиная с 0:00 часов).
Поскольку значения нагрузки, включаемые в сигналы LSA распространяются по сети не мгновенно, необходим ввод механизма, гарантирующего, что на момент расчета маршрутов все граничные узлы будут иметь одинаковые значения нагрузок. С этой целью предлагается распространять информацию о нагрузках на сеть с периодичностью, равной периодичности расчета маршрутов, а время начала распространения сместить от начала времени расчета на величину, достаточную для обмена анонсами о нагрузке между самыми дальними устройствами сети.
При децентрализованном способе расчета маршрутов в данной работе предлагается оптимизировать только трафик, заданный административно. То есть предельное число альтернативных маршрутов и величина пропускной способности сети, необходимой для данной MP-BGP-сессии должны быть заданы на этапе установления MP-BGP-сессии и являться ее свойствами. Это значит, что в соответствии с алгоритмом из раздела 3.3 расчет предельной пропускной способности сети для каждого источника должен быть осуществлен с начальными ограничениями, задающими минимальную пропускную способность МР-BGP-сессий. Таким образом с каждой парой источник/получатель трафика будет ассоциирована величина необходимой полосы пропускания, которую можно подавать на вход алгоритма расчета оптимальных маршрутов. Кроме того, для MP-BGP-сессий, у которых не задано предельное число альтернативных
1. В IP-сетях в протоколе OSPF это время по умолчанию равно 30 сек. маршрутов, считаем, что количество маршрутов равно единице.
На Рис. 3.7 представлена функциональная схема модели алгоритма динамической маршрутизации, функционирующего в граничном узле сети. База исходных данных наполняется протоколами OSPF и MP-BGP.
Алгоритм расчета запасных маршрутов и алгоритм расчета оптимальных маршрутов передают найденные маршруты протоколу CR-LDP. Последний через сеть устанавливает LSP-туннели, которые поступают в топологическую базу в виде односторонних каналов связи. С каждым маршрутом ассоциирован вес, величина которого чуть лучше чем кратчайший маршрут до данного получателя, а так же весовой коэффициент распределения нагрузки.
Функциональная схема алгоритма динамической маршрутизации Для запасных маршрутов коэффициент распределения нагрузки равен 0. Это значит что при штатном (безаварийном) функционировании сети трафик по этим маршрутам не передается. В случае, если в сети случилась авария, алгоритм CR-LDP гарантирует отключение из маршрутной и коммутационной таблицы всех туннелей, проходящих через аварийный участок. При этом алгоритм обхода аварийного участка FastReroute (в составе алгоритма коммутации) переключит трафик на один из запасных маршрутов.
