Сети связи и системы коммутации

Глава 3. Введение в теорию телетрафика

91

Распределение состояний занятости полнодоступного пучка

Сравнительный анализ соотношений (4), (8), (12) и (16) позволяет сделать вывод о том, что распределения Эрланга, Энгсета, биномиальное и пуассоновское связаны друг с другом посредством определенных зависимостей (рис. 3.5).

Еиномиальное	Пуассоновское
распределение	распределение

	Nконечно
Распределение	Распределение
Энгсета	Эрланга

Рис. 3.5 — Законы распределения состояний занятости полнодоступного пучка линий

3.4.5. Система с ожиданием

Общие положения

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

•коммутацию сообщений;

•коммутацию пакетов;

•статистическое уплотнение с временным разделением каналов;

•многопунктовую передачу данных;

•автоматическое распределение вызовов (АРВ);

•доступ к приемникам набора номера в АТС;

•обработку требований на установление соединений

èò.ä.

92	В.М. Винокуров. Сети связи и системы коммутации

Перечислим основные допущения, принятые при анализе СМО с ожиданием.

1.Величина поступающего телетрафика должна быть меньше числа обслуживающих приборов (A < N).

2.Как правило, вся поступающая нагрузка обслуживается системой (A = Y); уменьшение нагрузки (Y < A) может быть обусловлено либо конеч- ным объемом памяти для хранения требований, либо добровольным снятием требований «уставшими» абонентами.

3.Число источников в системе предполагается бесконечно большим (Ì → ∞).

4.В системе без потерь при Ì → ∞ очередь теоретически должна быть бесконечно длинной, но на практике реализуются лишь конечные очереди.

5.Общее время пребывания требования в системе подразделяется на

время ожидания tw è длительность обслуживания. Под длительностью обслуживания здесь понимают среднее время занятия tñð, принятое при анализе систем с потерями.

6.Работа системы зависит от распределения длительности обслуживания. Реальные системы функционируют с некоторым промежуточным распределением между детерминированным и случайным законами. В качестве детерминированного закона принято постоянное распределение длительности обслуживания, а в качестве случайного — экспоненциальное.

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

• по принципу «первым пришел, первым обслужен» (FIFO);

• циклический опрос источников — очередь обслуживается в порядке последовательности появления ожидающих вызовов;

• случайный выбор ожидающих вызовов;

• выбор согласно дисциплине приоритетов.

Основной целью анализа СМО с ожиданием является определение распределения вероятностей времени ожидания и на его основе нахождение величины среднего времени ожидания, а также вероятности того, что это время превысит некоторое заданное значение.

Классификация Д.Г. Кендалла

Для упрощения описания конкретных систем Д.Й. Кендаллом был предложен классификатор, составленный из буквенных сокращений, характеризующих различные свойства параметров СМО (рис. 3.6).

При описании систем, содержащих либо неограниченную длину очереди (последняя позиция классификатора), либо неограниченные длину очереди и число источников (две последние позиции классификатора), указанные позиции классификатора обычно исключают. Примером сокращенного формата может послужить описание трафика в шине Ethernet вида M/M/1, что означает систему с пуассоновским входным потоком, отрицательным экспоненциальным распределением времени ожидания и одним обслуживающим прибором.

Глава 3. Введение в теорию телетрафика				93
парактеристики входящего			G: Распределение общего вида (произвольное)
потока		М: Пуассоновское распределение
Распределение времени			G: Распределение общего вида (произвольное)
обслуживания			M: Отрицательное экспоненциальное распределение
			D: Постоянное время обслуживания
Число обслуживающих
приборов			N: Ограниченное число
Число			M: Ограниченное число
источников			Неограниченное число
Длина очереди			L: Ограниченная длина
			Неограниченная длина

1/2/3/4/5/

Рис. 3.6 — Обозначения, принятые в СМО с ожиданием

Модель Эрланга Ì /Ì /N

Примем следующие исходные допущения:

1)коммутационное устройство имеет N линий и полнодоступно;

2)пуассоновский поток требований с интенсивностью λ;

3)длительности занятий распределены экспоненциально со средним вре-

менем tñð;

