Разработка и исследование модели алгоритма динамической маршрутизации для сетей GMPLS тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Нижарадзе, Тимур Зурабович

• Нижарадзе, Тимур Зурабович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Нижарадзе, Тимур Зурабович

Основные обозначения и сокращения.

Введение.

Глава 1. Анализ существующих методов и алгоритмов распределения информационных потоков.

1.1 Промышленные протоколы маршрутизации-. ! ' ' '

1.111 Дистанционно-векторный протокол RIP.

1.1.2 Протокол состояния связей OSPF.

1.1.3 Протокол EIGRP.

1.2 Графовые алгоритмы поиска оптимальных маршрутов.

1.2.1 Алгоритм Дейкстры.

1.2.2 Алгоритм Флойда.

1.2.3 Поиск К-кратчайших путей (метод Дж.Иена).

1.2.4 Задача о максимальном потоке в сети.

1.2.5 Задача нахождения потока наименьшей стоимости.

1.3 Расчет маршрутов методами математического программирования.

1.3.1 Формулирование сетевых задач в терминах связей и путей.

1.3.2 Формулирование сетевых задач в терминах узлов и связей.

1.3.3 Решение некоторых сетевых оптимизационных задач методом математического программирования.

1.4 Методы реализации многопутевой маршрутизации. Технология MPLS.

1.4.1 Протокол распространения меток LDP.

1.4.2 Задача выбора оптимальных маршрутов.

1.4.3 Технология Traffic Engineering.

1.4.4 Механизмы MPLS, реализующие Traffic Engineering.

1.5 Полнооптические сети с коммутацией каналов. Технология GMPLS.

1.5.1 Сеть оптической коммутации блоков (OB S).

1.5.2 Технология DWDM.

1.5.3 Архитектурные решения коммутационного устройства узла сети.

1.5.4 Алгоритмы установления канала связи.

1.5.5 Существующие методы распределения потоков в сети OBS.

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

1.7 Выводы по главе 1.

Глава 2. Разработка алгоритма оптимального распределения информации, в сетях с канальной коммутацией.

2.1 Формулирование оптимизационной-задачи.

2.2 Решение оптимизационной задачи градиентным методом.

2.3 Решение оптимизационной задачи симплекс-методом.

2.4 Алгоритм поиска маршрутов из найденного вектора распределения сетевого трафика.

2.5 Разработка алгоритма конроля девиации сетевого потока.

2.6 Выводы по главе 2.

Глава 3. Разработка модели алгоритма динамической маршрутизации в сетях GMPLS с канальной коммутацией.

3.1 Объекты сети оптической коммутации блоков.

3.2 Протокол установления маршрутных туннелей CR-LDP.

3.3 Алгоритм расчета текущей нагрузки вдоль MP-BGP-сессии.

3.4 Повышение отказоустойчивости сети. Алгоритм расчета запасных маршрутов.

3.5 Функциональная схема разработанной модели алгоритма динамической> многопутевой маршрутизации.

3.6 Оптимизация распределения нагрузки городской сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком».

3.6.1 Постановка задачи оптимального распределения трафика.

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

3.7 Выводы по главе 3.

Глава 4. Разработка имитационной модели сети GMPLS и моделирование разработанного алгоритма динамической маршрутизации.

4.1 Разработка модели сети оптической коммутации блоков.

4.1.1 Модуль протокола установления канала связи.

4.1.2 Модуль оптической DWDM-линии.

4.1.3 Модуль фотонного коммутатора, коммутационный алгоритм.

4.1.4 Модуль имитации агента - источника блоков данных.

4.1.5 Сбор статистики и формирование результатов моделирования.

4.2 Имитационное моделирование сети оптической коммутации блоков.

4.3 Оптимальное распределение трафика в сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком».

4.4 Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Разработка и исследование модели алгоритма динамической маршрутизации для сетей GMPLS»

Когда необходимо доставить сетевой трафик из точки- А* в точку Б, ни один способ не подойдет всем приложениям сразу. Голосовым и видеоприложениям требуется минимальная вариация задержки, в то время как критически важным приложениям - жесткие гарантии предоставления сервиса и резервных маршрутов: 1

До сих пор необходимые многим приложениям дифференцированные услуги и гарантии предоставляли только сети с коммутацией каналов. Однако-с появлением технологии мультипротокольной коммутации с заменой меток-(Multiprotocol* Label Switching, MPLS) ситуация изменилась. MPLS позволяет поддерживать все упомянутые приложения в сети IP без необходимости-вводить в значительных областях сети иные транспортные механизмы, протоколы маршрутизации и планы адресации.

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

