WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 |

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

Выберем для определенности направление в цикле uv, сориентируем ребра цикла uv в соответствие с выбранным направлением и таким образом получим контур uv, в котором любое ребро (x, y) направлено от x к y. Бу дем считать, что ребро f = (x, y) и ребра (u,v) P( f ) направлены одинаково в соответствующих контурах (т.е. от x к y и от u к v ). Величина защитной полосы пропускания, которая должна быть выделена на этом ребре f = (x, y), определяется по следующим выражениям:

bзащ (x, y) = ma {b(v,u)}, (1) x (u,v)P( f ) bзащ ( y, x) = ma {b(u,v)}. (2) x (u,v)P( f ) В общем случае выделение дополнительной полосы пропускания может быть необходимо еще и на ребрах дерева T. Пусть произошел отказ на ребре (u,v) T и определен некоторый путь pxy в G - T, так что f pxy справед ливо P( f ) (u,v). В этом случае все ребра f pxy, а также ребро (u,v) T входят в цикл.

xy Тогда в рамках стратегии защиты звена на ребрах (i, j) T - (u,v) xy доп необходимо дополнительно выделить полосу пропускания buv (i, j) = b(v,u) и доп buv ( j,i) = b(u,v). При этом также будем считать, что ребро (u,v) и ребра (i, j) T - (u,v) направлены одинаково в контуре.В целом же, учитыxy xy вая все ребра (u,v) T, получим следующие выражения:

защ доп bT (i, j) = max {buv (i, j)}, (3) (u,v)T -(i, j) защ доп bT ( j,i) = max {buv ( j,i)}. (4) (u,v)T -(i, j) Для стратегии защиты пути полоса пропускания, которую необходимо дополнительно выделить на ребрах (i, j) T - (u,v), определяется соотношениями:

доп buv (i, j) = max min bout (i), bin ( j) - b(i, j) (5) 0, iQTuv (i, j) jQTuv ( j,i) доп buv ( j,i) = max min bin (i), bout ( j) -b( j,i) (6) 0, iQTuv (i, j) jQTuv ( j,i) Здесь Tuv = T - (u,v) + pxy, так что f pxy справедливо P( f ) (u,v). В целом же, учитывая все ребра (u,v) T, получим следующие выражения:

защ доп bT (i, j) = max {buv (i, j)}, (7) (u,v)T -(i, j) защ доп bT ( j,i) = max {buv ( j,i)}. (8) (u,v)T -(i, j) Применение выражений (1)-(8) для различных фрагментов VPN проиллю стрировано на рис.3. Для ребра f = (x, y) на рис.3а P( f ) = {(u,e),(e,v)}, поэтому защитная полоса на этом ребре равна bзащ (x, y) = max{b(v,e),b(e,u)} = 2, а bзащ (y, x) = max{b(e,v),b(u,e)} = 3. На рис.3б и рис.3в путь pue является защитным для ребра (u, x), а путь pxv – для ребер (x,e) и (e,v). При стратегии защиты звена (рис.3б) трафик от u к v при отказе (x,e) пойдет по маршруту защ доп доп (u, x),(x,v),(v,e),(e,v). Тогда: bT (x,e) = max{bux (x,e),bev (x,e)} = max{4,1} = 4 согласно (3). При стратегии защиты пути (рис.3в) трафик от u к v при отказе (x,e) будет передаваться по маршруту (u, x),(x,v). Тогда доп доп bux (x,e) = max 0, 0 -1 = 0 и bev (x,e) = max 0, 2 -1 = 1 согласно (5), а { } { } защ bT (x,e) = max{0, 1} = 1 согласно (7).

uv Рис.3. Пример расчета полосы пропускания Для обеспечения отказоустойчивости VPN требуется определить множество защитных ребер F G - T и величину выделенной на каждом ребре f = (x, y) F защитной полосы пропускания bзащ (x, y) и bзащ ( y, x), а также величину выделенной на каждом ребре дерева e = (i, j) T дополнительной зазащ защ щитной полосы пропускания bT (i, j) и bT ( j,i), так чтобы при отказе любого ребра дерева (u,v) T существовал путь puv, такой, что граф T - (u,v) + puv является деревом Tuv.

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

