WAITING TIME ANALYSIS FOR G/G/1 QUEUE

Abstract


The paper presents two methods for determining the average waiting time for G/G/1 queue: he method of scale averaging and approximation and the approximation of the sum of the elements to find a solution to Lindley’s integral equation. The practical significance of studying queues with dependent arrival processes is obvious, since exact analytical or numerical solutions are usually not available for G/G/1 system; the operations to investigate network traffic on IP networks where each type of traffic is mapped to a distribution law. The distribution functions (Weibull and Pareto) of time parameters were obtained in Easy Fit data analysis program. The traffic was captured using Wireshark traffic analyzer program. The approximation of PMRQ in the average waiting time in TES+/G/1, MMRR was compared with the analytical solution for the same value in case of the solution of the spectral method of Lindley’s integral equation and the error was about 4-14% which is acceptable. The comparison of methods of approximating network traffic allows to estimate the average waiting time of the packet using statistical data analysis, which makes it possible to improve the quality of service and predict the traffic behavior.

Full Text

Введение В телекоммуникационном оборудовании аналитическое исследование и расчет статистических параметров трафика, дает возможность приблизиться к определению пропускной способности сети, оптимального размера буфера. Для решения задач, в которых существуют случайные события, используются как аналитические, так и имитационные модели. Зачастую аналитические модели предпочтительнее имитационных по нескольким причинам: не требуется проведения большого числа испытаний; можно получить оптимальное решение. Традиционная теория очередей посвящена очередям, где время между прибытием и время обслуживания являются независимыми процессами обновления. Есть предположение о том, что время обслуживания потока пакетов взаимно независимые, а соответствующее предположение о независимости потока пакетов от интервалов между прибытиями, часто неоправданно - следовательно, необходимо учитывать при моделировании СМО G/G/1 свойство самоподобия данных процессов, Изучение очередей с зависимыми процессами прибытия является актуальным и имеет практическую ценность. Можно сделать вывод: точные решения (аналитические или численные) обычно недоступны для очереди G/G/1, так как исследователи прибегают к моделированию Монте-Карло или используют классическую теорию Маркова и ее вариации для проведения параметрического анализа по средней длине очереди [1]. Корреляции в прибывающем потоке событий, в предположении очереди на один сервер, существенно влияют на среднее время ожидания по сравнению с соответствующим потоком событий, приходящих повторно, тому же серверу. Однако если использовать такие модели СМО G/G/1, для которых созданы и построены реальные или максимально приближенные к действительности аппроксимации распределений интервалов времени между пакетами и длительной обслуживания для очередей с коррелированными поступлениями [2] становится возможным поиск решения неизвестных средних характеристик трафика. В основном используются распределения с «тяжелым» хвостом Парето и Вейбулла для построения процесса прибывающего потока пакетов и определения среднего времени ожидания пакета в очереди, учитывая его скорость, коэффициент вариации и другие характеристики. Исследование, проведенное относительно распределения времени между пакетами, описываемых распределениями с «тяжелым» хвостом Вейбулла, Парето показало, что его можно использовать для аналитического определения параметров трафика [3-4]. Применение распределений с «тяжелым» хвостом наилучшим образом приближенны к функциям распределений, описывающих статистические характеристики трафика. Определяя преобразования Лапласа законов распределений, которым подчиняются интервалы времени между пакетами и длительности пакетов, и, используя спектральный метод решения интегрального уравнения (ИУ) Линдли, можно найти функцию времени ожидания пакетов в очереди. Определение данной сетевой характеристики позволяет повысить качество обслуживания при конфигурации сети и проследить изменчивый характер трафика, учесть его свойства, чтобы, в свою очередь, наиболее точно оценить параметры сети. Предложенный в [5] метод аппроксимации распределения суммой затухающих экспонент дает неудовлетворительные результаты по точности на «восходящих» ветвях распределений. Кроме того, аппроксимация «восходящих» ветвей распределений приводит к появлению в сумме затухающих экспонент слагаемых с отрицательными коэффициентами, что нивелирует вычислительные преимущества спектрального метода, обусловленные использованием гиперэкспоненциальных распределений. Анализ времени ожидания в очередях СМО G/G/1 с использованием приближения PMRQ аппроксимации Ряд исследований подтвердило теоретические расчеты - продемонстрировав влияние автокорреляций в процессах прибытия (или сервисных процессах) на статистику очередей в связанных очередях по сравнению с их аналогами обновления [1; 5-6]. В более общем случае, если данные о статистических параметрах доступны, то методы, рассмотренные и проанализированные в этом исследовании, могут быть использованы для получения среднего времени ожидания. Для исследования произвели анализ результатов, полученных в работе [7]. Идея данной работы заключается в сравнении результатов аппроксимации способами PMRQ и PMRS при сопоставлении СМО G/G/1 аппроксимирующей GI/G/1 [7] и аппроксимации суммой затухающих экспонент [5,6] при одних и тех же параметрах сети смоделированными и приближенными к реальным значениям. Предложенная схема аппроксимации, представленная в работе [7], которая сопоставляет G/G/1 аппроксимирующей GI/G/1 PMRQ (Peakedness Matched Renewal Queue) использует аппроксимации потока распределения услуг в пиковом режиме, которые имеют названия PMRS (Peakedness Matched Renewal Stream). Приближенный процесс прибытия PMRS сохраняет пиковость исходного процесса прибытия и его скорость прибытия; кроме того, квадратный коэффициент вариации построенного процесса прибытия PMRS равен индексу дисперсии исходного процесса прибытия. Заслуга приближения PMRQ заключается в том, что он легко разрешим, в отличие от первоначальной очереди G/G/1. Для этого в работе [7] используется функция меры остроты пика [8], а отставание - коэффициентом автокорреляции в исходном потоке. Приближение PMRQ аппроксимации способом для поиска среднего времени ожидания в схеме TES+/G/1 (Transform Expand Sample) лучше по сравнению со ссылочными значениями, полученными с помощью моделирования, где простой вариант процессов прибытия TES+ служил процессом прибытия, связанным с автокором [9-10]. Рассмотрение универсальных классов автокорреляционных (лопастных) стохастических процессов, называемых TES+ [9-10] впоследствии служат процессами прибытия в очереди G/G/1, результирующая TES+/G/1 это проверка эффективности среднего времени ожидания приближения, предложенного в работе [7]. При рассмотрении данной модели одновременно подбирается маргинальное распределение и корреляционная функция. Целью при аппроксимации PMRQ и PMRS является построение модели, соответствующей трем требованиям одновременно: маргинальное распределение должно соответствовать ее оригиналу (гистограмме); основные корреляционные модели должны приближаться к оригиналам до приемлемой задержки; выборки, сгенерированные моделью, должны «иметь сходство» с опытными временными сериями. Интересное приближение PMRS возможно следующим образом. Можно показать [8], что пиковая функция любого возобновляемого потока трафика имеет представление (1) где - преобразование Лапласа плотности временного интервала между временем и . Из (1) следует, что для общего движения процесса соответствующее PMRS аппроксимирующего процесс обновления полностью определяется через преобразование Лапласа от его плотности временного интервала между временем вида (2) Уравнение (2) фактически подразумевает, что . Обоснование аппроксимации PMRS очевидно: в целом аналитически проще, чем - факт, который будет использоваться позже в приблизительном анализе очереди G/G/1. Более конкретно, PMRQ аппроксимации очереди G/G/1 общего процесса является просто соответствующей очереди GI/G/1 с обновлением предлагаемого трафику процесс , где - PMRS аппроксимации . Поэтому трафик рассматривается как пульсирующий процесс времени [11], имеющий описания и свойства процессов TES [9]. Процессы TES представляют собой универсальный класс стационарных временных рядов, допускающих любое предельное распределение, большое разнообразие автокорреляционных функций (монотонность, колебание, чередование и др.), и широкий спектр поведения, в том числе направленных и ненаправленных процессов. Процессы TES могут быть разработаны, чтобы соответствовать любому эмпирическому (маргинальному) распределению, и одновременно приближенных эмпирических автокорреляционных функций различных функциональных форм. В частности, можно определить TES процессы с различными автокорреляционными функциями, тем самым контролируя (оценивая) их степень. Решение статистики равновесного времени ожидания в очереди GI/G/1 обычно требует сложной расчетной процедуры. Для нахождения функции времени ожидания (3) необходимо воспользоваться обратным преобразованием Лапласа функции посредством интегрирования, учитывая, свойства дельта-функции [1] (например, ИУ Линдли для частного случая) (3) Для оценки параметров приближенного среднего времени ожидания в качестве альтернативы вычислению среднего времени ожидания рассматривается приближение большого трафика. Из работы [7] когда GI/G/1 имеем очередь при большом трафике, а именно аппроксимация среднего времени ожидания (4) (4) где - коэффициенты вариации интервалов поступления времени и времени обслуживания соответственно [12]. В [7] исследована эффективность предлагаемого приближения путем сравнения с моделированием. Проведено сравнение точности аппроксимации двумя способами: масштабный метод усреднения и аппроксимация , изменялись три типа параметров в системе TES+/G/1. Рассмотрены частоты поступления со значениями и Данные частоты соответствуют средней загрузке и тяжелой загрузке системы, соответственно, поскольку среднее значение службы всегда было равным единице. Параметр пачечности должен быть различен по диапазону значений надлежащим выбором параметров . Значения определяют сильный эффект пачечности, в то время как имеет вторичный эффект. В результате рассмотрены четыре среднесрочных распределения времени обслуживания: Exponential, Erlang, Deterministic, MCE2 и MMPP (Markov-modulated Poisson processes) [7], где получены результаты для среднего времени ожидания СМО TES+/G/1. Аппроксимация в виде суммы затухающих экспонент Анализ сетевого трафика проводился с использованием сети связи, в которой при передаче в глобальную сеть через коммутатор были получены данные, имеющие один Uplink. Пропускная способность абонентского канала изменялась с помощью программного обеспечения коммутатора, а порт, являющийся пограничным для этого коммутатора, имел конфигурацию зеркалирования, что позволяло производить захват всего трафика, проходящего в глобальную сеть. Uplink к узлу агрегации был занижен по скорости, а именно скорость передачи была ограничена до 60 и 80 Мбит/с. Основываясь на имеющихся исследованиях трафика при загрузках со значениями и , и полученных распределений согласно их гистограмме, были рассмотрены случаи системы СМО G/G/1: система типа P/W/1 и W/P/1, где символы и означают соответственно распределения Парето и Вейбулла. Распределение Парето и Вейбулла, соответственно, имеют вид: ; (5) , (6) где - параметр формы; - масштабный параметр. Уравнение Линдли имеет следующий общий вид [1]: , (7) где - функция распределения времени ожидания требования в очереди; - ядро, связывающее произвольную функцию распределения вероятностей интервалов времени между поступлениями соседних требований и произвольную функцию распределения длительности обслуживания требований . Заметим, что само ИУ Линдли выведено в предположении независимости элементов последовательности интервалов времени между заявками и интервалов времени обработки заявок. Известно, что для СМО G/G/1 возможен спектральный метод решения ИУ Линдли, если для плотностей вероятностей и , соответствующих распределениям и использовать аппроксимацию в виде суммы затухающих экспонент [3-4]. При этом и имеют представления, соответственно: (8) (9) где . Среднее время ожидания пакета в очереди для вышеприведенных примеров находится согласно известному свойству характеристической функции (10) По результатам моделирования была проведена проверка соответствия параметров генерируемого узлом-отправителем потока заданным параметрам с использованием программы EasyFit. Рассматривался случай с частотой поступления или интенсивностью . Данная частота соответствуют средней загрузке системы, соответственно, поскольку среднее значение интенсивности обслуживания всегда равно единице. При рассмотрении СМО TES+/G/1 (распределение интервалов времени между поступления TES+ и длительностей обслуживания MGE2) с параметрами: ; После вычисления по масштабному методу усреднения и аппроксимация , среднее время ожидания пакета получилось равным Если рассмотреть при той же средней загрузке полученные гистограммы статистических параметров снятого трафика (см. рисунок 1) имеем соответствие системе W/P/1. Интервалы времени между пакетами распределены по закону Вейбулла с параметрами: а для длин пакетов распределением Парето с параметрами После аппроксимации распределений СМО W/P/1 в виде суммы затухающих экспонент для поиска решения ИУ Линдли среднее время ожидания пакета получилось равным Рассмотрен случай при пиковой загрузке системы при интенсивности СМО TES+/G/1 (MMPP (Markov-modulated Poisson processes)) [7], где получены результаты для среднего времени ожидания. СМО MMPP с параметрами: После вычисления по масштабному методу усреднения и аппроксимации (7), среднее время ожидания пакета получилось равным Далее (11) где - вектор от ; ; ; ; находятся из алгоритма [13]. Если рассмотреть при том же значении загрузки полученные гистограммы статистических параметров снятого трафика (рис.1) имеем соответствие системе W/P/1. Интервалы времени между пакетами распределены по закону Вейбулла с параметрами: , а для длин пакетов распределением Парето с параметры: После аппроксимации распределений СМО W/P/1 в виде суммы затухающих экспонент для поиска решения ИУ Линдли среднее время ожидания пакета получилось равным Заключение В статье представлены методики определения среднего времени ожидания в очереди СМО G/G/1: масштабный метод усреднения и аппроксимация , а также аппроксимацию в виде суммы затухающих экспонент для поиска решения ИУ Линдли. При этом в качестве модуля транспортного уровня выбран модуль TCP, а интенсивность поступления пакетов равна и Погрешность решения ИУ Линдли спектральным методом в сравнении с результатами [7] составляет при порядка 4%, а при - до 14%, что вполне приемлемо. Такая погрешность может быть связана с идеализацией исходных распределений временных параметров рассматриваемых моделей, с допущением независимости элементов рассматриваемых последовательностей интервалов времени и с определенными точностями, характерными для любой используемой программы при снятии и обработки сетевого трафика. Захват трафика осуществлялся с помощью программы анализатора трафика Wireshark. Распределения временных параметров были получены в программе анализа данных EasyFit, разработанной для быстрого анализа статистических данных и принятия решения. Проведенное сравнение методов аппроксимации сетевого трафика позволяет оценить среднее время ожидание пакета с использованием статистического анализа данных, что даст возможность повысить качество обслуживания и спрогнозировать поведение трафика.

