Разработка метода и алгоритмов многопутевой маршрутизации для повышения отказоустойчивости IP сетей тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Гликман, Юрий Константинович

• Гликман, Юрий Константинович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Гликман, Юрий Константинович

Введение

Глава 1. Методы, протоколы и алгоритмы маршрутизации в современных IP сетях.

1.1. Архитектура сети Интернет.

1.2. Основные метрики динамических протоколов маршрутизации

1.3. Протоколы маршрутизации внутреннего шлюза.

1.3.1. Протокол маршрутизации RIP.

1.3.2. Протокол маршрутизации OSPF.

1.4. Современные алгоритмы маршрутизации.

1.4.1. Алгоритм маршрутизации на основе алгоритма Дейкстры

1.4.2. Алгоритм Суурбалле для поиска пары кратчайших независимых по рёбрам путей.

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

1.4.4. Алгоритм многопутевой маршрутизации Шольмайера.

1.4.5. Алгоритм многопутевой маршрутизации Райхерта.

1.5. Основные типы сбоев в компьютерных сетях.

1.6. Недостатки существующей IP маршрутизации.

1.7. Постановка задачи.

1.8. Выводы по первой главе.

Глава 2. Графы маршрутизации.

2.1. Моделирование маршрутизации на основе теории графов.

2.2. Метод 02 многопутевой маршрутизации.

2.3. Свойства топологий сетей совместимых с 02 многопутевой маршрутизацией.

2.4. Алгоритм проверки совместимости топологий сетей с 02 многопутевой маршрутизацией.

2.5. Алгоритм построения 02 совместимых топологий сетей.

2.6. Выводы по второй главе.

Глава 3. Алгоритмы многопутевой маршрутизации.

3.1. Требования к 02 алгоритмам маршрутизации.

3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе пошагового улучшения.

3.3. Шаблонный подход построения многопутевой маршрутизации.

3.3.1. Алгоритм построения графов многопутевой (02) маршрутизации на основе четырёх шаблонов.

3.3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе шести шаблонов.

3.4. Сравнение алгоритмов.

3.5. Выводы по третьей главе.

Глава 4. Пути практической реализации 02 многопутевой маршрутизации.

4.1. Реализация механизма работы соединений-джокеров.

4.2. Пакет программ для расчёта и анализа графов маршрутизации.

4.2.1. Программа для расчёта графов многопутевой маршрутизации.

4.2.2. Программа для анализа графов многопутевой маршрутизации и топологий сетей.

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

4.3. Выводы по четвёртой главе.

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

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

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

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

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

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

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

3) разработать критерии и алгоритм проверки совместимости топологии компьютерной сети с многопутевой маршрутизацией;

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

5) проверить эффективность применения разработанного метода маршрутизации;

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

Методы исследования. В ходе исследования были использованы подходы и методы теории графов, методы теории вероятности, комбинаторного анализа, системного и объектно-ориентированного анализа. В разработке программного обеспечения использовалась технология объектно-ориентированного программирования.

На защиту выносятся следующие результаты:

1) 02 метод многопутевой маршрутизации по адресу получателя.

2) Шаблонные алгоритмы многопутевой маршрутизации на основе 4 и 6 шаблонов.

3) Метод принятия решения о совместимости топологии компьютерной сети с многопутевой (02) маршрутизацией.

4) Алгоритм построения топологий компьютерных сетей, совместимых с многопутевой (02) маршрутизацией.

Научная новизна:

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

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

3) Разработан алгоритм для проверки совместимости топологии сети с многопутевой (02) маршрутизацией. Использование этого алгоритма позволяет быстро выявить недостатки топологии сети с точки зрения многопутевой маршрутизации.

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

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

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

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

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

Реализация результатов работы. Разработанные в рамках диссертации алгоритмы были реализованы в виде пакета программ для расчёта и анализа многопутевой маршрутизации, а также анализа топологий компьютерных сетей. Данный пакет программ применяется СЦПС «Спектр», а также фирмой ОАО «Телекомпания Санкт-Петербургское кабельное телевидение», при проектировании новых и для анализа существующих каналов связи. Разработанные алгоритмы многопутевой маршрутизации были использованы Фраунхоферским институтом Открытых телекоммуникационных Систем Фокус в проекте KING, посвящённом разработке компьютерных сетей следующего поколения. Разработанный метод многопутевой маршрутизации был оформлен в виде патентного предложения.

