автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Исследование и разработка графовых моделей отказоустойчивых виртуальных частных сетей

На правах рукописи

НУШТАЕВ Андрей Васильевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ГРАФОВЫХ МОДЕЛЕЙ ОТКАЗОУСТОЙЧИВЫХ ВИРТУАЛЬНЫХ ЧАСТНЫХ СЕТЕЙ

Специальность 05 12.13 -«Системы, сети и устройства телекоммуникаций»

АВТОРЕФЕРАТ , диссертации на соискание ученой с] кандидата технических наук

J

Самара 2007

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Поволжская Государственная Академия Телекоммуникаций и Информатики» (ГОУВПО ПГАТИ)

Научный руководитель кандидат технических наук

доцент Росляков А В

Официальные оппоненты доктор технических наук

профессор Тарасов В Н

кандидат технических наук доцент Дубина С М

Ведущая организация ГОУВПО «Самарский

Государственный Университет»

Защита диссертации состоится «16» ноября 2007 г в 14-00 на заседании диссертационного совета Д219 003 02 при Поволжской Государственной Академии Телекоммуникаций и Информатики по адресу: 443010, Самара, ул. Л.Толстого, 23

С диссертацией можно ознакомиться в библиотеке ГОУВПО ПГАТИ Автореферат разослан «12» октября 2007 г

Ученый секретарь

диссертационного совета Д219 003 02 доктор технических наук, доцент

Мишин Д В

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Поскольку строительство и эксплуатация собственной сети связи - занятие весьма дорогое, на рынке телекоммуникационных услуг появилось решение в виде технологии и услуги виртуальной частной сети VPN (Virtual Private Network) Технология VPN обязана имитировать два основополагающих свойства частной сети - гарантированные безопасность и качество обслуживания Вследствие повсеместного использования стека протоколов TCP/IP среди услуг VPN стали доминировать услуги виртуальных сетей на базе протокола IP - так называемые IP VPN, которые унаследовали традиционные для сетей IP проблемы с качеством обслуживания QoS (Quality of Service) Однако с появлением различных технологий и протоколов, призванных решить проблему гарантированного QoS, среди которых лидирующее положение по праву занимает технология мультипротокольной коммутации по меткам MPLS, услуга IP VPN стала широко востребованной

Разработка и внедрение таких технологий привело к всплеску научных публикаций по проблематике исследования VPN, удовлетворяющих заданным показателям качества обслуживания При этом в качестве таких показателей наиболее часто используется гарантированная полоса пропускания и значительно реже рассматриваются задержки или живучесть Среди зарубежных ученых, изучающих данную проблему, стоит особо выделить A Kumar, A Gupta, N G Duffíeld, R Rastogi, В Yener, G F Italiano, Y L Lrn, Y S Sun и др Все эти авторы занимаются исследованиями потоковой модели VPN, предложенной несколько лет назад в противовес традиционной, так называемой канальной модели VPN, основанной на полной матрице трафика Канальная и потоковая модели используются в задачах определения оптимальной топологии VPN Потоковая модель характеризуется в первую очередь эффективностью использования полосы пропускания, гибкостью в передаче трафика, простотой и удобством спецификации требований пользователей В России исследованиями VPN и смежных с ними проблем занимаются Б С Гольдштейн, А В Росляков, В Г Олифер, H А Олифер и др Стоит уточнить, что задача построения оптимальной топологии VPN на основе потоковой модели является весьма сложной, а некоторые ее разновидности и вовсе относятся к классам NP-сложных или NP-полных задач

Несмотря на повышенный интерес к проблеме исследования VPN, ряд теоретических задач так и не решен Так одной из важнейших проблем является защита трафика VPN от отказов каналов и узлов сети, которая особенно актуальна для наиболее часто используемой разновидности топологии потоковой модели в виде дерева Даже для относительно простой модели с сим-

метричным трафиком не найден эффективный полиномиальный алгоритм, позволяющий строить отказоустойчивые VPN с гарантированной полосой пропускания Имеющиеся алгоритмы по данной тематике имеют проблемы либо с эффективностью, либо с масштабируемостью Наиболее же актуальны исследования асимметричной модели VPN, обусловленной использованием на практике технологий асимметричного доступа (ADSL, ADSL2, ADSL2+) и таких услуг, как ftp и web сервисы, Интернет-радио, IPTV, Video On Demand и др , однако сведения о подобных исследованиях в печати отсутствуют Объектом исследования являются виртуальные частные сети Предметом исследования является полоса пропускания, которую необходимо дополнительно выделить в сети общего пользования для гарантированной защиты трафика VPN от отказов каналов сети

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

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

- анализ существующих моделей и методов решения задачи обеспечения отказоустойчивости VPN,

- разработка формализованного математического описания исследуемого объекта - отказоустойчивой VPN на основе потоковой модели,

- разработка способа определения величины необходимой защитной полосы пропускания для различных стратешй защиты,

- разработка алгоритмов определения оптимальных топологий отказоустойчивых VPN на основе симметричной и асимметричной моделей и различных стратегий защиты,

- проведение компьютерных экспериментов с разработанными и известными алгоритмами применительно к сетям различных размеров и топологий

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

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

Научная новизна. Научная новизна диссертационной работы заключается в следующем

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

- разработан способ определения величины дополнительной полосы пропускания на защитных ребрах и ребрах дерева VPN для стратегий защиты звена и защиты пути,

- разработаны полиномиальные алгоритмы определения оптимальных топологий отказоустойчивых VPN на основе симметричной модели VPN и, что наиболее важно, асимметричной модели VPN для стратегий защиты звена и защиты пути

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

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

Полученные результаты и алгоритмы могут быть использованы научно-исследовательскими, проектными и эксплуатационными организациями при проектировании, внедрении или усовершенствовании услуг VPN на сетях операторов связи и Интернет провайдеров

Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в Группе компаний «О APT» и внедрены в учебный процесс ГОУВПО ПГАТИ, что подтверждено соответствующими актами

Апробация работы. Основное содержание работы докладывалось и обсуждалось на 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 s VPN. Канальная модель подобна услуге выделенной линии и требует знания полной матрицы трафика между каждой парой конечных точек VPN. Для каждой такой пары провайдер организует в сети (рис. 1а) отдельный маршрут с гарантированной полосой пропускания (рис.1б). Для потоковой модели достаточно задать два вектора, элементы которых представляют собой значения максимальной скорости передачи трафика, который конечная точка может отправлять ко всем остальным конечным точкам (Вош) и получать от всех остальных конечных точек (Bin). Провайдер должен реализовать связность конечных точек (например, в виде дерева) и выделить необходимую полосу пропускания так, чтобы гарантированно обеспечить передачу любого трафика конечных точек, удовлетворяющего заданным векторам (рис. 1 в).

Рис.1. Топология сети провайдера (а), канальная (б) и потоковая (в) модели VPN В первой главе диссертации указаны преимущества потоковой модели над канальной, приведена классификация потоковых моделей и дан краткий обзор теоретических работ по проблематике определения оптимальной топологии VPN на основе потоковой модели. Также показано, что наиболее распространенная и легко реализуемая топология VPN на основе потоковой модели - дерево, является наиболее уязвимой для отказов сетевых звеньев VPN. Да-

6

т

лее проанализированы предложенные в литературе стратегии защиты от одиночных отказов, звеньев. VPN - стратегия защиты звена и стратегия защиты пути (рис.2), дана их сравнительная оценка, и приведена обобщенная постановка задачи обеспечения отказоустойчивости VPN.

На рис.2 приняты следующие обозначения: Рт для стратегии защиты звена есть маршрут, соединяющий вершины отказавшего ребра (u,v); Рт для стратегии защиты пути есть маршрут, соединяющий деревья Т(и, v) и T(v,u), на которые разбивается дерево VPN при отказе ребра (k,v) .

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

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

