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

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

ПОЗДНЯК Ирина Сергеевна

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

Специальность 05.12.13 — «Системы, сети и устройства телекоммуникаций»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Самара 2009

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» (ГОУВПО ПГУТИ).

Научный руководитель:

доктор технических наук профессор Лихтциндер Б. Я.

Официальные оппоненты:

доктор технических наук профессор Прохоров С. А.

кандидат технических наук доцент Гавлиевский С. Л.

Ведущая организация:

ГОУ ВПО «Самарский государственный технический университет»

Защита диссертации состоится «22» мая 2009 г. в 12-00 часов на заседании диссертационного совета Д219.003.02 при Поволжском государственном университете телекоммуникаций и информатики по адресу: 443010, Самара, ул. Л. Толстого, 23

С диссертацией можно ознакомиться в библиотеке ГОУВПО ПГУТИ.

Автореферат разослан «21» апреля 2009 г. Ученый секретарь

диссертационного совета Д219.003.02 доктор технических наук, доцент Мишин Д. В.

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

Актуальность темы.

Характерной тенденцией современного этапа развития компьютерных сетей является принципиальное изменение структуры передаваемого трафика. Анализ статистики агрегированного трафика большинства сетей доступа в Интернет явно показывает высокую долю в нем аудио- и видео-потоков данных. Можно определенно утверждать, что трафик сетей доступа в Интернет, а также сетей крупных предприятий, стал мультимедийным. При этом постоянно разрабатываются и внедряются новые алгоритмы, протоколы и технологии, которые в определенной степени улучшают качество передачи трафика реального времени в IP-сетях. Следствием этого является существенное усложнение архитектуры сетей TCP/IP, которые теперь характеризуются не просто как сети передачи данных, а как мультисервисные.

Между тем, каналы передачи данных, подходящие для предоставления одной услуги, не всегда подходят для предоставления другой. Увеличение объемов предоставляемых услуг заставляет операторов и провайдеров параллельно развивать несколько различных сетей. Это требует больших затрат и часто сопряжено со значительными техническими трудностями.

Маршрутизация на сегодняшний день определяется не формальными правилами и описаниями, характерными для сетей предыдущих поколений, а требованиями клиента и экономическими соображениями оператора связи. Чтобы оптимизировать работу сетей, разрабатываются различные методы маршрутизации, обеспечивающие сбалансированную нагрузку всех сетевых ресурсов. Среди зарубежных ученых, изучающих данную проблему, стоит особо выделить D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus, S. Hiroyuki, M. Yasuhiro, Y. Makiko и др.

Чтобы успешно передать по сети потоки информации самого различного рода необходимо, чтобы алгоритм маршрутизации учитывал требования, предъявляемые данными потоками к уровню качества обслуживания (Quality of Service, QoS). Для этого весь трафик подразделяют на классы сервиса. И тогда маршрутизация по всей сети будет осуществляться в соответствии с классом сервиса каждого отдельного потока. В России вопросами маршрутизации и смежными с ними проблемами занимаются Б.С. Гольдштейн, В. М. Вишневский, Ю.А. Семенов, В. Н. Тарасов, А. В. Росляков, С. Н. Степанов и др.

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

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

Объектом исследования являются методы маршрутизации в сетях с пакетной коммутацией (мультисервисные сети).

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

Цель работы и задачи исследования. Цель диссертации состоит в уменьшении размерности задачи маршрутизации в мультисервисных сетях.

Для достижения поставленной цели необходимо провести анализ существующих методов маршрутизации и решить следующие задачи:

- разработать алгоритм определения набора допустимых оптимальных маршрутов;

- разработать способ распределения потоков трафика по набору допустимых маршрутов;

- создать модель работы предложенного алгоритма;

- выполнить программную реализацию разработанного алгоритма;

- провести компьютерное моделирование процесса маршрутизации сети с использованием разработанного алгоритма.

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

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

Научная новизна результатов.

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

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

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

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

работе, переданы для эксплуатации в Центр информационных технологий Оренбургского государственного университета и в ООО «Инфосфера», а также использованы в учебном процессе ПГУТИ.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на VII Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2006), XIII Международной НТК «Радиолокация. Навигация. Связь» (Воронеж,

2007), XII Всероссийской НТК «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2007), Пятой Всероссийской НТК «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2007), III Международной НТК (Винница, 2007), Международной НТК ТЕЛЕКОМ-2007 (Ростов-на-Дону, 2007), 63-й научной сессии, посвященной Дню радио (Москва,

2008), российских НТК профессорско-преподавательского состава ПГАТИ (Самара, 2006 - 2009).