В" противоположность этому технология MPLS с расширениями Traffic Engineering.(MPLS ТЕ) позволяет применить многопутевые методы маршрутизации, что дает возможность решать практически любые сетевые задачи (максимальное использование каналов, обеспечение качества обслуживания, резервирование, дизайн и т.п.).

Методы расчета многопутевых маршрутов были известны задолго до появления технологии MPLS (Клейнрокк JI., Jackson J.R., Little J.D.C.,

В.М.Вишневский, Е.В:Левнер; Е.В.Федотов и др.). Однако в промышленных сетях передачи данных многопутевое распределение трафика почти не применялось из-за сложностей ее практической реализации.

Для сетей пакетной коммутации наиболее известным методом расчета оптимальных многопутевых маршрутов является- алгоритм, впервые предложенный в работе Л.Фратта, М.Герла и Л.' Клейнрока [94]. Ими, была изучена модель сети пакетной коммутации В; виде сети массового обслуживания, в которых узлы-описываются системой М/М/1А». Для данной модели была найдена взаимосвязь.между нагрузкой на сеть и величиной средней задержки пакетов! в сети. Указанная взаимосвязь дала возможность сформулировать и решитьхете-вую оптимизационную задачу, позволяющую найти между всеми парами источник/получатель такой набор многопутевых маршрутов, при котором суммарные задержки пакетов в сети были бы минимальны.

Однако в сетях с большим количеством альтернативных маршрутов при-использовании данного метода наблюдается неконтролируемая девиация (расщепление) потока между каждой парой источник/получатель вдоль множества найденных маршрутов, что объясняется отсутствием ограничения на количество используемых маршрутов. Этот эффект затрудняет реализацию метода в сетях MPLS/GMPLS, так как для каждой пары источник/получатель (которой является MP-BGP-сессия) в этом случае необходимо будет создать большое количество отдельных LSP'-туннелей (Label Switch Path - путь коммутации меток), что значительно усложняет управляемость сетью. Для устранения данной проблемы, необходима разработка алгоритма поиска оптимальных маршрутов, позволяющего ввести ограничение на число используемых параллельных маршрутов.

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

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

Оптимизационные задачи, формулируемые для сетей с канальной коммутацией, в основном связаны с нахождением 1) минимально необходимого количества выходов коммутационной системы при заданной поступающей нагрузке, 2) емкости коммутационных устройств, а так же 3) оптимального распределения межстанционной нагрузки (метод эквивалентных замен, метод укрупнения, состояний пучков и т.п.), и носят довольно статичный характер. То есть после расчета оптимальных параметров коммутационной системы, рассчитанные* параметры остаются-неизменными до тех пор, пока сеть не претерпит существенных изменений (напр. изменится емкость межстанционных связей или емкость самого коммутационного устройства). В современных сетях с канальной коммутацией в целях адекватного реагирования на изменения нагрузки в сети необходима разработка новых алгоритмов адаптивной маршрутизации, позволяющих адекватно и быстро реагировать на изменения нагрузки в сети и обеспечивать как надежность передачи информации, так и необходимую пропускную способность. При этом критерием оптимальности алгоритма маршрутизации для сетей с коммутацией каналов может служить величина потерь вызовов, а так же пропускная способность сети.

Успех MPLS дал толчок для создания универсальной технологии коммутации с использованием меток. Новая технология получила название Generalized MPLS (GMPLS - обобщенный MPLS). Она расширяет и унифицирует функции (маршрутизации и сигнализации) MPLS для любых транспортных технологий канального и физического уровней. В частности, появление технологии плотного волнового мультиплексирования (Dense Wavelength Division Multiplexing - DWDM) и технологий коммутации оптических сигналов предопределило появление концепций полнооптических сетей, в которых данные коммутируются * непосредственно в оптическом виде, без преобразования сигнала в электронную форму [22]. Наиболее перспективной концепцией полнооптической сети многими исследователями признается сеть оптической коммутации блоков (OBS), которая может служить примером сети с коммутацией каналов следующего поколения (NGN - Next Generation Network); В-сети 0BS управляющие сигналы обрабатываются электронно на каждом узле сети, в то время как блоки данных передаются в оптическом виде без О/Е/0-преобразований на промежуточных узлах. Технология^ GMPLS предназначена для'решения.вопросов маршрутизации в данной сети. Она наследует у технологии MPLS возможность многопутевой маршрутизации. В качестве меток GMPLS предусматривает использование длины оптической волны (иначе лямбды). канала DWDM. Таким образом сеть OBS является сетью с коммутацией каналов, для которой, как упоминалось ранее, отсутствуют эффективные-методы динамической маршрутизации. В связи с этим необходима разработка модели алгоритма динамической маршрутизации для сетей с канальной; коммутацией, включающей в себя алгоритм расчета оптимальных маршрутов, которую, в частности, можно было бы применить для сети OBS. В то же время алгоритм поиска оптимальных маршрутов должен обеспечить контролируемость максимального числа разрешенных к использованию параллельных маршрутов.

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

