Метод спектрального разложения для анализа системы со сдвинутыми эрланговским и гиперэрланговским распределениями

Обложка

Цитировать

Полный текст

Аннотация

В работе получено спектральное разложение решения интегрального уравнения Линдли для системы массового обслуживания со сдвинутыми эрланговским входным потоком требований и гиперэрланговским распределением времени обслуживания. На его основе выведена расчетная формула для среднего времени ожидания в очереди для этой системы в замкнутой форме. Как известно, все остальные характеристики системы массового обслуживания являются производными от среднего времени ожидания. Полученная расчетная формула дополняет и расширяет известную незавершенную формулу для среднего времени ожидания в очереди в теории массового обслуживания для систем G/G/1. В теории массового обслуживания исследования частных систем типа G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, а также при проектировании и моделировании различных систем передачи данных.

Полный текст

Введение

Данная работа посвящена анализу системы массового обслуживания (СМО) E2/HE2/1 со сдвинутыми эрланговским входным потоком требований и гиперэрланговским распределением 2-го порядка времени обслуживания в системе, которая обозначена E2/HE2/1, где знак «–» означает сдвиг закона распределения вправо от нулевой точки на величину t0. Как известно из теории массового обслуживания, среднее время ожидания является основной характеристикой для любых СМО. По этой характеристике оценивают задержки пакетов в сетях пакетной коммутации при моделировании телетрафика с помощью СМО. Рассматриваемая СМО E2/HE2/1 по символике Кендалла для их классификации относится к типу G/G/1.

В теории массового обслуживания исследования систем G/G/1 актуальны в связи с тем, что они активно используются в современной теории телетрафика, хотя необходимо заметить, что при моделировании активного сетевого оборудования с ограниченным буфером системы с неограниченным временем ожидания могут быть использованы только в первом приближении [9]. В пакетах имитационного моделирования также предусмотрено использование систем G/G/1 при частных законах распределений [10].

Метод спектрального разложения решения интегрального уравнения Линдли (ИУЛ) в исследовании систем G/G/1 играет важную роль, и большинство результатов в теории массового обслуживания получены именно с помощью данного метода. Одна из форм ИУЛ выглядит так [1]:

Wy=yWyudCu, y0;0, y<0,

где Wy – функция распределения вероятностей (ФРВ) времени ожидания требования в очереди; Cu=P(u~<u) – ФРВ случайной величины u~=x~t~, где, в свою очередь, x~ – случайное время обслуживания требования; t~ – случайная величина – интервал времени между поступлениями требований.

При кратком изложении метода решения уравнения Линдли будем придерживаться подхода и символики автора [1]. Для этого через A(s) и B(s) обозначим преобразования Лапласа функций плотности распределения интервалов между поступлениями и времени обслуживания соответственно. Суть решения интегрального уравнения Линдли методом спектрального разложения состоит в нахождении для выражения A*sB*s1 представления в виде произведения двух множителей, которое давало бы рациональную функцию от s. Следовательно, для нахождения закона распределения времени ожидания необходимо следующее спектральное разложение: A*sB*s1=ψ+s/ψs, где ψ+s и ψs – некоторые рациональные функции от s, которые можно разложить на множители. Функции ψ+s и ψs должны удовлетворять следующим условиям согласно [1]:

  1. Для Res>0 функция ψ+s является аналитической без нулей в этой полуплоскости;
  2. Для Res<D функция ψs является аналитической без нулей в этой полуплоскости, где D – некоторая положительная константа, определяемая из условия: limtateDt<.

Кроме того, функции ψ+s и ψs должны обладать следующими свойствами:

lims,Res>0ψ+ss=1;lims,Res<Dψss=1.   (2)

  1. Постановка задачи

В работе ставится задача нахождения решения для среднего времени ожидания требований в очереди в СМО E2/HE2/1 со сдвинутыми эрланговским (E2) и гиперэрланговским (HE2) входными распределениями с использованием классического метода спектрального разложения решения ИУЛ. Для других систем применение этого метода рассмотрено в работах [2; 6–8]. Вопросы аппроксимации законов распределений подробно освещены в [3–5], а новые исследования по системам массового обслуживания приведены в [11–14].

  1. Решение задачи для системы E2-/HE2-/1

