Введение
Глава 1. Методы, протоколы и алгоритмы маршрутизации в современных IP сетях 9
1.1. Архитектура сети Интернет 9
1.2. Основные метрики динамических протоколов маршрутизации 11
1.3. Протоколы маршрутизации внутреннего шлюза 13
1.3.1. Протокол маршрутизации RIP 15
1.3.2. Протокол маршрутизации OSPF 17
1.4. Современные алгоритмы маршрутизации 20
1.4.1. Алгоритм маршрутизации на основе алгоритма Дейкстры 20
1.4.2. Алгоритм Суурбалле для поиска пары кратчайших независимых по рёбрам путей 23
1.4.3. Алгоритм Суурбалле для поиска пары кратчайших независимых по вершинам путей 26
1.4.4. Алгоритм многопутевой маршрутизации Шольмайера 27
1.4.5. Алгоритм многопутевой маршрутизации Райхерта 28
1.5. Основные типы сбоев в компьютерных сетях 32
1.6. Недостатки существующей IP маршрутизации 35
1.7. Постановка задачи 37
1.8. Выводы по первой главе 37
Глава 2. Графы маршрутизации 39
2.1. Моделирование маршрутизации на основе теории графов 39
2.2. Метод 02 многопутевой маршрутизации 41
2.3. Свойства топологий сетей совместимых с 02 многопутевой маршрутизацией 47
2.4. Алгоритм проверки совместимости топологий сетей с 02 многопутевой маршрутизацией 55
2.5. Алгоритм построения 02 совместимых топологий сетей 58
2.6. Выводы по второй главе 59
Глава 3. Алгоритмы многопутевой маршрутизации 60
3.1. Требования к 02 алгоритмам маршрутизации 60
3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе пошагового улучшения 61
3.3. Шаблонный подход построения многопутевой маршрутизации .. 63
3.3.1. Алгоритм построения графов многопутевой (02) маршрутизации на основе четырёх шаблонов 67
3.3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе шести шаблонов 74
3.4. Сравнение алгоритмов 78
3.5. Выводы по третьей главе 95
Глава 4. Пути практической реализации 02 многопутевой маршрутизации 97
4.1. Реализация механизма работы соединений-джокеров 98
4.2. Пакет программ для расчёта и анализа графов маршрутизации. 101
4.2.1. Программа для расчёта графов многопутевой маршрутизации 101
4.2.2. Программа для анализа графов многопутевой маршрутизации и топологий сетей 103
4.2.3. Программа для построения топологий сетей, совместимых с 02 многопутевой маршрутизацией 105
4.3. Выводы по четвёртой главе 106
Заключение 107
Список литературы 109
