Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Рассмотрены задачи анализа сетей с технологией MPLS и оптимизации распределения потоков различных классов сервиса при ограничениях на установленные значения показателей качества обслуживания. Предложен алгоритм решения данной задачи. Описаны комбинированная задача оптимизации выбора пропускных спосо...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/14079 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS / Е.Ю. Зайченко // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 58-71. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859618321231511552 |
|---|---|
| author | Зайченко, Е.Ю. |
| author_facet | Зайченко, Е.Ю. |
| citation_txt | Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS / Е.Ю. Зайченко // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 58-71. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| description | Рассмотрены задачи анализа сетей с технологией MPLS и оптимизации распределения потоков различных классов сервиса при ограничениях на установленные значения показателей качества обслуживания. Предложен алгоритм решения данной задачи. Описаны комбинированная задача оптимизации выбора пропускных способностей и распределения потоков в сетях с технологи-ей MPLS и алгоритм ее решения. Приведены результаты экспериментальных исследований предложенных алгоритмов и сравнение их с известным методом.
|
| first_indexed | 2025-11-28T22:04:54Z |
| format | Article |
| fulltext |
Е.Ю. Зайченко, 2007
58 ISSN 1681–6048 System Research & Information Technologies, 2007, № 4
УДК 681.324
КОМПЛЕКС МОДЕЛЕЙ И АЛГОРИТМОВ ОПТИМИЗАЦИИ
ХАРАКТЕРИСТИК СЕТЕЙ С ТЕХНОЛОГИЕЙ MPLS
Е.Ю. ЗАЙЧЕНКО
Рассмотрены задачи анализа сетей с технологией MPLS и оптимизации рас-
пределения потоков различных классов сервиса при ограничениях на установ-
ленные значения показателей качества обслуживания. Предложен алгоритм
решения данной задачи. Описаны комбинированная задача оптимизации вы-
бора пропускных способностей и распределения потоков в сетях с технологи-
ей MPLS и алгоритм ее решения. Приведены результаты экспериментальных
исследований предложенных алгоритмов и сравнение их с известным мето-
дом.
ВВЕДЕНИЕ
К современным телекоммуникационным технологиям предъявляются тре-
бования передачи разных видов информации (аудио, видео и данных) по
общим каналам связи с помощью унифицированного транспортного меха-
низма и обеспечения при этом заданного качества обслуживания (Quality of
Service), а именно средней задержки срT и ее вариации. Существующие се-
тевые технологии, такие как IP, Ethernet, Frame Relay, Token Ring, не в со-
стоянии обеспечить требуемое качество обслуживания. Первой технологи-
ей, которая позволила обеспечить заданное качество, стала технология АТМ
(Asynchronous Transfer Mode), где впервые были введены различные катего-
рии сервиса и показатели качества обслуживания [1]. Однако высокая стои-
мость коммуникационного оборудования сетей АТМ, а также жесткое огра-
ничение на размер передаваемых блоков данных (53 байта) не позволили ей
получить широкое применение в современных компьютерных сетях. Поэто-
му в конце 90-х годов была создана новая технология многопротокольной
коммутации меток — MPLS (Multiprotocol Label Switching), свободная от
недостатков, свойственных АТМ [2]. Ее отличительные особенности:
1) введение различных категорий потоков классов обслуживания (Class
of Service);
2) возможность обеспечения заданного качества обслуживания QoS для
разных категорий;
3) предоставление единого транспортного механизма для передачи раз-
ных видов информации и, наконец, возможность работы с различными сете-
выми технологиями и протоколами (Frame Relay, Ethernet, IP, ATM) [1].
Важными задачами, которые приходится решать в процессе построения
сетей MPLS, являются задачи анализа и оптимизации их характеристик и, в
частности, оптимальный выбор пропускных способностей (ПС) каналов
связи (КС), а также распределение потоков (РП) различных классов по ка-
налам при ограничениях на заданные показатели качества. Впервые эти
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 59
задачи были сформулированы и решены для обычных глобальных сетей
Л. Клейнроком [3].
Автором данной статьи разработан комплекс моделей и алгоритмов
анализа и оптимизации для сетей с технологией АТМ [1]. Вместе с тем спе-
цифика технологии MPLS и наличие различных классов обслуживания, вве-
дение приоритетного обслуживания не позволяет непосредственно приме-
нить известные методы и алгоритмы, разработанные для технологии АТМ.
Анализ литературных источников по тематике MPLS показал, что в настоя-
щее время отсутствуют методы и алгоритмы, учитывающие специфику тех-
нологии MPLS и позволяющие решать задачи их анализа и оптимизации.
Поэтому цель настоящей статьи — развитие и обобщение моделей и алго-
ритмов анализа и оптимизации характеристик АТМ на сети с технологией
MPLS.
АНАЛИТИЧЕСКИЕ МОДЕЛИ ОЦЕНКИ ПОКАЗАТЕЛЕЙ КАЧЕСТВА СЕТИ
С ТЕХНОЛОГИЕЙ MPLS
Для решения задач анализа и оптимизации характеристик сетей с техноло-
гией MPLS по качеству обслуживания (QoS) прежде всего необходимо было
разработать аналитические модели оценки показателей качества для разных
классов сервиса в зависимости от интенсивности входных потоков, ПС ка-
налов, распределения потоков по КС. В работах автора получены зависимо-
сти средней задержки пакетов двух классов приоритетов VBR и ABR в сетях
АТМ от интенсивности входящих потоков и пропускных способностей КС
[1].
Обобщим модели показателей качества для любого количества классов
приоритетов. Пусть у нас есть КС, в котором обслуживается N потоков
данных с относительными приоритетами iP . Поток данных в канале ),( sr с
приоритетом i обозначим i
rsf , общую пропускную способность — rsµ . Для
удобства приоритеты расставим следующим образом:
Nppp >>> 10 .
Выбор обслуживания потоков различных классов с относительными
приоритетами определяется спецификой работы маршрутизаторов сети LSR.
Обслуживание пакетов различных классов происходит с относительными
приоритетами (без прерывания), т.е обслуживание (передача очередного
пакета ) LSR не прерывает обслуживание его при поступлении пакетов бо-
лее высокого приоритета до его завершения.
Для получения аналитических оценок средней задержки пакетов k -го
приоритета введем следующие допущения:
1. Входящие потоки в узле сети всех классов — пуассоновские с ин-
тенсивностью )(k
ijh .
2. Обслуживание в КС ),( sr распределено по показательному закону с
интенсивностью rsµ (Мбит/с), где rsµ — пропускная способность КС
),( sr .
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 60
3. Времена обслуживания пакета в разных КС — статистически неза-
висимые случайные величины.
При таких допущениях, используя аппарат теории массового обслужи-
вания, запишем выражение для задержки в канале ),( sr потоков разных
приоритетов [3, 4]
( ) rsrsrs
rs
rs
f
f
tp
µµ 0
0
0
0 :
−
= , (1)
−
−
=
∑∑
∑
=
−
=
=
j
k
k
rsrs
j
k
k
rsrs
j
i
k
rs
j
rsj
ff
f
tp
0
1
0
)(
01:
µµ
. (2)
Пусть задана матрица требований к передаче информационного потока
l -го приоритета l
ijl hH = . Используя эти выражения в работе [5], получена
окончательная оценка средней задержки потока k -го приоритета в сети
∑
∑∑
∑
∈
=
−
=
=
Σ
−
−
=
Esr
k
i
i
rsrs
k
i
i
rsrs
k
i
i
rs
k
rs
kk
ff
ff
H
T
),(
1
)(
1
1
)(
1
)()(
)(,ср
1
µµ
, (3)
где ∑∑
= =
Σ =
n
j
n
i
k
ij
k hH
1 1
)()( — суммарная интенсивность входящего потока и
класса k ; )(i
rsf — поток i -го класса приоритета в КС ),( sr .
Тогда, на основе полученного общего выражения средняя задержка для
потоков высшего приоритета составляет
( )∑
∑
∈
=
Σ −
=
Esr rsrsrs
k
k
rsrs
f
ff
H
T
),(
0
0
0
0
1
µµ
, (4)
где ∑∑
= =
Σ =
n
i
n
j
ijhH
1 1
)0()0( .
Недостатком данного выражения является то, что в нем не учитывают-
ся задержки в коммутаторах, связанные с обработкой поступающих пакетов
и их коммутацией, а учитываются задержки на ожидание освобождения КС.
Поэтому обобщим данное выражение.
Выведем выражение для средней задержки в маршрутизаторе LSR.
Пусть входящие потоки в маршрутизаторе iLSR пуассоновские с ин-
тенсивностями { rsλ }, а интенсивность (производительность) обслуживания
в LSR iµ (пак/c). Будем считать, что узел связи iLSR описывается моделью
М/М/ n /1, где n — число входящих потоков.
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 61
Тогда средняя задержка в iLSR определится как [4]
ii
T
Λ−
=
µ
1 , (5)
где ∑
∈∀
=Λ
Eiss
sii f
),(:
— суммарная интенсивность входящего потока в
маршрутизатор i .
Средняя задержка во всех LSR для заданной пары ),( ji на
маршруте ijm
∑∑
∈∈∀ Λ−
==
ijij mr rrmr
rij TT
µ
1 . (6)
Тогда средняя задержка во всех маршрутизаторах для произвольной
пары «источник – адресат» определится так:
∑∑
= =
=
n
j
n
i
ijij PTT
1 1
ср , (7)
где ijP — вероятность установления сеанса ),( ji .
Σ
=
H
h
P ij
ij . (8)
Подставляя (6) и (8) в (7), получаем
∑
=Σ Λ−
Λ
=
n
i ii
i
H
T
1
ср
1
µ
. (9)
В этом случае средняя задержка в сети MPLS для потоков k -го класса
приоритета с учетом задержки во всех маршрутизаторах на коммутацию
составит
)(1
1
)(
)(
∈),(
1
)(
1
1
)(
1
)()(
)(
)(
ср ∑
∑∑
∑
∑
=
=
−
=
=
Σ Λ−
Λ
+
−
−
=
n
i
к
ii
к
i
Esr
k
i
i
rsrs
k
i
i
rsrs
k
i
i
rs
k
rs
k
k
ff
ff
H
T
µ
µµ
. (10)
Определим вероятности потери пакетов разных классов.
Вероятность потери пакетов k -го класса в КС ( )sr, равна вероятности
состояния, когда все виртуальные каналы, выделенные под поток k -го
класса в линии связи ( )sr, , будут заняты [1, 5 ].
kk N
k
k
rs
k
nk
rsk
rs n
f
n
f
PP
=
µµ
)()(
0
)(
пот !
1 , (11)
где µ — ПС базового канала (например,
с
Кбит15441 =µ ); kn — число ка-
налов в линии связи ( sr, ), выделенных для передачи потока k -го класса;
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 62
kN — объем буфера коммутатора в пакетах для очереди k -го класса; 0P —
нормирующий множитель.
Тогда вероятность того, что не произойдет потерь пакетов k -го класса
ни в одном из каналов сети, будет равна
( ))(
),(пот
),(
1П k
sr
Esr
P−
∈
,
а вероятность (доля) потерянных пакетов k -го класса [1,5]
( ))(
),(пот
),(
11 П k
sr
Esr
k PPLR −−=
∈
. (12)
ПОСТАНОВКА ОБОБЩЕННОЙ ЗАДАЧИ РП
Рассмотрим общую постановку задачи РП с ограничениями на среднюю за-
держку и долю потерянных пакетов, которая отличается от известной [5]
учетом задержки в коммутаторах.
Задана сеть в виде графа ( )EXG , , где { }jxX = — множество узлов
связи (УС); { }),( srE — множество КС, а также заданы пропускные спо-
собности КС { }rsµ и матрица требований )()( khkH ij= , nji ,1, = , где
)(khij — интенсивность потока k -го класса, который необходимо переда-
вать из УС ix в узел jx (Кбит/с).
Требуется найти такие маршруты передачи и РП всех классов
[ ])()( kfkF rs= , при которых обеспечиваются ограничения на среднюю за-
держку зад,,ср kk TT ≤ и на долю (вероятность) потери пакетов k -го класса
зад,kk PLRPLR ≤ .
АЛГОРИТМ РЕШЕНИЯ ОБОБЩЕННОЙ ЗАДАЧИ РП
В работе [5] предложен алгоритм решения обобщенной задачи РП для пото-
ков k классов при ограничениях на
зад,,ср kk TT ≤ , (13)
зад,kk PLRPLR ≤ . (14)
Этот алгоритм состоит из k2 этапов. Его особенность заключается в
том, что на каждом из этапов проводилось распределение потоков k -го
класса по одному из ограничений (8) или (9), а недостаток — в том, что если
на этапе )12( −k мы распределяем поток k -го класса при ограничении
зад,,ср kk TT ≤ , а затем на этапе k2 распределяем поток )(kF по ограничению
зад,kk PLRPLR ≤ , то новое распределение потоков )(~ kF может нарушить
предыдущее ограничение (13). Потребуется дополнительное РП, чтобы
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 63
обеспечить выполнение ограничения (13). Для этого необходимы дополни-
тельные затраты машинного времени. Поэтому ниже предлагается усовер-
шенствованный алгоритм РП, в котором на каждом этапе ищется распреде-
ление потоков )(kF с учетом обоих ограничений (13) и (14) одновременно.
Описание алгоритма
Алгоритм состоит из K этапов (по числу классов сервиса K ), на каждом из
которых находится распределение потоков k -го класса )(kF при ограниче-
ниях (8) и (9).
Этап 1.
0 шаг. 0)0(1 =F ; 0)0(1 =H .
Этап состоит из )1(2 2 −= nnCn итераций, на каждой из которых нахо-
дим РП от очередного требования ijh , nji ,1, = , ji ≠ .
1-я итерация
1. Находим начальную условную метрику +
∂
∂
= )1(
1,ср)1(
rs
rs f
T
l λ
)1(
1)1(
rsf
PLR
∂
∂
−+ λ , где [ ]1;0∈λ .
Как видим, данная метрика является выпуклой комбинацией двух мет-
рик )1(
1,ср
rsf
T
∂
∂
и )1(
1
rsf
PLR
∂
∂ .
В качестве начального значения λ можно выбрать 5,0=λ .
2. Определяем кратчайшие пути в данной метрике между всеми узлами
)1(min
ijπ .
3. Выбираем первое требование из матрицы 1
1 ijhH = , например,
11 jih .
Находим кратчайший путь min
11 jiπ , распределяем поток от требования
11 jih
и определяем начальное РП.
=
∈=+
=
случае.противномв0)0(
,),(если,)0(
)1(
)1(
min)1(
)1( 111111
rs
jijijirs
rs
f
srhhf
f
π
(15)
Конец первой итерации. Переходим ко второй.
r -я итерация
Пусть уже проведены )1( −r итераций, распределены потоки от )1( −r
требований матрицы )1(H и найдено РП )1()1( −rfrs .
1. Определяем условную метрику
)1(|)1()( )1(
)1(
1
)1(
1,ср)1( −=
∂
∂
−+
∂
∂
= rff
f
PLR
f
T
rl rsrs
rsrs
rs λλ . (16)
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 64
2. Выбираем очередное требование rr jih из матрицы )1(H и находим
кратчайший путь min
rr jiπ в метрике )()1( rlrs .
3. Распределяем поток от требования
rr jih по пути min
rr jiπ и находим
новый поток )(1 rF .
−
∈+−
=
,случаепротивномв)1(
,),(если,)1(
)( )1(
min)1(
)1(
rf
srhrf
rf
rs
ji
a
jirs
rs
rrrr
π
где ( ){ }min
рез;min
rrrrrr jiji
a
ji Qhh π= — величина части требования
rr jih , ко-
торая передается по пути min
rr jiπ .
Конец r -й итерации.
Остальные итерации первого этапа выполняем аналогично до полного
исчерпания требований матрицы )1(H . Обозначим полученный поток
[ ])1(
1 rsfF = .
Проверяем выполнение ограничений
зад,11ср )( TFT ≤ , (17)
зад,11)( PLRFPLR ≤ . (18)
Если ограничения (17) и (18) выполняются, то конец этапа 1, переход к
этапу 2. Иначе проводим дополнительную оптимизацию потока 1F .
Пусть, например, ограничение (17) не нарушается, а ограничение (18)
нарушается.
Тогда изменяем весовые коэффициенты метрики 25,01 =→ λλ ,
75,01 12 =−= λλ и повторяем этап 1 либо проводим оптимизацию по крите-
рию min1 →PLR при ограничениях зад,11ср )( TFT ≤ .
Для этого введем штрафную функцию
( ) ( ){ }2зад,11,ср1ср ;0max)( TTFTg −= .
Используем в качестве минимизируемой функцию вида
( ))()( 1ср1 FTgrFPLR k+ ,
β1−= kk rr ; 1>β ; 10 =r .
Этап k
Пусть проведено 1−k этап и найдены РП от первых )1( −k требований
[ ])1(
121 ,...,, −
− = k
rsk fFFF .
Найдем распределение потоков k -го класса. Этап состоит из )1( −nn
итераций.
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 65
1-я итерация
1. Находим начальную условную метрику
)()(
,ср )1()1( k
rs
k
k
rs
kk
rs f
PLR
f
T
l
∂
∂
−+
∂
∂
= λλ , (19)
где [ ]1;0∈λ .
2. Находим кратчайшие пути в данной метрике между всеми узлами
)(min kijπ .
3. Выбираем первое требование
11 jih из матрицы k
ijk hH = . Находим
кратчайший путь в метрике (19) )(min
11
kjiπ .
Определяем ПС пути )(min
11
kjiπ .
( ) εµπ
π
−
∑−=
−
=∈
1
1
)(
)(),(
min
рез min
11
11
min
k
i
i
rsrs
ksr
ji fQ
ji
.
4. Распределяем поток от требования )(
11
k
ji
h величиной )(
11
a
ji
h , где
( ){ }min
рез
)(
111111
;min ji
k
ji
a
ji Qhh π= , и вычисляем новую величину потока.
=
∈+
=
случае.противномв0)0(
,),(если,)0(
)1(
)(
min)()()(
)( 1111
k
rs
k
ji
k
ji
k
rsk
rs
f
srhf
f
π
Конец 1-й итерации.
Остальные требования выполняются аналогично до полного исчерпа-
ния требований в матрице )()( khkH ij= nji ,1, = .
В результате получаем распределение потоков [ ])()( kfkF rs= . Далее
проверяем выполнение ограничений
зад,ср )( kk TFT ≤ , (20)
зад,)( kk PLRFPLR ≤ . (21)
Если оба ограничения выполняются, то STOP, конец работы алгоритма.
Иначе переход к дополнительной оптимизации распределения потока )(kF .
Допустим, что нарушено условие (20). Тогда используем метрику
)(
срн)(
k
rs
k
rs
f
T
l
∂
∂
= . (22)
Дальше осуществляем оптимизацию распределения потоков )(kF по
критерию kT ,срmin .
1. Вычисляем кратчайшие пути )(min kijπ в метрике н)(k
rsl (22).
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 66
2. Проверяем возможность дополнительной оптимизации РП по крите-
рию kT ,ср , для чего проверяем условие
∑∑
∈∈
<
Esr
k
rsrs
Esr
k
rsrs flfl
),(
)(
),(
)(н . (23)
Если условие (23) выполняется, то переходим к шагу 3, иначе STOP —
задача неразрешима.
3. Ищем такую пару ( )ss ji , , для которой
( ) ∑∑
∈∈
<
min
,
н
, ),(
),(н
),(
,н
sjsi
ss
sjsi
ss
sr
ji
rsrs
sr
ji
rsrs flfl
ππ
, (24)
где min
, ss jiπ — длина кратчайшего пути между парой ( )ss ji , в прежней мет-
рике; н
, sjsiπ — длина кратчайшего пути в новой метрике н)(k
rsl .
4. Перенаправляем поток от требования sjsih , со старого маршрта
min
, ss jiπ на новый н
, sjsiπ и вычисляем новое РП.
∈∩∉−
∉∩∈+
=
.
;),(),(,)(
;),(),(,)(
случаепротивномв
если
если
)(
minн)(
minн)(
н)(
k
rs
jijiji
k
rs
jijiji
k
rs
k
rs
f
srsrhkf
srsrhkf
f
ssssss
ssssss
ππ
ππ
5. Проверяем условие
зад,
н
ср )( kk TFT ≤ . (25).
Если (25) выполняется, то конец, иначе на шаг 4 и выбор другого тре-
бования ),( ji , для которого выполняется (24).
Шаги 4…6 повторяем до тех пор, пока условие (24) перестанет выпол-
няться. Обозначим )(* kF полученное новое распределение потоков k -го
класса.
Если зад,
*
ср ))(( kTkFT ≤ и зад,
* ))(( kPLRkFPLR ≤ , то конец работы ал-
горитма, в противном случае задача РП неразрешима при заданных ПС КС,
матрице требований )(kH и введенных ограничениях зад,kT и зад,kPLR .
ЗАДАЧА ВЫБОРА ПС КС И РП
Одна из целей внедрения технологии MPLS — обеспечение заданного каче-
ства обслуживания потоков различных классов. Высокая стоимость теле-
коммуникационного оборудования сетей MPLS — маршрутизаторов и КС,
стремление наилучшим образом использовать коммуникационные ресурсы
сетей и в первую очередь ПС КС обусловливают в качестве первоочередной
задачу оптимизации использования коммуникационных ресурсов сетей
MPLS.
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 67
Выше была рассмотрена важная задача оптимального РП различных
классов при ограничениях на среднюю задержку
к
Tср , долю потерянных
пакетов кCLP и заданных ПС каналов. Такая задача не всегда разрешима
вследствие недостаточных ПС отдельных каналов. В этом случае необходи-
мо либо ограничить матрицы потоков входящих требований, приведя их в
соответствие с наличными ПС, либо модифицировать ПС каналов так, что-
бы удовлетворить полностью требования пользователей сети.
Поэтому для обеспечения возможности передачи всех входящих пото-
ков требований с заданными показателями качества при произвольных мат-
рицах требований )(kH необходимо решать комбинированную задачу ин-
жиниринга трафика, в которой одновременно выбираются оптимальные ПС
КС и находятся соответствующие РП всех классов. К этим задачам относит-
ся комбинированная задача выбора пропускных способностей (ВПС) и РП.
Поэтому рассмотрим теперь постановку этой задачи, являющуюся раз-
витием соответствующей задачи ВПС РП для сетей АТМ.
Задана сеть MPLS в виде орграфа ),( EXG = , где { }jxX = , nj ,1= —
множество узлов сети; { }),( srE = — множество КС; набор ПС каналов
{ }kdddD ,...,, 21= и их удельных стоимостей { }kcccC ,...,, 21= . Заданы так-
же матрицы требований входящих потоков соответствующих классов
)(k
ijhH = , nji ,1, = , Kk ,1= ; ограничения на среднюю задержку для клас-
сов потоков kТ ,ср , KKk ⊂∈ 1 и на долю потерянных пакетов различных
классов зад,kPLR .
Требуется выбрать такие ПС каналов связи { })0(
rsµ и найти РП всех
классов [ ])()( kfkF rs= , при которых стоимость сети будет минимальной, а
установленные ограничения на задержки по классам выполняться полно-
стью. Математическая модель данной задачи имеет следующий вид.
Найти
∑
∈
Σ =
Esr
rsrsCC
),(
)(min µ (26)
при ограничениях
krsк TkFT ,зад,ср )),(( ≤µ Kk ,1= , (27)
зад,)( kk PLRFPLR ≤ . (28)
Описание метода решения комбинированной задачи ВПС РП
Задача является комбинированной из пары задач ВПС и РП. Опишем метод
ее решения, который состоит из предварительного этапа и конечного числа
однотипных итераций [1].
На предварительном этапе находим ПС КС { })0(rsµ и начальные РП
всех классов )(kF . Затем переходим к выполнению первой итерации.
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 68
)1( +l -я итерация
Пусть уже проведены l итераций, найдены текущие ПС { })(lrsµ и РП
[ ])()( )( lflF k
rsk = , а также величина общей стоимости )(lCΣ .
Цель итерации — оптимизация ПС КС и РП по критерию минимизации
стоимости ΣC и проверка признака оптимальности.
1. Для заданных ПС )(lrsµ решаем задачу РП и находим новые РП
всех классов.
[ ])1()1( )(
)( +=+ lflF k
rsk Kk ,1= .
2. Для найденных потоков )1()( +lF k решаем задачу ВПС и находим
новые ПС всех каналов { })1( +lrsµ и стоимость сети =+Σ )1(lC
∑
∈
+=
Esr
rs lC
),(
)1( .
3. Проводим сравнение. Если ε<+− ΣΣ )1()( lClC , где ε — заданная
точность, то конец. Найденные ПС { })1( +lrsµ и РП всех классов
)1( +lFk — искомые. Конец работы алгоритма. Иначе 1+= ll и переход к
следующей итерации.
Таким образом, в результате решения задачи ВПС РП находим одно-
временно ПС всех каналов связи и РП всех классов, минимизирующие
стоимость сети в целом, при заданных ограничениях на установленные зна-
чения показателей качества обслуживания (QoS) — среднюю задержку в
доставке пакетов для всех классов.
ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПРЕДЛОЖЕННЫХ
АЛГОРИТМОВ
Для экспериментального исследования разработаны соответствующие про-
граммы, которые вошли в состав моделирующего программного комплекса
MPLS NETBUILDER.
Все эксперименты проводились на сети из 15 узлов, 19 каналов и 3 ти-
пов трафика (рис. 1).
В процессе экспериментов изме-
нялась матрица требований )(kH пу-
тем умножения на соответствующий
коэффициент k .
Первый эксперимент (см. табли-
цу) заключался в увеличении коэффи-
циента для требований к передаче тра-
фика класса 1. Этот трафик имеет
приоритет 0. Следовательно только
под него выделяется отдельный тип
ПС «сетевое управление».
Результаты первого эксперимента
Коэффициент (к1)
Средняя задержка
(T Класс 1,с)
10 0,0002667
20 0,0006484
30 0,0012629
40 0,0023985
50 0,0068935
54 0,023741
55 0,0831388
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 69
Следующий эксперимент заключался в увеличении коэффициента для
требований к передаче трафика класса 2. Этот трафик имеет приоритет 2,
следовательно, он распределяется в общей полосе, оставшейся после РП
класса 1. Нужно отметить, что среди трафиков для этого эксперимента, ко-
торые распределяются в общую оставшуюся свободную полосу КС, трафик
класса 2 имеет наивысший приоритет. Результаты эксперимента показаны
на рис. 2 и 3. Как видно из графиков (рис. 2), зависимость задержки для
трафика класса 2 от интенсивности потока класса 2 носит близкий к квадра-
тичному характер, а зависимость задержки для менее приоритетного трафи-
ка класса 3 (рис. 3) является гиперболической, что хорошо согласуется с
формулой (10).
Рис. 1. Структура сети
Без задержки
С задержкой в LSR
Т ср
,с
К
Рис. 2. Средняя задержка трафика класса 2
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 70
В следующих экспериментах исследовалось влияние производительно-
сти маршрутизаторов на общую среднюю задержку сети для трафика клас-
са 1 (рис. 4).
Как и следовало ожидать, с ростом производительности маршрутизато-
ров средняя задержка пакетов разных классов убывает.
Далее проводились сравнительные эксперименты предложенного алго-
ритма РП с методом РП Л. Клейнрока. С этой целью алгоритм Л. Клейнрока
был соответствующим образом доработан так, чтобы он позволял распреде-
лять потоки K классов приоритетов (рис. 5).
Как видно из приведенных графиков, предложенный в работе алгоритм
оказывается эффективнее известного алгоритма Клейнрока, соответствую-
щие кривые проходят ниже.
Рис.4. Зависимость задержки в сети от интенсивности обслуживания в маршрути-
заторах
µ, пак/с
Тср,c
0,025
0,02
0,015
0,01
0,005
Т ср
,с
Без задержки
С задержкой в LSR
К
Рис. 3. Зависимость средней задержки трафика класса 3 от 2K
Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS
Системні дослідження та інформаційні технології, 2007, № 4 71
ВЫВОДЫ
1. Рассмотрены и исследованы задачи анализа и оптимизации характе-
ристик сетей с технологией MPLS. Сформулирована задача распределения
потоков различных классов сервиса при ограничениях на показатели каче-
ства обслуживания (QoS) в сетях MPLS.
2. Предложен новый алгоритм ее решения, отличающийся от извест-
ных учетом задержек в коммутаторах MPLS и одновременным распределе-
нием потоков по двум показателям качества — средней задержке и доли по-
терянных пакетов.
3. Рассмотрена комбинированная задача ВПС РП для сетей MPLS и
описан алгоритм ее решения, учитывающий специфику этой технологии.
4. Приведены результаты экспериментальных исследований предло-
женных алгоритмов и сравнение с известным методом.
ЛИТЕРАТУРА
1. Зайченко Е.Ю. Сети АТМ: Моделирование, анализ и оптимизация. — Киев:
ЗАТ «ВИПОЛ», 2003. — 224 с.
2. Олвейн В. Структура и реализация современной технологии MPLS / Пер. с
англ. — М.: Изд. дом «Вильямс», 2004. — 480 с.
3. Клейнрок Л. Вычислительные системы с очередями. — М.: Мир,1979. — 600 с.
4. Клейнрок Л. Теория массового обслуживания / Пер. с англ. под ред.
В.И. Неймана. — М.: Машиностроение, 1979. — 432 с.
5. Зайченко Ю.П., Ахмед А.М. Шарадка. Задача распределения потоков различ-
ных классов в сети с технологией MPLS // Вісн. Національного технічн. ун-
ту України «КПІ». Сер. «Інформатика управління та обчислювальна
техніка». — Вип. 43. — 2005. — С. 113 – 123.
6. Зайченко Е.Ю. Оптимізація характеристик мереж з технологією АТМ // Сис-
темні дослідження та інформаційні технології. — 2002. — № 3. —
С. 57 – 73.
Поступила 13.06.2007
Рис. 5. Сравнение алгоритма Клейнрока и предложенного алгоритма
Алгоритм
Клейнрока
Наш алгоритм
К
Т ср
,с
0,8
0,6
0,4
0,2
КОМПЛЕКС МОДЕЛЕЙ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ХАРАКТЕРИСТИК СЕТЕЙ С ТЕХНОЛОГИЕЙ MPLS
Е.Ю. Зайченко
ВВЕДЕНИЕ
Аналитические модели оценки показателей качества сети с технологией MPLS
Постановка обобщенной задачи РП
Алгоритм решения обобщенной задачи РП
Описание алгоритма
Задача выбора ПС КС и РП
Описание метода решения комбинированной задачи ВПС РП
Экспериментальные исследования предложенных алгоритмов
Выводы
Рис. 1. Структура сети
Рис. 2. Средняя задержка трафика класса 2
Рис. 3. Зависимость средней задержки трафика класса 3 от
Рис.4. Зависимость задержки в сети от интенсивности обслуживания в маршрутизаторах
Рис. 5. Сравнение алгоритма Клейнрока и предложенного алгоритма
|
| id | nasplib_isofts_kiev_ua-123456789-14079 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-11-28T22:04:54Z |
| publishDate | 2007 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Зайченко, Е.Ю. 2010-12-10T17:36:59Z 2010-12-10T17:36:59Z 2007 Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS / Е.Ю. Зайченко // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 58-71. — Бібліогр.: 6 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/14079 681.324 Рассмотрены задачи анализа сетей с технологией MPLS и оптимизации распределения потоков различных классов сервиса при ограничениях на установленные значения показателей качества обслуживания. Предложен алгоритм решения данной задачи. Описаны комбинированная задача оптимизации выбора пропускных способностей и распределения потоков в сетях с технологи-ей MPLS и алгоритм ее решения. Приведены результаты экспериментальных исследований предложенных алгоритмов и сравнение их с известным методом. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS Article published earlier |
| spellingShingle | Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS Зайченко, Е.Ю. Теоретичні та прикладні проблеми інтелектуальних систем підтримки прийняття рішень |
| title | Комплекс моделей и алгоритмов оптимизации характеристик сетей с технологией MPLS |
| 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/14079 |
| work_keys_str_mv | AT zaičenkoeû kompleksmodeleiialgoritmovoptimizaciiharakteristikseteistehnologieimpls |