Рассмотрим СМО E2/HE2/1, для которой законы распределения входного потока и времени обслуживания задаются функциями плотности:

at=4λ2tt0e2λtt0,t>t0;0,0tt0,   (3)

bt=4qμ12(tt0)e2μ1(tt0)++41qμ22(tt0)e2μ2(tt0),t>t0;0,0tt0.   (4)

Как видно из распределений (3) и (4), они при параметре сдвига t0 = 0 обращаются в обычные распределения, и в этом можно заметить преемственность обычных систем и систем с запаздыванием во времени.

Запишем преобразования Лапласа функций (3) и (4):

A*s=2λs+2λ2et0s;

B*s=q2μ1s+2μ12+1q2μ2s+2μ22et0s.

В этом случае выражение для спектрального разложения решения ИУЛ примет следующий вид:

ψ+sψs=2λ2λs2et0s××q2μ1s+2μ12+1q2μ2s+2μ22et0s1.   (5)

Здесь экспоненты из-за противоположных знаков обнуляются, и тем самым операция сдвига законов распределений нивелируется.

Представим выражение, стоящее в квадратных скобках, в виде

q2μ1s+2μ12+1q2μ2s+2μ22==b0+b1s+b2s2s+2μ12s+2μ22,

где промежуточные параметры обозначены b0=16μ12μ22, b1=16μ1μ2[qμ1+1qμ2], b2=4[qμ12+1qμ22]. Продолжая спектральное разложение (5), получим:

ψ+sψs=4λ2(b0+b1s+b2s2)(2λs)22μ1+s22μ2+s2

(2λs)22μ1+s22μ2+s2(2λs)22μ1+s22μ2+s2=

=s(s5d4s4d3s3d2s2d1sd0)(2λs)22μ1+s22μ2+s2=

=s(s+σ1)(s+σ2)(s+σ3)(s+σ4)(sσ5)(2λs)22μ1+s22μ2+s2.

Окончательно спектральное разложение решения ИУЛ для системы E2/HE2/1 имеет вид

ψ+sψs=s(s+σ1)(s+σ2)(s+σ3)(s+σ4)(sσ5)(2λs)22μ1+s22μ2+s2.   (6)

Пояснения к разложению (6). Многочлен пятой степени в числителе разложения в случае стабильной системы ρ=τ¯μ/τ¯λ<1

s5d4s4d3s3d2s2d1sd0   (7)

с коэффициентами:

d0=64λμ1μ2[μ1μ2λ(μ1+μ2)+4b1λ2],

d1=16{4λμ1μ2(μ1+μ2)λ2[2μ1μ2+(μ1+μ2)2]+4b2λ2},

d2=16λ[(μ1+μ2)2+2μ1μ2]16(μ1+μ2)(λ2+μ1μ2),

d3=4[λ2+μ12+μ224λ(μ1+μ2)+4μ1μ2],

d4=4(λμ1μ2)

имеет четыре действительных отрицательных корня σ1, σ2, σ3, σ4  (либо два действительных отрицательных корня и два комплексно сопряженных с отрицательными действительными частями) и один положительный корень σ5. Исследование знака младшего коэффициента d0 показывает, что d0>0 всегда в случае стабильной системы, когда 0<ρ<1. С учетом знака минус перед d0 в многочлене (7) это также подтверждает предположение о наличии таких корней многочлена.

На рисунке показана комплексная s – плоскость с нулями и полюсами функции ψ+s/ψs, где полюсы отмечены крестиками, а нули – кружками. Нули и полюсы нужны для построения функций ψ+s и ψs в отдельности.

 

Рис. Нули и полюсы функции ψ+(s)/ψ(s) для системы M/HE2/1

Fig. Zeros and poles of the function ψ+(s)/ψ(s) for the system M/HE2/1

 

Принимая во внимание условия спектрального разложения (1), (2) строим функции ψ+s и ψs с учетом нулей и полюсов разложения:

ψ+s=ss+σ1(s+σ2)(s+σ3)(s+σ4)2μ1+s22μ2+s2,

ψ(s)=2λs2(sσ5).

