INTERVAL METHOD FOR DELAY EVALUATION IN ONE-BOX QUEUE SYSTEMS WITH GENERAL TYPE DEMAND STREAMS

Abstract


This work concerns with analysis of time delays in queue systems with general type demand streams. Traffic of packet flows in multiservice networks is characterized by high correlation score. Based on proposed interval methods, we derived expressions that generalize Khinchin-Polaczek formula for average delay in queue systems with general type demand streams. Here the main analyzed parameters are time intervals between adjacent demands. We show that average queue size and average delays in queues are independent on which way they were been obtained - based on analysis of incoming demand intensity or as a result of adjacent demand time interval analysis. Some results of comparisons between computed data and real video traffic are represented.

Full Text

Введение Основным соотношением, определяющим размер очередей в системах массового обслуживания, является формула Хинчина-Поллячека, устанавливающая зависимость между средним размером очереди и коэффициентом загрузки системы [1-2] известного вида Указанная формула справедлива только для пуассоновских потоков при постоянном интервале времени обслуживания. Имеется много попыток преобразования указанной формулы [7-11], однако они оперируют в основном с пуассоновскими потоками. Поэтому возникала необходимость нахождения зависимостей, пригодных для определения размеров очередей в системах, с потоками общего вида. Такая зависимость была получена, в результате применения интервального метода, основанного на определении чисел заявок, поступающих в течение интервалов обслуживания [3-6]: (1) где - среднее значение длины очереди, - дисперсия числа заявок на -ом интервале обслуживания а - ковариация чисел заявок на -ом интервале и длины очереди на предыдущем интервале. Соотношение (1) обобщает формулу Хинчина-Поллячека, оно справедливо для любых стационарных и ординарных потоков заявок, при постоянном времени обслуживания и было получено, в результате анализа уравнения баланса (2) Формула (2) устанавливает зависимость между размером очереди числами заявок на текущем интервале времени, и размером очереди на предыдущем интервале. Преобразование обобщенной формулы Выразим в (1) значения через согласно (2): После преобразований, получим Суммируя данное выражение с (1), получим окончательно (3) Соотношение (3) также обобщает формулу Хинчина-Поллячека, и также справедливо для любых стационарных и ординарных потоков заявок, при постоянном времени обслуживания Временные задержки в очередях Рассмотрим временные задержки в очередях, на основе анализа уравнения баланса интервалов времени между соседними заявками: (4) где - i-ый интервал времени между двумя соседними заявками; и - промежутки времени ожидания в очереди (задержки) для заявок на -ом и () -ом интервалах между соседними заявками, соответственно. Как и прежде, здесь - детерминированная переменная величина, характеризующая интервал времени обработки одной заявки. Указанная величина может изменяться в пределах, соответствующих изменению значений коэффициента загрузки от нуля до единицы, то есть , где - математическое ожидание интервалов между соседними заявками; - средняя интенсивность потока заявок; - коэффициент загрузки. Анализ удобнее проводить в безразмерных относительных временных интервалах. Введем обозначения: , (5) где и - целые числа интервалов укладывающиеся в и соответственно, и принимающие значения Уравнение баланса в указанных безразмерных единицах может быть представлено в следующем виде: ; Перепишем уравнения как ; (6) Введем случайную величину ; (7) Тогда уравнение баланса (6) может быть представлено в виде (8) Обратим внимание на то, что неравенство выполняется лишь при условии, что каждое из слагаемых равны нулю, поскольку оба слагаемых не отрицательные целые числа. Это означает, что а также, Одновременно Возведем в квадрат обе части уравнения (8) и произведем усреднение: Из основного уравнения баланса (7) непосредственно следует, что Учитывая, что для стационарного процесса а также, что а получим: или (9) Соотношение (9) обобщает формулу Хинчина-Поллячека для среднего значения времени ожидания в очередях систем массового обслуживания с потоками заявок общего вида. Преобразование формулы временных задержек Обратим внимание на то, что соотношение (9) по форме аналогично (1), однако оно определяет среднее значение времени ожидания в очереди в зависимости от интервалов между соседними заявками. Коэффициент загрузки как и следовало ожидать, обратно пропорционален среднему значению интервалов между заявками. Определим из выражения (8): Ковариация После подстановки в (9) получим: (10) Суммирование (9) и (10) дает Учитывая, что после преобразования получим (11) Введем обозначения ; Очевидно, что С учетом этого соотношение (12) примет вид (12) Время ожидания и интервалы между заявками здесь выражены в относительных единицах, по отношению к среднему значению интервала между соседними заявками Инвариантность корреляционных связей Полученный результат позволяет сделать весьма важный дополнительный вывод. В соответствии с теоремой Литтла [1]: Приравняв (3) и (12), получим фундаментальное соотношение (13) которое устанавливает равенство по модулю значений ковариаций при различных методах определения средней длины очереди в одноприборных СМО, с потоками заявок общего вида. Знак «минус» в правой части возникает здесь потому, что с увеличением интервала между заявками размеры очередей уменьшаются. Можно сказать, что числители в (3) и (12) характеризуют динамическую составляющую мощностей потоков, которая не зависит от способа ее определения. На рис. 1 представлены результаты моделирования (13) для реального видеотрафика. Левая часть равенства соответствует кривой «для интенсивностей», правая соответствует кривой «для интервалов между заявками». Незначительные различия между ними возникают в результате погрешностей моделирования. Рис. 1. Результаты моделирования равенства (13) для реального видеотрафика Заключение В то время как приведенное в [3-6] соотношение (3) обобщает формулу Хинчина-Поллячека для определения среднего размера очереди в СМО с потоками заявок общего вида, полученные в настоящей работе соотношения (10)-(12) обобщают указанную формулу для определения среднего значения времени ожидания в очередях. В отличие от (3), где анализируются интенсивности заявок, поступающих в течение интервала времени обслуживания, основными анализируемыми параметрами в рассматриваемых соотношениях являются временные интервалы между соседними заявками.