Публикации. По теме диссертации опубликовано 16 работ, в том числе 1 статья в журнале, входящем в перечень ВАК РФ, 14 тезисов и текстов докладов.

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

1. Формализованная в терминах теории графов задача построения минимального направленного графа.

2. Графовая модель набора допустимых маршрутов между узлами мультисервисной сети.

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

4. Способы распределения потоков трафика по набору допустимых маршрутов.

5. Комплекс программных средств, реализующих предложенный алгоритм.

6. Результаты моделирования сетей с использованием предложенного алгоритма маршрутизации.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, списка литературы. Работа содержит 130 страниц машинописного текста, 38 рисунков и 3 таблицы. Список литературы включает в себя 70 наименований.

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

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

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

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

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

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

В первой главе также приводится описание и принципы действия основных протоколов маршрутизации, наиболее часто используемых в мультисервисных сетях. Приведены определения протоколов внутреннего (ЮР) и внешнего шлюзов (EGP). Показано, что наиболее часто используется протокол OSPF, который относится к протоколам маршрутизации по состоянию каналов, и обеспечивает обмен информацией в пределах автономной системы AS. Менее распространенный протокол IS-IS относится к протоколам ЮР с использованием принципа маршрутизации по состоянию каналов. Принципы маршрутизации данного протокола во многом схожи с теми, что используются в OSPF. Отличительной чертой является процесс обмена служебной информацией, для которого в IS-IS используется лавинная рассылка пакетов. Третьим протоколом, рассмотренным в главе, является протокола BGP, чья роль гораздо шире, чем протоколов OSPF и IS-IS. Его основное назначение - формировать иерархическую систему маршрутизации, связывающую разные узлы и автономные сети в единую IP-сеть. Показано отличие последней четвертой версии указанного протокола от предыдущих его реализаций.

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

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

1. Резервирование необходимой пропускной способности каналов.

2. Определение множества допустимых маршрутов.

3. Размещение потоков по полученным допустимым маршрутам.

Задача первого уровня для системы М/М/1/» решена в работе следующим образом. Для каждого класса сервиса s задается значение

максимально допустимого коэффициента загрузки рЛйол. р*доп - показывает, какую долю от пропускной способности линии может использовать трафик класса сервиса s. Тогда максимально допустимый поток класса сервиса s, который может пройти через линию (к,1) :

àon = СЫ ' Р àon ' (О

где ск1 - пропускная способность линии (к,1).

Суммарный допустимый коэффициент загрузки линии (к,1) потоками класса сервиса s и более приоритетными классами сервиса:

(2)

g=i

Коэффициент Rsàgn определяет максимальную пропускную способность линии (к,1), которую может использовать суммарный поток

A'h доп, т.е. максимально допустимый поток класса сервиса î и более приоритетных классов сервиса.

s

^■kl don ~ àon — Ckl ' Rèon • (3)

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

Пусть Л^ реальный поток трафика класса 5 и более приоритетных классов, проходящий по линии (к,1).

K=ÎK-«=1

Тогда

ДЛ^Л^-Л;,. (4)

Стоит отметить, что если доступная пропускная способность какой-либо линии для трафика класса s равна нулю, то данная линия не учитывается при построении графа G'.

Таким образом, запас пропускной способности в линии будет определяться из выражения (4).

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

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

Построение минимального направленного графа сводится к четырем основным этапам:

1. ранжирование и последовательная нумерация всех узлов;

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

3. удаление тупиковых маршрутов;

4. проверка связности.

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

за нулевой (ку. =0,/иу. =0), и заканчивая узлом-получателем V.-,

I I J

номер и ранг которого будут определены по окончании этого этапа.

Узлы V- е V и Vj е V (V - множество всех узлов) образуют пару

узлов . Множество узлов I-, инцидентных узлу-источнику, относят к первому рангу = 1) и нумеруют в порядке их возрастания. Ко второму рангу относятся узлы, инцидентные всем узлам первого ранга. Ранжирование производиться до тех пор, пока узел Vу не войдет в число узлов очередного ранга (рис. 1).

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

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

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

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

чит сеть с заданной топологией не будет гарантировать необходимое качество обслуживания С^оБ определенному классу сервиса трафика.

В результате построения минимального направленного графа образуется набор допустимых маршрутов, по которому необходимо распределить потоки информации. Это является задачей третьего уровня. Для этого необходимо определить значение задержки в линии (к, I) е 71®:г для потока трафика , где п]'г - допустимый маршрут,

по которому часть потока у* может достигнуть узла vJ. Каждая линия

имеет пропускную способность сы

бит/ / с.

