Анализ и синтез сетей с технологией АТМ
Рассмотрены задачи анализа функциональных характеристик сетей с технологией АТМ. Сформулирована задача синтеза структуры сетей АТМ при ограничениях на заданные значения показателей качества и описан алгоритм ее решения. Приводятся результаты экспериментальных исследований разработанного программного...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2003 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2003
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/50305 |
| 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: | Анализ и синтез сетей с технологией АТМ / Е.Ю. Зайченко // Систем. дослідж. та інформ. технології. — 2003. — № 4. — С. 93-112. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50305 |
|---|---|
| record_format |
dspace |
| spelling |
Зайченко, Е.Ю. 2013-10-09T21:30:23Z 2013-10-09T21:30:23Z 2003 Анализ и синтез сетей с технологией АТМ / Е.Ю. Зайченко // Систем. дослідж. та інформ. технології. — 2003. — № 4. — С. 93-112. — Бібліогр.: 12 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50305 681.513 Рассмотрены задачи анализа функциональных характеристик сетей с технологией АТМ. Сформулирована задача синтеза структуры сетей АТМ при ограничениях на заданные значения показателей качества и описан алгоритм ее решения. Приводятся результаты экспериментальных исследований разработанного программного комплекса анализа и синтеза сетей АТМ «АТМ NETBUILDER». Розглянуто задачі аналізу функціональних характеристик мереж з технологією АТМ. Сформульовано задачу синтезу структури мереж АТМ при обмеженнях на задані значення показників якості та описано алгоритм її розв’язання. Наведено результати експериментальних досліджень створеного програмного комплексу аналізу та синтезу мереж АТМ «АТМ NETBUILDER». Problems of ATM networks performance analysis of are considered. The problem of ATM network structure synthesis under limited input quality parameters is formulated and algorithm of its solution is presented. The results of experimental investigations of the created software kit «ATM NETBUILDER» for ATM networks analysis and synthesis are described. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Анализ и синтез сетей с технологией АТМ Аналіз та синтез мереж з технологією АТМ Analysis and synthesis of ATM networks Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Анализ и синтез сетей с технологией АТМ |
| spellingShingle |
Анализ и синтез сетей с технологией АТМ Зайченко, Е.Ю. Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| title_short |
Анализ и синтез сетей с технологией АТМ |
| title_full |
Анализ и синтез сетей с технологией АТМ |
| title_fullStr |
Анализ и синтез сетей с технологией АТМ |
| title_full_unstemmed |
Анализ и синтез сетей с технологией АТМ |
| title_sort |
анализ и синтез сетей с технологией атм |
| author |
Зайченко, Е.Ю. |
| author_facet |
Зайченко, Е.Ю. |
| topic |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| topic_facet |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| publishDate |
2003 |
| language |
Russian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Аналіз та синтез мереж з технологією АТМ Analysis and synthesis of ATM networks |
| description |
Рассмотрены задачи анализа функциональных характеристик сетей с технологией АТМ. Сформулирована задача синтеза структуры сетей АТМ при ограничениях на заданные значения показателей качества и описан алгоритм ее решения. Приводятся результаты экспериментальных исследований разработанного программного комплекса анализа и синтеза сетей АТМ «АТМ NETBUILDER».
Розглянуто задачі аналізу функціональних характеристик мереж з технологією АТМ. Сформульовано задачу синтезу структури мереж АТМ при обмеженнях на задані значення показників якості та описано алгоритм її розв’язання. Наведено результати експериментальних досліджень створеного програмного комплексу аналізу та синтезу мереж АТМ «АТМ NETBUILDER».
Problems of ATM networks performance analysis of are considered. The problem of ATM network structure synthesis under limited input quality parameters is formulated and algorithm of its solution is presented. The results of experimental investigations of the created software kit «ATM NETBUILDER» for ATM networks analysis and synthesis are described.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50305 |
| citation_txt |
Анализ и синтез сетей с технологией АТМ / Е.Ю. Зайченко // Систем. дослідж. та інформ. технології. — 2003. — № 4. — С. 93-112. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT zaičenkoeû analizisintezseteistehnologieiatm AT zaičenkoeû analíztasintezmerežztehnologíêûatm AT zaičenkoeû analysisandsynthesisofatmnetworks |
| first_indexed |
2025-11-24T15:57:58Z |
| last_indexed |
2025-11-24T15:57:58Z |
| _version_ |
1850849705924231168 |
| fulltext |
© Е.Ю. Зайченко, 2003
Системні дослідження та інформаційні технології, 2003, № 4 93
TIДC
ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО
ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ
ТА МЕРЕЖІ
УДК 681.513
АНАЛИЗ И СИНТЕЗ СЕТЕЙ С ТЕХНОЛОГИЕЙ АТМ
Е.Ю. ЗАЙЧЕНКО
Рассмотрены задачи анализа функциональных характеристик сетей с техноло-
гией АТМ. Сформулирована задача синтеза структуры сетей АТМ при ог-
раничениях на заданные значения показателей качества и описан алгоритм ее
решения. Приводятся результаты экспериментальных исследований разрабо-
танного программного комплекса анализа и синтеза сетей АТМ «АТМ
NETBUILDER».
ВВЕДЕНИЕ
В последние годы появилась новая перспективная технология в телекомму-
никационных сетях — технология АТМ (Asynchronous Transfer Mode) —
асинхронный режим доставки, которая дает возможность передавать разные
виды информации: речь, видео -, аудиоинформацию, сжатые видео- и ау-
диоинформацию, данные с высокими (155 Мбит/с, 622 Мбит/с) и сверхвы-
сокими (2488 Мбит/с) скоростями.
Используются унифицированные методы и средства передачи разно-
родной информации. Форум АТМ ввел такие категории передачи [1]:
• с постоянной скоростью — CBR (constant bit rate);
• с переменной скоростью — VBR (variable bit rate), которая разделяет-
ся на две подкатегории: передача в реальном времени (аудио- и видеоинфо-
рмация) — VBRrt и передача в реальном времени — VBRnrt;
• с доступной скоростью данных и программ — АBR (available bit rate);
• с неустановленной скоростью — передача наименее ответственных
данных (электронная почта, служба новостей) — UBR.
Для разных категорий трафика форум АТМ ввел также показатели ка-
чества обслуживания )( 0SQ :
• CTD (Cell Transfer Delay) — задержка в передаче ячеек;
• CDV (Cell Delay Variance) — вариация величины задержки;
• CLR (Cell Loss Ratio) — вероятность потери ячеек.
Наиболее жесткие значения этих показателей устанавливаются для
трафика CBR, менее жесткие — для VBR и, наконец, наиболее низкие значе-
ния — для трафика АBR.
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 94
Учитывая очень высокие требования к показателям SQ0 , для трафика
CBR выделяется постоянная часть полосы в каждом канале (физической ли-
нии). Если величина трафика CBR постепенно снижается, то часть полосы
CBR остается неиспользуемой. Для VBR и АBR выделяется общая часть по-
лосы, которая распределяется таким образом: трафик VBR занимает боль-
шую часть полосы и обслуживается в коммутаторах с высшим относитель-
ным приоритетом по дисциплине FIFO, а если в очереди коммутатора нет
ячеек VBR, то передаются ячейки трафика АBR. И, наконец, оставшаяся
часть полосы канала (если таковая имеется) используется для передачи тра-
фика UBR, причем для него параметры SQ0 не устанавливаются.
При проектировании сетей АТМ возникает проблема анализа, оптими-
зации характеристик и синтеза структуры сетей АТМ.
В настоящее время отсутствуют теоретические основы расчета, анализа
и оптимизации функциональных характеристик и синтеза структуры сетей
АТМ. Поэтому цель настоящей статьи — разработка и исследование мето-
дов анализа и синтеза сетей АТМ и создание на их основе соответствующе-
го комплекса алгоритмов и программ для задач проектирования сетей с тех-
нологией АТМ и обоснования принимаемых проектных решений.
В процессе проектирования новых сетей приходится решать комплекс
взаимосвязанных задач, среди которых можно выделить такие функцио-
нальные группы:
1. Анализ характеристик сетей АТМ.
2. Анализ показателей живучести сетей.
3. Структурный синтез сетей АТМ.
К группе задач анализа и оптимизации характеристик сетей относятся:
• выбор пропускных способностей каналов связи (ВПС);
• выбор маршрутов передачи и распределения потоков разных катего-
рий (РП);
• комбинированная задача выбора пропускных способностей и расп-
ределения потоков (ВПС РП).
К задачам структурного синтеза относятся:
• синтез корпоративной сети с коммутаторами данных;
• синтез структуры глобальной сети при ограничениях на заданные
значения SQ0 (показателей качества).
Подчеркнем, что постановка задачи анализа и синтеза сетей должна
учитывать специфику сетей АТМ и, в частности, наличие различных катего-
рий сервиса: CBR, VBR и ABR, а также наличие показателей качества для
них: CTD, CDV и CLR. Кроме того, для решения задач анализа сетей необ-
ходимо прежде всего найти аналитические модели для оценки показателей
качества SQ0 в зависимости от выбранных величин пропускных способно-
стей (ПС) и величин потоков.
Перейдем к рассмотрению постановок задач анализа и синтеза сетей АТМ.
Для решения задач анализа и оптимизации характеристик сетей АТМ
по SQ0 необходимо было прежде всего разработать аналитические модели
оценки показателей качества для разных категорий трафика в зависимости
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 95
от интенсивности входных потоков, ПС каналов и распределения потоков
по каналам. На основе аппарата систем и сетей массового обслуживания в
работе [2] получены такие аналитические модели оценки SQ0 :
для трафика CBR
{ }( ) ∑
∈Σ −
=
Esr
CBR
rsrs
CBR
rs
CBR
rsCBR
fn
f
H
CTD
),(
')0(
1
µ
µ , (1)
N
rsrs
CBR
rs
rs
n
rs
CBR
rs
krs n
f
n
f
PPCLR
rs
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
′′⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
==
′
µµ
µ
!
1)( 0 , (2)
где rsµ — пропускная способность каналов связи (КС), выделенная под
трафик CBR; rsn′ — число базовых цифровых каналов (64 кбит/с), выделен-
ных под трафик CBR в КС ),( sr ; CBR
rsf — поток трафика CBR в КС ),( sr ;
N — размер буфера коммутатора АТМ для ячеек трафика CBR; 0P — нор-
мирующий множитель.
Рассмотрим показатели качества трафиков VBR и ABR, которые исполь-
зуют общую полосу, причем трафик VBR является более приоритетным. Со-
гласно работе [2], средние задержки в КС ),( sr
для трафика VBR
( )( )
( ) ( )
( )( )1
21
1
rsrsrs
rsrs
rsrsrs
rsVBR
rs f
ff
f
t
−
+
=
−
=
Σ
µµµµ
λ , (3)
для трафика ABR
( ) ( )
( )( ) ( ) ( )( )211
21
rsrsrsrsrs
rsrsABR
rs
fff
ff
t
−−−
+
=
µµ
, (4)
и величины средних задержек в сети АТМ в целом, усредненные по всем
парам узлов:
для трафика VBR
( ) ( )( )
( )( )( )
∑
∈Σ −
+
=
Esr rsrsrs
rsrsrsVBR
f
fff
H
T
,
1
21)1(
)1(ср
1
µµ
, (5)
для трафика ABR
( ) ( )( )
( )( ) ( ) ( )( )∑
∈Σ −−−
+
=
Esr rsrsrsrsrs
rsrsrsABR
fff
fff
H
T
),(
211
21)2(
)2(ср
1
µµ
, (6)
где )2()1( , rsrs ff — величины потока (трафика) в канале ( )sr, соответственно
категориям VBR и ABR; )1(
ΣH , )2(
ΣH — общая величина внешнего потока
соответственно для VBR и ABR.
На основе полученных аналитических моделей для оценки показателей
качества ( SQ0 ) в работах [2, 3] сформулированы и решаются описанные
ниже задачи анализа и оптимизации характеристик сетей АТМ.
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 96
1. ЗАДАЧА ВПС И АЛГОРИТМ ЕЕ РЕШЕНИЯ
Постановка задачи
Задана структура сети АТМ в виде графа ( )EXG ,= , где { }
njjxX
,1=
= —
узлы сети (коммутаторы АТМ) и ( ){ }srE ,= — множество дуг (каналов свя-
зи). Имеем возможный набор пропускных способностей (скоростей переда-
чи) КС { }NdddD ,,, 21 …= , из которых осуществляется выбор. Заметим, что
для сетей АТМ эти скорости кратны базовой скорости цифрового канала
0DS 64 Кбит/с или канала 1DS — 1,544 Мбит/с.
Известны также удельные стоимости каналов разной пропускной спо-
собности { }NcccC ,,, 21 …= . Тогда стоимость канала связи длиной jil , и
скоростью передачи kd равняется ( ) ijkijkij lCldC =,пер .
Пусть также задана матрица требований jihH ,= в передаче трафика
CBR, где ijh — интенсивность потока, которую необходимо передать от уз-
ла i в узел j (Мбит/с). Кроме того, пусть при заданных виртуальных путях
передачи трафика ( )ijCBR π между всеми узлами определена величина об-
щего потока CBR в канале связи ( )sr, )1(
rsf и вектор потока ( ) [ ])1(1
rsfF = .
Необходимо выбрать такие пропускные способности всех каналов свя-
зи { } Mrs =µ , при которых стоимость сети CBR будет минимальной
( ) )(
),(
пер
rs
Esr
rsCMC µ∑
∈
Σ = , (7)
и при этом должны выполняться такие ограничения:
на допустимую среднюю вероятность потери ячеек
( )
( )
∑ ≤=
sr
rsrsrs CLRfCLR
m
CLR
,
зад,1 µ ; (8)
на допустимую задержку ячеек CBR, среднюю по сети
{ }{ }( ) CBR
rsrs
CBR TfT задср ; ≤µ (9)
и очевидных условиях rsrsf µ< ; ( ) Esr ∈, , Drs ∈µ .
Здесь задCLR — заданный уровень (%) потерь ячеек CBR; CBRTзад — за-
данная средняя задержка ячеек CBR в сети.
Выбор пропускных способностей каналов для трафиков VBR и ABR
Рассмотрим теперь постановку задачи ВПС для трафиков VBR и ABR [3].
Пусть заданы матрицы требований в передачи трафика VBR
njiij
VBR hH
,1,
)2(
2
=
= и ABR
njiij
ABR hH
,1,
)3(
3
=
= , и при заданных виртуальных
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 97
каналах (путях) поток ячеек VBR равняется )1(
rsf , а ячеек ABR — )2(
rsf . Пусть
выбор осуществляется из того же самого набора пропускных способностей
{ }NdddD ,,, 21 …= , что и раньше. Надо найти такие ПС { }rsµ этих каналов,
а также их часть, занятую трафиком VBR, при которых обеспечивается
( )∑
∈
Σ =
Esr
rsrsCC
),(
перmin µ (10)
при выполнении ограничений на показатели качества обслуживания трафи-
ков VBR и ABR
( ) ( ) VBR
Esr
rsrsrsVBR CLRfCLR
m
FMCLR зад
),(
)1()1( ,1, ≤= ∑
∈
µ , (11)
( ) VBR
VBR
VBR TFMT зад
)1(
ср , ≤ , (12)
( ) ABR
VBRАBR
ABR TFFMT зад
)1()2(
ср /, ≤ , (13)
где для расчета задержек используем модель СМО rsrs NnMM /// с двумя
потоками и приоритетным обслуживанием с относительными приоритетами
и дисциплиной FIFO (5), (6). Алгоритм ее решения приведен в работе [3].
2. ВЫБОР ОПТИМАЛЬНЫХ МАРШРУТОВ ПЕРЕДАЧИ И
РАСПРЕДЕЛЕНИЕ ПОТОКОВ В СЕТЯХ С ТЕХНОЛОГИЕЙ АТМ
Постановка задачи
Задана структура сети в виде орграфа ),( EXG = , }{ jxX = , nj ,1= — мно-
жество узлов сети — коммутаторов; )},{( srE = — множество каналов связи
(дуг).
Заданы также матрицы требований для передачи трафика VBR
n,ji,
)(
ij
)(
VBR hH
1
11
=
=
и трафика ABR
n,ji,
)(
ij
)(
ABR hH
1
22
=
= ,
где )2()1(
ijij h,h — интенсивность потока ячеек (cell/c), который необходимо
передать от узла i к узлу j . Для VBR и ABR заданы соответственно пропу-
скные способности каналов µnµ rsrs = , где rsn — количество цифровых ка-
налов типа 0DS ( 64=µ Кбит/с) или 1DS ( 544,1=µ Мбит/с), организован-
ных в КС ),( sr .
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 98
Нужно выбрать такие маршруты передачи и найти распределение пото-
ков для трафиков VBR ][ )1()1(
rsfF = и ABR ][ )2()2(
rsfF = , при которых обеспе-
чивался бы минимум вероятности потери ячеек VBR
)(min 1 )(
VBR F CLR (14)
при ограничении на среднюю задержку ячеек VBR
VBRVBR TFT зад
)1(
ср )( ≤ (15)
на среднюю задержку ячеек ABR
ABRABR TF|FT зад
)1()2(
ср )( ≤
и очевидных условиях
Esr,µ, nµff rsrsrsrs ∈∀=<+ )(21 .
Для решения задачи РП предложен модифицированный алгоритм РП,
описанный в работе [2].
3. ОПТИМАЛЬНЫЙ ВЫБОР ПРОПУСКНЫХ СПОСОБНОСТЕЙ И
РАСПРЕДЕЛЕНИЕ ПОТОКОВ (ВПС РП)
Постановка задачи
Рассмотрим теперь комбинированную задачу ВПС РП.
Задана структура сети АТМ в виде графа ( )EXG ,= , где { }
njjxX
,1=
= —
узлы сети (коммутаторы АТМ) и ( ){ }srE ,= — множество дуг (каналов свя-
зи). Имеем возможный набор пропускных способностей (скоростей переда-
чи) каналов связи { }NdddD ,,, 21 …= , из которых осуществляется выбор,
известные удельные стоимости каналов разной пропускной способности
{ }NcccC ,,, 21 …= . Пусть также задана матрица требований jiCBR hH = для
передачи трафика CBR, где ijh — интенсивность потока, который необхо-
димо передать от узла i в узел j (Мбит/с). Заданы также матрицы требова-
ний для передачи трафика VBR ( ) ( )
,nji,ijVBR hH
1
11
=
= и трафика ABR
( ) ( )
n,ji,ijABR hH 1
22
=
= .
Необходимо выбрать пропускные способности всех каналов связи
{ } Mrs =µ , часть общей полосы каналов, выделенную под трафики соответ-
ственно CBR, VBR, ABR, а также найти такое распределение потоков для
трафиков CBR,VBR, ABR, для которых стоимость сети будет минимальной
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 99
( )
( )
( )rs
Esr
rsCMC µ∑
∈
Σ =
,
пер (16)
и при этом будут выполняться ограничения
на допустимую среднюю вероятность потери ячеек
( )
( )
∑ ≤=
sr
CBR
rsrsrs
CBR CLRfCLR
m
CLR
,
зад,1 µ , (17)
на допустимую задержку ячеек CBR, среднюю по сети
{ }{ }( ) CBR
rsrs
CBR TfT задср ; ≤µ ,
а также на показатели качества обслуживания трафиков VBR и ABR
( )( ) ( )( )
( )
VBR
Esr
rsrsrsVBR CLRfCLR
m
FMCLR зад
,
11 ,1, ≤= ∑
∈
µ ,
( )( ) VBR
VBR
VBR TFMT зад
1
ср , ≤ , (18)
( ) ( )( ) ABR
ABRVBR
ABR TFFMT зад
21
ср , ≤ (19)
и очевидных условиях rsrsf µ< ; ( ) Esr ∈, ; Drs ∈µ .
Описание алгоритма ВПС РП
Учитывая, что для трафика CBR выделяется постоянная полоса, независимо
от текущего потока и от трафиков VBR и ABR, а под трафики VBR, ABR вы-
деляется общая часть полосы канала, целесообразно рассмотреть алгоритм
решения данной задачи отдельно для трафика CBR, а также для смеси тра-
фиков VBR и ABR.
На предварительном этапе находим начальное распределение трафиков
VBR и ABR ( ) [ ( ) ( ) ],00 1
rsVRB fF = ( ) [ ( ) ( ) ]00 2
rsABR fF = . Дале решаем задачу
ВПС и находим начальные пропускные способности всех каналов ( ) =01M
( ) ( ){ }01
rsµ= . Вычисляем начальную стоимость сети ( ) ( )( )
( )
∑
∈
Σ =
Esr
rssrcC
,
, 00 µ и
переходим к основному этапу [2].
Основной этап, ( )1+k -я итерация
Итак, пусть найдены пропускные способности всех каналов ( )[ ]krsµ , распре-
деление потоков ( ) ( )kFkF ABRVBR , и стоимость сети ( )kCΣ .
1. При заданных ПС ( )krsµ решаем задачу РП для смеси трафиков VBR,
ABR и находим такое распределение потоков ( )1+kFVBR и ( )1+kFABR , для
которых обеспечивается минимум ( )( )1+kFCLR VBRVBR при ограничениях
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 100
( )( ) VBR
VBR
VBR TFMT зад
1
ср , ≤ ;
( ) ( )( ) ABR
VBRABR
ABR TFFMT зад
22
ср , ≤ . (20)
Для этого используем алгоритм РП, описанный в работе [2].
2. При найденном распределении потоков ( )1+kFVBR и ( )1+kFABR ре-
шаем задачу ВПС и находим такие значения пропускных способностей
( ){ }1+krsµ , для которых достигается
( )
( )
∑
∈
Σ =
Esr
rsrsCC
,
перmin µ (21)
при выполнении ограничений на показатели качества обслуживания трафи-
ков VBR и ABR ( )( ) VBR
VBR
VBR TFMT зад
1
ср , ≤ и ( ) ( )( ) ABR
ABRVBR
ABR TFFMT зад
12
ср , ≤ .
3. Вычисляем значения критерия ( ) ( )( )11 +=+ ΣΣ kCkC rsµ . Сравниваем.
Если ( ) ( ) ε≤−+ ΣΣ kCkC 1 , то конец работы алгоритма, иначе переходим к
( )2+k -й итерации.
Таким образом, в результате решения задачи ВПС РП находим одно-
временно пропускные способности всех КС (из заданного набора), а также
распределение потоков всех категорий такое, при котором стоимость сети
минимальна при заданных ограничениях.
4. СИНТЕЗ СТРУКТУРЫ СЕТЕЙ С ТЕХНОЛОГИЕЙ АТМ
Одной из важнейших задач, которые возникают при проектировании теле-
коммуникационных сетей, является задача выбора (синтеза) структуры сети.
Эта задача рассматривалась многими авторами [4, 5, 6]. Традиционно она
формулируется как задача выбора рациональной или оптимальной структу-
ры коммуникационной сети, связывающей все источники и потребители
информации. Критерием качества обычно выступает стоимость коммуника-
ционной сети (или приведенные затраты на ее создание), а как ограниче-
ние — средняя задержка в доставке информации. Как дополнительные огра-
ничения могут быть использованы время задержки между заданными
парами узлов (конечных пользователей сети), а также ограничение на пока-
затели живучести сети [5]. Переход к новой коммуникационной технологии
АТМ с разнородными видами трафика и соответствующими значениями
показателей качества не позволяет использовать традиционные модели и
алгоритмы синтеза для решения задач структурного синтеза сетей АТМ.
Поэтому данная работа посвящена проблеме синтеза структуры сетей
АТМ с учетом установленных ограничений на показатели качества 0QS для
различных категорий сервиса.
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 101
4.1. Постановка и математическая модель задачи синтеза структуры
сетей АТМ
Заданы трафики конечных пользователей (конечные станции АТМ), комму-
таторов сети АТМ, матрицы требований для передачи информации:
CBR
),1(,
1
nji
CBR
ijCBR hH
=
= ;
VBR
),1(,
1
nji
VBR
ijVBR hH
=
= ;
ABR
),1(,
3
nji
ABR
ijABR hH
=
= ;
набор пропускных способностей КС сети АТМ { }ndddD ,...,, 21= и их
удельных стоимостей { }ncccC ,,, 21 …= на одну единицу длины. Нужно най-
ти такую структуру сети )},{( srE = , пропускные способности всех КС
{ }rsµ и распределение всех потоков трафиков CBR, VBR и ABR, для кото-
рых минимизируется общая стоимость сети при ограничениях на заданные
показатели качества ( 0QS ) разных типов трафика: T CBR
зад , TVBR
зад и T ABR
зад ,
CLRVBR
зад , CLRCBR
зад .
Решение этой задачи базируется на алгоритмах анализа и оптимизации
характеристик сетей АТМ и, в частности, на алгоритме выбора маршрутов и
РП, предложенного в работе [2], а также алгоритме оптимального выбора
пропускных способностей (ВПС) каналов сети АТМ [3].
Математическая модель данной задачи синтеза имеет следующий вид.
Найти такую структуру сети )},{(0 srЕ = и пропускные способности
{ Mrs =µ }, распределение потоков трафиков CBR { f CBR
rs }, VBR-{ f VBR
rs } и
ABR — { f ABR
rs }, при которых обеспечивается
∑
∈
Σ =
Esr
rsrs
MFE
CC
),(
0
,,
)(min
0
µ (22)
при условиях
( ) CBRCBRCBR
CBR CLRFMCLR зад0, ≤ , (23)
( ) TFMT CBRCBRCBRCBR
зад0ср , ≤ , (24)
( ) TFMT VBRVBRVBR
зад11ср , ≤ , (25)
( ) VBRVBRABR
VBR CLRFFMCRL зад121 ,, ≤ , (26)
( ) TFFMT ABRVBRABRABR
зад121ср ,, ≤ , (27)
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 102
где 0)2()1( ),(, Esrnff rsrsrs ∈∀≤+ µ , потоки )0(
rs
CBR
rs ff = , )1(
rs
VBR
rs ff = и
)2(
rs
ABR
rs ff = представляют собой соответственно многопродуктовые потоки
трафиков CBR, VBR и ABR, совместимые с матрицами HH VBRCBR
21 , и H ABR
3 .
Особенности данной задачи синтеза состоят в следующем.
1. Наличие большого числа ограничений (23) – (27).
2. Поскольку в связи со спецификой трафика CBR для него полоса про-
пускной способности в любом КС выделяется постоянно и независимо от
распределений потока, то это позволяет решать задачи анализа и оптимиза-
ци для трафика CBR независимо от потоков VBR и ABR, т. е. выделить эту
задачу в отдельную задачу синтеза.
3. Задача синтеза структуры сети для передачи трафиков VBR и ABR
должна решаться совместно для обоих трафиков с учетом более высокого
приоритета трафика VBR.
4.2. Алгоритм синтеза структуры сети АТМ при ограничениях на пока-
затели качества ( SQ0 )
Учитывая многоэкстремальный комбинаторный характер задачи синтеза
(22) – (27), для ее решения предлагается генетический алгоритм глобальной
оптимизации [10].
На предварительном этапе проводим синтез начального кратчайшего
связного дерева D0, которое связывает все узлы между собой. Для этих це-
лей используется алгоритм синтеза, описанный в работе [4]. Далее структу-
ра D0 случайным образом дополняется некоторыми каналами к связности
2KC = . При этом генерируется также случайным образом популяция из
трех начальных структур 2,1,0 EEE .
Переходим на первую итерацию оптимизации второго этапа, на кото-
рой генерируется случайным образом популяция из трех начальных струк-
тур ( ) ( ) ( )0,0,0 321 EEE .
Описание (k+1)-й итерации
Пусть в памяти системы сохраняется последовательность структур
)(Π)(3),(2),(1 kkEkEkE = , которым отвечают значения критерия
))(( 1 kEC∑ , ))(( 2 kEC∑ , ))(( 3 kEC∑ .
Случайным образом, с вероятностями, обратно пропорциональными
))(( kEC i∑ , выбирается структура )(kEi .
Для нее определяется множество каналов-претендентов на удаление.
)},{()(уд srkPi = — это те каналы, удаление которых не нарушает связ-
ности сети )(kEi .
1. Для любого из КС ),( sr вычисляется показатель неэкономичности
µ
µ
rs
k
rsrsrsk
rs
fCq
)( )(
)( −
= ,
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 103
где Crs — стоимость КС ),( sr ; µ rs — его ПС; f k
rs
)( — поток в КС ),( sr .
2. Вычисляются вероятности удаления КС ),( sr
∑
∈
=
Psr
k
rs
k
rs
rs
q
q
P
уд),(
)(
)(
.
3. Определяется множество каналов )},{()( jikPi
вв = претендентов на
введение в структуру )(kEi .
nji
i jiP ,1,вв )},{( == \ )(kEi .
4. Для любого КС iPji вв),( ∈ вычисляется экономический эффект от его
введения
( ) ijjiij
в
ij СhhG ∆+= )1()1()( ,
где )()( hhCШCC jiijijijij +−=∆ , )( ijШC — стоимость передачи информа-
ции между несмежными узлами ),( ji в сети )(kEi по пути ijШ ;
)( hhC jiijij + — стоимость введения прямого канала ),( ji .
5. С помощью случайного механизма выбирается один из механизмов
изменения iГ с вероятностью )( iГP 2,1=i , где 1Г — режим изменения:
удалить неэкономичный канал из структуры )(kEi ; 2Г — ввести новый ка-
нал в структуру )(kEi .
6. Если избранный режим 1Г , то, используя вероятностный механизм,
определяем с вероятностью Prs канал, который удаляется из сети. Получаем
структуру )(' kEi .
6.1. Для структуры )(` kEi решаем задачу ВПС РП и находим новые
ПС всех каналов {( )(krsµ′ )} и новое распределение потоков { f k
rs
)( }, для
чего используем алгоритм ВПС РП.
6.2. Определяем величину критерия ( ))(' kEC iΣ и сравниваем ( ))(' kEC iΣ
и ( ))(kEC iΣ . Если ( ) ( ))()(' kECkEC ii ΣΣ < , то заменяем структуру iE на
)(' kEi . Положим )()1( ' kEkE ii =+ и записываем в последовательность ло-
кально-эффективных структур ))(( kEiεΠ . В противоположном случае уда-
ляем КС ),( sr из множества претендентов на удаление: srkPkPH ,\)()( удуд =
и снова переходим на выполнение k -й итерации.
6.3. Корректируем вероятности выбора каналов на удаление: PH
rs с уче-
том множества )(уд kРН .
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 104
7. Если же избран режим 2Γ (введение ребра), то последовательность
шагов будет аналогичная.
7.1. С вероятностью
∑
∈
=
Pji
ij
ij
ij
G
G
P
вв),(
вв
вв
выбираем для введения канал ),( ji .
Получаем структуру ),()()( 11
'' jikEkE ii ∪= .
7.2. Решаем задачу ВПС РП для структуры )('' kEi и находим новое
распределение потоков РП в [ )(kf rs′′ ] и пропускные способности всех КС
{ )(krsµ ′′ }.
7.3. Сравниваем значения критерия ( ))('' kEC iΣ с ( ))(kEC iΣ . Если
( ) ( ))()('' kECkEC ii ΣΣ < , то фиксируем новую структуру )1()( ''' += kEkE ii , за-
писываем ее в память в последовательность ( ))(kEiΠ . Конец итерации.
В противоположном случае восстанавливаем исходную структуру
)(kEi , удаляем канал ),( ji из множества претендентов ),(\)( вввв jiPkPH = и
снова переходим на шаг1 )1( +k -й итерации.
Указанную последовательность шагов на )1( +k -й итерации повторяем
до тех пор, пока не получим новую структуру )(' kEi , для которой будет вы-
полняться условие локальной оптимизации ( ) ( ))()( kECkEC ii ΣΣ <′′ . В этом
случае записываем новую структуру ( )kEi
' вместо структуры ( )kEi в после-
довательность ( )( )kEiΠ . Конец итерации.
В противоположном случае выбираем другую структуру из последова-
тельности ( ) ( )kEk i1−Π , 3,2=i с вероятностями
( )( )
( )( )∑ −
Σ
−
Σ=
i
i
i
i
kEC
kEC
P 1
1
1
1
.
Повторяем с ней описанные шаги 1 – 7, и если ( )( )<+′Σ 1
1
kEC i
( )( )kEC i1Σ< , то фиксируем новую структуру в памяти системы.
Процесс синтеза на основе генетического алгоритма повторяется до тех
пор, пока не придем к случаю ( ) ( )kEkE ii <+1 , и тогда фиксируем новую
структуру ( )1+′ kEi вместо исходной в последовательности локально-
оптимальных структур ( )( )kEiΠ . Конец итерации.
В противном случае, если исчерпаны все возможные варианты синтеза
новой более экономичной структуры ( )1+kEi , то Stop, найдена искомая
оптимальная структура глобальной сети АТМ. Конец работы алгоритма.
Замечание. Использование генетического алгоритма для оптимизации
структуры сети АТМ обеспечивает возможность достижения глобального
оптимального решения.
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 105
5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ КОМПЛЕКСА
АЛГОРИТМОВ
В соответствии с предложенными алгоритмами анализа характеристик и
синтеза структуры сетей с технологией АТМ был разработан программный
комплекс ATM NETBUILDER [12]. Функциональная структура комплекса
приведена на рис. 1.
Здесь указаны функциональные взаимосвязи и информационные ин-
терфейсы между всеми программными модулями. Проведены многочислен-
ные экспериментальные исследования алгоритмов и программ анализа ха-
рактеристик и синтеза структуры сетей. Некоторые из полученных
результатов приведены ниже.
Задача выбора маршрутов и оптимального распределения потоков
(РП). Данный алгоритм позволяет найти оптимальное распределение пото-
ков для трафиков CBR, VBR и ABR по критерию минимизации вероятности
потери ячеек высокоприоритетного трафика VBR при ограничениях на пока-
затели качества (CTD) трафиков VBR и ABR. Проведены экспериментальные
исследования разработанного алгоритма и программы [2]. Размещение узлов
исследуемой сети АТМ приводится в таблице.
Характеристика узлов сети
Координаты Номер
узла х у
Тип узла Город
0 31 33,5 1 Киев
1 47 23 1 Днепропетровск
2 51 32 1 Харьков
3 57,5 21 1 Донецк
4 31,5 11,5 1 Одесса
5 47,5 19,5 1 Запорожье
6 1,5 25,5 1 Ужгород
7 8 31,5 1 Львов
8 16 35 1 Ровно
9 14,5 22,5 1 Черновцы
10 24,5 33 1 Житомир
11 23,5 27 1 Винница
12 33,5 39,5 1 Чернигов
13 38,5 13 1 Херсон
14 46 36,5 1 Сумы
В экспериментах задавались следующие параметры коммуникационной
сети: пропускная способность одного цифрового канала, который входит в
линию связи 64=µ Кбит/c, память в буфере коммутатора 2,5 Кбит/c. Огра-
ничение на среднюю сетевую задержку трафика VBR составляет 20мс, а на
среднюю задержку трафика ABR — 50мс.
В экспериментах исследовались зависимости средней вероятности по-
тери ячеек и средних задержек трафиков VBR и ABR от величины входного
трафика VBR.
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 106
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 107
Будем варьировать объём трафика VBR, изменяя коэффициент k_VBR в
диапазоне [3,5 – 4,5]. VBRVBR HVBRkkH *_)( = .
На рис. 2 показана зависимость вероятности потери ячеек типа VBR, на
рис. 3 — зависимость средней задержки трафика VBR, а на рис. 4 — зависи-
мость средней задержки трафика ABR от изменения величины k_VBR.
Проанализировав эти графики, можно сделать вывод: зависимость
CLP_VBR при изменении k_VBR нелинейная, средняя задержка T_VBR из-
меняется по линейному закону, а средняя задержка для трафика ABR изме-
няется по экспоненциальному закону. Далее были проведены эксперимен-
тальные исследования изменения показателей T_ABR от интенсивности
трафика ABR (рис. 5).
Проведенные исследования показали, что средняя вероятность потери
ячеек трафика VBR не зависит от величины ABR, а средняя задержка VBR
слабо зависит от величины трафика ABR (k_ABR).
Это легко объясняется тем, что трафик ABR является менее приоритетным,
чем VBR. Что же касается средней задержки ABR, то она резко возрастает
(по нелинейному закону) и при значении 15_ =ABRk трафик ABR достигает
такой интенсивности, что средняя задержка не может быть оптимизирована
так, чтобы удовлетворить введенному на нее ограничению cΑΒRT 05,0_ ≤ .
0
0,005
0,01
0,015
0,02
0,025
0,03
0,035
0,04
4,1 4,2 4,3 4,4 4,5k_VBR
CLR_VBR
Рис. 2. Зависимость CLP_VBR от величины k_VBR
0
0,0002
0,0004
0,0006
0,0008
0,001
0,0012
0,0014
4,1 4,2 4,3 4,4 4,5
Рис. 3.Зависимость Т_VBR от K_VBR
k_VBR
T_VBR
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 108
6. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ АЛГОРИТМА
СТРУКТУРНОГО СИНТЕЗА ГЛОБАЛЬНЫХ СЕТЕЙ АТМ
Задача синтеза решалась для сети АТМ с набором узлов (см. таблицу). Были
заданы такие вероятности потери ячеек и допустимые задержки (ограниче-
ния на SQ0 ):
18,0зад =VBRCLR ; cTVBR 15,0зад = ; cTABR 5,0зад = .
В результате работы программы синтезированы начальная (D0) (рис. 6)
и конечная оптимальная структура сети АТМ (рис. 7).
При этом получены следующие показатели вероятности потери ячеек и
средней задержки для синтезированной структуры:
17034,0=VBRCLR ; c004171,0=VBRT ; c047317,0=ABRT .
0
0,005
0,01
0,015
0,02
0,025
4,1 4,2 4,3 4,4 4,5k_VBR
T_ABR
Рис. 4. Зависимость T_ABR от величины k_VBR
0
0,01
0,02
0,03
0,04
0,05
0,06
0,07
0,08
11 12 13 14 15k_ABR
Рис. 5. Зависимость T_ABR от величины k_ABR
T_ABR
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 109
Стоимость начальной сети D0 составляет 144113518,5 у.е., конечной
оптимальной синтезированной структуры — 34153987,82 у.е. Таким обра-
зом, в результате применения программы оптимизации структуры стои-
мость сети сокращена на 70%.
В последующих экспериментах решалась задача структурного синтеза
сети при вариации матрицы требований VBRH . На рис. 8 приводится итого-
вая структура сети АТМ для коэффициента увеличения потока VBR
Рис.6. Начальная структура D0
Рис. 7. Конечная синтезированная структура сети
Днепропетровск (2)
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 110
2=VBRk , на рис. 9 — гистограмма распределения загрузок каналов связи,
на рис. 10 — синтезированная структура для 5=VBRk , на рис. 11 — соответ-
ствующая гистограмма распределения загрузок каналов.
Анализ полученных структур свидетельствует об устойчивости базовой
структуры сети в широком диапазоне вариации входных потоков, что под-
тверждает корректную работу алгоритма синтеза структуры. С другой сто-
роны, анализ рис. 9 и 11 показывает: при увеличении коэффициента kVBR пик
загрузки и средняя загрузка каналов увеличиваются, что вполне согласуется
с теорией. Кроме того, следует подчеркнуть, что алгоритм ВПС РП дает
равномерную загрузку всех каналов.
Рис. 8. Итоговая структура сети АТМ
Рис. 9. Гистограмма распределения загрузок каналов связи: минимальная загруз-
ка — 40%, канал «Киев-Узел 11»; максимальная загрузка — 82%, канал «Киев-
Узел 10»; средняя загрузка каналов — 62%
Чи
сл
о
ка
на
ло
в
%
Анализ и синтез сетей с технологией АТМ
Системні дослідження та інформаційні технології, 2003, № 4 111
ВЫВОДЫ
1. В статье рассмотрен комплекс моделей, алгоритмов и программ ана-
лиза характеристик и синтеза структуры сетей с технологией АТМ. Приве-
дены аналитические модели для оценки основных показателей качества се-
тей АТМ — средней задержки доставки ячеек CTD и вероятности их потери.
2. Сформулированы задачи анализа характеристик сетей АТМ — выбор
пропускных способностей (ВПС), распределение потоков (РП) и комбини-
рованная задача (ВПС РП).
Рис. 10. Синтезированная сеть с расчетными данными для kvbr=5
Рис. 11. Гистограмма распределения загрузок каналов связи: минимальная за-
грузка — 76%, канал «Узел 4 – Узел 3»; максимальная загрузка — 96%, канал «Ки-
ев – Узел 11»; средняя загрузка каналов — 85%
Чи
сл
о
ка
на
ло
в
%
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2003, № 4 112
3. Сформулирована задача структурного синтеза сетей АТМ при огра-
ничениях на заданные значения показателей качества и описан алгоритм ее
решения.
4. Описана структура программного комплекса, реализующего предло-
женные алгоритмы, и приводятся результаты некоторых экспериментов.
5. Применение разработанного комплекса алгоритмов и программ по-
зволяет оптимизировать функциональные характеристики сетей АТМ, син-
тезировать структуру проектируемых сетей, а также снизить затраты време-
ни и средств на проектирование и создание сетей АТМ.
ЛИТЕРАТУРА
1. Кульгин М. Технология корпоративных сетей. — СПб.: Питер, 1999. — 710 с.
2. Зайченко О.Ю. Вибір маршрутів передачі та оптимальний розподіл потоків у
мережах з технологією АТМ //Наук. вісті НТУУ «КПІ». — 2001. — № 4. —
С.16–24.
3. Зайченко О.Ю. Оптимальний вибір пропускних здатностей каналів зв’язку в
мережах АТМ // Наук. вісті НТУУ «КПІ». — 2000. — № 6. — С. 48–53.
4. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. — Ки-
ев:Техніка, 1986. — 168с.
5. Зайченко Е.Ю. Анализ и синтез структуры глобальных вычислительных се-
тей. — Киев: ЗАО «Укрспецмонтаж», 1998. — 108 с.
6. Клейнрок Л. Вычислительные системы с очередями. — М.: Мир, 1979. —
600 с.
7. Зайченко О.Ю. Аналіз показників живучості мереж з технологією АТМ // Наук.
вісті НТУУ «КПІ». — 2001. — № 3. — С. 14–21.
8. Зайченко О.Ю. Оптимізація характеристик мереж с технологією АТМ //
Системні дослідження та інформаційні технології. — 2002. — № 3. —
С. 57–73.
9. Зайченко О.Ю., Зайченко Ю.П. Знаходження максимального потоку в мережах
з режимом асинхронної передачі інформації // Відбір і обробка інформа-
ції. — Вип.17(93). — 2002. — С. 59–64.
10. Зайченко О.Ю. Структурний синтез глобальних мереж з технологією АТМ за
показниками обслуговування // Наук. вісті НТУУ «КПІ». — 2001. —
№ 5. — С. 5–11.
11. Синтез структури корпоративної мережі з комутаторами / Ю.П. Зайченко,
О.Ю. Зайченко, Д.М. Вішталь, Р.Ф. Хотячук // Наук. вісті НТУУ «КПІ». —
2001. — № 6. — С. 5 — 14.
12. Інструментальний комплекс алгоритмів і програм структурного аналізу та си-
нтезу мереж «АТМ NETBUILDER» / О.Ю. Зайченко, Ю.П. Зайченко,
О.А. Аврутін, Д.Д. Архипенко, І.В. Панченко // Наук. вісті НТУУ «КПІ». —
2002. — № 5. — С. 10–14.
Поступила 04.06.2003
|