Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка
For the network node it was suggested a method, which solves the problem of the packets aggregation transfer order optimization with the known distribution of network elements busy dynamics. To solve the problem it was proposed the criterion - maximum packet delivery duration, which is minimized. It...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2013
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/43897 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334238582341632 |
|---|---|
| author | Pustovoitov, P. E. Raskin, L. G. |
| author_facet | Pustovoitov, P. E. Raskin, L. G. |
| author_institution_txt_mv | [
{
"author": "P. E. Pustovoitov",
"institution": null
},
{
"author": "L. G. Raskin",
"institution": null
}
] |
| author_sort | Pustovoitov, P. E. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-03-30T15:16:01Z |
| description | For the network node it was suggested a method, which solves the problem of the packets aggregation transfer order optimization with the known distribution of network elements busy dynamics. To solve the problem it was proposed the criterion - maximum packet delivery duration, which is minimized. It was shown, that the complicated problem reduces to a set of two-indexed assignment problems. The estimation of expediency of the assessment for packet transfer order optimization method usage was done. The gain, obtained using packet transfer order optimization, increases with the number of transferred packets and with an increasing the level of the variability of packets order length, that are waiting for service in intermediate nodes. The equations for calculating the level of variability of the order lengths are received. Using the simulation model, the graphs, which show the gain of the application of the messages transfer order optimization in the network nodes for the different number of orders, were constructed. |
| first_indexed | 2025-07-17T10:18:52Z |
| format | Article |
| fulltext |
© П.Е. Пустовойтов, Л.Г. Раскин, 2013
Системні дослідження та інформаційні технології, 2013, № 3 53
УДК 681.324
ОПТИМИЗАЦИЯ ПОРЯДКА ПЕРЕДАЧИ СООБЩЕНИЙ
В УЗЛАХ КОМПЬЮТЕРНЫХ СЕТЕЙ
С УЧЕТОМ ДИНАМИКИ ТРАФИКА
П.Е. ПУСТОВОЙТОВ, Л.Г. РАСКИН
Для узла компьютерной сети предложен метод решения задачи определения
порядка передачи совокупности пакетов с учетом известного распределения
динамики занятости элементов сети. Для решения задачи предложен крите-
рий — максимальная продолжительность доставки пакета, которая минимизи-
руется. Предложенная задача редуцируется к решению совокупности двухин-
дексных задач назначения. Выполнено вычисление оценки целесообразности
использования метода оптимизации порядка передачи пакетов. Выигрыш, по-
лучаемый при оптимизации порядка передачи пакетов, растет с увеличением
числа передаваемых сообщений и повышением уровня вариабельности длины
очереди пакетов, ожидающих обслуживания в промежуточных узлах. Получе-
ны соотношения для вычисления уровня вариабельности длин очередей. Ис-
пользуя имитационную модель узла сети были построены графики, показы-
вающие выигрыш применения метода оптимизации порядка передачи
сообщений в узлах сети для различного числа очередей.
Анализ литературы. В современных компьютерных сетях (КС) в связи с не-
прерывным ростом объемов трафика между корреспондентами и ограничен-
ностью пропускных способностей линий связи и узлов сети высокую ак-
туальность приобретает проблема маршрутизации [1–3].
Задача маршрутизации состоит в отыскании для каждого передаваемо-
го сообщения маршрута с указанием всех промежуточных пунктов между
исходным и конечным пунктами, оптимального с точки зрения выбранного
критерия.
На практике наиболее часто используемый критерий — минимизация
суммарной задержки при прохождении маршрута, отождествляется с дли-
ной маршрута. При этом традиционные алгоритмы решения задачи отыска-
ния кратчайшего маршрута учитывают только задержки, возникающие при
прохождении линий связи между узлами сети, с учетом их пропускной спо-
собности, игнорируя задержки в собственно узлах [4, 5]. Этот недостаток
устраняется в [6], где поставлена и решена задача отыскания маршрута, ми-
нимизирующего соответствующую ему суммарную задержку. В этой работе
рассмотрена методика расчета законов изменения во времени длины очере-
ди сообщений, ожидающих начала обслуживания в каждом из узлов сети.
Отыскиваемые законы используются в дальнейшем для построения мар-
шрута с минимальной задержкой передаваемых сообщений. Полученный
в [6] результат, помимо непосредственной полезности его использования,
важен еще и потому, что выявил проблему, не рассматривавшуюся ранее.
Дело в том, что при учете различий в уровне занятости узлов сети возникает
необходимость отыскания рационального порядка передачи сообщений. Эта
задача ранее не рассматривалась.
П.Е. Пустовойтов, Л.Г. Раскин
ISSN 1681–6048 System Research & Information Technologies, 2013, № 3 54
Цель работы — отыскание рациональной организации работы при пе-
редаче совокупности пакетов от одного источника разным адресатам.
Пусть имеется источник сообщений, которые необходимо передать
разным потребителям. Поставим задачу отыскания оптимального порядка
передачи этих сообщений в предположении, что каждое из них будет
доставлено адресату по оптимальному маршруту.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ
При решении задачи маршрутизации для совокупности m передаваемых
пакетов информации будем исходить из того, что для каждого из промежу-
точных узлов обработки информации известен закон изменения во времени
),(tgk Kk ,...,2,1= и длины очереди пакетов, ожидающих начала обслужи-
вания в этом узле. Тогда, используя технологию [6], для любого из переда-
ваемых пакетов можно найти маршрут, минимизирующий время доставки
пакета получателю. Пусть при необходимости передачи m пакетов выбрана
некоторая последовательность их передачи. Такая последовательность мо-
жет быть задана следующим образом. Введем индикатор
⎩
⎨
⎧
=
−−
.случаепротиввномв0
порядку,помпредаетсяпакетйесли,1 ji
xij
Тогда матрица )( ijxX = однозначно задает последовательность передачи
пакетов, если для совокупности )( ijx , mi ,...,2,1= , mj ,...,2,1= , выполня-
ются ограничения
∑
=
=
m
i
ijx
1
1 , mj ,...,2,1= , (1)
∑
=
=
m
j
ijx
1
1 , mi ,...,2,1= , (2)
}1;0{∈ijx , mi ,...,2,1= , mj ,...,2,1= .
Выполнение совокупности ограничений (1) означает, что на каждое,
например, j -е место в последовательности передаваемых пакетов назначен
для передачи один пакет. Совокупность ограничений (2) определяет, что
каждому пакету в общем порядке передачи назначено какое-то одно место.
Пусть теперь для конкретной пары ),( ji значение .1=ijx Примем, что
длины пакетов не слишком сильно отличаются друг от друга и продолжи-
тельность передачи для любого из них равна .Δ Тогда при передачи i -го
пакета j -м по порядку с использованием [6] найдем кратчайший маршрут,
начинающийся в момент ,)1(0 Δ−+= jTTj и соответствующее этому мар-
шруту время задержки доставки ijT пакета потребителю ( 0T — момент на-
чала передачи набора пакетов). Решая задачу для всех пар ),,( ji ,,...,2,1 mi =
,,...,2,1 mj = составим матрицу ).( ijTT =
Оптимизация порядка передачи сообщений в узлах компьютерных сетей …
Системні дослідження та інформаційні технології, 2013, № 3 55
В рассматриваемой ситуации имеется !m различных последовательнос-
тей передачи пакетов. Понятно, что при реальных значениях m их перебор
бесперспективен. С целью отыскания наилучшего каким-либо разумным
образом выбранного порядка передачи пакетов введем следующий естест-
венный критерий — максимальное время доставки пакета, соответствующее
этому выбранному порядку передачи пакетов. При этом для конкретного
плана )( ijxX = значение критерия определяется соотношением
}{max)(
,
ijij
ji
xTX =η . (3)
Тогда задача выбора рационального порядка передачи пакетов сводится
к следующей: найти план )( ijxX = , минимизирующий (3) и удовлетворяю-
щий ограничениям (1)–(2). Полученная задача является минимаксной зада-
чей назначения. Для ее решения предлагается следующая методика. Упоря-
дочим множество значений ijT , mi ,...,2,1= , mj ,...,2,1= следующим
образом:
mmmmqq jijijiji TTTT ≥≥≥≥≥ ......
2211
.
С каждым элементом
qq jiT , },...,2,1{ 2mq∈ , свяжем двухиндексную
матрицу ),( )()( q
ij
q dD = компоненты которой зададим соотношением:
⎪⎩
⎪
⎨
⎧
≥
<
= ,если,
,если,)(
qq
qq
jiij
jiijijq
ij TTM
TTT
d
где M — достаточно большое число (например, }{max2
ij
ij
TmM = ).
Пусть .1=q При этом в матрице )( )1()1(
ijdD = будет один элемент, рав-
ный ,M стоящий на месте 11, ji . Решим теперь задачу отыскания набора
)( ijxX = , минимизирующего
∑∑
= =
=
m
i
m
j
ijij xdXL
1 1
)1()( (4)
и удовлетворяющего (1)–(2). Это обычная задача назначения, решаемая
«венгерским» методом [7–9]. Если при этом значение )( *
1XL на оптималь-
ном плане задачи (1)–(2), (4) меньше ,M то это означает, что существует
порядок передачи пакетов, при котором максимальное время передачи
меньше
11 jiT .
Положим теперь 2=q . В соответствующей матрице )( )2()2(
ijdD = бу-
дут два элемента, находящиеся на местах ),,( 11 ji ),,( 22 ji равные .M Вновь
решим задачу назначения с матрицей )2(D . Аналогично предыдущему, из
выполнения неравенства MXL <)( *
2 следует, что полученный на этом шаге
порядок передачи пакетов *
2X обеспечивает их передачу за время, не превос-
ходящее .
22 jiT
П.Е. Пустовойтов, Л.Г. Раскин
ISSN 1681–6048 System Research & Information Technologies, 2013, № 3 56
Продолжим решение задачи. Ясно, что рано или поздно найдется неко-
торое qq ~= такое, что ,)( ~ MXL q < но .)( 1~ MXL q >+ Это означает, что су-
ществует порядок передачи пакетов, в котором максимальное время переда-
чи не превосходит
qq jiT ~~ , , но не существует порядка, для которого
максимальное время меньше или равно
1~1~ , ++ qq jiT . Следовательно, план *~qX
является искомым решением минимаксной задачи (1)–(3).
Проведем оценку степени целесообразности оптимизации порядка пе-
редачи пакетов. С этой целью осуществим имитационное моделирование
[10] процесса функционирования узла КС на интервале передачи m паке-
тов для различных законов )(tgk изменения во времени длины очереди па-
кетов, ожидающих начала обслуживания в промежуточных узлах. Понятно,
что использование рационального порядка передачи пакетов тем более це-
лесообразно, чем выше вариабельность функции ),(tgk проявляющаяся в раз-
личиях величины задержки доставки ijT для пакетов, передаваемых разными
по порядку. Уровень вариабельности оценивается показателем
∑∑
= =
−
= m
i
m
j
ij
ij
j
ij
ji
T
m
TT
1 1
2
1
}minmax{max
ξ . (5)
Для оценки степени целесообразности оптимизации порядка передачи
пакетов используется показатель
*
*
max
max
)(
ijij
ij
ij
i
xT
T
X =ζ . (6)
Числитель этого соотношения определяет максимальную задержку
доставки в случае, когда пакеты передаются в соответствии с их порядко-
выми номерами. В знаменателе (6) стоит максимальная задержка доставки,
соответствующая оптимальному порядку передачи пакетов. Результаты
имитационного моделирования для разных значений числа m передавае-
мых пакетов приведены на рисунке.
Анализ приведенных кривых позволяет сделать следующий вывод: вы-
игрыш, получаемый при оптимизации порядка передачи пакетов растет
с увеличением числа передаваемых пакетов и повышением уровня вариабель-
ности длины очереди пакетов, ожидающих обслуживания в промежуточных
узлах.
Задача существенно усложняется, если в результате естественных, не-
избежных погрешностей оценки функций )(tgk расчет точных значений
задержек ijT , mi ,...,2,1= , mj ,...,2,1= , нереализуем, однако возможно опи-
сание этих задержек в виде нечетких чисел с соответствующими функциями
принадлежности )( ijTM . При этом стержневая задача методики оптимиза-
ции порядка передачи пакетов должна решаться в нечеткой постановке. Метод
решения задачи назначения при нечетких исходных данных изложен в [11].
Оптимизация порядка передачи сообщений в узлах компьютерных сетей …
Системні дослідження та інформаційні технології, 2013, № 3 57
ВЫВОДЫ
Таким образом, предложен метод решения задачи оптимизации порядка пе-
редачи совокупности пакетов с учетом динамики занятости элементов ком-
пьютерной сети. При решении задачи предложен минимаксный критерий.
Показано, что поставленная задача сводится к последовательности двухин-
дексных задач назначения. Целесообразность оптимизации порядка переда-
чи подтверждена имитационным моделированием. Направление дальней-
ших исследований может быть связано с решением сформулированной
задачи при учете различий в длине передаваемых пакетов.
ЛИТЕРАТУРА
1. Ирвин Дж, Харль Д. Передача данных в сетях: инженерный подход: пер.
с англ. — СПб.: БХВ–Петербург, 2003. — 448 с.
2. Иртегов Д.В. Введение в сетевые технологии. — СПб.: БХВ–Петербург,
2004. — 560 с.
3. Куроуз Дж., Росс К. Компьютерные сети. — СПб.: Питер, 2004. — 765 с.
4. Столлингс В. Современные компьютерные сети. — СПб.: Питер, 2003. —783 с.
5. Таненбаум Э. Компьютерные сети. — СПб.: Питер, 2003. — 992 с.
6. Пустовойтов П.Е., Ящук Н.И. Динамическая маршрутизация в компьютерных
сетях высокой размерности // Інформаційно-керуючі системи на залізничному
транспорті. — 2006. — № 3. — С. 68–71.
7. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. —
М.: Сов. Радио, 1961. — 384 с.
8. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управ-
ления. — М.: Сов. Радио, 1976. — 344 с.
9. Мину М. Математическое программирование. — М.: Наука, 1990. — 485 с.
10. А.с. № 39374 від 26.07.2011, Україна, ДДІВ. Комп’ютерна програма «Імітаційна
модель комп’ютерної мережі із різними за властивостями потоками
пакетів» / Пустовойтов П.Є.; Заявка №39622 від 23.05.2011.
11. Раскин Л.Г., Серая О.В. Нечеткая математика. Основы теории. Приложения. —
Х.: Парус. — 2008. — 352 с.
Поступила 19.03.2012
)(3 ξζ
)(2 ξζ
)(1 ξζ
m=20
m=20
m=20
ζ
ζ
Рисунок. Выигрыш, получаемый при оптимизации порядка передачи пакетов
|
| id | journaliasakpiua-article-43897 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:18:52Z |
| publishDate | 2013 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/24/fd46ff5cda3520a93e3de61072f4bf24.pdf |
| spelling | journaliasakpiua-article-438972018-03-30T15:16:01Z Optimization of package transfer order in network routers considering traffic dynamic Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка Pustovoitov, P. E. Raskin, L. G. For the network node it was suggested a method, which solves the problem of the packets aggregation transfer order optimization with the known distribution of network elements busy dynamics. To solve the problem it was proposed the criterion - maximum packet delivery duration, which is minimized. It was shown, that the complicated problem reduces to a set of two-indexed assignment problems. The estimation of expediency of the assessment for packet transfer order optimization method usage was done. The gain, obtained using packet transfer order optimization, increases with the number of transferred packets and with an increasing the level of the variability of packets order length, that are waiting for service in intermediate nodes. The equations for calculating the level of variability of the order lengths are received. Using the simulation model, the graphs, which show the gain of the application of the messages transfer order optimization in the network nodes for the different number of orders, were constructed. Для узла компьютерной сети предложен метод решения задачи определения порядка передачи совокупности пакетов с учетом известного распределения динамики занятости элементов сети. Для решения задачи предложен критерий — максимальная продолжительность доставки пакета, которая минимизируется. Предложенная задача редуцируется к решению совокупности двухиндексных задач назначения. Выполнено вычисление оценки целесообразности использования метода оптимизации порядка передачи пакетов. Выигрыш, получаемый при оптимизации порядка передачи пакетов, растет с увеличением числа передаваемых сообщений и повышением уровня вариабельности длины очереди пакетов, ожидающих обслуживания в промежуточных узлах. Получены соотношения для вычисления уровня вариабельности длин очередей. Используя имитационную модель узла сети были построены графики, показывающие выигрыш применения метода оптимизации порядка передачи сообщений в узлах сети для различного числа очередей. Для вузла комп’ютерної мережі запропоновано метод вирішення задачі визначення порядку передачі сукупності пакетів із урахуванням відомого розподілу динаміки зайнятості елементів мережі. Для розв’язання задачі запропоновано критерій — максимальна тривалість доставки пакета, що мінімізується. Запропоноване завдання редукується до розв’язку сукупності двоіндексних задач призначення. Виконано обчислення оцінки доцільності використання методу оптимізації порядку передачі пакетів. Виграш, одержуваний при оптимізації порядку передачі пакетів, зростає зі збільшенням числа повідомлень, що передаються, і підвищенням рівня варіабельності довжини черги пакетів, що очікують обслуговування в проміжних вузлах. Отримано співвідношення для обчислення рівня варіабельності довжин черг. Використовуючи імітаційну модель вузла мережі було побудовано графіки, що показують виграш застосування методу оптимізації порядку передачі повідомлень у вузлах мережі для різної кількості черг. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/43897 System research and information technologies; No. 3 (2013); 53-57 Системные исследования и информационные технологии; № 3 (2013); 53-57 Системні дослідження та інформаційні технології; № 3 (2013); 53-57 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/43897/40175 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Pustovoitov, P. E. Raskin, L. G. Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| title | Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| title_alt | Optimization of package transfer order in network routers considering traffic dynamic Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика |
| title_full | Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| title_fullStr | Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| title_full_unstemmed | Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| title_short | Оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| title_sort | оптимізація порядку передачі повідомлень у вузлах комп’ютерних мереж з урахуванням динаміки трафіка |
| url | https://journal.iasa.kpi.ua/article/view/43897 |
| work_keys_str_mv | AT pustovoitovpe optimizationofpackagetransferorderinnetworkroutersconsideringtrafficdynamic AT raskinlg optimizationofpackagetransferorderinnetworkroutersconsideringtrafficdynamic AT pustovoitovpe optimizaciâporâdkaperedačisoobŝenijvuzlahkompʹûternyhsetejsučetomdinamikitrafika AT raskinlg optimizaciâporâdkaperedačisoobŝenijvuzlahkompʹûternyhsetejsučetomdinamikitrafika AT pustovoitovpe optimízacíâporâdkuperedačípovídomlenʹuvuzlahkompûternihmerežzurahuvannâmdinamíkitrafíka AT raskinlg optimízacíâporâdkuperedačípovídomlenʹuvuzlahkompûternihmerežzurahuvannâmdinamíkitrafíka |