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

003484ааI

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

ПЕРЕПЕЛКИН Дмитрий Александрович

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

Специальность 05.13.13. «Телекоммуникационные системы

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

АВТОРЕФЕРАТ

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

I Ь 1"(1/)1

кандидата технических наук

Рязань 2009

003484991

Работа выполнена на кафедре систем автоматизированного проектирования вычислительных средств ГОУВПО "Рязанский государственный радиотехнический университет".

Научный руководитель: доктор технических наук, профессор

Шибанов Александр Петрович

Официальные оппоненты: доктор технических наук, профессор

Локтюхин Виктор Николаевич

кандидат технических наук Грицъ Валерий Матвеевич

Ведущая организация: Государственный научно-исследовательский

институт информационных технологий и телекоммуникаций (ГНИИ ИТТ) «Информика», г. Москва

Защита состоится 16 декабря 2009 г. в 12 часов на заседании диссертационного совета Д 212.211.02 в ГОУВПО "Рязанский государственный радиотехнический университет" по адресу: 390005, г. Рязань, ул. Гагарина, 59/1.

С диссертацией можно ознакомиться в библиотеке ГОУВПО "РГРТУ". Автореферат разослан « /<?» ноября 2009 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 390005, г. Рязань, ул. Гагарина, 59/1, Рязанский государственный радиотехнический университет.

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

диссертационного совета /

канд. техн. наук, доцент /^^/¿//¿у ^ Телков И.А.

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

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

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

Проблемами совершенствования методов и алгоритмов маршрутизации в вычислительных сетях занимались такие ученые, как Д. Бертсекас, Д. Гарсиа-Диас, П. Гупта, А.Б. Гольдштейн, B.C. Гольдштейн, Д. Кантор, О .Я. Кравец, Д.В. Куракин, И.П. Норенков, А. Филипс, С. Флойд и другие. Задачу нахождения кратчайших путей в транспортной системе рассматривали в своих трудах ученые JI. Беллман, Г. Габов, С. Гудман, Е. Дейкстра, В.А.Евстигнеев, В.Н. Касьянов, Р. Сэджвик, Р. Тарьян, С. Флойд, Р. Форд, Д. Фулкерсон. Подробное описание методов поиска кратчайших путей можно найти в работах Т. Кормена, Ч. Лейзерсона и Р. Ривеста.

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

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

На основании всего сказанного можно сделать вывод об актуальности выбранной темы диссертационной работы.

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

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

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

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

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

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

5) разработать адаптивный алгоритм поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах;

6) разработать адаптивный алгоритм поиска оптимальных маршрутов с учетом частичных изменений структуры сегги на основе информации о возможных перестановках маршрутов;

7) разработать методики применения алгоритмов поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах для протоколов ОБРЕ и ГСЛР.

Методы исследования. Разработка и исследование проводились на основе теории графов, теории алгоритмов, теории матриц, а также компьютерного моделирования.

Научная новизна диссертационной работы заключается в том, что впервые разработаны методы и алгоритмы адаптивной маршрутизации при условии частичного изменения структуры корпоративной вычислительной сети, которые позволяют получить меньшую трудоемкость \_0(Ы), где N - число узлов в сети] построения таблиц маршрутизации по сравнению с известными алгоритмами.

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

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

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

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

2) поиск кратчайших путей на графе с использованием алгоритма адаптивной маршрутизации и алгоритма парных перестановок маршрутов;

3) проведение экспериментов по изменению весов ребер графа, по добавлению и удалению вершин и ребер графа с построением дерева кратчайших путей;

4) оценка трудоемкости разработанных алгоритмов.

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

Апробация результатов диссертации. Основные результаты диссертационной работы докладывались на следующих конференциях:

• XII всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании», НИТ-2007. 19 - 21 апреля 2007 г., г. Рязань;

• всероссийской научно-технической конференции «Информационные и телекоммуникационные технологии. Подготовка специалистов для инфоком-муникационной среды» 21 - 23 апреля 2009 г., г. Рязань.

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

Внедрение результатов работы. Результаты работы внедрены в телекоммуникационной компании «Энлинк Трэйд», г. Рязань, где используются в составе комплекса диагностики и управления состоянием сети «ЫАОТ2», а также внедрены в учебный процесс ГОУВПО "Рязанский государственный радиотехнический университет".

Структура и объем диссертаций. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, приложения, изложенных на 140 с. Список использованной литературы содержит 105 наименований. Текст диссертации содержит 19 таблиц и 30 рисунков.

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

4. Алгоритм поиска оптимальных маршрутов с учетом частичных изменений структуры корпоративной сети на основе дополнительной информации о возможных парных переходах, который позволяет получить меньшую трудоемкость поиска оптимальных маршрутов \0(Ы), где N - число узлов в сети], по сравнению с известными алгоритмами поиска.

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