. Длины сообщений неза-

висимы и распределены по показательному закону со средним значе-

бит/ /пакет _

нием 1 / ft'

Допустимый маршрут п'уг представляет собой последовательность направленных линий связи, через которые должен пройти поток X]f = хУ ■ у у. Величина x*jr определяет долю потока у* , которая

должна пройти по маршруту 7t*'r.

Причем должны выполняться следующие условия:

Г=1 г~ 1

Необходимо отметить, что значение xstjr должно быть скорректировано таким образом, чтобы избежать распределения по нескольким маршрутам трафика отдельного TCP-соединения.

Через каждую линию (k,l) может проходить множество допустимых маршрутов, суммарный трафик которых не превышает пропускную способность линии. Поток трафика класса сервиса s пары узлов

<j-., который должен пройти через линию (k J) е пУ, обозначим X'jru.

Общий поток трафика класса сервиса s, который должен пройти через линию (k,l):

г = 1,2,..., Щ, , а, =1,2,..., /;,

где ¡1, - множество пар , у которых поток проходит через линию (к,1),

П^ - множество всех допустимых маршрутов л*/, в которые входит линия (к,1) .

г - индекс маршрута в множестве Щ .

Для систем массового обслуживания с относительными приоритетами (модель М/М/1/оо ) известна формула для определения задержки в линии, которая в результате преобразований принимает вид:

Т = £

I

1 «=i

-+

II

(5)

где g - порядковый номер класса сервиса во множестве всех классов сервиса.

Эта формула используется для определения значения задержки для трафика класса сервиса i на допустимом маршруте ns-jr .

Определять значение задержки по формуле (5) необходимо для каждого вновь введенного потока на множестве всех допустимых маршрутов Щ ■ При распределении новых потоков следует соблюдать

условие фг -> min. Причем для трафика самого приоритетного

->тах

i—1

класса (5 = 1) значение Ru = О.

Варьируя значениями доли потоков выражения (5) необходимо добиться того, чтобы наибольшая задержка для всех маршрутов между двумя заданными узлами стремилась к минимуму, но при этом она не должна превышать максимально допустимую задержку для данного вида трафика t^.

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

значения фг, расставляются приоритеты маршрутов на всем наборе

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

метрики. Далее поток с самым высоким С^оБ направляется по маршруту с номером приоритета 1.

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

После этого значение ¡'У необходимо рассчитать по формуле (5),

где я - класс следующего по приоритетности трафика.

Для вычисления задержки на всех остальных маршрутах, по которым распределяется поток единственного класса обслуживания, используется формула (6):

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

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

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

Программа состоит из семи основных этапов, пять из которых («Исходный графа», «Ранг и нумерация вершин», «Направление», «Устранение тупиковых маршрутов», «Проверка связности») предназначены для построения минимального направленного графа с провер-

(6)

кой на связность, а оставшиеся («Маршруты» и «Расчет задержек в линиях») - для вывода полученных результатов.

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

Следующим этапом является распределение заданного трафика по полученным маршрутам. Вычисление значения производится для всех возможных маршрутов. После чего делается выбор пути прохождения для всех заданных видов трафика по мере уменьшения их С^оБ. Результат этого отражается в программе в разделах «Распределение трафика» и «Маршруты, задержки».

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

Четвертая глава содержит описание системы анализа алгоритма, а также результаты исследований.

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

числу ветвей в минимальных направленных графах Е .

ОЛ. (7)

Е

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

Исследовался диапазон количества узлов сети от 3 до 40. При этом эксперименте диапазон разбивался на несколько поддиапазонов с целью уменьшения затрат процессорного времени при выполнении расчетов в программе. Такое разбиение возможно благодаря тому, что

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

После сведения данных, полученных на всех этапах, в одну систему координат, получили зависимость, представленную на рис. 3

Еу

Как видно из рис. 3 зависимость -=- носит линейный характер с

Е

коэффициентом пропорциональности 1,04, т. е. £О) = 2,6+1,04-(у-5), где V - число узлов. Такая закономерность

справедлива для V > 5 .

Еу

Наименьшее значение отношения -==- наблюдается при значении

£

узлов, равное 4. Для диапазона узлов от 3 до 8 характер прямой будет несколько отличаться.

Максимальное отклонение от линейной зависимости составляет 18,2%.

Полученные результаты позволяют делать прогнозы при дальнейшем изменении числа узлов.

ЗАКЛЮЧЕНИЕ

В целом по итогам работы сформулированы следующие основные полученные результаты:

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

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

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

