kryl_vych_seti

	λ0
λ0		λ0
0	μ0
μ0
1		NN–1
		μ0
τ0,1
μ0
λ0
2

Рис. 1.21. Модель ЛВС на структуре кольцо

ваются с интенсивностью μ0 (пакетов/с). Пусть известны времена распространения сигналов τij между узлами i и j и максимальное время распространения сигналов в среде τm. Пусть заданы средняя длина пакета Tp и скорость передачи в среде fd (бит/с).

Необходимо определить зависимость среднего времени задержки пакетов в узле τ (от момента поступления пакетов от абонента в узел до передачи его в среду) от коэффициента использования среды передачи

η= S , fd

где S – средняя (эффективная) скорость передачи информации в среде (бит/ с).

Рассмотрим цикл передачи в сети, при котором право на передачу последовательно проходит через все N узлов.

Будем полагать, что коэффициент загрузки каждого узла равен ρ0. Это означает, что каждый узел в момент получения права на передачу при экспоненциальном времени обслуживания с вероятностью ρ0 имеет в очереди хотя бы один пакет (активный узел) и с вероятностью (1 – ρ0) не имеет пакетов (пассивный узел). Пассивный узел немедленно передает управление (право на передачу) следующему узлу, затрачивая на это среднее время τ0. Активный узел, получив управление, вначале передает пакет, что занимает в среднем время Tp, а затем за время t′0 передает управление следующему узлу.

31

За один цикл передачи управление пройдет в среднем через Nρ0 активных и N (1–ρ0) пассивных узлов.

Длительность цикла управления составит

T0 = Nρ0 (Tp + τ0′) + N (1 – ρ0) τ0.

За время цикла будет передано в среднем Nρ0 пакетов по b бит. Следовательно, средняя скорость передачи в среде

S =					Nρ0b					.
	Nρ	0	(T	p	+τ′ )+ N (1	−ρ	0	)τ	0
					0

Коэффициент использования среды в этом случае

η=		S		=		ρ0 (b / fd )					=
		fd			ρ0 (Tp +τ′0 )+(1−ρ0 )τ0
=						ρ0Tp			(1.1)
										.
		ρ	0	(T	p	+ τ′ )+(1−ρ	0	)τ	0
						0

Интенсивность обслуживания пакетов в некотором узле сети можно определить из следующих условий.

Для вычисления τ рассмотрим среднее время обслуживания одного пакета Ts . Оно включает следующие компоненты: среднее время передачи пакета Tp; среднеее время передачи управления от активного узла

τ′0 и среднеее время ожидания управления Tу Тогда

Ts =Tp +τ′0 +Ty .

Время ожидания управления зависит от скорости передачи управления через остальные (N–1) узлов сети, которая, в свою очередь, зависит от загрузки узлов сети ρ0 .

Среднее значение времени ожидания управления Ту будет
Ty =(N −1)ρ0 (Tp + τ′0 )+(N −1)(1−ρ0 )τ0 ,	(1.2)

где τ′0 – среднее время передачи управления от активного узла; τ0 – среднее время передачи управления от пассивного узла.

Среднее время задержки, выраженное в относительных величинах времени передачи пакета Tp:

32

	T			Tp + τ′0 +Ty		1 + τ′0 / Tp +Ty / Tp
τ =		s	=		=			.
	Tp (1	−ρ0 )		Tp (1 −ρ0 )			1 −ρ0

Подставляя в это выражение Ту из (1.2), получим
τ =1 + (N −1) ρ0 + (τ′0/Tp [(N – 1) ρ0 + 1] + (τ0/Tp ) (N – 1) (1 –ρ0 ) . (1.3)
1−ρ0		и τ′0 , кото-
Величины η и τ в выражениях (1.1) и (1.3) зависят от τ	0

рые, в свою очередь, определяются используемым методом доступа.

1.4. Эффективность маркерного доступа на структуре шина

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

Маркерный доступа при упорядоченном расположении узлов на структуре шина

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

а)					τΝ −1,0
			τ0,1			τ0,2
		0		1			2		N–1

τ2,3

б)

τ1,2

τ0,1

2			0	1	3

Рис. 1. 22. Последовательность передачи маркера при упорядоченном и произвольном расположении узлов

33

τn = N1 (τ0,1 +τ1,2 +... +τN −2, N −1 +τN −1,0 ).

Поскольку

τ0,1 + τ1,2 + … + τN–, 2 + τN–1, 0 = τm

и

τN–1,0 = τm,

то

τn = 2τm/N.

(1.4)

Следовательно,

τ0 = 2τm/N.

В этом случае среднее время передачи управления для активного и пассивного узла одинаково, т. е.

τ0 = τ′0.