защ защ защ b (x, y) + bзащ (y, x) + (i, j) + bT ( j,i) min (9) bT ( x, y)F (i, j)T При этом маршрутизация трафика в каждом дереве Tuv, а также величина защитной полосы пропускания на ребрах дерева определяется в соответствие с выбранной стратегией защиты.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сделаем сначала необходимые пояснения. Во-первых, будем называть трафик ребер прямым, если он направлен в сторону корня дерева, трафик противоположного направления будем называть обратным. Отметим, что в алгоритмах для асимметричной модели строятся два графа G и вычисляется два пополнения – соответственно, для прямого трафика и обратного трафика.

Для прямого трафика все ребра дерева будут направлены к корню, а все ос тальные ребра графа G будут направлены в сторону вершин-потомков. Для обратного трафика, наоборот, все ребра дерева будут направлены от корня, а все остальные ребра графа G будут направлены в сторону вершин-предков.

Рассмотрим пополнение для прямого трафика и некоторое ребро ( x, (x, y) A. Пусть данному ребру соответствует путь puv y) G - T – путь в графе G - T между вершинами u,v T, который, в конечном счете, и привел к добавлению ребра (x, y) в граф G.

( x, Будем считать, что соответствующий контур uv y) ориентирован, так же ( x, как и ребра множества uv y) P(x, y). Следовательно, требование ребра ( x, ( x, (x, y) A к защитной полосе пропускания на ребрах uv y) puv y) (т.е. на ребрах графа G - T ) равно w(x, y) / w(u,v). Под wu,v) и wu,v) понимаются ( ( веса ребер (u,v) G и (u,v) G соответственно. В целом же:

w(x, y) bзащ ( j,i) = max. (10) ( x,y ( x, y) : (x, y) A, (i, j) puv ) wu,v) ( При этом считается, что ребра (i, j) ориентированы так же, как и соответ( x, ствующий им контур uv y).

Требование ребра (x, y) A к защитной полосе пропускания на ребрах ( x, ( x, (s,t) uv y) - puv y) (т.е. на ребрах T ) равно w(x, y) / w(u,v). В целом же:

w(x, y) защ bT (t, s) =- b(t, s). (11) max 0, ( x,y ( x, y) : ( x, y) A, (s,t )uv ) wu,v) ( При этом считается, что ребра (s,t) ориентированы так же, как и соответ( x, ствующий им контур uv y).

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

w(x, y) bзащ (i, j) = max, (12) ( x,y ( x, y) : (x, y) A, (i, j) puv ) wu,v) ( w(x, y) защ bT (s,t) = max 0, - b(s,t). (13) ( x,y ( x, y) : ( x, y) A, (s,t )uv ) wu,v) ( Для стратегии защиты пути распределение защитной полосы пропускания на ребрах дерева T производится согласно выражениям (5)-(8).

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

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

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

180 60 0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Число конечных точек 2 3 4 5 6 7 8 10 12 14 16 18 20 22 24 26 Число конечных точек Дерево Sym Дерево Asym Защита звена Sym Дерево Алгоритм А Алгоритм Б Алгоритм В Алгоритм Г Защита звена Asym Защита пути Sym Защита пути Asym Полоса проускания, усл.ед.

Полоса проускания, усл.ед.

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

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

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

0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Число конечных точек Число конечных точек Дерево Защита звена Защита пути Защита звена Защита пути Рис.7 Экономия защитной полосы про- Рис.8. Экономия суммарной полосы пропускания пускания Экономия защитной полосы пропускания при учете асимметричности трафика конечных точек VPN составляет порядка 20-30%. Суммарная экономия полосы пропускания с учетом как полосы пропускания VPN, так и защитной полосы пропускания, составляет 24-30%, что в итоге можно считать результатом, достаточным для использования асимметричной модели на практике.

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

ЗАКЛЮЧЕНИЕ В целом, по итогам работы можно сформулировать следующие основные полученные результаты:

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

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

Pages:     | 1 || 3 |






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