Методы и алгоритмы ускоренной маршрутизации в корпоративных вычислительных сетях тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Уваров, Дмитрий Владиславович

• Уваров, Дмитрий Владиславович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Уваров, Дмитрий Владиславович

Введение.

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

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

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

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

1.4. Протоколы маршрутизации.

1.5. Устройство маршрутизатора.

1.6. Поиск в ширину.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Проведено доказательство правильности и оценка трудоемкости разработанных алгоритмов.

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

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

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

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

• поиск кратчайших путей на графе с использованием алгоритмов Дейкстры и Беллмана-Форда;

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

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

• оценка трудоемкости (количества действий) алгоритма.

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

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

• применением выводов теории систем и сетей массового обслуживания, теории вероятностей и статистики;

• использованием результатов теории самоподобных стохастических процессов;

• применением положений теории графов;

• использованием выводов теории алгоритмов;

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

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

• 8-я Всероссийская конференция «Нейрокомпьютеры и их применения» НКП-2002 с международным участием 21-22 марта 2002 г., г. Москва.

• Всероссийская научная конференция "Проектирование научных и инженерных приложений в среде MATLAB" 28-29 мая 2002 г., г. Москва.

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

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

Публикации. По теме диссертационной работы опубликовано 13 работ.

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

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Содержит 196 страниц, 14 таблиц, 33 рисунка. Список литературы состоит из 118 наименований.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Уваров, Дмитрий Владиславович

Результаты работы были внедрены на предприятии ООО «Клиент серверные технологии - М-3» в составе «Информационной системы управления предприятием М-3», а также для организации информационного обмена между подразделениями предприятия и клиентами. Применение методики уменьшения размерности задачи и методов обработки изменения значения метрики связи обеспечило повышение оперативности и надежности передачи информации до получателей.

Заключение

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

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

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

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

1. Выбор единственного кратчайшего пути по критерию минимизации оценки пути.

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

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

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

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

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

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

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

Введено понятие парного перехода и точки вхождения ребра в дерево кратчайших путей. Сформулированы и доказаны теоремы, определяющие условия срабатывания парных переходов ребер графа. Операция обработки изменения веса ребра графа представлена как процедура выполнения парных переходов ребер графа. На основе выводов сформулированных теорем разработан алгоритм расчета и выбора парных переходов. Проведено доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости соответственно равны Q(N) и 0(N). Разработан программный комплекс для оценки эффективности выполнения функций маршрутизации в вычислительных корпоративных сетях. Предлагаемые в работе алгоритмы были реализованы на языке Object Pascal. При проектировании программного комплекса применялся модульный принцип построения. При разработке программного обеспечения использовался объектно-ориентированный подход к проектированию программных систем с использованием техники паттернов, что позволило добиться максимально возможной степени повторного использования проектных решений. Было проведено исследование работы предлагаемых алгоритмов. При этом основное внимание уделялось оценке корректности работы алгоритмов и размерности решаемой задачи. Для каждого эксперимента было найдено математическое ожидание и среднее квадрати-ческое отклонение для размерности задачи.

Список литературы диссертационного исследования кандидат технических наук Уваров, Дмитрий Владиславович, 2004 год

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

2. Альянах И.Н. Моделирование вычислительных систем. Д.: Машиностроение. Ленингр. отд-ние, 1988. - 233 с.

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

4. Ахо А. и др. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман: пер с англ. М.: Мир, 1979. - 356 с.

5. Баженова И.Ю. Delphi 5. Самоучитель программиста. М.: КУДИЦ-ОБРАЗ, 2000. - 335 с.

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

7. Бобровский С.И. Delphi 5. Начальный курс. М.: ДЕСС, 1999. -271 с.

8. Буч Г. и др. Язык UML. Руководство пользователя: Пер. с англ./ Буч Г., Рамбо Д., Джекобсон А. М.: ДМК, 2000. - 429 с.

9. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++/Пер. с англ. под ред. Романовского И. А., Андреева Ф. Г.- 2-е изд. М.: БИНОМ, 2001. -558 с.

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

11. В.Г. Олифер, Н.А. Олифер. Компьютерные сети. Принципы, техно-(iф логии, протоколы. СПб.: Питер, 2001. - 672 е.: ил.

12. Ванг Ж. Маршрутизация обретает интеллектуальность. // Журнал сетевых решений/ LAN. 2002. - № 6. - с. 73-77

13. Вентцель Е.С. Теория вероятностей: Учебник для вузов. 8-е изд., стереотип. - М.: Высшая школа, 2002. - 576 с.

14. Вентцель Е.С., Овчаров J1.A. Прикладные задачи теории вероятностей. М.: Радио и связь, 1983. - 416 с.

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

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

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

18. СПб: Питер, 2003. -368 е.: ил.

19. Гнеденко Б.В. Курс теории вероятностей: Учеб. 7-е изд., испр. -М.: Эдиториал УРСС, 2001.-318 с.

20. Гофман В. К., Хомоненко А. В. Delphi 5. СПб.: М.: Минск: Питер, 2001.-560 с.

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

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

23. Дарахвелидзе П.Г. и др. Программирование в Delphi 5/ Дарахвелид-зе П.Г., Марков Е.П., Котенок О. Е. СПб.: БХВ-Санкт-Петербург, 2000. - 774 с.

24. Дынкин Е. Б., Юшкевич А.А. Управляемые марковские процессы и (ф их приложения. М.: Наука, 1975. - 33 8 с.

25. Елкин Д.В., Перепелкин А.И. Аспекты моделирования процессов маршрутизации в вычислительных сетях // Межвуз. сб. научн. трудов «Математическое и программное обеспечение вычислительных систем». Рязань, 2002. С. 71-73.

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

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

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

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

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

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

32. Кениг Д., Штойян Д. Методы теории массового обслуживания / Пер.

33. Ф с нем. В. Ф. Матвеева, Р. Ш Нагапетяна; под ред. Г.П. Климова. М.:

34. Радио и связь, 1981. 127 с.

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

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

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

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

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

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

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

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

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

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

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

46. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика, АйТи. -М.: КомпьютерПресс. 1998. 320с.

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

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

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

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

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

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

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

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

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

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