Содержание к диссертации
Введение
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
Литература
- Классификация VPN
- Алгоритм минимальной пополнения Куллера-Туримеллы
- Суть алгоритма Италиано-Растоги
- Исследование алгоритмов для симметричной модели
Введение к работе
Актуальность темы
В последние десятилетия компьютерная техника и информационные технологии настолько глубоко проникли во все сферы человеческой деятельности, что сейчас любая организация, число офисов которой превышает хотя бы два, просто не представляет своей работы без объединения своих информационных и вычислительных ресурсов в единую сеть.
Поскольку строительство и эксплуатация собственной сети связи - занятие весьма дорогое, на рынке телекоммуникационных услуг появилось решение в виде технологии и услуги виртуальной частной сети VPN (Virtual Private Network). Технология VPN обязана имитировать два основополагающих свойства частной сети - гарантированные безопасность и качество обслуживания. Вследствие повсеместного использования стека протоколов TCP/IP среди услуг VPN стали доминировать услуги виртуальных сетей на базе протокола IP - так называемые IP VPN, которые унаследовали традиционные для сетей IP проблемы с качеством обслуживания QoS (Quality of Service). Однако с появлением различных технологий и протоколов, призванных решить проблему гарантированного QoS, среди которых лидирующее положение по праву занимает технология мультипротокольной коммутации по меткам MPLS, услуга IP VPN стала широко востребованной.
Разработка и внедрение таких технологий привело к всплеску научных публикаций по проблематике исследования VPN, удовлетворяющих заданным показателям качества обслуживания. При этом в качестве таких показателей наиболее часто используется гарантированная полоса пропускания и значительно реже рассматриваются задержки или живучесть. Среди зарубежных ученых, изучающих данную проблему, стоит особо выделить A.Kumar, Л. Gupta, N.G. Duffield, R.Rastogi, B.Yener, G.F. Italiano, Y.L. Liu, Y.S. Sun и др. Все эти авторы занимаются исследованиями потоковой модели VPN, предложенной несколько лет назад в противовес традиционной, так на-
8 зываемой канальной модели VPN, основанной на полной матрице трафика. Канальная и потоковая модели используются в задачах определения оптимальной топологии VPN. Потоковая модель характеризуется в первую очередь эффективностью использования полосы пропускания, гибкостью в передаче трафика, простотой и удобством спецификации требований пользователей. В России исследованиями VPN и смежных с ними проблем занимаются Б.С. Гольдштейн, А.В. Росляков, В.Г. Олифер, Н.А. Олифер и др. Стоит уточнить, что задача построения оптимальной топологии VPN на основе потоковой модели является весьма сложной, а некоторые ее разновидности и вовсе относятся к классам NP-сложных или NP-полных задач.
Несмотря на повышенный интерес к проблеме исследования VPN, ряд теоретических задач так и не решен. Так одной из важнейших проблем является защита трафика VPN от отказов каналов и узлов сети, которая особенно актуальна для наиболее часто используемой разновидности топологии потоковой модели в виде дерева. Даже для относительно простой модели с симметричным трафиком не найден эффективный полиномиальный алгоритм, позволяющий строить отказоустойчивые VPN с гарантированной полосой пропускания. Имеющиеся работы по данной тематике имеют проблемы либо с эффективностью, либо с масштабируемостью. Наиболее же актуальны исследования асимметричной модели VPN, обусловленной использованием на практике технологий асимметричного доступа (ADSL, ADSL2, ADSL2+) и таких услуг, как ftp и web сервисы, Интернет-радио, IPTV, Video On Demand и др., однако сведения о подобных исследованиях в печати отсутствуют.
Объектом исследования являются виртуальные частные сети, организуемые операторами связи.
Предмет исследования является полоса пропускания, которую необходимо дополнительно выделить в сети общего пользования для гарантированной защиты трафика VPN от отказов каналов сети
9 Цель работы и задачи исследования
Цель диссертации состоит в разработке и исследовании графовых моделей VPN, обеспечивающих определение топологий отказоустойчивых VPN, оптимальных с точки зрения минимизации занимаемой дополнительной полосы пропускания в сети.
Поставленная цель определила необходимость решения следующего ряда задач:
анализ существующих моделей и методов решения задачи обеспечения отказоустойчивости VPN;
разработка формализованного математического описания исследуемого объекта- отказоустойчивой VPN на основе потоковой модели;
разработка способа определения величины необходимой защитной полосы пропускания для различных стратегий защиты;
разработка алгоритмов определения оптимальных топологий отказоустойчивых VPN на основе симметричной и асимметричной моделей и различных стратегий защиты;
проведение компьютерных экспериментов с разработанными и известными алгоритмами применительно к сетям различных размеров и топологий.
Методы исследования
Для решения задач диссертационной работы используются методы теории связи, теории графов, теории алгоритмов и теории вычислительной сложности.
Достоверность результатов
Достоверность результатов подтверждается корректной постановкой задачи, применением строгого математического аппарата, а также сравнением известных результатов с результатами, полученными в данной работе.
10 Научная новизна
Научная новизна диссертационной работы заключается в следующем:
разработана графовая модель отказоустойчивой виртуальной частной сети с топологией дерева, учитывающая асимметрию трафика конечных точек VPN;
разработан способ определения величины дополнительной полосы пропускания на защитных ребрах и ребрах дерева VPN для стратегий защиты звена и защиты пути;
разработаны полиномиальные алгоритмы определения оптимальных топологий отказоустойчивых VPN на основе симметричной модели VPN и, что наиболее важно, асимметричной модели VPN для стратегий защиты звена и защиты пути.
Личный вклад
Все результаты, составляющие содержание диссертационной работы, получены автором самостоятельно.
Практическая ценность и реализация результатов работы
Применением полученных в диссертационной работе моделей и алгоритмов достигается повышение отказоустойчивости VPN и сокращение полосы пропускания, необходимой для обеспечения этой отказоустойчивости, что выгодно и провайдерам и потребителям услуг VPN.
Полученные результаты и алгоритмы могут быть использованы научно-исследовательскими, проектными и эксплуатационными организациями при проектировании, внедрении или усовершенствования услуг VPN на сетях операторов связи и Интернет провайдеров.
Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в Группе компаний «СТАРТ» и вне-
дрены в учебный процесс ГОУВПО ПГАТИ, что подтверждено соответствующими актами.
Апробация работы
Основное содержание работы докладывалось и обсуждалось на V Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки» (Самара, 2004), V Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2004), XII Российской НТК ПГАТИ (Самара, 2005), XIII Российской НТК ПГАТИ (Самара, 2006), VII Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2006), XIV Российской научной конференции ПГЛТИ (Самара, февраль 2007).
Публикации
По теме диссертации опубликовано 19 работ, в том числе 3 статьи в журналах из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 15 тезисов и текстов докладов, а также 1 свидетельство о регистрации алгоритмов и программ.
Основные положения, выносимые на защиту
графовая модель отказоустойчивой виртуальной частной сети с топологией дерева, учитывающая асимметрию трафика конечных точек VPN;
способ определения величины дополнительной полосы пропускания на защитных ребрах и ребрах дерева VPN для стратегий защиты звена и защиты пути;
полиномиальные алгоритмы определения оптимальной топологии отказоустойчивых VPN на основе симметричной и асимметричной моделей VPN для стратегий защиты звена и защиты пути.
Структура и объем работы
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 143 страницы машинописного текста, 47 рисунков и 7 таблиц. Список литературы включает в себя 135 наименований.
В первой главе дано понятие и сделан общий технологии VPN, рассмотрены возможные типы услуг и различные схемы поддержки VPN, перечислены и проанализированы соответствующие протоколы с позиции эволюции технологии и их отношения протоколов к уровню модели OSI. Также рассмотрены канальная и потоковая модели обеспечения QoS в VPN, указаны основные преимущества потоковой модели VPN над канальной моделью. Приведена классификация потоковых моделей и дан краткий обзор теоретических работ по проблематике расчета VPN на основе потоковой модели.
Показано, что наиболее распространенная и легко реализуемая топология VPN для потоковой модели - дерево, является уязвимой для отказов сетевых звеньев VPN. Далее проанализированы предложенные в литературе стратегии зашиты от одиночных отказов, дана их сравнительная оценка, и приведена обобщенная постановка задачи обеспечения отказоустойчивости VPN. Анализ рассмотренных в первой главе работ по данной тематике позволяет сделать выводы о том, что существующие модели и методы расчета отказоустойчивых VPN не всегда адекватны, поскольку, во-первых, не учитывают специфику асимметричного трафика, во-вторых, даже для симметричной модели не всегда эффективны и, в-третьих, даже для симметричной модели зачастую неполиномиальны.
Во второй главе представлена математическая модель отказоустойчивой VPN с древовидной топологией, учитывающая асимметрию трафика конечных точек и допускающая возможность одиночных отказов. Представлены выражения, позволяющие рассчитать величину дополнительной полосы
13 пропускания на звеньях сети, необходимую для обеспечения отказоустойчивости. Сделана строгая математическая формулировка задачи обеспечения отказоустойчивости VPN для представленной модели, показано близкое сходство данной задачи с задачей оптимального пополнения графа, которая относится к классу NP-complete.
В третьей главе разработаны приближенные алгоритмы расчета отказоустойчивых VPN для симметричной и асимметричной древовидной потоковой модели. Разработанные алгоритмы применимы как к стратегии защиты звена, так и к стратегии защиты пути, имеют полиномиальное время выполнения, оцениваемое величиной 0(VE + V2\ogV). Самое же главное достоинство алгоритмов в том, что они учитывают особенности асимметричной модели. Работа алгоритмов проиллюстрирована на соответствующих примерах.
В четвертой главе отражены некоторые особенности программной реализации разработанных алгоритмов и приведены результаты численных экспериментов над известными и разработанными в диссертации алгоритмами для сетей различного размера и топологий в зависимости от количества конечных точек VPN и их требований к полосе пропускания. Сравнение полученных результатов, позволяет сделать вывод, что применением разработанных алгоритмов для расчета VPN достигается ощутимая экономия суммарной полосы пропускания VPN при гарантированной защите от одиночных отказов.
В заключении обобщены выводы, сделанные по результатам каждой главы диссертации, и в тезисном виде изложены основные научные и практические результаты диссертационного исследования.
В приложении содержатся акты внедрения результатов диссертации.
1. МОДЕЛИ И МЕТОДЫ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ В ВИРТУАЛЬНЫХ ЧАСТНЫХ СЕТЯХ
Классификация VPN
В век информационных технологий для любой организации вполне естественно и даже необходимо объединение всех территориально разнесенных коммуникационных и вычислительных ресурсов в единую сеть. Понятно, что построить и эксплуатировать собственную сеть под силу только крупным и богатым фирмам, причем, построив собственную сеть, такие организации нередко начинают выступать на рынке инфокоммуникационных услуг в роли самостоятельного игрока. Что делать остальным? Спрос рождает предложение, и именно поэтому уже не первый год существует и развивается технология виртуальных частных сетей (Virtual Private Network, VPN), на базе, которой операторы связи предлагают одноименную услугу.
Индустрия инфокоммуникаций развивается настолько быстро и стремительно, что технология, которая на текущий момент смотрится весьма привлекательно, завтра сменяется двумя еще лучшими, поэтому зачастую терминология не успевает устояться. Вот и для VPN нет единственного и общепринятого определения.
К примеру, в [1] дано следующее понятие VPN. VPN - это объединение удаленных локальных сетей или отдельных рабочих мест с использованием специальных аппаратных или программных устройств, осуществляющих информационную защиту транзитного трафика и его туннелирование поверх публичных сетей с пакетной передачей информации. Можно привести и другое определение [2]. VPN - это технология позволяющая средствами разделяемой несколькими предприятиями сетевой инфраструктуры реализовать сервисы, по каче ству (безопасность, доступность, предсказуемая пропускная способность, независимость в выборе адресов) приближенные к сервисам частной (private) сети.
В целом же, под аббревиатурой VPN скрывается множество достаточно различающихся сетевых технологий и протоколов, одним из предназначений которых является предоставление сервиса, близкого к услугам частных сетей. Для пользователя, объединяющего свои сети с помощью услуги/технологии VPN, это объединение выглядит как единолично им используемая частная сеть. Пример такой VPN, объединяющей на основе разделяемой сетевой инфраструктуры сети двух офисов, показан на рис. 1.1. Данная VPN также позволяет осуществлять доступ к корпоративным ресурсам с компьютеров удаленных пользователей.
В силу того, что абсолютно вся сетевая инфраструктура частной сети находится в единоличной собственности одного владельца, ее наиважнейшей характеристикой является изолированность. Вследствие этого частной сети присущи два основных свойства: 1. Максимально возможная безопасность информационного обмена. 2. Предсказуемая производительность сети (поддержка показателей качества обслуживания (Quality of Service, QoS), таких как скорость передачи, задержка, джиттер, процент потерь на заданном уровне).
От VPN требуется качественная имитация именно этих свойств, а поскольку в качестве транспорта VPN по определению использует сети общего пользования (Интернет или сети провайдеров), то данная задача весьма нетривиальна. Кроме того, ясно, что качество реализации безопасности и качества обслуживания может весьма отличаться от технологии к технологии.
В сетях современных компаний стандартом де-факто стало использование стека протоколов TCP/IP (Transmission Control Protocol/Internet Protocol), поэтому неудивительно, что наибольшее распространение получили сети VPN на основе протокола IP, которые в литературе называют IP VPN.
Подавляїощая масса публикаций по IP VPN посвящена технологическим и протокольным аспектам VPN [3 - 33], вопросы качества обслуживания практически не затрагиваются. Это и неудивительно, поскольку до недавнего времени трудно было ожидать о сетей IP качества отличного от стандартного «по возможности». Однако появление таких технологий как IntServ, DiffServ [2,4] и в первую очередь MPLS [2,4,6- 12] изменило обстоятельства в лучшую сторону.
В литературе, как отечественной, так и зарубежной, приведено огромное количество вариантов классификации VPN [1,2,4,5]. Ограничимся рассмотрением только наиболее значимых классификаций, позволяющих глубже понять проблематику VPN.
Так одной из самых распространенных является классификация по типу услуг, предоставляемых VPN [1,2,4.5,30,33]. На базе технологии VPN могут быть реализованы три основных вида услуг: 1. VPN с удаленным доступом (Remote Access VPN). 2. Внутрикорпоративная (интранет) VPN (Intranet VPN). 3. Межкорпоративная (экстранет) VPN (Extranet VPN).
Виртуальная частная сеть с удаленным доступом (рис. 1.2) позволя ет реализовать защищенное взаимодействие между сегментом корпоратив ной сети (центральным офисом или филиалом компании) и удаленным пользователем, который подключается к корпоративным ресурсам из дома (надомный пользователь) или через переносной компьютер (мобильный пользователь). Удаленный пользователь, как правило, не имеет статического IP-адреса и подключается к защищаемому ресурсу не через выделенное устройство VPN, а напрямую с собственного компьютера, где и устанавливается программное обеспечение, реализующее функции клиента VPN.
Алгоритм минимальной пополнения Куллера-Туримеллы
Лучшим алгоритмом решения задачи минимального пополнения для случая к = 2 является алгоритм Куллера-Туримеллы (Khullerhurimella) [109,110] с коэффициентом аппроксимации 2 и временной сложностью 0(E + VlogV).
Перед рассмотрением алгоритма необходимо дать некоторые определения.
В ориентированном дереве с выделенным корнем г глубиной вершины и называется расстояние в дереве от корня г до этой вершины и (т.е. длина единственного пути от корня г до этой вершины и).
Рассмотрим путь в дереве от корня до какого-либо листа дерева и две любые вершины и и v этого пути. Если глубина вершины и больше глубины вершины v, то вершина v называется предком для вершины w, или родительской вершиной для вершины и.
Наименьшим общим предком вершин и и v называется общая вершина наибольшей глубины lca(u,v) в путях к этим вершинам из корня дерева.
Ветвлением называется ацикличный подграф ориентированного графа, содержащий все его вершины и удовлетворяющий условию: каждая вершина ветвления имеет не более одного входящего ребра. Более подробно понятие ветвления и алгоритмы поиска минимального ветвления будут рассмотрены в следующей главе.
Алгоритм Куллера-Туримелы решает задачу минимального пополнения для подграфа G czG, представляющего собой дерево. Если подграф G является несвязньш, то необходимо соединить связные компоненты G минимальным остовным деревом, чтобы получить новый связный подграф G .
Если подграф G (или С) содержат двухсвязные компоненты, то каждую такую компоненту можно стянуть в одну вершину и добавить в дерево Т эти вершины, ребра, связывающие эти вершины (т.е. мосты графа С), а также те вершины и ребра G , которые не входят в двухсвязные компоненты. Тогда алгоритм пополнения дерева Т включает в себя следующие шаги: Шаг 1. Построение ориентированного граф GD(V,ED). Шаг 1.1. Выберем произвольный лист дерева Т в качестве корня дерева г и направить все ребра дерева в направлении к корню г. Обозначим полученное дерево как Г. Шаг 1.2. Добавим в граф GD ребра дерева Г и обнулим вес этих ребер. Шаг 1.3. Рассмотрим ребро (w,v) графа G. Если это обратное ребро (т.е. вершина и является предком вершины v в дереве Г), то в граф GD добавляется ориентированное ребро (w,v) с весом w(w,v). Если это перекрестное ребро (т.е. ни и, ни v не являются предками друг друга), то в граф GD добавляются два ориентированных ребра {lca{u,v\u) и (/ca(w,v),v) с весом w(u,v). Здесь lca(u,v) - наименьший общий предок вершин и и v в дереве Г. Шаг 2. Найдем ветвление минимальной стоимости в графе GD с корнем г. Для каждого ориентированного ребра найденного ветвления eeGD -Т добавим соответствующее ребро (И,У)ЄС-Г в пополнение А дерева Т.
Так, к примеру, на рис.2.6 ребро (w,v) является обратным ребром, причем вершина v является предком для вершины и. В граф GD соответственно добавляется одно ориентированное ребро (v,w) с весом 2. . Пример построения графа GD Ребро (х9у) является перекрестным ребром и, поэтому в граф G добавляется два ориентированных ребра (а,х) и (а,у), где вершина а есть наименьший общий предок вершин и и V.
Можно отметить следующий весьма существенный недостаток алгоритма. При построении графа GD рассматриваются лишь те ребра графа G, конечные вершины которых принадлежат дереву Т. Если хотя бы одна конечная вершина ребра графа G не принадлежат дереву Г, такое ребро не учитывается, хотя оно также может использоваться при достроении дерева Т до двухсвязного графа. Примером таких ребер являются ребра (w,z) и (z,x) на рис.2.6.
Суть алгоритма Италиано-Растоги
Впервые подход, в основе которого лежит понятие оптимального пополнения графа, к решению задачи обеспечения отказоустойчивости для VPN потоковой модели был использован в работе Италиано (Italiano) и Рас-тоги (Rastogi) [67]. В данной работе был предложен аппроксимационный алгоритм, позволяющий обойти некоторые из обозначенных во второй главе ограничений присущих задаче оптимального пополнения и алгоритмам ее решения. В частности, алгоритмом Италиано-Растоги специфицируется функция стоимости ребер w(/):-»K+, позволяющая снять неопределенность веса ребер графа feG. Кроме того, разработчиками алгоритма учтена возможность включения в пополнение всех ребер графа feG, а не только ребер f = (x,y):feG9xeT,yeT (т.е. тех, вершины которых принадлежат дереву).
Однако, несмотря на это, алгоритму Италиано-Растоги присущ также ряд весьма принципиальных недостатков, детально которые будут разобраны ниже. Пока же остановимся на рассмотрении самого алгоритма.
Основная идея аппроксимационного алгоритма Италиано-Растоги заключается в следующем. Поиск оптимального пополнения дерева Т осуществляется не в графе G, а в новом графе G", который получается из исходного путем некоторых преобразований. Сначала граф G преобразуется в граф G . Все возможные пути между вершинами дерева Т в графе G —Т являются непересекающимися по ребрам, что снимает проблему разделяемых между несколькими защищаемыми ребрами защитных путей. Но по-прежнему затруднительно предсказать для какого множества P(f) ребро feG будет защитным. Поэтому далее граф G преобразуется в граф G", для которого уже весьма несложно определить стоимость каждого ребра /еС — Т и соответственно найти минимального пополнения. В итоге представленные преобразования дают коэффициент аппроксимации 16. Таким образом, алгоритм Италиаио-Растоги включает в себя следующие шаги. Шаг 1. Построение графа G ;G-+Gr с коэффициентом аппроксимации 8.
В граф С включаются все ребра и все вершины дерева Т. Кроме того, если между любыми двумя вершинами и и v дерева Т существует кратчайший путь в графе G, то в граф Gr добавляется ребро (w,v) . Вес этого ребра w(u,v) равен длине соответствующего кратчайшего пути. Шаг 2. Построение графа Gn:G - G" с коэффициентом аппроксимации 2. Шаг 2.1. Выбор корня г дерева Т. Рассмотрим два поддерева T(u9v) и T(v9u). Пусть B(w,v) - суммарная пропускная способность конечных точек VPN в дереве T(w,v), a B(v9u) - суммарная пропускная способность конечных точек VPN в дереве T(v9u). Иначе говоря: B(u,v)= b(i), (3.1) leQnT(utv) B(v,u)= J] ЦІ) (3.2) i QnT(v,u) Тогда, если B(u9v) B(v,u)9 то ребро (u9v) направляем от вершины и к вершине v. Если B(u,v) B(v,u), то ребро (w,v) направляем от вершины v к вершине м. В случае B(u9v) = B(v9u) ребро (w,v) направляем в сторону ближайшего листа дерева (т.е. в сторону ближайшей конечной точки VPN). Вершина, не имеющая входящих ребер, и есть корень дерева Т. Шаг 2.2. Поиск наименьших общих предков вершин. Для конечных вершин w и v каждого ребра f = (u9v)eG в ориентированном корневом дереве Т ищется наименьший общий предок lca{u9v). Шаг 2.3. Построение графа G". В граф G" включаются все ребра и все вершины дерева Г. Для каждого ребра (w,v) графа G рассмотрим по следовательность вершин дерева Г в пути от вершины и до lca(u9v): Щ=и9 u]9...,ur=lca(u,v). В граф G" добавляем ребра (uQiu{)9 (w0,w2),...,(w0,ww). Для различения такого ребра (u09uf) от возможного ребра (и0,и.) дерева Т будем обозначать его как (и09щ)". Стоимость каждого ребра (щ9щ)п равна произведению веса ребра (м,v) є G -Г на максимальное значение полосы пропускания, выделенной на ребрах (щ,и{)9 (щ9иг)9...9(и1А9щ) дерева Т. Если имеет место случай добавления параллельных ребер (щ9щ)"\ то из них выбирается ребро с минимальной стоимостью. Заметим, что фактически стоимость ребра (и09и{) это величина защитной полосы пропускания, которую необходимо выделить на этом ребре, если оно будет выбрано в качестве защитного ребра. Для последовательности вершин дерева Т в пути от вершины v до lca(u9v): v0 = v, v,,...,vn =lca(u9v) процедура аналогичная. Стоимость ребра (и щ) будем обозначать как Шаг 3. Поиск минимального пополнения А". Шаг 3.1. Все ребра дерева Т направляем в сторону его корня г, а их стоимость принимаем равной нулю. Шаг 3.2. Каждое ребро (w,v)ff графа G"-Т9 такое, что вершина и является предком для вершины v в ориентированном корневом дереве Г, направляем к вершине V. Шаг 3.3. Находим ветвление минимальной стоимости W с корнем в вершине г в ориентированном графе G". Ребра минимального ветвления feW и есть минимальное пополнение А" дерена Т в графе G".
Исследование алгоритмов для симметричной модели
Исследуем для начала эффективность алгоритмов для симметричной модели и случайно генерируемой сети со случайным расположением конченых точек VPN.
Сеть генерируется случайным образом и в среднем содержит 8 вершин и 20 ребер. Число конечных точек VPN, имеющих единичные требования к полосе пропускания, будем варьировать от 2 до 8.
Сведем результаты расчетов в таблицу 4.1. В таблицах примем следующие обозначения: - Алгоритм А - алгоритм Италиано-Растоги; - Алгоритм Б - алгоритм для симметричной модели, не распределяющий полосу пропускания на ребрах дерева (необходим для сравнения с алгоритмом Италиано-Растоги);
Результаты расчета для двухкольцевой сети По результатам расчетов можно сделать следующие выводы. Во-первых совершенно очевидно преимущество Алгоритма Б над алгоритмом А. Алгоритм А (Италиано-Растоги) определяет верхнюю оценку полосы пропускания, которую необходимо выделит на ребрах (7-7\ причем способ ее распределения по ребрам feG алгоритмом не специфицируется. Алгоритм Б представляет собой предложенную в диссертационной работе модификацию алгоритма Италиано-Растоги имеющую в качестве цели эффективное распределение полосы пропускания на ребрах feG. Как было показано в третьей главе теоретически алгоритм Б превосходит алгоритм А в два раза (коэффициенты аппроксимации 8 и 16 соответственно). Практически же, с ростом числа конечных точек, преимущество увеличивается в 1,5-2 раза. Таким образом, алгоритм Б, предложенный в диссертации, требует выделения полосы на ребрах feG в 2-4 раза меньше, нежели алгоритм Италиано-Растоги.
Тем не менее, ни один из этих алгоритмов не дает гарантированной защиты от отказов, поскольку не распределяет полосу пропускания на ребрах дерева Г, которая необходима как для стратегии защиты звена, так и для стратегии защиты пути. Вследствие этого, понятно что полоса пропускания требуемая алгоритмом В (защита звена) и алгоритмом Г (защита пути), будет превосходить требования алгоритма Б, поскольку алгоритмы В и Г являются дальнейшим развитием алгоритма Б. Однако, эти алгоритмы дают 100% гарантию защиты от одиночных отказов ребер дерева Т.
На диаграммах видно, что для стратегии защиты пути требуется выделить приблизительно столько же полосы пропускания, сколько выделено для дерева, т.е. около 100% от полосы дерева Т. В свою очередь, стратегия защиты звена требует порядка 150-200%. Результат этот согласуется с результатами аналогичных исследований отказоустойчивости симметричной модели [70, 77], что только подтверждает корректность разработанных алгоритмов и правильность расчетов.
Небольшие флуктуации на диаграммах можно объяснить специфической топологией сетевого графа, а различным размещением конечных точек VPN на нем. Очевидно, что когда конечных точек относительно мало (по сравнению с размером сетевого графа), очень многое зависит от их взаимного расположения друг от друга.
Исследуем эффективность алгоритмов для асимметричной модели для сетей со случайным расположением конечных точек VPN, создаваемых генератором VPN, используемых в предыдущем разделе. При этом сравнение будем производить с соответствующей симметричной моделью. Это значит, что асимметричные требования конечной точки вида 2/3, где 2 - входящая полоса, а 3 - исходящая полоса, будем менять на соответствующие симметричные требования 3/3. Входящую и исходящую полосу конечных точек ограничим значений в 5 единиц полосы пропускания, само же значение полосы пропускания будет выбирать произвольно.
По диаграммам на рис. 4.8-4.9 видно, что стратегия защиты звена для асимметричной модели требует выделения 150-200% полосы пропускания от дерева VPN, а стратегия защиты пути порядка 100% от полосы дерева VPN, что вполне согласовывается с аналогичными данными для симметричной модели.
Экономия полосы пропускания от использования асимметричной, показанная в абсолютном выражении на рис. 4.10-4.11, лежит в пределах 20-35% для сети из 30 вершин и 70 ребер, и в пределах 10-35% для кольцевой сети, что достаточно ощутимо (рис. 4.12-4.13). Если суммировать полосу VPN и защитную полосу, то диапазон выигрыша полосы сужается и составляет 25-30% для случайно сети, и 12-25% для двухкольцевой сети.
Небольшие отклонения, наблюдаемые на диаграммах, можно объяснить плотностью расположения конечных точек VPN на сетевых графах. Когда плотность, малая, то, как говорилось выше, многое зависит от взаимного расположения конечных точек. При высокой плотности VPN, т.е. когда число конечных точек стремится к числу вершин сетевого графа, число вероятных защитных путей уменьшается, а их загруженность возрастает.
В данной главе выполнена заключающая и, вместе с тем, одна из наиважнейших стадий процесса разработки алгоритмов - это программная реализация алгоритмов с использованием методов объектно-ориентированного программирования. Рассмотрен такой ключевой момент реализации, как представление в виде отдельных классов самого графа, дерева VPN и алгоритмов обработки графа, также рассмотрены некоторые важные детали реализации алгоритмов, позволяющие упростить их программирование.
Разработанные в диссертации алгоритмы реализованы в виде программного пакета, использованного при проведении численных экспериментов.
Результаты экспериментов позволяют сделать следующие выводы: - разработанные алгоритмы вполне работоспособны, и, что наиболее важно, корректны и справедливы, что подтверждается сравнением с известными результатами [70,77]; - сравнение с результатами работы других алгоритмов, в частности с алгоритмом Италиано-Растоги [67], показывает как минимум двукратное превосходство разработанных в диссертации алгоритмов; - для асимметричной модели применение разработанных алгоритмов позволяет получить экономию в 15-30% полосы пропускания по сравнению с соответствующей симметричной моделью.
