lect

достигается при неубывающих значениях	г (г^ < 7^+1, d = 1,D — 1), а
наибольшая -
fn(D,N,k) = T{D,N,0)-\-kTM		(5.40)
- в случае TI > Td, d = 2,D {тм = п).	Очевидно, что задержка сооб­

щения в виртуальном соединении с произвольными соотношениями между параметрами г^ удовлетворяет неравенству

fn{D,N,k) < Tn{D,N,k) < fn{D,N,k).

(5.41)

Теперь рассмотрим случай инверсного порядка пакетов в очереди перед сообщением. Из схемы, приведенной на рис.5.9, видно, что при d >2 меж­ ду потоком пакетов из очереди и последовательностью пакетов сообщения могут образовываться интервалы простоя отдельных звеньев виртуально­ го соединения У^. Размер интервала Yd определяется величиной простоя на предыдущем этапе пути Yd-i и разностью времени передачи по звену с номером d — 1 пакетов, адресованных в узлы-получатели звеньев с но­ мерами i = d — l,D, и временем передачи по звену с номером d пакетов, адресованных в узлы i = d,D:

D	d = 2,D, Y^ = 0. (5.42)
Yd = G lYd-i + kd-iXd-i + {Xd-i -Xd)Eki\,

С учетом введенного интервала простоя можно определить задержку сообщения в виртуальном канале.

У т в е р ж д е н и е 5.3.

Задержка сообщения в неоднородном виртуальном соединении с инверс­ ным расположением однородных пакетов в очереди отправителя сообще­ ний задается соотношением:

Tu{D,N,k) = T{D,N,0) + kDTM+YD.

(5.43)

Д о к а з а т е л ь с т в о .

Поскольку на участке пути d > 2 передача всех пакетов потока со­ вмещена с их передачей (за исключением первого пакета) на предыдущем

участке	(рис.5.9), то с учетом		(5.3) и интервала простоя для		задержки
сообщения имеем :		T,{D,N,k) =
= i:lrd+(f:ki		+ N-l]xd	+ Yd- ( Е ki-^N-l]xd-i-Yd-i] =
d=l [	\i=d	J	\iz=d-l	J	J

181

Путь передачи

Звено

Начало

передачи

Время

Конец

приема

Рис. 5.9: Схема прохождения сообпдения по нагруженному неоднородному виртуальному соединению (г4 > TI > Гг = Т5 > тз) с инверсной очередью однородных пакетов в начале пути (ki = к2 = к^ = 1, кз = 2, А;4 = 0, N = 5)

182

- Е	rrf + (iV - 1)Хд + 1Ъ + Е	X, i : А;, -	Е ' X, Е А;,.
d=l	d=l	i=d	d=l	i=d

Отсюда в силу утверждения 5.1 приходим к (5.43).

У т в е р ж д е н и е д о к а з а н о . С л е д с т в и е .

Для виртуального соединения с задержкой пакета в отдельных звеньях, удовлетворяющих условию

n>Td, d = 2,D,	(5.44)
справедливо следующее равенство:
fu{D,N,k)=fn(D,N,k).	(5.45)

Д о к а з а т е л ь с т в о .

Действительно, в силу условия (5.44) из (5.42) с учетом (5.5) получаем:

Yd = GYd-i +	kd-iXd-i.
Так как kd > О, Xd > О, d = 1,D, то
Yd = Yd-i + kd-iXd-ъ	d = 2,D,Yi = 0.
Ho тогда
D	D-l
Уп= J2 kd-iXd-i	= Ti E kd-
d=2	d=l

Подставляя данное соотношение в (5.43) и учитывая, что в силу условия (5.44) тм = TM{d) = '^ь получаем (5.40), а, следовательно, и (5.45).

С л е д с т в и е д о к а з а н о .

Очевидно, что при произвольных соотношениях между Td, d = 1,D

D-l

интервал простоя YD удовлетворяет неравенству О < Уд < Е kdXd- Тогда из (5.37) и (5.43) следует, что для задержки сообщения в виртуаль­ ном соединении справедливо

Tn{D,N,k)>Tu{D,N,k).	(5.46)
В наибольшей степени Tn{D,N,k) превышает Tu{D,N,k),	когда па­

раметры виртуального соединения удовлетворяют условию г^ < Td+i, d = 1, D — 1, поскольку при этом увеличение времени передачи пакетов на каждом этапе пути для инверсной организации очереди в определенной мере нейтрализуется тем, что пакеты, достигшие адресата, удаляются из

183

хвоста последовательности пакетов, принадлежаш;их очереди (см. рис.5.9). Из данных рассуждений и соотношений (5.41), (5.45), (5.46) можно за­ ключить, что между верхними и нижними границами сообщения спра­ ведлива следующая зависимость:

f,{D,N,k) <fn{D,N,k) <f^(D,N,k) <fn(D,N,k).

Здесь

f^(D, N, к) = T(D, iV, 0) -b koTD

- значение Tu{D, N, k), соответствующее порядку звеньев в виртуальном канале, при котором

Td<Td+u d = l,D-l

(5.47)

и Yd = О, d = 1,D. Очевидно, что задержка сообщения в виртуальном соединении с произвольным расположением пакетов в очереди перед ним T(D, N, к) удовлетворяет неравенству

Tu(D,N,k) < T(D,N,k) < TniD,N,k).