Модель формулируется следующим образом. Пусть имеется сеть общего пользования провайдера услуг VPN в виде неориентированного графа G(V,E), где V - множество вершин, соответствующих маршрутизаторам/коммутаторам сети, а Е - множество ребер, соответствующих каналам сети, связывающим эти маршрутизаторы. Будем считать, что каналы сети имеют достаточную полосу для пропуска трафика VPN. Пусть задано множество конечных точек VPN Q с V и два вектора Bin и Воц1 размера |0|, элементы которых bm{u)e В;„ и ЬМЫ) е Вм представляют собой верхнюю границу скорости передачи трафика, который конечная точка и е Q может получать от всех остальных конечных точек или отправлять ко всем остальным конечным точкам соответственно.

Пусть на графе G задана виртуальная частная сеть в виде дерева Т(Е' У), т.е. £"' и V' с V . На каждом ребре дерева (a,v)eT выделена необходимая полоса пропускания Ь(и,\>) в направлении от вершины и к вершине v и

Рис.2. Стратегии защиты звена (а) и защиты пути (б)

полоса пропускания b(v,u) в направлении от вершины v к вершине и Будем называть ребра дерева (u,v) е Т защищаемыми ребрагли, а выделенную на них полосу - защищаемой полосой пропускания

Будем считать, что одновременно может произойти отказ только одного ребра дерева ееТ, и что работоспособность этого ребра е будет восстановлена до отказа следующего ребра

Рассмотрим некоторый путь рш между вершинами иеТ и vеТ, который проходит вне дерева Т , те путь е G - Г Очевидно, что при добавлении этого пути к дереву Т, получим граф, содержащий один единственный цикл аю При удалении любого ребра ееТпстт из графа Т + рт мы получим новое дерево Т-е + рт, по которому может передаваться трафик конечных точек VPN Таким образом, ребра этого пути / е pw могут быть использованы для защиты ребер дерева е е Г n егт Если ребро / используется для защиты дерева VPN Т , то будем называть его защитным ребром, а полосу пропускания, которую необходимо на нем выделить - защитной полосой пропускания Обозначим через P(f) множество ребер, для которых ребро / является защитным

Выберем для определенности направление в цикле сгю , сориентируем ребра цикла ат в соответствие с выбранным направлением и таким образом получим контур аш,, в котором любое ребро (*,>) направлено 01 х к у Будем считать, что ребро / = (х,у) и ребра (и,у)еР(/) направлены одинаково в соответствующих контурах (те от л к у и от и kv) Величина защитной полосы пропускания, которая должна быть выделена на этом ребре / = (х,у), определяется по следующим выражениям

6 И1Ц (*,>•) = max {b(v,u)\, (1)

(к v)eP(f)

Ь™\у,х) = max {b(u,v)} (2)

(u.v)eHf)

В общем случае выделение дополнительной полосы пропускания может быть необходимо еще и на ребрах дерева Т Пусть произошел отказ на ребре Оu,v)eT и определен некоторый путь рХ) в G-T, так что V/е справедливо P(f)r\(u,v) ф0 В этом случае все ребра f ер„, а также ребро (u,v) е Т входят в цикл етп

Тогда в рамках стратегии защиты звена на ребрах (i,j)eTn<r0 -(u,v) необходимо дополнительно выделить полосу пропускания = b{v,u) и

¿C'0,i) = fr(«,v) При этом также будем считать, что ребро (u,v) и ребра (¡,j)еТпст„ ~(и,\) направлены одинаково в контуре <тп В целом же, учитывая все ребра (и \>) е Т, получим следующие выражения

8

(4)

Для стратегии защиты пути полоса пропускания, которую необходимо дополнительно выделить на ребрах (г;1/)еГ-(и,у), определяется соотношениями

Здесь Тт =■ Т - (и,у) + рху, так что У/ е рх. справедливо Р(/)п(и,у)* 0 В целом же, учитывая все ребра (и, у) е Т, получим следующие выражения

Применение выражений (1)-(8) для различных фрагментов VPN проиллюстрировано на рис 3 Для ребра / = (х,у) на рис За P(f) = {(u,e),(e,v)}, поэтому защитная полоса на этом ребре равна b1!"u(x,y)-max{b(v,e)>b(e,u)} = 2, а b*m(y,x) = max.{b(e,v),b(u,e)} = 3 На рис 36 и рис Зв путь рш, является защитным для ребра (и,х), а путь ра, - для ребер (х,е) и (e,v) При стратегии защиты звена (рис 36) трафик от и к v при отказе (х,е) пойдет по маршруту (и,х), (х, v), (v, е), (е, v) Тогда bp (х, е) = max {¿£°п (х,е), b™" (х, е)} = шах {4,1} = 4 согласно (3) При стратегии защиты пути (рис Зв) трафик от и к v при отказе (х,е) будет передаваться по маршруту (u,x),(x,v) Тогда Ь£"(х,е) = тах{0,0-1}=0 и ¿>гд;п(х,е) = тах{0,2-1} = 1 согласно (5), а Ь]Г(х,е) - max {0,1} = 1 согласно (7)

Рис 3 Пример расчета полосы пропускания Для обеспечения отказоустойчивости VPN требуется определить множество защитных ребер F cG-T и величину выделенной на каждом ребре

¿Г (',./) = max {6„70>7)}>

V(K,v)er-0,y)

(7)

(8)

/ = (x,y)<=F защитной полосы пропускания Ь'аш(х,у) и Ь2*щ(у,х), а также величину выделенной на каждом ребре дерева e = (¡,j)eT дополнительной защитной полосы пропускания и bjm(j,i), так чтобы при отказе любого ребра дерева (м,у)еГ существовал путь рт, такой, что граф Т -(w,v) + рш является деревом Тю

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

X [Ъ™{х,у) + Ь™{у,х)]+ X [ЬГ(г,Л + ЬГй,1)]^гшп (9)

U>)eF (i j)eT

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

Задача в такой постановке соответствует в теории графов задаче оптимального пополнения графа, которая формулируется следующим образом Задан взвешенный граф G и подграф этого графа G', требуется найти множество ребер с минимальным весом А, так чтобы AuG' было двусвязным графом Однако имеется и весьма принципиальное различие, которое делает исходную задачу более сложной В задаче пополнения графа задан взвешенный граф, а в рассматриваемой задаче вес (те полоса пропускания) ребер известен только для ребер дерева VPN Вес остальных ребер зависит от того, являются ли эти ребра защитными, и если являются, то от гого, для каких ребер дерева они являются защитными Сама же задача пополнения графа относится к классу NP-полных задач, что предопределяет соответствующие методы ее решения

Если преодолеть указанное различие, то для решения поставленной задачи можно будет применить любой подходящий алгоритм оптимального пополнения графа В диссертации для этого предложен подход, использующий алгоритм пополнения графа Куллера- Гуримеллы [Khuller-Thurimella]

В третьей главе представлены разработанные алгоритмы определения оптимальных топологий отказоустойчивых VPN на основе симметричной и асимметричной древовидных потоковых моделей, базирующиеся на алгоритмах Италиано [Italiano] и Куллера-Туримеллы

Перед рассмотрением собственно основной идеи разработанных алгоритмов сформулируем ключевые недостатки алгоритма Италиано

1 Не учитывается асимметрия трафика конечных точек VPN

2 Не учитывается необходимость выделения дополнительной защитной полосы пропускания на ребрах дерева VPN

3 Не распределяется полоса пропускания на защитных ребрах, а лишь дается оценка верхней границы суммарной полосы пропускания

4 Достаточно высокий коэффициент аппроксимации 16

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

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