парных перестановках, имеющий меньшую трудоемкость поиска оптимальных маршрутов [0(N'), где N - число узлов в сети], по сравнению с известными алгоритмами поиска.

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

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

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

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

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

Приведено описание известных протоколов маршрутизации в корпоративных вычислительных сетях, таких как OSPF, RIP, IGRP, EIGRP, EGP, BGP, NLSP, IS-IS.

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

строения таблиц маршрутизации до величины порядка О (И), где N - число узлов в сети.

На основе проведенного анализа сформулированы цель и задачи диссертационной работы.

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

Вычислительная сеть представлена в виде неориентированного взвешенного связного графа 0=(У,Е, Ш), где V- множество вершин, ||Р|| = Ы, Е- множество ребер, ||£|| = М, IV - множество весов ребер. Пусть на графе С в некоторый момент времени уже решена задача поиска кратчайших путей до всех вершин множества из начальной вершины т. е. построено дерево кратчайших

путей с корнем в вершине V,. На рис. 1 жирными линиями обозначено построенное дерево кратчайших путей.

Обозначим это дерево как Рассмотрим множество ребер Е графа С. По признаку вхождения ребер в дерево Тг можно разделить исходное множество Е на два подмножества: Е, еТе н Ег0Те Е,иЕг=Е.

Множество ребер дерева Ет- множество ребер дерева 'Гг для графа С. Для заданного графа й, согласно свойству дерева, мощность множества Ет будет равняться мощности множества V минус единица ||£г||=||^|-7.

Множество ребер замены для дерева £д- множество ребер графа С, не вошедших в дерево При соответствующих условиях некоторое ребро е^еЕц, инцидентное вершинам V, и V/, может перейти во множество ребер дерева Ет, заменив собой некоторое ребро е^еЕт- При этом инцидентность ребра вершине у, или Vj является обязательным условием. В свою очередь,- ребро еу перейдет во множество

Будем называть такие переходы парными переходами и обозначать е^—

ек,Р■

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

Теорема 1. Для любого ребра е^еЕт, инцидентного некоторым вершинам V, и V,-, маршрутные степени которых больше единицы, при заданной конфигурации графа, неизменных весах других ребер существует такое значение веса что при и>у> и>у' ребро еу становится ребром замены и переходит во множество Ец

Величину мц будем называть точкой вхождения в дерево для ребра еу.

Отношение парного перехода г,- - отношение соответствия элемента еу множества Ет элементу вк,Р множества Ец такое, что при увеличении веса ребра еу так, что >Су> щ], имеет место парный переход е,гекр.

Теорема 2. Для любого ребра находящегося в отношении парного

перехода с некоторым ребром е^еЕт с заданной точкой вхождения в дерево существует такое значение веса что при ^кр< \1>кр' ребро екр становится веткой дерева Тн и переходит во множество Ет-

Теорема 3. Для элементов парного отношения г, ечеЕ, и екр еЕг при известной точке вхождения в дерево и и'к,р справедливо, что н'у'-ц;у= н^-

Следствие 1. Если для элементов парного отношения г„ е^еЕт и екр еЕр, соответствующих весов Wy и при известной точке вхождения в дерево измешшся вес ребра еу до значения то ^кр = у/^+^гМ^-

Следствие 2. Если для элементов парного отношения г,, еиеЕт и екр еЕц, соответствующих весов му и при известной точке вхождения в дерево изменился вес ребра екф до значения \а2, то IV,/=

Теорема 4. Ребра еиеЕт и екр еЕк, находящиеся в одном отношении с г, еЯ, инцидентны одной и той же вершине V/ при условии, что V, является листом дерева кратчайших путей.

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

Множество непарных ребер ЕР - это такое подмножество множества ЕК, элементы-ребра которого не участвуют ни в одном отношении из множества Л.

В общем случае множество ЕР может быть пустым \\ЕР\\~-0. Множество Е5 будет пустым только при условии, что исходный связный граф С является деревом и задача поиска кратчайших путей в этом случае лишена смысла.

Теорема 5. Для любого ребра еу инцидентного некоторым вершинам V! и V), маршрутные степени которых больше двух, при заданной конфигурации графа, неизменных весах других ребер существует такое значение веса что при м>у> и',/ ребро еу становится непарным ребром и переходит во множество Ер

Величину м>к,р будем называть точкой вхождения во множество замены для ребра еКр.

Теорема 6. Для любого ребра е^ еЕ$, инцидентного некоторым вершинам V/ и маршрутные степени которых больше двух, при заданной конфигурации графа, неизменных весах других ребер существуют такое ребро е£> и такое значение его веса что при Мк.р^кр ребро екр становится ребром замены и переходит во множество

Теорема 7. При добавлении нового ребра ец инцидентного вершинам г и причем / лежит выше чем j по дереву иерархии, с весом то без изменения окажутся кратчайшие пути и их оценки дня вершин множества У^'К

Следствие. При добавлении нового ребра еи инцидентного вершинам / и у с весом м/ц при не изменении оценок 4 и ^ дерево не изменится. Если изменяется оценка какой-либо вершины V/ или Уу, то необходимо определить новые кратчайшие пути для множества вершин, не принадлежащих множеству У^К

На рис. 2 жирными линиями обозначено дерево кратчайших путей, которое не требует изменения при добавлении нового ребра Е^.

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

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

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

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