Таким образом, при формировании очередей к выходным каналам связи отдельных звеньев более предпочтительной (в смысле задержки) является стратегия инверсного по длинам путей упорядочения пакетов. Отметим также, что если все пакеты очереди адресованы в D, то Yd = О, d = 1,D, k]j = к, и задержка (5.43) совпадает с (5.39).

Рассмотренный нами случай, когда очередь имеется только в начале пу­ ти, вообще говоря, является вырожденным. Более общей следует признать ситуацию, когда поток пакетов, следующих по виртуальному соединению, застает очередь к выходному каналу связи на каждом этапе пути.

Для дальнейшего анализа предположим, что задана структура трафи­ ка вдоль тракта передачи, то есть будем считать, что известны размеры очередей k{d), d = 1,D, которые застает поток данных на каждом участ­ ке пути, и состав очередей kj(d), j = d^D, указывающий число пакетов очереди узла-источника звена d = 1,D, адресованных в узел-приемник звена j = d,D. Очевидно, что

J2kj(d) = Kd), d = T;D.	(5.48)
j=d

Будем полагать, что размеры и состав очередей образуют вектор струк­ туры трафика вдоль соединительного пути:

^*(*) = hW,..-, ко(1),..., kd(d),..., koid),..., ко{0).

184

Для наиболее общего случая произвольного расположения пакетов в очередях и произвольных соотношений между временами передачи паке­ та по различным межузловым соединениям виртуального канала найти простое выражение для задержки сообщений, позволяющее обнаружить какие-либо закономерности, не удается. Здесь можно получить липгь верх­ нюю границу задержки сообщения в нагруженном виртуальном канале, па­ раметры которого удовлетворяют условию (5.47). Очевидно, что эта гра­ ница соответствует случаю прямого переупорядочения пакетов в каждом транзитном узле, когда прибывающие в узел пакеты становятся не в конец очереди к выходному каналу связи, а упорядочиваются в соответствии с длиной пути до места назначения (номером адресата). Нетрудно видеть, что при выполнении условия (5.47) такое переупорядочение возможно.

У т в е р ж д е н и е 5.4.

Время передачи сообщения по нагруженному виртуальному соедине­ нию, удоволетворяющему (5.47), с очередями на всех этапах соединитель­ ного пути и прямым переупорядочением пакетов в транзитных узлах опре­ деляется соотношением:

D

D

(5.49)

г=13=1

Д о к а з а т е л ь с т в о .

d

D

Поскольку по звену

d>\

передача N пакетов сообщения и

kj{i)

Е

Е

г=1j=d

пакетов из очередей звеньев

г* =

1, с? совмещена с передачей потока из

Л''-!-

d-l

D

Е

T.kj{i) — 1

пакетов по предыдущему звену (рис.5.10), то для задержки

г=1

j=d

сообщения в силу условий утверждения справедливо:

D

iv + EE^iW Td-