Целью настоящей диссертационной работы является разработка модели эффективного алгоритма динамической многопутевой маршрутизации для сетей с канальной коммутацией. Под эффективностью понимается следующее: уменьшение вероятности потерь информации, повышение пропускной способности сети, повышение отказоустойчивости сети и возможность контроля-девиации (расщепления) сетевого потока. Для этого требуется провести анализ состояния проблемы и решить следующие основные задачи:

1. проанализировать существующие методы и алгоритмы оптимального распределения трафика в сетях передачи данных;

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

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

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

5. реализовать алгоритмы распределения информации в виде программ на ПЭВМ в среде MATLAB;

6. разработать имитационную модель сети GMPLS на примере сети оптической коммутации блоков (OBS) с использованием сетевого симулятора NS-2;

7. разработать модули к среде имитационного моделирования NS-2 на языках программирования С++ и Tel, реализующих разрабатываемый алгоритм распределения информации;

8. провести испытания (имитационное моделирование на ПЭВМ) и оценить эффективность разработанного алгоритма.

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

Научная новизна работы. В диссертации получены следующие новые научные и практические результаты:

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

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

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

В первой главе на основе известных автору источников осуществлен анализ функционирования основных промышленных протоколов маршрутизации (RIP, OSPF, EIGRP). Сделан вывод о низкой эффективности классических алгоритмов маршрутизации в части оптимального распределения сетевых потоков.

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

Сделан обзор современных технологий, позволяющих применить методы оптимального распределения трафика в сетях передачи данных (MPLS и GMPLS с расширениями Traffic Engineering).

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

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

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

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

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

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

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

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

Третья глава посвящена разработке модели алгоритма динамической маршрутизации для сетей GMPLS с канальной коммутацией. Модель включает в себя алгоритмы поиска оптимальных и запасных маршрутов. Показана применимость разработанного алгоритма динамической маршрутизации при двух вариантах управления сетевыми потоками: централизованным способом (на выделенном вычислителе) и децентрализованным.

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

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

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

Разработан алгоритм расчета величин нагрузок, удовлетворяющих двум условиям: 1) каждой нагрузке предоставлена минимальная гарантированная полоса пропускания, и 2) каждой нагрузке предоставлена максимальная полоса пропускания из условия равного приоритета всех нагрузок.

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

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

В алгоритм расчета оптимальных маршрутов внесена модификация с целью возможности его применения в городской сети IP-MPLS Вологодского филиала. ОАО «Северо-Западный Телеком». В соответствии с поставленной задаI чей изменен критерий оптимальности - распределение нагрузки по маршрутам, обеспечивающим минимальные задержки для пакетов.

Четвертая глава посвящена разработке имитационной модели сети GMPLS с канальной коммутацией на примере сети OBS и моделированию полученного алгоритма распределения информации. В качестве базового выбран популярный сетевой симулятор NS-2.

Для реализации модели исследуемой сети осуществлено ее разбиение на функциональные блоки, т.е. сделана декомпозиция исследуемого объекта, а затем на языках С++ и Tel разработаны соответствующие им модули. Верификация модели осуществлена путем отладки, контроля входных и выходных параметров, а так же визуального контроля анимации результатов прогона модели.

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

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

Для подтверждения эффективности модифицированной методики, оптимального распределения информации, предлагаемой к использованию в городской сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком», разработана имитационная модель указанной сети. При моделировании использованы маршруты, найденные модифицированным оптимизационным алгоритмом. Полученные результаты были сравнены с результатами прогона имитационной модели при работе алгоритма кратчайших маршрутов. Сравнительный анализ показал, что предлагаемая методика эффективнее существующего способа маршрутизации по кратчайшим маршрутам.