4. Результаты компьютерного эксперимента показали, что изменение критерия эффективности процесса поиска маршрута по разработанному алгоритму носит линейный характер с коэффициентом пропорциональности 1,04, для числа узлов более 4. Причем отклонение результатов эксперимента от линейности составляет не более 18,2%.

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

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

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Никулин, С. С. Средства сбора и анализа трафика. Преимущества использования продукта с открытым исходным кодом / С. С. Никулин, И. С. Поздняк // Тез. докл. XIII юбилейной российской научной конференции. -ПГАТИ, Самара, 2006. - С.41-42.

2. Поздняк, И. С. Методы маршрутизации в сетях NGN / И. С. Поздняк // Докл. VII Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций». - Самара, 2006 г. - С.148-149.

3. Поздняк, И. С. Формирование множества допустимых маршрутов с использованием алгоритма адаптивной маршрутизации / И. С. Поздняк // Тез. докл. XIV российской научной конференции ПГАТИ. - Самара, 2007. - С.61.

4. Лихтциндер, Б. Я. Применение алгоритма минимального направленного графа при адаптивной маршрутизации в мультисервисных сетях I Б. Я. Лихтциндер, И. С. Поздняк // Докл. XIII Международной научно-технической конференции «Радиолокация. Навигация. Связь». - Воронеж, 2007 г. - С.910-916.

5. Лихтциндер, Б. Я. Резервирующий алгоритм построения минимального направленного графа при адаптивной маршрутизации / Б. Я. Лихтциндер, И. С. Поздняк // Инфокоммуникационные технологии. - 2007. - Том №5, №2. -С.42-46.

г

6. Поздняк, И. С. Резервирующие алгоритмы адаптивной маршрутизации / И. С. Поздняк // Тез. докл. XII Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и в образовании». - Рязань, 2007 г. - С. 146-147.

7. Лихтциндер, Б. Я. Система автоматизированного расчета сетей ATM / Б. Я. Лихтциндер, И. С. Поздняк // Докл. конференции «Инновационные технологии в управлении, образовании, промышленности «АСТИНТЕХ-2007». -Астрахань, 2007 г. - С. 124-126.

8. Лихтциндер, Б. Я. Распределение потока по множеству допустимых маршрутов / Б. Я. Лихтциндер, И. С. Поздняк // Докл. Пятой Всероссийской научно-технической конференции «Современные проблемы создания и эксплуатации радиотехнических систем». - Ульяновск, 2007 г. - С.161-164.

9. Лихтциндер, Б. Я. Распределение голосового абонентского трафика в мультисервисных сетях / Б. Я. Лихтциндер, И. С. Поздняк // Тез. докл. III Международной научно-технической конференции СПРТП-2007.- Винница,2007г.

10. Лихтциндер, Б. Я. Вероятностные оценки уровня подготовки специалистов / Б. Я. Лихтциндер, В. В. Пугин, И. С. Поздняк // Докл. VII Международной конференции «Интерактивные системы: проблемы человеко-компьютерного взаимодействия». - Ульяновск, 2007 г. - С. 212-214.

11. Лихтциндер, Б. Я. Управление трафиком по резервирующему алгоритму / Б. Я. Лихтциндер, И. С. Поздняк // Докл. Международной научно-практической конференции ТЕЛЕКОМ-2007. - Ростов-на-Дону, 2007 г. - С. 9195.

12. Поздняк, И. С. Распределение потоков трафика в мультисервисных сетях / Тез. докл. XV российской научной конференции ПГАТИ. - Самара, 2008.

13. Лихтциндер, Б. Я. Уровни формирования допустимых маршрутов и распределения потоков в решении задачи маршрутизации / Б. Я. Лихтциндер, И. С. Поздняк // Докл. 63-й научной сессии, посвященной Дню радио. - Москва, 2008 г.-С. 201-204

14. Свидетельство о государственной регистрации программы для ЭВМ. Маршрутизация с учетом приоритетов маршрутов / И. С. Поздняк, Б. Я. Лихтциндер. - № 2008614656 от 26.09.2008. - 1 с.

15. Поздняк, И. С. Программная реализация «Маршрутизация с учетом приоритетов маршрутов I И. С. Поздняк // Тез. докл. XVI российской научной конференции ПГУТИ. - Самара, 2009. - С. 59.

16. Поздняк, И. С. Анализ эффективности работы резервирующего алгоритма / И. С. Поздняк, Т. П. Яшмолкина // Тез. докл. XVI российской научной конференции ПГУТИ. - Самара, 2009. - С. 60.

Подписано в печать 16.04.09г. Формат 60х841/1б Бумага писчая№1 Гарнитура Тайме Заказ 367. Печать оперативная .

