Simulation of Teletrafc Based on E2/HE2/1 System

Full Text

Статья посвящена анализу системы массового обслуживания (СМО) E2/HE2/1 с эрланговским (E2) и с гиперэрланговским (HE2) входными распределениями. В открытом доступе авторам не удалось обнаружить результаты для среднего времени ожидания требований в очереди для такой СМО. Как известно из теории массового обслуживания, среднее время ожидания является главной характеристикой для любых СМО. По этой характеристике, например, оценивают задержки пакетов в сетях пакетной коммутации при их моделировании с помощью СМО. Рассматриваемая СМО относится к типу G/G/1. В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, к тому же нельзя получить решения для таких систем в конечном виде для общего случая. Законы распределений Вейбулла или Гамма наиболее общего вида, которые обеспечивают диапазон изменения коэффициентов вариаций от 0 до ∞ в зависимости от величины их параметров, не позволяют их использовать в теории массового обслуживания. Поэтому остается применять другие частные законы распределений. В исследовании систем G/G/1 важную роль играет метод спектрального разложения решения интегрального уравнения Линдли и большинство результатов в теории массового обслуживания получены именно с помощью данного метода. Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) составляет важную часть теории систем G/G/1. Для за- G/G/1. Для за- /G/1. Для за- G/1. Для за- /1. Для записи ИУЛ введем следующие обозначения [1]: ( ) Wy - функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; ( ) () Cu Pu u = <  - ФРВ случайной величины ; u xt = -   x  - случайное время обслуживания требования; t  - интервал времени между поступлениями требований. Тогда одна из форм уравнения Линдли выглядит так [1]: ( ) ( ) ( ) d, 0 0, 0 y W y u Cu y Wy y -∞  -≥  =   <  ∫ . При кратком изложении метода спектрального разложения решения ИУЛ будем придерживаться подхода [1]. Для этого через () As ∗ и () Bs ∗ обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения ИУЛ методом спектрального разложения состоит в нахождении для выражения ( ) ( ) * *1 A sB s -⋅ - представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: ( ) ( ) ( ) ( ) * *1 / , A sB s s s +- - ⋅ -=ψ ψ где ( ) s + ψ и ( ) s - ψ - некоторые дробно-рациональные функции от s. Функции ( ) s + ψ и ( ) s - ψ должны удовлетворять следующим условиям согласно [1]: - для ( ) Re s 0 > функция ( ) s + ψ является аналитической без нулей в этой полуплоскости; - для ( ) Re s D < функция ( ) s - ψ - аналитическая без нулей в этой полуплоскости, где D - некоторая положительная константа, определяемая из условия ( ) / lim Dt t at e - →∞ <∞. Кроме того, функции ( ) s + ψ и ( ) s - ψ должны обладать следующими свойствами: ( ) ( ) ,Re 0 lim 1; ss s s + →∞ > ψ = (1) ( ) ( ) ,Re lim 1. s sD s s - →∞ < ψ = - (2) Теперь остается применить метод спектрального разложения к рассматриваемой системе. Постановка задачи В статье ставится задача вывода формулы для среднего времени ожидания для рассматриваемой системы E2/HE2/1 и подтверждения адекватности построенной математической модели путем численного моделирования в пакете Mathcad. Вывод решения для среднего времени ожидания проводится классическим методом спектрального разложения решения ИУЛ, как это показано в [3-6; 13]. Аналогичные подходы к аппроксимации законов распределений использованы в [2; 7-10; 12]. Решение для системы E2/HE2/ 1 В системе E2/HE2/1 интервалы времени между поступлениями требований заданы функцией плотности ( ) 22 , 4 t a t te -λ = λ (3) преобразование Лапласа которой выглядит как: ( ) 2 * 2 . 2 As s λ  =  +λ  (4) Время обслуживания распределено с функцией плотности ( ) ( ) 12 22 22 12 4 41 , tt b t q te q te -µ -µ =µ + -µ (5) а ее преобразование Лапласа имеет вид ( ) ( ) 22 12 12 22 * 1. 22 Bs q q ss   µµ = +-   +µ +µ   (6) Тогда спектральное разложение решения ИУЛ для системы E2/HE2/1 ( ) ( ) * *1 A sB s - ⋅ -= ( ) ( ) / ss +- =ψψ примет вид: ( ) ( ) ( ) 2 22 12 12 2 2 22 1 1. 22 s ss qq ss + - ψ λ  = ×  ψ λ-     µµ × +- -    µ+ µ+     (7) Выражение в квадратных скобках (7) примет вид: ( ) ( ) ( ) ( ) ( ) ( ) 1 2 12 2 22 12 2 01 2 22 12 1 16 16 4 22 , 22 q ss ss b bs bs ss - µµ + µµ + µ += µ+ µ+ ++ = µ+ µ+ где промежуточные параметры 22 0 12 16 , b = µµ ( ) 1 12 1 2 16 [ 1], b qq = µµ µ + - µ ( ) 22 21 2 4[ 1]. bq q = µ+ - µ Продолжая разложение (7), получим: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 22 01 2 22 2 12 22 2 12 22 2 12 5432 4 3 2 10 22 2 12 12345 22 2 12 4( ) (2 ) 2 2 (2 ) 2 2 (2 ) 2 2 () (2 ) 2 2 ( )( )( )( )( ) . (2 ) 2 2 s b bs bs s ss s ss s ss s ss ds ds ds ds d ss s ssssss ss s + - ψ λ ++ = - ψ λ- µ + µ + λ- µ + µ + -= λ- µ + µ + ------ = = λ- µ + µ + - +σ +σ +σ +σ -σ = λ- µ + µ + Окончательно спектральное разложение решения ИУЛ для системы HE2/E2/1 имеет вид ( ) ( ) ( ) ( ) 12345 22 2 12 ( )( )( )( )( ) . (2 ) 2 2 s s ssssss ss s + - ψ = ψ - +σ +σ +σ +σ -σ = λ- µ + µ + (8) Исследование многочлена в числителе разложения (8) и определение его корней являются основным моментом метода спектрального разложения решения ИУЛ. Поэтому выпишем многочлен пятой степени в числителе разложения (8): 5432 4 3 2 10. s ds ds ds ds d ----- (9) Его коэффициенты, сформированные с помощью символьных операций Mathcad, равны: 2 0 12 12 1 2 1 64 [ ( ) 4 ]; db = λµµ µµ -λµ +µ + λ 1 12 1 2 2 22 12 1 2 2 16{4 ( ) [2 ( ) ] 4 }; d b = λµ µ µ +µ - -λ µµ + µ +µ + λ 2 2 1 2 12 2 1 2 12 16 [( ) 2 ] 16( )( ); d = λ µ +µ + µµ - - µ +µ λ +µµ 222 3 1 2 1 2 12 4[ 4 ( ) 4 ]; d =- λ +µ +µ - λ µ +µ + µµ 4 12 4( ), = λ-µ -µ d и выражаются через параметры распределений (3) и (5), которые предстоит еще определить. Многочлен (9) имеет четыре действительных отрицательных корня 1, -σ 2 , -σ 3, -σ 4 -σ (либо два действительных отрицательных корня и два комплексно сопряженных с отрицательными действительными частями) и один положительный корень 5. σ Исследование знака младшего коэффициента 0 d показывает, что 0 0 d > всегда в случае стабильной системы, когда 0 1. <ρ< С учетом знака минус перед 0 d в многочлене (6) это также подтверждает предположение о наличии таких корней многочлена. C учетом условий [1] строим рациональные функции ( ) s + ψ и ( ): s - ψ 1234 22 12 ( )( )( )( ) () , (2 ) (2 ) ss s s s s ss + +σ +σ +σ +σ ψ= µ+ µ+ так как нули многочлена (9) 0, s = 1, s = -σ 2 , s = -σ 3, s = -σ 4 s = -σ и двукратные полюсы 1 2 s =-µ и 2 2 s =-µ лежат в области ) , ( 0 Re s ≤ ( ) 2 5 2 () , () s s s - λ- ψ=- -σ так как ее нули и полюсы лежат в области ( ) , Re s D > определенной условием [1]. Теперь выполнение обоих условий метода спектрального разложения для построенных функций ( ) s + ψ и ( ) s - ψ очевидно. Далее по методике спектрального разложения найдем константу K: ( ) ( ) ( ) ( ) ( ) 0 1234 22 0 12 1234 22 12 lim () () lim 22 , 16 s s s K s ssss ss + → → ψ = = +σ +σ +σ +σ = = +µ +µ σσσσ = µµ где 1, σ 2 , σ 3, σ 4 σ - абсолютные значения отрицательных корней 1, -σ 2 , -σ 3, -σ 4. -σ Постоянная K определяет вероятность того, что поступающее в систему требование застает ее свободной. Для нахождения преобразования Лапласа ФРВ времени ожидания построим функцию ( ) ( ) ( ) ( ) ( ) ( ) 1234 22 12 22 12 1234 16 22 . () () K s ss ss ssss + + σσσσ Φ= = × ψ µµ +µ +µ × +σ +σ +σ +σ Отсюда преобразование Лапласа ФРВ времени ожидания ( ) * () Ws s s + = ⋅Φ будет равно ( ) ( ) ( ) ( ) ( ) * 22 1234 1 2 22 12 1 2 3 4 22 . 16 () () Ws ss ssss = σσσσ +µ +µ = µµ +σ +σ +σ +σ (10) Для нахождения среднего времени ожидания вычислим производную от функции ( ) * W s со знаком минус в точке 0: s = ( ) * 12 412 0 3 111111 . s dW s ds = -= σσ +++-- σ σµµ Окончательно среднее время ожидания для системы E2/HE2/1: 12 4 2 3 1 111111 . W +++-- µ σ σ σµ = σ (11) Из выражения (10) при необходимости также можно определить моменты высших порядков времени ожидания, например, вторая производная от преобразования (10) в точке 0 s = дает второй начальный момент времени ожидания, что позво- ляет определить дисперсию времени ожидания. Учитывая определение джиттера в телекоммуникациях как разброс времени ожидания вокруг его среднего значения [10], тем самым получим возможность определения джиттера через дисперсию. Это является важным результатом для анализа трафика, чувствительного к задержкам. Для практического применения формулы (11) необходимо определить числовые характеристики распределений (3) E2 и (5) HE2, а через них - неизвестные параметры этих распределений. Для распределения Е2 среднее значение 1 , - λ τ=λ ко- эффициент вариации 1/ 2. cλ = Для нахождения числовых характеристик до второго порядка для распределения (5) воспользуемся свойством преобразования Лапласа * () Bs воспроизведения моментов и запишем начальные моменты: ( ) 12 1 , q q µ - τ= + µµ ( ) 2 22 12 1 3 . 2 q q µ -  τ= +  µµ  (12) Рассматривая равенства (12) как запись метода моментов, найдем неизвестные параметры распределения (5) 1, µ 2 , µ . q Система двух уравнений (12) при этом является недоопределенной, поэтому к ней добавим выражение для квадрата коэффициента вариации: 22 2 2 () , () c µµ µ µ τ-τ = τ (13) как связующее условие между (12). Кроме того, коэффициент вариации будем использовать в расчетах в качестве входного параметра системы. Исходя из вида первого уравнения (12), положим 1 2/ , q µ µ= τ 2 2(1 ) / q µ µ= - τ (14) и потребуем выполнения условия (13) [2; 3]. Подставив выражения (12) и (14) в (13), получим уравнение четвертой степени относительно неизвестного параметра q: 22 2 (1 )[8(1 ) 8(1 ) 3] 0. q q cq cq µµ - + - + += Отбросив тривиальные решения 0 q = и 1, q = получим квадратное уравнение 22 8(1 ) cq µ +- 2 8(1 ) 3 0, µ - + += cq решив его, выберем для однозначности больший корень: 2 2 2(1 ) 3 1 . 2 8(1 ) c q c µ µ +- = + + (15) Отсюда следует, что коэффициент вариации 1/ 2. cµ ≥ Теперь, подставив (15) в (14), определяем все три неизвестных параметра распределе- ния (5). Аналогичную аппроксимацию законов распределений с использованием начальных моментов можно увидеть в [3-5; 13]. Таблица. Исходные данные и результаты вычислительного эксперимента для СМО E2/HE2/1 Входные параметры Среднее время ожидания ρ cµ для системы E2/HE2/1 для системы E2/H2/1 0,1 0,71 0,018 - 2 0,160 0,160 4 0,796 0,795 8 3,452 3,448 0,5 0,71 0,395 - 2 2,102 2,094 4 8,092 8,082 8 32,089 32,079 0,9 0,71 4,380 2 20,082 20,072 4 74,075 74,065 8 290,074 290,063 Результаты численного моделирования В таблице приведены данные расчетов для системы E2/HE2/1 для случаев малой, средней и высокой нагрузки 0,1; ρ= 0,5; 0,9. Заметим, что эта система определена для 1/ 2 cλ = и 1/ 2. cµ ≥ Данные расчетов для системы E2/HE2/1 сравниваются с результатами близкой системы E2/H2/1, где H2 - гиперэкспоненциальный закон распределения второго порядка. Прочерки в таблице означают, что при данных параметрах система E2/H2/1 неприменима. Коэффициент загрузки ρ определяется отношения средних интервалов /. µλ ρ=τ τ Результаты, приведенные в таблице, получены для нормированного времени обслуживания 1. µ τ= Данные таблицы свидетельствуют о незначительном различии сравниваемых систем, так как сами распределения HE2 и H2 мало отличаются друг от друга. Результаты для системы E2/HE2/1 хорошо согласуются с данными [10] в той области изменения параметров, при которых применима данная система, что свидетельствует об адекватности разработанной модели. Заключение В работе получено спектральное разложение решения интегрального уравнения Линдли для системы E2/HE2/1 и через него выведена расчетная формула для среднего времени ожидания в очереди в такой системе. Это расчетное выражение дополняет известную незавершенную формулу для среднего времени ожидания для систем типа G/G/1. Среднее время ожидания в очереди - это основная характеристика для систем массового обслуживания, так как все остальные характеристики: время задержки, средняя длина очереди,количество требований в системе и др. - являются производными от основной характеристики. Адекватность полученных результатов обеспечена корректным использованием классического метода спектрального разложения, а проведенные вычислительные эксперименты только подтверждают данный факт.

About the authors

V. N Tarasov

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russia Federation

N. F Bakhareva

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russia Federation

O. Kada

Povolzhskiy State University of Telecommunications and Informatics

Email: tarasov-vn@psuti.ru
Samara, Russia Federation

References

Supplementary files