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

 

6.1. Последовательное распределение постоянных интервалов времени передачи

 

Канал передачи рассматривается как одноприборная СМО. Алгоритм предусматривает определение чисел заявок m_i, поступающих в течении последовательно расположенных постоянных интервалов времени передачи пакетов τ.

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

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

Заявка с номером один сразу же поступает в обслуживающий прибор, а остальные три заявки становятся в очередь рис. 6.1.в. В течение следующего интервала времени t в обслуживающем приборе находится заявка с номером два, при этом очередь уменьшается на одну заявку.

Рис.6.1 последовательное расположение интервалов обслуживания

 

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

Так, последовательно происходит непрерывная обработка всех заявок, включая заявку с номером девять. Если интервал между очередными заявками 9 и 10 окажется достаточно большим, таким, что во время обработки заявки с номером 9 не успеет поступить очередная заявка с номером 10, то непрерывный процесс обработки (период занятости) закончится и наступит период простоя. Период простоя длится до момента появления заявки с номером 10, которая на рисунке не показана.

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

 

6.2. Средняя доля недообслуженных заявок

 

Рассмотрим пачечный поток заявок, поступающих в СМО в течение достаточно большого промежутка времени T(рис. 6.2). Длительность каждого интервала времени обработки выберем постоянной и равнойt. Разделим весь промежуток времени T на N одинаковых интервалов времени, длительностьюt.

Рис.6.2 Пачечный поток заявок

Значения m_j(t) j=1…N представляют числа заявок , поступающих на каждом интервале (число заявок в пачке). Некоторые «пачки» могут иметь нулевое количество заявок. Так, в течение первого интервала поступает m₁(t)=4заявки, причем заявка с номером один сразу же поступит на обработку, поскольку она застает обслуживающий прибор свободным. Появление заявок на первом интервале приведет к возникновению очереди. Суммарную очередь, возникающую в период обслуживания j– ой пачки, при условии, что первая заявка застает обслуживающий прибор свободным, а в период обслуживания всех заявок пачки, других заявок не поступает, назовем числом недообслуженных заявок в пачке.

 

,

(6.1)

 

где, l– порядковый номер заявки вj – ой пачке, .

Сумма элементов в (6.1) представляет собой сумму членов убывающей арифметической прогрессии. Следовательно,

(6.2)

Общее число заявок на рассматриваемом интервале времени T(6.3):

.

(6.3)

 

Суммируя значения a_j(t) по всем интервалам, определим среднее значение недообслуживания, приходящееся на один интервал обслуживания (6.4):

(6.4)

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

 

6.3. Дообслуживание очередей

 

Если рассмотренное выше условие не выполняется и поступающие заявки последующей пачки вынуждены ожидать окончания обработки всех заявок предыдущих пачек, то возникает некоторая дополнительная доля недообслуживания d_j(t), показанная на рисунке 6.3.

Рис.6.3 Образование дополнительной доли недообслуживания

 

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

Очередь размером q_j-1на промежутке, предшествующем появлению пачки m_j должна полностью обработаться. Поэтому обработка пачки m_j начинается с задержкой, равной q_j-1промежутков.

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

 

.

(6.5)

 

Средняя доля дообслуживания, приходящаяся на один интервал обслуживания (6.6),

 

(6.6)

 

6.4. Уравнение баланса

 

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

 

	(6.7)
		(6.8)