_Усл. печ. л.0.94. Уч. изд. л.0.89. Тираж ЮОэкз_

Отпечатано в издательстве учебной и научной литературы Поволжского государственного университета телекоммуникаций и информатики 443090, г. Самара, Московское шоссе 77. т. (846) 228-00-44

-С. 66-67.

Глава 1 МЕТОДЫ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ.

1.1 Основные положения

1.2 Классификация алгоритмов маршрутизации.

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

1.4 Маршрутизация в мультисервисных сетях.

1.5 Протоколы маршрутизации мультисервисных сетей.

1.5.1 Протокол OSPF.

1.5.2 Протокол IS-IS.

1.5.3 Протокол BGP.

1.6 Выводы.

Глава 2 РАЗРАБОТКА МЕТОДА АДАПТИВНОЙ МАРШРУТИЗАЦИИ.

2.1 Управление трафиком.

2.2 Постановка задачи маршрутизации.

2.3 Уровень резервирования пропускной способности.

2.4 Уровень формирования допустимых маршрутов.

2.5 Уровень распределения потоков.

2.6 Статистические характеристики трафика.

2.7 Разработка алгоритма. Создание набора допустимых маршрутов.

2.8 Процедура устранения «тупиковых» маршрутов.

2.9 Алгоритм проверки связности графа.

2.10 Распределение трафика.

2.11 Распределение потоков с учетом приоритетов маршрутов.

2.12 Распределение трафика с учетом приоритетов направлений.

2.13 Особенности применения резервирующего алгоритма.

2.14 Выводы.

Глава 3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МАРШРУТИЗАЦИИ С

УЧЕТОМ ПРИОРИТЕТОВ МАРШРУТОВ.

3.1 Обоснование выбора среды разработки.

3.1.1 Особенности среды разработки Delphi 7.

3.1.2 Особенности объектно - ориентированного программирования в языке Object Pascal.

3.2 Использование объектно-ориентированного программирования в программной реализации.

3.3 Работа с интерфейсом программы.

3.4 Выводы.

Глава 4 АНАЛИЗ ЭФФЕКТИВНОСТИ РАЗРАБОТАННОГО АДАПТИВНОГО МЕТОДА МАРШРУТИЗАЦИИ.

4.1 Методы оценки эффективности.

4.2 Моделирование системы анализа.

4.3 Анализ результатов.

4.4. Выводы.

Актуальность темы

Характерной тенденцией современного этапа развития компьютерных сетей является принципиальное изменение структуры передаваемого трафика. Анализ статистики агрегированного трафика большинства сетей доступа в Интернет явно показывает высокую долю в нем аудио- и видео-потоков данных. Можно определенно утверждать, что трафик сетей доступа в Интернет, а также сетей крупных предприятий, стал мультимедийным. При этом постоянно разрабатываются и внедряются новые алгоритмы, протоколы и технологии, которые в определенной степени улучшают качество передачи трафика реального времени в IP-сетях. Следствием этого является существенное усложнение архитектуры сетей TCP/IP, которые теперь характеризуются не просто как сети передачи данных, а как мультисервисные.

Между тем, каналы передачи данных, подходящие для предоставления одной услуги, не всегда подходят для предоставления другой. Увеличение объемов предоставляемых услуг заставляет операторов и провайдеров параллельно развивать несколько различных сетей. Это требует больших затрат и часто сопряжено со значительными техническими трудностями.

Маршрутизация на сегодняшний день определяется не формальными правилами и описаниями, характерными для сетей предыдущих поколений, а требованиями клиента и экономическими соображениями оператора связи. Чтобы оптимизировать работу сетей, разрабатываются различные методы маршрутизации, обеспечивающие сбалансированную нагрузку всех сетевых ресурсов. Среди зарубежных ученых, изучающих данную проблему, стоит особо выделить D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus, S. Hiroyuki, M. Yasuhiro, Y. Makiko и др.

Чтобы успешно передать по сети потоки информации самого различного рода необходимо, чтобы алгоритм маршрутизации учитывал требования, предъявляемые данными потоками к уровню качества обслуживания (Quality of Service, QoS). Для этого весь трафик подразделяют на классы сервиса. И тогда маршрутизация по всей сети будет осуществляться в соответствии с классом сервиса каждого отдельного потока. В России вопросами маршрутизации и смежными с ними проблемами занимаются Б.С. Гольдштейн, В. М. Вишневский, Ю.А.Семенов, В. Н. Тарасов, А. В. Росляков и др.

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

Объектом исследования являются сети с пакетной коммутацией (муль-тисервисные сети).

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

Цель работы и задачи исследования

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