Константа спектрального разложения 

K=lims0ψ+ss==lims0s+σ1(s+σ2)(s+σ3)(s+σ4)2μ1+s22μ2+s2==σ1σ2σ3σ416μ12μ22.

Эта константа определяет вероятность того, что поступающее в систему требование застает ее свободной.

Далее по методике спектрального разложения строим функцию

Φ+s=Kψ+s==σ1σ2σ3σ42μ1+s22μ2+s216μ12μ22ss+σ1(s+σ2)(s+σ3)(s+σ4).

Отсюда преобразование Лапласа функции плотности времени ожидания W*(s)=sΦ+s будет равно

W*s=σ1σ2σ3σ42μ1+s22μ2+s216μ12μ22s+σ1(s+σ2)(s+σ3)(s+σ4), (8)

Для нахождения среднего времени ожидания найдем производную от функции W*s со знаком минус в точке s = 0:

W¯=1σ1+1σ2+1σ3+1σ41μ11μ2. (9)

Преобразование Лапласа (8) позволяет кроме среднего времени ожидания находить также и моменты высшего порядка времени ожидания. С учетом определения вариации задержки – джиттера в телекоммуникациях как разброс времени ожидания от его среднего значения [14], тем самым получим возможность определения джиттера через дисперсию времени ожидания.

Для того чтобы воспользоваться формулой (9) для расчетов среднего времени ожидания, необходимо задать входные параметры, в качестве которых используем значения начальных моментов первого порядка интервалов поступлений τ¯λ и времени обслуживания τ¯μ, а также их коэффициентов вариаций cλ, cμ. С помощью этих входных параметров необходимо определить методом моментов неизвестные параметры распределений (3) и (4) λ, q, μ1, μ2, а затем коэффициенты многочлена (7).

Определим числовые характеристики распределения (3) с использованием преобразования Лапласа. Средний интервал между поступлениями требований в систему E2/HE2/1 равен

τ¯λ=λ1+t0.   (10)

Второй начальный момент интервала между поступлениями равен

d2A*(s)ds2s=0=32λ2+2t0λ+t02,

откуда

τλ2¯=32λ2+2t0λ+t02.

Определим квадрат коэффициента вариации:

cλ2=τλ2¯(τλ¯)2(τλ¯)2=12(1+λt0)2.

Отсюда коэффициент вариации:

cλ=[2(1+λt0)]1.   (11)

Значение первой производной функции B(s) со знаком минус в точке s = 0 дает среднее значение времени обслуживания

τ¯μ=qμ11+(1q)μ21+t0, (12)

а значение второй производной функции B*s в точке s = 0 дает второй начальный момент времени обслуживания

τμ2¯=t02+2t0qμ1+(1q)μ2+3q2μ12+3(1q)2μ22. (13)

Отсюда определим квадрат коэффициента вариации интервалов поступления:

cμ2=μ122qμ2(μ1μ2)+q(12q)(μ1μ2)22[μ1q(μ1μ2)+t0μ1μ2]2. (14)

Заметим, что коэффициенты вариации 0<cλ<1/2 и cμ>0 при параметре сдвига t0>0. Таким образом, очевидно, что система E2/HE2/1 относится к типу G/G/1.

Рассматривая выражения (10)–(15) как форму записи метода моментов, найдем неизвестные параметры распределения (3) и (4). Определим параметр распределения (3) λ из (10) и получим значение λ=1/(τ¯λt0).

Нахождение параметров распределения (4) μ1,μ2,q будет аналогичным нахождению этих параметров для обычного распределения. Теперь, исходя из вида уравнения (12), положим:

μ1=2q/(τ¯μt0),μ2=2(1q)/(τ¯μt0) (15)

и потребуем выполнения условия (14). Подставив частное решение (15) в (14), решим полученное уравнение четвертой степени q(1q)[8(1+cμ2)q28(1+cμ2)q+3]=0 относительно параметра q с учетом условия 0<q<1 и выберем нужное решение:

q=12+143(τ¯μt0)28[(τ¯μt0)2+cμ2τ¯μ2],

а затем определим из (15) параметры μ1 и μ2.

