QUEUEING SYSTEM HE2/HE2/1

Abstract

The article is devoted to the analysis of the queuing system HE2/HE2/1 type G/G/1 with hyper Erlangen input distributions of the second order. The goal is to obtain a solution for the average waiting time for requests in the queue. To achieve it, the classical method of spectral decomposition of the solution of Lindley integral equation is used. For the practical application of the results obtained, the method of moments is used. It turns out that the hyper Erlangen distribution law HE2, same as the hyperexponential law H2, which has three parameters, can be defined by both the first two moments and the first three moments. The article proposes an approximation mechanism for the hyper Erlangen law of arbitrary distributions using the well-known method of moments. The choice of such a law of probability distribution is due to the fact that its coefficient of variation is larger and covers a wider range than the hyperexponential distribution law, for which the coefficient of variation is greater than one. The method of spectral decomposition of the solution of the Lindley integral equation for the QS HE2/HE2/1 allows one to obtain a closed-form solution. Thus, the system under consideration allows working with coefficients of variations in the intake intervals and service time in the range ( , ∞), which expands the field of application of QS. The resulting formula for the average waiting time for the HE2/HE2/1 system complements and extends the well-known formula for the average waiting time in the G/G/1 system with arbitrary laws of the distribution of input flow intervals and service time.

Full Text

