CORRELATIVE FEATURES OF QUEUE SIZE IN QUEUE SYSTEMS WITH GENERAL FLOWS

Abstract

This work describes queue systems with request train flows being typical for modern multiservice networks. Influence of correlation features of flows on queue sizes is shown. Here the expression for correlation was derived. It generalizes a well known Pollaczek-Khinchin formula and it is correct for any stationary and ordinary request flows. Therefore average queue size is defined by dispersion and sum of correlative parameters of requests over service cycle. Flow parameters are easy determined by experiment. They can be used further for computing of average queue size in multiservice communication systems.

Full Text

Введение При анализе систем массового обслуживания (СМО) наиболее часто применяются две вероятностные характеристики распределения. Это распределение интервалов между соседними заявками и распределение интервалов времени обработки заявок На основе указанных распределений определяются параметры и , входящие в формулу Хинчина-Поллячека [1]: где - средняя длина очереди; - среднее время обслуживания заявки; - средний интервал между соседними заявками; - дисперсия времени обработки заявок. Существенным ограничением данной формулы является ее применимость исключительно к простейшим потокам, для которых интервалы между заявками распределены экспоненциально. Имеется ряд попыток модернизации формулы (1) с целью ее применения для не экспоненциальных потоков заявок [2]. Однако, все полученные результаты применимы лишь для слабо изменяющихся входных потоков, для которых коэффициент вариации интервалов между заявками не превышает единицу. Современные мультисервисные телекоммуникационные сети имеют входные потоки пакетов, для которых коэффициент вариации в несколько раз превышает единицу. К таким потокам применение аналитических соотношений, указанных в [2], становится невозможным. Это обусловлено тем, что в качестве основного параметра, характеризующего длину очереди, в аналитических соотношениях используется распределение интервалов между соседними заявками. Вместе с тем, Л. Клейнроком [1] показано, что длина очереди одноприборной СМО, в общем случае, определяется случайной величиной - числом поступивших заявок, приходящихся на одну обработанную заявку. Уравнение баланса Для любой одноприборной СМО справедливо рекуррентное соотношение, устанавливающее связь между поступающими и обработанными заявками [3]: (1) где и - числа заявок, поступивших в течение i-го интервала и размер очереди, образовавшейся на указанном интервале, соответственно. Скорость изменения очереди Найдем из соотношения (1) приращение очереди в течение i-го промежутка времени (2) (3) Указанное приращение, отнесенное к промежутку времени определяет скорость изменения длины очереди на i-ом промежутке. Длина очереди на указанном промежутке, при нулевых начальных условиях, определяется суммой: (4) Случайная величина целочисленная, и может принимать любые положительные, и нулевые значения, а также, отрицательные значения, равные единице. Таким образом, случайная величина , определяющая длину очереди на i-ом промежутке времени, представляет сумму значений величины на всех промежутках, начиная с нулевого. В любой одноприборной устойчивой СМО всегда имеется два режима работы: активный, в течение которого прибор обслуживания загружен, и режим простоя, в течение которого прибор обслуживания простаивает. Каждому активному режиму всегда предшествует период и период простоя образуют цикл. Началу каждого цикла всегда должен предшествовать интервал полного отсутствия заявок. Поэтому, циклы можно считать независимыми. Размеры очередей будем определять для каждого цикла отдельно, а затем, производить их усреднение. На рис. 1 показан процесс образования очередей в одноприборной СМО, при поступления пачечного потока заявок. Весь временной промежуток разбит на интервалы времени в течение каждого из которых успевает полностью обработаться по одной заявке. На рис. 1а показано поступление пачек заявок Интервалам, на которых поступление заявок отсутствует, соответствует На рис. 1а показано поступление подряд четырех пачек по три заявки в каждой: k = 4, Рис. 1. Процесс образования очередей в одноприборной СМО На рис. 1б показан процесс изменения размеров очередей и поступление заявок в прибор обслуживания В начальный момент заявки в приборе обслуживания отсутствуют При поступлении пачки заявок в течение первого интервала времени первая заявка сразу попадает на обслуживание, а остальные - образуют очередь На каждом из последующих интервалов число заявок первой пачки, находящихся в очереди, уменьшается на единицу. Если в системе предусмотрена дисциплина обслуживания FIFO, то вне зависимости от поступающих в дальнейшем заявок, заявки первой пачки обслужатся до конца. В течение второго интервала поступит пачка заявок они увеличивают имеющуюся очередь. Лишь, после завершения обработки всех заявок первой пачки, заявки второй пачки поступят на обработку, и далее, будут обрабатываться до конца. Заявки, поступившие в течение третьего интервала становятся в очередь, и будут находиться в ней до полной обработки всех заявок второй пачки. Аналогичный процесс будет происходить и с заявками четвертой пачки. Из рис. 1 видно, как наличие предыдущих заявок приводит к увеличению времени пребывания в очереди более поздних заявок. Если бы очередная пачка заявок поступила после завершения обработки всех заявок предыдущей пачки, то образовался бы пассивный период, в течение которого заявки в системе отсутствуют. На рис. 1в показаны размеры очередей на каждом из интервалов В рассматриваемом примере, активный период составляет интервалов. Число интервалов времени активного периода всегда в точности равно суммарному числу заявок, поступивших, в течение указанного периода (поскольку, все заявки должны обработаться). Поэтому, в активном режиме всегда выполняется соотношение и соотношение (4) примет вид: (5) Суммарный интервал определяется соотношением (значение коэффициента загрузки в данном примере выбрано равным 0,5). Пассивный период составляет интервалов времени. Определим суммарный объем всех очередей на активном участке. В соответствии с (5) (6) Из рассмотрения рис. 1б следует, что вся суммарная очередь представляет собой две суммы: (7) Первая сумма учитывает суммарную очередь, если последующая пачка заявок поступает после полной обработки заявок предыдущих пачек (треугольные фигуры). Вторая сумма учитывает увеличение суммарной очереди, за счет задержек, возникающих при обработке заявок предыдущих пачек (прямоугольные фигуры, которых в рассматриваемом примере - три). Определим среднее значение размера очереди на каждом интервале времени всего рассматриваемого цикла: В течение всего пассивного периода, заявки и очереди отсутствуют, поэтому, суммирование можно проводить не по а по всему циклу Математическое ожидание числа заявок на каждом интервале времени Дисперсия числа заявок, на каждом интервале времени всего рассматриваемого цикла: Нетрудно показать, что математическое ожидание первой суммы в (7): (8) Найдем математическое ожидание второй суммы в (7): Известно [1], что (9) где корреляционный момент между числом заявок, поступающих на i-ом интервале и размером очереди на предыдущем интервале. Из (9) определим значение Определим среднее значение размера очереди на интервалах , с учетом (8)-(9): Отсюда получаем , где - коэффициент загрузки, а - средняя интенсивность поступления заявок. Если средняя интенсивность поступления заявок известна, то, при заданном значении коэффициента загрузки, размер интервалов τ определяется однозначно, и соотношение может быть записано в следующем виде: (10) Подставляя значения всех полученных выше величин в (10), убеждаемся в его справедливости. Рассмотренные примеры показывают, что не учитывание корреляционных свойств потока заявок может привести к возникновению стопроцентной погрешности, при определении размеров очередей. Рис. 2. Зависимость потока пакетов видео трафика Особое влияние на размер очереди оказывает величина дисперсии числа заявок при заданной загрузке. Дисперсия при пуассоновском потоке равна и линейно увеличивается с увеличением загрузки. Отметим, что в данном случае дисперсия более чем в два раза превышает дисперсию пуассоновского потока: На рис. 2, в качестве примера, показана зависимость дисперсии для потока пакетов реального видеотрафика. Значения дисперсии видеотрафика при фиксированном коэффициенте загрузки 0,5 почти в 20 раз превышают дисперсию пуассоновского потока. Рис. 3. Зависимости от коэффициента загрузки Еще более разительны различия размеров очередей. На рис. 3. показаны зависимости чисел заявок в очередях от коэффициента загрузки, для пуассоновского потока и потока видеотрафика. При коэффициенте загрузки 0,5 имеет место разница более чем в 200 раз. Это еще раз подтверждает невозможность применения формулы Хинчина-Поллячека для расчета размеров очередей пачечных потоков. Заключение Соотношение (10) обобщает формулу Хинчина-Поллячека, и справедливо для любых стационарных и ординарных потоков заявок, при постоянном времени обслуживания [3]. Из (10) также следует, что средние значения размера очереди определяются дисперсией и корреляционными и характеристиками чисел заявок на интервалах обслуживания. Для пуассоновского потока заявок, если корреляционные связи отсутствуют, а и мы получаем формулу Хинчина-Поллячека в ее обычном виде. Для потоков трафика мультисервисных сетей характерны сильные корреляционные зависимости, и могут достигать весьма больших значений. Величины и для каждого вида потока заявок легко определяются экспериментально, и могут использоваться при расчете средних значений очередей трафика в мультисервисных сетях связи.