lect
.pdfПуть передачи
Звено
Конец
приема
Рис. 5.12: Схема переноса неоднородного трафика в однородном виртуальном соединении при инверсной организации очереди в начале пути, / = 5; г^^) < г^^^ = г^^^ = т^^^ <
т(з) = г(«); А;(1) = 2, к^^) = 1, А;(з) = 1, А;(4) = з, А;(5) = 2, TV = 2; ii = 1, г'г = гз = 2, ц = 4
191
где di - длина пути до адресата пакетов г'-го типа.
Д о к а з а т е л ь с т в о .
В силу конвейерного эффекта на этапе d >2 передача Ё ^^*^ пакетов
i=id
из очереди и N пакетов сообщения совмещена с передачей Е к^^^ —
1 + Л^ пакетов по предыдущему этапу пути. Тогда с учетом введенного интервала простоя между передачей пакетов различных типов (5.53) для задержки сообщения справедливо:
T:(D, TV, к*) = Y: к^^т^^ + iVrC+i) + Е |
( Е |
Ы^т^^ + Ef) + iVr('+^)- |
|
г=1 |
d=2 |
\i=id ^ |
^ |
|
|
|
(О ^^лгЛт) |
I |
- [к^'^^ - 1) г^^'^) + Eii_i + Е {к^^г^^ + 4-i) + NT |
|
|||
== ^ |
A;(^VW + NT^'^'^ + E |
^^'''^ + E |
E (4'^ - Ef_,). |
(5.56) |
г=1 |
d=2 |
d=2 |
i=id |
|
Рассмотрим двойную сумму данного соотношения. Меняя порядок сум мирования в ней, получаем:
Е Е (4'* - E^jli) = Ё Ec^i*' - 4'2i) = Ё 4:'-
Подставляя это выражение в (5.56), получаем (5.55).
У т в е р ж д е н и е д о к а з а н о .
Теперь проанализируем поведение задержки (5.55) в ряде частных слу чаев.
С л е д с т в и е ! .
Время передачи сообщения в однородном виртуальном соединении с "прямой" очередью в начале пути, содержащей разнотипные пакеты, упо рядоченные по убыванию г:
rW>r(*'+i), i = Tj; |
(5.57) |
задается соотношением
T^{D,N,k*) = ^к^^т^^ |
+ Мт^^+^^ + J2 г^'"^- |
(5.58) |
г=1 |
d=2 |
|
С л е д с т в и е 2.
192
Время передачи сообщения в однородном виртуальном соединении с оче редью в начале пути, неоднородной по составу пакетов, упорядоченных по возрастанию г:
|
rW <т^'+^\ г =17/; |
|
(5.59) |
не зависит от структуры очереди: |
|
|
|
T\D,N,k*) |
= ^ A;WrW + {N + D- |
1)т^^+'^\ |
(5.60) |
Д о к а з а т е л ь с т в о . |
Е Еу. Поскольку для |
||
Рассмотрим в соотношении (5.55) компоненту |
|||
типов пакетов i = id, i^+i |
— 1 длина пути равна d, |
а для типов |
i = ij)^ - |
D, то полагая, что пакеты сообщения образуют тип z/j+i = 1 + 1, данную сумму можно переписать в виде:
Е 4:' |
= Е |
Е 4"- |
(5.61) |
i=l2 |
d=2 |
i=id |
|
Прямой подстановкой в (5.53) нетрудно проверить, что в силу условия (5.59)
Ef = 4 ^ l + г^'"-'^ - r{i) = {d- 1)(г(^>1) - r(i)). Тогда, (5.61) принимает вид
Е 4 ? = E{d- |
l^T^''^^^ - т^'"^) = {D- l)r('+i) - |
f: т^''\ |
|
i=i2 |
dz=2 |
d=2 |
|
Подставляя это выражение в (5.55), получаем (5.60). |
|
||
С л е д с т в и е |
д о к а з а н о . |
|
|
Если все пакеты очереди адресованы в D, то id =^ I, |
d = 1,D, а |
||
di = D, i = IJ |
и задержка (5.55) преобразуются к |
|
|
T%D,N,k*) = ^(А;«г(г) + Eg^) + iVr('+i) + {D - 1У^\ |
(5.62) |
||
|
г = 1 |
|
|
Нетрудно видеть, что при выполнении условия (5.59) отсюда получа ем (5.60). Для однородного трафика (г^*^ = г, г = 1,/ -f-1) соотношения (5.55), (5.58), (5.60), (5.62) преобразуются к полученному ранее выражению (5.38). По аналогии с (5.41) для задержки сообщения в однородном вирту альном соединении с неоднородным трафиком можно записать следующее неравенство:
f:(D,N,k*) < T-^{D,n.k^) < f:{D,N,k*),
193
где T^(D,N,k*) - |
определяется соотношением (5.58) и достигается при |
выполнении условия (5.57), а |
|
r„"(L>, N, к*) = Е |
A;(^VW + iVrC+i) + (D - 1)т^^\ r^^) = таз^г^^'^ (5.63) |
г=1 |
г=1,/+1 |
- При справедливости (5.59).
Перейдем к рассмотрению инверсного по длинам путей порядка паке тов в очереди. Так же как и в случае однородного трафика (см. п.5.4.1) здесь за счет убытия пакетов, достигших адресата, из хвоста последо вательности пакетов очереди могут образовываться интервалы простоя каналов отдельных звеньев тракта передачи данных. Аналогично (5.42) длительность этого интервала Yd, d > 2 определяется его размером на предыдущем этапе Yd-i и разностью времен одновременно передаваемых на различных этапах пути пакетов, адресованных в узлы i = d — 1,D, и пакетов, направляемых в узлы г = d,D (см. рис.5.12):
y, = y,_i + G|(/t("-i)r(')+ |
ё 'fc<'V')+ Е 4'2i + ^'"'- |
|
I |
i=id-i |
i=id-i |
i=id |
) |
|
= y,_i-bG rO-r(')+ £ |
A;«r(^-)+ ^ |
E £ I " E 4 ^ |
i=id-i |
t=td-i |
i=id |
d = 2,D, Yi = 0. |
(5.64) |
|
Теперь найдем задержку сообш;ения в виртуальном канале.
У т в е р ж д е н и е 5.6.
Время передачи сообщения в однородном виртуальном соединении с ин версным расположением пакетов в очереди, состав которой задается век тором неоднородности (5.52), определяется соотношением:
T:{D, N, к*) = Е (А;«г« + Е§) -Ь Nr^^^ + {D - l)r(') + YD- |
(5.65) |
i=iD
Д о к а з а т е л ь с т в о .
В силу конвейерного эффекта для задержки сообщения справедливо:
T:{D, N,k' = i: к^^т^^+NT^^^ + Е ( Е i^^^r^'^+4''^)+^^+NT^^^-
i=l |
d=2 Ki=id |
194
- {{к^'^ - l)r^'^ + 4 ^ 1 + |
Е |
{k^iy |
+ E«i) + Yd-г + iVrW |
|
||||||
= |
^ |
A;«r('') + NT^^^ + ( D - |
l)r(') + |
YD- |
|
|||||
D |
id-l ... ... |
D |
I ... |
D |
I |
... |
(5.66) |
|||
- Е Е |
«^<'V« + E E 4" - E |
E |
s«i. |
|||||||
d=2i=id-i |
|
d=:2i=id |
|
d=-2i=id-i |
|
|
||||
Так как zi = 1, то |
|
|
|
|
|
|
|
|
|
|
|
|
D |
«d —1 |
|
«D —1 |
|
|
|
|
|
|
|
d=2i=fd _ i |
|
г=1 |
|
|
|
|
||
Тогда, поскольку по определению |
Е{^ = |
0, |
г = 1,/, |
то задержка (5.66) |
||||||
принимает вид (5.65). |
|
|
|
|
|
|
|
|
|
|
У т в е р ж д е н и е |
д о к а з а н о . |
|
|
|
||||||
С л е д с т в и е ! . |
|
|
|
|
|
|
|
|
||
Задержка сообщения в однородном виртуальном соединении при ин версной организации очереди из неоднородных пакетов, время передачи
которых по звеньям пути удоволетворяет условию |
|
^(i-i) < ^(0^ i = i j |
(5.67) |
(заметим, что это условие эквивалентно условию (5.57) для очереди "пря мой" структуры), задается выражением
r,"(D, AT, к*) = Е |
к^^т^^ 4- NT^^^ -Ь ( D - l)r(') + YD- |
(5.68) |
||
г—ID |
|
|
|
|
Если при ЭТОМ еще и |
|
|
|
|
^^°^ + |
Е |
^(г)ПО > ^^'^ d = 2,D, |
|
(5.69) |
|
i=id-i |
|
|
|
ТО |
|
|
|
|
T:{D, iV, к*) = Е A;(^VW + {N + D- |
l)r(°), |
(5.70) |
||
В противном случае |
|
г = 1 |
|
|
|
|
|
|
|
Т«(1),АГ,Г) |
= |
Е ^^''^^^'^ + NT^^^ + {D- |
l)r('). |
(5.71) |
Д о к а з а т е л ь с т в о .
195
в силу (5.67) из (5.54) имеем: Е^^ = 0, i = 1,1, d = 2,D. Тогда из (5.65) получаем (5.68). Рассмотрим (5.64) при условиях (5.67) и (5.69):
Yo=T.(г^'^ - г^'^ + Е ' A;(^V«) = {D- l)(rW - rW) + ' £ ' A;«rW.
Подставляя данное выражение в (5.68), получаем (5.70). В том случае,
когда |
условие (5.69) не выполняется. Yd = О при d = 1,D и соотношение |
|
(5.68) |
принимает вид (5.71). |
|
С л е д с т в и е |
д о к а з а н о . |
|
С л е д с т в и е |
2. |
|
Задержка сообщения в однородном виртуальном соединении с очередью
из неоднородных пакетов, параметры |
т которых удовлетворяют условию |
|
r(^'-i)>rW, |
г = 171, |
(5.72) |
эквивалентному условию (5.59) для "прямой" организации очереди, не за висит от структуры очереди:
T'^iD, N, к*) = Е А;^г« + (N + D- 1)г(°). |
(5.73) |
г= 1
До к а з а т е л ь с т в о .
Найдем величину интервала простоя Уд. В силу (5.72) Е^^ = (б? — 1)(7-0-1) _ ^(г))_ гр^^,д^ JJ3 (5.64) имеем:
|
D |
( |
|
r(') + |
id-l |
A;(^V« + (^ - 2) (г^^'^—^) - |
r^^)) - |
|
YD = EG\ |
r^'^ - |
E |
||||||
|
|
|
|
- ( d - l ) p ' ^ - i ) - r ( ' ) ) } = |
|
|||
= EGl'f: |
k^^T^^ + (r(°) - |
T^''-^^) + {d- 2)(r(*'<'-i) - |
r^^'-^-i))! . |
|||||
d=2 |
[i=id-i |
|
|
|
|
|
J |
|
Поскольку |
id-i |
< id, |
то в силу (5.72) |
r^^d-i-i) _ ^-Od-i) > 0, d = 1,D и |
||||
Yo можно переписать следующим образом: |
|
|||||||
|
|
|
г Ъ - 1 |
|
£> |
D |
1)т^''-^^ = |
|
YD = (D- |
l)r(°) + |
Е |
hi)''^ |
+Eid- |
2)т^''-'-^^ -E(d- |
|||
|
|
|
i-l |
|
d-2 |
d=2 |
|
|
«o—1
= {D- l)(r(°) - r(^'^-i)) + E A;(^V«.
г = 1
196
Подставляя данное соотношение для YD В (5.65) и учитывая, что
1 ^« = (I)-l)(r('-z.-i)_r(0), получаем (5.73).
г=го |
|
С л е д с т в и е |
д о к а з а н о . |
Нетрудно видеть, что в силу (5.51) выражения (5.60) и (5.73) совпадают. В том случае, когда все пакеты очереди адресованы в D, задержка (5.65) с учетом порядка расположения пакетов в очередях различной структу ры преобразуется к (5.62). Для однородного трафика соотношения (5.65), (5.68), (5.70), (5.73) принимают вид (5.38). Сравнивая (5.55) и (5.65), (5.58) и (5.68), (5.60) и (5.73), можно сделать вывод о том, что задержка сообпдения в однородном виртуальном соединении с неоднородной очередью в начале пути произвольной структуры в общем случае удовлетворяет не равенству:
T„"(D,iV,r) < T%D,N,k*) < T^(D,NX)'
Данное неравенство можно дополнить соотношением между верхними и нижними границами задержек для регулярных структур очереди:
f:(D,N,k*) < f:iD,N,k*) < f:{D,N,k*) = f:{D,N,k*),
где T^{D, N, к*) - определяется выражением (5.71) и достигается при выполнении (5.67) и нарушении условия (5.69), а T^{D, iV, к*) - определяется зависимостью (5.63) и достигается при условии (5.72).
Теперь рассмотрим случай, когда очередь к выходному каналу связи имеется в каждом звене однородного виртуального соединения. Будем счи тать, что известен размер каждой очереди k(d), с? = 1, D, количество ти
пов пакетов в ней l{d), время передачи пакета г-го типа из |
d-ож очереди |
||
T^^\d) и число пакетов данного типа в этой очереди |
k^^\d). |
Очевидно, |
|
что |
|
|
|
l{d) |
|
|
|
J2k^'Kd) = k(d), |
d = l,D. |
|
|
г = 1 |
|
|
|
Будем полагать, что величины k^^\d), |
с? = 1,D, i |
= l,l(d) |
образуют |
вектор структуры трафика вдоль тракта передачи данных: |
|
||
Г(*) = |
|
|
|
= А;(1)(1),..., А;('(1))(1),..., k^'\d),..., k^^^'^\d),..., к^'\П),..., |
A;(™(i^). |
||
Тип пакетов передаваемого сообщения обозначим через /(1)-|-1. Множе ство пакетов, адресованных из d = 1,D в j = d,D, обозначим следующим образом:
k^'\d), г = ij(d),ij+i(d)-l, |
id(d) = 1, iD+i{d) - 1 = l{d). |
197
Для общего случая произвольных структур очередей и произвольных соотношений между T^^\d) получить соотношение для задержки сообще ния не удается, но возможна формализация варианта прямого переупоря дочения пакетов в транзитных узлах соединительного пути, аналогичного тому, который рассматривался в п,5.4.1. Необходимым условием прямого переупорядочения является невозрастающее по г положение пакетов в каждой очереди:
T^^{d) > T^'+^\d), i = l,l(d)-l, d = 17^,
так как при перестройке прибывающего в транзитный узел потока паке тов и очереди в нем не допустимы интервалы простоя Е^^ > О канала связи. Поскольку переупорядочение ведется внутри множества типов па кетов, адресованных в заданный узел j из узлов d = l,j, то должны соблюдаться дополнительные соотношения между параметрами т для
типов пакетов, адресованных в j |
и j -Ь 1 |
из различных узлов: |
|
^(b+i(d)-i)(^) > r(b+i(^))(p), |
d = T;D, |
g = Tj, j = |
d,D-i. |
Теперь в силу конвейерного эффекта для задержки сообщения в одно родном виртуальном соединении с неоднородным трафиком можно запи сать следующее выражение:
|
|
|
'(1) |
|
|
|
|
г=1 |
|
D |
|
d |
Kj) |
|
+ Е |
Е |
Е A:«(i)r«(i) + 7Vr('(i)+i)(l)- |
|
|
d=2 |
j=i i=id{j) |
|
||
'd-l |
4J) |
, , |
|
|
E |
E |
*:«0>«(Л - r£f,_„ + iVr('(iH')(i) |
|
|
I j = l |
t=ii{j) |
|
|
|
где |
|
|
|
|
Выполняя суммирование в соотношении для задержкки |
TI^(D,N,k*(*)), |
|||
получаем: |
|
|
|
|
|
|
D К^) |
D-1 |
г&Л (5.74) |
r«(I>,iV,F(*)) = Y:Ek^4d)T^4d) + NT('('^+'\l) + Е |
||||
|
d=li=l |
d=l |
|
|
198
Отсюда нетрудно видеть, что если все пакеты адресованы в |
D, то |
id = |
|||
1, d = 1,D и задержка принимает вид: |
|
|
|
||
|
D Kd) |
D-l |
|
(5-75) |
|
r«(D,iV,r(*)) =ЕЕ |
^^'V«M + iVr('(i)+i)(l) + |
Y: 4\dy |
|||
|
d=li=l |
|
d=l |
|
|
В |
случае однородного |
трафика {т^^\(Г) = г, |
d — |
l,D, |
i = |
ITpJ, |
r(^(i)+i)(l) = r) из (5.74) и (5.75) имеем (5.50). |
|
|
|
|
Рассмотрим общий случай передачи сообщения, состоящего из неодно родной последовательности пакетов, от источника до адресата по неодно родному виртуальному соединению. Обозначим через Td{n), d = l,D, п = 1,N - время передачи п-го пакета сообщения по (i-му звену. При переносе информации в таком тракте после передачи по межузловому соединению очередного (п-го) пакета образуются интервалы ожидания следующего, обусловленные неоднородностью потока данных:
Ed{n) = G{tEd-i{i) |
+ Е rd-i{i) - |
t rd(i) - |
E |
Ed{i)] , |
1г=1 |
j=2 |
2=1 |
i=l |
J |
Ei{n) |
= 0, n = l,N |
-1. |
|
|
У т в е р ж д е н и е 5.7.
Задержка неоднородной последовательности из А^ пакетов в неоднород
ном тракте передачи данных длины D определяется соотношением: |
|
||
T\D,N,0) = Е г,(1) |
+ Е МП) |
+ 'ЕМГЬ)- |
(5.76) |
d=l |
п=2 |
п=1 |
|
Д о к а з а т е л ь с т в о .
Поскольку передача потока пакетов на d-ou этапе пути совмещена с передачей N — 1 пакета на d — 1-ом участке переприема, то для полной задержки сообщения справедливо:
r«(D,iv,o)=En(n)+
|
|
|
n=l |
|
D |
( N |
N-l |
N |
N-1 |
+ E |
E |
rd{n) + E |
Edin) - E rd-i{n) - |
E Ed-iin) \. |
d=2 |
(n=l |
n=l |
n=2 |
n=\ |
С учетом определения интервала ожидания Ed{n) отсюда приходим к (5.76).
199
У т в е р ж д е н и е |
д о к а з а н о . |
С л е д с т в и е ! . |
|
Время передачи сообщения, состоящего из однородной последователь ности пакетов, в однородном виртуальном соединении {та{п) = т, d = 1,D, п = l,iV) определяется соотношением (5.6).
С л е д с т в и е 2.
Время передачи сообщения, состоящего из однородной последователь ности пакетов, в неоднородном виртуальном соединении {Td(n) = Td, п = 1,N) определяется соотношением (5.1).
С л е д с т в и е 3.
Время передачи сообщения, состоящего из неоднородной последователь ности пакетов, в однородном виртуальном соединении {Td{n) = т{п), d =
1,D) определяется соотношением: |
|
Т\В,М,0) = Пт(М)Л- Е |
^ W , г(М) = шах г(п). |
п=1,пфМ |
n=l,N |
Из данного соотношения видно, что задержка неоднородного сообщения в однородном тракте в значительной мере определяется самым длинным пакетом.
Проанализируем задержку (5.76) при различных соотношениях между Td{n). Если множество неоднородных пакетов образует невозрастающую последовательность
rd(n)>Tdin-\-l), |
n = l,N-l, |
d = l,D, |
а звенья виртуального канала - неубывающий по времени передачи пакета на отдельном участке переприема порядок
Td{n) < Td+i(n), d = l,D -1, |
n = l,N, |
|
||
то интервалы ожидания Ео{п) |
= О, п = l^N |
и задержка неоднородного |
||
сообщения в неоднородном тракте принимает вид: |
|
|||
T%D,N,0) |
= Е |
Td{l) + Е |
TD{n). |
(5.77) |
|
d=l |
п=2 |
|
|
В том случае, когда величины Td{n) удовлетворяют невозрастающему порядку в пространстве (в тракте передачи данных)
rd(n)>Td+i{n), d = l,D-l, |
n = l,N, |
200