Введение. Постановка задачи Статья посвящена исследованию системы массового обслуживания (СМО) HE2/HE2/1 типа G/G/1 с гиперэрланговскими входными распределениями второго порядка. В теории массового обслуживания исследования систем G/G/1 особо актуальны в связи с тем, что до сих пор не существует решения в конечном виде для общего случая. Начнем с определения гиперэрланговского закона распределения. Распределение с плотностью , где , называют гиперэрланговским порядка R и обозначают HER [1-2]. Гиперэрланговское распределение представляет собой вероятностную смесь нормированных распределений Эрланга порядка k с функцией плотности вида и является наиболее общим распределением неотрицательных непрерывных случайных величин, поскольку имеет коэффициент вариации в интервале от 0 до ∞ [3]. Ограничимся гиперэрланговскими входными распределениями 2-го порядка с функцией плотности . Ниже будет показано, что коэффициент вариации для такого распределения . Это распределение в литературе обозначают как НE2. Оно содержит три параметра (0 < p < 1, ) и таким образом, позволяет аппроксимировать произвольные входные распределения на уровне трех первых моментов с использованием известного метода моментов. Ниже будет показано, что распределение НE2, как и гиперэкспоненциальное H2 может определяться как двумя, так и тремя первыми моментами. В статье ставится задача нахождения решения для времени ожидания требований в очереди в СМО HE2/HE2/1 и построения механизма аппроксимации произвольных законов распределений гиперэрланговским. Вывод решения для системы HE2/HE2/1 В СМО HE2/HE2/1 интервалы между соседними требованиями входного потока распределены по закону: , (1) а время обслуживания - . (2) Преобразование Лапласа (1) имеет вид: , (3) а функции (2) - . (4) Перейдем к определению спектрального разложения решения интегрального уравнения Линдли (ИУЛ) в виде отношения двух рациональных функций в случае распределений (1)-(2) с учетом преобразований Лапласа (3)-(4), где сами функции и в отдельности могут быть определены только после получения полного разложения. Получим следующее выражение для отношения: Первый сомножитель в правой части в квадратных скобках представим в виде: где ; ; . Аналогично представим второй сомножитель: где , , . Тогда искомое выражение для спектрального разложения будет иметь вид: Многочлен в числителе в правой части такого разложения (5) как правило всегда имеет один нуль [1]. В данном случае свободный член разложения также равен нулю: . В числителе дроби в правой части разложения (5) получили многочлен 8-й степени , коэффициенты которого равны: (6) . Данные коэффициенты получены с помощью выполнения трудоемких символьных операций математического пакета Mathcad над числителем разложения (5), так как числитель разложения включает 90 слагаемых и вручную привести подобные члены после раскрытия скобок проблематично. Видимо поэтому в литературе, включая web-ресурсы, нет упоминаний о такой системе. Выделим многочлен в числителе (5): , (7) так как определение его корней и работа с ними является важным моментом метода спектрального разложения решения ИУЛ. Исследование многочлена (7) с коэффициентами (6) с использованием формул Виета подтверждает наличие четырех отрицательных действительных корней либо двух отрицательных действительных корней и двух комплексно-сопряженных корней с отрицательными вещественными частями, а также трех положительных действительных корней либо одного положительного и двух комплексно сопряженных корней с положительными вещественными частями. Исследование знака младшего коэффициента многочлена (7) показывает, что . С учетом знака минус в многочлене перед коэффициентом , формулы Виета не противоречат факту наличия четырех отрицательных корней у многочлена (7). В общем случае, наличие таких корней следует из существования и единственности спектрального разложения [1] или же факторизации [4]. Обозначив корни многочлена (7) с отрицательными вещественными частями для удобства через , а с положительными вещественными частями через , отношение окончательно можно разложить на следующие множители: (8) Тогда с учетом условий, налагаемых на функции и , за функцию примем , так как нули многочлена (7): , , и полюсы , лежат в области . За функцию примем . Таким образом, построенные функции и удовлетворяют всем условиям метода спектрального разложения. Далее по методике спектрального разложения определим постоянную которая физически определяет вероятность того, что поступающее в систему требование застает ее свободной. Функция позволяет найти преобразование Лапласа функции распределения вероятностей времени ожидания : Тогда преобразованием Лапласа для функции плотности времени ожидания будет функция , то есть . (9) Среднее время ожидания в очереди равно значению производной от преобразования Лапласа (11) функции плотности со знаком минус в точке : . Окончательно, среднее время ожидания в очереди для СМО НE2/НE2/1: . (10) Из выражения (9) также можно определить дисперсию времени ожидания. Вторая производная от преобразования (9) в точке дает второй начальный момент времени ожидания, что позволяет определить дисперсию времени ожидания. Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания [8], тем самым получим возможность его определения через дисперсию. Этот результат является важным для анализа трафика, чувствительного к задержкам. Аппроксимация законов распределения на уровне двух первых моментов Воспользуемся свойством преобразования Лапласа воспроизведения моментов и запишем начальные моменты до второго порядка для распределения (1): (11) . (12) Рассматривая равенства (11)-(12) как запись метода моментов, найдем неизвестные параметры распределения (1) . Система уравнений (11)-(12) при этом является не доопределенной, поэтому к ней добавим выражение для квадрата коэффициента вариации , (13) как связующее условие между (11) и (12). Кроме того, коэффициент вариации будем использовать в расчетах в качестве входного параметра системы. Исходя из вида уравнения (11) положим , (14) и потребуем выполнения условия (13). Подставив выражения (11)-(12) и частное решение (14) в (13) и решив квадратное уравнение относительно параметра p, выберем одно нужное значение: . Отсюда следует, что коэффициент вариации Таким образом, получено частное решение недоопределенной системы уравнений (11) и (12) методом подбора. Аналогично поступив с законом распределения (2), определяем его неизвестные параметры . Такой же подход к аппроксимации законов распределения гиперэкспоненциальным распределением применен в работах [5-7]. Таким образом, гиперэрланговский закон распределения может определяться полностью двумя первыми моментами и перекрывать весь диапазон изменения коэффициента вариации от до , что шире, чем у гиперэкспоненциального распределения . Учитывая тот факт, что распределение НE2 является трехпараметрическим, аппроксимацию можно выполнить и на уровне трех первых моментов. Для этого запишем выражения для начального момента третьего порядка, полученное через преобразование Лапласа (3): (15) Теперь присоединив уравнение (15) к уравнениям моментов (11) и (12) и решив систему 3-х нелинейных уравнений с тремя неизвестными в пакете Mathcad находим все три параметра распределения (1). Аналогично определяем три параметра распределения (2). Как показано в работе [5] на примере гиперэкспоненциальных входных распределений, аппроксимация с использованием двух первых моментов в отличие от трех моментов, может занижать величину среднего времени ожидания до 10% в зависимости от загрузки и величины третьего момента. Практическое применение полученных результатов Ниже в таблицах 1-2 приведены результаты расчетов в пакете Mathcad среднего времени ожидания для системы НE2/НE2/1 по полученной расчетной формуле (12) для случаев малой, средней и высокой нагрузки . Коэффициент загрузки в расчетах определяется отношением средних интервалов времени обслуживания и интервалов между требованиями . Расчеты проведены для нормированного времени обслуживания . В таблице 1 приведены результаты для коэффициентов вариаций меньших единицы, а в таблице 2 - больших единицы. При этом для сравнения использованы результаты для СМО E2/E2/1 и H2/H2/1 соответственно. Как видно из таблиц 1-2, результаты в обеих случаях достаточно близки. Кроме того, полученные результаты хорошо согласуются с данными [11]. Таблица 1. Результаты для времени ожидания при коэффициентах вариаций , меньших единицы Входные параметры Среднее время ожидания ρ для системы HE2/HE2/1 для системы E2/E2/1 0,1 (0,71; 0,71) 0,02 0,02 0,5 (0,71; 0,71) 0,40 0,39 0,9 (0,71; 0,71) 4,40 4,36 Таблица 2. Результаты для времени ожидания при коэффициентах вариаций , больших единицы Входные параметры Среднее время ожидания ρ для системы HE2/HE2/1 для системы H2/H2/1 0,1 (2,2) 0,34 0,45 (4,4) 1,68 1,78 (8,8) 7,16 7,11 0,5 (2,2) 3,98 4,04 (4,4) 16,53 16,13 (8,8) 66,73 64,18 0,9 (2,2) 36,21 36,20 (4,4) 145,31 144,83 (8,8) 580,56 577,86 Заключение В работе получено аналитическое решение для среднего времени ожидания для системы HE2/HE2/1 с использованием символьных операций пакета Mathcad. Этот результат дополняет и расширяет известную формулу для среднего времени ожидания для систем типа G/G/1. Используя предложенный подход, помимо среднего времени ожидания, можно определить дисперсию и моменты высших порядков времени ожидания. Полученный результат, с одной стороны, дополняет систему Н2/Н2/1, а с другой стороны, расширяет диапазон изменения коэффициентов вариаций интервалов поступлений и времени обслуживания от до . Для убедительности, данные расчетов для системы HE2/HE2/1 сравниваются с результатами для систем E2/E2/1 и Н2/Н2/1, что демонстрирует их достаточную близость. Полученный результат с успехом может быть применен в современной теории телетрафика, где задержки пакетов входящего трафика играют первостепенную роль. Для этого необходимо знать числовые характеристики интервалов входящего трафика и времени обслуживания на уровне двух первых моментов, что не вызывает трудностей при использовании современных анализаторов трафика [7].
×

