lect

всей сети, его следует определять из условия максимума выигрыша для виртуальных соединений всех возможных длин. Таким образом, для прак­ тического применения зависимостей (5.12), (5.13) их необходимо обобщить на случай интегрального критерия.

5.2.3Выбор рационального размера кадра

Предположим, что для сети передачи данных заданы все возможные длины путей Dj, j = 1,J и распределение интенсивностей (долей) сетево­ го трафика по трактам передачи данных aj, удоволетворяющее условию

J

нормировки Е Qfj = 1, где J - число различных информационных потоков.

Пусть также для каждого информационного потока задано непрерыв­ ное распределение длин сообщений fj{B). Рассмотрим в качестве целевой функции средний выигрыш, являющийся естественным обобщением кри­ терия (5.8) на всю сеть передачи данных:

J ОО

AiNuN2,...,Nj)=Zc^jjHDj,Nj)dfj(B) =

i=i о

(5.14)

где Bj = J Bdfj{B) - средняя длина сообщений j-го информационного

потока. Поскольку каждое виртуальное соединение имеет свое значение коэффициента разбиения, то в данном соотношении удобнее сразу перейти

к искомой длине кадра	L. Подстановкой		L = Н + jf: из (5.14) получаем:
				J
^	^^	а-й	^	^^	ал
j=l	й=14фМ^	^jd	j=l	d=l,dT/^Mj	^jd

Отсюда легко определяем оптимальное значение L:

Е ajBj	"t:	+ Гм,
= Н +		(5.16)
Lo--
Eaj	E	Tf-
\ j=l	d=l,d^Mj	Cjd

161

Здесь параметры CMJ И ТМ^ , определяющие узкое звено j-ro виртуаль­ ного соединения, находятся из условия аналогичного (5.2):

aMjL	_	(ojdL	(5.17)
	+ TMJ=	m ^ l ^ + Tjd], j = hJ.

В случае однородной сети зависимость для оптимального L преобра­ зуется к виду:

	Lo = H +	\|	В{аН + СТ)	'	^^-^^^
			аф-1)
J	-				-

где Б = Е OijBj - средний размер сообщений, передаваемых по сети, D = i=i

ЕCijDj - средняя длина сетевых трактов передачи данных. Отметим, что

вслучае передачи сообщений одного размера из (5.16) и (5.18) получаем соответственно (5.12) и (5.13).

Нетрудно видеть, что условие (5.17) однозначно определяет "узкие" зве­ нья виртуальных соединений только при нулевом времени обработки паке­ та в узлах коммутации, в общем же случае, параметрическая зависимость

условия (5.17) от L не допускает однозначного определения "узких" мест до вычисления оптимального размера кадра. Для случая, когда временем обработки пакета в узлах пренебречь нельзя, можно предложить процеду­ ру последовательного вычисления оптимального размера кадра. Согласно

такой процедуре оптимальное значение L			рассчитывается итеративно.
В качестве начального значения	L	для определения "узких" звеньев по
условию (5.17) можно принять	L	= Н.	По найденным таким образом
параметрам См^, Тм^, амр j = ^,J		из (5.16) вычисляется размер кадра,

который используется для определения "узких" звеньев на следующем ша­ ге. Критерием останова итеративного процесса является совпадение раз­ мера кадра или множества индексов узких звеньев Mj, j = 1,J в двух последовательных итерациях.

Теперь соотношения (5.16), (5.18) можно дополнить решающим прави­ лом, учитывающим ограничения рекомендации ITU-T Х.25 на множество значений размера информационной части пакета. В силу унимодальности критерия (5.15) наилучшее из разрешенных рекомендаций Х.25 значений

162

L в битах определится по правилу:

	2 ^	Ln-H	<27.
			)i+l
	L'=H+\	2 ' < L o - Я < 2 * + ^ V i > 0 ,
		2* < ^ о - Я < 2*'+1, V i < 0 ,
	о13
		Ln-H>	2^^

	г =	7Д2;	(5.19)
	г =	7Д2;