Рис 4 Обобщенный алгоритм определения оптимальной топологии отказоустойчивой

VPN

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

1 Алгоритм для симметричной модели и стратегии защиты звена

2 Алгоритм для симметричной модели и стратегии защиты пути

3 Алгоритм для асимметричной модели и стратегии защиты звена

4 Алгоритм для асимметричной модели и стратегии защиты пути

При распределении полосы пропускания на ребрах графа С - Т , а также на ребрах дерева Т для стратегии защиты звена, вместо выражений (1)-(4) предлагается использовать выражения, соответствующие логике работы алгоритмов и учитывающие результаты, полученные на предыдущих шагах алгоритмов

Сделаем сначала необходимые пояснения Во-первых, будем называть трафик ребер прямым, если он направлен в сторону корня дерева, трафик противоположного направления будем называть обратным Отметим, что в алгоритмах для асимметричной модели строятся два графа С?" и вычисляется два пополнения - соответственно, для прямого трафика и обратного трафика Для прямого трафика все ребра дерева будут направлены к корню, а все остальные ребра графа С" будут направлены в сторону вершин-потомков Для обратного трафика, наоборот, все ребра дерева будут направлены от корня, а все остальные ребра графа в" будут направлены в сторону вершин-предков

Рассмотрим пополнение для прямого трафика и некоторое ребро (х,у)"еЛ" Пусть данному ребру соответствует путь р'уг е<7-Т - путь в графе <7 -Т между вершинами и,уеТ, который, в конечном счете, и привел к добавлению ребра (х,у)" в граф С

Будем считать, что соответствующий контур а£>г ориентирован, так же как и ребра множества п,Р(х,у)" Следовательно, требование ребра (х,у)"еЛ" к защитной полосе пропускания на ребрах ^'''п^'1 (те на ребрах графа в-Т) равно \\>(х,у)" ¡м>(и^)' Под ии м<и,у)" понимаются веса ребер (и,у)'еС и (и,у)"е<У соответственно В целом же

При этом считается, что ребра (г,/) ориентированы так же, как и соответствующий им контур

Требование ребра (х,у)еЛ" к защитной полосе пропускания на ребрах (¿ОеёЦу* - р[уг (те на ребрах Т ) равно у,>(х,у)" !м?(и,у)' В целом же

(10)

¿>ГЧм) =

тах

<> Л <\1) ел" (х г)г,г<; '>

(П)

При этом считается, что ребра 0,0 ориентированы так же, как и соответствующий им контур п^-"',

Для обратного трафика соответственно получим следующие выражения:

кфс.уУ]

иг

b™(i,j) =

(s,t)~ max <10,

(*,)■)'■ (x,y)-e.r.(i,j)np<;-'rt0 w(U,v)' w(x,y)"

b(s,t)

(12)

(13)

Для стратегии зашиты пути распределение защитной полосы пропускания на ребрах дерева Т производится согласно выражениям (5)-(8).

Отметим, что разработанные алгоритмы имеют полиномиальное время выполнения, оцениваемое величиной 0{VE + V2 logF), если для расчета кратчайших путей используется алгоритм Дийкстры [Dijkstra], для расчета наименьших общих предков алгоритм Харела-Тарьяна [Harel-Tarjan], для поиска оптимального пополнения алгоритм Куллера-Туримеллы, реализующего алгоритм Габова [Gabow] для поиска минимального ветвления.

В четвертой главе описана программная реализация разработанных алгоритмов, приведены результаты экспериментов над известными и разработанными алгоритмами для сетей различных размеров и топологий в зависимости от требований к полосе пропускания и количества конечных точек VPN.

На рис.5, приведены результаты расчетов для сети из 40 вершин и 90 ребер. Число конечных точек с единичными требованиями к полосе пропускания варьируется от 2 до 28. Приняты следующие обозначения алгоритмов: А -Италиано; Б - для симметричной модели без распределения полосы пропускания на ребрах дерева; В - для симметричной модели и стратегии защиты звена; Г - для симметричной модели и стратегии защиты пути. На рис.6, приведено сравнение алгоритмов для симметричной и асимметричной модели на сети из 30 вершин и 70 ребер.

— Алгоритм А Алгоритм 6

Дерою S/m

Рис.5. Результаты расчета для симметричной модели

Рис.6. Сравнение алгоритмов для симметричной и асимметричной модели

Очевидно преимущество Алгоритма Б над алгоритмом А. Алгоритм Б представляет собой предложенную в диссертационной работе модификацию алгоритма Италиано с целью эффективного распределения полосы пропускания на ребрах /еС-Т . Тем не менее, ни один из этих алгоритмов не дает гарантированной защиты от отказов, поскольку не распределяет полосу пропускания на ребрах дерева Т , которая необходима как для стратегии защиты звена, так и для стратегии защиты пути. Вследствие этого, понятно что полоса пропускания, требуемая алгоритмом В (защита звена) и алгоритмом Г (защита пути), будет превосходить требования алгоритма Б, поскольку алгоритмы В и Г являются дальнейшим развитием алгоритма Б. Однако, эти алгоритмы дают 100% гарантию защиты от о диночных отказов ребер дерева Т .

По диаграммам на рис. 5 и 6 видно, что стратегия защиты звена для асимметричной модели также требует выделения полосы пропускания в 1,5-2 раза больше, чем стратегия защиты пути, что согласуется с аналогичными данными для симметричной модели.

На рис.7 и рис.8 приведены результаты расчета экономии (в процентном соотношении) защитной и суммарной полосы пропускания в асимметричной модели по сравнению с симметричной.

Рис.7 Экономия защитной полосы про- Рис.8. Экономия суммарной полосы пропускания пускания

Экономия защитной полосы пропускания при учете асимметричности трафика конечных точек VPN составляет порядка 20-30%. Суммарная экономия полосы пропускания с учетом как полосы пропускания VPN, так и защитной полосы пропускания, составляет 24-30%, что в итоге можно считать результатом, достаточным для использования асимметричной модели на практике.

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

ЗАКЛЮЧЕНИЕ

В целом, по итогам работы можно сформулировать следующие основные

полученные результаты

1 Предложена графовая модель отказоустойчивой VPN, учитывающая асимметрию трафика конечных точек

2 Разработан способ определения величины дополнительной полосы пропускания на защитных ребрах и ребрах дерева VPN на основе асимметричной потоковой модели для стратегий защиты звена и защиты пути

3 Разработаны полиномиальные алгоритмы определения оптимальных топологий отказоустойчивых VPN как с симметричным, так и асимметричным трафиком конечных точек

4 Разработанные алгоритмы реализуют как стратегию защиты звена, более близкую к-практике, так и стратегию защиты пути, более эффективную

5 Проведены компьютерные эксперименты, доказывающие преимущество разработанных алгоритмов над существующими

6 Показано, что для асимметричной модели стратегия защиты звена требует в 1,5-2 раза больше полосы пропускания чем стратегия защиты пути, что согласуется с аналогичными результатами для симметричной модели

7 Показано, что применение разработанных алгоритмов позволяет получить экономию в 20-30% полосы пропускания по сравнению с соответствующей симметричной моделью с учетом защиты VPN от одиночных отказов звеньев сети

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Нуштаев, А В Анализ возможности применения технологии VPN для ФЦП «Электронная Россия» / А В Нуштаев // Тез докл XI Российской НТК ПГАТИ -ПГАТИ, Самара, 2004 - С 60-61

2 Нуштаев, А В Математическая модель проектирования виртуальных частных сетей / А В Нуштаев // Докл V Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки» - СамГТУ, Самара, 2004 -Части 14-17 - С36-38

3 Нуштаев, А В Резервирование ресурсов в потоковой модели реализации виртуальных частных сетей / А В Нуштаев // Доклады V Международной НТК «Проблемы техники и технологии телекоммуникаций» - Самара, 2004г - С 49-50