4)ожидающие требования обслуживаются в порядке поступления (дисциплина FIFO);

5)À < N, чтобы очередь не росла до бесконечности.

При принятых допущениях исходные данные по аналогии с моделью Эрланга для системы с потерями приобретают вид:

1)õ = 0, 1, 2, …, N, N+1, …, ∞;

2)åñëè õ < N, то занято õ линий, но очереди ожидания нет;

3)åñëè õ ≥ N, то занято N линий и (õ−N) заявок находятся в очереди ожидания;

4)интенсивности:

λx = A + x, 0 ≤ x ≤ N − 1;		(18)
λx = A + N, x ≥ N;

5) вероятности переходов системы из состояния z в другие состояния:

P (z, z + 1) = A λZ , 0 ≤ z ≤ N;
P (z, z − 1) = z λZ ,		(19)
	0 ≤ z ≤ N;
P (z, x) = 0, z > N;

94	В.М. Винокуров. Сети связи и системы коммутации
6) системы линейных уравнений состояний занятости:
λ	x	Q(x) =	∑	λ	zi	P	( i	)	Q	( i )	z Z;
							z ,x			z ,

∑Q(x) = 1; x Z.

Найдем решения системы уравнений состояний занятости для различ- ных областей существования переменной õ.

1. Для области 0 ≤ x < N.

z1 = x − 1; λZ1 = A + x − 1; P (z1,x) = P (x − 1,x) = AλZ1 ;

z2 = x + 1; λZ2 = A + x + 1; P (z2,x) = P (x + 1,x) = z2 λZ2 .

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

(A + x) Q(x) = A Q(x − 1) + (x + 1) Q(x + 1), дающую для различных õ:

AQ(0) = Q(1); x = 0;

(A + 1)Q(1) = AQ(0) + 2Q(2) èëè AQ(1) = 2Q(2); x = 1; (A + 2)Q(2) = AQ(1) + 3Q(3) èëè AQ(2) = 3Q(3); x = 2;

(A + N −1)Q(N −1) = AQ(N −2) + NQ(N) èëè AQ(N −1) = NQ(N);

x = N −1.

(20) Результатом такого представления, во-первых, служит значительное упрощение исходного рекуррентного соотношения AQ(x) = xQ(x + 1); во-вто- рых, появляется возможность записать общую формулу для любого 0 ≤ õ < N:

	Q(x) =	Ax	Q(0);	(21)
		x !

в-третьих, найденная рекуррентность позволяет распространить результат на случай x = N, что следует из выражения (20):

	Q(N) =	A	Q(N − 1)	=	AN	Q(0).	(22)
		N			N !

2. Для области õ ≥ N.

Справедливо равенство λõ = À + N, что позволяет определить переходные вероятности:

z1 = x − 1; λZ1 = A + N; P (z1,x) = P (x − 1,x) = AλZ1 ;

z2 = x + 1; λZ2 = A + N; P (z2,x) = P (x + 1,x) = NλZ2 .

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

(A + N) Q(x) = AQ(x + 1) + NQ(x + 1),

упрощаемое до формы

AQ(x) = NQ(x + 1)

и позволяющее записать общую формулу вероятности состояния занятости в виде

Q(x) = (A N)x−N Q(N),	(23)
ãäå Q(N) = (AN N !)Q(0).

Глава 3. Введение в теорию телетрафика

95

Таким образом, единственной неизвестной величиной в формулах (21) и (23) остается величина Q(0), найти которую позволяет условие нормировки

∞

N

Ax

∞

A x−N

AN

∑ Q(x) = 1 = ∑

Q(0)

+

∑

Q(0) =

x=0

x=0

x !

x=N +1

N

N

N

Ax

AN ∞

A

x

N

Ax

AN +1

= Q(0)

∑

+

∑

= Q(0)

∑

+

.

x !

x !

N !(N −

x=0

N ! x=N +1

N

x=0

A)

Последнее равенство позволяет записать результат в виде

N

Ax

AN +1

−1

Q(0) =

∑

+

.

(24)

x=0 x !

N !(N − A)

Таким образом, формулы (21), (23) и (24) полностью описывают вероятность состояния занятости в системе с ожиданием.

Однако полученный результат мало пригоден на практике. Для системы с очередями определяюшую роль играет не столько знание вероятности состояния, сколько знание времени ожидания. Среднее время ожидания может быть определено как математическое ожидание случайной величины «время ожидания t»:

		∞
		w = ∫tW(t)dt,	(25)
	t
0

ãäå W(t) — плотность вероятности случайной величины t. Задача сводится

êпоискам закона распределения времени ожидания в системе.

Âтеории очередей этот закон определяется в нестандартной, дополняющей, форме

P (> t) = 1 − F(t),

(26)

ãäå P(> t) — вероятность того, что поступившее требование будет ожидать

t

обслуживания в течение времени, большего величины t; F(t) = ∫ W(t)dt —

−∞

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

Распределение (26) может быть получено по формуле полной вероятности для любого возникающего требования

∞
P(> t) = ∑ Q(x)Px (> t),	(27)

x=N

x−N

ãäå Px (> t) = ∑ Pk (λ′t).

k=0

Величина Px(> t) имеет смысл условной вероятности того, что время ожидания обслуживания для некоторого требования с порядковым номером (x + 1) окажется больше величины t при условии, что требование застает при своем появлении õ ≥ N более ранних, а следовательно, более приоритетных вызовов, (õ − N) из которых организованы в очередь с дисциплиной FIFO.

Здесь величина Pk(λ′t) означает вероятность того, что за время t завершатся k вызовов (сеансов связи):

96	В.М. Винокуров. Сети связи и системы коммутации
	Pk (λ′t) = (λt)e		,	(28)
	′ k	−λt

k !

ãäå λ′ = Ntñð — частота обслуживания требований пуассоновского входного потока в системе с ожиданием при полностью задействованной емкости пуч- ка ЭСЛ (õ ≥ N).

Производя элементарные действия над выражением (27) по перестановке операций суммирования и уточнению их пределов, приходим к следующему результату:

∞	x−N	∞			∞
P(> t) = ∑	Q(x) ∑ Pk (λ′t) = ∑ Pk (λ′t) ∑ Q(x).
x=N	k=0	k=0		x=N +k
После подстановки соотношений (23) и (28) в полученный результат фор-
мула для вычисления параметра P(> t) приобретает вид
	∞	(λ′t)k ∞		A x−N
P(> t) = Q(N)e−λ′t ∑		∑			.
	k=0	k ! x=N		N

Свертывая бесконечно убывающую геометрическую прогрессию и учи- тывая ранее введенное обозначение λ′ = N tñð , окончательно приходим к соотношению

				−	N −A t
				P(> t) = P(> 0) e	tñð ,	(29)
	ãäå P(> 0) =	N		Q(N) — вероятность ожидания (вероятность наличия оче-
		N −	A

реди на обслуживание); P(> t) — вероятность того, что время ожидания в очереди превысит величину t.

Вероятность P(> 0) представляет собой весьма важный параметр, характеризующий систему с ожиданием. С учетом соотношений (23) и (24) формула для вычисления P(> 0) принимает вид, известный в теории телетрафика как вторая формула Эрланга, или С-формула Эрланга:

P(> 0) = E2,N (A) = C =	N E1,N (A)			,	(30)
		− E1,N
	N − A 1		(A)

ãäå Å1,N(A) — первая формула Эрланга для системы с потерями (9), так называемая В-формула.

Формула (30) иллюстрирует классическое определение вероятности события «наличие очереди». Определение соответствует модели системы с потерями, адекватной системе с ожиданием по основным параметрам, но без оче- редей. В такой системе при величине поступающей нагрузки À и емкости пучка ЭСЛ коммутационной системы, равной N, имеется вероятность блокировки величиной Â = Å1,N(A). Обслуженный трафик подсчитывается по формуле Y = A (1 − B). Максимальный поток, который может обслужить коммутационная система из N ЭСЛ, равен N Ýðë.