TniD,N,h{^))

= N + k{l)n

+ Y:

d=2

г=1j=d

d-1

D

2=1 j=d

Td-l

= E'Td + NTD + EE

kj{d)Td +E{Td-

d-l

D

kj{i).

r,_i) E

E

d=l

d=l j-d

d=2

i=l

j=d

Из (5.47) следует что тм = TD.

Тогда с учетом (5.48) и утверждения

5.1 выражение для Tn{D,N,

к^^{^)) преобразуется к

Tn{D,N,k,{^))

= T{D,N,0)

+ Е

kid)Td +

Е

Е

Е kjii){Td

-

r,_i).

d=l

d=2 г=1

j=d

185

Путь передачи

Звено

Начало

передачи

Время

к{4) = 2

Г„р,]УД.(*))

Конец

приема

Рис. 5.10: Схема прохождения сообщения по нагруженному неоднородному виртуальному соединению (п < тг < Гз < Т4) с прямым переупорядочением очередей однородных пакетов в транзитных узлах соединительного пути при {ki{l) = kiil) = кг{1) = 1, k^il) = 2; ^2(2) = ^з(2) = ^4(2) = 1; кз{г) = 1, к^З) = 2; ^4(4) = 2; Л^ = 5)

186

Рассмотрим тройную сумму данного выражения. Очевидно, что соотно­ шения

d = 2,D] i = l,d~l; j = d,D\

и

z = l , D - l ; i = i + l,D; £^ = i + l,i;