4 Росляков, А В Восстановление от отказов звеньев в виртуальных частных сетях / А В Росляков, А В Нуштаев // Тез докл. XII Российской НТК ПГАТИ - ПГАТИ, Самара, 2005 - С 62-64

5 Росляков, А.В Асимметричная потоковая модель VPN/ А В Росляков, А В Нуштаев//Тез докл XII Российской НТК ПГАТИ - ПГАТИ, Самара, 2005 -С 56-58

6 Нуштаев, А В Обеспечение качества обслуживания в виртуальных частных сетях в случае отказов / А В Нуштаев // Докл VI Международной конференции «Цифровая обработка сигналов и ее применение» (DSPA-2005) - Москва, 2005 -С 152-154

<vT)

7 Нуштаев, А В Алгоритмы построения отказоустойчивых виртуальных частных сетей / А В Нуштаев, А В Росляков //Докл 60-ой научной сессии, посвященной Дню Радио -Москва, 2005 -С 54-57

8 Нуштаев, А В Формальная постановка задачи резервирования ресурсов в VPN / А В Нуштаев // Докл 6-й Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» -Уфа, 2005 - С 130-131

9 Нуштаев, А В Способы построения отказоустойчивых jVPN в древовидной потоковой модели / А В Нуштаев // Тез Докл XIII юбилейной российской научной конференции -ПГАТИ, Самара, 2006 - С 50-51

10 Нуштаев, А В Проектирование отказоустойчивой VPN как задача оптимальной аугментации графа / А В Нуштаев // Докл 61-й научной сессии, посвященной Дню Радио - Москва, 2006 - С 199-201

11 Росляков, А В Улучшенный аппроксимационный алгрритм построения отказоустойчивой древовидной VPN / А В Росляков, А В Нуштаев // Труды учебных заведений связи - 2006 - № 175 - С 54-61

12 Росляков, А.В Обеспечение отказоустойчивости в древовидной потоковой модели VPN / А В Росляков, А В Нуштаев // Тез докл VII Международной НТК «Проблемы техники и технологии телекоммуникаций» - Самара, 2006 - С 58-60

13 Нуштаев, А В Приближенные алгоритмы проектирования отказоустойчивых VPN в симметричной и ассиметричной древовидной потоковой модели / А В Нуштаев // Материалы XIV российской научной конференции ПГАТИ - Самара, 2007 -С 47

14 Росляков, А В Приближенные алгоритмы проектирования отказоустойчивых VPN в симметричной л ассиметричной древовидной потоковой модели / А В. Росляков, А В Нуштаев // Докл 9-й Международной ^конференции «Цифровая

, обработка сигналов и ее применение» (DS.PA-2007) - Москва, 2007 - С 153-155

15 Нуштаев, А В Приближенные алгоритмы проектирования отказоустойчивых VPN в симметричной и ассиметричной-древовидной потоковой модели / А В Нуштаев // Тез докл Седьмого Всероссийского Симпозиума По, Прикладной и Промышленной Математике (зимняя сессия) - Йошкар-Ола, 2006 - С 330-331

16 Нуштаев, А В Аппроксимационные алгоритмы для проектирования отказоустойчивых VPN в потоковой модели с асимметричным трафиком и древовидной топологией / А В Нуштаев И Докл XIII Международной научно-технической конференции «Радиолокация, навигация, связь» -Воронеж, 2007 - С 1026-1035

17 Росляков, А В Модели и Методы реализации отказоустойчивых VPN / А В Росляков, А В Нуштаев // Электросвязь - 2007. - №7 - С 47-50.

18 Росляков, А В Аппроксимационные алгоритмы проектирования отказоустойчивых VPN в древовидной асимметричной потоковой модели / А В Росляков, А В Нуштаев // Инфокоммуникационные технологии - 2007 ¡- №4 - С 43-48

19 Свидетельство об отраслевой регистрации разработки В: Отраслевом фонде алгоритмов и программ № 8947 Пакет проектирования виртуальных частных сетей [Пакет программ] / А В Росляков, А В Сергеев, А В Нуштаев -№50200701857 опубл 23 08 2007 Бюл №8 - 1 с

Подписано в печать И 1007 Формат 60х84'/|й Бумага писчая № 1 Гарнитура Тайме Печать оперативная Уел печ л 0,93 Физ печ л 1,00 Уч-изд л 0,52 Тираж! 00 экз

Типография государственного образовательного учреждения высшего профессионального образования «Поволжская государственная академия телекоммуникаций и информатики» 443010, г Самара, ул Л Тотстого,23 Тел/факс (846) 339-1141,339-11-81

1. МОДЕЛИ И МЕТОДЫ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ

В ВИРТУАЛЬНЫХ ЧАСТНЫХ СЕТЯХ.

1.1. Основы технологии VPN.

1.1.1. Понятие технологии VPN.

1.1.2. Классификация VPN.

1.1.3. Особенности BGP/MPLS VPN.

1.2. Модели VPN в аспекте QoS.

1.2.1. Проблема обеспечения качества обслуживания в VPN.

1.2.2. Канальная модель.

1.2.3. Потоковая модель.

1.3. Проблема обеспечения отказоустойчивости VPN.

1.3.1. Введение в проблему и классическая постановка задачи.

1.3.2. Стратегии обеспечения отказоустойчивости.

1.4. Обзор моделей и методов расчета отказоустойчивых VPN.

1.5. Выводы.

2. ГРАФОВАЯ МОДЕЛЬ ОТКАЗОУСТОЙЧИВОЙ ВИРТУАЛЬНОЙ ЧАСТНОЙ СЕТИ.

2.1. Описание модели отказоустойчивой VPN.

2.2. Формальная постановка задачи.

2.3. Задача оптимальной пополнения графа.

2.4. Алгоритм минимальной пополнения Куллера-Туримеллы.

2.5. Функции стоимости для пополнения.

2.6. Выводы.

3. РАЗРАБОТКА АППРОКСИМАЦИОННЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ VPN.

3.1. Приближенный алгоритм Италиано-Растоги для симметричной модели

3.1.1. Суть алгоритма Италиано-Растоги.

3.1.2. Недостатки алгоритма.

3.2. Улучшение и модификация алгоритма.

3.2.1. Уменьшение коэффициента аппроксимации алгоритма.

3.2.2. Преобразование пополнений А" в А.

3.2.3. Распределение полосы пропускания на ребрах дерева Т.

3.2.4. Учет в функции стоимости пополнения ребер дерева Т.

3.3. Алгоритмы для симметричной модели VPN.

3.4. Адаптация алгоритмов для асимметричной модели VPN.

3.5. Примеры решения задач разработанными алгоритмами.

3.5.1. Пример расчета для симметричной модели VPN.

3.5.2. Пример расчета для асимметричной модели VPN.

3.6. Характеристики алгоритмов.

3.7. Выводы.

4. РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ.

4.1. Особенности реализации разработанных алгоритмов.

4.2. Исследование алгоритмов для симметричной модели.

4.3. Исследование алгоритмов для асимметричной модели.

4.4. Выводы.

Актуальность темы

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

Поскольку строительство и эксплуатация собственной сети связи - занятие весьма дорогое, на рынке телекоммуникационных услуг появилось решение в виде технологии и услуги виртуальной частной сети VPN (Virtual Private Network). Технология VPN обязана имитировать два основополагающих свойства частной сети - гарантированные безопасность и качество обслуживания. Вследствие повсеместного использования стека протоколов TCP/IP среди услуг VPN стали доминировать услуги виртуальных сетей на базе протокола IP - так называемые IP VPN, которые унаследовали традиционные для сетей IP проблемы с качеством обслуживания QoS (Quality of Service). Однако с появлением различных технологий и протоколов, призванных решить проблему гарантированного QoS, среди которых лидирующее положение по праву занимает технология мультипротокольной коммутации по меткам MPLS, услуга IP VPN стала широко востребованной.

Разработка и внедрение таких технологий привело к всплеску научных публикаций по проблематике исследования VPN, удовлетворяющих заданным показателям качества обслуживания. При этом в качестве таких показателей наиболее часто используется гарантированная полоса пропускания и значительно реже рассматриваются задержки или живучесть. Среди зарубежных ученых, изучающих данную проблему, стоит особо выделить A.Kumar, A. Gupta, N.G. Duffield, R.Rastogi, B.Yener, G.F. Italiano, Y.L. Liu, Y.S. Sun и др. Все эти авторы занимаются исследованиями потоковой модели VPN, предложенной несколько лет назад в противовес традиционной, так называемой канальной модели VPN, основанной на полной матрице трафика. Канальная и потоковая модели используются в задачах определения оптимальной топологии VPN. Потоковая модель характеризуется в первую очередь эффективностью использования полосы пропускания, гибкостью в передаче трафика, простотой и удобством спецификации требований пользователей. В России исследованиями VPN и смежных с ними проблем занимаются Б.С. Гольдштейн, А.В. Росляков, В.Г. Олифер, Н.А. Олифер и др. Стоит уточнить, что задача построения оптимальной топологии VPN на основе потоковой модели является весьма сложной, а некоторые ее разновидности и вовсе относятся к классам NP-сложных или NP-полных задач.

Несмотря на повышенный интерес к проблеме исследования VPN, ряд теоретических задач так и не решен. Так одной из важнейших проблем является защита трафика VPN от отказов каналов и узлов сети, которая особенно актуальна для наиболее часто используемой разновидности топологии потоковой модели в виде дерева. Даже для относительно простой модели с симметричным трафиком не найден эффективный полиномиальный алгоритм, позволяющий строить отказоустойчивые VPN с гарантированной полосой пропускания. Имеющиеся работы по данной тематике имеют проблемы либо с эффективностью, либо с масштабируемостью. Наиболее же актуальны исследования асимметричной модели VPN, обусловленной использованием на практике технологий асимметричного доступа (ADSL, ADSL2, ADSL2+) и таких услуг, как ftp и web сервисы, Интернет-радио, IPTV, Video On Demand и др., однако сведения о подобных исследованиях в печати отсутствуют.

Объектом исследования являются виртуальные частные сети, организуемые операторами связи.

Предмет исследования является полоса пропускания, которую необходимо дополнительно выделить в сети общего пользования для гарантированной защиты трафика VPN от отказов каналов сети

Цель работы и задачи исследования

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

Поставленная цель определила необходимость решения следующего ряда задач:

• анализ существующих моделей и методов решения задачи обеспечения отказоустойчивости VPN;

• разработка формализованного математического описания исследуемого объекта - отказоустойчивой VPN на основе потоковой модели;

• разработка способа определения величины необходимой защитной полосы пропускания для различных стратегий защиты;

• разработка алгоритмов определения оптимальных топологий отказоустойчивых VPN на основе симметричной и асимметричной моделей и различных стратегий защиты;

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

Методы исследования

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

Достоверность результатов

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

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

Научная новизна диссертационной работы заключается в следующем:

• разработана графовая модель отказоустойчивой виртуальной частной сети с топологией дерева, учитывающая асимметрию трафика конечных точек 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 наименований.

4.4. Выводы

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

Разработанные в диссертации алгоритмы реализованы в виде программного пакета, использованного при проведении численных экспериментов.

Результаты экспериментов позволяют сделать следующие выводы:

- разработанные алгоритмы вполне работоспособны, и, что наиболее важно, корректны и справедливы, что подтверждается сравнением с известными результатами [70, 77];

- сравнение с результатами работы других алгоритмов, в частности с алгоритмом Италиано-Растоги [67], показывает как минимум двукратное превосходство разработанных в диссертации алгоритмов;

- для асимметричной модели применение разработанных алгоритмов позволяет получить экономию в 15-30% полосы пропускания по сравнению с соответствующей симметричной моделью.

ЗАКЛЮЧЕНИЕ

В данной диссертационной работе было произведено исследование и разработка алгоритмов расчета отказоустойчивых VPN для древовидной потоковой модели.

В результате анализа существующих работ по данной тематике, проведенного в ходе диссертационного исследования, выявлены их общие моменты и раскрыты их ключевые недостатки. Показано, что существующие методы являются либо хорошо проработанными в теоретическом плане (гарантированная верхняя граница защитной полосы пропускания в виде коэффициента аппроксимации, оценка временной сложности алгоритмов), но слабыми в практическом отношении (не распределяется полоса по защитным ребрам, не выбираются защитные маршруты, нет результатов численных экспериментов). Либо с точностью до наоборот повторяют их достоинства и недостатки, т.е. являются более завершенными для практического применения, однако область применения ограничена в силу недостаточной масштабируемости. Самое же главное, ни один из существующих алгоритмов не применим к асимметричной модели VPN.

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

Для решения поставленных задач в диссертационной работе предложена математическая модель отказоустойчивой VPN, учитывающая особенности асимметричной потоковой модели, древовидность топологии VPN, стратегии защиты звена и защиты пути, и допускающая одиночные отказы на ребрах дерева VPN. Для представленной модели сделана строгая математическая формулировка задачи обеспечения отказоустойчивости VPN. Показано близкое сходство данной задачи с задачей оптимального пополнения графа, относящейся к классу NP-complete, позволяющее сделать вывод о том, что решение, скорее всего, может быть лишь приближенным.

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

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

В целом, по итогам работы можно сформулировать следующие основные полученные результаты:

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

• Разработан способ определения величины дополнительной полосы пропускания на защитных ребрах и ребрах дерева VPN на основе асимметричной потоковой модели для стратегий защиты звена и защиты пути.

• Разработаны полиномиальные алгоритмы определения оптимальных топологий отказоустойчивых VPN как с симметричным, так и асимметричным трафиком конечных точек.

• Разработанные алгоритмы реализуют как стратегию защиты звена, более близкую к практике, так и стратегию защиты пути, более эффективную.

• Проведены компьютерные эксперименты, доказывающие преимущество разработанных алгоритмов над существующими.

• Показано, что для асимметричной модели стратегия защиты звена требует в 1,5-2 раза больше полосы пропускания чем стратегия защиты пути, что согласуется с аналогичными результатами для симметричной модели.

• Показано, что применение разработанных алгоритмов позволяет получить экономию в 20-30% полосы пропускания по сравнению с соответствующей симметричной моделью с учетом защиты VPN от одиночных отказов звеньев сети.

1. Росляков, А.В. Виртуальные частные сети. Основы построения и применения / А.В. Росляков. - М.: Эко-Трендз, 2006. - 304 с.

2. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд. / В.Г. Олифер, Н.А. Олифер. СПб.: Питер, 2006.-958 с.

3. Браун, С. Виртуальные частные сети / С. Браун. М.: Лори, 2001. - 508 с.

4. Олифер, В.Г Новые технологии и оборудование IP-сетей / В.Г. Олифер, Н.А. Олифер. СПб.: БХВ-Петербург, 2001. - 512 с.

5. Запечников, С.В. Основы построения виртуальных частных сетей: Учебн. пособие для вузов / С.В. Запечников, Н.Г. Милославская, А.И. Толстой М.: Горячая линия-Телеком, 2003. - 249 с.

6. Гольдштейн, А.Б. Технология и протоколы MPLS / А.Б. Гольдштейн, Б.С. Гольдштейн. СПб.: БХВ-Санкт-Петербург, 2005. - 304 с.

7. Morrow, М. MPLS and Next-Generation Networks: Foundations for NGN and Enterprise Virtualization / M. Morrow, A. Sayeed. Cisco Press, 2006. -P.422

8. Guichard, J. MPLS and VPN Architectures / J. Guichard, I. Pepelnjak. -Cisco Press, 2000.-P.448

9. Luo, W. Layer 2 VPN Architectures / W. Luo, C. Pignataro, D. Bokotey. -Cicso Press, 2005. P.648

10. Reddy, K. Building MPLS-Based Broadband Access VPNs / K. Reddy. -Cisco Press, 2004. P.408

11. Guichard, J. MPLS and VPN Architectures, Volume II / J. Guichard, I. Pepelnjak, J. Apcar. Cisco Press, 2003. - P.504

12. Олифер, В.Г. MPLS на службе VPN Электронный документ. / В.Г. Олифер, Н.А. Олифер. Режим доступа: http://www.abn.ru/inf/lan/ mpls.shtml. - 21.03.2002.

13. Леонов, С. Реальная виртуальность Электронный документ. / С. Леонов. Режим доступа: http://www.computerra.ru/offline/1998/237/1149 -09.03.2004.

14. Воронин, А., Курилов О. Организация услуг VPN на базе операторских сетей / А. Воронин, О. Курилов // Технологии и средства связи Ежегодный отраслевой каталог. - 2002. - С. 68-73.

15. Лукацкий, А. Атаки на VPN Электронный документ. / А. Лукацкий. -Режим доступа: http://www.bugtraq.ru/library/crypto/vpn3.html. 24.04.02.

16. Ален, Д. Следующая волна VPN на базе IP / Д. Ален // LAN. 2001. -№ 3. - С. 86-95.

17. Гвоздев, И. М. Отечественные средства построения для виртуальных частных сетей / И.М Гвоздев, В.Н. Зайчиков, Н.Н. Мошак, М.Б. Пелени-цын, С.П. Селезнев, Д.А. Шепелявый // Сети и системы связи. 1999. -№ 12.-С. 24-28.

18. Горностаев, В. Зарубежные VPN в России Электронный документ. / В. Горностаев, В. Лукоянов. Режим доступа: http://www.setevoi.ru/cgi-bin/text.pl/magazines/2000/9/Ю. - 09.03.2004.

19. Дэниэль, М. VPN нового поколения: крепкий орешек Электронный документ. / М. Дэниэль. Режим доступа: http://www.setevoi.ru/cgi-bin/materials.pl?issue=032000&article=31. - 20.03.2004.

20. Прокопьев, Н. Теория и практика: VPN стандартными средствами Windows 2000 Электронный документ. / Н. Прокопьев. Режим доступа: http://i2r.rusfund.ru/static/385/out10155.shtml. - 09.03.2004.

21. Первый кирпич в стене VPN. Обзор устройств VPN начального уровня Электронный документ. Режим доступа: http://www.ixbt.com/comm /vpnl.shtml.- 09.03.2004.

22. Захватов, М. Построение виртуальных частных сетей (VPN) на базе технологии MPLS / М. Захватов. Cisco Systems, 2001. - 48 с.

23. Олифер, Н. Виртуальные частные сети на основе MPLS Электронный документ. / Н. Олифер, В. Олифер. Режим доступа: http://www.osp.ru/lan/2002/01/135687/. - 09.03.2004.

24. Виртуальные частные коммутируемые сети Virtual Private Dialup Network (VPDN) Электронный документ. Режим доступа: http://cisco.udm.ru/doc/vpdn/vpdn.htm. - 09.03.2004.

25. Загнетко, A. IP VPN: осознанная необходимость Электронный документ. / А. Загнетко. Режим доступа: http://www.connect.ru/article.asp ?id=5343. - 09.03.2004

26. Березин, А. VPN-технологии для Интернет-провайдеров ISP Электронный документ. / А. Березин. Режим доступа: www.setevoi.ru/cgi-bin/text.pl/magazines/2000/10/66. - 09.03.2004.

27. Турская, Е. VPN как средство "неотложной помощи" Электронный документ. / Е. Турская. Режим доступа: http://www.setevoi.ru/cgi-bin/ text.pl/magazines/2000/11/31. - 09.03.2004.

28. Саламон, С. Виртуальные частные сети: новые предложения? Электронный документ. / С. Саламон. Режим доступа: http://www.setevoi.ru /cgi-bin/text.pl/magazines/2000/l 1/40. - 09.03.2004.

29. Лукацкий, А. Неизвестная VPN Электронный документ. / А. Лукацкий. Режим доступа: http://www.abn.ru/inf/compress/network4.shtml. -09.03.2004.

30. Технологии виртуальных частных сетей Электронный документ. Режим доступа: http://www.ecoprog.ru/lvs/ techl .shtml. - 09.09.2004.

31. Ганьжа, Д. Под флагом VPN Электронный документ. / Д. Ганьжа. Режим доступа: http://www.osp.ru/lan/2006/03/377835/. - 09.03.2004.

32. Ален, Д. Следующая волна VPN на базе IP Электронный документ. / Д. Ален. Режим доступа: http://www.osp.ru/lan/2001/03/134723/. -09.03.2004.

33. Лукацкий, A. VPN. Старые песни о главном Электронный документ. / А. Лукацкий. Режим доступа: http://www.compress.ru/Archive/CP/2001 /5/67/. -09.03.2004.

34. Carugi, М. Virtual Private Network Services Электронный документ. / М. Carugi. Режим доступа: http://www.isoc-gfsi.org/gfsi/reunions/docs /IETF2002/Carugi/VPN-Carugi-2ndFrenchIETF day-final.pdf. - 10.04.2006.

35. Carugi, М. Virtual Private Network Services Электронный документ. / M. Carugi. Режим доступа: http://www.inrialpes.fr/planete/people /roca/rhdm02/slides/08Mai JVr.CamgiVPN-RHDM02.pdf. - 10.04.2006/

36. Kompella, К. RFC4761. Virtual Private LAN Service (VPLS) Using BGP for Auto-Discovery and Signaling, January 2007 Электронный документ. / К. Kompella, Y. Rekhter. Режим доступа: http://www.rfc-editor.org. -15.01.2007.

37. Lasserre, M. RFC4762. Virtual Private LAN Service (VPLS) Using Label Distribution Protocol (LDP) Signaling, January 2007 Электронный документ. / M. Lasserre, К. Kompella. Режим доступа: http://www.rfc-editor.org.- 15.01.2007.

38. Rouskas, G.N. Tutorial on Optical Networks / G.N. Rouskas, H.G. Perros // Networking 2002 Tutorials, LNCS. 2002. - 112 p.

39. Эльке, Я. Тенденция собственной длины волны / Я. Эльке // Журнал сетевых решений LAN. 2004. - № 12. - С. 20-21.

40. Rosen, Е. RFC4364. BGP/MPLS IP Virtual Private Networks (VPNs), February 2006 Электронный документ. / E. Rosen, Y. Rekhter. Режим доступа: http://www.rfc-editor.org. - 15.01.2007.

41. Mitra, D. VPN DESIGNER: a tool for design of multiservice virtual private networks / D. Mitra, J.A. Morrison, K.G. Ramakrishnan // Bell Labs Technical Journal. 1998.- № 10. - P. 15-31.

42. Mitra, D.Virtual private networks: joint resource allocation and routing design / D. Mitra, J.A. Morrison, K.G. Ramakrishnan // Proc. IEEE INFOCOM '99. -New York, 1999. P. 480-490.

43. Росляков, А.В. Оптимальное распределение сетевых ресурсов для реализации виртуальных частных сетей / А.В. Росляков // Труды учебных заведений связи / СПб., СПбГУТ. 2004. - С. 65-74.

44. Kelly, F.P. Routing in circuit-switched networks: optimization, shadow prices and decentralization / F.P. Kelly // Adv. Appl. Prob. 1988. - №20. - P. 112-144.

45. Kelly, F.P. Fixed point models of loss networks / F.P. Kelly // J. Austr. Math. Sot. 1989. - Ser. В, № 31. - P. 204-218.

46. Mitra, D. ATM network design and optimization: a multirate loss network framework / D. Mitra, J.A. Morrison, K.G. Ramakrishnan // IEEE/ACM Trans. Networking. 1996. - № 4(4). - P. 531-543.

47. Ross, K.W. Multirate loss models for broadband telecommunications / K.W. Ross. New York, Springer, 1995. - 412 p.

48. Duffield, N.G. Resource management with hoses: point-to-cloud services for virtual private networks / N. Duffield, P. Goyal, A. Greenberg, P. Mishra, K.

49. Ramakrishnan, J.E. van der Merwe // IEEE/ACM Transactions on Networking. 2002 - V. 10, № 5. - P. 679-692.

50. Duffield, N.G. A flexible model for resource management in virtual private networks / N. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. Ramakrishnan, J.E. van der Merwe // ACM SIGCOMM Computer Communication Review.- 1999. V 29, № 4. - P. 95-108.

51. Росляков, A.B. Построение виртуальных частных сетей на базе потоковой модели / А.В. Росляков // 7-я Международная конференция «Цифровая обработка сигналов и ее применение» (DSPA-2005): Тез. докл. М., 2005.-С. 136-139.

52. Росляков, А.В. Исследование потоковой модели реализации виртуальных частных сетей / А.В. Росляков // V Международная конференция «Проблемы техники и технологии телекоммуникаций»: Матер, конф. -Самара, 2004. С. 21-23.

53. Росляков, А.В. Асимметричная потоковая модель VPN / А.В. Росляков, А.В. Нуштаев // Труды XII Российской научной конференции профессорско-преподавательского состава ПГАТИ: Тез. докл. Самара, 2005. -С. 50-52.

54. Kumar, A. Algorithms for provisioning virtual private networks in the hose model / A. Kumar, R. Rastogi, A. Silberschatz, В. Уепек // IEEE/ACM Transactions on Networking. 2002. - V. 10, № 4. - P. 565 - 578.

55. Gupta, A. Provisioning a virtual private network: a network design problem for multicommodity flow /А. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, B. Yener // Proceedings of ACM STOC. 2001. - P. 389-398.

56. Swamy, C. Primal-dual algorithms for connected facility location problems source / C. Swamy, A.Kumar // Proceedings of the 5th International

57. Workshop on Approximation Algorithms for Combinatorial Optimization. -2002.-P. 256-270.

58. Eisenbrand, F. An improved approximation algorithm for virtual private network design / F. Eisenbrand, F. Grandoni // ACM-SIAM Symposium on Discrete Algorithms. 2005. - P. 928-932

59. Eisenbrand, F. New approaches for virtual private network design / F. Eisenbrand, F. Grandoni, G. Oriolo, M. Skutella // International Colloquium on Automata, Languages and Programming. 2005. - P. 1151-1162.

60. Jiittner, A. On bandwidth efficiency of the hose resource management model in virtual private networks / A. Jiittner, I. Szabo, A. Szentesi // IEEE INFOCOM. 2003. Jiittner, A., Szabo I., Szentesi A. - P. 356-362.

61. Italiano, G. F. Restoration algorithms for virtual private networks in the hose model / G.F. Italiano, R. Rastogi, B. Yener // IEEE INFOCOM. 2002. -Volume 1, Issue.-P. 131-139.

62. Росляков, A.B. Улучшенный аппроксимационный алгоритм построения отказоустойчивой древовидной VPN / А.В. Росляков, А.В. Нуштаев // Труды учебных заведений связи. 2006. - №175. - С. 54-61.

63. Chekuri, С. Building edge-failure resilient networks./ С. Chekuri, A. Gupta, A. Kumar, S. Naor, D. Raz // In Integer Programming and Combinatorial Optimization (IPCO). 2002. - P. 439-456.

64. Balasubramanian, A. Bandwidth requirements for the protected VPNs in the hose model / A. Balasubramanian, G. Sasaki // International Symposium on Information Theory. Kanagawa 2003. - P.89-90.

65. Liu, Y.-L. Traffic Engineering for Provisioning Restorable Hose-Model VPNs / Y.L. Liu, Y.S. Sun, M.C. Chen // IEICE Trans. Commun. -September 2006. Vol.E89-B, No.9. - P. 67-75.

66. Росляков, A.B. Восстановление от отказов звеньев в виртуальных частных сетях / А.В. Росляков, А.В. Нуштаев // Тезисы докладов XII Российской НТК ПГАТИ: Тез. Докл. 2005. - С. 62-64.

67. Росляков, А.В. Аппроксимационные алгоритмы проектирования отказоустойчивых VPN в древовидной асимметричной потоковой модели / А.В. Росляков, А.В. Нуштаев // Инфокоммуникационные технологии. -2007. №4. - С.43-48.

68. Росляков, А.В. Модели и методы реализации отказоустойчивых VPN / А.В. Росляков, А.В. Нуштаев // Электросвязь. 2007. - №7. - С. 47-50.

69. Нуштаев А.В., Росляков А.В. Алгоритмы построения отказоустойчивых виртуальных частных сетей // Доклады 60-й научной сессии, посвященной Дню Радио. М., 2005. - С. 54-57.

70. Hussain, I. Fault-Tolerant IP and MPLS Networks /1. Hussain. Cicso Press, 2004.-P. 336

71. Balasubramanian, A. Protected virtual private networks in the hose model / A. Balasubramanian. MS dissertation thesis, 2003. - P.51.

72. Liu, Y.L. Traffic Engineering for Hose-Model VPN Provisioning / Y. L. Liu, Y. S. Sun, M. C. Chen // in: Proc. of IEEEGLOBECOM. 2005.

73. Cinkler, T. Configuration of Protected Virtual Private Networks / T. Cinkler, M. Maliosz // Design Of Reliable Communication Networks, DRCN, Budapest, Hungary. 2001.

74. Hegyi, P. Shared Protection of Virtual Private Networks with Traffic Concentration /Р. Hegyi, M. Maliosz, A. Ladanyi, T. Cinkler // Proceeding in Fourth Int. Conf. on Design of Reliable Communications Networks (DRCN 2003), Banff, Alberta, Canada. 2003.

75. Veciana, G. Routing and provisioning VPNs based on hose traffic models and/or constraints / G. Veciana, S. Park S, A. Sang, S. Weber // Proceedings of the 40th Annual Allerton Conference on Communication, Control and Computing. 2002. - P. 77-86.

76. Hota, C. Restoration of Virtual Private Networks with QoS Guarantees in the Pipe Model / C. Hota, S.K. Jha, G. Raghurama // Proceedings in Distributed Computing IWDC, Kolkata, India. 2004. - P. 289-302.

77. Каминецкий, И.С. Использование П-циклов для формирования сетевого резерва на транспортных сетях связи / И.С. Каминецкий, А.Н. Зюзин // Труды учебных заведений связи. 2005. - № 173. - С. 59-67

78. Каминецкий, И.С. Современные механизмы резервирования и восстановления транспортных сетей связи / И.С. Каминецкий, А.Н. Зюзин // Электросвязь. 2005. - №7. - С. 18-21.

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

80. Bremler-Barr, A. Restoration by path concatenation: Fast recovery of MPLS paths / A. Bremler-Barr, Y. Afek, H. Kaplan, E. Cohen, M. Merritt // Proceedings of ACM SIGMETRICS, 2001.

