RESEARCH AND COMPARISON OF DUAL SYSTEMS E2/M/1 AND M/E2/1

Full Text

Abstract

This article presents the comparative results of original research on dual E2/M/1 and M/E2/1 systems with second order exponential and erlangian input distributions. By Kendall’s definition, these systems belong to the classes G/M/1 and M/G/1, respectively. In queuing theory, the systems M/G/1 and G/M/1 are widely used. Investigations of G/M/1 systems are particularly relevant due to the fact that there is still no solution in the final form in the general case, with arbitrary laws of the distribution of intervals of the input flow. Using a higher order erlangian distribution is difficult to derive a solution for the average waiting time due to increasing computational complexity. For such distribution laws, the classical spectral decomposition method for solving the Lindley integral equation for G/G/1 systems allows one to obtain a solution in closed form. The E2/M/1 system is applicable when the coefficient of variation of the arrival intervals is equal 1/ 2 to the coefficient of variation of the service time equal to 1, and the system M/E2/1 is applicable when the coefficient of variation of the interval of receipt is 1 and the coefficient of variation of the service time is equal 1/ 2. To derive solutions, the classical method of spectral decomposition of the solution of the Lindley integral equation is used. The results of numerical simulation indicate a slight difference in the considered dual systems due to the relatively small coefficients of variation of the used distribution laws. In the case of other laws of distributions, dual systems G/M/1 and M/G/1 will give rather different results.

Full Text

В настоящее время не существует аналитических методов для точного определения характеристик системы массового обслуживания (СМО) общего вида G/M/1 или G/M/m, в отличие от СМО общего вида M/G/1, для которой известна формула Полячека - Хинчина. Статья посвящена исследованию и сравнению двойственных СМО вида E2/M/1 и M/E2/1 с эрланговским и экспоненциальным входными распределениями. Первая система относятся к типу G/M/1, а вторая - M/G/1. По определению системы называются двойственными, когда закон распределения интервалов входного потока одной системы (первая позиция в трехпозиционной системе Кендалла) становится законом распределения времени обслуживания для другой системы (вторая позиция в указанной системе). Так, в системах E2/M/1 и M/E2/1 закон распределения входного потока E2 первой системы становится законом обслуживания второй системы. В теории СМО исследования G/M/1 особо акG/M/1 особо ак/M/1 особо акM/1 особо ак/1 особо актуальны в связи с тем, что до сих пор не существует решения в конечном виде для общего случая распределения интервалов входного потока. Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) составляет важную часть теории систем G/G/1. Для записи интегрального ИУЛ введем следующие обозначения: ( ) Wy - функция распределения вероятностей времени ожидания требования в очереди; ( ) () C u P u u = <  - аналогичная функция для случайной величины uxt = -  ; x  - случайное время обслуживания требования; t  - случайный интервал времени между поступлениями требований. Форма ИУЛ выглядит как ( ) ( ) ( ), 0; 0, 0. y W y u dC u y Wy y -∞  -≥=   <  ∫ (1) При кратком изложении метода спектрального разложения решения ИУЛ будем придерживаться подхода и символики автора теории СМО [2]. Для этого как () As ∗ и () Bs ∗ обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения ( ) ( ) * * 1 A s B s - ⋅ - представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) ( ) ( ) * * 1 / , A s B s s s +- - ⋅ - =ψ ψ где ψ и ( ) s-ψ - некоторые дробно-рациональные функции от s. Функции ( ) s+ψ и ( ) s-ψ должны удовлетворять следующим условиям согласно [2]: - для ( ) Re 0 s > функция ( ) s+ψ является аналитической без нулей в этой полуплоскости; - для ( ) Re sD < функция ( ) s-ψ является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия: ( ) lim / Dt t a t e - →∞ <∞. Кроме того, функции ( ) s+ψ и ( ) s-ψ должны обладать следующими свойствами: ( ) ( ) ,Re 0 lim 1; ss s s + →∞ > ψ = ( ) ( ) ,Re lim 1 s s D s s - →∞ < ψ = - . (2) Теперь остается применить метод спектрального разложения к рассматриваемым системам. Постановка и решение задачи для системы E2/М/1 В статье ставится задача качественного и количественного сравнения результатов для двойственных систем E2/M/1 и M/E2/1 по среднему времени ожидания в очереди. Для проведения сравнительного анализа приведем решения для обеих систем, полученные методом спектрального разложения ИУЛ. В системе E2/М/1 время поступления требований задано функцией плотности ( ) 22 4 t a t te-λ = λ , (3) преобразование Лапласа которой имеет вид ( ) 2 * 2 2 A s s λ =  λ+  . (4) Время обслуживания распределено с функцией плотности ( ) t b t e -µ=µ , (5) а ее преобразование Лапласа имеет вид ( ) * Bs s µ = µ+ . (6) Для применения метода спектрального разложения воспользуемся результатами [2] для систем общего вида G/М/1, к которым принадлежит система E2/M/1. Выражение для спектрального разложения решения ИУЛ для системы G/М/1 заG/М/1 за/М/1 задается в виде [2]: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ** * 1 1 * 1 , s A s B s s A s s s s s s s s s + - ψ - - = = ψ  µ - - -µ + =  + +µ   (7) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ** * 1 1 * 1 , s A s B s s A s s s s s s s s s + - ψ - - = = ψ  µ - - -µ + =  + +µ   где 1 ss = - - единственный отрицательный корень уравнения ( ) * 0. s A s +µ-µ - = Выражение в первых скобках (5) не имеет ни плюсов, ни нулей в области Re( , ) 0 ≤s кроме 0 s = и 1 ss = - [2]. Поэтому за функцию () s+ψ исходя из условий (1)-(2) примем выражение во вторых скобках, так как его нули 0 s = , 1 ss = - и полюс s =-µ лежат в области Re( 0 )s ≤ , а за функцию ( ) s-ψ - выражение в первых скобках ( ) ( ) 1ss ss s+ + ψ= +µ ; ( ) ( ) ( ) 1 * s s s s s A s- -+ ψ= +µ-µ - . Для окончательного построения функции ( ) s-ψ подставим в ее выражение ( ) * As -= 22 2 s λ =  λ+  Тогда функция ( ) s-ψ примет вид ( ) ( ) ( ) ( )( ) ( )( ) ( )( ) ( ) 1 22 2 1 2 22 1 1 2 2 [4 2 2 ( 4 ) 4 ( ) 22 /] , s s s s ss s s s ss s s s s s s s s s s - -+ ψ= = +µ-µ λ λ- - + λ- = = + µ- λ + λ λ-µ - + λ- λ- = = - + - - так как квадратное уравнение, полученное из знаменателя 2 ( 4 ) 4 ( ) 0 ss + - λ + λ λ-µ = µ , имеет один отрицательный корень 2 1 ( 4 )/2 [( 4 )/2] 4 ( )s - = - µ- λ - µ- λ + λ µ-λ и один положительный корень ) ( ( ) 2 2 (4 )/2 [ 4 /2] 4s = λ-µ + µ- λ + λ µ-λ . В случае стабильной системы при λ<µ выполнено условие 4 ( ) 0 λ µ-λ > . Теперь выполнение условий (1) и (2) метода спектрального разложения для построенных функций ( ) s+ψ и ( ) s-ψ очевидно. Это подтверждает и рисунок 1, где отображены нули и полюсы отношения ( ) ( ) / ss +- ψψ на комплексной s-плоскости для исключения ошибок построения спектрального разложения. На рисунке 1 полюсы отмечены крестиками, а нули - кружками. Рисунок 1. Нули и полюсы функции ( ) ( ) / ss +- ψψ для системы E2/M/1 Далее по методике спектрального разложения найдем константу K: ( ) 11 00 lim lim ss s s s sK ss + →→ ψ + = = = +µ µ . Построим функцию ( ) s+Φ , через которую найдем преобразование Лапласа функции плотности времени ожидания: ( ) ( ) ( ) * 1 1 * () ss W s s s ss+ +µ = Φ = µ+ . Производная от функции ( ) * Ws со знаком минус в точке 0 s = : ( ) * 0s dW s ds = -= ( ) ( ) 1 1 1 22 1 0 () s s s s s s ss =  µ + - +µ µ = - µ+   = 22 11 22 11 11 .ss ss µ - µ = = - µµ Тогда среднее время ожидания для системы E2/M/1: 11/ 1/ Ws = - µ , (8) где 2 1 ( 4 )/2 [( 4 )/2] 4 ( ),s = µ- λ + µ- λ + λ µ-λ абсолютное значение корня 1 s- выражается через параметры распределений (3) и (4). Для практического применения формулы (8) в качестве входных параметров для системы E2/М/1 будем использовать числовые характеристики распределений (3) и (4), а именно средние значения интервалов между поступлениями требований и времени обслуживания и коэффициенты вариаций этих интервалов: 1/ λ τ = λ , 1/ , µ τ = µ 1/ 2c λ = , 1 cµ = . Задав эти числовые характеристики, методом моментов определяем параметры распределений (3)-(4) , λ . µ Решение для системы М/E2/1 и его сравнение с формулой Полячека - Хинчина В этом случае функция плотности распределения для интервалов поступления имеет вид ( ) t a t e -λ=λ , (9) а для времени обслуживания ( ) 22 4 t b t te-µ = µ . (10) Преобразование Лапласа (9) и (10) есть ( ) * As s λ = λ+ , ( ) 2 * 2 2 Bs s  µ = µ+  . Тогда спектральное разложение решения ИУЛ для системы М/E2/1 имеет вид ( ) ( ) ( ) ( ) ( )( ) 2 ** 2 2 2 11 2 44 . 2 A s B s ss s s s ss  λµ - × - = × - = λ- µ+   + µ-λ + µ µ-λ = λ- µ+ Квадратный трехчлен в числителе разложения ( ) ( ) 22 44 ss + µ-λ + µ -λµ , где ( )40 µ µ-λ > и ( ) 40 µ-λ > при µ>λ в случае стабильной системы, имеет два действительных отрицательных корня 1 s- , 2 s- : ( ) ( ) ( ) 2 1 4 /2 [ 4 /2] 4s - = - µ-λ + µ-λ - µ µ-λ , ( ) ( ) ( ) 2 2 4 /2 [ 4 /2] 4s - = - µ-λ - µ-λ - µ µ-λ . Тогда окончательно спектральное разложение будет иметь вид: ( ) ( ) ( )( ) ( )( ) 12 22 s s s s s s s ss + - ψ + + = ψ λ- µ+ . (11) Нули и полюсы этого разложения показаны на рисунке 2: полюсы отмечены крестиками, а нули - кружками. Рисунок 2. Нули и полюсы функции ( ) ( ) / ss +- ψψ для системы М/E2/1 Исходя из правил построения функций ( ) s+ψ и ( ) s-ψ (1)-(2) выбираем ( ) ( )( ) ( ) 12 2 , 2 s s s s s s s+ ++ ψ= µ+ ( ) . ss- ψ =λ- Необходимая для получения решения константа ( ) ( ) 12 220 4 lim 1 . 44s s ssK s + → ψ µ µ-λ = = = = -ρ µµ Далее строим функцию ( ) ( ) ( )( ) ( )( ) 2 12 12 sKs s s s s s s+ + -ρ µ+ Φ = = ψ + + , откуда следует, что преобразование Лапласа функции плотности времени ожидания в системе М/E2/1 ( )( ) 2 * 12 12 * s W s s s ssss+ -ρ µ+ = Φ = ++ . (11) В связи с тем, что система М/E2/1 относится к классу М/G/1, воспользуемся результатом для систем данного класса. Уравнение Полячека - Хинчина для преобразования Лапласа функции плотности времени ожидания для системы М/G/1 имеет вид ( ) ( )( ) * * 1 . s Ws s B s -ρ = -λ+λ (12) С учетом равенства преобразования Лапласа ( ) 2 * 2 2 Bs s  µ = µ+  после его подстановки в (12) получим, что ( ) ( )( ) ( )( ) 2 * 12 12 s Ws ssss -ρ µ+ = ++ . Тем самым подтверждено, что преобразование Лапласа функции плотности времени ожидания для системы М/G/1 в случае СМО М/E2/1 совпадает с выражением (11). Среднее время ожидания в системе М/G/1 даG/1 да/1 дается формулой Полячека - Хинчина [2]: ( ) 2 21 W µ λτ = -ρ , (13) где λ - интенсивность входного потока, ρ - коэффициент загрузки системы, 2 µτ - второй начальный момент времени обслуживания. Для распределения E2 второй начальный момент времени обслуживания 22 3/ 2 ) (µ τ = µ , тогда среднее время ожидания в системе М/E2/1: ( ) 3 41 W ρ = µ -ρ . (14) Сравнительные расчеты среднего времени ожидания для систем E2/M/1 и M/E2/1 Для того чтобы лучше оценить количественную разницу между рассматриваемыми двойственными системами, проведем вычислительные эксперименты для среднего времени ожидания по формулам (1), (7) и (11) соответственно. Выше было отмечено, что формулы (1) и (7) дают идентичные результаты. В таблице 1 приведены результаты расчетов для рассмотренных систем для случаев малой загрузки системы ρ = 0,1; средней загрузки ρ = 0,5 и высокой загрузки ρ = 0,9. Здесь ρ - коэффициент загрузки, определяемый отношением среднего времени обслуживания к среднему интервалу поступлений /µλ ρ= τ τ . Для удобства вычислений принято нормированное время обслуживания в обеих системах 1 1 - µ τ =µ =. Таблица 1. Расчет среднего времени ожидания для систем Н2/M/1 и M/H2/1 Входные параметры Среднее время ожидания ρ для системы E2/M/1 для системы M/E2/1 0,1 0.030 0,083 0,5 0,618 0,750 0,9 6,588 6,750 Данные таблицы 1 свидетельствуют о незначительном различии рассмотренных двойственных систем в связи с сравнительно небольшими коэффициентами вариаций используемых законов распределений. В случае других законов распределений двойственные системы G/M/1 и M/G/1 будут давать достаточно отличающиеся результаты. Результаты расчетов хорошо согласуются с данными [9]. Заключение Основная характеристика для СМО - это среднее время ожидания в очереди, так как все остальные характеристики: время задержки, средняя длина очереди, количество требований в системе и другие являются производными от нее. Результаты по среднему времени ожидания в очереди для систем E2/M/1 и M/E2/1 получены одним и тем же методом спектрального разложения решения ИУЛ [1]. Полученные результаты показывают, насколько отличаются эти две двойственные системы, и свидетельствуют о незначительном различии рассмотренных двойственных систем в связи со сравнительно небольшими коэффициентами вариаций используемых законов распределений.
×

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

References

  1. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. 2016. № 1. С. 16-26.
  2. Клейнрок Л. Теория массового обслуживания/ пер. с англ. М.: Машиностроение, 1979. 432 с.
  3. Тарасов В.Н., Горелов Г.А., Ушаков Ю.А. Восстановление моментных характеристик распределения интервалов между пакетами входящего трафика // Инфокоммуникационные технологии. 2014. Т. 12. № 2. С. 40-44.
  4. Анализ входящего трафика на уровне трех моментов распределений временных интервалов / В.Н. Тарасов [и др.] // Информационные технологии. 2014. Т. 12. № 9. С. 54-59.
  5. Тарасов В.Н., Бахарева Н.Ф., Горелов Г.А. Математическая модель трафика с тяжелохвостным распределением на основе системы массового обслуживания Н2/М/1 // Инфокоммуникационные технологии. 2014. Т. 12. № 3. С. 36-41.
  6. Myskja A. An improved heuristic approximation for the GI/GI/1 queue with bursty arrivals // Teletraffic and datatraffic in a Period of Change - ITC-13. Elsevier Science Publishers, 1991. P. 683-688.
  7. Тарасов В.Н., Бахарева Н.Ф., Липилина Л.В. Математическая модель телетрафика на основе системы G/M/1 и результаты вычислительных экспериментов // Информационные технологии. 2016. Т. 14. № 2. С. 121-126.
  8. Whitt W. Approximating a point process by a renewal process: two basic methods // Operation Research. 1982. Vol. 30. No. 1. P. 125-147.
  9. Кругликов В.К., Тарасов В.Н. Анализ и расчет сетей массового обслуживания с использованием двумерной диффузионной аппроксимации // Автоматика и телемеханика. 1983. Т. 44. № 8. С. 74-83.
  10. Тарасов В.Н., Бахарева Н.Ф., Ахметшина Э.Г. Анализ системы массового обслуживания E2/E2/1 с запаздыванием // Инфокоммуникационные технологии. 2018. Т. 16. № 3. С. 277-282.

Statistics

Views

Abstract: 61

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2019 Tarasov V.N.

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