Разработка и исследование алгоритмов адаптивной маршрутизации в мультисервисных сетях связи тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Поздняк, Ирина Сергеевна

• Поздняк, Ирина Сергеевна
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Поздняк, Ирина Сергеевна

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

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

Список литературы диссертационного исследования кандидат технических наук Поздняк, Ирина Сергеевна, 2009 год

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.