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

• Автор: Гликман, Юрий Константинович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 122 с. : ил.

Содержание
Введение .

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

современных 1Р сетях.

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

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

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

1.3.1. Протокол маршрутизации К1Р

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

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

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

1.4.2. Алгоритм Суурбалле для поиска пары кратчайших независимых по рбрам путей.
1.4.3. Алгоритм Суурбалле для поиска пары кратчайших независимых по вершинам путей.
1.4.4. Алгоритм многопутевой маршрутизации Шольмайера.
1.4.5. Алгоритм многопутевой маршрутизации Райхерта.
1.5. Основные типы сбоев в компьютерных сетях
1.6. Недостатки существующей 1Р маршрутизации
1.7. Постановка задачи.
1.8. Выводы по первой главе
Глава 2. Г рафы маршрутизации
2.1. Моделирование маршрутизации на основе теории графов.
2.2. Метод многопутевой маршрутизации.
2.3. Свойства топологий сетей совместимых с многопутевой маршрутизацией
2.4. Алгоритм проверки совместимости топологий сетей с многопутевой маршрутизацией.
2.5. Алгоритм построения совместимых топологий сетей.
2.6. Выводы по второй главе.
Глава 3. Алгоритмы многопутевой маршрутизации.
3.1. Требования к алгоритмам маршрутизации.
3.2. Алгоритм построения графов многопутевой маршрутизации на основе пошагового улучшения
3.3. Шаблонный подход построения многопутевой маршрутизации
3.3.1. Алгоритм построения графов многопутевой маршрутизации на основе четырх шаблонов.
3.3.2. Алгоритм построения графов многопутевой маршрутизации на основе шести шаблонов.
3.4. Сравнение алгоритмов.
3.5. Выводы по третьей главе
Глава 4. Пути практической реализации многопутевой
маршрутизации
4.1. Реализация механизма работы соединенийджокеров
4.2. Пакет программ для расчта и анализа графов маршрутизации.
4.2.1. Программа для расчта графов многопутевой маршрутизации.
4.2.2. Программа для анализа графов многопутевой маршрутизации и топологий сетей.
4.2.3. Программа для построения топологий сетей, совместимых с многопутевой маршрутизацией
4.3. Выводы по четвртой главе.
Заключение
Список литературы


В случае отказа одного из сетевых элементов передача информации не будет приостановлена, что особенно важно для сетевых служб, работающих в режиме реального времени, как например Интернет-телефония (VoIP). Представленные алгоритмы могут заменить собой алгоритм поиска кратчайшего пути (алгоритм Дейкстры) в протоколах внутридоменной маршрутизации с учётом состояния канала. Для оценки совместимости имеющихся сетей с многопутевой маршрутизацией могут быть использованы разработанные в диссертации геометрические критерии и основанный на них алгоритм проверки. Для построения же новых компьютерных сетей, совместимых с многопутевой маршрутизацией, может быть использован алгоритм построения совместимых сетей, представленный в данной работе. Реализация результатов работы. Данный пакет программ применяется СЦПС «Спектр», а также фирмой ОАО «Телекомпания Санкт-Петербургское кабельное телевидение», при проектировании новых и для анализа существующих каналов связи. Разработанные алгоритмы многопутевой маршрутизации были использованы Фраунхоферским институтом Открытых телекоммуникационных Систем Фокус в проекте KING, посвящённом разработке компьютерных сетей следующего поколения. Разработанный метод многопутевой маршрутизации был оформлен в виде патентного предложения. Апробации работы. Приведенные в диссертации результаты были представлены на VIII Санкт-Петербургской международной конференции "Региональная информатика " (Санкт-Петербург, - ноября ), на III Санкт-Петербургской конференции «Информационная безопасность регионов России (ИБРР-)» (Санкт-Петербург, - ноября ), на « IEEE Workshop on High Performance Switching and Routing» (Турин, Италия, - июня, ) и на «IPS-MoMe » (Варшава, Польша, - марта ). Публикации. Основные результаты диссертации опубликованы в 5 печатных работах. Структура и объем работы. Диссертация содержит введение, четыре главы, заключение, список литературы (4 наименований); таблиц и рисунок (общий объем диссертации — 9 листов). Глава 1. Методы, протоколы и алгоритмы маршрутизации в современных 1Р сетях. С точки зрения маршрутизации Интернет состоит из большого количества автономных систем (АБ), которые представляют собой логически ограниченные области. Каждая автономная система управляется своей организацией и может использовать внутри свой алгоритм маршрутизации или несколько различных алгоритмов маршрутизации. Совокупность маршрутизаторов и сетей, использующих один и тот же алгоритм маршрутизации, называется доменом маршрутизации. Таким образом, автономная система может состоять из одного или нескольких доменов маршрутизации (Рис. Однако чёткого различия между этими понятиями нет, и их часто применяют взаимозаменяемо []. Рис. Exterior). Протоколы, обеспечивающие маршрутизацию внутри автономной системы, называются протоколами внутреннего шлюза или внутридоменными (ЮР - Interior Gateway Protocol), а протоколы, обеспечивающие маршрутизацию между различными автономными системами, называются протоколами внешнего шлюза (Exterior Gateway Protocol) []. Внутри корпоративной сети могут одновременно функционировать несколько протоколов внутреннего шлюза, отслеживающих маршруты к подсетям в пределах автономной системы. Маршрутизаторы, поддерживающие один и тот же протокол внутреннего шлюза, обмениваются информацией друг с другом в пределах одного домена маршрутизации. На границе доменов маршрутизации или автономных систем располагаются так называемые граничные маршрутизаторы (Border router). Они поддерживают несколько протоколов маршрутизации с целью обеспечения соединения доменов маршрутизации или автономных систем. Так на Рис. R1, который соединяет два домена маршрутизации внутри одной автономной системы, и маршрутизаторы R2 и R3, являющиеся граничными маршрутизаторами автономных систем AS1 и AS2 соответственно. Граничные маршрутизаторы различных автономных систем поддерживают, во-первых, какой-либо протокол внутреннего шлюза через интерфейсы внутри своей «родной» автономной системы, и, во-вторых, какой-либо протокол внешнего шлюза через внешние интерфейсы, соединяющие собственную AS с удалённой AS. Протоколы внешнего шлюза распознают только автономные системы в иерархии маршрутизации и игнорируют протоколы внутреннего шлюза.