Следствие 1. При добавлении некоторой вершины Ук, имеющей ребро с вершиной К/ и V), если < 4> то дерево кратчайших путей до вершины У/ не изменится.

Следствие 2. При добавлении некоторой вершины Ук, имеющей ребро с вершиной VI и если аГ/ < 4> то необходимо определить новые кратчайшие пути для множества вершин, инцидентных вершине Ук.

На рис. 4 жирными линиями обозначено дерево кратчайших путей, которое не требует изменения при добавлении вершины Уд.

Теорема 10. При удалении некоторого ребра инцидентного вершинам V,- и У}, входящего в дерево кратчайших путей, причем 4 < дерево кратчайших путей и их оценки до вершины V/ окажутся без изменения.....

Следствие. При удалении некоторого ребра еф инцидентного вершинам Г/ и У), входящего в дерево кратчайших путей, причем <1, < необходимо определить новые кратчайшие пути для множества вершин, инцидентных вершине К;.

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

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

Обозначим тсу -вес ребра, соединяющего вершины ц и V/, т/ц - новое значение веса, полученное в результате изменения значения метрики линии связи. Вершина Vу располагается ниже по иерархии дерева кратчайших путей относительно у,. Обозначим Ет множество ребер, каждый элемент которого входит, по крайней мере, в один кратчайший путь из начальной вершины, Ек -множество остальных ребер. ЕяиЕт=Е, Екп Ег=0. Обозначим Ут - множество вершин, до которых найден кратчайший путь из начальной вершины, Уя - множество остальных вершин. Уки Ут-У, Укп Ут=0.

Будем называть {^-путем Як совокупность подмножества V т ¿У вершин, через которые проходит кратчайший путь до вершины V* из исходной вершины уя и подмножества ^ребер, составляющих этот путь.

Назовем К*-деревом Тк совокупность подмножества У/1^ сУ, состоящего из всех вершин, кратчайшие пути до которых из исходной вершины содержат вершину у*, и подмножества Ет^'сЕ ребер, составляющих эти пути после V* при движении от вершины

Обозначим множество путей до вершины V, из исходной вершины V, через Д, где элемент множества ж1к еТТ, будет множеством неповторяющихся ребер е^еЕ, образующих вместе путь, соединяющий ^ и V/. Для всех щеЦ поставим в соответствие некоторое число, равное сумме весов входящих в него ребер, т.е. длину пути сйдв'А. На множестве Д задан селектор Н, возвращающий кратчайший путь из множества Ц. В том случае, если существует нескольких путей в Д с минимальной длиной, то выбирается один из них. Кратчайший путь до вершины V/ будем обозначать л,=Н(Щ, оценку длины щ - ¿¡.

Теорема 11. Если и е^еЕт, то изменению могут подвергнуться

кратчайшие пути и оценки их длин для вершин У^К

Теорема 12. Если пу/ц^ц и еуе£г, то без изменения останутся кратчайшие пути для вершин множества уеК/1® и У а для вершин множества неизменными останутся и оценки длин кратчайших путей.

Теорема 13. Если гтц>м»ц и Ет, то исходное дерево кратчайших путей и оценки длин путей всех вершин не изменятся.

Теорема 14. Если пмг^ч/ц и е^ё Ет, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества У^'К

Теорема 15. Если е^еЕт и /ту> ту,] (точки вхождения в дере-

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

и

вершин V^ и новые кратчайшие пути к этим вершинам будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.

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

Теорема 16. Если mv,j<Wjj, e,j0 Ет, и новое значение mvij< Шц (точки вхождения в дерево), то новые кратчайшие пути к вершинам множества v eV-p® uV^ будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.

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

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

В третьей главе «Применение разработанных адаптивных алгоритмов маршрутизации в корпоративных вычислительных сетях» предложены методики применения разработанных адаптивных алгоритмов поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах для протоколов OSPF и IGRP.

Протокол OSPF (Open Shortest Path First) широко используется в современных корпоративных вычислительных сетях и для построения таблиц маршрутизации применяет алгоритм Дейкстры. Однако трудоемкость этого алгоритма достаточно высокая, порядка 0(N2). Для повышения эффективности использования протокола OSPF предложена методика применения разработанных адаптивных алгоритмов маршрутизации, реализованная в виде программы, которая учитывает изменения структуры корпоративной вычислительной сети и позволяет получить трудоемкость 0(N).

Протокол IGRP (Interior Gateway Routing Protocol - протокол внутреннего шлюза) используется в корпоративных вычислительных сетях на базе маршрутизаторов CISCO и для построения таблиц маршрутизации применяет алгоритм Беллмана - Форда. Однако трудоемкость этого алгоритма достаточно высокая, порядка 0(N3). Для повышения эффективности использования протокола IGRP предложена методика применения разработанных адаптивных алгоритмов маршрутизации, реализованная в виде программы, которая учитывает изменения структуры корпоративной вычислительной сети и позволяет получить трудоемкость 0(N).

В четвертой главе «Программная реализация разработанных адаптивных алгоритмов маршрутизации в корпоративных вычислительных сетях» для исследования и сравнительного анализа эффективности выполнения процедур маршрутизации известных и предлагаемых алгоритмов поиска кратчайших путей разработан программный комплекс «Имитационное моделирование процессов маршрутизации в корпоративных вычислительных сетях». При реализации использовались средства разработки Borland Delphi.

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

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

Рис. 6. Число изменений дерева в графе из 10 вершин

Рис. 7, Число изменений дерева в графе из 100 вершин

' • ......

М-0,05939

максим}*! 1

л .....

О 10 20 30 40 50 60 70 60 90 100

юмер испытания

Рис. 8. Число изменений дерева в графе из 500 вершин

В таблице приведены обобщенные статистические характеристики для средней размерности задачи. В представленной таблице через СКО обозначено среднее квадратичное отклонение.

Были проведены исследования графов, состоящих из 10, 100 и 500 вершин. Исследование разработанных алгоритмов адагггивной маршрутизации показало, что математическое ожидание числа изменений не превышает величины N12, а его максимальное значение не превышает N. На основании этого можно сделать вывод, что предложенные адаптивные алгоритмы маршрутизации являются эффективными при поиске оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах.

Статистические характеристики для средней размерности задачи

Число вершин графа Минимальное значение Максимальное значение Математическое ожидание СКО

10 0,30 0,8182 0,5047 0,0943

100 0,06 0,7401 0,2185 0,1368

500 0 0,9192 0,0594 0,1173

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

В приложении представлены копии актов о внедрении.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

• проанализированы цели и задачи маршрутизации данных в вычислительных сетях с пакетной обработкой информации. Проведен анализ существующих протоколов адаптивной маршрутизации, в результате чего выявлены достоинства, недостатки и область применения протоколов. Выполнен анализ известных алгоритмов поиска кратчайших путей в графе, применяемых в современных маршрутизаторах. Показано, что трудоемкость современных алгоритмов определения оптимальных маршрутов не менее 0(1Ч2), где N - число маршрутизаторов в сети. На основании проведенного анализа сформулированы задачи разработки методов и алгоритмов определения оптимальных маршрутов с трудоемкостью

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

веса ребра графа представлена как процедура выполнения парных переходов ребер графа;

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

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

• на основе доказанных теорем и выводов разработаны метод и алгоритм адаптивной маршрутизации с учетом частичных изменений структуры сети в графе сокращенной размерности. Проведены доказательство правильности и расчет трудоемкости предлагаемого алгоритма, Верхняя и нижняя оценки трудоемкости соответственно равны ЩИ+М) и 0(М), где N - число узлов в сети, а М- число связей между ними;

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

• на основе доказанных теорем и выводов разработан метод и алгоритм парных перестановок маршрутов с учетом частичных изменений структуры сети. Проведено доказательство правильности разработанного алгоритма и показано, что его трудоемкость оценивается величиной 0(М), где N - число узлов в сети;

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

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

1. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Вестник Рязанской государственной радиотехнической академии. 2006. № 19. С. 114 - 116.

2. Перепелкин Д. А. Алгоритмы маршрутизации в локальных сетях // Информационные технологии в образовании: межвуз. сб. науч. тр. РГРТУ. 2006. С. 79-81.

3. Перепелкин Д.А. Исследование процессов маршрутизации в корпоративных вычислительных сетях // Новые информационные технологии в научных исследованиях и образовании: материалы XII всероссийской научно-технической конференции студентов, молодых ученых и специалистов. РГРТУ. 2007. С. 227 - 229.

4. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина. 2008. С. 100- 105.

5. Перепелкин Д.А., Перепелкин А.И. Алгоритмы маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина. 2008. С. 106 - 108.

6. Перепелкин Д.А., Перепелкин А.И. Программный комплекс для оценки процессов маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина, 2008* С. 109-111.

7. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритма динамической маршрутизации на базе протокола OSPF в корпоративных вычислительных сетях // Вестник Рязанского государственного радиотехнического университета. 2009. № 2 (выпуск 28). С. 68 - 72.

8. Перепелкин Д.А., Шибанов А.П. Повышение эффективности протокола OSPF при условии частичного изменения структуры корпоративных вычислительных сетей // 13-я Международная телекоммуникационная конференция студентов и молодых ученых «Молодежь и наука». Москва. МИФИ. 2009. http://www.mephi.ru/molod.

9. Перепелкин Д.А., Кравчук Н.В. Применение алгоритмов адаптивной маршрутизации в протоколе IGRP // 13-я Международная телекоммуникационная конференция студентов и молодых ученых «Молодежь и наука». Москва. МИФИ. 2009. http ://www.mephi.ru/molod.

ПЕРЕПЕЛКИН Дмитрий Александрович

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

Автореферат

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

Подписано в печать 09.11.09. Формат бумаги 60x84 1/16. Бумага офисная. Печать трафаретная. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Рязанский государственный радиотехнический университет. 390005, г. Рязань, ул. Гагарина, д.59/1. Редакционно-издательский центр РГРТУ.