Задавая значения τ¯λ, τ¯μ, cλ, cμ, t0  в качестве входных параметров системы, таким образом находим известным методом моментов все неизвестные параметры распределений (3) и (4).

Теперь рассмотрим влияние параметра сдвига на коэффициенты вариаций распределений. Для эрланговского закона распределений интервалов поступлений сλ=1/2, и, сравнивая это с выражением (11), устанавливаем, что параметр сдвига t0>0 уменьшает коэффициент вариации интервалов поступлений в 1+λt0 раз. Для обычного распределения HE2 времени обслуживания, как следует из выражений (14), получим:

cμ2=μ122qμ2(μ1μ2)+q(12q)(μ1μ2)22[μ1q(μ1μ2)]2.

Сравнивая последнее выражение с (14), убеждаемся, что параметр сдвига во времени t0>0 уменьшает коэффициент вариации интервалов поступлений в 1+t0μ1μ2[μ1(1q)+μ2q] раз. Учитывая квадратичную зависимость среднего времени ожидания от коэффициентов вариаций интервалов поступлений и времени обслуживания, убеждаемся в том, что введение параметра сдвига в законы распределения уменьшает среднее время ожидания в очереди в СМО.

  1. Результаты вычислительных экспериментов

В таблице приведены расчетные значения среднего времени ожидания для системы с запаздыванием E2/HE2/1 для случаев малой, средней и высокой нагрузки ρ=0,1; 0,5; 0,9 при значениях параметра сдвига t0 от 0,001 до 0,999 и коэффициенте вариации времени обслуживания сμ=0,71 для обычной системы E2/H2/1. Значения параметров сλ и сμ в системе E2/HE2/1 изменяются согласно выражениям (11) и (14). Расчеты проведены для нормированного времени обслуживания τ¯μ=1.

 

Таблица. Результаты экспериментов для СМО Е2/H2/1 при cμ=0,71 для системы E2/HE2/1

Table. Результаты экспериментов для СМО Е2/H2/1 при cμ=0,71 для системы E2/HE2/1

Входные параметры

Среднее время ожидания

ρ

cλ

cµ

t0

для системы (1)

для системы E2/HE2/1

0,1

0,636

0,355

0,999

0,006

0,018

0,672

0,473

0,5

0,006

0,700

0,645

0,1

0,013

0,706

0,703

0,01

0,017

0,707

0,709

0,001

0,018

0,5

0,354

0,355

0,999

0,063

0,395

0,530

0,473

0,5

0,124

0,672

0,645

0,1

0,321

0,704

0,703

0,01

0,386

0,707

0,709

0,001

0,394

0,9

0,071

0,355

0,999

0,568

4,380

0,389

0,473

0,5

1,511

0,643

0,645

0,1

3,578

0,701

0,703

0,01

4,292

0,706

0,709

0,001

4,371

 

Таким образом, данные таблицы демонстрируют качественное и количественное влияние параметра сдвига t0>0 на числовые характеристики распределений (3) и (4) и, следовательно, на основную характеристику системы - среднее время ожидания. Как и следовало ожидать, уменьшение коэффициентов вариации сλ и сμ влечет за собой многократное уменьшение времени ожидания.

Заключение

Таким образом, по результатам работы можно сделать следующие выводы.

Научная новизна результатов заключается в том, что получено спектральное разложение решения интегрального уравнения Линдли для рассматриваемой системы и с его помощью выведена расчетная формула для среднего времени ожидания в очереди для этой системы в замкнутой форме. Данные численных экспериментов подтверждают полную адекватность полученных теоретических результатов.

Практическое значение работы состоит в том, что полученные результаты с успехом могут быть применены в современной теории телетрафика, где задержки пакетов входящего трафика играют первостепенную роль. Для этого необходимо знать числовые характеристики интервалов входящего трафика и времени обслуживания на уровне двух первых моментов, что не вызывает трудностей при использовании современных анализаторов трафика.

×

Об авторах

Вениамин Николаевич Тарасов

Поволжский государственный университет телекоммуникаций и информатики

Email: tarasov-vn@psuti.ru

доктор технических наук, профессор, заведующий кафедрой программного обеспечения и управления в технических системах 

Россия, Самара