Тогда выражения (1.1) и (1.3) будут

	η=		ρ0	;		(1.5)
			ρ0 +τ0 /Tp
τ =	1+ρ0	(N −1) +τ0 N /Tp			.	(1.6)
			1−ρ0

Вслучае упорядоченного расположения узлов на среде передачи,

т.е. в условиях, когда логическое кольцо передачи маркера соответ-

ствует физической последовательности подключения узлов к среде (см. рис. 22, а) значение τn может быть определено по формуле (1.4)

τn = 2τm/N.

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

Для рассматриваемого случая

τ0′ = 2τm/N + Tм.

C учетом этой величины и выражений (1.5) и (1. 6):

η=					ρ0					;
	ρ	0	+ 2τ	m	/(T	p	N ) +T	/T
								м	p

34

τ = 1+ρ0 (N −1) + 2τm / Tp + (Tм/Tp )N

.

1−ρ0

Маркерный доступ при произвольном расположении узлов на структуре шина

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

τn = τm/2 + Tм.

Следовательно,

τ0 = τm/2 + Tм.

С учетом этого выражения и выражений (1.5) и (1.6) получим

η=	ρ0	;
	ρ0 + τm /(2Tp ) +Tм/Tp

τ= 1+ρ0 (N −1) + N (τm /(2Tp ) +Tм/Tp ) .

1−ρ0

1.5.Эффективность маркерных способов доступа

на структуре кольцо

Маркерный доступ при упорядоченном расположении узлов на структуре кольцо

В этом случае τ0 = τ0′ и τn = τm/N .

При оценке T будем считать, что это время равно времени передачи маркера Тм ,т. е.

Т = Tм.

Следовательно,

τ0 = τm / N + Tм. Из выражений (1.5) и (1.6) получим

η=	ρ0	;
	ρ0 + τm /(Tp N ) +Tм/Tp

τ = 1+ρ0 (N −1) + τm / Tp + (Tм N )/Tp . 1−ρ0

35

Таким образом, получены выражения для η и τ для рассматриваемого случая.

Маркерный доступ при произвольном расположении узлов на структуре кольцо

Здесь среднее время распространения между парой узлов

τn = τm/2 + Tм.

Следовательно,

τ0 = τm/2 + Tм.

Аналогично маркерному доступу при произвольном расположении узлов на структуре шина из выражений (1.5) и (1.6) имеем

			η =	ρ0		;
				ρ0 + τm /(2Tp ) +Tм/Tp
τ =	1		+ρ0 (N −1) + τm /(2Tp ) + (Tм			/Tp )N
							.
				1−ρ0
Итак, выведены выражения для η и τ.

1.6. Анализ эффективности маркерных способов доступа при групповой передаче пакетов

Внекоторых случаях целесообразно передаваемые пакеты объединять в группы и передавать такие группы целиком. Пусть каждая такая группа содержит k (k = 1, 2, …) пакетов. Таким образом, k – число пакетов (размер) в группе.

Вкачестве математической модели сети с таким функционированием может быть использована одноканальная система массового обслуживания (СМО) с очередями, которые взаимодействуют с обслуживающим прибором (ОП) в циклическом порядке.

Предположим, что длина очередей не ограничена, а система симметрична. Пусть время, необходимое на переключение ОП от i-й к (i + 1)-й

очереди, постоянно и равно .

Предположим, что поток пакетов, поступающий в каждую очередь, является пуассоновским с интенсивностью λ0, время обслуживания пакета постоянно и равно Tp и обслуживание каждой очереди осуществляется по k пакетов.

В этом случае локальная сеть может быть представлена СМО с эрланговскими входными потоками k-го порядка с интенсивностями 36

λ0* = λ0/k

и временем обслуживания

T* = k T.

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

Рассмотрим статистические характеристики длительности интервала обращения.

Пусть E[To] – среднее значение интервала ОП к произвольной очереди. Тогда загрузка произвольной очереди

ρ = λ0* E[T0].

Для существования стационарной системы необходимо, чтобы выполнялось условие ρ < 1.

При ρ → 1 длительность интервала обращения становится детерминированной величиной

T0 = N (T* + ),

поскольку в этом случае число очередей, где имеются пакеты для передачи, стремится к N.

Таким образом, условие, что система находится в стационарном режиме

λ0* N(T* + ) < 1.

(1.7)

При выполнении условия (1.7) каждая очередь на интервале обращения с вероятностью ρ находится в активном состоянии, т. е. имеет пакеты для передачи, и с вероятностью (1 – ρ) является пассивной, т. е. не имеет пакетов для передачи.

Вероятность того, что за один интервал обращения будет обслужено ровно l очередей (l = 1, …, N):

Pl (T0 ) =CNl	ρl (1 −ρ)N −1 ,		(1.8)
где СlN – биномиальный коэффициент. При этом
CNl =	N !	.
	(N −l)!l

37

Среднее число E[l] обслуженных очередей за интервал обращения

N

E[l] = ∑lPl (T0 ) = Nρ.

l=0

Среднее значение длительности интервала обращения

E[T0] = N (Δ) +E[l]T* = N			+ NρT* = N + Nλ0* E[T0].
Следовательно,
E[T ]		=	N				,
0		1− Nλ0Tp
ρ =		λ0 N				.
	k(1− Nλ T			p	)
		0

(1.9)

(1.10)

2

третий

3

моменты распределения длительнос-

Второй E T0

,

E T0

ти интервала обращения и дисперсия D[T0] соответственно равны

2

N

2

= ∑(N

+lT

2

Pl(T0 )

= Nρ(1 −

ρ)T

+(N

+ NρT

2

E T0

)

)

,

l=0

3

N

+lT

3

Pl (T0 ) =

3

+

)

(NΔ)

E T0

= ∑(N

l=0

+3(NΔ)2T Nρ +3NΔT2[N(N −1)ρ2 + Nρ] +

+T 3[N(N −1)(N −2)ρ3 +3N(N −1)ρ2 + Nρ],

(1.11)

D[T0 ]− E T02 −(E T02 )2 = Nρ (1−ρ)T 2.

Рассмотрим среднее время задержки передачи группы пакетов. Произвольная очередь может быть описана тактированной систе-

мой типа G/GT/1 .

Для нетактированной системы G/G/1 известна аппроксимация для среднего времени ожидания

	E[W ] = E[t		]	ρ	(C2	+С2 )ξ,
		0		2(1−ρ )			(1.12)
					В	0

38

где

				1−C			2
	2(1−ρ	)					В
ξ = exp −			×						,
				C	2	+C		2
	3ρ				В			0

E[t0] – математическое ожидание времени обслуживания заявки; ρ* – статистическая загрузка очереди; C02 – квадратичный коэффициент ва-

риации времени обслуживания заявок; CВ2 – квадратичный коэффициент вариации входного потока заявок. При этом

ρ* = λ*E[t0];

С2	=	D[t0 ]	,
0		(E[t0 ])2

где D[t0] – дисперсия времени обслуживания. Для потока Эрланга k-го порядка

CВ2 =1/ k.

Для k = 1 коэффициент CВ2 =1 (пуассоновский входной поток), а величина ξ в выражении (1.12) становится равной 1.

Для экспоненциального распределения длительности обслуживания C02 = 1. При пуассоновском входном потоке (k = 1) и экспоненциальном

распределении длительности обслуживания (С02 =1) выражение (1.12) примет вид

E[W ]= E[t0 ](1−ρρ) ,

а при тех же условиях, но при постоянной длительности обслуживания(C02 =1)

E[W ] = E[t0 ]		ρ	.
		2(1−ρ)
Таким образом, при k = 1	выражение (1.12) сводится к формуле Пол-
лачека-Хинчина для систем	M/M/1 и M/D/1 соответственно.

39

Заявка, поступающая в тактированную систему массового обслуживания СМО G/GT/1 в произвольный момент времени, ожидает в течение времени τ до начала очередного обращения ОП к очереди. При этом

E[τ] = E[T02 ] ; 2E[T0 ]

E[τ2 ] = E[T03] ; 3E[T0 ]

D[τ] = E[τ2] – (E[τ])2.

При поступлении заявки в пустую очередь тактированной СМО G/GT/1 (вероятность этого 1–ρ) она ожидает начала обслуживания в течение времени τ, после чего обслуживается. Для эквивалентной нетактированной СМО G/G/1 математическое ожидание времени обслуживания E[τ] + T*, а дисперсия D[τ].

Если заявки поступают в непустую очередь тактированной системы G/GT/1 (вероятность этого ρ), то после обслуживания стоящих впереди заявок она ожидает начала своего обслуживания в течение времени T0. Для эквивалентной нетактированной СМО G/G/1 среднее значение времени обслуживания заявки E[T0] + T*, а дисперсия D[T0].

Окончательно получаем

E[t ] = (1– ρ)(E[τ] + T*) + ρ(E[T ] + T*);
0	0
	D[t0] = (1–ρ)D[τ] + ρD[T0].	(1.13)

Подставляя выражения (1.13) в формулу (1.12), получим среднее время ожидания заявок в очереди E[W].

Среднее время задержки заявок в системе E[D] (время пребывания заявок в системе)

E[D] = E[W] + E[t0].

(1.14)

Таким образом, формула (1.12) определяет среднее значение времени ожидания, а формула (1.14) – среднее значение задержки группы пакетов в системе с циклической дисциплиной обслуживания.

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

40