Апробации работы. Приведенные в диссертации результаты были представлены на VIII Санкт-Петербургской международной конференции "Региональная информатика 2002" (Санкт-Петербург, 25-28 ноября 2002), на III Санкт-Петербургской конференции «Информационная безопасность регионов России (ИБРР-2003)» (Санкт-Петербург, 25-27 ноября 2003), на «2003 IEEE Workshop on High Performance Switching and Routing» (Турин, Италия, 24-28 июня, 2003) и на «IPS-MoMe 2005» (Варшава, Польша, 14-17 марта 2005).

Публикации. Основные результаты диссертации опубликованы в 5 печатных работах.

Структура и объем работы. Диссертация содержит введение, четыре главы, заключение, список литературы (124 наименований); 12 таблиц и 41 рисунок (общий объем диссертации — 119 листов).

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Гликман, Юрий Константинович

4.3. Выводы по четвёртой главе

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

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

Заключение

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Гликман, Юрий Константинович, 2005 год

1. Белоцерковский Д.Л., Вишневский В.М. Новый алгоритм генерации остовных двусвязных подграфов для оптимизации топологии сетей передачи данных // Автоматика и телемеханика. 1997. - №1. -С.108-120.

2. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. М: Мир, 1989. - 544с.

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

4. Вишневский В.М., Воробьев Д.Л. Архитектура IP-сети для качественной пакетной телефонии // Электросвязь. 2000. - №10. - С. 14-15.

5. Вишневский В.М., Левнер Е.В., Федотов Е.Б. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных // Информационные процессы. 2001. - Т.1, №2. - С.103-126.

6. Вишневский В.М., Пороцкий С.М. Динамическая маршрутизация в ATM сетях проблемы и решения // Автоматика и телемеханика. -2003.-№6.-С. 20-23.

7. Вишневский В.М., Федотов Е.Б. Анализ методов маршрутизации при проектировании сетей пакетной коммутации // Proceedings of 3-rd I.S. "Teletrafflc Theory and Computing Modeling". София: 1992. - С. 8693.

8. Воробьев В.И., Гликман Ю.К. Повышение безопасности IP сети при помощи многопутевой маршрутизации // Proceedings of Материалы конференции "Региональная информатика 2002". - СПб: 2002.

9. Гликман Ю.К. "Выбор и усовершенствование генератора WEB трафика для тестирования поведения маршрутизатора в состоянииперегрузки", Труды СПИИРАН / Под ред. P.M. Юсупова вып. 1 т. 3. -СПб.: «Анатолия», 2003. С. 49-56.

10. Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей // Автоматика. 1981. - №3. - С.35-44.

11. Зима В.М., Молдавян Н.А., Молдавян А.А. Безопасность сетевых технологий. СПб.: СПбГУ, 1999. - 368с.

12. Зима В.М., Молдовян А.А., Молдовян Н.А. Безопасность глобальных сетевых технологий. СПб.: "БХВ-Петербург", 2000. - 320с.

13. Камер Д., Э. Сети TCP/IP, том 1. Принципы, протоколы и структура, 4-е изд.: пер. с англ. М.: Издательский дом "Вильяме", 2003. - 880с.

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

15. Коннов В.В., Клековкин Г.А., Коннова Л.П. Геометрическая теория графов. М: Народное образование, 1999. - 240с.

16. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2001. - 960с.

17. Круглый З.П. Алгоритмы расчета моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины. 1980. - № 4. - С. 73-79.

18. Кульчин М. Технологии корпоративных сетей. СПб: Изд-во "Питер", 2000. - 704с.

19. Купиллари А. Трудности доказательств: пер. с англ. М: Техносфера, 2002. - 304с.

20. Лазарев В.Г. Интеллектуальные цифровые сети. М: Финансы и статистика, 1996. - 382с.

21. Макконнелл Д. Анализ алгоритмов. Вводный курс: пер. с англ. М: Техносфера, 2002. - 304с.

22. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М: Радио и связь, 1986. - 408с.

23. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. М: Наука, 1990. - 488с.

24. Олифер В., Олифер Н. Новые технологии и оборудование IP-сетей. -СПб: Изд-во "Питер", 2000. 512с.

25. Остерлох X. Маршрутизация в IP- сетях. Принципы, протоколы, настройка: пер. с англ. СПб.: ООО «ДиаСофт», 2002. - 512с.