Надежда Федоровна Бахарева

Поволжский государственный университет телекоммуникаций и информатики

Автор, ответственный за переписку.
Email: bakhareva-nf@psuti.ru

доктор технических наук, профессор, заведующая кафедрой информатики и вычислительной техники 

Россия, Самара

Список литературы

  1. Клейнрок Л. Теория массового обслуживания / пер. с англ. под ред. В.И. Неймана. М.: Машиностроение, 1979. 432 с.
  2. Brännström N. A Queueing Theory Analysis of Wireless Radio Systems: master’s thesis applied to HS-DSCH. Lulea University of Technology, 2004. 79 p. URL: http://ltu.diva-portal.org/smash/get/diva2:1016709/FULLTEXT01
  3. Алиев Т.И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. № 2 (84). С. 88–93. URL: https://ntv.ifmo.ru/ru/article/4127/approksimaciya_veroyatnostnyh_raspredeleniy_v_modelyah_massovogo_obsluzhivaniya.htm
  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: proc. of congress. Copenhagen, Denmark. 19–26 June 1991. P. 683–688. URL: https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc13/myskja911.pdf?inline=true
  5. Whitt W. Approximating a point process by a renewal process, I: Two basic methods // Operation Research. 1982. Vol. 30, No. 1. P. 125–147. DOI: https://doi.org/10.1287/opre.30.1.125
  6. Малахов С.В., Карташевский И.В., Тарасов В.Н. Теоретическое и экспериментальное исследование задержки в программно-конфигурируемых сетях // Инфокоммуникационные технологии. 2015. Т. 13, № 4. С. 409–413. DOI: https://doi.org/10.18469/ikt.2015.13.4.08
  7. Малахов С.В., Тарасов В.Н. Экспериментальные исследования производительности сегмента программно-конфигурируемой сети // Интеллект. Инновации. Инвестиции. 2013. № 2. С. 81–85.
  8. Тарасов В.Н., Липилина Л.В., Бахарева Н.Ф. Автоматизация расчета характеристик систем массового обслуживания для широкого диапазона изменения их параметров // Информационные технологии. 2016. Т. 22, № 12. С. 952–957. URL: http://novtex.ru/IT/it2016/it1216_web-952-957.pdf
  9. Тарасов В.Н. Вероятностное компьютерное моделирование сложных систем. Самара: СНЦ РАН, 2002. 194 с.
  10. Тарасов В.Н., Коннов А.Л., Ушаков Ю.А. Анализ и оптимизация локальных сетей и сетей связи с помощью программной системы OPNET Modeler // Вестник Оренбургского государственного университета. 2006. № 6-2 (56). С. 197–204. URL: http://vestnik.osu.ru/doc/1033/article/2762/lang/0
  11. Jennings O.B., Pender J. Comparisons of ticket and standard queues // Queueing Systems. 2016. Vol. 84, No. 1–2. P. 145–202. DOI: https://doi.org/10.1007/s11134-016-9493-y
  12. Gromoll H.C., Terwilliger B., Zwart B. Heavy traffic limit for a tandem queue with identical service times // Queueing Systems. 2018. Vol. 89, No. 3–4. P. 213–241. DOI: https://doi.org/10.1007/s11134-017-9560-z
  13. Legros B. M/G/1 queue with event-dependent arrival rates // Queueing Systems. 2018. Vol. 89. № 3–4. P. 269–301. DOI: https://doi.org/10.1007/s11134-017-9557-7
  14. Jacobovic R., Kella O. Asymptotic independence of regenerative processes with a special dependence structure // Queueing Systems. 2019. Vol. 93, No. 1–2. P. 139–152. DOI: https://doi.org/10.1007/s11134-019-09606-1
  15. Demichelis C., Chimento P. IP Packet Delay Variation Metric for IP Performance Metrics. URL: https://tools.ietf.org/html/rfc3393

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Рис. Нули и полюсы функции для системы M/HE2/1

Скачать (17KB)

© Тарасов В., Бахарева Н., 2021

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

СМИ зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор).
Регистрационный номер и дата принятия решения о регистрации СМИ: серия ФС 77 - 68199 от 27.12.2016.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах