Queues modeling in batch queuing systems (QMS)

Abstract


The paper describes queuing systems with batch request flows typical for modern multiservice telecommunication networks. It contains generalization of Pollaczek-Khinchin formula for systems with common type flows. The dependences of queues average value at low duty ratio are examined. Full absence of any queues because of a minimal time interval between nearby requests takes place. The term of conditional average queue size that is an average value with the absence of processor downtime intervals is given.

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
23, Lev Tolstoy st., Samara, 443010, Russian Federation
(Dr. Sci. (Techn.)), Professor

Lyudmila B Ivanova

Povolzhskiy State University of Telecommunications and Informatics

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

References

  1. Степанов С.Н. Теория телетрафика. Концепции, модели, приложения. - М.: Горячая линия Телеком, 2015. - 808 с.: ил.
  2. Лихтциндер Б.Я. Интервальный метод анализа трафика мультисервисных сетей // Приложение к журналу ИКТ Модели инфокоммуникационных систем: разработка и применение. - Вып. 8. - Самара, 2011. - С. 101-152.
  3. Лихтциндер Б.Я. Интервальный метод анализа трафика мультисервисных сетей доступа. - Самара: ПГУТИ, 2015. - 121 с.: ил.
  4. Клейнрок Л. Вычислительные системы с очередями. Т. 2. Пер. с англ. - М.: Мир, 1979.
  5. Лихтциндер Б.Я. О некоторых обобщениях формулы Хинчина - Поллячека // Инфокоммуникационные технологии. - 2007. - Т. 5. - № 4. - С. 253-258.
  6. Лихтциндер Б.Я. Интервальный метод анализа мультисервисного трафика сетей доступа // Электросвязь. - 2015. - № 12. - С. 52-54.

Statistics

Views

Abstract - 48

PDF (Russian) - 20

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2016 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies