SOLUTION FOR QUEUING SYSTEMS E2/M/1 WITH ORDINARY AND SHIFTED INPUT DISTRIBUTIONS

Abstract

In queuing theory, the studies of the systems G/M [g1] 1 and G/G/1 are particularly relevant because there still exist no final solution for the general case. In this article we present results on (QS) G/G[F2] /1 and G/G/1 queuing systems (QS): E2/M/1 with Erlang and exponential input distributions, and also systems with delay in time, respectively. For the system with time delay the Erlang distribution of the second order shifted to the right from the zero point is selected as the input distribution along with the shifted exponential distribution. For such distribution laws, the classical method of spectral decomposition of the solution of the Lindley’s integral equation for systems G/G/1 allows to obtain a closed-form solution. It is shown that in a system with time delay the average waiting time in queue is less than in the usual system. This is explained by the fact that the time shift reduces the coefficients of variation of the intervals between the arrival and the service time, and as known from queuing theory, the average waiting time is related to these coefficients of variation by a quadratic dependence. The E2/M/1 system works only for the arrival intervals variation factor equal to and the service time variation factor equal to 1, while the system allows us to work with the arrival intervals variation factor in the range of (0, ) and the service time variation factor in the range of (0, 1), which expands the scope of these systems. For deriving the solutions, the classical method of spectral decomposition of the solution of the Lindley’s integral equation was used.

Full Text

Введение Статья посвящена исследованию систем массового обслуживания (СМО) E2/M/1 с эрланговским входным распределением 2-го порядка и с запаздыванием во времени. Первая система относятся к типу G/M/1, а вторая G/G/1. В теории СМО исследования систем G/G/1 и G/M/1 актуальны в связи с тем, что до сих пор не существует решения в конечном виде для общего случая. В работе авторов [1] впервые приведены результаты для системы M/M/1 с запаздыванием во времени и сдвинутыми экспоненциальными входными распределениями. Показано, что среднее время ожидания требования в очереди в системе M/M/1 с запаздыванием во времени меньше, чем в классической системе M/M/1 при одинаковом коэффициенте загрузки за счет того, что коэффициенты вариации времен поступления и обслуживания становятся меньше единицы при параметре запаздывания . Результаты [1] совместно с классикой теории СМО [2] позволяют распространить метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) также на сдвинутое эрланговское распределение. Метод спектрального разложения решения ИУЛ составляет важную часть теории систем G/G/1. Для записи ИУЛ введем следующие обозначения: - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; - ФРВ случайной величины ; - случайное время обслуживания требования; - случайный интервал времени между поступлениями требований. Тогда нужная нам форма уравнения Линдли будет выглядеть как . При изложении метода решения ИУЛ будем придерживаться подхода и символики [2]. Для этого через и обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение , где и некоторые рациональные функции от s, которые можно разложить на множители. Функции и должны удовлетворять следующим условиям [2]. 1. Для функция является аналитической без нулей в этой полуплоскости; 2. Для функция является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия . (1) Кроме того, функции и должны обладать следующими свойствами: . (2) Построенные функции и должны удовлетворять условиям (1)-(2). Система E2/М/1 и вывод решения для среднего времени ожидания Для системы E2/М/1 законы распределения интервалов входного потока и времени обслуживания задаются функциями плотности вида: ; (3) . (4) При таком задании функций (3), решения для среднего времени ожидания для системы E2/М/1 в классике по теории СМО [2-3] авторами не найдено, поэтому это решение находим классическим методом спектрального разложения решения ИУЛ аналогично [4]. Такой подход позволяет определить не только среднее время ожидания, но и моменты высших порядков времени ожидания. Тогда, учитывая определение джиттера в телекоммуникациях как разброс времени ожидания от его среднего значения [5], получим возможность определения джиттера через дисперсию. Преобразования Лапласа функций (3) и (4) будут соответственно . Для применения метода спектрального разложения воспользуемся результатами [2] для систем общего вида G/М/1, к которым принадлежит система E2/M/1. Выражение для спектрального разложения решения ИУЛ для системы G/М/1 задается в виде (5) где - единственный отрицательный корень уравнения Выражение в первых скобках (5) не имеет ни полюсов, ни нулей в области кроме и [2]. Поэтому, учитывая условия (1) и (2) за функцию примем выражение во вторых скобках, так как его нули , и полюс лежат в области , а за функцию - выражение в первых скобках: , . Для окончательного построения функции подставим в ее выражение ; так как квадратное уравнение , полученное из знаменателя, имеет один отрицательный корень: и один положительный корень: . В случае стабильной системы при выполняется условие . Теперь выполнение условия (1) для построенных функций и очевидно. Это подтверждает и рисунок 1, где отображены нули и полюса отношения на комплексной s-плоскости для исключения ошибок построения спектрального разложения. На рисунке 1 полюсы отмечены крестиками, а нули - кружками. Рисунок 1. Нули и полюсы функции для системы E2/M/1 Проверка выполнения условий (2) дает , , следовательно, эти условия также выполнены. Далее по методике спектрального разложения найдем константу K: . Далее построим функцию : Отсюда преобразование Лапласа функции плотности времени ожидания . Для нахождения среднего времени ожидания найдем производную от функции со знаком минус в точке s = 0: В окончательном виде среднее время ожидания для системы E2/M/1 равно , (6) где , абсолютное значение корня . Система E2/М/1 с запаздыванием Рассмотрим СМО, для которой законы распределения входного потока и времени обслуживания заданы функциями плотности как ; (7) . (8) Такую систему мы уже обозначили Утверждение. Спектральное разложение решения ИУЛ для системы имеет точно такой же вид, что и для системы E2/М/1. Доказательство. Преобразование Лапласа функции (7) есть , а функции (8): . Из предыдущего раздела следует, что для системы E2/М/1 спектральное разложение имеет вид . Для системы имеем Здесь показатели степени у экспонент обнуляются, и тем самым операция сдвига в спектральном разложении нивелируется. Спектральные разложения решения ИУЛ, а также преобразование Лапласа функции плотности времени ожидания (5) для обеих систем E2/М/1 и совпадают, что и требовалось доказать. Далее нам необходимо определить числовые характеристики распределений (7) и (8). Они нужны в свою очередь для определения неизвестных параметров распределений (7) и (8) по известному методу моментов. Определение числовых характеристик распределения и Для их определения воспользуемся свойством преобразования Лапласа функции плотности воспроизводить моменты: Отсюда среднее значение интервала между поступлениями требований: Найдя вторую производную от преобразования Лапласа функции (7) при s = 0 определим второй начальный момент интервала между поступлениями . Тогда коэффициент вариации . Второй начальный момент интервала между поступлениями , откуда Отсюда коэффициент вариации . (9) Поступив аналогично для распределения с преобразованием Лапласа функции (8), получим среднее значение времени обслуживания , а коэффициент вариации . (10) Заметим, что для распределения Е2: . Сравнивая результаты числовых характеристик для распределений Е2 и можно увидеть разницу между ними, полученную ввиду сдвига законов распределений на Коэффициент вариации для распределения уменьшается при сдвиге в раз по сравнению с коэффициентом для распределения Е2. Для времени обслуживания по закону коэффициент вариации уменьшается при сдвиге в раз по сравнению с коэффициентом для распределения M. Учитывая, что среднее время ожидания в системе G/G/1 связано с коэффициентами вариаций времени между поступлениями требований и времени обслуживания квадратичной зависимостью, в системе с запаздыванием время ожидания будет меньше, чем в обычной системе. Теперь исходя из полученных параметров распределения для системы время ожидания для нее определяем из выражения (6), где параметры , . Теперь задав в качестве входных параметров для расчета системы полученные выше значения можно рассчитать среднее время ожидания по выражению (6) для диапазонов изменения коэффициентов вариаций и , определяемыми выражениями (9) и (10) соответственно в зависимости от величины параметра сдвига . Ниже в таблице 1 приведены данные расчетов для системы , полученные при малой средней и высокой нагрузки и параметре сдвига . Для сравнения в правой колонке приведены данные для обычной системы E2/М/1. Таблица 1. Результаты экспериментов для СМО и E2/М/1 Входные параметры Среднее время ожидания t0 Для Для E2/E2/1 0,1 0,64 0,1 0,9 0,000 0.030 0,67 0,5 0,5 0,005 0,70 0,9 0,1 0,023 0,71 0,99 0,01 0,029 0,5 0,39 0,1 0,9 0,003 0,618 0,53 0,5 0,5 0,132 0,67 0,9 0,1 0,491 0,70 0,99 0,01 0,605 0,9 0,13 0,1 0,9 0,055 6,588 0,39 0,5 0,5 1,609 0,64 0,9 0,1 5,322 0,70 0,99 0,01 6,456 С уменьшением значения параметра среднее время ожидания в системе стремится к среднему времени ожидания в системе E2/М/1. Данные таблицы 1 подтверждают тот факт, что за счет уменьшения коэффициентов вариации и из-за ввода параметра сдвига уменьшается среднее время ожидания в системе . Заключение Полученные результаты приводят к следующим выводам. 1. Операция сдвига во времени с одной стороны, приводит к увеличению загрузки системы с запаздыванием. Для системы с запаздыванием загрузка увеличивается в раз по сравнению с обычной системой E2/М/1. 2. Операция сдвига во времени с другой стороны, уменьшает коэффициенты вариаций интервала между поступлениями и времени обслуживания требований. В связи с тем, что среднее время ожидания в системе G/G/1 связано с коэффициентами вариаций интервалов поступления и обслуживания квадратичной зависимостью, среднее время ожидания в системе с запаздыванием будет меньше, чем в обычной системе при одинаковом коэффициенте загрузки. Например, для системы при загрузке и параметре сдвига t0=0,9 коэффициент вариации интервалов поступления уменьшается с 1 для обычной системы до 0,13, коэффициент вариации времени обслуживания уменьшается с до 0,1, а время ожидания уменьшается с 6,59 единиц времени для обычной системы до 0,055 единиц времени. 3. Изложенные результаты справедливы только для одинаковых параметров сдвига t0 для распределения интервалов между поступлениями требований и времени обслуживания.
×

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