где	Vj = А(Я + 2*) — А(Я + 2*"^^). Таким образом, вычисляя значение
LQ	по предложенному алгоритму и LQ ПО правилу (5.19), определяем ра­

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

Геометрически решающее правило (5.19) интерпретируется неперекры­ вающимися областями оптимальности альтернативных значений размера

информационной части пакета b = L — Н	(рис.5.5), уравнения границ
между которыми определяются условиями	Vj =	0, г = 7,12	и для одно­
родной сети имеют вид:
а(П-1) = ^-^^г^^,г	=	7,12.	(5.20)

В том случае, когда "узкие" участки виртуальных соединений сети мо­ гут быть однозначно определены при L = Н -\-2^ и не изменяются при 2'' < I/ — Я < 2^^, уравнения границ альтернативных значений b прини­ мает простой вид и для случая неоднородной сети:

J

E	Cljd _ _J-	dMjH	+ Г,	1 = 1,12.	(5.21)
	Ё OijBj	c,
			Mj

Из (5.20), (5.21) нетрудно получить соотношения для оптимального по­ казателя степени ZQ. С учетом требования целочисленности i оптималь­ ная степень определяется выражениями:

«о	,	(В{аН + СТУ				7 <	г'о < 13	(5.22)
	^'^' [			2аф-1)
для однородной сети и
	/	J	-	+ T,
	log.				Mj	,	7 < io < 13	(5.23)
«о =		J		Dj	a-jd
		2E	aj E
					Cjd
		j=l		d=l,d^Mj

163

6	6 = 2»	6 = 2^°	6 = 2^

4

2

log,{B{H + СТ)}

О

-2

-4

-6

Рис. 5.5: Диаграмма областей оптимальности альтернативных значений размера информационной части пакета b для однородной сети

164

для неоднородной сети. Очевидно, что значение L'Q определится при этом равенством L'Q = Н + 2*°.

П р и м е р 5.1. Рассмотрим однородную сеть, переносящую 5 информапионных потоков с равномерным распределением интенсивности трафи­ ка по трактам передачи. Пусть длины путей имеют значения от 1 до 5, а время узловой обработки пакета составляет 0.01с. Будем считать, что сообщения, передаваемые по различным виртуальным соединениям, име­ ют одинаковые средние В = 3000байт. Скорость передачи данных по сетевым соединениям примем равной ЮООбайт/с.

Предположим, кроме того, что передача данных в подсети связи регла­ ментируется протоколами, выполненными в соответствии с рекомендапией ITU-T Х.25 Тогда, величина Я, определяемая кадровой служебной информацией и заголовком пакета "данные" сетевого протокола, составит 9байт [34, 112]. Коэффициент удлинения кадра в сетевых каналах связи положим равным 1.

Действуя в соответствии с предложенной схемой, из (5.22) получаем: г'о = 7. Тогда L'Q = Н + 2*° = 131байт. При этом сетевая задержка, вычисляемая по формуле

aL + CT
^(^•^) = (^ + r ^ - i )	С

полученной из (5.7) подстановкой N = B/(L — Н), для средней длины пути и среднего размера сообщений, уменьшилась с 9.07с для L = H + B до 3.75с для L = L'Q, что составило более чем двукратное ее понижение.

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

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

5.2.4Учет реальных свойств каналов связи

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

165

4 -

3 -

1 -,

D

Рис. 5.6: Зависимость относительного выигрыша от длины виртуального соединения

166

вой ошибки в прямом (г„) и обратном (го) каналах связи звеньев передачи данных. Тогда среднее значение задержки Td с учетом повторных передач, обусловленных искажениями в передающей среде, определится соотноше­ нием (2.2). Поскольку мы рассматриваем ненагруженный тракт передачи данных, то можно считать, что трафик на виртуальном соединении имеет однонаправленный характер, то есть т ^ = 1, d = 1,D и

td + Td	udL + CdTd
Td = i-Hd	Cd{i-r,dY^^{i-rodY''''

Подставляя данное выражение в (5.1) и учитывая, что N = JZH^ по­ лучаем следующее соотношение для задержки отдельного сообщения:

	d=l,d^M^d[i- - Гпв) '^
В	ам^ -\- СмТм	/_ Рдч
^ 1-НСм{1-г,мУ^^{1-ГомУ^'''		^' ^

Тогда средняя задержка абонентских сообщений в сети передачи данных определится выражением:

		J	°°		=
	f{D,L)=Ec^jjT{Dj,L)dfj{B)
		i=i	о
J	^		ttjdL	-f-	CjdTjd
	i< d=i%M, Cid(i -			T^jdY^^^^i - rojdY^'^
	Bj	aMjL +		CMjTMj		(5.25)
Отсюда в предположении		Vnjd = fojd = '^j o-jd = о.-, d = l,Dj, j = 1, J
и справедливости	(1 — гУ^	~	1 — raL		удается найти аналитическую

оценку оптимального размера кадра, минимизирующего среднюю задерж­ ку (5.25):

1		( J
L = —J		< а J2 o^jiH(Pj - TBJTMJ )+
а Е aj{(pj -\-raBj/CMj)		i =i
f -^ /	гаВЛ	-^

+ra' U-HJ:		ajipj (аЯ E ^	+ 27^ ^ ' '	(5.26)
\	i=i	V i=i	^Mj

167

где

	^>	/ 1	\	1	'^	-
^3 =	Е	77-	+ ^^irf	; Фз = т^ + гТы^, 7 =	T.O'JBJTMJ.

Для однородной сети данная оценка несколько упрощается:

L = ~-^	г7—Ц^7=^		^\a(H(D-1)(1+		гСТ)-гВСТ)+
a((D -	1)(1 + гСГ) + гаБ) ^ ^ V			А	;	;^
+ {аБ {{{D -		1)(1 + гСТ) + гаВ){аН{1 + гСГ) + СГ)+
+га(гВС^Т^		- H(D -	1)(1 + гСТ)(аН	+ 2СГ)))}Н .		(5.27)

Нетрудно видеть, что при г = О соотношения (5.26), (5.27) преобразу­ ются к (5.16) и (5.18) соответственно.

Очевидно, что для расчета оптимальной длины кадра неоднородной сети можно построить итеративную процедуру, аналогичную предложен­ ному в п.5.2.3 последовательному процессу вычисления LQ. В целом вы­ ражения (5.26), (5.27) слишком громоздки для практического применения. Перейдем к поиску более простых аналитических оценок оптимального размера кадра.

5.3Совместная оптимизация сетевых параметров по критерию системы и критерию пользователя

5.3.1Проблемная ситуация

Эксплуатационные характеристики сети передачи данных с коммута­ цией пакетов в значительной мере определяются длиной кадра и размером окна на линейном уровне. Задача выбора этих параметров носит сложный многокритериальный характер [20, 207, 211]. С одной стороны, необходи­ мо удоволетворить системные требования по обслуживанию сетью наи­ большего числа ее абонентов. С другой стороны, каждый пользователь се­ ти желает быть обслуженным за минимальное время. Наиболее важными критериями системы и пользователя, экстремальных значений которых в первую очередь добиваются проектировщики сети передачи данных, явля­ ются соответственно пропускная способность межузловых соединений и время доставки пользовательских даных по виртуальным соединениям. Во многих случаях выбор параметров, оптимальных по одному критерию, да­ ет неудоволетворительные значения другого критерия [207, с.92-94]; [210,

168

с.256]. Очевидно, что решение задачи выбора значений параметров должно обеспечить разумный компромисс между требованиями системы и поль­ зователя.

Разработанные в главах 2-3 и п.5.2 методы формального выбора значе­ ний параметров ориентированы на безусловную оптимизапию по одному из критериев. В данном разделе с целью совместного учета требований си­ стемы и пользователя для неоднородной сети передачи данных строится композиционный критерий, позволяющий получить достаточно простые аналитические оценки оптимальной длины кадра и размера окна, обес­ печивающие минимальное среднее время доставки сообщенй пользовате­ лей по виртуальным соединениям при несущественном отклонении потен­ циальной пропускной способности сетевых соединений от максимального значения. Построения выполнены в предположении умеренной нагрузки на сеть, позволяющем пренебречь взаимодействием информационных пото­ ков, переносимых различными виртуальными соединениями. Кроме того, считается, что задержка сообщений в виртуальном соединении описывает­ ся соотношением (5.1), межузловые соединения управляются нормальной процедурой обмена в режиме группового или селективного отказа, а сете­ вые каналы связи характеризуются низкой интенсивностью искажений.

5.3.2Метод выбора длины кадра и ширины окна

Для построения формальной процедуры выбора сетевых параметров, учитывающей требования системы и пользователя, воспользуемся априор­ ной информацией о виде зависимости целевых функций вблизи экстрему­ ма от оптимизируемых параметров: если мода системного критерия имеет размытый характер от параметра длины кадра [134], то критерий пользо­ вателя имеет ярко выраженный экстремум по этой координате [135], обес­ печиваемый трубопроводным эффектом; в то же время для размера окна имеет место обратная, хотя и менее яркая картина. Такая зависимость критериев от оптимизируемых параметров позволяет упорядочить выбор значений длины кадра и ширины окна. Совершенно естественно и разум­ но при этом длину кадра выбирать по критерию пользователя, а затем для найденной длины кадра определить оптимальный по критерию систе­ мы размер окна. Учитывая, что наибольшая длина кадра должна иметь единственное значение для всей сети, а ширина окна может иметь инди­ видуальный размер для каждого межузлового соединения, задача упоря-

169

доченного выбора параметров формально записывается в виде:

^(D, L) —>• min, Cffi(L,LJi,l) ^^ max, г = 1,к.

(5.28)

Напомним, что T{D,L) - средняя задержка абонентских сообщенй в сети передачи данных (критерий пользователя), определяемая соотноше­ нием (5.25); CHi{L,uji,l) - потенциальная пропускная способность г-го межузлового соединения (критерий системы), определяемая зависимостью (2.10) для нормальной процедуры обмена в случае селективного отказа и выражением (2.11) в случае группового отказа, к - количество сетевых линий связи.

Прямое решение (5.28) приводит к громоздкой оценке оптимального значения L вида (5.26) и (5.27). Для получения более простой аналити­ ческой зависимости для оптимального L модифицируем задачу упорядо­ ченного выбора, построив композиционный критерий эффективности сети пакетной коммутации. Из соотношений (2.10), (2.11) видно, что критерий системы может быть представлен в виде произведения:

Ся.-(Ь,а,.,1) = (Ь-Я)^=1Ь11).

Второй сомножитель данного выражения является средней пакетной ско­ ростью передачи данных. Тогда для критерия пользователя в терминах пакетной скорости передачи из (5.25) имеем:

л		Dj
T{D, Ь) = Е	<yj	^
i=i		d=i,d^Mj

ijd	JBjtMj
^Hjdil, 1)	(L - H)ZHMJ{X, 1) ^

Если в данном выражении ZHjd{l,l) заменить на Zffjd{ujjdA)^ <^jd > 1, то получим композиционный критерий и задача оптимизации сетевых параметров перепишется в виде:

K{L,u) =	J	y^	^i^	I	__	^i^^i
	J2O:J						mm,
		d=l,d:il:Mj ZffjdioJjd, 1)			(L -	H)ZHMJ (^M; , 1)	L.w

(5.29) где uj - вектор параметров и>{ размерности к. Отметим, что для вирту­ альных соединений единичной длины полученный композиционный крите­ рий с точностью до постоянного множителя совпадает с критерием систе­ мы. Нетрудно видеть, что относительно параметров cui, г = 1,к задачи (5.28) и (5.29) эквивалентны, а по параметру L отличаются пакетными скоростями передачи данных. Однако, учитывая относительно малое для

170