Для достижения поставленной цели необходимо провести анализ существующих методов маршрутизации и решить следующие задачи:

- разработать алгоритм определения набора допустимых оптимальных маршрутов;

- разработать способ распределения потоков трафика по набору допустимых маршрутов;

- создать объектно-ориентированную модель работы предложенного алгоритма;

- выполнить программную реализацию разработанного алгоритма;

- провести компьютерное моделирование процесса маршрутизации сети с использованием разработанного алгоритма.

Методы исследования

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

Достоверность результатов

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

Научная новизна результатов.

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

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

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

Практическая ценность и реализация результатов работы

Основные теоретические и практические результаты, полученные в диссертационной работе, переданы для эксплуатации в Центр информационных технологий Оренбургского государственного университета и в ОАО «Инфосфера», а также использованы в учебном процессе ПГУТИ.

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на VII Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2006), XIII Международной НТК «Радиолокация. Навигация. Связь» (Воронеж, 2007), XII Всероссийской НТК «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, 2007), Пятой Всероссийской НТК «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2007), III Международной НТК (Винница, 2007), Международной НТК TEJIEKOM-2007 (Ростов-на-Дону, 2007), 63-й научной сессии, посвященной Дню радио (Москва, 2008), российских НТК профессорско-преподавательского состава ПГАТИ (Самара, 2006 - 2009).

Публикации

По теме диссертации опубликовано 16 работ, в том числе 1 статья в журнале, входящем в перечень ВАК РФ, 14 тезисов и текстов докладов.

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

1. Формализованная в терминах теории графов задача построения минимального направленного графа.

2. Графовая модель набора допустимых маршрутов между узлами мультисервисной сети.

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

4. Способы распределения потоков трафика по набору допустимых маршрутов.

5. Комплекс программных средств, реализующих предложенный алгоритм.

6. Результаты моделирования маршрутизации, с использованием предложенного алгоритма.

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав, списка литературы. Работа содержит 130 страниц машинописного текста, 38 рисунков и 3 таблицы. Список литературы включает в себя 70 наименований.

4.4. Выводы

Анализ показал, что в качестве критерия оценки эффективности следует выбрать отношение м или

Е

V 2; ср \ ср

Разработанное программное обеспечение «Маршрутизация с учетом приоритетов маршрутов» обеспечивает моделирование с возможностью дальнейшего исследования сетей.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

В целом, сформулированы следующие основные полученные результаты:

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

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

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

- С использованием разработанного пакета программ проведены компьютерные эксперименты, показавшие эффективность предложенного алгоритма.

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

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

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

1. CISCO Internetworking Technology Overview Электронный ресурс. / В. Плешаков Режим доступа: http://www.ods.com.ua/win/rus/net-tech/ciscoito/. -06.09.2006

2. Вишневский, В. М. Теоретические основы построения компьютерных сетей / В. М. Вишневский. Москва: Техносфера, 2003. - 512 с

3. Таненбаум, Э. Компьютерные сети / Э. Таненбаум; пер. с англ. под ред. В. Шграга. 4-издание. - Спб.: Питер, 2006. - 992 с.

4. Поздняк, И. С. Методы маршрутизации в сетях NGN / И. С. Поздняк // VII Междунар. науч.-техн. конф. «Проблемы техники и технологии телекоммуникаций»: труды конференции. — Самара, 2006. с. 148-149.

5. Олифер Н. Протоколы маршрутизации Электронный документ. / Н. Олифер // Журнал сетевых решений LAN. 2001. - № 09. - Режим доступа: http://www.osp.ru/lan72001/09/024.htm. - 22.11.2006

6. Столингс, В. Современные компьютерные сети // В. Столингс; пер. с англ. А. Леонтьева. 2-издание. - Спб.: Питер, 2003. - 783 с.7. http://proffy.info/inet/35.htm

7. Савельев, А. Современные протоколы маршрутизации Электронный документ. / Журнал сетевых решений LAN. — 1998. — №12. — Режим доступа: http.V/www.unix.org.ua/routing/1/- 15.11.20069. http ://rk6 .bmstu.ru/electronicbook/net/net02/routing.htm

8. Солдатова, В. А. Динамический алгоритм маршрутизации на основе агентных технологий Электронный документ. / В.А. Солдатова. Режим доступа: http.V/www.masters.donntu.edu.ua/2005/fVti/soldatova/library/soldatova.htm. -22.04.2008.

9. Моу, J. RFC2328. OSPF Version 2, April 1998 Электронный документ. / J.Moy. Режим доступа: http://rfc.net/rfc2328.html. - 06.09.2006.

