WWW.DISSERS.RU

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

   Добро пожаловать!

Pages:     | 1 |   ...   | 52 | 53 ||

MPLS является универсальным решением проблем обеспечения заданного уровня QoS, стоящих перед современными сетевыми технологиями, она обеспечивает высокую скорость передачи, масштабируемость, контроль, оптимизацию распределения трафика, а также маршрутизацию [1, 2].

Одной из важных задач, которые приходится решать в процессе проектирования сетей с технологией MPLS является задача обеспечения заданного уровня ее живучести. В работе [4] была рассмотрена задача анализа живучести сетей MPLS, введены показатели живучести сетей и предложен алгоритм их оценки для различных классов потоков. Целью настоящей работы является решение задачи оптимизации сетей с технологией MPLS по установленным ограничениям на показатели живучести сети по критерию минимизации стоимости.

Постановка и математическая модель задачи Задано множество узлов сети X = xj j = 1, n - маршрутизаторов MPLS (так называемых LRS – Label { } Switching Routers), их размещение по территории региона, набор пропускных способностей каналов связи D = d1, d2,..., dk из которых ведется синтез и их удельных стоимостей на длины C = c1,c2,...,ck, { } { } определены классы обслуживания CoS (Class of Service), известны матрицы входящих требований для kго класса H (k) = hij (k) i, j = 1,n ; k = 1, 2,..., K, где hij (k) – интенсивность k-го класса, который необходимо передавать из узла i в узел j в единицу времени (Кбит/с).

Fourth International Conference I.TECH 2006 Кроме того, введены ограничения на показатели качества QoS для каждого класса k в виде ограничения на среднюю задержку Tзад,k, k = 1, K и установлены требования на уровни показателей живучести каждого класса Pk,зад[y].

Требуется найти структуру сети в виде набора каналов связи (КС) E = (r, s), выбрать пропускные { } способности (ПК) каналов связи rs, таким образом, чтобы обеспечить передачу требований всех { } классов H (k) в полном объеме и при этом бы выполнялись ограничения на установленные показатели живучести, а стоимость сети была бы минимальной.

Составим математическую модель данной задачи синтеза.

Требуется найти:

min C(M ) = Crs ( rs ) { } (1) E rs { } (r,s)E при следующих ограничениях на показатели живучести Ф P H (1) aHзад(1) P1,зад { } Ф P H (2) aHзад(2) P2,зад {} (2) --------------P H (k) a%Hзад (k) Pr,зад Ф {} Ф где H (k) - фактическая величина потока к-го класса, передаваемого в сети при отказах; ее элементов (каналов и узлов связи)., (0) H - величина номинального потока к-го класса,в безотказном состоянии.

В работе [5] для потока k-го класса; при условии что обслуживание в классах происходит с относительными приоритетами k в порядке убывания номера класса (т.е. 1 > 2 >... > k ) при ( заданном наборе ПС каналов rs и распределении потоков (РП) – F(k) = [ frsk )] было получено { } следующее выражение для средней задержки Tср,k :

K ( ( frsk ) frsi) i=Tср,k ( rs, F) = { } (3) ( Hk ) (r,s)E (rs - K -1 frsi))(rs - K frsi)) ( ( i=1 i=K ( при условии, что суммарная величина потока в канале (r,s) удовлетворяет условию frsi) = frs < rs i=( где frsi) - величина потока класса i в КС ( r, s ).

В работе [4] была рассмотрена задача анализа живучести компьютерных сетей с технологией MPLS,, введены показатели живучести и предложен алгоритм оценки показателей живучести (ПЖ) сетей для разных классов сервиса при отказах её элементов – каналов и узлов связи (КС).

В данной работе ставится задача оптимизации структуры сетей по заданным значениям ПЖ.

Networks and Telecommunications Описание алгоритма оптимизации структуры при ограничениях на заданные уровни ПЖ Пусть одним из известных методов, например предложенным в работе [3] получена базовая структура сети E в виде набора каналов (r,s) заданной пропускной способности, обеспечивающих передачу всех категорий требований в полном объеме в безотказовом состоянии.

Цель алгоритма – оптимизация структуры при ограничениях на заданные уровни ПЖ Pk,зад.приотказах ее элементов.

Перед началом этапа (0 шаг) рассчитываем начальные значения ПЖ для всех классов: требований Ф P H (k) a%H k = 1, K a 50 100 % { } [ ] Для этого используем алгоритм оценки ПЖ, предложенный в [4].

Далее проверяем выполнение ограничений:

Ф P H (k) a%H Pka (4) { },зад Если условие (4) выполняются для всех классов k = 1, K и всех уровней a 50 100 %, то конец [ ] работы алгоритма, иначе переход на 1-ю итерацию.

Цель каждой итерации состоит в повышении текущих значений ПЖ, путем резервирования соответствующих каналов и узлов.

Пусть заданы надежностные характеристики каналов (КС) и узлов связи (УС) – коэффициенты готовности КС (r,s), kГrs - коэффициент готовности і-го УС kГi i = 1, n.

Пусть zi - отказовое состояние, состоящее в отказе КС (ri, si ).

Тогда вероятность его появления определится согласно [4] так n P(zi ) = (1- kГrs ) П kГrs (5) kГi i i (r,s)(ri,si ) i=Допустим, что мы резервируем КС (ri, si ). Тогда вероятность состояния zi после резервирования определяется так:

n Pрез (zi ) = (1- kГrs )2 П kГrs (6) kГi i i (r,s)(ri,si ) i=Изменение этой величины равно n P(z0) = Pрез (zi ) - P(zi ) = -kГrs (1- kГrs ) kГrs = -kГrs P(zi ) (7) kГi i i i i i i (r,s)(ri,si ) i=Будем оценивать эффект от резервирования КС (ri, si ) так P(zi ) rs =- (8) i i Cрез (ri, si ) где Cрез (ri, si ) - стоимость резервирования КС (ri, si ).

Fourth International Conference I.TECH 2006 Разбиваем все множество отказовых состояний на подмножества Z1 = zi, Z2 = z, Z3 = zs, { } { } { } j Z4 = zr и Z5 = zt, где zi Z1, если максимальный поток в состоянии zi H(zi ) < 90%H ;

{ } { } 0 zj Z2, если H (z ) < 80%H ; zs Z3, если H (zs ) < 70%H ; zr Z4, если j 0 H(zr ) < 60%H ; и наконец zt Z5, если H (zt ) < 50%H.

Очевидно между данными подмножествами имеется следующее отношение включения:

Z5 Z4 Z3 Z2 Z1.

Поэтому для резервирования выбираем в первую очередь состояния zk Z5 (т.е. наибольшие критические отказовые состояния).

1-я итерация Рассматриваем состояние zi Z5, представляющее отказ КС (ri, si ).

1. Для всех КС (ri, si ) вычисляем эффект от резервирования rs согласно (8).

i i * 2. Выбираем КС (ri*, si ) с максимальным показателем эффективности.

r si = maxrs * * (9) i i i 3. Резервируем КС (ri*, si*) и пересчитываем ПЖ сети после резервирования Ф 0 Ф P(н) H (k) a%H (k) = P H (k) a%H (k) + P(zi*) для всех k = 1, K { } { } (10) где zi* - состояние отказа КС (ri*, si*).

4. Проверка ограничений на показатели живучести:

Ф P(н) H (k) a%H (k) Pk,зад для всех k = 1, K (11) { } Если условия (11) выполняются для всех К, то STOP конец работы алгоритма, иначе переход к следующей итерации. Указанные итерации повторяем до тех пор, пока условия (11) не начнут выполнятся для всех К.

Конец работы алгоритма.

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

Заключение 1.В работе сформулирована задача структурной оптимизации сетей MPLS по ограничениям на показатели живучести сети.

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

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

2.Олвейн Вивьен. Структура и реализация современной технологии MPLS. Перевод с английского. Изд. дом «Вильямс», 2004. 480 с.

3.Зайченко Е. Ю. Сети ATM: Моделирование, анализ и оптимизация. Киев, 2003. 216 с.

4.Зайченко Ю.П., Мухаммедреза Моссавари. Анализ показателей живучести компьютерной сети с технологией MPLS. Вісник національного технічного університету «КПІ». Сер. Інформатика, управління та обчислювальна техніка. N43 ВЕК+ 2005. с. 73 - 80.

5.Зайченко Ю.П., Шарадка Ахмед. Задача распределения потоков различных классов в сети с технологией MPLS.

Вісник національного технічного університету «КПІ». Інформатики, управління та обчислювальна техніка №43.

2005. с.113 –Authors’ Information Зайченко Юрий Петрович – НТУУ Киевский политехнический институт, профессор, Киев-56, Проспект Победы 37, тел 38-044-2418693, e-mail: zaych@i.com.ua Мухаммедреза Моссавари (Иран) – НТУУ Киевский политехнический институт, аспирант, Киев-56, Проспект Победы 37, тел.8-067-7099053, e-mail: olgamax@mmsa.ntu-kpi.kiev.ua ОПТИМИЗАЦИЯ ХАРАКТЕРИСТИК СЕТЕЙ MPLS ПРИ ОГРАНИЧЕНИЯХ НА ЗАДАННЫЕ ПОКАЗАТЕЛИ КАЧЕСТВА ОБСЛУЖИВАНИЯ Юрий П. Зайченко, Ахмед А. М. Шарадка Аннотация: В докладе сформулирована задача оптимизации характеристик сетей с технологией MPLS, включающая оптимальный выбор пропускных способностей и распределение потоков (ВПС РП).

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

Abstract: The problem of MPLS networks analysis and optimization – including optimal capacities assignment and flows distribution is considered in this paper. The corresponding algorithm of its solution is suggested enabling to choose optimal channel capacities and distribute flows of all classes minizing the network cost under constraints on quality of service (QoS). The experimental investigations of the suggested algorithm are presented.

Keywords: MPLS networks, optimization, capacities assignment, flows distribution.

Fourth International Conference I.TECH 2006 Введение К современным телекоммуникационным (сетевым) технологиям предъявляются требования передачи разных видов информации (аудио, видео и данных) по общим каналам связи с помощью унифицированного транспортного механизма и обеспечения при этом заданного качества обслуживания (Quality of Service) – а именно средней задержки T, и её вариации. Существующие сетевые технологии ср такие, как IP, Ethernet, Frame Relay, Token Ring не в состоянии обеспечить требуемое качество обслуживания. Технологий АТМ, которая была разработана для решения указанной проблемы качества, оказалась дорогостоящей и не смогла выдержать конкуренции с технологией Gigabit Ethernet и IP.

Поэтому на смену ей в конце 90-х годов была создана новая технология многопротокольной коммутации меток (Multiprotocol Label Switching-MPLS). Её отличительными способностями являются: 1) введение различных категорий потоков классов обслуживания (Class of Service); 2) возможность обеспечения заданного качества обслуживания QoS для разных категорий; 3) предоставление единого транспортного механизма для передачи разных видов информации и наконец возможность работы с различными сетевыми технологиями и протоколами (Frame Relay, Ethernet, IP, ATM). [1] Важными задачами которые приходится решать в процессе построения сетей MPLS являются задача анализа и оптимизации их характеристик, и в частности, оптимальный выбор пропускных способностей каналов связи и распределение потоков различных классов по каналам (РП).