В Заключении сформулированы основные результаты работы.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Нижарадзе, Тимур Зурабович

4.4 Выводы по главе 4

Настоящая глава посвящена разработке имитационной модели сети оптической коммутации блоков и моделированию алгоритмов распределения информации.

1. Сделан обзор систем имитационного моделирования и выбор в пользу популярного сетевого симулятора NS-2.

2. Для создания имитационной модели исследуемой сети осуществлено ее разбиение на функциональные блоки: DWDM-канал, фотонный коммутатор, алгоритм коммутации, протокол установления канала связи, очередь управляющих сообщений, источник оптических блоков и разработаны соответствующие им модули на языках С++ и Tel.

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

4. Поставлены два эксперимента с разными типами генерируемого трафика: пуассоновским и детерминированным, в ходе которых получена статистика переданных и уничтоженных блоков. Построены графики зависимости суммарной нагрузки на сеть и вероятности потерь оптических блоков. Исследовано влияние на производительность сети сигнальных схем алгоритма установления соединений Just-In-Time.

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

Заключение

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

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

1. Подробно рассмотрены основные промышленные протоколы маршрутизации (RIP, OSPF, EIGRP). Сделан обзор современных технологий, позволяющих применить методы оптимального распределения трафика в сетях передачи данных (MPLS и GMPLS с расширениями Traffic Engineering), что позволяет с более широких позиций подойти к проблеме увеличения производительности полнооптических сетей передачи данных.

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

3. Сформулированы основные задачи, которые необходимо решить для разработки окончательного и практически реализуемого алгоритма распределения информации на основе уменьшения потерь блоков данных: а. разработать математическую модель информационных потоков для сетей с канальной коммутацией (на примере сети оптической коммутации блоков) и на его основе разработать алгоритм поиска оптимальных К-путевых маршрутов. Разрабатываемый алгоритм должен обеспечить контролируемость девиации сетевого потока (иначе говоря — позволяющий ввести ограничение на предельное количество разрешенных к использованию параллельных маршрутов); б. модифицировать существующий алгоритм поиска оптимальных К-путевых маршрутов по критерию средних задержек для сетей с пакетной коммутацией, с целью реализации контроля девиации сетевого потока. в. разработать модель алгоритма динамической маршрутизации для сетей оптической коммутации блоков, позволяющего применить как централизованный (на выделенном вычислителе), так и децентрализованный способ расчета оптимальных маршрутов, а также повысить отказоустойчивость сети; г. реализовать алгоритмы распределения информации в виде программ на ПЭВМ в среде MATLAB; д. разработать имитационную модель сети GMPLS на примере сети оптической коммутации блоков (OBS) с использованием сетевого симуля-тора NS-2; е. разработать модули к среде имитационного моделирования NS-2 на языках программирования С++ и Tel, реализующих разрабатываемый алгоритм распределения информации; ж. провести испытания (имитационное моделирование на ПЭВМ) и оценить эффективность разработанных алгоритмов.

4. Разработана аналитическая модель сетевого потока и сформулирована оптимизационная задача, в которой критерием оптимальности является уменьшение вероятности потерь блоков данных. Задача решена с использованием пакета математических программ MATLAB и реализована градиентным методом. Из за свойств выпуклой штрафной функции задача была сведена к линейной и решена симплекс-методом.

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

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

Список литературы диссертационного исследования кандидат технических наук Нижарадзе, Тимур Зурабович, 2008 год

1. Все уже описано. К счастью, не обо всем еще подумано.1. С. Лец

2. Голышко А. В., Лескова Н. А. Фотонный транспорт: концепция. // Вестник связи. -№ 12, 2000.

3. Иванов П. Оптика в новой ипостаси. // Сети. №23, 2003.

4. Голышко А.В., Лескова Н.А. Оптическая коммутация блоков. // Вестник связи.-№8,2001.

5. Олифер В., Олифер Н. Искусство оптимизации трафика // Журнал сетевых решений LAN-№12, 2001.

6. Qiao С., Yoo М. Choices, Features and Issues in Optical Burst Switching // Optical Networking Magazine. Vol.1, No.2, April 2000. - pp. 36-44.

7. Qiao C., Yoo M. Optical Burst Switching (OBS): A new paradigm for an Optical Internet. // Journal of High Speed Networks. vol. 8, no. 1., 1999 - pp. 69-84.