Наличие в системе очереди означает априори, что емкость коммутационной системы уже использована максимально. В таком случае очередь формируется за счет избыточного потока, равного (NB). Эта величина дает количе- ство, благоприятное событию «наличие очереди» (числитель формулы (30)). Общее же количество возможных случаев, когда при максимальной загрузке очередь может либо быть, либо нет, определяется величиной разности между максимально возможным и реальным потоками (N − Y) (знаменатель форму-

Глава 3. Введение в теорию телетрафика

97

лы (30)). Легко видеть, что при N = A вероятность возникновения очереди равна ста процентам: Ð(> 0) = 1.

Уравнение (29) определяет вероятность того, что вызов, поступающий в случайно выбранный момент времени, ожидает не более t/tñð длительностей обслуживания. На рис. 3.7 представлено соотношение (29) в виде пропускной способности различного числа обслуживающих устройств как функции допустимого времени ожидания. Для заданной нормы времени ожидания t/tñð (ðèñ. 3.7,à) интенсивность нагрузки максимальна, если норма ожидания будет превышена только для 10 % поступающих вызовов. Аналогично интенсивность нагрузки максимальна, если норма ожидания оказывается превышенной только для 1 % поступающих вызовов (рис. 3.7,á). Заметим, что при ð(> 0) = 0,01 системы обслуживания не достигают своей максимальной пропускной способности, если только допустимое время ожидания не оказывается в несколько раз большим, чем tñð.

Ýðë	8	N=10		9		8
	7
способность,	6						7
	5						6
							5
	4
								4
	3
Пропускная								3
	2
								2
	1							1
		0	0,5	1,0	1,5	2,0	2,5	3,0
					t/tm
					à
Ýðë	8		N=10
	7				9
способность,						8
	6
							7
	5						6
	4							5
								4
Пропускная	3
	2							3
	1							2
		0	0,5	1,0	1,5	2,0	2,5	3,0
					t/tm
					á
Рис. 3.7 — Пропускная способность системы с ожиданием
с несколькими обслуживающими приборами в случае
экспоненциального распределения длительности обслуживания [25]:
à — вероятность ожидания свыше времени t, p(>t)=10 %;
á — вероятность ожидания свыше времени t, p(>t)=1 %

98	В.М. Винокуров. Сети связи и системы коммутации

Согласно формулам (26) и (29), распределение времени ожидания приобретает вид

		−	N −A		t, t > 0;
F(t) = 1 − P(> 0) e			tcp
						N −A		(31)
	P(> 0)(N	− A)			−		t
						tcp
W(t) =				e			, t > 0.
	tcp

Таким образом, распределение времени ожидания имеет форму, близкую к классической экспоненциальной W(t) = αe−αt c интенсивностью, рав-

íîé (N − A) tñð .

Среднее время ожидания определим по формуле (25):

		∞	P(> 0)(N − A)	−	N −A	t	P(> 0)tcp
					t
	tw = ∫t			e		dt =		.	(32)
					cp
			tcp				N − A
	0

Величину tw = tcp/(N−A), входящую в формулы (31) и (32), можно трактовать как среднее время пребывания заявок в очереди при усреднении только среди заявок, находящихся в очереди.

В свою очередь, величина tw предполагает усреднение среди полного ансамбля заявок: tw = P(> 0)tw, ãäå

t =

tcp

.

(33)

w	N − A

Выражение (33) иллюстрируется рис. 3.8.

A Ýðë	F.I.F.O.	N Ýðë
		N ýñë

Рис. 3.8 — Модель-иллюстрация соотношения (33)

Для лучшего понимания смысла введенных параметров проанализируем формулу (33). Для этого найдем величину, обратную tw:

1	=	N	−	A	.	(33à)
t		t
				t
w		cp		cp

Нетрудно заметить, что данное равенство интерпретируется как комбинация трех интенсивностей:

• частоты поступления вызовов — λ = A ;

tcp

• частоты рассасывания очереди — λw = 1 ; tw

• частоты обслуживания — λ′ = N = λ + λw .

tcp

Введенные обозначения позволяют переписать выражение (33а) в виде

λw = λ′ − λ èëè λ′ = λ + λw.

Глава 3. Введение в теорию телетрафика

99

Умножая обе части полученного равенства на tw , получим:

λ′tw = λtw + λwtw.

