СМО с непуассоновскими потоками

5.1. Особенности мультисервисного трафика

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

Любой пакетный трафик является продуктом компьютерной обработки, выполняемой процессором при решении задач приложений. Решение любой задачи состоит из трех последовательных этапов: получение исходных данных, процесс обработки и процесс выдачи результатов, причем, трафик образуется именно на третьем этапе. Это и обуславливает его пачечный характер. На структуру трафика оказывают влияние и особенности применяемых алгоритмов обслуживания. Например, моменты возникновения запросов на обслуживание сильно коррелированны, если в используемых протоколах применяется повторная передача ошибочно принятых пакетов. Все это приводит к тому, что для мультисервисных потоков характерна неравномерность поступления заявок и пакетов. Пакеты группируются в «пачки» в одних промежутках времени и практически отсутствуют – в других промежутках. Случайный процесс поступления заявок(пакетов) в систему характеризуется законом распределения, устанавливающим связь между значениями случайной величины и вероятностями появления указанных значений. В большинстве случаев, такой поток характеризуется функцией распределения временных интервалов между соседними заявками. Имеется также множество работ, в которых потоки заявок характеризуются функцией распределения числа заявок за условную единицу времени.

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

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

1. В большинстве случаев для характеристики числа заявок, поступающих за некоторый интервал времени, используется «нормальный» закон распределения.

Однако, исследования показали, что для мультисервисного трафика аппроксимация «нормальным» законом распределения не согласуется с действительностью.

Реальные распределения обладают существенной асимметрией, в то время, как «нормальный» закон предполагает симметричное распределение.

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

3. Большая «пачечность» потока приводит к появлению значительного числа интервалов, в течение которых заявки вообще не поступают. Именно эта весьма высокая вероятность «нулевого состояния» приводит к отличию реального закона распределения от «нормального».

4. Характер закона распределения числа заявок, поступающих за некоторый интервал времени t существенно зависит от величины указанного интервала.

5.2. Непуассоновские потоки

Рассмотрим понятие образующей функции.

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

(5.1)

Указанная функция определяет вероятности P(J£t) того, что J£t. Эту функцию распределения вероятностей назовем образующей функцией.

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

(5.2)

Это есть функции попадания некоторого числа событий в интервал t, где под интервалом t мы понимаем постоянное время обработки одной заявки, а отсчет времени начинается в момент появления первой заявки (рис. 5.1).

Рис. 5.1. Образующие функции.

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

Обозначим через P_i(t) вероятность того, что на интервале t появится ровно i заявок.

Тогда, функция 1-F₁(t)=P(J₁>t)=P₀(t) определяет вероятность отсутствия заявок на интервале t (не считая исходной). Это равносильно утверждению, что на указанном интервале появится не более 0 заявок.

Аналогично, функция (5.3) определяет вероятность того, что на интервале появится не более, чем n-1 заявок.

(5.3)

Очевидно, что разность F_i(t)-F_i+1(t)=P_i(t), а сумма всех вероятностей равна единице (5.4).

.

(5.4)

5.3. Функция Г-распределения

интервалов между заявками

Мы предлагаем аппроксимировать семейства образующих функций семейством функций Г-распределения.

Функция Г-распределения хорошо известна. Она определяется двумя параметрами:– средний интервал времени между двумя соседними заявками поступления заявок , и η – величина, обратная квадрату коэффициента вариации распределения интервалов между заявками (5.5). Кроме того, используется параметр средней интенсивности (5.6).

,	(5.5)
.	(5.6)

(5.7)

Почему такая функция была выбрана? Во-первых, потому, что экспоненциальное распределение является частным случаем Г-распределения (при η=1). Главное же заключается в том, что функция F_n(t) получается из функции F₁(t) (5.7) простым умножением показателя η на величину n. Действительно, исходное выражение для функции (5.8) с учетом (5.9), примет вид (5.10).

	(5.8)
; ;	(5.9)
.	(5.10)

Введем переменную x=h·t и получим окончательно формулу (5.11).

(5.11)

Такая аппроксимация позволяет анализировать уже не только экспоненциальные входные потоки, но и потоки, с самыми различными коэффициентами вариации интервалов.

На рис. 5.2 показано семейство функций распределения вероятностей при различных значениях коэффициента η (η – величина, обратная квадрату коэффициента вариации v²).

Рис. 5.2. Семейство образующих функций F(λτ).

