RESEARCH OF QUEUING SYSTEM WITH DISPLACED EXPONENTIAL INPUT DISTRIBUTIONS

Full Text

Abstract

The problem of determining characteristics of a queuing system (QS) produced by two flows with displaced exponential distributions is considered. Such a system is considered for the first time. For the classical M/M/1 system the coefficients of variation of the input flow intervals and the service time are equal to one, and for the new system they become less than one and we get a non-Markov queueing model of G/G/1 type. By varying the time displaced parameter in the input distributions, it is possible to change the values of the variation coefficients of the arrival intervals and the service time. Thus, the displaced exponential distributions widen the range of the arrival time variation coefficients and service time, thereby expanding the scope of the new queuing system. The problem is solved by the classical method of queuing theory - the method of spectral decomposition of the solution of the Lindley integral equation. It is shown that the load in such a system is higher than in the classical M/M/1 system, and the average waiting time is shorter because of reduced variation coefficients of the intervals between the receipt and the service time. It is known that the average waiting time is related to the coefficients of variation by a quadratic dependence. Thus, the article presents a solution for the new G/G/1 system. The possible applications for this new QS have yet to be assessed.

Full Text

К системам с запаздыванием в науке и технике можно отнести системы автоматического регулирования, системы автоматического и дистанционного управления, телеметрии и др. В литературе по теории систем массового обслуживания (СМО) и в интернет-ресурсах нет упоминаний о таких системах со смещенными во времени входными распределениями. В основе описания любой СМО, в том числе СМО с запаздыванием, лежит понятие рекуррентного потока [1], определяемого совокупностью функций распределения 12 ( ) ( ) ... F t F t = = = ( ) ... ( )n F t F t = = = между поступающими требованиями. Далее мы рассмотрим случай, когда СМО образована двумя потоками, определяемыми функциями ( ) 0() 0 0 1,; 0, 0 , tt e t t Ft tt -γ - -≥ =  ≤< где 0, γ> и потоки имеют одинаковое время запаздывания 0. t В качестве математической модели таких систем предлагается рассматриваемая ниже СМО с запаздыванием. Рассмотрим СМО, на вход которой поступают требования, случайные интервалы между кото рыми распределены с функцией плотности (см. также рисунок 1) вида ( ) ( ) 0 0 0 ,; 0, 0 . tt e t tat tt -λ - λ≥=  ≤<  (1) Аналогично распределено и время обслуживания: ( ) ( ) 0 0 0 ,; 0, 0 . tt e t tbt tt -µ - µ≥=  ≤<  (2) Рисунок 1. График функции плотности с запаздыванием (1) Функции плотности (1) и (2) являются сдвинутыми вправо от нулевой точки на величину 0t экспоненциальными распределениями с двумя параметрами ( ) 0, tλ и ( ) 0 ,, tµ причем µ λ< (см. рисунок 1). Таким образом, мы имеем СМО с запаздыванием во времени на величину 0 0. t > Заметим, что законы распределения (1) и (2) содержит два параметра, следовательно, они могут быть описаны двумя первыми моментами. Новую СМО, в отличие от классической, обозначим M /M /1. -- Постановка и способ решения задачи Методом спектрального разложения решения интегрального уравнения Линдли (ИУЛ) требуется получить результат по среднему времени ожидания в очереди, а также требуется оценить, как операция сдвига во времени скажется на характеристиках новой СМО M /M /1, -- и чем эта внешне схожая с классической СМО М/М/1 система будет от нее отличаться. Для последующего применения метода спектрального разложения к решению данной задачи сначала определим числовые характеристики интервала поступления требований и времени обслуживания. Для этого воспользуемся преобразованием Лапласа функций плотности (1)-(2): ( ) 0 * tseAs s -λ = +λ ; (3) ( ) 0 * tseBs s -µ = +µ . (4) Первая производная функции (3) ( ) ( ) ( ) 00 0 2 * ts ts dA s t e s e ds s -- -λ +λ -λ = +λ , а ее значение со знаком минус в точке 0: s = ( ) 0 2 10 02 * . s dA s ds t t = - -= λ +λ = =λ + λ По свойству преобразования Лапласа правая часть последнего выражения равна среднему значению интервалов между соседними требованиями входного потока 1 0 t-λ τ =λ + . (5) Из равенства (5) следует, что интенсивность поступления требований 1/ λ ′ λ = τ в СМО M /M /1 -- определяется через параметры распределения (1) как 0 /(1 ). t′ λ =λ +λ (6) Поступая аналогично с функцией (4), находим среднее время обслуживания в системе 1 0. t-µ τ =µ + (7) Тогда интенсивность обслуживания требований ′ µ определяется через параметры распределения (2) из равенства (7): 0 /(1 ). t′ µ =µ +µ (8) Таким образом, интенсивности поступления ′λ и обслуживания ′ µ в системе M /M /1 -- напрямую зависят от интенсивностей λ и µ классической системы и параметра сдвига 0. t Загрузка рассматриваемой системы, определяемая отношением интенсивностей поступления (6) и обслуживания (8), возросла в 0 0 1 1 t t +µ +λ раз по сравнению с системой М/М/1: 0 0 (1 ) (1 ) t t ′ λ λ +µ ρ= = ′ µ µ +λ . (9) Из равенств (5) и (7) следует, что в качестве входных параметров системы удобнее использовать средние значения интервалов λ τ и , µτ так как их отношение /µλ ρ= τ τ определяет загрузку СМО. Определим начальный момент второго порядка интервалов поступления. Для этого находим значение второй производной от функции (3) при 0.s = Тогда 22 0 0 2 22 ttλ τ = + + λλ и, с учетом того, что дисперсия интервалов для распределения (1) равна 2, D - λ =λ получим коэффициент вариации интервалов входного потока ( ) 1 0 1. ct - λ = +λ (10) Аналогично определим коэффициент вариации времени обслуживания. Дисперсия этого времени 2, D - µ =µ а коэффициент вариации ( ) 1 0 1. ct - µ = +µ (11) Заметим, что коэффициенты вариации cλ и cµ меньше единицы при 0, t , λ 0. µ> Полученные числовые характеристики позволяют сделать следующие предположения. 1. Операция сдвига во времени приводит к увеличению загрузки системы в 0 0 1 1 t t +µ +λ раз, чем в классической системе М/М/1. 2. В связи с тем, что коэффициенты вариации интервалов поступления cλ и времени обслуживания cµ меньше единицы, мы имеем немарковскую модель массового обслуживания. Среднее время ожидания требования в очереди в такой системе должно быть меньше, чем в системе M/M/1 при одинаковом коэффициенте загрузки, так как cλ и cµ для системы M/M/1 равны единице. 3. Использование функций плотности (1) и (2) позволяет аппроксимировать исходные входные распределения, в отличие от классической СМО, на уровне двух первых моментов. Таким образом, мы выделили основные отличия рассматриваемой системы от классической СМО, но, как оказывается, между ними есть и много общего. Определение среднего времени ожидания в очереди для системы -- M /M /1 на основе метода спектрального разложения ИУЛ Основные характеристики системы G/G/1, как следует из [2], описываются известными из теории случайных процессов интегральными уравнениями типа Винера - Хопфа. Одно из этих уравнений в [2] выведено в форме интегрального уравнения Линдли: ( ) ( ) ( ), 0; 0, 0, y W y u dC u y Wy y -∞  -≥=   <  ∫ (12) где ( ) Wy - функция распределения вероятностей времени ожидания требования в очереди, ( ) Cu - аналогичная функция предельной случайной величины lim n n UU →∞ = = 1; nn xt +- n x - время обслуживания n-го требования ; nC 1 nt + - интервал времени между поступлением требований nC и 1. nC + Важно заметить, что интегральная форма уравнения (12) имеет место только для неотрицательных значений аргумента y, так как для отрицательных значений аргумента функция ( ) 0. Wy≡ Суть решения ИУЛ (12) спектральным методом сводится к тому, чтобы для выражения ( ) ( ) * * 1 A s B s -- (13) найти представление в виде произведения двух множителей, которое давало бы рациональную функцию от s [2]. Таким образом, для нахождения распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) ( ) ( )* * 1 s A s B s s + - ψ - - = ψ , (14) где ( ) s+ψ и ( ) s-ψ - некоторые рациональные функции от s, которые можно разложить на множители. Функции ( ) s+ψ и ( ) s-ψ должны удовлетворять определенным условиям [2]. 1. Для ( ) Re 0 s > функция ( ) s+ψ является аналитической без нулей в этой полуплоскости. 2. Для ( ) Re sD < функция ( ) s-ψ является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия ( ) lim . Dtt at e-→∞ <∞ (15) Кроме того, функции ( ) s+ψ и ( ) s-ψ должны обладать следующими свойствами: ( ) ( ) ( ) ( ) Re 0 lim 1; Re 0 lim 1. äëÿ : äëÿ : S S s s s s s s + →∞ - →∞ ψ - > = ψ - < = - (16) Таким же путем получены решения для систем с гиперэкспоненциальными входными распределениями в работах [3; 6-7]. Определим теперь спектральное разложение (14) для распределений (1)-(2) с учетом преобразований Лапласа (3)-(4). Метод спектрального разложения для решения ИУЛ (12) в этом случае дает ( ) ( ) 00 1 t s t ss ee s s s - + - ψ λµ = - ψ λ- µ+ , где ( ) s+ψ и ( ) s-ψ должны быть рациональными функциями. Выполнив несложные вычисления, получим ( ) ( ) ( )( ) ( )( ) ( ) ( )( ) s s s s s s s s s s + - ψ λµ- λ- µ+ +µ-λ = = ψ λ- µ+ λ- µ+ . Таким образом, показатели степени у экспонент в числителе дроби обнуляются, и тем самым операция сдвига нивелируется. Следовательно, спектральные разложения решения ИУЛ для систем M /M /1 -- и M/M/1 совпадают, так как функция ( ) ( ) ( ) ( )( ) s s s s s s + - ψ +µ-λ = ψ λ- µ+ (17) является спектральным разложением для решения системы М/М/1 [1]. Совпадение разложения (17) с результатом для системы М/М/1 является чисто внешним, так как здесь параметры λ и µ не являются для системы M /M /1 -- интенсивностями поступления и обслуживания соответственно. Далее, следуя [2], в качестве функции ( ) s+ψ выбираем ( ) ( ) ( ) ss s s+ +µ-λ ψ= µ+ , которая не имеет нулей и полюсов в области ( ) Re 0, s > а в качестве функции ( ) , ss- ψ =λ- которая не имеет нулей в области ( ) Re . s <λ Постоянная K определяется из условия: ( ) 00 lim lim 1 sS s sK ss + →→ ψ +µ-λ = = = -λ µ +µ , где параметры λ и µ определяются выражениями (5) и (7) и отношение /λµ не определяет коэффициент загрузки как в случае системы М/М/1. Преобразование Лапласа для функции распределения времени ожидания согласно [2] имеет вид ( ) ( ) ( )( ) ( ) 1 sKs ss+ + -λ µ µ+ Φ = = ψ +µ-λ . Следовательно, преобразование Лапласа функции плотности времени ожидания ( ) ( ) ( )( ) ( ) 1 * s W s s s s+ -λ µ µ+ = Φ = +µ-λ . (18) Найдем первую производную от (18): ( ) ( )( ) ( )( ) ( ) ( ) ( ) 2 2 * 11 1 . dW s ds ss s s = -λ µ +µ-λ - -λ µ µ+ = = +µ-λ -λ -λ µ = +µ-λ Тогда значение первой производной со знаком минус при s = 0 будет равно ( ) ( ) ( ) ( ) 2 0 *1 / s dW s ds = λ -λ µ λµ - = = µ-λµ-λ . Отсюда среднее время ожидания W λµ = µ-λ . (19) Результат (19) полностью совпадает с результатом для системы М/М/1, где 1 W ρµ = -ρ (20) при значении . ρ=λµ Таким образом, формулы для среднего времени ожидания для системы с запаздыванием M /M /1 -- и для системы М/М/1 совпадают при одинаковых значениях параметров λ и , µ создавая при этом разные нагрузки на системы. Это интересный факт сходства двух различных систем. Определение неизвестных параметров рассматриваемых распределений Полученные числовые характеристики распределений (1) и (2) в виде равенств (5), (7), (10) и (11) позволяют определить неизвестные параметры , λ µ и 0. t Запишем их в виде системы уравнений 1 0 1 0 1 0 1 0 , (1 ) , , (1 ) , t tc t tc - λ - λ - µ - µ  λ + = τ  +λ =   µ + = τ   +µ =  (21) где числовые характеристики в правых частях системы будут входными параметрами системы для определения неизвестных параметров. Система (21) является переопределенной, и поэтому мы получим ограничение на входные параметры СМО , λτ , cλ µ τ и . cµ Для решения системы из первого уравнения выразим 0: t 1 0 .t - λ = τ -λ Второе уравнение дает 1/(1 1) , c λλ +λτ - = откуда 1/( ) cλλ λ = τ . (22) Третье уравнение дает 11 , -- λµ µ + τ -λ = τ тогда ( ) 1 1 c µ λ λ µ= τ - τ - . (23) Из четвертого уравнения получим следующее ограничение: ( ) ( ) 1 , 1 1 1 c c c µ λλ µ λ λ = τ- + τ - τ - отсюда ( ) ( ) 1 1 1 , c cc µ λ λ µλ µ τ - τ - = = - - ρ τ где /. µλ ρ= τ τ Окончательно коэффициент вариации времени обслуживания есть ( ) 1 1 . cc µλ = -ρ - (24) Таким образом, входные параметры системы M /M /1: -- , λτ , cλ µ τ и cµ строго связаны соотношением (23). Примеры расчета среднего времени ожидания для системы M-/M-/1 В качестве примера рассмотрим случаи разных нагрузок. Примем следующие значения входных параметров СМО: 1, µ τ= 10 λ τ= и 0,5. cµ = Тогда ограничение (24) при загрузке 0,1 ρ= дает c λ = Далее определим неизвестные параметры λ и . µ Из (22) находим значение 1/9,5 λ = =2/19, а из (23) 1/ 1 10 0,5 () µ = - ⋅ =2. Тогда среднее время ожидания из (19) есть 119/36 19 W = = 1/36. Для сравнения среднее время ожидания для системы М/М/1 при такой же нагрузке 0,1 ρ= и интенсивности обслуживания 1 µ= равно 0,11 1 1 0,9 9 W ρµ = = = -ρ , что в четыре раза больше, чем в системе с запаздыванием M /M /1 -- . В качестве второго примера рассмотрим случай высокой нагрузки: 1, µ τ= 10/9 λ τ= и 0,5.c µ = В этом случае получим загрузку 0,9; ρ= ограничение (24) дает 0,55, cλ = а равенства (22)- (23) - значения 18/11 λ= и 2. µ= Тогда среднее время ожидания 1811 2 18 11 9 2 1811 4 22 4 W ⋅ = = = -⋅ . Система М/М/1 при той же нагрузке дает 0,9 1 9 1 0,9 W = = - . Расчетные данные хорошо согласуются с результатами двухмоментной аппроксимации [8]. Заключение Рассмотренная СМО с запаздыванием M /M /1 -- позволяет рассчитать ее характеристики при коэффициентах вариации интервалов между поступлениями требований cλ и времени обслуживания , cµ меньших единицы при некоторых ограничениях на входные параметры системы. Учитывая тот факт, что основные характеристики СМО, такие как средняя длина очереди, среднее количество требований в системе и другие, являются производными от среднего времени ожидания, они в статье не рассмотрены. Полученные результаты приводят к следующим выводам. 1. Операция сдвига во времени приводит к увеличению загрузки системы в 0 0 1 1 t t +µ +λ раз по сравнению с классической системой М/М/1. 2. В связи с тем, что коэффициенты вариации интервалов поступления cλ и времени обслуживания cµ меньше единицы, мы получили немарковскую модель массового обслуживания G/G/1, для которой существует решение в замкнутой форме. Среднее время ожидания требования в очереди в такой системе меньше, чем в системе M/M/1 при одинаковом коэффициенте загрузки. 3. Использование функций плотности (1)-(2) позволяет аппроксимировать исходные входные распределения в СМО на уровне двух первых моментов, в отличие от классической системы.
×

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