8. Lisong Xu, Perros H.G., Rouskas G. Techniques for Optical Packet Switching and Optical Burst Switching. // IEEE Communications Magazine. Volume: 39 Issue: 1, Jan. 2001.-Pages: 136-142.

9. Павлов И. П. Системы DWDM: особенности и применение. // Сети и системы связи. № 4, 2003.

10. Yoo М., Qiao С., Dixit S. QoS Performance of Optical Burst Switching in IP-Over-WDM Networks. // IEEE journal on selected areas in communications. -vol. 18, no. 10.-October 2000.

11. Технология волнового мультиплексирования (DWDM) Электронный ресурс. / Корпорация ЮНИ, 2004 Режим доступа: http://www.uni.ru/article/art2536 dwdm.shtml

12. Detti A., Listanti М. Application of Tell & Go and Tell & Wait Reservation Strategies in a Optical Burst Switching Network: a Performance Comparison. // Proceedings of IEEE International Conference on Telecommunication (ICT).

13. Vol.2, June 2000. pp. 540-548.

14. Qiao С., Yoo M. A Novel Switching Paradigm for Buffer-less WDM Networks. // Proceedings of Optical Fiber Communication Conference (OFC). Paper ThM6, Feb. 1999.-pp. 177-179.

15. Davie В., Doolan P., Rekhter Y. Switching in IP Networks. Morgan Kaufmann, 1998.

16. Awduche D. et al. Multi-Protocol Lambda Switching: Combining MPLS Traffic Engineering Control With Optical Cross-connect. / Internet draft, draft-awduche-mpls-te-optical-01 .txt. Nov. 1999.

17. Awduche D. MPLS and Traffic Engineering in IP Networks. // IEEE Commun. Mag., Dec. 1999.

18. Papadimitriou Georgios I., Papazoglou Chrisoula, Pomportsis Andreas S. Optical Switching: Switch Fabrics, Techniques, and Architectures // 384 JLT. -Vol. 21, N0.2. Feb 2003.

19. Turner J. Terabit Burst Switching. // Journal of High Speed Networks. 1999.

20. Ramamirtham J., Turner J. Design of Wavelength Converting Switches for Optical Burst Switching. // WUCS-01-21. Aug 7, 2001.

21. Dragone C. An NxN optical multiplexor using a planar arrangement of two star couplers. // IEEE Photonic Technology Letters. vol. 6, Sept. 1991. - pp. 812815.

22. Haselton E. A PCM frame switching concept leading to burst switching network architecture. // IEEE Comm. Magazine. vol. 21, June 1983. - pp. 13-19.

23. Amstutz S. Burst switching an introduction. // IEEE Communications Magazine. - vol. 21, Nov. 1983. - pp. 36-42.

24. Qiao C. Labeled Optical Burst Switching for IP-over-WDM integration. // IEEE Communications Magazine. Vol.38, No 9, September 2000. - pp. 104-114.

25. Ramaswami R., Sivarajan K. N. Optical Networks: A Practical Perspective. -San Francisco: Morgan Kaufmann, 1998.

26. Masetti F., et al. Fiber Delay Lines Optical Buffer for ATM Photonic Switching

27. Applications. // in Proc. INFOCOM'93. San Francisco, 1993. - pp. 935-942

28. Karasan E., Ayanoglu E. Effects of Wavelength Routing and Selection Algorithms on Wavelength Conversion Gain in WDM Optical Networks. // IEEE/ACM Trans. Networking. №6, 1998.

29. Kovacevic, Acampora A. On Wavelength Translation in All-optical Networks. // in Proc. INFOCOM'95. Boston, 1995. - pp. 413-422

30. Subramaniam S., Barry R. Wavelength Assignment in Fixed Routing WDM Networks. // in Proc. ICC'97. Montreal, 1997. - pp. 406-415.

31. Blumenthal D. J., et al. Photonic Packet Switches: Architecture and Experimental Implementations. // in Proc. of the IEEE, 82. 1994. - pp. 16501667.

32. Park Jae-Hyun, et al. The Deflection Self-Routing Banyan Network: A Large-Scale ATM Switch Using the Adaptive Self-Routing and its Performance Analyses. // IEEE/ACM Trans. Networking, 7. 1999. - pp. 588-604.

33. Varvarigos E. A., et al. A Virtual Circuit Deflection Protocol. // IEEE/ACM Trans. Networking, 7. 1999. - pp. 335-349.

34. Dutta R.and Rouskas G. N. A survey of virtual topology design algorithms for wavelength routed optical networks. // Optical Networks. №1(1). - January 2000.-pp. 73-89.

35. Baresi M., Bregni S., Pattavina A., Vegetti G. Deflection Routing in Full-Optical IP Switching Networks. // in Proc. of the IEEE ICC 2003.

36. Chen Y., Wu H., Hu D., Qiao C. Performance Analysis of Optical Burst Switched Node with Deflection Routing. // in Proc. of the IEEE ICC 2003.

37. Dueser M., Bayvel P. Analysis of a Dynamically Wavelength-Routed Optical Burst Switched Network Architecture. // Journal of Lightwave Technology. -vol. 20. April 2002. - pp. 574-585.

38. Липский В. Комбинаторика для программистов: Пер. с польск М.: Мир, 1988.-213с. ил.

39. Goldberg А. V. Combinatorial Optimization Lecture Notes for CS363/OR349.

40. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974 -519с.

41. Форд JI. Р., Фалкерсон Д. Р. Потоки в сетях. М.: Мир, 1966.

42. Диниц Е. А. Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой // Докл. АН СССР. 1970. - Т. 194, N 4. - С. 754-757

43. Карзапов А. В. Нахождение максимального потока в сети методом предпотоков // Докл. АН СССР. 1974. - Т. 215, N 1. - С. 49-52.

44. Goldberg А. V., Tarjan R. Е. A New Approach to the Maximum Flow Problem. // J. Assoc. Comput. Mach. №35. 1988. - pp. 921-940

45. Goldberg A. V., Rao S. Length functions for flow computations. // Technical report #97-055: NEC Research Institute. 1997.

