Введение
1. Модели и методы обеспечения отказоустойчивости в виртуальных частных сетях 14
1.1. Основы технологии VPN 14
1.1.1. Понятие технологии VPN 14
1.1.2. Классификация VPN 16
1.1.3. Особенности BGP/MPLS VPN 26
1.2. Модели VPN в аспекте QoS 29
1.2.1. Проблема обеспечения качества обслуживания в VPN 29
1.2.2. Канальная модель 31
1.2.3. Потоковая модель 32
1.3. Проблема обеспечения отказоустойчивости VPN 38
1.3.1. Введение в проблему и классическая постановка задачи 38
1.3.2. Стратегии обеспечения отказоустойчивости 41
1.4. Обзор моделей и методов расчета отказоустойчивых VPN 44
1.5. Выводы 48
2. Графовая модель отказоустойчивой виртуальной частной сети ... 51
2.1. Описание модели отказоустойчивой VPN 5!
2.2. Формальная постановка задачи 58
2.3. Задача оптимальной пополнения графа 59
2.4. Алгоритм минимальной пополнения Куллера-Туримеллы 63
2.5. Функции стоимости для пополнения 65
2.6. Выводы 67
3. Разработка аппроксимационных алгоритмов решения задачи обеспечения отказоустойчивости VPN 69
З.1. Приближенный алгоритм Италиано-Растоги для симметричной модели VPN 69
З.1.1. Суть алгоритма Италиано-Растоги 69
3.1.2. Недостатки алгоритма 72
3.2. Улучшение и модификация алгоритма 73
3.2.1. Уменьшение коэффициента аппроксимации алгоритма 73
3.2.2. Преобразование пополнений А" в А 76
3.2.3. Распределение полосы пропускания на ребрах дерева Г 76
3.2.4. Учет в функции стоимости пополнения ребер дерева Т 78
3.3. Алгоритмы для симметричной модели VPN 79
3.4. Адаптация алгоритмов для асимметричной модели VPN 84
3.5. Примеры решения задач разработанными алгоритмами 91
3.5.1.. Пример расчета для симметричной модели VPN 91
3.5.2. Пример расчета для асимметричной модели VPN 95
3.6. Характеристики алгоритмов 99
3.7. Выводы 101
4. Реализация и исследование разработанных алгоритмов 103
4.1. Особенности реализации разработанных алгоритмов 103
4.2. Исследование алгоритмов для симметричной модели 112
4.3. Исследование алгоритмов для асимметричной модели 117
4.4. Выводы 124
Заключение 125
Литература