Введение.

Глава 1. Основные принципы маршрутизации в корпоративных вычислительных сетях.

1.1. Цели и задачи маршрутизации.

1.2. Методы маршрутизации.

1.3. Классификация методов маршрутизации.

1.4. Алгоритмы поиска кратчайших путей.

1.5. Протоколы адаптивной маршрутизации.

1.6. Алгоритмы адаптивной маршрутизации.

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

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

Проблемами совершенствования методов и алгоритмов маршрутизации в вычислительных сетях занимались такие ученые, как Д. Бертсекас, Д. Гарсиа-Диас, П. Гупта, А.Б. Гольдштейн, Б.С. Гольдштейн, Д. Кантор, О.Я. Кравец,

Д.В. Куракин, И.П. Норенков, А. Филипс, С. Флойд, Р. Форд, Д. Фулкерсон и другие. Задачу нахождения кратчайших путей в транспортной системе рассматривали в своих трудах ученые Л. Беллман, Г. Габов, С. Гудман, Е. Дейкстра, В.А. Евстигнеев, В.Н. Касьянов, Р. Сэджвик, Р. Тарьян, С. Флойд, Р. Форд, Д. Фулкерсон. Подробное описание методов поиска кратчайших путей можно найти в работах Т. Кормена, Ч. Лейзерсона и Р. Ривеста.

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

На основании всего сказанного можно сделать вывод об актуальности выбранной темы диссертационной работы.

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

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

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

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

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

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

5) разработать адаптивный алгоритм поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах;

6) разработать адаптивный алгоритм поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных перестановках маршрутов;

7) разработать методики применения алгоритмов поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах для протоколов 08РР и ЮМ*.

Методы исследования. Разработка и исследование проводились на основе теории графов, теории алгоритмов, теории матриц, а также компьютерного моделирования.

Научная новизна диссертационной работы заключается в том, что впервые разработаны методы и алгоритмы адаптивной маршрутизации при условии частичного изменения структуры корпоративной вычислительной сети, которые позволяют получить меньшую трудоемкость [0(1V), где N - число узлов в сети] построения таблиц маршрутизации по сравнению с известными алгоритмами.

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

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

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

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

2) поиск кратчайших путей на графе с использованием алгоритма адаптивной маршрутизации и алгоритма парных перестановок маршрутов;

3) проведение экспериментов по изменению весов ребер графа, по добавлению и удалению вершин и ребер графа с построением дерева кратчайших путей;

4) оценка трудоемкости разработанных алгоритмов.

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

Апробация результатов диссертации. Основные результаты диссертационной работы докладывались на следующих конференциях:

• XII всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании», НИТ-2007. 19 — 21 апреля 2007 г., г. Рязань;

• всероссийской научно-технической конференции «Информационные и телекоммуникационные технологии. Подготовка специалистов для инфоком-муникационной среды» 21-23 апреля 2009 г., г. Рязань.

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

Внедрение результатов работы. Результаты работы внедрены в телекоммуникационной компании «Энлинк Трэйд», г. Рязань, где используются в составе комплекса диагностики и управления состоянием сети «НА1)Т2», а также внедрены в учебный процесс ГОУВПО "Рязанский государственный радиотехнический университет".

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, приложения, изложенных на 148 с. Список использованной литературы содержит 105 наименований. Текст диссертации содержит 19 таблиц и 30 рисунков.

Основные результаты и выводы

• Предложенные в диссертационной работе алгоритмы адаптивной маршрутизации были реализованы на языке Object Pascal. Разработан программный комплекс для исследования трудоемкости алгоритмов. При проектировании программного комплекса применялся модульный принцип построения.

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

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

121

Заключение

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

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

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

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

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

• на основе доказанных теорем и выводов разработаны метод и алгоритм адаптивной маршрутизации с учетом частичных изменений структуры сети в графе сокращенной размерности. Проведены доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости соответственно равны £2(Ы+М) и 0{Ы), где N — число узлов в сети, а М— число связей между ними;

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

• на основе доказанных теорем и выводов разработан метод и алгоритм парных перестановок маршрутов с учетом частичных изменений структуры сети. Проведено доказательство правильности разработанного алгоритма и показано, что его трудоемкость оценивается величиной 0(И), где N - число узлов в сети;

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

1. Адаптивный протокол иерархической маршрутизации // Экспресс — информация. Сер. ПИ. 1990. № 23. с. 9-12.

2. Архангельский А. Я. Приемы программирования в Delphi. М.: БИНОМ. 2003. 784 с.

3. Архангельский А .Я. Delphi 5. Справочное пособие. М.: ЗАО «Издательство БИНОМ». 2001. 768 с.

4. Блэк Ю. Сети ЭВМ: протоколы, стандарты, интерфейсы. Пер. с англ. М.: Мир. 1990. 506 с.

5. Буч Г., Якобсон А. и др. Унифицированный процесс разработки программного обеспечения для профессионалов / Якобсон А., Буч Г., Рамбо Дж. М.: СПб.: Киев: Минск: Питер. 2003. 496 с.