26. Сатовский Б.Л. MPLS технология маршрутизации для нового поколения сетей общего пользования // Сети и системы связи. - 2001.- № 3. С.29.

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

28. Тимофеев А.В. Методы высококачественного управления, интеллектуализации и функциональной диагностики автоматических систем // Международный теоретический и прикладной научно-технический журнал «Мехатроника, автоматизация и управление». -2004. С. 2-9.

29. Тимофеев А.В. Проблемы и методы адаптивного управления потоками данных в телекоммуникационных системах // «Информатизация и связь». 2003. - №№1-2. - С. 68-74.

30. Шварц М. Сети связи: протоколы, моделирование и анализ. М: Наука, 1992. - 263с.

31. Al-Fuqaha A., Chaudhry G.M. Routing and wavelength assignment in all-optical DWDM networks with sparse wavelength conversion capabilities.- Kansas City: University of Missouri, 2004. 161p.

32. Anand V., Chakrabarty K. Cisco IP routing protocols: troubleshooting techniques, 1st ed. Hingham, Mass.: Charles River Media, 2004. - 409p.

33. Apostolopoulos G., Guerin R., Kamat S., Tripathi S. Improving QoS Routing Performance under Inaccurate Link State Information // ITC. -1999.- 16.-pp.32-37.

34. Ash G.R. Dynamic routing in telecommunications networks. New York: McGraw Hill, 1998. - 746p.

35. Bak S. Load-Balanced routing. Houston: University of Houston, 2000. -145p.

36. Baker F., "RFC1812 Requirements for IP Version 4 Routers," IEEE, 1995.

37. Bedrosian E., Rand Corporation. A routing algorithm for digraphs. Santa Monica: Rand Corporation, 1976. - 4 p.

38. Bhandari R. Survivable networks: algorithms for diverse routing. -Boston; London: Kluwer Academic Publishers, 1999. 200p.

39. Black U. IP routing protocols: RIP, OSPF, BGP, PNNI, and Cisco routing protocols. London: Prentice-Hall International, 2000. - 287p.

40. Blaunstein N., Andersen J.B. Multipath phenomena in cellular networks. -Boston, Mass.; London: Artech House, 2002. 296 p.

41. Cantor D.G., Gerla M. Optimal routing in a packet-switched computer network // IEEE Trans, on Computers. 1974. - V. C-23, N 10. - pp. 10621068.

42. Chao H.J., Guo X. Quality of service control in high-speed networks. -New York: Wiley, 2002. 432p.

43. Chaparadza R., Glickman Y. RTLG -RSVP enabled Traffic Load Generator for Intra-Domain and Inter-Domain QoS Signalling Tests // Proceedings of Internet Performance, Simulation, Monitoring and Measurments (IPS-MoMe 2005). Warsaw: 2005. - pp. 132-140.

44. Chen S., Nahrstedt K. An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions // IEEE

45. Network Magazine, Special Issue on Transmission and Distribution of Digital Video. 1998. - V.12, No.6. - pp.64-79.

46. Cidon I., Rom R., Shawitt Y. Analysis of Multi-Path Routing // IEEE Transaction on Networking. 1999. - V.7. - pp.885-896.

47. Clark M.P. Data networks, IP and the Internet: protocols, design and operation. Chichester: Wiley, 2003. - 848 p.

48. Das R., Chakrabarty K. Enabling IP routing with Cisco routers, 1 st ed. -Hingham, Mass.: Charles River Media, 2004. 486p.

49. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. - V.l. - pp.269-271.

50. Dror M. Arc routing: theory, solutions, and applications. Boston, Mass.; London: Kluwer Academic, 2000. - 483 p.

51. Evans J.R., Minieka E., Minieka E. Optimization algorithms for networks and graphs, 2nd ed. New York: M. Dekker, 1992. - 470p.

52. Floyd R.W. Algorithm 97: Shortest path // Comm. ACM. 1997. - N3. -pp.320-327.

53. Forouzan B.A. TCP/IP protocol suite, 2nd ed. Boston: McGraw-Hill, 2003. - 942 p.

54. Fotz В., Rexford J., Thorup M. Traffic Engineering with Traditional IP Routing Protocols // IEEE Communications Magazin. 2002. - No. 10. -pp. 118-124.

55. Fotz В., Thorup M. Optimizing OSPF/IS-IS Weights in a Changing World // IEEE J. Select. Areas Commun. 2002. - V.20. - pp.756-767.

56. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic shortest paths and negative cycle detection on digraphs with arbitrary arc weights. Saarbruecken: Max-Planck-Institut fuer Informatik, 1998. - 18p.

57. Gafni M., Berstsekast D. Asymptotic Optimality of Shortest Path Routing Algorithms // IEEE Trans, on Information Theory. 1987. - no.l. - pp. 97133.

58. Garcia-Luna-Aceves J.J., Murthy S. A Path-Finding Algorithm for Loop-Free Routing // IEEE ACM Trans. Networking. 1997. - N2. - pp.76-82.

59. Gavish В., Hantler S.L. An algorithm for optimal rout selection in SNA networks // IEEE Trans, on Commun. 1983. - N10. - pp.1154-1161.

60. Gelenbe E., Pujolle G. Introduction to queueing networks. N.Y.: John Wiley, 1998. - 396c.

61. Guerin R., Orda A. QoS-based Routing in networks with Inaccurate Information: Theory and Algorithms // Proceedings of INFOCOM'97. Spring-Verlag, 1997. pp. 154-161.

62. Guido P. Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study // Proceedings of 4th International Workshop on Algorithm Engineering. Saarbruecken, Germany: Spring-Verlag, 1982. -pp.228-235.

63. Hedrick C., "RFC 1258 Routing Information Protocol," IEEE, 1988.

64. Henig M.I. The shortest path problem with two objective functions // European J. of Operational Research. 1985. - V.25. - pp.281-291.

65. Huitema C. Routing in the internet, 2nd ed. ed. Upper Saddle River, N.J.: Prentice Hall, 2000. - 384p.

66. Jacquet P., Muhlethaler P., Qayyum A. Optimized Link State Routing Protocol//-2001.

67. Johnson D. The Evolution of a Reliable Transport Network // IEEE Commun. Mag. 1999. - V.8. - pp.52-57.

68. Jungnickel D. Graphs, networks and algorithms. Berlin, Germany: Springer, 1999. - 589p.

69. Kelly F.P. Routing and capacity Allocation in Networks with Trunk Reservation // Mathematics of Operations Research. 1990. - V.15. -pp.771-793.

70. Kelly F.P. Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentralization // Advances in Applied Probability. 1998. -V.20.-pp.112-144.

71. Kelly F.P., Williams R.J. Stochastic networks. New York: Springer-Verlag, 1995. - 427p.

72. Korilis Y.A., Orda A. Incentive compatible pricing strategies for QoS routing. Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 2002. - 21 p.

73. Lee W.C.e.a. Rule-Based Call-by-Call Source Routing for Integrated Communication Networks // Proc. IEEE INFOCOM'93. 1993. - pp.987993.

74. Lorenz D.H. Efficient QoS partition and routing of unicast and multicast.- Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1999. 24 p.

75. Lorenz D.H., Orda A. QoS routing in networks with uncertain parameters.- Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1997. 51 p.

76. Loshin P. Big book of border gateway protocol (BGP) RFCs. San Diego, Calif.; London: Morgan Kaufmann, 2000. - 570p.

77. Loshin P. Big book of World Wide Web RFCs. San Francisco, Calif.; London: Morgan Kaufmann, 2000. - 655p.

78. Malkin G., "RFC 2453," IEEE, 1998.

79. Malkin G.S. RIP: an intra-domain routing protocol. Reading, MA: Addison-Wesley, 2000. - 253p.81 . McDysan D.E. QoS and traffic management in IP and ATM networks. -New York: McGraw Hill, 2000. 456p.

80. Minsoo J., Dongseung K. Avoiding Network Congestion with Local Information // Proceedings of International Symposium on High Performance Computing. Kansai Science City, Japan: Springer, 2002. -pp.33-40.

81. Mouftah H.T., Ho P.-H. Optical networks: architecture and survivability. -Boston: Kluwer Academic, 2003. 302p.

82. Moy J. OSPF, RFC 1583. IEEE, 1998.

83. Moy J.T. OSPF: anatomy of an Internet routing protocol. Reading, Mass.; Harlow: Addison-Wesley, 1998. - 339p.

84. Murakami K., Kim H.-S. Comparative study on restoration schemes of survivable ATM networks // IEEE Commun. Mag. 1997. - no.5. -pp.652-680.

85. Nagle J. Congestion Control in TCP/IP Internetworks // Computer Commun. Rev. 1984. - vol.14. - pp.112-116.

86. Nishizeki Т., Chiba N. Planar graphs: theory and algorithms. -Amsterdam: North-Holland, 1988. 232p.

87. Orda A. Routing with end to end QoS guarantees in broadband networks.- Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1997. 26p.

88. Orda A., Rom R. Optimal routing with packet fragmentation in computer networks. Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1992. - 30p.

89. Orda A., Sprintson A. Precomputation schemes for QoS routing. Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 2003. - 31 p.

90. Parkhurst W.R. Cisco router OSPF: design and implementation guide. -New York; London: McGraw-Hill, 1998. 340p.

91. Parkhurst W.R. Routing first-step. Indianapolis, IN: Cisco, 2005. - 414p.

92. Pepelnjak I. EIGRP network design solutions. Indianapolis, IN, USA: Cisco Press, 2000. - 366p.

93. Peterson L.L., Davie B.S. Computer networks: a systems approach, 3rd ed. Amsterdam; Boston: Morgan Kaufmann Publishers, 2003. - 813p.

94. Piro M., Medhi D. Routing, flow, and capacity design in communication and computer networks. San Francisco, Calif.: Morgan Kaufmann; Oxford: Elsevier Science, 2004. - 400p.

95. Postel J.B., United States. Defense Advanced Research Projects Agency A Graph model analysis of computer communications protocols. Los Angeles: University of California. School of Engineering and Applied Science, 1974. - 183p.

96. Reichert C., Glickman Y., Magedanz T. Two Routing Algortihms for Failure Protection in IP Networks // Proceedings of 10th IEEE Symposium on Computers and Communications. IEEE Press, 2005. pp. 97-102.

97. Retana A., White R., Slice D. EIGRP for IP: basic operation and configuration. Boston: Addison-Wesley, 2000. - 123p.

98. Roberts J. Traffic theory and the Internet // IEEE Communications Mag. -2001.-vol.39.-pp.94-99.

99. Salama H., Reeves D., Viniotis Y. Distributed Algorithm for Delay-Constrained Routing // Proceedings of INFOCOM'97. 1997. pp. 146-152.

100. Schollmeier G., Charzinski J., Kirstadter A., Reichert C., Schrodi K.J., Glickman Y., Winkler C. Improving the Resilience in IP Networks // Proceedings of IEEE Workshop on High Performance Switching and Routing 2003. 2003. pp.91-96.

101. Schulzrinne H. A comprehensive multimedia control architecture for the Internet // Proceedings of International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV). -St. Louis, Missouri: 1997. pp. 322-327.

102. Schulzrinne H. Internet problems and potential // Proceedings of Global Information Infrastructure Workshop at IEEE International Conference on Communications (ICC). Montreal, Canada: 1997. - pp. 154-159.

103. Schulzrinne H., Rosenberg J. Signaling for internet telephony // Proceedings of ICNP. Austine, Texas: 1998. - pp.231-237.

104. Shands D. The performance of probabilistic routing. Miami: University of Florida, 1998. - 91p.

105. Stallings W. High-speed networks and internets: performance and quality of service, 2nd ed. Upper Saddle River, N.J.: Prentice Hall, 2002. -715p.

106. Stamatelakis D., Grover W. IP Layer Restoration and Network Planning Based on Virtual Protection Cycles // IEEE J. Select. Areas Commun. -2000. vol.18. - pp. 1938-1949.

107. Stewart J.W. BGP4: inter-domain routing in the Internet. Reading, Mass.; Harlow: Addison-Wesley, 1999. - 137p.

108. Suurballe J.W. Disjoint Paths in a Network // Networks. 1974. - no.4. -pp. 125-145.

109. Suurballe J.W., Taijan, R.E. A quick method for finding shortest pairs of disjoint paths //Networks. 1984. - vol.14. - pp.325-336.

110. Thomas S.A. IP switching and routing essentials: understanding RIP, OSPF, BGP, MPLS, CR-LDP, and RSVP-TE. New York: Wiley, 2001. - 358p.

111. Thomas T.M. OSPF network design solutions, 2nd ed. Indianapolis, IN: Cisco Press, 2003. - 747p.

112. To M., Neusy P. Unavailability Analysis of Long-Haul Networks // IEEE J. Select. Areas Commun. 1994. - vol.12, no.l. - pp. 100-109.

113. Toy M. Optical networking. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc., 2001. - 397p.

114. Tran D.T., Do T.V. Generalised invariant Subspace based Method for Steady State Analysis of QBD-M Proceses // Periodica Polytechnica. -2000. Vol.44. - pp. 159-178.

115. Vegesna S. IP quality of service. Indianapolis, Ind.: Cisco, 2001. - 343p.

116. Vishnevskiy V.M. Algorithms optimisation queueing networks and application for computer networks // Proceedings of International symposium Teletraffic theory and computer simulation. Sofia: 1988. -pp.345-358.

117. Vogel R.e.a. QoS Based Routing of Multimedia Streams in Computer Networks // IEEE Journal on Selected Areas in Communications. 1996. -V.14, no.7. - pp. 1235-1244.

118. White R., McPherson D., Srihari S. Practical BGP. Boston: Addison-Wesley, 2005. - 434p.

119. Wisniewski J.A., Sameh A. Parallel algorithms for network routing problems and recurrences. Urbana, 111.: Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1979. - 34 p.

120. Wu T.-H. Fiber network service survivability. Boston: Artech House, 1992. - 459p.

121. Xu J. Topological structure and analysis of interconnection networks. -Dordrecht: Kluwer Academic Publishers, 2001. 342p.

122. Zhang R., Bartell M. BGP design and implementation. Indianapolis, Ind.: Cisco Press, 2004. - 638p.

123. Главный конструктор СЦПС «Спектр»1. А. Молдовян1. ЧЛЕНЫ КОМИССИИ:

124. Начальник НИО СЦПС «Спектр»

125. Настоящий акт составлен в том, что следующие результаты диссертационной работы Ю.К. Гликмана приняты к внедрению в ОАО «Телекомпания Санкт-Петербургское кабельное телевидение»:

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

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

128. Программное обеспечение для анализа топологий компьютерных сетей;

129. Указанные результаты диссертационной работы Гликмана Ю.К. с успехом используются в ОАО «Телекомпания Санкт-Петербургское кабельное телевидение» при проведении работ по проектированию новых и по анализу существующих каналов связи.

130. Директор по эксплуатации ОАО <1. К.Н.Рахимов

131. Fraunhofer|nstjtutfQr0ffene1. Kommunikationssysteme

132. Fraunhofer FOKUS Kaiserin-Augusta-Allee 31 10589 Berlin2308.2004, Berlin1. STATEMENT

133. After using Yuri Glickman's thesis:

134. Elaboration of method and algorithms of multipath routing for improving the resilience in IP networks"

135. The FOKUS-TIP KING committee, formed by Dr. Peter Deussen, Eng. Ranganai Chaparadza and Eng. Justyna Zander-Nowicka considered the presented materials and decided, that:

136. The main features of the thesis were used during the scientific project "KING -Key Components for the Mobile Internet of Next Generation" in 2002-2004 years.

137. The presented in the theses pattern based algorithms achieve full node protection in topologies where this is theoretically feasible and they are well suited for link weight optimization.

138. The created software is well suited for computation and analysis of routing graphs.

139. The proposed method, algorithms and software allow to significantly improve the resilience in IP networks.1. Committee chairman,1. Dr. Peter Deussen1. Committee members:1. Ranganai Chaparadza1. Justyna Zander-Nowicka

140. Fraunhofer-Gesellschaft zur FSrderung der angewandten Forschung e.V. HansastraBe 27c 80686 Munchen

141. Bankverbindung: Deutsche Bank, MOnchen Konto 75 21 933 BLZ 700 700 10

142. Vorstand der Fraunhofer-Gesellschaft Prof. Dr. Hans-JOrg Bullinger, President

143. Dr. rer. pol. Alfred Gossner Dr. jur. Dirk-Meints Polter Prof. Dr. Dennis Tsichritzis

144. Fraunhofer Institut fur Offer>« Kommunikationssysteme FOKUS

145. Kaiserin-Augusta-Allee 31 10589 Berlin

146. Tel [phone] Fax [phone]. FOKUS Institutsleitung1.stitute leiter

147. Univ.-Prof. Dr.-lng.habil. Prof.e.h. Dr.h.c. Radu Popescu-Zeletin Stellvertretender Institutsleiter Dipl.-lng. Berthold Butscher