Оптимизация коммутации пакетов в распределенных системах
Рассматривается зависимость времени доставки пакетов данных в транспортной системе от объема этих данных, длины заголовка и количества коммутаторов. Доказана теорема, подтверждающая возможность минимизации время доставки потока данных за счет оптимального выбора соотношений показателей конкретной тр...
Gespeichert in:
| Datum: | 2004 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6410 |
| 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: | Оптимизация коммутации пакетов в распределенных системах / Н.И. Алишов // Комп’ютерні засоби, мережі та системи. — 2004. — № 3. — С. 87-94. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860176563720421376 |
|---|---|
| author | Алишов, Н.И. |
| author_facet | Алишов, Н.И. |
| citation_txt | Оптимизация коммутации пакетов в распределенных системах / Н.И. Алишов // Комп’ютерні засоби, мережі та системи. — 2004. — № 3. — С. 87-94. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| description | Рассматривается зависимость времени доставки пакетов данных в транспортной системе от объема этих данных, длины заголовка и количества коммутаторов. Доказана теорема, подтверждающая возможность минимизации время доставки потока данных за счет оптимального выбора соотношений показателей конкретной транспортной системы.
|
| first_indexed | 2025-12-07T18:01:05Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2004, № 3 87
Рассматривается зависимость
времени доставки пакетов дан-
ных в транспортной системе от
объема этих данных, длины заго-
ловка и количества коммутато-
ров. Доказана теорема, подтвер-
ждающая возможность миними-
зации время доставки потока дан-
ных за счет оптимального выбо-
ра соотношений показателей кон-
кретной транспортной системы.
Н.И. Алишов, 2004
ÓÄÊ 004.72
Í.È. ÀËÈØÎÂ
ÎÏÒÈÌÈÇÀÖÈß ÊÎÌÌÓÒÀÖÈÈ
ÏÀÊÅÒÎÂ Â ÐÀÑÏÐÅÄÅËÅÍÍÛÕ
ÑÈÑÒÅÌÀÕ
Введение. Коммутация пакетов – базовая те-
хнология для распределенных систем и сетей
компьютеров. Эффективность таких систем
во многом определяется выбранными алго-
ритмами коммутации. До настоящего време-
ни научные исследования в этой области
были, в основном, связаны с оценкой харак-
теристик трафика и разработкой адекватных
алгоритмов маршрутизации пакетов. Совре-
менные интеллектуальные сети предъявляют
особые требования к производительности
коммутации пакетов и времени доставки от-
дельных потоков данных. Необходимость оп-
тимизации времени доставки информацион-
ных пакетов при прочих равных условиях
(т.е. при заданных характеристиках сети ком-
мутации пакетов) обусловливает разработку
соответствующих алгоритмов и технологий.
В данной работе описываются теоретические
основы создания алгоритмов, позволяющих
оптимизировать время доставки в конкрет-
ных сетях коммутации пакетов.
Состояние проблемы. Разработка сетей
коммутации пакетов началась в середине про-
шлого века по результатам теоретических ис-
следований Клейнрока [1]. Дальнейшие при-
кладные работы велись под руководством
Дэвиса [2]. За прошедшие годы практически
все научные исследования были связаны с
анализом трафика (теория очередей), разра-
боткой теории маршрутизации пакетов, соз-
данием технической и технологической баз
сети коммутации пакетов. Для современных
интеллектуальных мультимедийных сетей
Н.И. АЛИШОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 88
особое значение имеет время транспортировки потоков данных. Исследования в
этой области, в основном, связаны с разработкой технологий высокопроизводи-
тельных коммутаций. Для каждой отдельной сети разрабатываются оптимизи-
рованные форматы пакетов с учетом архитектурных особенностей этих сетей.
Вопросы же, связанные с анализом влияния (инвариантным относительно кон-
кретной сети) на время доставки отдельных потоков данных таких показателей,
как соотношение полезной и служебной информации, характеристики маршрут-
ной информации, количество пакетов в данном потоке и т.п., к сожалению, до
настоящего времени не были объектом фундаментальных исследований. В дан-
ной работе сделана попытка, частично заполнить этот пробел.
Постановка задачи. Рассмотрим распределенную транспортную систему
(ТС) передачи данных, состоящую из оконечных хостов-источников, хостов-
приемников информации и коммутаторов пакетов. Хосты-источники, имеющие
D байтов информации, формируют запросы к ТС для передачи этих данных хос-
там-приемникам. Предварительно между взаимодействующими хостами выпол-
няется процедура согласования сеанса транспортировки, в течение которого по
выбранному маршруту должны передаваться данные. Допускается возможность
выбора разных маршрутов в разных сеансах связи. Это означает, что количество
коммутаторов в разных сеансах связи может варьироваться. Коммутаторы име-
ют не менее двух буферов. В каждом цикле коммутатора один из буферов вы-
полняет роль входного, а другой – выходного. Прием и передача в буферах –
параллельные процессы, т. е. коммутатор может одновременно принимать дан-
ные во входной буфер и выдавать их из выходного буфера. После приема и вы-
дачи данных эти буферы меняются ролями: выходной буфер становится вход-
ным и наоборот.
Циклом коммутатора назовем максимальное время, необходимое для прие-
ма данных во входной буфер и выдачи данных, накопленных в выходном буфе-
ре. Временные характеристики ТС будем оценивать в байт-тактах. Один байт-
такт равен времени приема или передачи одного байта между соседними узлами.
Каждый пакет состоит из полезных данных и заголовка. Будем рассматривать
наиболее распространенный случай, когда объем заголовка пакета практически
не зависит от количества полезных данных.
Выбранный в данном сеансе маршрут R между хостом-источником и хос-
том-приемником содержит { }rrrrrr ,...,,, 321= 1 коммутаторов. В общем случае
хосты-приемники информации и коммутаторы пакетов могут изменить объем
заголовка h в зависимости от используемой технологии коммутации пакетов.
Требуется оптимизация времени доставки потоков данных.
Методы решения задачи. Пусть хост-источник А имеет массив данных
объемом D байтов для передачи в хост-приемник B с заголовком объемом
1 Далее по тексту r будет обозначать количество коммутаторов, а ri – порядковый
номер i-го коммутатора.
ОПТИМИЗАЦИЯ КОММУТАЦИИ ПАКЕТОВ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ
Комп’ютерні засоби, мережі та системи. 2004, № 3 89
0hA ≥ байтов. Соответственно каждый коммутатор ir , может изменить преды-
дущий заголовок на 0≥ih байтов.
Лемма [3]. Пусть пакет данных, содержащий D байтов полезной информа-
ции и Ah байтов заголовка, должен передаваться в транспортную систему для
доставки AhD+ байтов к приемнику информации. Тогда время доставки пакета
данных от источника A, к приемнику B через r коммутаторов, каждый из кото-
рых вносит задержку пакета на 0≥ih байт-тактов, будет равно
∑
+
=
→ ++=
1r
1i
i
D
BA h1rDT )( байт-тактам.2
Доказательство. Рассмотрим последовательность прохождения пакета
объемом AhD+ байтов от источника A через r коммутаторов к приемнику B.
Пакет доставляется к r -му коммутатору за
∑
=
→ +=+++++=
r
i
irA
D
rA hrDhDhDhDT
1
2 ... байт-тактов, где Ahh =1 .
Поскольку пакет от r-го коммутатора на хост-приемник передается за
B
D
Br hDT +=→ байт-тактов, то общее время доставки пакета
∑∑
+
==
→→→ ++=+++=+=
1r
1i
iB
r
1i
i
D
Br
D
rA
D
BA h1rDhDhrDTTT )( , где B1r hh =+ .
Пусть D
BA
D
1 TT →= . D
1T – время передачи массива информации, состоящего
из D байтов полезной информации и Ah байтов заголовка, одним пакетом от
хоста-источника к хосту-приемнику через маршрут R с r коммутаторами.
Теорема. Минимальное время передачи D байтов полезной информации и
Ah байтов заголовка между хостом-источником и хостом-приемником n па-
кетами через выбранный маршрут R с r коммутаторами, каждый из которых
вносит задержку пакета на 0≥ih байт-тактов:
{ } { } ∑
+
=
+−⋅+=
1r
1i
iii
D
n hhhDr2DT maxmax байт-тактам.
Если исходный массив данных объемом D байтов разбить на n пакетов,
то исходя из вышедоказанной леммы, один пакет доставляется за время
∑
+
=
++=
1r
1i
i
nD
1 h1r
n
DT )( байт-тактам. Следующий пакет поступит к хосту-при-
емнику за { }ihnD max+ байт-тактов. Поскольку за первым пакетом будут сле-
довать еще 1n − пакетов, то
2 Будем полагать, что A1 hh = , в противном случае 1: hhA =
Н.И. АЛИШОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 90
{ } { }( ).max)()(max)()( i
1r
1i
ii
1r
1i
i
D
n h1nhnr
n
Dh
n
D1nh1r
n
DT −+++=
+−+++= ∑∑
+
=
+
=
Чтобы найти минимум функционала D
nT относительно величины n вычиcлим
производную D
nT по n при фиксированных значениях ihrD ,, .
{ } { } .maxmax
−⋅+++
∂
∂
=
∂
∂ ∑
+
=
ii
1r
1i
i
D
n hhnhDr
n
D
nn
T
При 0
n
T D
n =
∂
∂
{ } 0
n
Drh 2i =−max . Отсюда { }ihDrn max= . Подставив
значение n, получим
{ } { } ∑
+
=
+−⋅+=
1r
1i
iii
D
n hhhDr2DT maxmaxmin .
Рассмотрим частный случай передачи массивов данных от A к B – ко-
гда r1i1hh Ai ,, =∀≥= . Это означает, что размер заголовка передаваемых по
маршруту R пакетов на всем маршруте остается величиной постоянной. Такая
ситуация наиболее типична для современных сетей с коммутацией пакетов.
Поскольку при этом
{ } AiA
1r
1i
i hhh1rh =+=∑
+
=
max;)( , то
)()()( nrh
n
Dnrhnr
n
DT AA
D
n +
+=+++= . При
Ah
Drn= ,
( ) .min 2
AAA
D
n DrhDrDh2rhT +=++=
Дальнейший анализ будет проводиться с учетом r1i1hh Ai ,, =∀≥= , хо-
тя аналогичные результаты могут быть получены и для общего случая. Будем
также полагать, что hhA = .
Поскольку ( )( )1rhDT D
1 ++= и ( )( )Drh1T D
D ++= , то при h = r,
D
D
D
1 TT = . Таким образом, если h = r это время доставки массива из D байтов
одним пакетом совпадает со временем доставки этого массива D пакетами. То-
гда, Dn= т. е. ( )( ) ( ) 2D
D hDDhhDT +=++= . Если D = 1 или hDr ≤ ,
необходимо установить n: = 1. Это означает, что при hDr ≤ массив объемом D
байтов должен быть передан одним пакетом, и тогда время передачи
( )( )1rhDT D
1 ++= . Аналогично, если 1D> и rDh ≤ , то n:= D. В этом случае
время доставки массива объемом D байтов ( )( )Drh1T D
D ++= . Время доставки
ОПТИМИЗАЦИЯ КОММУТАЦИИ ПАКЕТОВ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ
Комп’ютерні засоби, мережі та системи. 2004, № 3 91
D
nT будет максимальным при n=1, либо при n=D (в зависимости от соотноше-
ния величин h и r, рис. 1).
Из
( )( )
( )( ) 1
1hrD
1rhD
>
++
++
следует, что
rDhhDr +>+ , hr > . Это означает, что
при hr > ( )( )1rhDTT D
1
D
n ++==max ,
т. е. D
D
D
1 TT > и, наоборот, при r < h
( )( )1hrDTT D
D
D
n ++==max , т. е.
D
D
D
1 TT < .
Чтобы определить предельные воз-
можности достижения минимального
времени доставки относительно D
nTmax
в зависимости от значения D, необходи-
мо найти D
n
D
n
D T
T
min
max
lim
∞→
. Когда r>h
( )( )
( )( )
( ) ( )
( ) ( ) .limlim
min
max
lim 1r
D
hrD
D
hrD
D
hD1r
hrDhrD
1rhD
T
T
DDD
n
D
1
D
+=
++
+
+
=
++
++
=
∞→∞→∞→
Таким же образом, при hr ≤ 1h
T
T
D
n
D
n
D
+=
∞→ min
max
lim .
Предложенные расчеты показывают, что возможно уменьшение времени
доставки пакетов в (r+1) или (h+1) раз!
Для оптимизации транспортной системы могут быть использованы свойства
функционала D
nT , связанные с возможностью достижения одинаковой произво-
РИС. 1
Н.И. АЛИШОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 92
дительности при разных значениях r (h). Для этого необходимо определить
21 nиn , при которых D
n
D
n 21
TT = . Поскольку
( ) ( )2
2
1
1
nrh
n
Dnrh
n
D
+
+=+
+ , тогда ( ) 0DrnhnDrnnhn 1
2
12
2
21 =++− ;
( ) ( ) 122
11
2
1
2
1
12 ;
2
)( nn
hn
Dr
hn
hnDrhnDrn ==
−±+
= . Таким образом, получаем
D
hn
Dr
D
n
1
2
TT = . Вычислим минимум соотношений
( )
( )( )1rhD
Dhr
T
T
2
D
1
D
n
++
+
=
min
при hr > и
( )
( )( )Drh1
Dhr
T
T 2
D
D
D
n
++
+
=min , при hr<
которые определяют предельные случаи уменьшения времени доставки паке-
тов при передаче массива объемом D байтов одним пакетом, D пакетами или
h
Drn0 = пакетами в D
n
D
D
0
T
T
K = или D
n
D
1
0
T
T
K = раз (рис.2). Для этого необхо-
димо вычислить при hr >
( ) ( )
( ) ( ) ( )
.
+−++
++
=
∂
∂
D
DDhrhDDhr
1rhD
1
D
T
T
2
2
D
1
D
n0
Из ( ) ( ) ( )( ) 0DDhrhDDhr 2 =+−++ следует
( ) ( ) ;0DDhrhD =+−+ ,DhrDhD +=+ т. е. .rhD= Тогда
22
2
D
n 1rD1r
r
h
r
hhr2hr1rhrhT )()())((min +=+=
++
=++= . Если
2
2
D
n 1hD
h
rhr2rh1hrhrTтоhrиhrD )())((min, +=
++
=++=>= .
Для 22D
n )Dr()Dh()Dh)(hD(Tminhr +≡+=++== .
При ( ) ))(()()()()( hr1D1hrD1rhDTThr D
D
D
1 −−=++−++=−∆> .
Если ,hr < то ( ) ))(()()()()( rh1D1rhD1hrDTT D
1
D
D −−=++−++=−∆ .
Определим значение D, при котором rTT D
n
D
1 0
= :
( ) ( )rrrrr2rrrr2
r
hDr
Dhr
1rhD 234234
212 −−+−−+==
+
++ ∓,;)()(
.
ОПТИМИЗАЦИЯ КОММУТАЦИИ ПАКЕТОВ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ
Комп’ютерні засоби, мережі та системи. 2004, № 3 93
РИС. 2
Таким образом, зная объем пакета можно регулировать время его доставки в
интеллектуальных сетях в зависимости от характеристик транспортной системы.
С точки зрения времени доставки данных для сетей коммутации пакетов ха-
рактеристическими показателями являются величины h и r. Соотношения этих
величин позволяют выбрать наиболее рациональные значения времени доставки
пакетов. Особый интерес представляет их произведение: hr=µ . При const=µ
для массива данных объемом D байтов ( ) constDT 2D
n =+µ=min . Это оз-
начает, что варьируя значениями величин h и r можно выбрать разные пути
между источником и приемником информации без потери времени доставки па-
кетов. Например, при 1024=µ время доставки массива данных, состоящего из
4096 байтов, через маршруты, включающие 64=r коммутаторов или 4=r
коммутатора одинаково и составляет 9216 байт-тактов. Однако может показать-
ся, что увеличение h приводит к увеличению трафика. Это может снизить зна-
чимость выбора разных путей с одинаковым временем доставки пакетов. Поэто-
Н.И. АЛИШОВ
Комп’ютерні засоби, мережі та системи. 2004, № 3 94
му необходимо вычислить и сравнить значения трафика при разных h и r .
Количество байтов, переданных по ТС при заданных значениях D, hi и ri вычис-
ляется по формуле: ( ) =+= iiiiirh hDrhrDhQ iirDhD+ . Поскольку
constrh ii ==µ , то количество байтов, переданных по ТС при разных hi и ri
constrDhDQ iirh =+= .
Для непрерывных систем время доставки hrnrnDT D
n ++= )( . Если
∞→n то hrDT D
n +→ . На практике значение n не может быть большеD ,
где минимальный размер делимых частей D. При =n функционал
hrnrnDT D
n ++= )( характеризирует непрерывность доставки ресурсов. Это
позволяет разграничить фундаментальные отличия непрерывных и дискретных
систем.
Заключение. Доказанная теорема и предложенные расчеты позволяют
адаптировать время доставки пакетов данных к реальным условиям функциони-
рования транспортной среды с учетом значения расчетной величины 0n . Кроме
того, становится возможным создание интеллектуальной подсистемы анализа
требований к передаче мультимедийной информации и принятия оптимальных
решений за счет варьирования и расчета необходимых характеристик транс-
портной системы. Данная концепция может быть обобщена для устранения про-
стоев в любой транспортной среде и поэтому может быть использована в таких
отраслях как транспортировка товаров, технологические процессы, химическая
промышленность, медицина и здравоохранение, биология и биотехнология и
др. Особый эффект от полученных результатов ожидается в развитых сетях
транспортировки данных типа MPLS- WWDM- коммутация, а также в будущих
поколениях интегральных схем, таких, как системы на чипах – SoC (Systems on
Chip) и сети на чипах – NoC (Network on Chip). Теоретические исследования по
данному направлению могут дать новые результаты для интеллектуализации
транспортной системы.
Инь и янь сетей коммутации пакетов являются величины h и r.
1. Клейнрок Л. Вычислительные сети с очередями. – М.: Мир, 1979. – 400 c.
2. Дэвис Д. Вычислительные сети и сетевые протоколы. – М.: Мир, 1979. – 563 c.
3. Алишов Н.И. Адаптивный стековый алгоритм универсального множественного доступа
в распределенных системах и сетях компьютеров // УСиМ. – 2004. – № 2. – С. 59–72.
Получено 02.04.2004
|
| id | nasplib_isofts_kiev_ua-123456789-6410 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-12-07T18:01:05Z |
| publishDate | 2004 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Алишов, Н.И. 2010-03-02T11:57:05Z 2010-03-02T11:57:05Z 2004 Оптимизация коммутации пакетов в распределенных системах / Н.И. Алишов // Комп’ютерні засоби, мережі та системи. — 2004. — № 3. — С. 87-94. — Бібліогр.: 3 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6410 004.72 Рассматривается зависимость времени доставки пакетов данных в транспортной системе от объема этих данных, длины заголовка и количества коммутаторов. Доказана теорема, подтверждающая возможность минимизации время доставки потока данных за счет оптимального выбора соотношений показателей конкретной транспортной системы. ru Інститут кібернетики ім. В.М. Глушкова НАН України Оптимизация коммутации пакетов в распределенных системах Article published earlier |
| spellingShingle | Оптимизация коммутации пакетов в распределенных системах Алишов, Н.И. |
| title | Оптимизация коммутации пакетов в распределенных системах |
| title_full | Оптимизация коммутации пакетов в распределенных системах |
| title_fullStr | Оптимизация коммутации пакетов в распределенных системах |
| title_full_unstemmed | Оптимизация коммутации пакетов в распределенных системах |
| title_short | Оптимизация коммутации пакетов в распределенных системах |
| title_sort | оптимизация коммутации пакетов в распределенных системах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6410 |
| work_keys_str_mv | AT ališovni optimizaciâkommutaciipaketovvraspredelennyhsistemah |