6. В.Г. Олифер, H.A. Олифер. Компьютерные сети. Принципы, технологии, протоколы. СПб.: Питер. 2001. 672 с.

7. Вирт Н. Алгоритмы и структуры данных / Пер. с англ. Подшивалова Д.Б. -2-е изд., испр. Спб.: Невский Диалект. 2001. 351 с.

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

9. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб: Питер. 2003. 368 с.

10. Ю.Грайнер В. Пополнение среди магистральных маршрутизаторов // Журнал сетевых решений / LAN. 2003. № 8. с. 51-54.

11. П.Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов-М.: Мир. 1981.368 с.

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

13. Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Техн. ун-т. М.: Лаборатория базовых знаний. 2001. 288 с.

14. Казаков В.А. Введение в теорию марковских процессов и некоторые радиотехнические задачи. М.: Сов. Радио. 1973. 231 с.

15. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: Обработка, визуализация и применение. Спб.: БХВ-Петербург. 2003. 1104 с.

16. Кемени Дж. и др. Счетные цепи Маркова / Пер. с англ. A.M. Зубкова, Б.А. Севастьянова. М.: Наука. 1987. 413 с.

17. Кемени Дж., Снелл Дж., Лори Дж. Конечные цепи Маркова / Пер. с англ. С.А. Молчанова и др.; под ред. A.A. Юшкевича. М.: Наука. 1970. 271 с.

18. Кениг Д., Штойян Д. Методы теории массового обслуживания / Пер. с нем. В. Ф. Матвеева, Р. Ш Нагапетяна; под ред. Г.П. Климова. М.: Радио и связь. 1981. 127 с.

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

20. Клейнрок Л. Теория массового обслуживания / Пер. с англ. И.И. Грушко; под ред. В.И. Неймана. М.: Машиностроение. 1979. 432 с.

21. Кнут Д.Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме». 2001. 720 с.

22. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск / Пер. с англ. под общ. ред. Казаченко Ю.В. 2-е изд., испр. и доп. М.: Издательский дом «Вильяме». 2000. 822 с.

23. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Центр непрер.матем. образования. 2000. 960 с.

24. Королев Д.Г. Разработка механизмов определения маршрутов между произвольными точками // Новые информационные технологии. 2001. с. 80-95.

25. Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие для вузов. 3-е изд., перераб. и доп. М.: Энергоатомиздат. 1987. 496 с.

26. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат. 1987. 400 с.

27. Коваленко И.Н. Случайные процессы: Справочник / И.Н. Коваленко, Н.Ю. Кузнецов, В.М. Шуренков. Киев: Наук, думка. 1983. 366 с.

28. Крейнес А. От Москвы до самых до окраин: маршрутами PNNI // Сети. Глобальные сети и телекоммуникации. 1998. №1. с.16-19.

29. Кравец О.Я., A.B. Пономарев, И.С. Подерский. Повышение эффективности маршрутизации в переходных режимах функционирования вычислительных сетей // Системы управления и информационные технологии. 2003. № 1-2. с.73-77.

30. Кульгин М. В. Технологии корпоративных сетей: Энциклопедия. СПб.: Питер. 2000. 699 с.

31. Кульгин М.В. Коммутация и маршрутизация 1РЛРХ трафика, АйТи. М.: КомпьютерПресс. 1998. 320с.

32. Куракин Д.В. Маршрутизаторы для глобальных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии. 1996. №2.

33. Куракин Д.В. Маршрутизация в сетях телекоммуникаций, построенных на базе международных стандартов взаимосвязи открытых систем // Автоматизация и современные технологии. 1996. №3. с. 35-43.

34. Куроуз Д., Росс К. Компьютерные сети. Многоуровневая архитектура Интернета: Пер с англ. 2-е изд. М.: СПб.: Питер. 2004. 765 с.

35. Кэнту М. Delphi 5 для профессионалов. СПб.: Питер. 2001. 644 с.

36. Льюис К. RIP: не пора ли на заслуженный отдых? // Сети и системы связи. 1997. №1. с.56-59.

37. Льюис К. Альтернативы протоколу RIP в больших сетях // Сети и системы связи. 1997. №5. с. 58-64.

38. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. М.: Мир. 1981. 323 с.

39. Марков A.A., Нагорный Н.М. Теория алгоритмов. М.: Наука. Гл. ред. физико — математ. лит. 1984. 432 с.

40. Матчо Д., Фолкнер Д.Р. Delphi / Под ред. Тимофеева В. М.: БИНОМ. 1996. 464 с.

41. Миллер Б.М., Панков А.Р. Теория случайных процессов в примерах и задачах/ Под ред. Кибзуна А.И. М.: Физматлит. 2002. 320 с.

42. Миллер М. Новый IP: на что он способен? // Сети. №1. с. 24-29.

43. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. И предисловие А.И. Штерна. М.: Наука. Гл. ред. физ-мат. лит. 1990. 488 с.

44. Новиков А.Б. Маршрутизация трафика в IP-сетях с применением генетических алгоритмов // Системы управления и информационные технологии. 2003. №1-2. с. 78-81

45. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети / Московский государственный технический университет. Москва. 1998. 232с.

46. Нанс Б. Компьютерные сети. М.: БИНОМ. 1995. 400с.

47. Олифер В.Г., Олифер H.A. Новые технологии и оборудование IP-сетей. СПб.: БХВ-Санкт-Петербург. 2001. 512 с.

48. Ope О. Теория графов. 2-е изд. М.: Наука. Главная редакция физико-математической литературы. 1980. 336 с.

49. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Вестник Рязанской государственной радиотехнической академии. 2006. № 19. С. 114 116.

50. Перепелкин Д.А. Алгоритмы маршрутизации в локальных сетях // Информационные технологии в образовании: межвуз. сб. науч. тр. РГРТУ.2006. С. 79-81.

51. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина. 2008. С. 100- 105.

52. Перепелкин Д.А., Перепелкин А.И. Алгоритмы маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина. 2008. С. 106 108.

53. Перепелкин Д.А., Перепелкин А.И. Программный комплекс для оценки процессов маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина, 2008. С. 109 111.

54. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритма динамической маршрутизации на базе протокола OSPF в корпоративных вычислительных сетях // Вестник Рязанского государственного радиотехнического университета. 2009. № 2 (выпуск 28). С. 68 72.

55. Перепелкин Д.А., Кравчук H.B. Применение алгоритмов адаптивной маршрутизации в протоколе IGRP // 13-я Международная телекоммуникационная конференция студентов и молодых ученых «Молодежь и наука». Москва. МИФИ. 2009. http://www.mephi.ru/molod.

56. Поповский В.В., Лемешко A.B., Мельникова Л.И., Андрушко Д.В. Обзор и сравнительный анализ основных моделей и алгоритмов многопутевой маршрутизации в мультисервисных телекоммуникационных сетях // Прикладная радиоэлектроника. 2005. Т.4. № 4. С. 372 382.

57. Пятибратов А.П. и др. Вычислительные системы, сети и телекоммуникации: Учебник. (2-е изд.). ФИС. 1998.

58. Пачеко К., Тейксейра С. Delphi 5. Руководство разработчика: Пер. с англ. Т.1: Основные методы и технологии. М.: Вильяме. 2000. 831 с.

59. Потемкин В.Г. Matlab 6: среда проектирования инженерных приложений. М.: Диалог-МИФИ. 2003. 448 с.

60. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows / Пер с англ. 4-е изд. СПб: Питер. М.: Издательско-торговый дом «Русская редакция». 2001. 752 с.

61. Саати Т. Элементы теории массового обслуживания и ее приложения / Пер. с англ. Е.Г. Коваленко; под ред. И.Н. Коваленко с предисл. Акад. Б.В. Гнеденко. 2-е изд. М.: Сов. Радио. 1971. 520 с.

62. Саймон P.Windows 2000 API. Энциклопедия программиста: Пер. с англ. / Ричард Саймон. К.: СПб.: ООО «ДиаСофтЮП». 2002. 1088 с.

63. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: Мир. 1984. 455 с.

64. Седжвик Р. Фундаментальные алгоритмы на С. Анализ, структуры данных, сортировка, поиск, алгоритмы на графах: Пер. с англ. СПб.: ООО «ДиалогСофтЮП». 2003. 1136 с.

65. Столлингс В. Современные компьютерные сети. 2-е изд. СПб.: Питер. 2003. 783 с.

66. Танненбаум Э. Компьютерные сети. Спб.: Питер. 2002. 848 с.

67. Трауб Д., Вожняковский X. Общая теория оптимальных алгоритмов / Перевод с англ. А.Г. Сухарева; под ред. Н.С. Бахвалова. М.: Мир. 1983. 382 с.

68. Уваров Д.В. Определение условий возникновения и принципов обработки парных переходов ребер в графе в задаче поиска кратчайших путей // Межвузовский сборник научных статей «Новые информационные технологии». Рязань. 2004. с. 55-60.

69. Уваров Д.В., Перепелкин А.И. Динамический алгоритм маршрутизации в вычислительной сети // Вестник Рязанской государственной радиотехнической академии. Выпуск 12. Рязань. 2003. с. 77-80.

70. Уваров Д.В., Перепелкин А.И. Определение условий использования линии связи при решении задачи маршрутизации в вычислительной сети // Известия Белорусской инженерной академии. 2004. с. 131—134.

71. Уваров Д.В., Перепелкин А.И., Корячко В .П. Построение дерева кратчайших путей в графе на основе данных о парных переходах // Системы управления и информационные технологии. 2004. №4(16). с. 93-96.

72. Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения. М.: Наука. 1987. 288 с.

73. Фардал Р. Как повысить производительность IP-магистрали // Сети. 1998. №5. с. 24-25.

74. Фаронов В.В. Delphi. Программирование на языке высокого уровня: Учебник. М.: СПб.: Питер. 2003. 640 с.

75. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х т. Т. 1. Перевод с англ. под ред. Ю.В. Прохорова. М.: Мир. 1984. 528 с.

76. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х т. Т. 2. Перевод с англ. под ред. Ю.В. Прохорова. М.: Мир. 1984. 738 с.

77. Филипс Д. Гарсиа-Диас А. Методы анализа сетей: пер. с англ. М.: Мир. 1984. 496 с.

78. Френк Г., Фриш И. Сети, связи и потоки / Пер. с англ. под ред. Д.А. Поспелова. М.: Связь. 1978. 448 с.

79. Эдди С.Э. XML: Справочник. СПб.: Питер. 1999. 477 с.

80. Brodnik A., Carlsson S., Degemark М., Pink S., «Small Forwarding Tables for Fast Routing Lookups». Proceedings of ACM SIGCOMM '97 (Cannes, France, Oct, 1997). pp. 3-15. http://www.acm.org/sigs/-sigcomm/sigcomm97/papers/pl92.html.

81. Christiansen M., Jeffay K., Ott D., Smith F. D., «Tuning Red for Web Traffic», IEEE / ACM Transactions on Networking. Vol. 9. No. 3 (June 2001). pp. 249-264. http://www.cs.unc.edu/~ieffav/papers/IEEE-ToN-01 .pdf.

82. Cisco Systems Inc. Catalyst 8500 ampus Switch Router Architecture».http://www.cisco.com/univercd/cc/td/doc/pcat/ca8500c.htm.

83. Cisco Systems Inc. «Next Generation ClearChannel Architecture for Catalyst 1900/2820 Ethernet Switches»,http://www.cisco.com/warp/public/cc/pd/si/casi/cal900/tech/nwgenwp.htm.

84. Cisco Systems.«Cisco 12000 Series Gigabit Switch Router~s», http://www.cisco.com/univercd/cc/td/doc/pcat/12000.htm.

85. Floyd S. «References on RED (Random Early Detection) Queue Management», http://www.icir.org/floyd/red.html.

86. Gupta P., Lin S., McKeown N., «Routing lookups in hardware at memory access speeds», Proc. IEEE Infocom 1998 (San Francisco, CA, April 1998), pp. 1241-1248, http://tinytera.stanford.edu/~nickm/papers/ Infocom981ookup.pdf.

87. Gupta P., McKeown N., «Algorithms for Packet Classification», IEEE Network Magazine.Vol. 15. o. 2 (Mar. / Apr. 2001).pp. 24-32, http://klamath.stanford.edu/~pankai-/paps/ieeenetwork tut Ol.pdf.

88. Labrador M., Banerjee S., «Packet Dropping Policies for ATM and IP Networks». IEEE Communications Surveys. Vol. 2. No. 3 (Third Quarter 1999). pp. 2-14. http://www.comsoc.org/livepubs/surveys/public/ 3q99issue/banerjee.html.

89. Leland W., Taqqu M., Willinger W., Wilson D. On the Self-Similar Nature of Ethernet Traffic. Proceedings (Extended Veresion). IEEE/ACM Transactions on Networking. February 1994.

90. RFC-1745. BGP4/IDRP for IP ~ OSPF Interaction. K. Varadhan, S. Hares, Y. Rekhter. December 1994.

91. RFC—1058. Routing Information Protocol. C.L. Hedrick. 1988.

92. RFC—1142. OSIIS-IS Intra-domain Routing Protocol. D. Oran. 1990.

93. RFC—1163. A Border Gateway Protocol (BGP). K. Logheed, Y. Rekhter. 1990.

94. RFC—1247. OSPF Version 2. J. Moy. 1991.

95. RFC—1267. A Border Gateway Protocol 3 (BGP-3). K. Logheed, Y. Rekhter. 1991.

96. RFC—904. Exterior Gateway Protocol Formal Specification. D.L. Mills. 1984.

97. Srinivasan V. and Varghese G. «Fast Address Lookup Using Controlled Prefix Expansion». ACM Transactions Computer Sys. Vol. 17. No. 1 (Feb 1999). pp. 1-40. http://www-cse.-ucsd.edU/-users/varghese/PAPERS/cpeTOCS.ps.Z.

98. Waldvogel M. et al. «Scalable High Speed IP Routing Lookup». Proceedings of ACM SIGCOMM '97 (Cannes, France, Sept. 1997). http://www.acm.org/sigs/-sigcomm/-sigcomm97/-papers/pl 82.html.

99. Williamson C. A Model for Self-Similar Ethernet LAN Traffic: Design, Implementation, and Performance Implications, ftp://ftp.cs.usask.ca/ pub/discus/paper.95-7.ps.Z.

100. Williamson C. Generating Synthetic Traffic Streams for ATM Network Simulations, http://www.cs.usask.ca/faculty/carev/papers/guidelines.ps.

101. Williamson C. Statistical Multiplexing of Self-Similar Network Traffic. http://www.cs.usask.ca/faculty/-carey/papers/statmuxing.ps.

102. Xiaojun H. The Self-Similar Traffic Modeling in the Internet. http://www.ee.ust.hk/~heixj/publication/comp660fi/comp660f.html.1. ЪЪ