Чем меньше коэффициент η, т. е. чем больше его обратная величина – коэффициент вариации, тем круче идут графики указанных функций. Все они, так же, как и экспоненциальное распределение, описываются единым уравнением.

Зная эти функции, мы легко можем вычислять вероятности появления n событий на интервале τ (5.12) и (5.13).

	(5.12)
	(5.13)

При экспоненциальном распределении (коэффициент η=1) получаем закон Пуассона в его обычном виде.

Стало быть, указанное соотношение это в интегральной форме обобщенный закон Пуассона, где мы получаем вероятность появления n событий на интервале τ при заданных значениях параметров Г-распределения.

Рис. 5.3. Вероятности P_n для различных η.

На рис. 5.3 показаны вероятности попадания n – событий в узкий временной интервал, соответствующий выражению (5.14).

.

(5.14)

Для экспоненциального потока (η=1) вероятность попадания двух или более событии в указанный интервал крайне мала. В то же время, вероятность попадания двух событии для потока с коэффициентом вариации =5 (η=0.2) значительно выше, и соответствует 0.2. Это может вызвать появление очередей.

На рис. 5.4 показаны графики очередей q(t), в зависимости от коэффициента загрузки lt для различных значений коэффициентов вариации потоков, имеющих Г- распределение интервалов между заявками.

Рис. 5.4. Очереди.

Мы видим, что при экспоненциальном входном потоке существенное возрастание очереди происходит при коэффициенте загрузки, равном 0.9, в то время, как для потока v²=5, аналогичного значения длина очереди достигает уже при коэффициенте загрузки λτ = 0.1.

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

5.4. Квазипуассоновское распределение вероятностей числа заявок

Рассмотренное выше соотношение (5.13) устанавливает вероятности появления заданного числа n заявок на интервале t, при Г-распределении интервалов между соседними заявками.

Рассмотрим случайную величину v=n·h. Ее функция распределения описывается выражением (5.15)

(5.15)

Допустим, что случайная величина v может принимать только целочисленные значения (0,1,2…), тогда вероятность появления заданного числа n заявок на интервале t примет вид (5.16).

(5.16)

Учитывая выражения (5.16), (5.17) и (5.18) получим закон Пуассона для целых v (5.19).

,	(5.17)
	(5.18)
	(5.19)

После подстановки значений , получим формулу (5.20).

, где , v =0, 1, 2,…

(5.20)

Указанный закон распределения вероятностей, подчиняющийся (5.20), назовем квазипуассоноаским.

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

В общем случае, на указанном интервале может разместиться не целое число интервалов J_j между заявками, поэтому, представим величину n_i в виде суммы целой и дробной частей (5.21).

, где vi = 0, 1, 2… и 0£ ei £1.

(5.21)

Если τ < J_i, то целая часть v_i =0.

Если τ ³ J_i то целая часть, т.е. v_i, определяется из целочисленного уравнения (5.22).

(5.22)

Дробная часть e_i показывает долю от интервала J_i+vi, которую составляет остаток.

Таким образом, становится ясным физический смысл не целых значений n.

Напомним, что h есть величина, обратная коэффициенту вариации интервалов между соседними заявками исходного потока, при Г- распределении интервалов, которая может принимать любые значения. В частном случае, при экспоненциальном распределении интервалов, h=1, мы приходим к закону Пуассона в его обычном виде (5.23).

.

(5.23)

Следовательно, (5.20) обобщает закон Пуассона на не экспоненциальные потоки, заданные Г- распределением интервалов между заявками, с произвольным коэффициентом вариации.

5.5. Г- распределение вероятностей числа заявок на интервале t

Предлагается плотность распределения W_m(t) - вероятностей числа заявок на интервале t представить в виде - распределения (5.24).

,

(5.24)

где: , а и D_m(t) -математическое ожидание и дисперсия числа заявок на интервале t, соответственно.

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

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

Вероятности P_m(t) поступления целых чисел заявок определяются соотношением (5.25)

, m =1, 2, 3…

(5.25)

Предположим, что суммарный поток включает в себя K потоков различной активности. Допустим, что периоды активности потоков различного вида не пересекаются. Поток k -го вида характеризуется распределением вероятностей P_kn(t) числа заявок n, поступающих в течение интервалов t. ( Это условные распределения вероятностей, полученные при условии, что рассматриваются периоды, соответствующие потоку k -го вида).