Eleonora Gazinurovna Akhmetshina

Povolzhsky State University of Telecommunications and Informatics

Email: elyamalusha@mail.ru

References

  1. Тарасов В.Н. Бахарева Н.Ф., Блатов И.А. Анализ и расчет системы массового обслуживания с запаздыванием // Автоматика и телемеханика - 2015. - № 11. - С.51-59.
  2. Клейнрок Л. Теория массового обслуживания. Пер. с англ. М.: Машиностроение, 1979. - 432 с.
  3. Brannstrom N. A Queueing Theory analysis of wireless radio systems - Appllied to HS-DSCH. Lulea university of technology, 2004. - 79 p.
  4. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. - 2016. - №1. - С.16-26.
  5. RFC 3393 IP Packet Delay Variation Metric for IP Performance Metrics (IPPM)// URL: https://tools.ietf.org/html/rfc3393 (д.о. 26.02.2016).
  6. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А. Математическая модель трафика с тяжелохвостным распределением на основе системы массового обслуживания Н2/М/1 // Инфокоммуникационные технологии. - 2014. - Т.12. - №3. - С.36-41.
  7. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А., Малахов С.В. Анализ входящего трафика на уровне трех моментов распределений временных интервалов // Информационные технологии - 2014. - №9. - С.54-59.
  8. Тарасов В.Н., Бахарева Н.Ф., Липилина Л.В. Математическая модель телетрафика на основе системы G/M/1 и результаты вычислительных экспериментов // Информационные технологии. - 2016. - №2. - С.121-126.
  9. Тарасов В.Н., Горелов Г.А., Ушаков Ю.А. Восстановление моментных характеристик распределения интервалов между пакетами входящего трафика // Инфокоммуникационные технологии - 2014. - Т.12. - №2. - С.40-44.
  10. 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: 76

PDF (Russian): 20

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2018 Tarasov V.N., Bakhareva N.F., Akhmetshina E.G.

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