Teletraffic mathematical model based on Erlang and hypererlang distributions

Full Text

Статья посвящена анализу систем массового обслуживания (СМО) 22 / /1HE E с гиперэрланговским 2 HE и эрланговским E2 входными распределениями. В открытом доступе авторам не удалось обнаружить результаты для среднего времени ожидания требований в очереди в такой СМО. Из теории СМО известно, что среднее время ожидания является главной характеристикой, по которой, например, оценивают задержки пакетов в сетях пакетной коммутации при их моделировании с помощью СМО. Рассматриваемая СМО относится к типу G/G/1. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, к тому же нельзя получить решения для таких систем в конечном виде для общего случая. Законы распределений Вейбулла или гамма наиболее общего вида, которые обеспечивают диапазон изменения коэффициентов вариаций от 0 до ∞ в зависимости от величины их параметров, не позволяют их применять в теории массового обслуживания. Поэтому остается использовать другие частные законы распределений. В исследовании систем G/G/1 важную роль играет метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) и большинство результатов в теории СМО получены именно с помощью данного метода. Метод спектрального разложения решения ИУЛ составляет важную часть теории систем G/G/1. Для записи ИУЛ введем следующие обозначения [1]: () Wy - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; ( ) ( ) C u P u u = <  - ФРВ случайной величины . uxt = -  Здесь x  - случайное время обслуживания требования; t  - случайная величина: интервал времени между поступлениями требований. Используемая [1] форма ИУЛ выглядит как ( ) ( ) ( ), 0; y W y W y u dC u y -∞ = - ≥ ∫ ( ) 0, Wy= 0. y< При изложении метода спектрального разложения решения ИУЛ будем придерживаться классического подхода и символики [1]. Для этого через () As ∗ и () Bs ∗ обозначим преобразования Лапласа ФРВ интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения *( ) *( ) 1 A s B s -- представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: *( ) *( ) 1 A s B s - - = ( )/ ( ), ss +- ψψ где ψ и () s-ψ - некоторые дробно-рациональные функции от s. Функции () s+ψ и () s-ψ должны удовлетворять следующим условиям [1]: - для Re(s) 0 > функция () s+ψ является аналитической без нулей в этой полуплоскости; - для () Re sD < функция () s-ψ является аналитической без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия: ( )/ . lim Dt t a t e - →∞ <∞ Кроме того, функции () s+ψ и () s-ψ должны обладать следующими свойствами: () ,0 () 1; s Re lim s s s + →∞ > ψ = (1) , () 1() . Re lim s s D s s - →∞ < ψ = - (2) Теперь остается применить метод спектрального разложения к рассматриваемой системе. Постановка задачи Необходимо вывести формулу для среднего времени ожидания для рассматриваемой системы 22 / /1HE E и подтвердить адекватность построенной математической модели путем численного моделирования в пакете Mathcad. Вывод решения для среднего времени ожидания проводится методом спектрального разложения решения ИУЛ. Решение для системы HE2 / E2 / 1 В системе 22 / /1HE E интервалы времени между поступлениями требований заданы функцией плотности 12 22 22 12 ( ) 4 4(1 ) , tta t p te p te -λ -λ = λ + - λ (3) преобразование Лапласа которой имеет вид: 22 * 12 12 22( ) (1 ) . 22 A s p p ss     λλ = + -     +λ +λ     (4) Время обслуживания распределено с функцией плотности 22 ( ) 4 , tb t te -µ= µ (5) а ее преобразование Лапласа имеет вид: 2 * 2 () 2 .Bs s  µ = +µ  (6) Тогда спектральное разложение решения ИУЛ для системы 22 / /1HE E *( ) *( ) 1 A s B s - - = ( )/ ( ) ss +- =ψ ψ примет вид: ( ) 2 1 1 2 2 2 2 2( 2 ) () 22 1 1. 22 p s p s s s s + -   ψλ = +   ψ λ -     λµ +- -  λ - µ+      (7) Первый сомножитель (7) примет вид: ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) 22 12 12 2 2 2 22 1 2 1 2 1 22 12 2 2 2 2 2 1 2 1 2 2 22 12 2 0 1 2 22 12 22 1 22 16 16 4 22 1 16 16 4 22 , 22 pp ss p s s ss p s s ss a a s a s ss      λλ +- =      λ- λ-       λ λ - λ λ + λ = + λ - λ - - λ λ - λ λ + λ += λ - λ - -+ = λ - λ - где промежуточные параметры ( ) ( ) 22 0 1 2 1 1 2 1 2 22 2 1 2 16 , 16 1 , 41. a a p p a p p = λ λ = λ λ λ + - λ    = λ + - λ  Продолжая разложение (7), получим: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( )( )( )( ) ( ) ( ) ( ) 2 2 2 12 2 2 2 12 5432 4 3 2 1 0 2 2 2 12 12 2 345 2 2 2 12 0 1 2 2 2 2 12 222 ( ) 4 ( ) () 222 222 . 2 (2 ) ( ( 2 2 2 2 ) ) s a a s a s s s s s s s s s c s c s c s s cs c s s s s s s s s s s s s s s s s s s s s + - λ - λ - µ+ -= λ - λ - µ+ - - - - - - = = λ - λ - µ+ - + + - - - = λ - λ - ψ µ - + = - ψ λ - + µ+ λ - µ Окончательно спектральное разложение решения ИУЛ для системы 22 / /1HE E имеет вид: ( )( )( )( )( ) ( ) ( ) ( ) 12345 2 2 2 12 . 222 () () s s s s s s s s s s s s ss ss + - ψ = ψ - + + - - - = λ - λ - µ+ (8) Исследование многочлена в числителе разложения (7) и определение его корней является основным моментом метода спектрального разложения решения ИУЛ. Поэтому выпишем многочлен пятой степени в числителе разложения (8) 5432 4 3 2 1 0 .s c s c s c s cs c - - - - - (9) Его коэффициенты, сформированные с помощью символьных операций Mathcad, равны ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) 2 0 1 1 2 1 2 1 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 1 2 2 2 2 + λ λ - µλ λ = - λ +λ +µ - µ λ +λ - λ λ = λ +λ -µ ca c c c и выражаются через параметры распределений (3) и (5), которые предстоит еще определить. Многочлен (9) имеет два действительных отрицательных корня 1, s- 2 s- и три положительных корня 3, s 4, s 5 s (либо вместо последних один действительный положительный и два комплексно сопряженных с положительной вещественной частью) в случае стабильной системы, то есть когда / 1. µλ ρ= τ τ < Исследование знака младшего коэффициента 0c показывает, что 0 0 c > всегда в случае стабильной системы, когда 0 1. <ρ< С учетом знака «минус» перед 0 c в многочлене (9) это также подтверждает предположение о наличии таких корней многочлена. Далее, с учетом условий (1) и (2) строим рациональные функции () s+ψ и () :s-ψ 2 12 ( ) ( )( )/(2 ) , s s s s s s s+ ψ = + + µ+ так как нули многочлена (9): 0, s = 1, ss = - 2 ss = - и двукратный полюс 2 s =-µ лежат в области ) ,( 0Re s ≤ ( ) ( ) ( ) ( )( )( ) 22 12 345 22 , ss s s s s s s s- λ - λ - ψ = - --- так как ее нули и полюсы лежат в области ( ) ,Re s D> определенной условием (1). Теперь выполнение условий (1) и (2) метода спектрального разложения для построенных функций () s+ψ и () s-ψ очевидно. Далее по методике спектрального разложения найдем константу K: ( )( ) ( ) 1212 2 200 ( , 42 ) lim lim ss ssss K s ss s s + →→ ++ψ = = = µ+µ где 1, s 2 s - абсолютные значения отрицательных корней 1, s- 2. s- Постоянная K определяет веK определяет веK роятность того, что поступающее в систему требование застает ее свободной. Для нахождения преобразования Лапласа ФРВ времени ожидания построим функцию ( ) ( )( ) 2 12 2 12 2 . 4 () () ss sK ss s s sss+ + +µ Φ = = ψ µ + + Отсюда преобразование Лапласа функции плотности времени ожидания *( ) ( ) Ws ss += Φ будет равно ( ) ( )( ) 2 * 12 2 12 2 .( 4 ) ss s W s s s s s +µ = µ + + (10) Для нахождения среднего времени ожидания найдем производную от функции *() Ws со знаком минус в точке 0 :s = * 120 1 .( 1) 1 s ds s s sdW = - = + - µ Окончательно среднее время ожидания для системы 22 / /1HE E 12 111 .W ss =+- µ (11) Из выражения (10) при необходимости также можно определить моменты высших порядков времени ожидания, например вторая производная от преобразования (10) в точке 0 s = дает второй начальный момент времени ожидания, что позволяет определить дисперсию времени ожидания. Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания вокруг его среднего значения [10], тем самым получим возможность определения джиттера через дисперсию. Это является важным результатом для анализа трафика, чувствительного к задержкам. Для практического применения формулы (11) необходимо определить числовые характеристики распределений (3) 2 HE и (5) 2, E а через них - неизвестные параметры этих распределений. Для этого воспользуемся свойством преобразований Лапласа (4) и (6) воспроизведения моментов и запишем начальные моменты до второго порядка для распределения (3): ( ) 12 1 , pp λ - τ = + λλ ( )2 22 12 13 . 2 pp λ -  τ = +  λλ  (12) Рассматривая равенства (12) как запись метода моментов, найдем неизвестные параметры распределения (3) 1, λ 2, λ . p Система двух уравнений (12) при этом является не доопределенной, поэтому к ней добавим выражение для квадрата коэффициента вариации: 22 2 2 () () λλ λ λ τ-τ = τ c (13) как связующее условие между (12). Кроме того, коэффициент вариации будем использовать в расчетах в качестве входного параметра системы. Исходя из вида первого уравнения (12) положим 1 / , 2p λ λ = τ ( ) 2 2 1 / p λ λ = - τ (14) и потребуем выполнения условия (13) [2-3]. Подставив выражения (12) и (14) в (13), получим уравнение четвертой степени относительно неизвестного параметра p: p p c p c p λλ  - + - + + =  Отбросив тривиальные решения 0 p = и 1, p = получим квадратное уравнение ( )22 81 cp λ +- ( ) 2 8 1 3 0, cp λ - + + = решив которое выберем для однозначности больший корень для параметра p: ( ) ( ) 2 2 2 1 31 . 2 81 c p c λ λ +- = + + (15) Отсюда следует, что коэффициент вариации 1/ 2.c λ ≥ Теперь, подставив (15) в (14), определяем все три неизвестных параметра распределения (3) согласно [2]. Для распределения (4) числовые характеристики равны 1/ , µ τ = µ 1/ 2 µ =c [4]. Аналогичную аппроксимацию законов распределений с использованием начальных моментов можно увидеть в [7; 8]. Результаты численного моделирования В таблице приведены данные расчетов для системы 22 / /1HE E для случаев малой, средней и высокой нагрузки 0,1; ρ= 0,5; 0,9. Заметим, что эта система определена для 1/ 2 cλ ≥ и 1/ 2. cµ = Данные расчетов для системы 22 / /1HE E сравниваются с результатами близкой системы 22 / /1, HE где 2 H - гиперэкспоненциальный закон распределения второго порядка. Прочерки в таблице означают, что при данных параметрах система параметрах система па 22 / /1 HE не применима. Коэффициент загрузки ρ в определяется отношением средних интервалов / . µλ ρ= τ τ Расчеты в таблице проведены для нормированного времени обслуживания 1. µ τ= Данные таблицы свидетельствуют о незначительном различии сравниваемых систем в случае средних и высоких нагрузок и более значительных расхождениях при малых нагрузках. Результаты расчетов для системы 22 / /1HE E хорошо согласуются с данными [10] в той области изменения параметров, при которых применима данная система. Заключение В работе получено спектральное разложение решения ИУЛ для системы 22 / /1HE E и через него выведено расчетное выражение для среднего времени ожидания в очереди в такой системе. Это расчетное выражение дополняет известную незавершенную формулу для среднего времени ожидания для систем типа G/G/1. Среднее время ожидания в очереди - это основная характеристика для СМО, так как все остальные характеристики: время задержки, средняя длина очереди, количество требований в системе - являются производными от основной характеристики. Адекватность полученных результатов обеспечена корректным использованием классического метода спектрального разложения, а проведенные вычислительные эксперименты только подтверждают данный факт. Таблица. Результаты экспериментов для СМО

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

O. Kada

Povolzhskiy State University of Telecommunications and Informatics

Samara, Russian Federation

References

Supplementary files