Queues modeling in batch queuing systems (QMS)

Full Text

Введение Процесс формирования очередей заявок в СМО подробно и широко рассмотрен в литературе [1, 4]. Формирование очередей в СМО с пакетным пачечным трафиком рассмотрено нами в [2]. Анализ проводился для стационарных потоков интервальными методами, основанными на определении чисел заявок (пакетов), поступающих в систему, в течение интервала времени обработки одной заявки [2, 3]. В этих работах показано, что среднее значение размера очередей для однопоточных СМО определяется величиной коэффициента загрузки чисел заявок и дисперсией чисел заявок , поступающих в течение интервала , соответствующего данному коэффициенту загрузки. Здесь - средняя интенсивность потока заявок. Показано, что среднее число заявок всегда равно коэффициенту загрузки . Получено обобщение формулы Хинчина - Поллячека [2, 5, 6]: , (1) где - среднее значение длины очереди, определенное на всем промежутке времени наблюдения, с учетом интервалов времени простоя процессора; - дисперсия чисел заявок на интервале обслуживания, соответствующем коэффициенту загрузки ; - коэффициент ковариации и ; - интервал корреляции. Потоки пакетов трафика современных мультисервисных сетей доступа носят явно выраженный пачечный характер [2]. Поэтому существует весьма значительное число временных интервалов, в течение которых заявки не поступают. На рис. 1, а показаны количества пакетов видеотрафика, поступающих в течение постоянных интервалов времени , которые соответствуют различным значениям коэффициентов загрузки. (- черные линии, - серые линии). На рис. 1, б показан фрагмент этого же трафика в увеличенном масштабе времени. В качестве единицы времени здесь выбран постоянный интервал времени обработки одной заявки. На рис. 2, a показан процесс образования очередей в потоке пакетов рассмотренного видеотрафика при различных значениях коэффициентов загрузки (- черные линии, - серые линии). На рис. 2, б показан фрагмент этого же трафика в увеличенном масштабе времени. Рис. 1, а. Количества пакетов видеотрафика, поступающих в течение постоянных интервалов времени Из графиков следует, что в периоды активного поступления пакетов очереди быстро возрастают. При малых значениях коэффициента загрузки (интервал времени обработки мал) очередь быстро уменьшается, достигает нулевого значения, и все остальное время процессор простаивает. При большой загрузке (интервал времени обработки велик) очередь уменьшается медленно и процессор простаивает меньше. Рис. 1, б. Фрагмент количества пакетов видеотрафика, поступающих в течение постоянных интервалов времени (масштаб времени увеличен) Рис. 2, а. Образование очередей в потоке пакетов реального видеотрафика Рис. 2, б. Фрагмент образования очередей в потоке пакетов реального видеотрафика (масштаб времени увеличен) Очевидно, что при малых загрузках средние значения чисел заявок в очереди весьма малы. Из рис. 2, б видно, что даже при весьма значительных загрузках график изменения очереди имеет треугольную форму. Процесс формирования очереди можно разделить на три этапа: этап нарастания, этап уменьшения и этап полного отсутствия очереди, когда процессор простаивает. Формирование очереди На рис. 3 приведен график формирования очереди при пачечном потоке. В рассматриваемом примере показаны пакеты, поступающие в период цикла в течение промежутка времени , пачками, размером , с максимальной интенсивностью (этап нарастания очереди). Примем, что на всем интервале времени наблюдения максимальная интенсивность поступления пакетов (заявок) и время обработки одной заявки остаются постоянными. В течение времени обработки в систему каждый раз поступает заявок (в рассматриваемом примере - три заявки). Примем, что на промежутке времени укладывается целое число интервалов (в рассматриваемом примере - 4 интервала): . Рис. 3. График формирования очереди при пачечном потоке На этапе уменьшения в течение каждого интервала временипроисходит убывание очереди на одну заявку. Длительность этапа простоя определяется принятым периодом, после окончания которого в систему поступает очередная пачка заявок. Обозначим максимальный размер очереди, образованной -й пачкой заявок, (на рис. 3 показана одна пачка). Нетрудно доказать, что максимальный размер определяется соотношением . (2) На рис. 2, б хорошо заметно, что с увеличением нагрузки увеличивается максимальное значение очереди. Естественно, что эта формула имеет ограничение , что соответствует. В противном случае в течение интервала обслуживания будет поступать не более одной заявки и очередь отсутствует. Нетрудно показать, что в случае появления одной пачки заявок в течение цикла общее число заявок, которые находились в очередях (суммарная площадь треугольника), Если предположить, что в течение каждого из циклов появляется несколько пачек, но каждая из последующих пачек появляется после окончания обработки всех заявок предыдущей пачки, и размеры пачек взаимно независимы, то общее число заявок, находившихся в очередях в течение всего периода наблюдения , определяется соотношением , где - общее число пачек на всем периоде наблюдения (в рассматриваемом примере и )). Среднемаксимальное значение очереди Введем в рассмотрение понятие «среднемаксимальное значение» очередей (среднее из всех максимальных значений). Обозначим также среднее число заявок в пачке через : . Поскольку каждой пачке заявок соответствует максимальное значение , определяемое соотношением (2), а всего на интервале рассмотрения имеется пачек, то . (3) Введем понятие условного среднего значения размера очереди , которое представляет среднее значение очереди на каждом из интервалов , соответствующем условию активной загрузки процессора (процессор не простаивает): , (4) где - второй начальный момент чисел заявок в пачках (в рассматриваемом примере и 4)). Сравнивая (3) и (4), получаем зависимость , (5) где - коэффициент вариации чисел заявок и пачках. Если все пачки одинаковые (, то имеют наибольшее значение . Подставляя из (4) в (5), получим , при . Подобный результат не является неожиданным, поскольку случайные величины и в (2) отличаются только постоянным коэффициентом . Среднее число заявок , находящихся в очереди, с учетом наличия интервалов простоя процессора: . Указанные соотношения определяют среднее значение очереди при условии, что очередная пачка не может появиться до окончания обработки предыдущей пачки. Однако это условие выполняется далеко не всегда. На рис. 2, a видно, что при коэффициенте загрузки происходит наложение очередей от соседних пачек. В работах [2, 3] показано, что расположение взаимно независимых пачек не оказывает влияния на числитель формулы (1), а учитывается изменением коэффициента загрузки в знаменателе. Таким образом, с учетом возможного наложения обобщенная формула для определения средних значений очередей в одноприборных СМО с рассмотренными пачечными потоками примет вид . (6) При этом . (7) На рис. 4 для рассмотренного выше видеотрафика показаны количества пакетов, поступающих в течение постоянных интервалов времени , которые соответствуют коэффициенту загрузки (черные линии). Для сравнения здесь же показаны количества пакетов пуассоновского потока, полученные при той же загрузке (серые линии). Из рис. 4 следует, что по сравнению с видеотрафиком пуассоновский поток носит весьма равномерный характер. Для пуассоновского потока при постоянном времени обслуживания условное среднее значение очереди определятся на основании известной формулы Хинчина - Поллячека [4]: . Анализ показывает, что абсолютная разница среднего и условного среднего значений, полученных по этим формулам для пуассоновских потоков, не превышает 0,25 заявки. Для потока видеотрафика указанная разница становится весьма значительной. На рис. 5 для рассмотренного выше реального видеотрафика показана зависимость в диапазоне изменения коэффициента загрузки от 0 до 0, 05. Рис. 4. Количества пакетов, поступающих в течение интервалов времени , которые соответствуют коэффициенту загрузки , для видеотрафика и пуассоновского потока Из графика следует, что коэффициент загрузки соответствует среднему значению очереди (показано в верхней части рисунка). Условное среднее число пакетов в очереди при этом составляет Среднее от максимальных значений очередей , определенное соотношением (5), почти в 60 раз превышает среднее значение очереди . Таким образом, среднее значение плохо отражает реальное состояние очередей; для характеристики размеров очередей следует ориентироваться на условные средние значения чисел пакетов в очереди . На рис. 6 для рассмотренного выше реального видеотрафика показана зависимость в диапазоне изменения коэффициента загрузки от 0 до 0,05. Так как согласно (7) при малых значениях , Рис. 5. Зависимость для реального видеотрафика в диапазоне изменения коэффициента загрузки от 0 до 0, 05 Рис. 6. Зависимость в диапазоне изменения коэффициента загрузки от 0 до 0,05 для трафика с экспоненциальным распределением длительностей пачек () при малой загрузке . Таким образом, условное среднее число пакетов полностью определяет среднее от максимальных значений размеров очереди. Заключение Для СМО с пачечными потоками среднее значение очереди с учетом интервалов простоя процессора плохо отражает реальную картину размера очередей и не может непосредственно использоваться для определения размеров буферной памяти. Условное среднее число пакетов более чем в 30 раз превышает среднее значение и полностью характеризует максимальные значения размеров очередей, которые и определяют требуемые предельные значения объема буферной памяти.

About the authors

Boris Ya Lichtcinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psati.ru
(Dr. Sci. (Techn.)), Professor 23, Lev Tolstoy st., Samara, 443010, Russian Federation

Lyudmila B Ivanova

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psati.ru
(Ph.D. (Techn.)), Associate Professor 23, Lev Tolstoy st., Samara, 443010, Russian Federation

References

Supplementary files