46. Черкасский Б.В. Алгоритм построения максимального потока в сети с трудоемкостью 0(|V|"W|E|) действий // Математические методы решений экономических задач. Сб. 7. М.: ВНИИСИ, 1977. - С. 117-126.

47. Элиас П., Фанстейн А., Шеннон К. О максимальном потоке через сеть. // Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963.-с. 729-734.

48. Dijkstra Е. W. A note on two problems in connection with graphs. // Numerische Mathematik, 1. 1959. - p. 269.

49. Bennington G. E., An efficient minimal cost flow algorithm, Report № 75, Department of Industrical Engineering, North Carolina State University at Raleigh. 1972.

50. Bray J. A., Wizgall C., Algorithm 336 NETFLOW, Comm. of ACM, 11, 1961. -p. 631.

51. Busacker R. G., Gowen P. J., A procedure for determining a family of minimal-cost network flow patterns, Operations Research Office, Technical paper 15. -1961

52. Ford L. R., Fulkerson D.R., Flows in networks, Princeton University Press, Princeton. 1962.

53. Klein M., A primal method for minimal cost flows with applications to the assignment and transportation problems, Man. Sci., 14, 1967. p. 205.

54. Johnson E. L. On shortest paths and sorting. // Proc. of Annual Conf. of ACM. -Boston, 1972-p. 510.

55. Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. // Prentice Hall, Englewood Cliffs, N.J. 1993.

56. Лившиц Б. С., Пшеничников А. П., Харкевич А. Д. Теория телетрафика. -Учебник для вузов. 2-е изд., перераб. и доп. М.: Связь, 1979. - 224 е., ил.

57. Астафьев Н. Н. Линейные неравенства и выпуклость. М.: Наука, 1982. -153с.

58. Ашманов С. А., Тимохов А. В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. - 448 с.

59. Baldine I., Cassada М., Bragg A., Karmous-Edwards G., Stevenson D. Just-in-time optical burst switching implementation in the ATDnet all-optical networking testbed. // In Proceedings of Globecom 2003, volume 5. San Francisco, USA. - December 2003.

60. Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981.-383 с.

61. Еремин И. И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. - 192 с.

62. Bannister J., Borgonovo F., Fratta L., and Gerla M. A performance model of deflection routing in multibuffer networks with nonuniform traffic. // IEEE/ACM Transactions on Networking, 3(5):509-520. October 1995.

63. Bellman R. On the approximation of curves by line segments using dynamic programming. // Communications of the ACM, 4(6):284. June 1961.

64. Chen Y., Qiao C., Yu X. Optical burst switching: A new area in optical networking research. // IEEE Network, 18(3): 16-23. May/June 2004.

65. Андронов A. M., Копытов E. А., Гринглаз Л.Я. Теория вероятностей и математическая статистика. Учебник для вузов. СПб.: Питер, 2004.461с.: ил.

66. Антонов А. В. Системный анализ. Учеб. для вузов М.: Высш. шк., 2004. -454 е.: ил.

67. Моисеев Н. Н. Математические задачи системного анализа. — М.: Наука. 1981.-488 с.

68. Таха Хэмди А. Введение в исследование операций, 6-е издание. -Издательский дом "Вильяме". 2001. - 912 с.

69. Канторович J1.B. Функциональный анализ-и прикладная математика. // Успехи мат. наук.— 1948.—Т. 3, № 6.—С. 89-185.

70. Данциг Дж. Б. Линейное программирование, его применение и обобщения. М.: Прогресс. - 1966. - 600 с.

71. Уолрэнд Дж. Телекоммуникационные и компьютерные сети. Вводный курс. М.: Постмаркет, 2001. - 480 с.

72. Ершов М. А., Кузнецов Н. А. Теоретические основы построения сети с интеграцией служб. М.: ИППИ РАН, 1995.

73. Лагутин В. С., Степанов С. И. Телетрафик мультисервисных сетей связи. -М.: Радио и связь, 2000. 320 с.

74. Гмурман В. Е. Теория вероятностей и математическая статистика. Учеб. пособие для вузов. 8-е изд., стер. - М.: Высш. шк., 2002. - 479 с.

75. Вентцель Е. С., Овчаров Л. А. Теория случайных процессов и ее инженерные приложения. Учеб. пособие для втузов. 2-е изд., стер. - М.: Высш. шк., 2002. - 383с.

76. Трифонов А. Г. Постановка задачи оптимизации и численные методы ее решения. Электронный ресурс. Режим доступа:http://www.nsu.ru/matlab/MatLab RU/optimiz/book 1 /index.asp.htm

77. Аоки M. Ведение в методы оптимизации. М.: Наука. 1977. 344с.

78. Бояринов А. И., Кафаров В. В. Методы оптимизации в химической технологии. М.: Химия. — 1975. — 576с.

79. Голыитейн Е. Г., Юдин Д. Б. Задачи линейного программированиятранспортного типа. М.: Наука, 1969. - 382с.

80. Фурунжиев Р. И., Бабушкин Ф. М., Варавко В. В. Применение математических методов и ЭВМ: Практикум. Мн.: Выш.шк. - 1988. - 191с.

81. Кирьянов Д. В. Самоучитель MathCad 2001. СПб.: БХВ-Петербург. -2002. - 544с.

82. Хинчин А. Я. Три жемчужины теории чисел. М.: Наука. - 1979.

83. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир. -1978.-432 е., ил.

84. Pioro М., Medhi D. Routing, Flow, and Capacity Design in Commu-nication and Computer Networks. Morgan Kaufmann. - 2004.

85. Yen J.Y. Finding the K-shortest, loopless paths in a network. // Man. Sci., 17. -1971.-p. 712.

86. Беллман P., Дрейфус С. Прикладные задачи динамического программирования. М., 1965. -460с., ил.

87. Кельтон В., Jloy А. Имитационное моделирование. Классика CS. 3-е изд. -СПб.: Питер; Киев: Издательская группа BHV. 2004. - 847 е.: ил.

88. Березко М. П., Вишневский В. М., Левнер Е. В., Федотов Е. В. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных. // Информационные процессы, Том 1. № 2, 2001. - стр. 103-125.

89. Клейнрок Л. Коммуникационные сети. М.: Наука, 1975.

90. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.

91. Шварц М. Сети ЭВМ. Анализ и проектирование. М.: Радио и связь, 1981.

92. Бертсекас Д., Галлагер Р. Сети передачи данных. М.: Мир, 1989.

93. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы. М.: Мир. - 1981.

94. Мизин И. А., Богатырев В. А., Кулешов А. П. Сети коммутации пакетов. -М.: Радио и связь. 1986.

95. Jackson J. R. Networks of Waiting Lines. // Operations Research, № 5. 1957.pp. 518-521.

96. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука. - 1987.

97. Fratta L., Gerla М., Kleinrock L. The Flow Deviation Method: An Approach to Store-and-Forward Communication Network Design. // Networks, vol. 3, № 2. -1973.-pp. 97-133.

98. Jackson J.R. Networks of Waiting Lines. // Operations Research, № 5.- 1957 -pp. 518-521.

99. Cantor D. G, Gerla M. Optimal Routing in a Packet-Switched Computer Network. IEEE Trans. // Computers, vol. C-23, № 10. 1974. - pp. 1062-1068.

100. Schwartz M., Cheung C.K. The Gradient Projection Algorithm for Multiple Routing in Message-Switched Networks. // IEEE Trans. Commun., vol. COM-24, № 4. 1976. - pp. 449-456.

101. Gerla M., Kleinrock L. On the Topological Design of Distributed Computer Networks. // IEEE Trans. Commun., vol. COM-25, № 1. 1977. - pp. 48-53.

102. Frank M., Wolfe P. An Algorithm for Quadratic Programming. // Naval Research Logistic Quarterly, № 3. 1956. - pp. 95-110.

103. Floyd R. W. Algorithm 97: Shortest Path. Comm. // ACM, № 3. 1962 - p. 345.

104. Murchland J. D. A965), A new method for finding all elementary paths in a complete directed graph, London School of Economics, Report LSE-TNT-22.