About the authors

Veniamin Nikolaevich Tarasov

Povolzhsky State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru

Nadezhda Fedorovna Bakhareva

Povolzhsky State University of Telecommunications and Informatics

Email: bakhareva-nf@psuti.ru

Othmane Kada

Povolzhsky State University of Telecommunications and Informatics

Email: otman2333@gmail.com

References

  1. Клейнрок Л. Теория массового обслуживания. Пер. с англ. - М. Машиностроение, 1979. - 432 с.
  2. Brannstrom N. A Queueing Theory analysis of wireless radio systems - Appllied to HS-DSCH. Lulea university of technology, 2004. - 79 p.
  3. Алиев Т.И. Основы моделирования дискретных систем. - СПб: СПбГУ ИТМО, 2009. - 363 с.
  4. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. - М.: Изд-во РУДН, 1995. - 529 с.
  5. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. - 2016. - №1. - С.16-26.
  6. Тарасов В.Н., Карташевский И.В. Способы аппроксимации входных распределений для системы G/G/1 и анализ полученных результатов // Системы управления и информационные технологии. - 2015. - № 3. - С. 182-185.
  7. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А., Малахов С.В. Анализ входящего трафика на уровне трех моментов распределений временных интервалов // Информационные технологии. - 2014. - №9. - С.54-59.
  8. HTTPS: URL //tools.ietf.org/html/rfc3393. RFC 3393 IP Packet Delay Variation Metric for IP Performance Metrics (IPPM) (д.о. 26.02.2016).
  9. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А. Математическая модель трафика с тяжелохвостным распределением на основе системы массового обслуживания Н2/М/1 // Инфокоммуникационные технологии. - 2014. - Т.12. - №3. - С. 36-41.
  10. Тарасов В.Н. Бахарева Н.Ф. Обобщенная двумеpная диффузионная модель массового обслуживания типа GI/G/1 // Телекоммуникации - 2009. - № 7. - С. 2-8.
  11. Whitt W. Approximating a point process by a renewal process: two basic methods // Operation Research, 30. - 1982. - No. 1. - P. 125-147.

Statistics

Views

Abstract: 73

PDF (Russian): 22

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2019 Tarasov V.N., Bakhareva N.F., Kada O.

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