WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |

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

НУШТАЕВ Андрей Васильевич ИССЛЕДОВАНИЕ И РАЗРАБОТКА ГРАФОВЫХ МОДЕЛЕЙ ОТКАЗОУСТОЙЧИВЫХ ВИРТУАЛЬНЫХ ЧАСТНЫХ СЕТЕЙ Специальность 05.12.13 – «Системы, сети и устройства телекоммуникаций»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Самара 2007

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

Научный консультант: кандидат технических наук доцент Росляков А.В.

Официальные оппоненты: доктор технических наук профессор Тарасов В.Н.

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

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

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

443010, Самара, ул. Л.Толстого, 23

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

Автореферат разослан «12» октября 2007 г.

Ученый секретарь диссертационного совета Д219.003.02 доктор технических наук, доцент Мишин Д.В.

2

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

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

Поскольку строительство и эксплуатация собственной сети связи – занятие весьма дорогое, на рынке телекоммуникационных услуг появилось решение в виде технологии и услуги виртуальной частной сети 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), ХII Российской НТК ПГАТИ (Самара, 2005), ХIII Российской НТК ПГАТИ (Самара, 2006), VII Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2006), XIV Российской научной конференции ПГАТИ (Самара, февраль 2007).

Публикации. По теме диссертации опубликовано 19 работ, в том числе статьи в журналах из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 15 тезисов и текстов докладов, а также 1 свидетельство о регистрации алгоритмов и программ.

Основные положения, выносимые на защиту:

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

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

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 143 страницы машинописного текста, 47 рисунков и 7 таблиц. Список литературы включает в себя 135 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

Модель формулируется следующим образом. Пусть имеется сеть общего пользования провайдера услуг VPN в виде неориентированного графа GV, E), ( где V – множество вершин, соответствующих маршрутизаторам/коммутаторам сети, а E – множество ребер, соответствующих каналам сети, связывающим эти маршрутизаторы. Будем считать, что каналы сети имеют достаточную полосу для пропуска трафика VPN. Пусть задано множество конечных точек VPN Q V и два вектора Bin и Bout размера Q, элементы которых bin (u) Bin и bout (u) Bout представляют собой верхнюю границу скорости передачи трафика, который конечная точка u Q может получать от всех остальных конечных точек или отправлять ко всем остальным конечным точкам соответственно.

T Пусть на графе G задана виртуальная частная сеть в виде дерева T (ET,V ), T т.е. ET E и V V. На каждом ребре дерева (u,v) T выделена необходимая полоса пропускания b(u,v) в направлении от вершины u к вершине v и полоса пропускания b(v,u) в направлении от вершины v к вершине u. Будем называть ребра дерева (u,v) T защищаемыми ребрами, а выделенную на них полосу – защищаемой полосой пропускания.

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

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»