Структурный синтез компьютерных сетей с технологией MPLS
Сформулирована задача синтеза структуры сетей MPLS с ограничениями на заданные показатели качества сервиса. Построена математическая модель задачи и предложен генетический алгоритм структурного синтеза, позволяющий оптимизировать структуру сети MPLS по критерию стоимости при ограничениях для различн...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2006 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2006
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/42199 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Структурный синтез компьютерных сетей с технологией MPLS / Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин // Систем. дослідж. та інформ. технології. — 2006. — № 4. — С. 65–70. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860203938872033280 |
|---|---|
| author | Зайченко, Е.Ю. Зайченко, Ю.П. Ашраф Абдель Хилал Карим Абу-Аин |
| author_facet | Зайченко, Е.Ю. Зайченко, Ю.П. Ашраф Абдель Хилал Карим Абу-Аин |
| citation_txt | Структурный синтез компьютерных сетей с технологией MPLS / Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин // Систем. дослідж. та інформ. технології. — 2006. — № 4. — С. 65–70. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Сформулирована задача синтеза структуры сетей MPLS с ограничениями на заданные показатели качества сервиса. Построена математическая модель задачи и предложен генетический алгоритм структурного синтеза, позволяющий оптимизировать структуру сети MPLS по критерию стоимости при ограничениях для различных классов потоков.
Сформульовано задачу синтезу структури мереж MPLS з обмеженнями на задані показники якості серверу. Побудовано математичну модель задачі і запропоновано генетичний алгоритм структурного синтезу, що дозволяє оптимізувати структуру мережі MPLS за критерієм вартості при обмеженнях для різних класів потоків.
The problem of structural synthesis of MPLS networks is formulated. A mathematical model of the problem is elaborated and a genetic algorithm for the structural synthesis is suggested, which makes it possible to optimize the MPLS structure by cost criterion at limited flows of different types.
|
| first_indexed | 2025-12-07T18:11:36Z |
| format | Article |
| fulltext |
© Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин, 2006
Системні дослідження та інформаційні технології, 2006, № 4 65
TIДC
ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО
ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ ТА
МЕРЕЖІ
УДК 681.513
СТРУКТУРНЫЙ СИНТЕЗ КОМПЬЮТЕРНЫХ СЕТЕЙ С
ТЕХНОЛОГИЕЙ MPLS
Е.Ю. ЗАЙЧЕНКО, Ю.П. ЗАЙЧЕНКО,
АШРАФ АБДЕЛЬ ХИЛАЛ КАРИМ АБУ-АИН
Сформулирована задача синтеза структуры сетей MPLS с ограничениями на
заданные показатели качества сервиса. Построена математическая модель за-
дачи и предложен генетический алгоритм структурного синтеза, позволяющий
оптимизировать структуру сети MPLS по критерию стоимости при ограниче-
ниях для различных классов потоков.
ВВЕДЕНИЕ
В последние годы в связи с резким возрастанием объемов передаваемой ин-
формации и ее видов (данные, аудио и видеоинформация) возникла необхо-
димость в разработке новой технологии, обеспечивющей заданное качество
сервиса QоS (Quality of Service), и перечня услуг для пользователей. Извест-
ные коммуникационные технологии (Ethernet, Frame Relay, IP) не позволяют
реализовать заданное качество обслуживания и требуемый уровень QoS. По
мере расширения мультимедийных приложений и телеконференций, тре-
бующих более высоких скоростей передачи и более широкой полосы про-
пускания, возникла необходимость в новой технологии, обеспечивающей
единый транспортный механизм передачи QоS, работающий «поверх» са-
мых разнообразных технологий, таких как Ethernet, Frame Relay, ATM,
SONET, и обеспечивающий высокоскоростную передачу информации с
требуемым качеством. Такой технологией является технология много-
протокольной коммутации меток — MPLS (Multiprotocol Label Switching).
MPLS — универсальное решение проблем обеспечения QoS, стоящих перед
современными сетевыми технологиями. Она реализует высокую скорость
передачи, масштабируемость, контроль и оптимизацию распределения тра-
фика и маршрутизацию [1, 2].
Одной из важных задач, стоящих перед проектировщиками сетей с тех-
нологией MPLS, является задача структурного (топологического) синтеза
сети под заданную входящую нагрузку, в результате которого определяются
общая структура сети, типы каналов связи, их пропускные способности,
распределение потоков при ограничениях на заданный уровень QoS для по-
токов различных классов обслуживания (Class of Service) по критерию
Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 66
стоимости. При этом в качестве дополнительных ограничений могут высту-
пать показатели надежности и живучести сети.
Ранее задачи структурного синтеза сети с перспективными техноло-
гиями рассматривались для сетей с технологией ATM (Asynchronous Trans-
fer Mode) [3, 4]. Был разработан и исследован достаточно эффективный ал-
горитм оптимизации структурного синтеза, учитывающий специфику
технологии ATM, в частности наличие нескольких категорий сервиса CBR,
VBR и ABR.
Цель настоящей статьи — постановка и формализация задачи синтеза
структуры сетей с технологией MPLS и разработка соответствующего алго-
ритма ее решения.
ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ
Основные особенности технологии MPLS.
1. Введение различных классов потоков (классов сервиса — CoS). Ка-
ждый класс имеет свой приоритет в обслуживании, которое реализуется в
маршрутизаторах MPLS [1,2].
2. В данной технологии вводятся показатели QoS, в частности, средняя
задержка, ее вариация и доля потерянных ячеек. Для каждого класса пото-
ков устанавливаются свои значения QoS. Основная функция сети MPLS —
обеспечение установленных показателей качества, поэтому при решении
задач анализа и синтеза сетей с технологией MPLS соответствующие моде-
ли оценки показателей QoS должны учитывать указанные выше особенно-
сти технологии MPLS.
Имеется несомненная зависимость между числом классов потоков, ус-
тановленными показателями QoS для классов потоков и результатами син-
теза структуры сетей, так как синтезируемая топология сети должна обеспе-
чить передачу всех классов входящих потоков с заданными показателями
при минимальной стоимости.
Рассмотрим постановку и математическую модель задачи структурного
синтеза.
Задано множество узлов сети { }jxX = , nj ,1= — маршрутизаторов
MPLS (так называемых LSR — Label Switching Routers), их размещение по
территории региона, набор пропускных способностей каналов связи
{ }kdddD ,...,, 21= , из которых ведется синтез, и их удельных стоимостей на
единицу длины { }kcccC ,...,, 21= , определены CoS, известны матрицы вхо-
дящих требований для потока k-го класса )()( khkH ij= , nji ,1, = ;
Kk ,...,2,1= , где )(khij — интенсивность потока k -го класса, который не-
обходимо передавать из узла i в узел j в единицу времени (Кбит/с).
Кроме того, введены ограничения на показатели QoS для каждого клас-
са k в виде ограничения на среднюю задержку kT ,зад , Kk ,1= .
Требуется найти структуру сети в виде набора каналов связи (КС)
{ }),( srE = , выбрать пропускные способности (ПС) каналов связи { }rsµ и
найти распределение потоков всех классов )]([)( kfkF rs= таким образом,
Структурный синтез компьютерных сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2006, № 4 67
чтобы обеспечить передачу требований всех классов )(kH в полном объеме
и с задержками срT , не превышающими заданные задT при минимальной
стоимости сети.
Составим математическую модель данной задачи синтеза.
Требуется найти
{ }
{ }∑
∈
Σ =
Esr
rsrsE
CMC
rs ),(
)()(min µ
µ
(1)
при условиях
{ } { } krsrs TfT ,задср );( ≤µ Kk ,1= , (2)
rsrsf µ< для всех ),( sr , (3)
Drs ∈µ . (4)
В работе [5] для потока k-го класса при условии, что обслуживание в
классах происходит с относительными приоритетами kρ в порядке убыва-
ния номера класса (т.е. kρρρ >>> ...21 ) при заданном наборе ПС каналов
{ }rsµ и распределении потоков (РП) ][)( )(k
rsfkF = , получено следующее
выражение для средней задержки kT ,ср :
{ } ∑
∑∑
∑
∈
=
−
=
=
Σ −−
=
Esr
K
i
i
rsrs
K
i
i
rsrs
K
i
i
rs
k
rs
krsk
ff
ff
H
FT
),(
1
)(
1
1
)(
1
)()(
)(,ср
))((
1),(
µµ
µ (5)
при условии rsrs
K
i
i
rs ff µ<=∑
=1
)( , где )(i
rsf — величина потока класса i в КС
( sr, ).
Данная задача синтеза относится к классу комбинированных задач дис-
кретного программирования и является NP-полной. Поэтому для ее решения
предлагается генетический алгоритм структурного синтеза.
ОПИСАНИЕ АЛГОРИТМА СТРУКТУРНОГО СИНТЕЗА
Алгоритм состоит из двух этапов: предварительного и основного.
Предварительный этап. Синтезируется N начальных структур
{ })0(),...,0(),...,0(1 Ni EEE .
Сначала из исходных узлов { }nxxxX ,...,, 21= синтезируется кратчай-
шее связывающее дерево (КДС), для чего используется известный алгоритм
Исау-Вильямса. Здесь в качестве корня дерева 0D выбирается узел *i с наи-
большей суммарной интенсивного информационного обмена с остальными.
∑
=
→=
n
j
ijii
hHx
1
max:* .
Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 68
Далее случайным образом, используя процедуру «Ввод ребра», струк-
тура 0D дополняется до заданной степени избыточности, и на ее основе ге-
нерируется N начальных многосвязных структур { })0(),...,0(),...,0(1 Ni EEE ,
где N — размер популяции (подбирается экспериментально). В данном ва-
рианте принимаем 53…=N .
Далее переходим к основному этапу.
Основной этап cостоит из однотипных итераций, на каждой из кото-
рых осуществляется оптимизация одной текущей структуры в памяти.
)1( +k -я итерация.
Допустим в результате k -й итерации построена текущая популяция
{ })(),...,(),...,(1 kEkEkEП Ni= . Обозначим ))(( kEC iΣ величину критерия
для структуры )(kEi .
1. Выбираем структуру )(kEi для модификации с вероятностью
)(kpi , обратно пропорциональной )( iECΣ .
∑
=
−
Σ
−
Σ= N
i
i
i
i
EC
kEC
kp
1
1
1
)(
))((
)( . (6)
2. Определяем множество КС претендентов на удаление )(уд kR
i
по ус-
ловиям сохранения заданной связности и множество КС претендентов на
ввод )(,вв kR i для структуры )(kEi .
3. Вычисляем показатель неэффективности
)()1(
rs
rsrs
rsrsrsrs
f
CCq
µ
µ
ρ
−
=−= (7)
для КС )(),( уд kRsr
i
∈ и с вероятностями
∑
∈
=
уд),( Psr
rs
rs
rs q
q
q выбираем канал
*)*,( sr , удаляем его из структуры )(kEi и получаем =)()н( kEi
*)*,(\)( srkEi= .
4. Решаем задачу выбора пропускных способностей и распределения
потоков (ВПСРП) для структуры )()н( kEi , используя алгоритм ВПС, пред-
ложенный в работе [5], и РП в [6], находим новые ПС { })()н( krsµ и РП
)]([)( )н()н( kfkF rs= . Вычисляем ее стоимость { }( ))н()н(
rsСC µΣΣ = .
5. Сравниваем. Если
( ))()()н( kEСkC iΣΣ < , (8)
то полагаем )()1( )н( kEkE ii =+ и записываем структуру )1( +kEi вместо
)(kEi в популяцию П. И конец итерации )1( +k . Иначе на шаг 6.
Структурный синтез компьютерных сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2006, № 4 69
6. Восстанавливаем структуру ( )iE k и удаляем КС *)*,( sr из списка
претендентов.
*)*,(\)()( удуд srkRkR
ii
= .
7. Анализируем множество КС — )(,вв kR i . Рассчитываем для них по-
казатели эффективности от ввода в структуру КС ),( ji .
ijijij CПCG −= )(вв , (9)
где ∑
∈
=
ijПsr rs
ji
rs
rsrsij f
f
fCПC
),(
),(
)()( — стоимость передачи информации меж-
ду узлами i и j по маршруту ijП в структуре )(kEi ; ijC — стоимость вве-
дения нового КС ),( ji ; ),(
),(
ji
srf — доля трафика в КС ),( sr между узлами
),( ji ; rsf — суммарный трафик в КС ),( sr .
8. Выбираем с вероятностями
∑
∈
=
вв),(
вв
Pji
ij
ij
ij G
G
P из множества )(вв kR
i
КС *)*,( ji и вводим его в структуру )(kEi . Получаем структуру =)(
)н(
kE i
*)*,()( jikEi ∪= .
9. Решаем задачу ВПСРП для структуры
)н(
iE , используя алгоритмы
ВПС и РП, находим новые ПС { })()н( krsµ и потоки { })()н( kf rs , а также стои-
мость новой сети ∑
∈
ΣΣ =⎟
⎠
⎞⎜
⎝
⎛=
)н(
),(
)н()н()н( ))(()()(
iEsr
rsi kkEСkC µ .
10. Проверяем условие: если
( ))()()н( kEСkC iΣΣ < , (10)
то фиксируем структуру )1()(
)н(
+= kEkE ii , записываем )1( +kEi вместо
)(kEi в текущую популяцию П. Конец итерации.
11. Восстанавливаем прежнюю структуру )(kEi и удаляем КС *)*,( ji
из списка претендентов: *)*,(\)()( вввв jikRkR
ii
= и переходим на шаг 1.
Повторим шаги 111… со структурами из популяции П до тех пор, пока
либо не выполнится одно из двух условий: ( ))())(()н( kEСkEC ii ΣΣ < , и тогда
конец итерации )1( +k , либо списки претендентов на удаление и ввод
будут исчерпаны: 0)(вв =kR
i
; 0)(уд =kR
i
для всех Ni ,1= . Тогда выбира-
ем из популяции )(kП наилучшую структуру )(* kE
i
: =Σ ))(( * kEC
i
))((min kEC i
i
Σ= , и конец работы алгоритма.
Данный алгоритм является генетическим. Он сходится к некоторому
субоптимальному решению за конечное число итераций, благодаря конеч-
Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 70
ности множеств каналов претендентов на удаление и ввод. Использование
основных идей генетического метода оптимизации, а именно: популяция из
текущих структур, введение вероятностных механизмов для выбора режи-
мов изменения структуры (ввод канала, его удаление и замена), повышает
вероятность нахождения глобального минимума.
Вычислительная сложность алгоритма )( 22 knmON = , где m — число
каналов; n — число узлов сети; k — размеры популяции.
Данный алгоритм был реализован программно. Проведены его экс-
периментальные исследования в задаче синтеза структуры глобальной
компьютерной сети Украины с числом узлов 25=n ; 39=m (начальное
число каналов).
В результате проведенных исследований установлено, что применение
предложенного алгоритма структурного синтеза позволяет снизить стои-
мость сети по сравнению с базовым вариантом на %2520… .
ВЫВОДЫ
1. Сформулирована задача синтеза структуры сетей с технологией
MPLS, отличающаяся от известных постановок учетом специфики техноло-
гии MPLS, в частности, наличием нескольких классов потоков и введением
соответствующих показателей качества сервиса, которые должны быть
обеспечены синтезируемой сетью.
2. Предложен генетический алгоритм структурного синтеза сетей
MPLS, позволяющий оптимизировать структуру сети MPLS по критерию
стоимости при ограничениях на установленные значения средней задержки
для различных классов потоков.
ЛИТЕРАТУРА
1. Гольдштейн А.Б., Гольдштейн Б.С. Технология и протоколы MPLS. — СПб.:
БХВ, 2005. — 304 с.
2. Вивьен О. Структура и реализация современной технологии MPLS / Пер. с
англ. — М.: Изд. дом «Вильямс», 2004. — 480 с.
3. Зайченко О.Ю. Структурний синтез глобальних мереж з технологією ATM за
заданими показниками якості обслуговування // Наук. вісті НТУУ «КПІ».
— 2001. — № 5. — C. 5–11.
4. Зайченко Е.Ю. Сети ATM: Моделирование, анализ и оптимизация. — Киев:
ВІПОЛ, 2003. — 216 с.
5. Зайченко Ю.П., Хамуди Мухаммед Али-Аззам. Оптимальный выбор пропуск-
ных способностей каналов связи в сети с технологией MPLS // Вісник
НТУУ «КПІ». Інформатика, управління та обчислювальна техніка. — 2005.
— № 43. — С. 196–201.
6. Зайченко Ю.П., Ахмед Шарадка. Задача распределения потоков различных
классов в сети с технологией MPLS // Вісник НТУУ «КПІ». Інформатика,
управління та обчислювальна техніка. — 2005. — № 43. — С. 113–123.
Поступила 31.03.2006
|
| id | nasplib_isofts_kiev_ua-123456789-42199 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T18:11:36Z |
| publishDate | 2006 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Зайченко, Е.Ю. Зайченко, Ю.П. Ашраф Абдель Хилал Карим Абу-Аин 2013-03-12T20:02:15Z 2013-03-12T20:02:15Z 2006 Структурный синтез компьютерных сетей с технологией MPLS / Е.Ю. Зайченко, Ю.П. Зайченко, Ашраф Абдель Хилал Карим Абу-Аин // Систем. дослідж. та інформ. технології. — 2006. — № 4. — С. 65–70. — Бібліогр.: 6 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42199 681.513 Сформулирована задача синтеза структуры сетей MPLS с ограничениями на заданные показатели качества сервиса. Построена математическая модель задачи и предложен генетический алгоритм структурного синтеза, позволяющий оптимизировать структуру сети MPLS по критерию стоимости при ограничениях для различных классов потоков. Сформульовано задачу синтезу структури мереж MPLS з обмеженнями на задані показники якості серверу. Побудовано математичну модель задачі і запропоновано генетичний алгоритм структурного синтезу, що дозволяє оптимізувати структуру мережі MPLS за критерієм вартості при обмеженнях для різних класів потоків. The problem of structural synthesis of MPLS networks is formulated. A mathematical model of the problem is elaborated and a genetic algorithm for the structural synthesis is suggested, which makes it possible to optimize the MPLS structure by cost criterion at limited flows of different types. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Структурный синтез компьютерных сетей с технологией MPLS Структурний синтез комп’ютерних мереж з технологією MPLS MPLS computer networks structural synthesis Article published earlier |
| spellingShingle | Структурный синтез компьютерных сетей с технологией MPLS Зайченко, Е.Ю. Зайченко, Ю.П. Ашраф Абдель Хилал Карим Абу-Аин Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| title | Структурный синтез компьютерных сетей с технологией MPLS |
| title_alt | Структурний синтез комп’ютерних мереж з технологією MPLS MPLS computer networks structural synthesis |
| title_full | Структурный синтез компьютерных сетей с технологией MPLS |
| title_fullStr | Структурный синтез компьютерных сетей с технологией MPLS |
| title_full_unstemmed | Структурный синтез компьютерных сетей с технологией MPLS |
| title_short | Структурный синтез компьютерных сетей с технологией MPLS |
| title_sort | структурный синтез компьютерных сетей с технологией mpls |
| topic | Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| topic_facet | Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/42199 |
| work_keys_str_mv | AT zaičenkoeû strukturnyisintezkompʹûternyhseteistehnologieimpls AT zaičenkoûp strukturnyisintezkompʹûternyhseteistehnologieimpls AT ašrafabdelʹhilalkarimabuain strukturnyisintezkompʹûternyhseteistehnologieimpls AT zaičenkoeû strukturniisintezkompûternihmerežztehnologíêûmpls AT zaičenkoûp strukturniisintezkompûternihmerežztehnologíêûmpls AT ašrafabdelʹhilalkarimabuain strukturniisintezkompûternihmerežztehnologíêûmpls AT zaičenkoeû mplscomputernetworksstructuralsynthesis AT zaičenkoûp mplscomputernetworksstructuralsynthesis AT ašrafabdelʹhilalkarimabuain mplscomputernetworksstructuralsynthesis |