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

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

НИЖАРАДЗЕ Тимур Зурабович

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

05 13 13 - "Телекоммуникационные системы и компьютерные сети" (технические науки)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

□□3166642

Вологда, 2008

003166642

Работа выполнена на кафедре Автоматики и вычислительной техники Вологодского государственного технического университета

На\чный руководитель - кандидат технических наук, доцент

СУКОНЩИКОВ Алексей Александрович Официальные оппоненты - кандидат технических наук, доцент

ФИЛИППОВ Владимир Александрович - доктор технических наук, профессор СВИРИДОВ Александр Петрович

Ведущая организация - Институт проблем передачи информации

Российской академии наук

Защита состоится «29» апреля 2008г в «16 00» на заседании диссертационного совета Д 212 133 03 Московского государственного института электроники и математики по адресу 109028, г Москва, Большой Трехсвятительский пер , д 3/12, зал Ученого совета

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу 109028, Москва, Большой Трехсвятительский пер , д 3/12, диссертационный совет Д 212 133 03

Автореферат разослан «_» марта 2008 года

Ученый секретарь

- ЮЛ Леохин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Методы расчета оптимальных многопутевых маршрутов были известны задолго до появления технологии MPLS (Л Клейнрокк, Дж Р Джексон, Дж Д С Литтл, В М Вишневский, Е В Левнер, Е В Федотов и др) Однако в промышленных сетях передачи данных многопутевое распределение трафика почти не применялось из-за сложностей ее практической реализации

Для сетей пакетной коммутации наиболее известным методом расчета оптимальных многопутевых маршрутов является алгоритм, впервые предложенный в работе Л Фратта, М Герла и Л Клейнрока Ими была изучена модель сети пакетной коммутации в виде сети массового обслуживания, в которых узлы описываются системой М/М/1Л*> Для данной модели была найдена взаимосвязь между нагрузкой на сеть и величиной средней задержки пакетов в сети Указанная взаимосвязь дала возможность сформулировать и решить сетевую оптимизационную задачу, позволяющую найти между всеми парами источник/адресат такой набор многопутевых маршрутов, при котором суммарные задержки пакетов в сети были бы минимальны

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

1 LSP-туннели являются способом задания многопутевых маршрутов в сетях MPLS Г\

Успех MPLS дал толчок для создания универсальной технологии коммутации с использованием меток Новая технология получила название Generalized MPLS (GMPLS - обобщенный MPLS) Она расширяет и унифицирует функции (маршрутизации и сигнализации) MPLS din любых транспортных технологии канального и физического уровней В частности, появление технологии плотного волнового мультиплексирования (Dense Wavelength Division Multiplexing - DWDM) и технологий коммутации оптических сигналов предопределило появление концепций полнооптических сетей, в которых данные коммутируются непосредственно в оптическом виде, без преобразования сигнала в электронную форму, тес точки зрения теории телетрафика указанные сети используют метод канальной коммутации, с использованием сигнальных протоколов GMPLS Несмотря на обширность и глубокую проработанность тем, связанных с исследованием сетей с канальной коммутацией, одной области исследований - алгоритмов и принципов распределения информации (маршрутизации) - было уделено сравнительно мало внимания

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

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

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту

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

- алгоритм поиска оптимальных К-путевых маршрутов по критерию вероятности потерь,

- алгоритм контроля девиации сетевого потока,

- алгоритм поиска запасных маршрутов,

- имитационная модель сети оптической коммутации блоков,

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

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

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

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

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

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

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

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

Разработанная в диссертации имитационная модель исследуемой сети и алгоритм оптимального распределения сетевых потоков используется в демонстрационной лабораторной работе по дисциплине «Сети ЭВМ и телекоммуникации» на кафедре Автоматики и вычислительной техники ВоГТУ Имеется соответствующий Акт об использовании

Апробация работы Основные результаты диссертационной работы докладывались и получили одобрение на заседаниях кафедры «Автоматики и вычислительной техники» ВоГТУ, на заседаниях комиссий по аттестации аспирантов в 2003-2007гг , а также на международных и всероссийских научно-технических конференциях Международная научно-техническая конференция «Автоматизированная подготовка машиностроительного производства, технология и надежность машин, приборов и оборудования» (Вологда, 2005), III международная научно-техническая конференция «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта» (Вологда, 2005), Международная научно-техническая конференция «Информационно-вычислительные технологии и их приложения» (Пенза, 2005), VII международная научно-техническая конференция «Кибернетика и высокие технологии XXI века» (Воронеж, 2006)