10. Штовба, С. Д. Муравьиные алгоритмы / С. Д. Штовба // Exponenta Pro. Математика в приложениях. — 2003.- №4.- С. 70-75.

11. Subramanian, D.Ants and reinforcement learning: A case study in routing in dynamic networks Электронный документ. / D. Subramanian, P. Druschel, J. Chen. -Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=l0.1.1.52.2400. -20.04.2008.

12. Thompson, Jonathan. Ant Colony Optimization Электронный документ. / Jonathan Thompson. — Режим доступа: http://orsoc.org.uk/region/regional/swords/swords.ppt

13. Головин, С. Технологии мультисервисных сетей / С. Головин // СЮ. 2005. -№10. -С. 27-32

14. Rekhter, Y. RFC 1771. A Border Gateway Protocol 4 (BGP-4). March, 1995 Электронный документ. / Y. Rekhter, T. J. Watson, T. Li. Режим доступа: http://rfc.neiyrfcl771.html. - 02.10.2006.

15. Гольдштейн, А. Б. Технология и протоколы MPLS / А. Б. Гольдштейн, Б. С. Гольдштейн. СПб.: БХВ - Санкт-Петербург, 2005. - 304 с.

16. Awduche, D. RFC2702. Requirements for traffic engineering over MPLS. September, 1999 Электронный документ. / D.Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus. Режим доступа: http://rfc.net/rfc2702.html. - 16.03.2007.

17. Хелеби, Сэм. Принципы маршрутизации в Internet // Сэм Хелеби, Денни Мак-Ферсон; пер. с англ. В. В. Ткаченко. — 2-е издание. — М.: Издательский дом "Вильяме", 2001.- 448 с.

18. Семенов, Ю.А. Telecommunication technologies телекоммуникационные технологии (v3.1, 19 марта 2008 года) Электронный ресурс. / Ю.А. Семенов. -Электрон, дан. - Режим доступа: http://book.itep.ru/4/44/rut441 l.htm, свободный. — Загл. с экрана.

19. Pu, J. Reliable Routing in MPLS Networks Электронный документ. / J. Pu, E. Manning, and G.C. Shoja (Canada). — Режим доступа:http ://www. actapres s. com/Abstract.aspx?paperId=24278

20. Глоссарий.Ру: Маршрутизация Электронный документ. /. Режим доступа: http://www.glossary.rU/cgi-bin/glsch2.cgi7RMgw@wzyong.o9

21. Орлов, Сергей. Перекресток миров Электронный документ. / Журнал сетевых решений LAN. 2004. - №5. - Режим доступа:http://www.osp.ni/lan/2004/05/139060/.-2.02.200724. http ://www. ietf.org/html. charters/mpls-charter.html

22. Олифер, В. Г. Компьютерные сети Принципы, технологии, протоколы. Учебник для вузов. 3-е изд. / В. Г. Олифер, Н. А. Олифер. Спб.: Питер, 2006 - 958 с.

23. Тимофеев, А. В. Модели и методы маршрутизации потоков данных в телекоммуникационных системах с изменяющейся динамикой / А.В. Тимофеев, Сырцев А.В. М.: Новые технологии, 2005. — 32 с. — (Прил. к журн. "Информационные Технологии" N 8/2005).

24. Ермолаев, С. Ю. Муравьиные алгоритмы оптимизации / С. Ю. Ермолаев // Инфокоммуникационные технологии. 2008. -Т. 6, №1. — С.23 - 29.

25. Кормен, Томас. Алгоритмы: построение и анализ / Томас Кормен, Чарльз

26. Лейзерсон, Рональд Ривест. М.: Издательский дом "Вильяме", 2006. - 1296 с.

27. Амато, Вито. Основы организации сетей Cisco, том 2., испр. изд. / Вито Амато; пер. с англ. А.Н. Крикун. — М.: Издательский дом "Вильяме", 2004. - 464 с.

28. Hiroyuki, S. Traffic Engineering using Multiple Multipoint-to-Point LSPs Электронный документ. / S. Hiroyuki, M. Yasuhiro, Makiko Y. Режим доступа: http://www.ieee-infocom.org/2000/papers/533.pdf. - 3.12.2007.

29. Лихтциндер, Б. Я. Инжиниринг трафика в мультисервисных сетях / Б. Я. Лихтциндер, П. М. Попов // Электросвязь. 2005. - № 7. - С. 22-26.

30. Ильин, В. Э. Линейная алгебра / В. Э. Ильин, Э. Г. Позняк. М.: Наука-Физматлит. - 1999. - 280 с.