Обратим внимание на некоторые очевидные особенности δ_i(τ₎:

	(6.9)
		(6.10)
		(6.11)

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

Возведем в квадрат левую и правую части уравнения (6.7) и найдем математические ожидания от полученных выражений.

С учетом (2.9) получим,

 

.

(6.12)

Откуда,

,

(6.13)

где D_m(τ) - дисперсия m_i(t).

Окончательно имеем:

 

(6.14)

Обратим внимание, что в формулу (6.12) входят составляющими средняя доля недообслуженных заявок и средняя доля дообслуживания заявок , которые вместе и формируют среднюю длину очереди .

Соотношение (6.14) обобщает известную формулу Хинчина-Поллячека и справедливо для любых стационарных и ординарных потоков заявок, при постоянном времени обслуживания τ.

Не трудно также показать, что числитель выражения (6.13) определяется соотношением (6.15):

(6.15)

Действительно, подставив значение q_i(τ) из (6.7), и производя усреднение, имеем (6.16):

(6.16)

Напомним, что

Таким образом, получено еще одно соотношение, определяющее значение очереди :

(6.17)

 

Обозначим

.

(6.18)

 

Тогда (6.19),

.

(6.19)

 

Сравнивая с (6.14), убеждаемся в том, что

, где

, что и следовало ожидать.

Выражение (6-16) дает простой алгоритм определения значений E_m(τ):

На основании уравнения баланса (6.7) последовательно находятся значения

q_j-1(t₎₊q_j (t)и, m_i(t)-ρ, а затем усредняются их произведения.

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

6.5. Аппроксимация

 

Рассмотрим некоторые частные случаи:

1. Интервал времени обработки всегда остается меньше, чем минимальный промежуток времени ϑ_min между двумя соседними заявками. В этом случае в интервал не может попасть более одной заявки, а корреляционные связи отсутствуют r_m(τ)=0. Дисперсия D_m(τ), при этом, определяется соотношением 6.20:

(6.20)

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

2.Рассмотрим пуассоновский поток заявок. Для такого потока D_m(τ)=ρ.

Коэффициент корреляцииr_m(τ)для пуассоновского потока также равен нулю.

После подстановки в (6.19), получаем формулу Хинчина - Поллячека в её обычном виде 6.21:

.

(6.21)

 

3. Рассмотрим поток заявок, имеющий пачечный характер, с максимальной интенсивностью поступления заявок, равной λ_max и средней интенсивностью λ. Времена обслуживания заявок постоянны и равны τ. Максимальное число заявок, поступающих в течение интервала времени τ обозначим через (6.22)

.

(6.22)

 

Выберем некоторый, достаточно большой промежуток времени, на котором подряд размещается N интервалов обслуживания. Поскольку поток носит пачечный характер, на K интервалах заявки поступают, а на остальных интервалах отсутствуют. Расположение интервалов независимое. Рассмотрим наихудший случай, когда на каждом из указанных К-интервалов поступает одинаковое, максимально – возможное число заявок m_max(τ). Очевидно, что должно выполняться условие (6.23) или (6.24)

	(6.23)
	(6.24)

Обозначим отношение (6.25)

(6.25)

где P- Вероятность того, что интервал τ заполнен заявками.

Обратная величина k=1/P характеризует пачечность потока.

С учетом сказанного, получим

	(6.26)
	(6.27)
	(6.28)

Поскольку расположение интервалов независимое, коэффициент корреляции между ними равен нулю. Подставляя значения дисперсии D_m(τ) в (6.19), получим

.

(6.29)

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

И, лишь при значениях ρ k=λ_max τ=1, приходим к рассмотренному выше первому случаю, когда очередь отсутствует (пачки содержат не более одной заявки).

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

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

 

Рис. 6.4. Графики функций

 

Потоки имеют различные коэффициенты вариации ε_ϑ интервалов между заявками , где D_ϑ и ϑ-дисперсия и математическое ожидание временных интервалов между соседними заявками, соответственно.

Для экспоненциального распределения ε_ϑ=1 (пуассоновский поток), взаимная корреляция отсутствует, и зависимость E_m(ρ), как уже было показано, имеет линейный характер E_m(ρ)=ρ.

 

6.5.1. Аппроксимация степенной зависимостью

 

В общем случае, мы предлагаем представлять зависимость E_m(ρ) в виде степенной функции (6.30)

 

(6.30)

 

где коэффициенты K> 0 и 0<H<1 полностью характеризуют пачечный характер потока заявок и легко определяются экспериментально, путем аппроксимации кривых рис.(6.4) методом наименьших квадратов.

После подстановки в (6.19) получим (6.31):

,	(6.31)
где .

Если в процессе вычисления поучатся отрицательные значения, то следует приравнять нулю. Отрицательные значения свидетельствуют о наличии, рассмотренного выше, первого частного случая. Для пуассоновского потока K=1; H=0,5 , и полностью справедливо соотношение (6.21).

Коэффициент H по своему характеру, аналогичен известному коэффициенту Хэрста [8], который для пуассоновских потоков также равен 0,5 и изменяется в тех же пределах.

 

6.5.2. Полиномиальная аппроксимация

 

Анализ графиков, представленных на рис.6.4, также показывает целесообразность аппроксимации функции E_m(ρ) полиномом второй степени, вида (6.32)

 

(6.32)

 

Где α – некоторый постоянный коэффициент, а k- коэффициент пачечности потока.

Во многих случаях, коэффициент α незначительно отличается от единицы, и выражение для аппроксимации примет вид (6.33):

 

.

(6.33)

 

Действительно, для пуассоновского потока α=1, коэффициент пачечности k=1, E_m(ρ)=D_m(ρ)=ρ, что и следовало ожидать.

Для детерминированного потока α=1, коэффициент пачечности k=0. И E_m(ρ)=D_m(ρ)=ρ(1-ρ), что полностью соответствует (6.20).

Для низко вариабельных потоков, коэффициент пачечности изменяется в пределах от нуля до единицы, а для высоко вариабельных – он существенно превышает единицу.

Таким образом, для определения среднего размера очереди одноприборной СМО получено простое аппроксимативное соотношение (6.34):

,

(6.34)

Если в процессе вычисления получатся отрицательные значения, то следует приравнять нулю. Отрицательные значения свидетельствуют о наличии, рассмотренного выше, первого частного случая.

Соотношение (6.34) показывает, что очередь увеличивается с увеличением некоторого коэффициента k, учитывающего степень вариабельности потока заявок. Указанный коэффициент, совместно с коэффициентом α являются характерными для данного потока и легко определяются экспериментально на основании аппроксимации зависимости E_m(ρ) в соотношении (6.33). Аппроксимация производится на интервале изменения коэффициента загрузки ρ, в пределах от 0 до единицы.

 

6.6. Мультиплексирование потоков

6.6.1. Бесприоритетное обслуживание

 

Известно, что математические ожидания, дисперсии, коэффициенты корреляции и коэффициенты загрузки сумм независимых потоков заявок равны сумме значений соответствующих величин исходных потоков. Соотношения (6.13) и (6.14) позволяют легко получить выражение для суммарной очереди от Q независимых потоков, при их мультиплексировании.

, , .

 

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

 

(6.35)

Или

(6.36)

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

При суммировании Q одинаковых независимых потоков, получим (6.37):

(6.37)

При аппроксимации суммы Q одинаковых потоков, получим (6.38)

,	(6.38)
где ,	(6.39)

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

(6.39)

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

Если суммируются потоки с различными постоянными временами обслуживания, то предлагается определить суммарные величины для каждого из значений τ_j, j=1,2…Q

; ;

,

а затем, определить их математические ожидания, с учётом вероятностей появления заявки каждого типа:

;	(6.40)
	(6.41)
.	(6.42)

 

6.6.2. Мультиплексирование групповых потоков

 

Допустим, что мультиплексируются Q групповых потоков. Каждый групповой поток группы j (j=1,2,..Q) образуются путем мультиплексирования N_j одинаковых потоков пакетов. Каждый из потоков, образующих группу j имеет одинаковое время обслуживания τ_j

В этом случае

	(6.43)
	(6.44)
где	(6.45)

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

	(6.46)
	(6.47)
	(6.48)

6.7. Относительные приоритеты

 

Приоритеты заявок характеризуются целыми положительными числами 1,2…, причем, высокому приоритету соответствует меньшее число.

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

Обозначим числитель выражения (6.35) через , и назовем его «латентной очередью». Латентная очередь возникает в тех случаях, когда заявки любого типа, поступившие в течение промежутка времени обработки , успевают полностью обслужиться, до прихода в систему следующей очередной заявки.

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

Если указанное условие не выполняется, то очередь будет увеличиваться, по сравнению с «латентной» (6.49).

(6.49)

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

Обозначим через - суммарную длину очереди всех заявок, с приоритетами, не ниже k, k =1,2,…K. Поскольку на размер указанной очереди влияют только заявки, имеющие приоритеты, не ниже k, в формулу (6.49) следует вместо R_Q(τ),подставить коэффициент загрузки именно указанными заявками (6.50).

(6.50)

В результате (6.51),

(6.51)

Среднее число заявок с приоритетом k, находящихся в очереди,

(6.52)

После подстановки значений, получим окончательно (6.53):

.

(6.53)

Соотношение (6.53) позволяет также легко определить среднее время нахождения заявки приоритета k в очереди.

Учитывая, что , где λ_k- интенсивность заявок k-го приоритета, получим (6.54):

.

(6.54)

Указанный результат полностью согласуется с соотношениями, полученными для многоприоритетных пуассоновских потоков, и справедлив для потоков общего вида. Если рассматриваются потоки с различными временами обслуживания, то соотношение (6.54) следует применять, с учетом (6.42). Таким образом, соотношения (6.53) и (6.54) позволяют, соответственно, определить средние размеры очередей и время ожидания в очередях потоков заявок общего вида, при их многоприоритетном обслуживании.