Поток каждого k -го вида присутствует в течение суммарного времени T_k.

,

(5.26)

где T - весь исследуемый промежуток времени.

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

k=1

(5.27)

5.6. Гиперпуассоновское распределение вероятностей числа заявок на интервале t

Предположим, что составляющие потоки k -го вида характеризуются квазипуассоновскими распределениями числа заявок, соответствующими (5.13). Тогда выражение (5.28) назовем гиперпуассоновский распределением.

		(5.28)
k=1

Наиболее простой формулой гиперпуассоновского распределения является распределение второго порядка (k=2). Оно имеет 5 независимых параметров.

(5.29)

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

Квазипуассоновское распределение заявок на интервалах занятости можно рассматривать как условное, при условии, что прибор обслуживания находится в состоянии занятости. Вероятность этого состояния определяется коэффициентом загрузки r. Вероятность состояния простоя равна (1-r). В состоянии простоя заявки на вход не поступают.

Мы получили гиперпуассоновское распределение второго порядка, где P₁ =(1-r), а условное распределение вероятностей числа заявок на интервале простоя является вырожденным (5.30)

, где

(5.30)

Обозначим через P_n2(t) - условное квазипуассоновское распределение вероятностей случайной величины n на фазе занятости. Тогда общее распределение вероятностей, с учетом наличия интервалов простоя, определится соотношением (5.31)

,

(5.31)

Не трудно показать, что сумма значений всех вероятностей равна единице (5.32).

,

(5.32)

Подставляя значения из (5.20), получим.

,

(5.33)

Соотношение (5.33) предполагает наличие Г- распределения интервалов между заявками на интервалах занятости и учитывает наличие интервалов простоя, когда заявки в систему не поступают.

5.7. Гипер Г- распределение вероятностей числа заявок на интервале t

Предположим, что составляющие потоки k -го вида характеризуются независимыми Г- распределениями числа заявок, соответствующими (5.5). Тогда:

.

(5.34)

Не трудно показать, что для такого распределения выполняются соотношения (5.35).

;	(5.35)
.

Наиболее простой формулой гипер Г- распределения является распределение второго порядка (k=2).

m = 0, 1, 2…

(5.36)

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

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

Такому режиму соответствуют малые значения математического ожидания числа пакетов , поступающих в течение интервала t, малые значения коэффициента h_m1(t) и весьма большие значения дисперсии D_m1(t).

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

Такому режиму соответствуют большие значения математического ожидания числа пакетов , поступающих в течение интервала t, большие значения коэффициента h_m2(t) и весьма малые значения дисперсии D_m2(t).

Таким образом, весь поток заявок рассматривается как двухфазный, с последовательным чередованием фаз. Частным случаем многофазного потока является однофазный Г- поток.

Предположим, что в течение режима активности имеется Г- поток пакетов, в то время, как в пассивном режиме заявки вообще отсутствуют.

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

Разделим весь рассматриваемый промежуток времени на N(t) одинаковых интервалов t. Порядковые номера интервалов обозначим через i, i =1, 2,… N(t). Числа заявок, поступающих в течение i -го интервала, обозначим через m_i(t).

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

Обозначим через N_m(t) число интервалов t, в течение которых поступило ровно m(t) заявок, m(t) =0,1,2…

При достаточно большом объеме выборки можно считать, что вероятности P_m(t) поступления на интервалах t ровно m(t) заявок определяется соотношением (5.37).

m =0,1,2…

(5.37)

Вероятность отсутствия заявок на указанных интервалах обозначим через P₀(t) (5.38).

.

(5.38)

Искомое распределение вероятностей (5.39) представляется в виде двух составляющих, одна из которых P₀(t), а вторая - P_m(t):

, m =0,1,2…	(5.39)
где, .

Окончательно, распределение вероятностей имеет вид (5.40).

m =0,1,2…

(5.40)

Из полученных соотношений следует, что, при заданном коэффициенте загрузки (5.41), распределение вероятностей определяется вероятностью P₀(r) отсутствия заявок и значениями дисперсии (5.42) числа заявок на интервале t.

	(5.41)
	(5.42)

Следует подчеркнуть, что точное знание распределения числа заявок на интервале обработки t ещё не достаточно для определения средней длины очереди. Существенное влияние оказывают корреляционные свойства потока. На размер очереди влияет приведенный коэффициент автокорреляции r_m(t).

Дата добавления: 2015-08-05