Структурний синтез мереж, що розвиваються
A new problem of computer networks structural synthesis with the account of dynamics of its development is considered. The algorithm of its solution is suggested. The experimental investigations of the algorithm were carried out on the example of the Ukrainian global network design.
Saved in:
| Date: | 2019 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/176058 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334390332260352 |
|---|---|
| author | Zaychenko, H. Ju. |
| author_facet | Zaychenko, H. Ju. |
| author_institution_txt_mv | [
{
"author": "H. Ju. Zaychenko",
"institution": null
}
] |
| author_sort | Zaychenko, H. Ju. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-08-15T19:35:31Z |
| description | A new problem of computer networks structural synthesis with the account of dynamics of its development is considered. The algorithm of its solution is suggested. The experimental investigations of the algorithm were carried out on the example of the Ukrainian global network design. |
| first_indexed | 2025-07-17T10:26:07Z |
| format | Article |
| fulltext |
© Е.Ю. Зайченко, 2002
Системні дослідження та інформаційні технології, 2002, 4 97
TIДC
ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО
ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ
ТА МЕРЕЖІ
УДК 683.5193
СТРУКТУРНЫЙ СИНТЕЗ РАЗВИВАЮЩИХСЯ СЕТЕЙ
Е.Ю. ЗАЙЧЕНКО
Сформулирована новая задача структурного синтеза компьютерных сетей с
учетом динамики их развития. Предложен алгоритм ее решения и приведены
экспериментальные исследования алгоритма на примере синтеза глобальной
сети Украины.
ВВЕДЕНИЕ
Процесс создания глобальных сетей занимает продолжительный период
(5–8 лет) и требует больших капитальных затрат. В связи с этим возникает
проблема планирования поэтапного развития сети из некоторого исходного
состояния в конечное, при котором сеть достигает требуемой производи-
тельности и полностью обеспечивает потребности всех абонентов в обработке
информации. Данная проблема обусловливает необходимость постановки и
решения задач проектирования структуры глобальных компьютерных сетей
с учетом динамики их развития. При такой постановке могут использовать-
ся различные критерии, но, исходя из принципа системного подхода, важно
на каждом этапе построения сети обеспечивать максимальный эффект от ее
использования.
Цель настоящей статьи — формулировка и алгоритм решения новой
задачи структурного синтеза развивающихся сетей.
ПОСТАНОВКА ЗАДАЧИ
Рассмотрим постановку динамической задачи проектирования глобальной
компьютерной сети, в которой сеть является развивающейся системой, и ее
построение представляется как многоэтапный процесс развития.
Заданы узлы сети njx j ,1; = (узлы коммутации), определены потреб-
ности в передаче информации (матрица требований) ( ) ( )thtH ij= ; nji ,1, = ,
[ ]Ttt ,0∈ , где 0t — момент начала создания сети; T — момент окончания
создания функционально полной сети; ( )thij — требуемая интенсивность
информационного обмена между ix и jx в момент времени t . Задан набор
пропускных способностей каналов связи { }ndddD ,...,, 21= и их удельных
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2002, 4 98
стоимостей { }ncccC ,,..., 21= . Введены показатели качества обслуживания
абонентов сети.
Требуется составить такой план создания сети по этапам, при котором
обеспечивается минимум приведенных затрат при заданных потребностях в
передаче информации и ограничениях на выделенные ресурсы.
В зависимости от исходных условий возможны две основные задачи
проектирования структуры развивающихся сетей.
Задача 1. Задано распределение затрат по этапам { } Kkwk ,1; = и
требуется найти оптимальную структуру сети на каждом этапе.
Задача 2. Задана общая структура затрат и требуется распределить
их по этапам оптимальным образом.
Математическая модель задачи 1. Пусть 0D — начальная структура
сети; kD — структура сети, получаемая в результате k -го этапа. В качестве
критерия эффективности используем интегральный критерий — максималь-
ный эффект от использования действующей части сети, который можно
косвенно оценить величиной суммарного потока, передаваемого по сети
( )kDHΣ .
Требуется найти такую последовательность структур сети на этапах
KDDD ,...,, 21 , при которых обеспечивается
( )∑
=
Σ
K
k
kDH
1
max (1)
при ограничениях
( ) kkk WDDW ≤∆ −1 , (2)
( ) KijKij tthDh =≤ ,зад , (3)
( ) ( )kijkij thDh зад≤ , (4)
где ( ) ( ) ( )11 −Σ−ΣΣ ∆+= kkkk DDHDHDH ; ( ) задср , TFMT ≤ ; kW — объем
капиталовложений, выделенных на этапе k .
При построении развивающейся сети вводим допущение о вложенно-
сти структур сети на последовательных этапах, т.е. KDDD ⊆⊆⊆ ...21 . По-
этому от задачи (1) мы переходим к последовательности задач вида
( )( )1max −Σ∆ kk
D
DDH (5)
при условиях
( ) kkk WDDW ≤∆ −1 , (6)
( ) ( )kijkij thDh зад≤ .
Структурный синтез развивающихся сетей
Системні дослідження та інформаційні технології, 2002, 4 99
Содержательный смысл задачи k -го этапа (5), (6) такой: имея исход-
ную структуру 1−kD и объем капитальных вложений kW , синтезировать та-
кую структуру на k -м этапе kD , которая обеспечивает максимум прироста
производительности сети.
ОПИСАНИЕ АЛГОРИТМА
Алгоритм синтеза состоит из трех частей: основной алгоритм поэтапного
синтеза развивающейся сети и вспомогательные алгоритмы: построения пу-
тей в структуре сети и максимизации потока в сети.
Основной алгоритм (А1)
Предварительный этап. Используя общий алгоритм синтеза структуры
компьютерных сетей, предложенный в [1], синтезируем конечную опти-
мальную структуру O
KD , которая определяется набором каналов и их пропу-
скных способностей, и переходим к основной части алгоритма А1.
k-я итерация
Здесь исходной информацией являются набор ПС каналов связи, их
удельные стоимости kc , матрица требований ( )ktH и объем выделенных
средств kW .
Первоначально рассматриваются все каналы, выходящие из корня де-
рева — узла 0x . Среди них находится канал ( )j,0 и его ПС с наилучшим
отношением максимальный поток / стоимость.
Пропускная способность канала ( )j,0 определяется с учетом ограниче-
ния на его стоимость, т.е. ( ) k
k
j WC ≤0µ .
Далее идут итерации, идентичные как для всех этапов, так и внутри этапа.
Итерация r
1. Просматриваются все каналы ( ) 1, −∈ kDji . Для них определяется те-
кущая пропускная способность ( )1−k
ijµ и максимально возможная, получае-
мая из ограничений набора существующих ПС { }mdddD ,...,, 211 = и не
превышения условий ( ) kij WC ≤∆ maxµ .
Далее производим подитерации при изменении только ПС данного ка-
нала ( )ji, от min
ijµ до max
ijµ и находим наилучшее отношение увеличения
потока к стоимости данного канала при увеличении ПС до данного значения
( )
ij
ij
ij C
H
q
∆
∆
=
µ
.
2. Шаг 1 выполняем со всеми каналами. В результате находим канал
( ) 1
** , −∈ kDji , для которого показатель
( ) ij
Djiji
qq
K 1
**
,
max
−∈∀
= .
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2002, 4 100
3. На данном шаге рассматриваем каналы, не входящие в структуру
1−kD , но являющиеся смежными к каналам структуры 1−kD . Для каждого
( )sr, из них выполняются одни и те же действия.
Строим структуру kD , включающую канал ( )sr, , находим в ней пути и
определяем оптимальную ПС этого канала O
rsµ , которая дает максимум по-
казателя
( )
( ) rs
rs
rs q
C
H
=
∆
µ
µmax .
4. Отыскиваем канал, не входящий в структуру ( )** , sr , с наибольшим
значением показателя эффективности
( ) rs
srsr
qq
,
max** = .
5. Сравниваем наилучший канал ( )**, ji , из множества уже сущест-
вующих в структуре 1−kD , с каналом ( )**, sr , смежным с существующими.
Если: а) **** srji
qq > , то увеличиваем пропускную способность КС
( )** , ji до оптимального значения ( )k
ji **µ , в противном случае — б) вводим в
структуру новый канал ( )**, sr с ПС **sr
µ и определяем остаток выделен-
ных нам средств на развитие сети на k -м этапе:
( ) ⎟
⎠
⎞⎜
⎝
⎛−= ** jik
H
k CWW µ — в случае а);
( ) ( )**srk
H
k CWW µ−= — в случае б).
Конец итерации.
6. Если ( )
minCW H
k ∆≥ , то переход к следующей итерации 1+r , в про-
тивном случае — конец k -го этапа. Структура kD синтезирована.
Здесь minC∆ — минимальный объем капитальных средств, достаточ-
ный для увеличения текущей ПС до следующего значения самого дешевого
канала.
ОПИСАНИЕ ВСПОМОГАТЕЛЬНОГО АЛГОРИТМА МАКСИМИЗАЦИИ
ПОТОКА (МП)
Данный алгоритм является классическим. Он соответствует описанию алго-
ритма, предложенного в [2], за исключением того, что пути строятся не
внутри данного алгоритма, а передаются извне. Это сделано для избежания
многократного построения путей на неизменной структуре.
Алгоритм состоит из предварительного этапа и однотипных итераций.
Допустим, что проведены ( 1−k ) итерация, в результате которых опре-
делен поток величиной ( )1−kH Σ .
Структурный синтез развивающихся сетей
Системні дослідження та інформаційні технології, 2002, 4 101
k-я итерация
1. Находим кратчайшие пути min
kk jiπ для еще не распределенных требо-
ваний и определяем резерв по пропускной способности пути:
( )
( ){ }εµθ
π
−−−=
∈
1min
min,
kf rsrs
sr
ji
kjki
kk
.
2. Определяем часть требования ( )kk ji , которую можно передать
a
ji kk
h : если
kkkk jijih θ< , то ( )
kkkk ji
a
ji hh = , иначе полагаем ( )
kkkk ji
a
jih θ= .
3. Вычисляем новый поток ( )1+kF :
( ) ( )
⎪⎩
⎪
⎨
⎧ ∈+
=+
случае.противномв,
;, если,
)(
)(
1
k
rs
ji
a
ji
k
rsk
rs
f
srhf
f kkkk
π
4. Проверяем ограничения ( )( ) зад
1
ср TFT k ≤+ , если выполняется, то ко-
нец k-й итерации, находим ( ) ( ) a
ji kk
hkHkH +−= 1ΣΣ и переходим к следую-
щей итерации. В противном случае переходим на 5-й шаг.
5. Уменьшаем величину передаваемого требования
kk jih до такого
значения, что ( )( ) задср 1 TkFT =+ и конец работы алгоритма.
АНАЛИЗ РЕЗУЛЬТАТОВ ЭКСПЕРИМЕНТОВ
При проведении экспериментов была использована конечная оптимальная
структура, полученная с помощью программы NetBuilder [3], а также ин-
формация о возможных пропускных способностях и их удельных стоимо-
стях (таблица).
Пропускные
способности 2400 9600 28800 38400 43200 57600 86400
Удельная стои-
мость 200 500 900 1400 1600 1800 2700
Конечная структура сети приведена на этапе 4. Матрицы требований
для каждого этапа во входном файле были получены умножением конечной
матрицы требований на соответствующий коэффициент каждого этапа. При
проведении данного эксперимента использовались следующие коэффи-
циенты:
для этапа 1 — 2,0=k ;
для этапа 2 — 5,0=k ;
для этапа 3 — 8,0=k ;
для этапа 4 — 1=k .
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2002, 4 102
Затрачиваемые средства выделялись поэтапно, в соответствии с задан-
ными коэффициентами — долями их общей стоимости. В данном экспери-
менте использовались следующие коэффициенты и соответствующие им
суммы средств:
для этапа 1 — 3,0=k ; 15167=Wk ;
для этапа 2 — 2,0=k ; 76744=Wk ;
для этапа 3 — 25,0=k ; 95955=Wk ;
для этапа 4 — 25,0=k ; 95955=Wk .
Приведем график динамики изменения выделяемых средств с накопле-
нием (рис 1).
Ограничение на среднее время задержки было принято равным 5 с. Ко-
ординаты узлов сети задавались входным файлом и на их основе рассчиты-
вались длины каналов.
Соответственно рассмотрим поэтапное увеличение максимального по-
тока в сети, полученное в результате работы алгоритма (рис. 2).
Для наглядности сравнения выделяемых средств и получаемого макси-
мального потока представим их на едином графике в нормированном виде
(график максимального потока начинается ниже, затем пересекает график
вложений и на 3-м – 4-м этапе проходит выше него) (рис. 3).
0
50 000
100 000
150 000
200 000
250 000
1 2 3 4
Wk sum
Рис. 1
0
200 000
400 000
600 000
1 2 3 4
H sum
Рис. 2
Структурный синтез развивающихся сетей
Системні дослідження та інформаційні технології, 2002, 4 103
Проанализировав данный график, можно сделать вывод о меньшей эф-
фективности вложения средств на первоначальном этапе и некотором ее
снижении на конечном этапе. Рассмотрим изменение по этапам затрат на
единицу потока:
этап 1 — 0, 49155053;
этап 2 — 0, 376110254;
этап 3 — 0, 356920074;
этап 4 — 0, 388650724.
Отсюда четко видно наименьшую эффективность капитальных вложе-
ний на первом этапе.
На рис. 4 – 7 показаны синтезированные структуры развивающейся
сети по этапам 1 – 4 в соответствии с планом развития структуры сети.
Анализируя поэтапно включение каналов в структуру следует отметить,
что первоначально строится некоторый остов будущей части сети, затем он
достраивается каналами и процесс повторяется для следующей части сети.
0
0,2
0,4
0,6
0,8
1
1,2
1 2 3 4
H sum
Wk sum
Рис. 3
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Днепропетровск
Херсон
Одесса
Винница
Черновцы
Ужгород
Чернигов
Рис. 4. Этап 1. Wk = 67151
Е.Ю. Зайченко
ISSN 1681–6048 System Research & Information Technologies, 2002, 4 104
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Херсон
Одесса
Винница
Черновцы
Ужгород
Чернигов
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Днепропетровск
Херсон
Одесса
Винница
Черновцы
Ужгород
Чернигов
Рис. 5. Этап 4. Wk = 44767; Wk rest = 220
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Херсон
Одесса
Винница
Ужгород
Чернигов
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Днепропетровск
Херсон
Одесса
Винница
Черновцы
Ужгород
Чернигов
Рис. 6. Этап 3. Wk = 55959; Wk rest = 3
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Херсон
Одесса
Винница
Ужгород
Чернигов
12
10
8
14
2
1
5
3
11
7
6
9
4
13
Киев Житомир
0
Ровно
Львов
Суммы
Харьков
Донецк
Запорожье
Днепропетровск
Херсон
Одесса
Винница
Черновцы
Ужгород
Чернигов
Рис. 7. Этап 4. Wk = 55959; Wk rest = 3840
Структурный синтез развивающихся сетей
Системні дослідження та інформаційні технології, 2002, 4 105
ВЫВОДЫ
В целом проведенные эксперименты подтверждают целесообразность по-
становки и решения динамических задач структурного синтеза развиваю-
щихся сетей с учетом динамики их развития по этапам и эффективность
предложенного алгоритма их решения.
ЛИТЕРАТУРА
1. Зайченко О.Ю. Структурний синтез глобальних мереж з технологією АТМ за
заданими показниками якості // Наукові вісті НТУУ «КПІ». — 2001. —
№ 5. — С. 5–11.
2. Зайченко Е.Ю., Зайченко Ю.П. Нахождение максимального потока и анализ
показателей живучести сети при отказах // Автоматика и телемеханика. —
1996. — № 6. — С. 102–113.
3. Зайченко Ю.П., Зайченко Е.Ю., Поспелов И.В. Комплекс программ анализа и
синтеза структуры региональных и глобальных вычислительных сетей //
Управляющие системы и машины. — 2000. — № 5/6. — С. 71–87.
Поступила 10.11.2001
|
| id | journaliasakpiua-article-176058 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:26:07Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/d0/ea5a06a42920af73f4b3c96389f550d0.pdf |
| spelling | journaliasakpiua-article-1760582019-08-15T19:35:31Z Structural Synthesis of developing networks Структурный синтез развивающихся систем Структурний синтез мереж, що розвиваються Zaychenko, H. Ju. A new problem of computer networks structural synthesis with the account of dynamics of its development is considered. The algorithm of its solution is suggested. The experimental investigations of the algorithm were carried out on the example of the Ukrainian global network design. Сформулирована новая задача структурного синтеза компьютерных сетей с учетом динамики их развития. Предложен алгоритм ее решения и приведены экспериментальные исследования алгоритма на примере синтеза глобальной сети Украины. Сформульована нова задача структурного синтезу комп’ютерних мереж із врахуванням динаміки їх розвитку. Запропоновано алгоритм її розв’язку та наведені експериментальні дослідження алгоритму на прикладі глобальної мережі України. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-08-15 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/176058 System research and information technologies; No. 4 (2002); 97-105 Системные исследования и информационные технологии; № 4 (2002); 97-105 Системні дослідження та інформаційні технології; № 4 (2002); 97-105 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/176058/175897 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Zaychenko, H. Ju. Структурний синтез мереж, що розвиваються |
| title | Структурний синтез мереж, що розвиваються |
| title_alt | Structural Synthesis of developing networks Структурный синтез развивающихся систем |
| title_full | Структурний синтез мереж, що розвиваються |
| title_fullStr | Структурний синтез мереж, що розвиваються |
| title_full_unstemmed | Структурний синтез мереж, що розвиваються |
| title_short | Структурний синтез мереж, що розвиваються |
| title_sort | структурний синтез мереж, що розвиваються |
| url | https://journal.iasa.kpi.ua/article/view/176058 |
| work_keys_str_mv | AT zaychenkohju structuralsynthesisofdevelopingnetworks AT zaychenkohju strukturnyjsintezrazvivaûŝihsâsistem AT zaychenkohju strukturnijsintezmerežŝorozvivaûtʹsâ |