Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS
Рассмотрена задача оперативного управления трафиками разных категорий в сетях с технологией MPLS. Данная задача сформулирована как задача ремаршрутизации потоков разных классов сервиса при отказах каналов и узлов сети и обеспечении заданного качества обслуживания. Построена математическая модель зад...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2015
|
| Schriftenreihe: | Системні дослідження та інформаційні технології |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86132 |
| 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 / Е.Ю. Зайченко // Системні дослідження та інформаційні технології. — 2015. — № 1. — С. 68-76. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-86132 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-861322025-02-23T20:02:10Z Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS Оперативне керування потоками у комп’ютерних мережах з технологією MPLS Online traffic management in MPLS computer networks Зайченко, Е.Ю. Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Рассмотрена задача оперативного управления трафиками разных категорий в сетях с технологией MPLS. Данная задача сформулирована как задача ремаршрутизации потоков разных классов сервиса при отказах каналов и узлов сети и обеспечении заданного качества обслуживания. Построена математическая модель задачи и разработан ее алгоритм, позволяющий оперативно определить новые маршруты требований, получивших отказ в обслуживании и перераспределить их по новым маршрутам так, чтобы обеспечить максимальную величину передаваемого скорректированного потока. Для оценки эффективности предложенного алгоритма оперативного управления трафиком и ремаршрутизации потоков в сети были проведены экспериментальные исследования. Решена задача оптимального выбора пропускных способностей и распределения потоков. Смоделированы отказовые состояния и осуществлена ремаршрутизация потоков по предложенному алгоритму, определено новое распределение потоков и общая величина скорректированного потока по каждому классу сервиса. Анализ результатов подтвердил, что применение оперативного управления трафиком в виде ремаршрутизации позволяет существенно повысить общую пропускную способность сети и величину передаваемого потока сети в случае отказов элементов сети. Розглянуто задачу оперативного керування трафіками різних категорій у комп’ютерних мережах з технологією MPLS. Цю задачу сформульовано як задачу ремаршрутизації потоків різних класів сервісу при відмовах каналів і вузлів мережі та забезпеченні заданої якості обслуговування. Побудовано математичну модель задачі й розроблено алгоритм її вирішення, що дозволяє оперативно визначити нові маршрути вимог, які одержали відмову в обслуговуванні й перерозподілити їх за новими маршрутами так, щоб забезпечити максимальну величину переданого скорегованого потоку. Для оцінки ефективності запропонованого алгоритму оперативного управління трафіком і ремаршрутизації потоків у мережі було проведено експериментальні дослідження. Вирішено задачу оптимального вибору пропускних спроможностей і розподілу потоків. Змодельовано стани відмов і здійснено ремаршрутизацію потоків за запропонованим алгоритмом, визначено новий розподіл потоків і загальну величину скорегованого потоку з кожного класу сервісу. Аналіз результатів підтвердив, що застосування оперативного управління трафіком у вигляді ремаршрутизації дозволяє істотно підвищити загальну пропускну спроможність мережі і величину потоку при відмовах. The problem of traffic management of different classes of service in MPLS computer networks is considered. This problem is formulated as a rerouting problem of flows of different service classes under failures of channels and nodes while preserving the quality of service (QoS). The mathematical model of this problem is constructed and the algorithm to solve it is suggested. This algorithm allows to determine new routes for requests which were rejected due to failures and reroute them over new virtual routes so that to maximize the value of transmitted global flow. Experimental studies were conducted to estimate the efficiency of the suggested algorithm of traffic management of different classes of service. The problem of optimal choice of carrying capacities and flows distribution was solved. Further fault states were simulated and flows rerouting was performed using the suggested algorithm, the new flow distribution and the total value of the corrected flow from every service class were determined. The results analysis confirms that application of operative traffic management as a rerouting allows to promote the general capacity of a network and increase the total flow value in a case of faults of network elements. 2015 Article Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS / Е.Ю. Зайченко // Системні дослідження та інформаційні технології. — 2015. — № 1. — С. 68-76. — Бібліогр.: 7 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/86132 004.8 ru Системні дослідження та інформаційні технології application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| spellingShingle |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Зайченко, Е.Ю. Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS Системні дослідження та інформаційні технології |
| description |
Рассмотрена задача оперативного управления трафиками разных категорий в сетях с технологией MPLS. Данная задача сформулирована как задача ремаршрутизации потоков разных классов сервиса при отказах каналов и узлов сети и обеспечении заданного качества обслуживания. Построена математическая модель задачи и разработан ее алгоритм, позволяющий оперативно определить новые маршруты требований, получивших отказ в обслуживании и перераспределить их по новым маршрутам так, чтобы обеспечить максимальную величину передаваемого скорректированного потока. Для оценки эффективности предложенного алгоритма оперативного управления трафиком и ремаршрутизации потоков в сети были проведены экспериментальные исследования. Решена задача оптимального выбора пропускных способностей и распределения потоков. Смоделированы отказовые состояния и осуществлена ремаршрутизация потоков по предложенному алгоритму, определено новое распределение потоков и общая величина скорректированного потока по каждому классу сервиса. Анализ результатов подтвердил, что применение оперативного управления трафиком в виде ремаршрутизации позволяет существенно повысить общую пропускную способность сети и величину передаваемого потока сети в случае отказов элементов сети. |
| format |
Article |
| author |
Зайченко, Е.Ю. |
| author_facet |
Зайченко, Е.Ю. |
| author_sort |
Зайченко, Е.Ю. |
| title |
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS |
| title_short |
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS |
| title_full |
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS |
| title_fullStr |
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS |
| title_full_unstemmed |
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS |
| title_sort |
оптимальная ремаршрутизация потоков в компьютерных сетях с технологией mpls |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| publishDate |
2015 |
| topic_facet |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/86132 |
| citation_txt |
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS / Е.Ю. Зайченко // Системні дослідження та інформаційні технології. — 2015. — № 1. — С. 68-76. — Бібліогр.: 7 назв. — рос. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT zajčenkoeû optimalʹnaâremaršrutizaciâpotokovvkompʹûternyhsetâhstehnologiejmpls AT zajčenkoeû operativnekeruvannâpotokamiukompûternihmerežahztehnologíêûmpls AT zajčenkoeû onlinetrafficmanagementinmplscomputernetworks |
| first_indexed |
2025-11-24T21:10:31Z |
| last_indexed |
2025-11-24T21:10:31Z |
| _version_ |
1849707600197713920 |
| fulltext |
© Е.Ю. Зайченко, 2015
68 ISSN 1681–6048 System Research & Information Technologies, 2015, № 1
TIДC
ПРОБЛЕМНО- І ФУНКЦІОНАЛЬНО-
ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ
ТА МЕРЕЖІ
УДК 004.8
ОПТИМАЛЬНАЯ РЕМАРШРУТИЗАЦИЯ ПОТОКОВ
В КОМПЬЮТЕРНЫХ СЕТЯХ С ТЕХНОЛОГИЕЙ MPLS
Е.Ю. ЗАЙЧЕНКО
Рассмотрена задача оперативного управления трафиками разных категорий
в сетях с технологией MPLS. Данная задача сформулирована как задача ре-
маршрутизации потоков разных классов сервиса при отказах каналов и узлов
сети и обеспечении заданного качества обслуживания. Построена математиче-
ская модель задачи и разработан ее алгоритм, позволяющий оперативно опре-
делить новые маршруты требований, получивших отказ в обслуживании и пе-
рераспределить их по новым маршрутам так, чтобы обеспечить максимальную
величину передаваемого скорректированного потока. Для оценки эффективно-
сти предложенного алгоритма оперативного управления трафиком и ремар-
шрутизации потоков в сети были проведены экспериментальные исследо-
вания. Решена задача оптимального выбора пропускных способностей
и распределения потоков. Смоделированы отказовые состояния и осуществле-
на ремаршрутизация потоков по предложенному алгоритму, определено новое
распределение потоков и общая величина скорректированного потока по каж-
дому классу сервиса. Анализ результатов подтвердил, что применение опера-
тивного управления трафиком в виде ремаршрутизации позволяет существен-
но повысить общую пропускную способность сети и величину передаваемого
потока сети в случае отказов элементов сети.
ВВЕДЕНИЕ
В последние годы задачи разработки моделей и методов для оптимального
управления трафиком в сетях с перспективной технологией многопрото-
кольной коммутации меток (MPLS) представляют большой интерес в связи
с широким практическим внедрением этой технологии в глобальных ком-
пьютерных сетях в развитых странах, в том числе и в Украине. Оперативное
управление трафиками различных классов сервиса в сетях MPLS реализует-
ся в маршрутизаторах сети, так называемых LSR (Label switching routers —
маршрутизатор комуникации по меткам), в которых реализованы дополни-
тельные функции TE [1–2]. LSR с функциями инжиниринга трафика имеют
две отдельные базы данных: традиционную — LSD (Link-state Database)
и специальную — TED (Traffic Engineering Database) для реализации функ-
ций управления трафиком. Управление трафиком осуществляется путем ре-
маршрутизации потоков, передаваемых по виртуальным путям, так назы-
ваемым LSP (Label switching pathes ) [1–3] в случае перегрузок, вызванных
отказами оборудования или каналов связи. Для практической реализации
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS
Системні дослідження та інформаційні технології, 2015, № 1 69
этих функций оперативного управления необходима разработка эффектив-
ных методов и алгоритмов ремаршрутизации путем реконфигурации мар-
шрутов в сети MPLS в случае отказов элементов сети.
Цель работы — разработка математической модели и алгоритма ре-
шения задачи оптимальной ремаршрутизации трафиков в сети MPLS и его
исследования.
ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ
ОПТИМАЛЬНОЙ РЕМАРШРУТИЗАЦИИ ПОТОКОВ В СЕТИ
Как известно, важной особенностью сети с технологией MPLS является на-
личие различных классов сервиса (CoS), каждый из которых обслуживается
в маршрутизаторах (LSR) с соответствующим приоритетом. Кроме того,
вводятся показатели качества обслуживания потоков различных классов:
среднее время доставки пакетов ,)( )(
ср
kT вариация времени доставки пакетов,
а также доля потерянных пакетов [1–3]. Поэтому соответствующая матема-
тическая модель задачи ремаршрутизации должна учитывать указанные
особенности технологии MPLS.
Пусть задана сеть MPLS со структурой },,{ EXG = ,}{ jxX =
nj ,1= — множество узлов сети (УС), },{ srE = — множество каналов свя-
зи (КС) сети, заданы также пропускные способности (ПС) всех КС rsμ ,
,),( Esr ∈ и матрица требований )()( khkH ij= nji ,1, = , )(khij — интен-
сивность потока k -го класса сервиса, который необходимо передавать из
узла i в j (Кбит/с), распределение потоков всех классов )]([)( kfkF rs= , где
)(kfrs — величина потока класса k , передаваемого по КС ),( sr и соответ-
ствующего матрице ).(kHΣ
При этом, общая величина потока всех классов в КС ),( sr будет равна:
.)(
1
∑
=
=
K
k
rsrs kff (1)
В случае, когда обслуживание потоков различных классов k происхо-
дит с относительными приоритетами kρ , убывающими с ростом номера
класса, т.е. ,,,21 kρρρ >>> K ,,1 Kk = то средняя задержка пакетов k-го
класса задается следующим выражением [5]:
.1
),(
1
)(
1
1
)(
1
)()(
)(,ср ∑
∑∑
∑
∈
=
−
=
=
Σ
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
=
Esr
k
i
i
rsrs
k
i
i
rsrs
k
i
i
rs
k
rs
kk
ff
ff
H
T
μμ
(2)
Введены также ограничения на значения показателя качества (QoS) для
всех классов в виде:
k
k TT ,зад
)(
ср ≤ , (3)
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2015, № 1 70
где )(
ср
kT — средняя задержка пакетов k -го класса (сек.); kT ,зад — ограниче-
ние на эту величину.
Известны также маршруты коммутации меток LSP )}({ kПij для каждо-
го соединения (пары) ),( ji , которые устанавливаются с помощью протокола
RSVP или SNMP [1–2].
Допустим, что отказал КС ),( ii sr — отказовое состояние обозначим
как .iz Требуется реконфигурировать все маршруты отказавшего соедине-
ния КС ),( ii sr таким образом, чтобы в максимальной степени удовлетворить
соответствующие требования, получившие отказ в обслуживании при со-
хранении остальных соединений по объему трафика и заданному качеству
QoS — срT . Назовём эту задачу задачей оптимальной ремаршрутизации
сети MPLS при отказах.
Математическая модель данной задачи имеет следующий вид [5].
Требуется найти такое распределение потоков ,)]([ kfrs при котором
обеспечивается:
max
),(:),(
)корр( →= ∑
∈
Σ
ijji Пsrji
ijhH (4)
при условиях
,)( зад
)(
коррср TFT k ≤ ,,1 Kk = (5)
где )(
корр
kF — скорректированный поток k -го класса сервиса после реконфи-
гурации.
ОПИСАНИЕ АЛГОРИТМА ОПТИМАЛЬНОЙ РЕМАРШРУТИЗАЦИИ
СЕТИ MPLS
Метод основан на том свойстве оптимального решения, что поток k-го клас-
са сервиса в силу формулы (2) не влияет на задержку потоков более высоко-
го уровня приоритета, а именно, классов: .1,,2,1 −kK
Алгоритм состоит из 2-х этапов [5].
На первом этапе определяются все требования (соединения) ),,( ji ко-
торые использовали КС ),( ii sr , и отключаются временно от сети и пересчи-
тываются потоки в КС [ ],)()( k
rs
k fF = .),( Esr ∈
На втором — определяются резервы по ПС всех КС и оптимальным об-
разом перераспределяются потоки отказанных требований так, чтобы обес-
печить достижение критерия max→ΣH (назовём их отказовыми требова-
ниями).
1-й этап.
1. Находим все требования ),( ji , проходившие через отказанные соеди-
нения КС ).,( ii sr Обозначим их множество как )}.,(:),{(, ijiisr ПsrjiP
ii
∈=
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS
Системні дослідження та інформаційні технології, 2015, № 1 71
2. Временно отключаем передачу информации для требований множе-
ства
ii srP , и вычисляем новые значения потоков — :)]([)( нн kfkF rs=
⎪⎩
⎪
⎨
⎧ ∈−
=
∑
∈
.случаяхостальных в ,
,),( где , ,
),(:),(н
rs
sr
Пsrji
ijrs
rs
f
Pjihf
f
ii
ijii
Это выполняется следующим образом:
• Находим первое требование .),( ,11 ii srPji ∈
• Полагаем 0
11, =jih и вычисляем новое распределение потоков:
⎪⎩
⎪
⎨
⎧ ∈−
=
,случаях остальных в ),(
,),( если ,)(
)( 1111 ,,н
kf
Пsrhkf
kf
rs
jijirs
rs (6)
где
11, jiП — маршрут передачи потока требования .),( 11 ji
• Проверка условия: .),(\ 11, ∅≠jiP
ii sr Если ДА, то на шаг 1 и повто-
ряем шаги 1–3 до исчерпания множества
ii srP , . В результате получим новое
распределение потоков всех классов |)(|)( нн kfkF rs= , включающее потоки
только от требований, не получивших отказа в обслуживании .\),( , ii srPji
• Определяем резервы по ПС всех КС:
.)(
1
н
,,рез ∑
=
−=
K
k
rsrssr kfQ μ (7)
Переходим ко второму этапу.
2-й этап.
Для требований множества
ii srP , находим новые маршруты (реконфи-
гурируем) так, чтобы обеспечить выполнение условий:
,)( зад
)(
коррср TFT k ≤ Kk ,1= , (8)
и при этом max
,),(
)корр( →∑
∈ isirPji
ijh .
Второй этап состоит из k подэтапов, на каждом из которых осуществ-
ляем реконфигурацию маршрутов и переопределение потоков для k -го
класса. При этом, с учетом свойств оптимального решения, перераспределе-
ние потоков отказавших требований различных классов осуществляется
в порядке убывания приоритетов до полного исчерпания резерва ПС кана-
лов и контроля выполнения ограничений (8).
Подэтап 1.
1-я итерация.
1. .1=k Сначала распределяем отказанные требования класса 1.
2. Находим условную метрику .)1(| н
)1(
ср
rs
rs
f
f
T
∂
∂
3. Находим кратчайшие пути )1(min
ijП для всех отказанных требований
класса .1=k
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2015, № 1 72
4. Выбираем первое требование
ii srPji ,11 ),( ∈ такое, что =)( min
, 11 jiПl
).(min min
,
),(
ji
ji
Пl=
5. Проверяем возможность передачи его в полном объеме по пути
:min
, 11 jiП
),( min
,рез 1111 jiji ПQh < (9)
где )( min
,рез 11 jiПQ — свободная ПС маршрута min
, 11 jiП :
}.{min)(
11
11 ),(
min
,рез rsrs
Пsr
ji fПQ
ji
−=
∈
μ (10)
Если условие (10) выполняется, то распределяем полностью поток тре-
бования
11 jih по маршруту min
, 11 jiП и находим скорректированное распреде-
ление потоков (РП):
⎪⎩
⎪
⎨
⎧ ∈+
=
случаях.остальных в ),1(
,),( если ,)1(
)(
н
min
,,
н
н 1111
rs
jijirs
rs
f
Пsrhf
kf (11)
Иначе переходим на шаг 6.
6. Полагаем .)( min
,рез
)(
, 1111
Δ−= ji
a
ji ПQh Здесь )(
, 11
a
jih — доля требования
11 , jih , передаваемая по маршруту min
, 11 jiП , Δ — некоторая заданная велична.
7. Находим скорректированное распределение потоков:
( )
⎪⎩
⎪
⎨
⎧ ∈+
=
случаях.остальных в ),1(
,),( если ,)1(
)(
min
,,
н
корр 1111
rs
ji
a
jirs
rs
f
Пsrhf
kf (12)
Проверяем выполняется ли ограничение на 1,срT :
1,зад
)1(
коррср )( TFT ≤ . (13)
Если условие (13) выполняется, то ),,(\ 11,, jiPP
iiii sr
н
sr = иначе на шаг 9.
8. Проверка условия: .н
, ∅≠
ii srP Если ДА, то переходим к следующей
итерации и распределяем очередное требование класса .1=k Иначе на
шаг 9.
9. Конец первого подэтапа. Переходим ко второму подэтапу .2=k На
этом этапе перераспределяем отказанные требования класса 2=k так, что-
бы не нарушалось условие:
2,зад
)2(
коррср )( TFT ≤ . (14)
Подэтап 2 аналогичен подэтапу 1. Поэтому его описание можно опус-
тить. Отказанные требования КС 2 перераспределяем до тех пор, пока либо
они не будут распределены полностью, либо начнет нарушаться условие (8).
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS
Системні дослідження та інформаційні технології, 2015, № 1 73
Тогда конец подэтапа 2 и переходим к подэтапу 3.
Подэтап k. На этом подэтапе находим реконфигурированные маршру-
ты для отказанных требований k -го класса: )(
,),( k
sr ii
Pji ∈ .
Пусть )]([)( 00 kfkF rs= — вектор многопродуктового потока k -го класса,
после выполнения )1( −k -го подэтапа и при этом <− ))1(),...,1(|)((ср kFFkFT
kT ,зад< .
1-я итерация.
1. Находим условную метрику )(|
)(
)( ср kf
kf
T
kl o
rs
rs
rs
∂
∂
= .
2. Находим кратчайшие пути в метрике )(klrs для всех отказанных
требований k -го класса — )(min kПij .
3. Ищем такое требование )(
,),( k
srkk ii
Pji ∈ для которого =))(( min
, kПl
kk ji
)).((min min
,
),( )(
kПl ji
Pji k
isir
∈
=
4. Определяем резерв по ПС маршрута :min
, kk jiП
))((min))((
min),(
min
,рез εμ −−=
∈
rsrs
Пsr
ji fkПQ
kjki
kk
, (15)
где .
1
)(∑
=
=
k
i
i
rsrs ff
5. Проверка условия:
)).(( min
,рез kПQh
kkkk jiji < (16)
Если ДА, то на шаг 6, иначе на 7.
6. Распределяем поток от требования
kk jih в полном объеме по мар-
шруту min
, kk jiП и находим новое распределение потоков (РП):
⎪⎩
⎪
⎨
⎧ ∈+
=
.случаяхостальных в ),(
,),( если ,)(
)(
min
,н
kf
Пsrhkf
kf
rs
jijirs
rs
kkkk
Переход на шаг 9.
7. Полагаем .)( min
,рез
)(
, Δ−=
kkkk ji
a
ji ПQh
8. Распределяем поток от требования ),( kk ji величиной )(
,
a
ji kk
h по
маршруту min
, kk jiП и находим новое РП.
( )
⎪⎩
⎪
⎨
⎧ ∈+
=
.случаяхостальныхв ),(
,),( если ,)(
)(
min
,,н
kf
Пsrhkf
kf
rs
ji
a
jirs
rs
kkkk (17)
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2015, № 1 74
9. Проверка условия: .))1(),...,1(|)(( ,задср kTkFFkFT <− Если да, то на
шаг 10, или уменьшаем величину передаваемого потока требования ),( kk ji
до значения *
, kk jih такого что: kTkFFkFT ,зад
*
ср ))1(),...,1(|)(( =− и конец
подэтапа .k
10. Полагаем ).,(\,
)(
, kk
k
sr
k
sr jiPP
iiii
=
Проверка условия: ., ∅=k
sr ii
P Если ДА, то конец подэтапа ,k иначе на
шаг 1 следующей итерации.
Последовательность итераций k -го подэтапа повторяется до тех пор,
пока не выполняется одно из следующих условий:
а) ;))1(),...,1(|)(( ,задср kTkFFkFT =−
б) skTkFFskFT +=+ ,задср ))(),...,1(|)(( , ;1 kKs −≤≤
в) ∅=)(
,
k
sr ii
P и .))1(),...,1(|)(( ,задср kTkFFkFT ≤−
В случае (а) переходим на 1+k подэтап, и ищем распределение пото-
ков 1+k -го класса приоритета.
В случае (б), когда вышло на границу ограничение для менее приоритет-
ного потока )( skF + и ,Ksk <+ переходим к распределению потока класса
,1++ sk поскольку распределение потоков класса )1( ++ skF не влияет на
среднюю задержку для более приоритетных потоков .1++< skr
В случае (в) переходим на 1+k подэтап, как и в случае (а).
Последовательность выполняемых подэтапов заканчивается либо
полным перераспределением всех отказанных требований, что мало вероят-
но, либо при выходе на границу по некоторым из ограничений, включая ог-
раничение для наименее приоритетного потока, то есть:
.)(, ,зад
)(
коррср k
k TFTk ≥∃ (18)
Это означает полное исчерпание всех свободных ресурсов (свободной
полосы) каналов связи.
В результате работы алгоритма находятся реконфигурированные пути
(LSP) для соединений ),( ji получивших отказ в обслуживании из-за отказа
соответствующего КС или УС. Естественно, что в силу ограниченной ПС
сети при этом некоторые требования обслуживаться не будут. При этом,
учитывая очередность реконфигурации, отказ в обслуживании получат наи-
менее приоритетные соединения, а величина общего потока, передаваемого
в сети после реконфигурации — максимальна.
ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
Для оценки эффективности предложенного алгоритма оперативного управ-
ления трафиком и ремаршрутизации потоков в сети с технологией MPLS
были проведены его экспериментальные исследования. Все эксперименты
проводились с сетью MPLS, структура которой приведена на рисунке.
Оптимальная ремаршрутизация потоков в компьютерных сетях с технологией MPLS
Системні дослідження та інформаційні технології, 2015, № 1 75
Сеть состояла из 25 узлов, 39 каналов связи и вводились 3 типа класса
сервиса. По каждому классу задавалась матрица требований ),(kH .3,1=k
Введены ограничения на среднюю доставку пакетов по сети (QoS) для раз-
личных классов:
1,01зад, =T cек, 5,02зад, =T cек, 13зад, =T cек.
При этих ограничениях решалась задача оптимального выбора пропуск-
ных способностей и распределения потоков (ВПСРП) [5–6], в результате
были определены ПС всех каналов связи и найдено оптимальное распределе-
ние потоков всех классов ,][ )()( k
rs
k fF = а также была определена общая ве-
личина потока, передаваемого в сети по каждому классу ,)()(
),(
∑
∈
Σ =
ijПji
ij khkH
3,1=k при указанных ограничениях на среднюю задержку. Далее модели-
ровались отказовые состояния: отказы одного канала связи (КС), двух кана-
лов связи и трех КС. При этих состояниях определялись новые значения по-
токов — )]([)( нн kfkF rs= и фактическая величина передаваемого потока
класса k в случае действия отказов ).(Ф kHΣ Далее осуществлялась ремар-
шрутизация потоков по предложенному алгоритму и определялось новое
распределение потоков )(
корр
kF и общая величина скорректированного потока
по каждому классу сервиса Ф
корр,ΣH при ограничениях .)( зад,
)(
коррср k
k TFT ≤
Общая величина передаваемого потоков сети )(Ф kHΣ и Ф
корр,ΣH до
и после ремаршрутизации соответственно в процентах от величины номи-
нального потока в безотказовом состоянии )(,),2(),1( )0()0()0( kHHH ΣΣΣ K при-
водится в таблице для различных классов отказовых состояний.
Рисунок. Топология сети
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2015, № 1 76
Т а б л и ц а . Зависимость величины передаваемого потока для различных
отказовых состояний в процентах от )()0( kHΣ
Класс сервиса 1=k Класс сервиса 2=k Класс сервиса 3=k Тип отказовых
состояний )(Ф kHΣ )(Ф
корр, kHΣ )(Ф kHΣ )(Ф
корр, kHΣ )(Ф kHΣ )(Ф
корр, kHΣ
Отказ 1КС 94,7 97,2 93 94,5 90 90,5
Отказ 2КС 90,5 94,3 88 89,5 85 85,5
Отказ 3 КС 84,3 88,2 82 83 74 74
Анализ приведенных результатов свидетельствует о том, что примене-
ние оперативного управления трафиком в виде ремаршрутизации позволяет
существенно повысить общую пропускную способность сети и величину
передаваемого потока сети в случае отказов элементов сети. При этом такое
увеличение относится к потокам высокого приоритета (класс 1 и 2), что
вполне объяснимо, т.к. они ремаршрутизируются в первую очередь и заби-
рают всю резервную пропускную способность каналов связи.
ВЫВОДЫ
• В статье рассмотрена задача ремаршрутизации потоков информации
разных классов сервиса в сетях с технологией MPLS.
• Построена математическая модель данной задачи и предложен алго-
ритм ее решения, использующий свойства оптимального потока.
• Проведены экспериментальные исследования и определена эффек-
тивность предложенного алгоритма ремаршрутизации
ЛИТЕРАТУРА
1. Thomas D. Nadeua. MPLS Network Management: MIBs, Tools and Techniques. —
NY.: Morgan Kaufmann, 2003. — 529 p.
2. Request for Comments 5151. A. Farrel, Ed, A. Ayyangar, JP. Vasseur. Inter-Domain
MPLS and GMPLS Traffic Engineering. Resource Reservation Protocol-Traffic
Engineering (RSVP-TE) Extensions Cisco Systems, Inc. February, 2008. —
https://tools.left.org/html/rfc5151.
3. Vivek A. Advanced MPLS design and implementation. — Indianapolis: Cisco Press,
2002. — 320 p.
4. Гольдштейн А.Б., Гольдштейн Б.С. Технология и протоколы MPLS. — СПб:
БХВ, 2005. — 304 с.
5. Вивек O. Структура и реализация современной технологии MPLS. Пер.
С англ. — СПб.: Изд. дом «Вильямс», 2004. — 480 с.
6. Зайченко Е.Ю., Зайченко Ю.П. Сети с технологией MPLS: моделирование, ана-
лиз и оптимизация. — К.: Политехника, 2008. — 240 с.
7. Zaychenko Y., Zaychenko H. New Generation Computer Networks Survivability
Analysis and Optimization // In book «Distributed Computer and Communi-
cation Networks». — Bern: Springer International Publishing Switzerland,
2014. — P. 73–81.
Поступила 27.02.2014
|