31. Лихтциндер, Б. Я. Автоматизация расчета характеристик трафика ATM / Б. Я. Лихтциндер // Инфокоммуникационные технологии. 2003. - Т. 1, № 1, С. 47-53.

32. Харрари, Ф. Теория графов / Ф. Харрари. М.: Мир, 1973. - 300 с.

33. Diestel, R. Graph Theory / R. Diestel. Springer-Verlag, New York, 2005. - 322 p.

34. Татт, У. Теория графов / У. Татт. М.: Мир, 1998. - 424 с.

35. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. М.: Мир, 1981.-324 с.

36. Зыков А. Основы теории графов / А. Зыков. — М.: Наука Гл. рад. физ.-мат. наук. 1987.-384 с.

37. Нахождение к кратчайших путей в графе Электронный документ. Режим доступа: http://algolist.manual.ru/maths/graphs/shortpath/yen.php - 5.03.2008.

38. Лихтциндер, Б.Я. Техника инжиниринга трафика в мультисервисных и многоприоритетных сетях / Б. Я. Лихтциндер, П. М. Попов // Инфокоммуникационные технологии. 2004. — Т. 2, №.3. — С. 48-56.

39. Лихтциндер, Б. Я. Резервирующий алгоритм построения минимального направленного графа при адаптивной маршрутизации / Б. Я. Лихтциндер, И. С. Поздняк // Инфокоммуникационные технологии. — 2007. — Т. 5, №2. С. 42-46.

40. Клейнрок, Л. Вычислительные системы с очередями. Том 2 / Л. Клейнрок; пер. с англ. под ред. Б. С. Цыбакова. М.: Мир. - 1979. — 599 с.

41. Internetworking Technology Overview Электронный документ. Режим доступа: http://athena.wsu.ru/docs/nettech/itocisco/.— 15.04.2008.

42. Нетес, В.А. Качество обслуживания на сетях связи. Обзор рекомендаций МСЭ Электронный документ. / В.А. Нетес // Сети и системы связи. — 1999. — № 3. — Режим доступа: http://www.ccc.ru/magazine/depot/9903/read.html70301.htm. — 12.11.2007.

43. Пашеку, Хавьер. Программирование в Borland Delphi 2006 для профессионалов / Хавьер Пашеку. — М.: Издательский дом "Вильяме", 2006. 944 с.

44. Елманова, Наталья. Delphi 7: первый взгляд Электронный документ. / Наталья Елманова. Режим доступа: http://www.compress.ru/article.aspx?id=12048&iid=466. - 24.04.2008.

45. Чужа, Виталий. Borland Delphi 7 миграция в сторону .Net Электронный документ. / Виталий Чужа. — Режим доступа:http://www.realcoding.net/article/view/243. 11.04.2008.

46. Элиенс, Антон. Принципы объектно-ориентированной разработки программ. 2-е издание / Антон Элиенс. — М.: Издательский дом "Вильяме", 2002. 496 с.

47. Нефедова, В. Ю. Преимущества объектно-ориентированного программирования по сравнению с процедурными языками. ИТО-2005 Электронный документ. / В. Ю. Нефедова. Режим доступа: http://ito.edu.ru/2005/MoscowA/2A-2-5440.html. -5.05.2008.

48. Tutte, W. T. Graph Theory / W. T. Tutte. Addison-Wesly, 1984. - 424 p.

49. Нечепуренко M. И. Алгоритмы и программы решения задач на графах и сетях / М. И. Нечепуренко, В. К. Попков, С. М. Майнагашев и др. Новосибирск: Наука, 1990.-515 с.

50. Нуштаев, А. В. Исследование и разработка графовых моделей отказоустойчивых виртуальных частных сетей: дис. . канд. техн. наук / А. В. Нуштаев ПГАТИ, 2007. - 143 с.

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

52. Балк, В. М. Первое знакомство с сетями Петри. Часть 1. Необходимые сведения о теории графов Электронный документ. / В. М. Балк. Режим доступа: http://www.smolensk.rU/user/sgma/MMORPH/N-2-html/8.HTM. - 15.10.2008.

53. Иванов, А.Г. Объектно-ориентированный подход технологии программирования Электронный документ. / А.Г. Иванов, А.А.Пятницкий, Ю.Е.Филинов. Режим доступа: http://www.math.sfedu.ru/smalltalk/article91.ru.html. - 19.07.2008.

54. Семенов, Ю.А. Элементы теории графов Электронный документ. / Ю.А. Семенов. Режим доступа: http://book.itep.ru/10/grap 102l.htm. - 22.08.2008.70. http://olddesign.isu.ru/~slava/do/disc/frgraph.htm.