About the authors

Boris Yakovlevich Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psati.ru

References

  1. Клейнрок Л. Вычислительные системы с очередями. Т.2. Пер. с англ. М.: Мир, 1979. - 600 с.
  2. Степанов С.Н. Теория телетрафика. Концепции, модели, приложения. М.: Горячая линия-Телеком, 2015. - 808 с.
  3. Лихтциндер Б.Я. Интервальный метод анализа трафика мультисервисных сетей // Модели инфокоммуникационных систем: разработка и применение. Приложение к журналу ИКТ. Вып. 8, 2011. - С. 101-152.
  4. Лихтциндер Б. Я. О некоторых обобщениях формулы Хинчина-Полллячека // ИКТ. Т.5, №4, 2007. - С.253-258.
  5. Лихтциндер Б.Я. Интервальный метод анализа мультисервисного трафика сетей доступа // Электросвязь. №12, 2015. - С. 52-54.
  6. Лихтциндер Б.Я. Интервальный метод анализа трафика мультисервисных сетей доступа. Самара: ПГУТИ, 2015. - 121 с.
  7. Chan W.C., Lu T.C., Chen R.J. Pollaczek-Khinchin formula for the M/G/1 queue in discrete time with vacations // IEE Proceedings-Computers and Digital Techniques. 1997. V.144. № 4. - P. 222-226.
  8. Lakatos L. A note on the Pollaczek-Khinchin formula // Annal. Univ. Sci. Budapest Sect. Comp. 2008. V.29. - P. 83-91.
  9. Zheng F.U., Wang J. A new method for the Pollaczek-Khinchin formula // ICIC express letters. Part B, Applications: an international journal of research and surveys. 2015. V.6. - P. 1619-1624.
  10. Huang L., Lee T.T. Generalized pollaczek-khinchin formula for markov channels // Communications, IEEE Transactions on. 2013. V. 61. №. 8. - P. 3530-3540.
  11. Huang L. Generalized Pollaczek-khinchin Formula for Queueing Systems with Markov Modulated Services Rates: diss. - The Chinese University of Hong Kong. 2013.

Statistics

Views

Abstract - 22

PDF (Russian) - 2

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2016 Likhttsinder B.Y.

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

This website uses cookies

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

About Cookies