Исследование и разработка графовых моделей отказоустойчивых виртуальных частных сетей тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Нуштаев, Андрей Васильевич

• Нуштаев, Андрей Васильевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Нуштаев, Андрей Васильевич

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 от одиночных отказов звеньев сети.

Список литературы диссертационного исследования кандидат технических наук Нуштаев, Андрей Васильевич, 2007 год

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 с.