Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика

Для узла компьютерной сети предложен метод решения задачи определения порядка передачи совокупности пакетов с учетом известного распределения динамики занятости элементов сети. Для решения задачи предложен критерий — максимальная продолжительность доставки пакета, которая минимизируется. Предложенна...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автори:	Пустовойтов, П.Е., Раскин, Л.Г.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2013
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Проблемно і функціонально орієнтовані комп’ютерні системи та мережі
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/85096
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика / П.Е. Пустовойтов, Л.Г. Раскин // Системні дослідження та інформаційні технології. — 2013. — № 3. — С. 53-57. — Бібліогр.: 11 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85096
record_format	dspace
spelling	irk-123456789-850962015-07-20T03:01:56Z Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика Пустовойтов, П.Е. Раскин, Л.Г. Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Для узла компьютерной сети предложен метод решения задачи определения порядка передачи совокупности пакетов с учетом известного распределения динамики занятости элементов сети. Для решения задачи предложен критерий — максимальная продолжительность доставки пакета, которая минимизируется. Предложенная задача редуцируется к решению совокупности двухиндексных задач назначения. Выполнено вычисление оценки целесообразности использования метода оптимизации порядка передачи пакетов. Выигрыш, получаемый при оптимизации порядка передачи пакетов, растет с увеличением числа передаваемых сообщений и повышением уровня вариабельности длины очереди пакетов, ожидающих обслуживания в промежуточных узлах. Получены соотношения для вычисления уровня вариабельности длин очередей. Используя имитационную модель узла сети были построены графики, показывающие выигрыш применения метода оптимизации порядка передачи сообщений в узлах сети для различного числа очередей. Для вузла комп’ютерної мережі запропоновано метод вирішення задачі визначення порядку передачі сукупності пакетів із урахуванням відомого розподілу динаміки зайнятості елементів мережі. Для розв’язання задачі запропоновано критерій — максимальна тривалість доставки пакета, що мінімізується. Запропоноване завдання редукується до розв’язку сукупності двоіндексних задач призначення. Виконано обчислення оцінки доцільності використання методу оптимізації порядку передачі пакетів. Виграш, одержуваний при оптимізації порядку передачі пакетів, зростає зі збільшенням числа повідомлень, що передаються, і підвищенням рівня варіабельності довжини черги пакетів, що очікують обслуговування в проміжних вузлах. Отримано співвідношення для обчислення рівня варіабельності довжин черг. Використовуючи імітаційну модель вузла мережі було побудовано графіки, що показують виграш застосування методу оптимізації порядку передачі повідомлень у вузлах мережі для різної кількості черг 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. 2013 Article Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика / П.Е. Пустовойтов, Л.Г. Раскин // Системні дослідження та інформаційні технології. — 2013. — № 3. — С. 53-57. — Бібліогр.: 11 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/85096 681.324 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Проблемно і функціонально орієнтовані комп’ютерні системи та мережі
spellingShingle	Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Пустовойтов, П.Е. Раскин, Л.Г. Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика Системні дослідження та інформаційні технології
description	Для узла компьютерной сети предложен метод решения задачи определения порядка передачи совокупности пакетов с учетом известного распределения динамики занятости элементов сети. Для решения задачи предложен критерий — максимальная продолжительность доставки пакета, которая минимизируется. Предложенная задача редуцируется к решению совокупности двухиндексных задач назначения. Выполнено вычисление оценки целесообразности использования метода оптимизации порядка передачи пакетов. Выигрыш, получаемый при оптимизации порядка передачи пакетов, растет с увеличением числа передаваемых сообщений и повышением уровня вариабельности длины очереди пакетов, ожидающих обслуживания в промежуточных узлах. Получены соотношения для вычисления уровня вариабельности длин очередей. Используя имитационную модель узла сети были построены графики, показывающие выигрыш применения метода оптимизации порядка передачи сообщений в узлах сети для различного числа очередей.
format	Article
author	Пустовойтов, П.Е. Раскин, Л.Г.
author_facet	Пустовойтов, П.Е. Раскин, Л.Г.
author_sort	Пустовойтов, П.Е.
title	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика
title_short	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика
title_full	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика
title_fullStr	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика
title_full_unstemmed	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика
title_sort	оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2013
topic_facet	Проблемно і функціонально орієнтовані комп’ютерні системи та мережі
url	http://dspace.nbuv.gov.ua/handle/123456789/85096
citation_txt	Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика / П.Е. Пустовойтов, Л.Г. Раскин // Системні дослідження та інформаційні технології. — 2013. — № 3. — С. 53-57. — Бібліогр.: 11 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT pustovojtovpe optimizaciâporâdkaperedačisoobŝenijvuzlahkompʹûternyhsetejsučetomdinamikitrafika AT raskinlg optimizaciâporâdkaperedačisoobŝenijvuzlahkompʹûternyhsetejsučetomdinamikitrafika
first_indexed	2025-07-06T12:15:18Z
last_indexed	2025-07-06T12:15:18Z
_version_	1836899756249448448
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 ζ ζ Рисунок. Выигрыш, получаемый при оптимизации порядка передачи пакетов

Оптимизация порядка передачи сообщений в узлах компьютерных сетей с учетом динамики трафика

Репозитарії

Схожі ресурси