задают одно и то же множество индексов d^ г, j . Тогда, последовательно меняя порядок суммирования, получаем:

	D d-l		D		Td-i) =	D-1	D	D
	И^И		kj{i){rd -			Е	Е	Е kj{i){Td - Td-i) =
	d=:2 i=l j=d					i=l	d=i+l	j=d
D-l	D		j	kj{^{rd -		D-l	D	kj{i)Tj-	D-l	D
= E	E	E			Td-i) = E		E		E	E %(«>»•
i=l	j=i+l	d=i+l				г'=1	j=i+l		i=l	j—i+1
						D-l
Прибавляя и отнимая здесь сумму						Е ki{i)Ti, имеем:
						1=1
	D d-l D					D-l D			D-l	^(«>i.
	E	E	E	kj{i){Td - Td-i) =			E E %W^i -		E
	d=2 i=l		j=d			i=l j=i			i=l

Подставляя данное значение тройной суммы в выражение для Tn{D, iV, К{*)), получаем:

Tn(D,iV,К(*))	= T{D,TV,0) + Е ' Е kj{i)Tj + k{D)Tn.
	г=1 j=l
Учитывая, что koi^D) = k[D). отсюда приходим к (5.49).
У т в е р ж д е н и е	д о к а з а н о .

Сл е д с т в и е ! .

Воднородном нагруженном виртуальном соединении задержка сообще­ ния не зависит от состава отдельных очередей и описывается соотноше­ нием

T{D, N, fc*(*)) = T(D, iV, 0) -f- г Е k(d)-

(5.50)

d=l

Данное выражение подтверждает вывод (5.38), полученный при анализе задержки сообщения в виртуальном соединении с очередью в начале пути.

С л е д с т в и е 2.

Если все пакеты данных, находящиеся в очередях, адресованы в узелприемник звена D:

kj(d) = 0, j = d,D-l, d = l,D-l,

kD{d) = k{d), d = l,D,

187

то задержка сообщения определяется зависимостью:

r ( D , iV, h{^)) = T{D, AT, 0) + тпЕ k{d).

Проведенный анализ направлен на изучение задержки сообщения в на­ груженном виртуальном канале, переносящем пакеты данных одного раз­ мера и, следовательно, имеющих одинаковые времена передачи по кон­ кретному межузловому соединению. Более реальной представляется ситу­ ация, когда сетевые потоки содержат пакеты различной длины, которые, естественно, имеют различные задержки даже в одном отдельном звене. Назовем такой сетевой трафик неоднородным и перейдем к анализу за­ держки абонентского сообщения в нагруженном виртуальном соединении, переносящем потоки с неоднородными свойствами.

5.4.2Модели виртуального соединения с неоднородным трафи­ ком

Рассмотрим однородное виртуальное соединение. Предположим, что

сообщение, содержащее N фрагментов, застает	в начале пути очередь из
А; > О пакетов, среди которых будем различать	/ < к типов. Полагаем,

что пакеты различных типов могут отличаться друг от друга размерами.

Число пакетов г-го типа	(г = 1,/) обозначим через	к^^\	а время передачи
пакета г-го типа - через	т^^\ Очевидно, что Е	^^*^ =	к. Считаем, что
	i—l

В транзитных узлах тракта передачи данных очередей нет.

Как и прежде будем рассматривать две регулярные структуры очереди - прямую и инверсную. Будем считать, что пакеты, адресованные в узелполучатель звена d = 1,D — 1, имеют типы г = id,id+i — 1, а пакеты, направляемые в D - типы г = IDJ- Очевидно, что соответствующей нумерацией и введением дополнительных типов пакетов всегда можно до­ биться такого состава очереди. В тех случаях, когда в некоторый узел d не адресовано ни одного пакета, тип id должен совпадать с id+i-

При прямой организации очереди в ее начале расположено множество

пакетов	к^^\	i =	1,Z2 — 1,	адресованных в	d =	1,	затем -	множество
пакетов	к^^\	i =	Z2,«3 ~ 1?	отправляемых в	d =	2,	и т.д. За	пакетами

/-Г0 типа расположены пакеты сообщения, образующие множество пакетов / -Ь 1-го типа.

При инверсной организации очереди положение ее элементов обратное: множество пакетов, адресованных в D {к^^\ i = in J), находится в начале

188

очереди, за ними - множество пакетов, адресованных в D — 1 {к^^\ г = io-i^io — 1)? и т.д. Пакеты сообщения находятся в конце очереди - за пакетами 1-го типа и образуют множество пакетов 0-го типа. Очевидно, что

rW = r('+i).

(5.51)

Будем полагать, что множество пакетов различных типов, находящихся в очереди, образуют вектор неоднородности ее состава:

к* = {к^'\к('\...,кЩ.

(5.52)

В дальнейшем для обозначения задержки в виртуальном соединении, переносящем неоднородный трафик, наряду с нижними индексами " п" и " и", указываюпщми на прямую и инверсную структуры очередей, будем использовать верхний индекс "м". Из рис. 5.11, 5.12, видно, что при d > 2 между окончанием передачи пакетов г'-го типа и началом передачи пакетов i -j- 1-го типа могут появляться интервалы простоя выходных каналов связи Е^', величина которых в силу однородности виртуального соединения определяется следуюпщм образом:

4'^ = GJ(yb(^'^)-i)r(''^)-f-^y_i-b i: fe^')r(^')-f4-i)+^^'^^^-

j=id j=id J I j=id j=id

i = T^l, d = XD] £?P = 0, г = T7I	(5.53)
для прямой организации очереди и
Ef = G ((А:(') - l)r(') -Ь Е^Л, + E(A;(^VW + Е^}^ -Ь r^^'-D -	Е ^^^V^^')-

- Ё s«H = G

j=i	iJ=i+l)
d = 27D, E P = 0, г = M	(5.54)

для инверсной организации очереди.

У т в е р ж д е н и е 5.5.

Задержка сообщения в однородном виртуальном соединении с прямым расположением пакетов в очереди, состав которой задается вектором не­ однородности (5.52), определяется соотношением:

r«(i?,iV,F) = Е	^«r(i) + iVr('+i) + f:	т^'^^ + J: 4 f ,	(5.55)
г=1	d=2	i=Id

189

Путь передачи

Звено

Начало

передачи

Время

T:{D,N,k*)

Конец

приема

Рис. 5.11: Схема переноса неоднородного трафика в однородном виртуальном соединении при прямой организации очереди в начале пути, / = 5; т^"*) < т^^) = т^^^ = т^^) < г^^^ = т(«); it(^) = 2, Jfc(2) = 1, jt(3) = 1, А;(4) = з, к^^^ = 2, N = 2; h = 1, i2 = г'з = 2, н = 4

190