N. F Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

E. G Akhmetshina

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

References

  1. Алиев Т.И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. № 2 (84). С. 88-93.
  2. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979. 432 с.
  3. Тарасов В.Н. Исследование систем массового обслуживания с гиперэкспоненциальными входными распределениями // Проблемы передачи информации. 2016. Т. 52 № 1. С. 16-26.
  4. 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.
  5. Whitt W. Approximating a point process by a renewal process: two basic methods // Operation Research. 1982. Vol. 30. No. 1. P. 125-147.
  6. Тарасов В.Н., Бахарева Н.Ф., Липилина Л.В. Математическая модель телетрафика на основе системы G/M/1 и результаты вычислительных экспериментов // Информационные технологии. 2016. № 2. С. 121-126.
  7. Анализ входящего трафика на уровне трех моментов / В.Н. Тарасов [и др.] // Информационные технологии. 2014. № 9. С. 54-59.
  8. Кругликов В.К., Тарасов В.Н. Анализ и расчет сетей массового обслуживания с использованием двумерной диффузионной аппроксимации // Автоматика и телемеханика. 1983. № 8. С. 74-83.
  9. Тарасов В.Н., Карташевский И.В. Способы аппроксимации входных распределений для системы G/G/1 и анализ полученных результатов // Системы управления и информационные технологии. 2015. № 3.1. С. 182-185.
  10. HTTPS://tools.ietf.org/html/rfc3393. RFC 3393 IP Packet Delay Variation Metric for IP Performance Metrics (IPPM) (дата обращения: 26.02.2016).

Statistics

Views

Abstract: 50

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2019 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