81. Kodialam, M. Dynamic routing bandwidth guaranteed tunnels with restoration / M. Kodialam, Т. V. Lakshman // Proceedings IEEE INFOCOM, 2000.

82. Kodialam, M. Dynamic routing of locally restorable bandwidth guaranteed tunnels using aggregated link usage information / M. Kodialam, Т. V. Lakshman // Proceedings IEEE INFOCOM, 2001.

83. Cheuk Wan William Lau. Restoration Strategies and Algorithms For Survivable Networks / Cheuk Wan William Lau. PhD thesis, 2004. - P.332.

84. Zhou, D. Survivability in optical networks / D. Zhou, S. Subramaniam //IEEE Network, 2000, Vol.14, № 6. P. 16-23

85. Haque, A. Design of Survivable Optical Virtual Private Networks (O-VPNs) / Anwar Haque, Pin-Han Ho // in: Proc. of IEEEGLOBECOM. 2005.

86. Modiano, E. Survivable Lightpath Routing: A New Approach to the Design of WDM-Based Networks / Eytan Modiano, Aradhana Narula-Tam // IEEE journal on selected areas in communications, 2002. Vol. 20, №. 4.

87. Lee, D. Path Protection and Blocking Probability Minimization in Optical Networks / D. Lee, L. Libman, A. Orda // IEEE INFOCOM, 2004.

88. Кристофидес, H. Теория графов. Алгоритмический подход / Н. Кристо-фидес. М.: Мир, 1978. - 432 с.

89. Оре, О. Теория графов / О. Ope. М.: Наука, 1968. - 336 с.

90. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. -М.: Мир, 1981.-324 с.

91. Diestel, R. Graph Theory / R. Diestel. Springer-Verlag, New York, 2000. -P.322

92. Свами, M. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. -М.:Мир, 1994.-454 с.

93. Татт, У. Теория графов / У. Татт. М.:Мир, 1998. - 424 с.

94. Зыков, А. Основы теории графов / А. Зыков. М.: Наука Гл. ред. физ.-мат. наук. 1987.-384 с.

95. Diestel, R. Graph Theory / R. Diestel. Springer-Verlag, New York, 2005. -P.322.

96. Ope, О. Графы и их применение / О. Оре. М.:Мир, 1965. - 174 с.

97. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.:Мир, 1977. - 208 с.

98. Харрари, Ф. Теория графов. / Ф. Харрари. М.:Мир, 1973. - 300 с.

99. Басакер, Р. Конечные графы и сети / Р. Басакер, Т. Саати. М.:Наука, 1974-367 с.

100. Т.Н. Wu, Fiber Network Service Survivability, Artech House, Norwood, MA, 1992.

101. Eswaran, K.P. Augmentation problems / K.P. Eswaran, R.E. Tarjan // SIAM Journal on Computing. 1976. - №5. - P.653-665.

102. Khuller, S. Approximation algorithms for graph augmentation / S. Khuller, R. Thurimella // Journal of Algorithms. 1993. - vol. 14-2. - P. 214-225.

103. Hochbaum, D.S. Approximation Algorithms for NP-Hard Problems / D. S. Hochbaum. PWS Publishing Company, 1997.

104. Hsu, T.-S. Graph augmentation and related problems: theory and practice / T.-S. Hsu. PhD thesis, University of Texas at Austin, 1993. - P. 342.

105. Гэри, M. Вычислительные машины и труднорешаемые задачи / М. Гэри . Д. Джонсон. М.: Мир, 1982. - 419 с.

106. Watanebe, Т. Edge connectivity augmentation problems / Т. Watanebe, A. Nakamura A. // J. Сотр. Systems Sci. 1987. - №35. - P.96-114.

107. Frederickson, G. N. Approximation algorithms for several graph augmentation problems / G. N. Frederickson, J. Ja-Ja // SIAM Journal of Computing. 1981 vol. 10-2. -P. 270-283.

108. Khuller, S. Biconnectivity approximations and graph carvings / S. Khuller, U. Vishkin. //. Journal of the ACM. 1994. -vol. 41(2). - P. 214-235.

109. Garg, N. Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques / N. Garg, V. Santosh, A. Singla. // Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms. 1993. - P. 130-111.

110. Watanebe, T. The k-edge connectivity augmentation problem of weighted graph / T. Watanebe, T. Mashima, S. Taoka // In Proc. 3rd Annual Int'l Symp. on Algorithms and Computations. vol. LNCS #650. - P.387-395.

111. Watanebe, T. Graph augmentation problems for a specified sets of vertices / T. Watanebe, Y. Nagishi, A. Nakamura // In Proc. 1st Annual Int'l Symp. on Algorithms and Computations. vol. LNCS #450. - P.378-387.

112. Ravi, R. When cycles collapse: a general approximation technique for constrained two-connectivity problems / R. Ravi, P. Klein // In Proc. 1st Europian Symp. On Algorithms. 1993.

113. Bang-Jensen, J. Edge-connectivity augmentation with partition constraints Электронный документ. / J. Bang-Jensen, H.N. Gabow, T. Jordan. Режим доступа: http://www.cs.colorado.edu/~hal/Papers/pttn.comp.ps.gz. -21.09.2007.

114. Watanebe, Т. 3-edge connectivity augmentation problem / T. Watanebe, T. Narita, A. Nakamura // In Proc. of 1989 IEEE Int'l Symp. Circuits and Systems. 1989.-P.335-338.

115. Watanebe, T. A linear time augmenting algorithm for 3-edge connectivity augmentation problem / T. Watanebe, M. Yamakado, K. Onaga // In Proc. of 1991 IEEE Int'l Symp. Circuits and Systems. 1991. - p. 1168-1171.

116. Cai, G.R. The minimum augmentation of any graph to a k-edge-connected graph / G.R. Cai, Y.-G. Sun // Networks. 1989. - № 19. - P. 151 -172.

117. Naor, D. A fast algorithm for optimally incresing the edge-connectivity / Naor D., Gusfield D., Martel C. // In Proc. 31th Annual IEEE Symp. on Foundation of Comp.Sci. 1990. -P.698-707.

118. Кормен, Т. X. Алгоритмы: построение и анализ. 2-е издание / Т.Х. Кормен, Ч.И. Лейзерсон, Р.Л. Ривест, К. Штайн. М.: Вильяме, 2005. - 1296 с.

119. Harel, D. Fast algorithms for finding nearest common ancestors / D. Harel, R.E. Tarjan // SIAM Journal on Computing. 1984. - vol. 13-2. - P. 338355.

120. Gabow, H. N. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs / H.N. Gabow, Z. Galil, T. Spenser, R.E. Tarjan // Combinatorica. 1986. - vol. 6-2. - P. 109-122.

121. Седжвик, P. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск / Р. Седжвик. К.: ДиаСофт. - 2001. - 688 с.

122. Седжвик, Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах. Спб.: ДиаСофтЮП. - 2002. - 496 с.

123. Прата, С. Язык програмиирования С++. Лекции и упражнения. Учебник: пер. с анг. / Стивен Прата. СПб.: ДиаСофтЮП. - 2005. - 1104 с.

124. The LEDA Library Электронный документ. Режим доступа: http://www.mpi-inf.mpg.de/LEDA/. 05.06.2005.

125. GTL. The Graph Template Library [Электронный документ]. Режим доступа: http://www.infosun.fim.uni-passau.de/GTL/. - 06.06.2005.

126. The Boost Graph Library Электронный документ./ Режим доступа: http:// www.boost.org/libs/graph/. - 06.05.2006.

127. Edmonds, J. Optium branchings / J.Edmonds // J. Res. Nat. Bur. Standards. 1967. 71B. - P.233-240.

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