Публикации. Автор имеет 7 опубликованных работ по теме диссертации, из них 4 на международных конференциях, 2 в научно-технических журналах и 1 в журнале [7], включенном в «Перечень ведущих рецензируемых научных журналов и изданий », рекомендуемых к публикации ВАК

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и 6 приложений Основная часть работы изложена на 161 странице Список литературы состоит из 124 наименований, таблиц 5, рисунков 38

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Подробно рассмотрены существующие алгоритмы поиска оптималь-

ных маршрутов графовыми методами, а так же методами математического программирования

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

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

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

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

Обозначим сеть в виде ориентированного графа G = (V,E) , где У = 1,2, ,V множество узлов (вершин) сети и е = 1,2, ,Е множество однонаправленных оптических линий (дуг), d = 1,2, ,D - нагрузки между источниками и получателями

Выразим интенсивности трафиков, являющихся исходными данными, в виде вектора где Äd - параметр потока вызовов или средняя скорость формирования блоков (вызовов) на узле Sd предназначенных узлу Td Пусть 1/Дг = LKaöpajvка1ШШ , где Д/ - параметр длительности обслуживания, зависящий от скорости канала Укашш и средней длины блоков данных LK(K), передаваемых от узла Sd к узлу Td, тогда у(1 = Ä(j /ßd - предполагаемая интенсивность формируемых блоков (вызовов) узлом Sd в единицу времени

Пусть pL - вероятность потерь блоков на дуге е Сделаем допущение, что pt « 1 для любой дуги и что вероятность потерь на дуге е не зависит от источника или получателя блока, а так же не зависит от предыдущего пути, по которому прошел блок до поступления в дугу е В этом случае вероятность потерь блоков р(л) на пути л, согласно формуле надежности параллельных систем, будет равна

/»(л-Н-ПО-ЛЫР*«1 (1)

t-ел- сея

Следовательно, мы можем допустить, что наблюдаемая в сети реальная интенсивность трафика между узлами Sd и Td равна исходной интенсивности трафика уj Это допущение близко к истине в случае малых вероятностей потерь

Пусть хп/ - доля сетевого трафика между узлами и Т11 на дуге е, О < хес1 < 1 Следовательно, вся потерянная нагрузка в сети может быть выражена так

^ = (2)

«е£Ч ЛС /

где ^ >',/*«/ = >>( - суммарная интенсивность нагрузки на дуге е в предполо-£/еО

жении, что потери блоков отсутствуют

Сделаем допущение, что модель поступления трафика на любой дуге -пуассоновская с показательным распределением длительности обслуживания (простейший поток вызовов) Необходимо отметить, что даже в случае, когда источники формируют простейший поток вызовов - интенсивность поступления блоков данных на конкретную дугу может уменьшиться вследствие потерь на предыдущих дугах, соответственно трафик на данной дуге не будет пуассоновски и Тем не менее, если потери блоков относительно малы, то мы можем считать, что этот «разреженный» поток для любых дуг - тоже пу-ассоновский В этом случае вероятность потерь в каждой дуге е можно выразить первой формулой Эрланга

у "/и»

1>,7'

1=0

где IV- количество частотных каналов на дуге е

Подставив в выражение (3) выражение (2) получим

У1 = Е(Рг(Уе)ХУе) №

ее Е

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

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

Рассмотрим суммируемое выражение в формуле (4) и назовем его оценочной функцией Пусть

Ре(Уе)=РЛУе)ХУе (V

Построив семейство кривых и исследовав поведение функции ^е(уе) при различных значениях постоянной IV, выяснено, что все кривые оценочной функции являются выпуклыми Из теории системного анализа известно, что в этом случае задачу (4) возможно сформулировать в терминах линейно-

го программирования путем аппроксимации функции Р1(уе) кусочно-линейной гск (уе), где - К - количество линейных сегментов

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

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

Приведем окончательную формулировку задачи поиска оптимальных маршрутов по критерию минимизации потерь с учетом возможности контроля девиации сетевого потока (предотвращения эффекта «растекания» нагрузки)

индексы

с1 = 1,2, , В нагрузки между источниками и получателями е = 1,2, ,Е однонаправленные каналы связи (дуги орграфа) р = 1,2, пути потоков, реализующих нагрузку г/

к = 1,2, ,Ке последовательные части функции Ре(уе) константы

Иц величина нагрузки <1

дцф =1, если канал е принадлежит пути р, реализующий нагрузку с1 аек>Ье к коэффициенты линейных частей функции п^ максимально разрешенное количество маршрутов нагрузки с1

переменные

Хф доля нагрузки с/ на пути р

уе нагрузка канала с

ге непрерывная переменная, аппроксимирующая Р"е()'е)

Нф бинарная переменная, связанная с переменной Хф

целевая функция

т1п/г = £'; (5)

I

ограничения

^ад+^е где е = 1,2, ,£",£ = 1,2, ,К

Уе =ХЕ. где е = 1,2, , £

л Р

= Е *<//» > где <1 = 1,2,

р

£ £йф*ф=о, (6)

Чтобы реализовать ограничение на максимальное число разрешенных к использованию маршрутов в задачу введены бинарные переменные иир, ассоциированные с соответствующей переменной Поставленная задача является целочисленной С учетом того, что вводимая переменная «ф является бинарной, наиболее подходящим методом ее решения является метод ветвей и границ Пусть 1, те применять маршрут р нагрузки с/ - разрешается

Тогда в соответствии с формулой (6) переменная Хф может принимать любые значения, иначе - Хф всегда будет равна 0 Таким образом бинарные переменные стали коэффициентами линейного ограничения, т е задача целочисленного программирования сведена к частной задаче линейного программирования относительно заданного множества N значений переменных Иф,

Ы= ! г/ф р -1,2, ,Р^ = 1,2, ,£>}

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

Пусть для нагрузки с! алгоритмом Иена найдено Р11 маршрутов Пусть к с] -максимальное число маршрутов, разрешенное к использованию и при этом к^ < Р<] Тогда количество возможных вариантов использования маршрутов для данной нагрузки с/будет равно числу сочетаний по к^