В работе [2] была рассмотрена задача оптимального выбора ПС каналов связи (ВПС) при ограничениях на установленные значения показателей качества обслуживания (QoS), а именно средней задержки для различных классов потоков и описан алгоритм её решения.

В работе [3] исследована задача оптимального распределения потоков различных каналов в сети MPLS при ограничениях на показатели QoS и предложен соответствующий алгоритм РП. Целью настоящей работы является обобщение полученных результатов, постановка и формализация комбинированной задачи ВПС РП, и разработка алгоритма её решения.

Постановка и математическая модель задачи Задана сеть MPLS со структурой G = (X, E), где X = xj j =1, n – множество узлов сети (УС);

{ } E = (r, s) – множество КС; задан набор пропускных способностей D = d1, d2,..., dK и их удельных { } { } стоимостей C = c1,c2,...,cK.

{ } Определено число классов потоков k = 1, K, заданы матрицы требований входящих потоков H (k) = hij (k) i, j = 1,n, где hij (k) – интенсивность потока, который необходимо передавать из УС xi в xj (Мбит/с). Установлены требования по обеспечению заданного показателя качества (QoS) – Tср,k.

Требуется выбрать такие ПС всех КС rs и найти распределение потоков всех классов F(k) frs (k) { } [ ] при которых стоимость сети будет минимальна, а средняя задержка для каждого класса не будет превышать заданную величину Tср,зад.

Составим математическую модель данной задачи.

Networks and Telecommunications Требуется найти min C = crs (rs ) (1) (r,s)E при условиях k ( ( frsk ) frsi) ( i=Tсрk )( rs ) = Tзад,к (2) { } ( k -1 k Hk ) (r,s)E ( ( rs - frsi) rs - frsi) i=1 i=k ( (r, s) E frsi) < rs для всех k = 1, k (3) i=rs D ( где frsi) - многопродуктовый поток і-го класса, протекающий по КС (r,s), предполагается что обслуживание потоков в узлах сети (коммутаторах) с относительными приоритетами, приоритеты i убывают с ростом номера класса, т.е. 1 > 2 >... > k.

Описание алгоритма решения Алгоритм состоит из предварительного этапа и конечного числа однотипных итераций.

На предварительном этапе находятся начальные ПС каналов связи ( rs (0) ) и начальное { } распределение потоков всех классов Fk (0), k = 1, k.

Цель последующих итераций – оптимизация ВПС и РП по критерию стоимости.

Пусть проведено r итераций и найдены ПС rs (r), распределение потоков F(k) frs (r) и стоимость { } [ ] сети C (r).

(r+1)я-итерация 1. Решаем задачу РП по критерию minTср1 используя алгоритм предложенный в [1] и находим Fk (r +1).

2. Решаем задачу ВПС по критерию min C для РП Fk (r +1) при ограничениях Tср (k) Tзад,k и находим rs (r +1).

{ } 3. Вычисляем величину критерия C (r +1) и проверка условия [C (r) - C(r +1)] <. Если да, то STOP распределение потоков Fk (r +1) и ПС rs (r +1) – искомые, иначе r = r +1 и на шаг { } следующей итерации.

Экспериментальные исследования алгоритма ВПС РП Предложенный алгоритм был реализован программно и были проведены эксперименты по анализу его эффективности.

В экспериментах рассматривалась сеть с n = 10 узлов и m = 16 каналов связи. Структура сети задавалась случайным набором каналов связи:

{(1,6); (1,9); (2,3); (2,4); (2,6); (3,4); (4,5); (4,6); (4,7); (5,6); (5,10); (6,9); (7,8); (7,10); (8,9); (9;10)}.

Fourth International Conference I.TECH 2006 Число классов сервиса к=6.

Набор базовых ПС каналов связи Д задается в таблице 1, а их удельная стоимость – в таблице 2.

Pages:     | 1 |   ...   | 52 | 53 ||



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

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.