105. Федотов E. В. Определение оптимальных маршрутов в сети пакетной коммутации. // В сборнике: Сетевая обработка информации. М.: МДНТП, 1990.-стр. 95-98.

106. Gavish В., Hantler S. L. An Algorithm for Optimal Route Selection in SNA Networks. // IEEE Trans. Commun., vol. COM-31, № 10. 1983. - pp. 11541161.

107. Courtois P. J., Semal P. An Algorithm for the Optimization of Nonbifurcated Flows in Computer Communication Networks. // Performance Evaluation, vol. 1. 1981.-pp. 139-152.

108. Вишневский В. М., Федотов Е. В. Анализ методов маршрутизации при проектировании сетей пакетной коммутации. // 3rd I.S. "Teletraffic Theory and Computing Modeling". София. - 1990.

109. Мину M. Математическое программирование. Теория и алгоритмы. М.: Наука, - 1990.

110. Поляк Б. Т. Введение в оптимизацию. М.: Наука. - 1983.

111. Held М., Wolfe P., Growder Н.Р. Validation of Subgradient Optimization. // Mathematical programming, № 6. 1974. - pp. 62-88.

112. Dijkstra E. W. A Note on Two Problems in Conection with Graphs. // Numer. Math., № 1.- 1959. pp. 269-271.

113. Land A.H., and Doig A.G. An autmatic method of solving discrete programming problems. // Econometrica, v28. 1960. - pp 497-520.

114. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. // Operations Research, vl 1. 1963. - pp. 972-989.

115. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. M. Наука. Гл. ред. физ.-мат. лит. 1969.

116. Зайченко Ю. П. Задачи проектирования структуры распределенных вычислительных сетей. // Автоматика, № 3. 1981. - С. 35-44.

117. Жожикашвили В. А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь. - 1988.

118. Нижарадзе Т. 3. Алгоритм оптимальной маршрутизации в сетях оптической коммутации блоков // Информационные технологии моделирования и управления № 6(24). Воронеж: науч.-техн. журнал, 2005 - С. 872-877.

119. Нижарадзе Т. 3., Суконщиков А. А. Метод оптимального распределения трафика в сетях оптической коммутации блоков // Информационно-вычислительные технологии и их приложения. Пенза: РИО ПГСХА, 2005. -С. 152-155.

120. Нижарадзе Т. 3. Моделирование сетей оптической коммутации блоков с использованием пакета Network Simulator 2. // Кибернетика и высокие технологии XXI века: Материалы VII межд. науч.-техн. конф.т.2. -Воронеж, 2006. - С. 773-781.

121. Нижарадзе Т. 3. Алгоритм многопутевой маршрутизации в сетях оптической коммутации блоков. // Системы управления и информационные технологии № 2.1(24) Воронеж: науч.-техн. журнал, 2006-С. 167-170.

122. Сетевой симулятор ns-2 Электронный ресурс. Электрон, докум. и прогр. - Режим доступа: http://www-mash.CS.Berkeley.EDU/ns.

123. Официальный сайт проекта VINT Электронный ресурс. .- Режим доступа: http://www.isi.edu/nsnam/vint/index.html

124. Вопросы развертывания MPLS-TE Электронный ресурс. .- Режим доступа: http://www.cisco.com/en/US/tech/tk436/tk428/technologies white рарег09186а00800a4472.shtml#wp39803