Заметим, что если ки>Р11, то к использованию разрешены все маршруты Рс/ и при этом необходимо проверить только одну комбинацию, когда все «ф=1 для всех р = 1,2, Таким образом максимальное количество комбинаций значений бинарных переменных Мф (а соответственно и максимально возможное число итераций поискового алгоритма) можем выразить так

1 = П СРа

'шах

ЛО

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

матрицы ис/ Размерность матрицы {/^ составляет столбцов и строк

Обозначим иЛк] - к-тую строку матрицы ис/ Тогда текущая комбинация N переменных ис/р может быть получена путем последовательного объе-

динения строк из всех матриц Ud, т е

Л/ = | U,1k,} U2[k2] U[к] }, \<i< D где кI, к2, , к, - индексы текущего сочетания переменных udp для нагрузки d, переменная i - глубина рекурсии алгоритма ветвей и границ В процессе работы поискового алгоритма из каждой матрицы Uj извлекается по одной строке, которые далее объединяются в один вектор N Этот вектор будет содержать текущую комбинацию переменных udp на глубине рекурсии /, которую уже можно подавать на вход задачи линейного программирования в виде выражения (6)

Разработанный алгоритм был реализован с использованием пакета математических программ Matlab Практика показала, что время поиска оптимума для сети, состоящей из 14 узлов, 12 каналов и 8 различных нагрузок составляет меньше секунды

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

Моде 1ь алгоритма динамической маршрутизации

При разработке модели были поставлены следующие задачи

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

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

3 Разработать алгоритм равноприоритетного распределения остаточной пропускной способности сети между всеми источниками трафика

Технология GMPLS предусматривает использование протоколов OSPF (или IS-IS) и протокола MP-BGP Установка оптимальных маршрутов осуществляется протоколом CR-LDP

Централизованный способ расчета оптимальных маршрутов предполагает наличие в сети одного или нескольких выделенных вычислителей маршрутов (RC) Так как для доставки маршрутной информации между РЕ-маршрутизаторами используется протокол MP-BGP, то для доставки информации об источниках и получателях предлагается функции RC-вычислителей совместить с функцией BGP-отражателей Тем самым мы обеспечим алгоритм расчета оптимальных маршрутов исходными данными Вычисленные маршруты передаются всем источникам (РЕ-маршрутизаторам) по протоколу MP-BGP

При децентрализованном способе расчета маршрутов в качестве транспорта исходных данных предлагается использовать протокол OSPF (LSA Туре 10) Распределение трафика в сети будет оптимальным только в том случае, если все РЕ-маршрутизаторы будут иметь идентичные входные данные алгоритма расчета оптимальных маршрутов (соответственно - идентичный набор маршрутов) Для достижения этой цели вводится механизм син-

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

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

Алгоритм поиска запасных маршрутов

Для повышения отказоустойчивости сети разработан алгоритм поиска запасных маршрутов, который позволяет обеспечить непрерывность связи между источником и получателем при выходе из строя одного элемента сети (узла или канала) В его основе автор воспользовался известным алгоритмом поиска двух кратчайших маршрутов, не пересекающихся ни в одной из своих вершин Недостаток указанного алгоритма заключается в том, что если в сети существует хотя бы один (критический) узел, в котором все маршруты между данной парой источник/адресат пересекаются, то алгоритм завершится, не найдя маршрутов Тем не менее существует возможность найти два альтернативных маршрута с минимальным числом пересечений в узлах Для этого предлагается исходный граф в разбить на подграфы, заключенные между критическими вершинами исходного графа А затем для каждого подграфа решить задачу поиска альтернативных маршрутов После этого найденные в каждом подграфе маршруты необходимо соединить

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

В случае, если один или оба вычисленных маршрута совпадут с маршрутами, найденными оптимизационным алгоритмом, то они могут быть исключены - отказоустойчивость будет соблюдена автоматически Функциональная схема модели алгоритма маршрутизации На Рис 1 представлена функциональная схема разработанной модели алгоритма динамической маршрутизации База исходных данных включает в себя 1) топологию, емкость линий связи, размер коммутационной матрицы в узлах сети (протокол ОБРР), 2) источников и получателей трафика, формируемую ими нагрузку (протокол МР-ВСР) При децентрализованном расчете маршрутов расчет выполняют РЕ-маршрутизаторы При централизованном -ЯС-вычислители (доставка вычисленных маршрутов осуществляется протоколом МР-ВвР)

На основе топологической информации осуществляется расчет запасных маршрутов Затем протокол СЯ-ЬОР устанавливает ЬЯР-туннели запас-

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

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

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

Оптимизация распределения нагрузки в сети IP-MPLS.

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

1. Обеспечить автоматическое определение необходимого количества LSP-туннелей и соответствующих им коэффициентов балансировки нагрузки.

2. Количество LSP-туннелей для каждой нагрузки не должно превысить наперед заданного числа.

3. Каждой нагрузке (паре источник/получатель), из условия равиости

приоритета предоставить максимальную пропускную способность

4 При распределении нагрузки обеспечить 5% резерв в каждом канале для целей передачи служебного трафика

5 Сетевую нагрузку распределить по маршрутам, обеспечивающим наименьшую задержку для пакетов

В соответствии с RFC 3209 и RFC 3212 задание полного пути следования пакетов возможно при помощи LSP-туннелей Поэтому разработанная методика полностью подходит для решения первой задачи Вторая задача есть ограничение на количество разрешенных к использованию маршрутов -решается в рамках предложенной методики

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

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

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

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

1 DWDM-канал,

2 фотонный коммутатор, в т ч алгоритм коммутации,

3 протокол занятия канала связи,

4 очередь управляющих сообщений,

5 источник блоков данных

На языках программирования С++ и Tel были разработаны следующие модули, моделирующие компоненты сети OBS

- очередь использования подканалов,

- алгоритм резервирования оптических путей Just-In-Time,

- генератор трафика (простейший поток вызовов и детерминированный поток),

- алгоритм коммутации блоков данных

Топология исследуемой сети представлена на Рис 2 Во всех исследованиях используется 4 пары источник-получатель(81-01, S2-D2 и т д )

S1

S2

S4

Рис. 2 Топология исследуемой сети оптической коммутации блоков.

Исходными данными для моделирования являются:

1. Емкость каждой DWDM-линии равна 32 каналам, каждый из которых передает со скоростью 2 Гбит/с/ Длина каждой линии - 100 км.

2. Скорость управляющего канала 622 Мбит.

3. Емкость оптического коммутатора в каждом узле достаточна для коммутации всех входящих линий во все исходящие

4. Алгоритм установления канала связи - Just-In-Time с неявной установкой и плановым завершением передачи блока.

5. Средний размер блоков данных составляет 2 Мбайт.

6. Время моделирования - 2 секунды.

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

Для сравнения рассмотрены четыре способа распределения информации.

1 способ - разработанный нелинейный алгоритм распределения информации. На графике будет обозначен как GMNL (Gradient Method of Nonlinear Programming).

2 способ - разработанный линейный алгоритм, использующий аппроксимацию выпуклой штрафной функции кусочно-линейной функцией. На графике - CCLP (Convex Cost Linear Programming)

3 способ - линейное распределение нагрузки по критерию стоимости и ограничением на пропускную способность каналов. На графике - BCLP (Bandwidth Cost Linear Programming).

4 способ - маршрутизация по кратчайшим маршрутам. На графике - SP (Shortest Path Routing).

Все представленные методы, кроме алгоритма кратчайших путей, реализованы методами математического программирования в среде Matlab

Е 0.01

0.001

0.0001

10000 15000 20000 25000 30000 35000 Суммарная нафузка, блок/сек

40000 45000

Е

■ BCLP -*-CCLP -*-GMNL -

-SP

Рис. 3 Зависимость потерь от нагрузки.

10000 15000 20000 25000 30000 35000 40000 45000

Внешний график, блок/сек

Рис. 4 Зависимость переданных данных от полного внешнего трафика

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

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

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

ОБРР. Критерий оценки эффективности - пропускная способность сети.

В качестве источников трафика использованы пары РТР-сервер и РТР-клиент. Нагрузки на сеть, а так же направление передачи трафика представ-

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

Источник Получатель CCLP, Мбит/сек SP, Мбит/сек

2 7 311 284

3 7 334 205

13 7 466 121

7 4 335 276

7 5 317 209

7 12 299 197

7 13 309 225

12 8 485 328

Общая пропускная способность сети: 2853 1845

Как видно из таблицы, предлагаемая методика в части увеличения пропускной способности сети эффективнее алгоритма ОЗРР.

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

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

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

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

ных Задача была решена градиентным методом Благодаря свойствам выпуклой оценочной функции задача сведена к линейной и решена симплекс-методом Выявленная проблема девиации сетевого потока решена путем введения дополнительного ограничения Полученная целочисленная задача решена методом ветвей и границ Оптимизирована скорость поиска оптимума

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

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

В Приложение вынесены распечатки листингов разработанных программ, выходные данные экспериментов, акты о внедрении

Список публикаций по теме диссертации

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

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

3 Нижарадзе Т 3 , Суконщиков А А Решение задачи оптимального распределения трафика в сетях оптической коммутации блоков // Системы и методы обработки и анализа информации Сборник научных статей / Под ред С С Садыкова, Д Е Андрианова — М Горячая линия - Телеком, 2005 -С 175-180

4 Нижарадзе Т 3 Среда имитационного моделирования сетей оптической коммутации блоков // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и искусственного интеллекта Материалы межд науч-техн конф - Вологда ВоГТУ, 2005 -С 106-109

5 Нижарадзе Т 3 , Суконщиков А А Алгоритм коммутации блоков данных в сети оптической коммутации блоков // Автоматизированная подготовка машиностроительного производства, технология и надежность машин, приборов и оборудования материалы межд науч -техн конф Т 2 - Вологда ВоГТУ, 2005 -С 103-106

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

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

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

Введение.

Глава 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.

Когда необходимо доставить сетевой трафик из точки- А* в точку Б, ни один способ не подойдет всем приложениям сразу. Голосовым и видеоприложениям требуется минимальная вариация задержки, в то время как критически важным приложениям - жесткие гарантии предоставления сервиса и резервных маршрутов: 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. С помощью имитационного моделирования исследовано функционирование и подтверждена эффективность предлагаемого алгоритма оптимального распределения информационных потоков. Исследовано влияние выбора стратегии резервирования оптических путей на производительность сети.

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