About the authors

Olga Aleksandrovna Karaulova

Povolzhskiy State University of Telecommunications and Informatics

Email: Olya4369@yandex.ru

Natalia Valerievna Kireeva

Povolzhskiy State University of Telecommunications and Informatics

Email: zeppelinSN@yandex.ru

Liliya Ravilevna Chupakhina

Povolzhskiy State University of Telecommunications and Informatics

Email: garip4ik555@mail.ru

References

  1. Клейнрок Л. Теория массового обслуживания. Пер. с англ. М.: Машиностроение, 1979. - 432 с.
  2. Altiok T., Melamed B., The case for modeling correlation in manufacturing systems // IIE Trans. - 2001. - No 33. - P. 779-791. doi: 10.1023/A:1010949917158.
  3. Kartashevskiy V.G., Kireeva N.V., Buranova M.A. e.a. Approximation of distributions in the problems of the analysis of self-similar traffic // Third International Scientific-Practical Conference Problems of Infocommunications Science and Technology (PIC S&T). - 2016. - P. 105-108.
  4. Карташевский В.Г., Киреева Н.В., Буранова М.А. и др. Моделирование и анализ системы массового обслуживания общего вида с произвольными распределениями временных параметров системы // Инфокоммуникационные технологии. - 2015/ - Т.13. - №3. - С. 252-258. doi: 10.18469/ikt.2015.13.3.03
  5. Livny M., Melamed B., Tsiolis A.K. The impact of autocorrelation on queuing systems // Management Science. - 1993. - 322-339 p. doi: 10.1287/mnsc.39.3.322.
  6. Patuwo B.E., Disney R.L., McNickle D.C. The effects of correlated arrivals on queues // IIE Trans. - 1993. - P. 105-110. doi: 10.1080/07408179308964296.
  7. Jagerman D.L., Balcıoglu B., Altiok T. e.a. Mean waiting time approximations in the G/G/1 // Queue Queueing Systems. - 2004. - P. 481-506. doi: 10.1023/B:QUES.0000027996.28824.89
  8. Jagerman D.L., Melamed B., Willinger W. Stochastic modeling of traffic processes (invited chapter) // Frontiers in Queueing, Models and Applications in Science and Engineering, ed. Dshalalow J.H. - CRC Press, Boca Raton, FL, 1997. - P. 271-320.
  9. Melamed B. An overview of TES processes and modeling methodology // Performance Evaluation of Computer and Communications Systems, eds. Donatiello L., Nelson R. // Lecture Notes in Computer Science (Springer, New York), 1993. - P. 359-393.
  10. Jagerman D.L., Melamed B. The transition and autocorrelation structure of TES processes Part II // Special cases, Stochastic Models. - 1992. - P. 499-527. doi: 10.1080/15326349208807236.
  11. Melamed B. TES: A class of methods for generating autocorrelated uniform variates // ORSA J. Computing 3. - 1991. - P. 317-329. doi: 10.1287/ijoc.3.4.317.
  12. Shantikumar J.G., Buzacott J.A. On the approximation to the single server queue, Internat. J. Prod. Res., 1980. - P. 761-773. doi: 10.1080/00207548008919705.
  13. Fischer W., Meier-Hellstern K. The Markov-modulated Poisson process (MMPP) cookbook // Performance Evaluation 18. - 1992. - P. 149-171. doi: 10.1016/0166-5316(93)90035-S.

Statistics

Views

Abstract - 18

PDF (Russian) - 1

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2018 Karaulova O.A., Kireeva N.V., Chupakhina L.R.

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