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

• Автор: Нижарадзе, Тимур Зурабович
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Вологда
• Количество страниц: 188 с. : ил.

СОДЕРЖАНИЕ

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

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

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

1.1 1 Дистанционновекторный протокол I

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

1.1.3 Протокол I.

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 Методы реализации многопутевой маршрутизации. Технология .
1.4.1 Протокол распространения меток .
1.4.2 Задача выбора оптимальных маршрутов
1.4.3 Технология i ii.
1.4.4 Механизмы , реализующие i ii
1.5 Полнооптические сети с коммутацией каналов. Технология
1.5.1 Сеть оптической коммутации блоков
1.5.2 Технология
1.5.3 Архитектурные решения коммутационного устройства узла сети
1.5.4 Алгоритмы установления канала связи
1.5.5 Существующие методы распределения потоков в сети
1.6 Постановка задачи поиска оптимальных маршрутов в полнооптических сетях с канальной коммутацией.
1.7 Выводы по главе I
Глава 2. Разработка алгоритма оптимального распределения информации, в сетях с канальной коммутацией.
2.1 Формулирование оптимизационной задачи
2.2 Решение оптимизационной задачи градиентным методом.
2.3 Решение оптимизационной задачи симплексметодом
2.4 Алгоритм поиска маршрутов из найденного вектора распределения сетевого трафика
2.5 Разработка алгоритма конроля девиации сетевого потока
2.6 Выводы по главе 2.
Глава 3. Разработка модели алгоритма динамической маршрутизации в сетях с канальной коммутацией
3.1 Объекты сети оптической коммутации блоков.
3.2 Протокол установления маршрутных туннелей
3.3 Алгоритм расчета текущей нагрузки вдоль сессии.
3.4 Повышение отказоустойчивости сети. Алгоритм расчета запасных маршрутов
3.5 Функциональная схема разработанной модели алгоритма динамической многопутевой маршрутизации.
3.6 Оптимизация распределения нагрузки городской сети I Вологодского филиала ОАО СевероЗападный Телеком.
3.6.1 Постановка задачи оптимального распределения трафика.
3.6.2 Модификация алгоритма расчета оптимальных маршрутов для сетей
с пакетной коммутацией.
3.7 Выводы по главе 3.
Глава 4. Разработка имитационной модели сети и моделирование разработанного алгоритма динамической маршрутизации
4.1 Разработка модели сети оптической коммутации блоков
4.1.1 Модуль протокола установления канала связи.
4.1.2 Модуль оптической линии.
4.1.3 Модуль фотонного коммутатора, коммутационный алгоритм
4.1.4 Модуль имитации агента источника блоков данных.
4.1.5 Сбор статистики и формирование результатов моделирования.
4.2 Имитационное моделирование сети оптической коммутации блоков
4.3 Оптимальное распределение трафика в сети 1 Вологодского филиала ОАО СевероЗападный Телеком
4.4 Выводы по главе
Заключение.
Список использованной литературы


При постановке задачи узловой коммутатор был принят полнодоступным и неблокирующим. В задачу внесена модификация, позволяющая учесть 0раничение на количество одновременных соединений в узловом коммутаторе. Вследствие появления эффекта сильного разветвления потоков но различным маршрутам в задачу внесено ограничение на максимальное количество используемых маршрутов, разрешенных к использованию каждой нагрузкой. Задача решена целочисленным программированием методом ветвей и границ путем введения дополнительных бинарных переменных. Третья глава посвящена разработке модели алгоритма динамической маршрутизации для сетей ОМРЬБ с канальной коммутацией. Модель включает в себя алгоритмы поиска оптимальных и запасных маршрутов. Показана применимость разработанного алгоритма динамической маршрутизации при двух вариантах управления сетевыми потоками централизованным способом на выделенном вычислителе и децен грализованным. Определены объекты сети, необходимые для функционирования разработанного алгоритма граничные и транзитные узлы, узловые коммутационные устройства, вычислитель маршрутов. Определены условия и способ предоставления канала связи двум абонентам. Определен способ установления оптимальных маршрутов с помощью протокола СЯЬПР, а так же принято ограничение на количество узлов сети, в которой может быть применен разрабатываемый алгоритм. Разработан алгоритм сбора статистических данных о переданной нагрузке между приемником и получателем для их дальнейшей передачи в качестве исходных данных алгоритму расчета оптимальных маршрутов. Даны рекомендации по установке начальных параметров алгоритма для различных типов планирования распределения нагрузки при стратегическом планировании и для случаев оперативного реагирования на изменения в сети. Разработан алгоритм расчета величин нагрузок, удовлетворяющих двум условиям 1 каждой нагрузке предоставлена минимальная гарантированная полоса пропускания, и 2 каждой нагрузке предоставлена максимальная полоса пропускания из условия равного приоритета всех нагрузок. Разработан алгоритм расчета запасных маршрутов, позволяющий повысить отказоустойчивость сети. Разработана функциональная схема полученной модели алгоритма динамической маршрутизации для полнооптических сетей с канальной коммутацией. В алгоритм расчета оптимальных маршрутов внесена модификация с целью возможности его применения в. I Вологодского филиала. ОАО СевероЗападный Телеком. В соответствии с поставленной зада
чей изменен критерий оптимальности распределение нагрузки по маршрутам, обеспечивающим минимальные задержки для пакетов. Четвертая глава посвящена разработке имитационной модели сети с канальной коммутацией на примере сети и моделированию полученного алгоритма распределения информации. В качестве базового выбран популярный сетевой симулятор 2. Для реализации модели исследуемой сети осуществлено ее разбиение на функциональные блоки, т. СЬ4 и разработаны соответствующие им модули. Верификация модели осуществлена путем отладки, контроля входных и выходных параметров, а так же визуального контроля анимации результатов прогона модели. С помощью имитационного моделирования исследуемой сети осуществлено сравнение полученного алгоритма с двумя существующими алгоритмами многопутевой маршрутизации, основанным на решении задачи поиска оптимальных маршрутов по критериям а средней задержки блоков, б ограничению на емкость каналов, а так же осуществлено сравнение с алгоритмом наикратчайших маршрутов. Построены графики зависимости потерь блоков данных от суммарной нагрузки на сеть, из которых следует, что для сети оптической коммутации блоков разработанная методика эффективнее существующих методов распределения информации. При моделировании использованы маршруты, найденные модифицированным оптимизационным алгоритмом. Полученные результаты были сравнены с результатами прогона имитационной модели при работе алгоритма кратчайших маршрутов. Сравнительный анализ показал, что предлагаемая методика эффективнее существующего способа маршрутизации по кратчайшим маршрутам. В Заключении сформулированы основные результаты работы.