Величину λtw называют емкостью накопителя вызовов, или средней длиной очереди:

	l = λ			= λtwP(> 0) =	Atw	P(> 0).	(34)
		tw
					tcp

Слагаемое λwtw равно вероятности ожидания Ð(> 0):

λ			=	twP(> 0)	= P(> 0).	(35)
		t
	w w			tw

Таким образом, выполняется соотношение

λ′			(36)
	tw = P(> 0) + l.

Среднее время пребывания требования в системе легко вычислить, суммируя время ожидания tw и среднее время обслуживания tcp:

						P(> 0)
tnp	= tw + tcp			= tcp 1	+	N − A	.	(37)

Среднее число требований, находящихся в системе, вычисляется по теореме Литтла и равно сумме поступающего телетрафика и средней длины оче- реди:

ms = λtnp = l + A.

(38)

В случае наличия в системе единственного обслуживающего прибора (N = 1; однолинейная СМО) имеют место следующие соотношения:

E

(A) =

A

, P(> 0) = A, l =

A2

,

1,1

1+ A

1− A

=t

A

t =

tcp

m =

A

t

,

,

.

− A

1− A

1− A

w

cp 1

np

s

Контрольные вопросы

1.Закончите фразу: «Входной поток требований в теории телетрафика задается статистическим распределением…».

2.Сколько обслуживающих приборов входят в состав коммутатора двухфазной трехлинейной СМО?

3.Что такое блокировка вызова в ТФОП: неисправность абонентской линии; неисправность магистральной линии; нехватка ресурса коммутационной станции или неисправность коммутационной системы?

4.Что означает на практике наличие свойства одинарности входного потока: а) вызовы идут по единственной абонентской линии; б) вызовы поступают на коммутатор последовательно, один за другим; в) речь идет о единственном абоненте сети; г) два и более вызовов не могут прийти одновременно на коммутатор?

5.Что на практике означает равенство величины телетрафика одному Эрлангу: а) терминал одного абонента активен в среднем в течение всех 24 часов времени суток; б) терминал одного среднестатистического абонента

100	В.М. Винокуров. Сети связи и системы коммутации

активен в течение всех 24 часов времени произвольно взятых суток; в) терминал одного среднестатистического абонента активен в течение 60 минут часа наибольшей нагрузки; г) терминал одного среднестатистического абонента сохраняет свою активность непрерывно за все время наблюдения?

6.Какое из приведенных ниже утверждений отвечает концепци статистического равновесия СМО с потерями по А.К. Эрлангу: а) пропускная способность СМО равна поступающему телетрафику À; б) СМО стремится к

наиболее вероятному состоянию, когда занято À = λtñð эквивалентных соединительных линий; в) вероятность блокировки СМО с потерями равна величи- не «опасного времени»?

7.Укажите в приведенном списке правильный классификатор по А.Й. Кендаллу для описания трафика в шине Ethеrnet: M/D/1; G/M/N; M/M/1; M/M/N/M.

8.Какова дисциплина обслуживания очереди в модели Эрланга M/M/N: LIFO; FILO; FIFO или LILO?

9.Укажите, чему равно среднее число требований, одновременно находящихся в системе с очередями M/M/N: а) величине поступающего телетрафика; сумме поступающего телетрафика и средней длины очереди; б) сумме поступающего телетрафика и потока требований, покидающих очередь за время ожидания.

10.Укажите, чему равна вероятность блокировки вызовов в СМО с конечным числом абонентов: а) величине опасного времени G(N) в системе

ñзаданным конечным числом абонентов; б) величине опасного времени G(N) в системе с числом источников, увеличенном на единицу; в) величине опасного времени G(N) в системе с числом источников, уменьшенном на единицу.

11.Чему равна максимальная величина телетрафика в Эрлангах для СМО с явными потерями, порожденного Ì абонентами, при ресурсе коммутационной сети, равном N?

12.Какой результат следует ожидать от СМО с очередями, если величи- на поступающего телетрафика превышает ресурс коммутационной системы: а) прекращение работы системы вследствие недопустимо большой величины вероятности блокировки вызовов; б) очередь бесконечной длины; в) нормальное функционирование системы с блокировкой излишнего трафика?