Например, Бобцов

ТРЕХМОМЕНТНАЯ АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ

Т.И. Алиев

УДК 519.872
ТРЕХМОМЕНТНАЯ АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ В МОДЕЛЯХ МАССОВОГО ОБСЛУЖИВАНИЯ
Т.И. Алиева
а Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО), Санкт-Петербург, Россия, aliev@d1.ifmo.ru
Рассматривается задача аппроксимации вероятностных распределений случайных величин, определенных в положительной области действительных чисел и имеющих отличный от единицы коэффициент вариации. При использовании в качестве моделей компьютерных сетей систем массового обслуживания расчет характеристик обычно выполняется на уровне математического ожидания и дисперсии. В то же время одной из основных характеристик качества при передаче мультимедийных данных в компьютерных сетях является джиттер задержки, для расчета которого необходимо знать функцию распределения времени задержки пакетов. Показано, что при изменении третьего момента распределения задержки пакетов результаты расчета джиттера могут отличаться на десятки и сотни процентов при одних и тех же значениях двух первых моментов – математического ожидания и коэффициента вариации задержки. Это означает, что аппроксимация распределения задержки для расчета джиттера должна выполняться с учетом третьего момента распределения времени задержки. Для случайных величин с коэффициентами вариации больше единицы предлагается итерационный алгоритм аппроксимации двухфазным гиперэкспоненциальным распределением с учетом трех моментов аппроксимируемого распределения. Показано, что для случайных величин с коэффициентами вариации меньше единицы влияние третьего момента распределения незначительно, и для аппроксимации таких распределений целесообразно использовать распределение Эрланга по двум первым моментам. Такой подход позволяет получить верхние оценки соответствующих характеристик, в частности, верхнюю оценку джиттера задержки. Ключевые слова: вероятностное распределение, коэффициент вариации, третий начальный момент, аппроксимация, гиперэкспоненциальное распределение, распределение Эрланга.
THREE-MOMENT BASED APPROXIMATION OF PROBABILITY DISTRIBUTIONS IN QUEUEING SYSTEMS
T.I. Alievа
а Saint Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University), Saint Petersburg, Russia, aliev@d1.ifmo.ru
The paper deals with the problem of approximation of probability distributions of random variables defined in positive area of real numbers with coefficient of variation different from unity. While using queueing systems as models for computer networks, calculation of characteristics is usually performed at the level of expectation and variance. At the same time, one of the main characteristics of multimedia data transmission quality in computer networks is delay jitter. For jitter calculation the function of packets time delay distribution should be known. It is shown that changing the third moment of distribution of packets delay leads to jitter calculation difference in tens or hundreds of percent, with the same values of the first two moments – expectation value and delay variation coefficient. This means that delay distribution approximation for the calculation of jitter should be performed in accordance with the third moment of delay distribution. For random variables with coefficients of variation greater than unity, iterative approximation algorithm with hyper-exponential two-phase distribution based on three moments of approximated distribution is offered. It is shown that for random variables with coefficients of variation less than unity, the impact of the third moment of distribution becomes negligible, and for approximation of such distributions Erlang distribution with two first moments should be used. This approach gives the possibility to obtain upper bounds for relevant characteristics, particularly, the upper bound of delay jitter. Keywords: probability distribution, coefficient of variation, the third raw moment (start moment), approximation, hyperexponential distribution, Erlang distribution.
Введение
Одной из основных характеристик качества обслуживания (QoS) в компьютерных сетях, наряду со средней задержкой передачи пакетов, является вариация или джиттер задержки [1–4], для расчета которого необходимо знать функцию распределения времени задержки пакетов [4]. При использовании моделей массового обслуживания в качестве моделей компьютерных систем [5–10] аналитические зависимости, отображающие связь характеристик функционирования системы с ее структурнофункциональными и нагрузочными параметрами, могут быть получены в явном виде на уровне нескольких (обычно двух) моментов распределений вероятностных характеристик, если процессы, протекающие в исследуемых системах, являются марковскими [11–13]. При этом временные характеристики, такие как задержка пакетов, обычно представляют собой случайные величины, распределенные в области положительных значений τ  0 , зачастую по законам, отличным от экспоненциального, коэффициент вариации
которого ν  1 . В [14] для аппроксимации временных интервалов с коэффициентами вариации ν  1
предлагается использовать мультиэкспоненциальные распределения: гипоэкспоненциальное, если 0  ν  1, и гиперэкспоненциальное, если ν  1 . При этом аппроксимация реального распределения вы-
полняется по двум моментам распределения – математическому ожиданию и коэффициенту вариации [15]. В то же время влияние моментов более высокого порядка, в частности, третьего момента, на характеристики качества обслуживания, как показано ниже, может быть значительным. Это обусловливает

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, №2 (90)

107

ТРЕХМОМЕНТНАЯ АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ...

необходимость решения задачи аппроксимации реальных распределений с учетом трех моментов вероятностных распределений: математического ожидания t , коэффициента вариации ν и третьего началь-
ного момента t (3) . Особенно актуальна эта задача для распределений, имеющих коэффициент вариации
больше единицы, ν  1 , поскольку их третий момент может оказаться сколь угодно большим. Следовательно, для таких распределений невозможно получить верхние границы, в отличие от распределений с коэффициентом вариации, лежащим в интервале (0; 1), для которых верхняя граница может быть получена, например, при аппроксимации экспоненциальным распределением или распределением Эрланга.

Аппроксимация распределений с ν  1

Для аппроксимации распределения с коэффициентом вариации ν  1 по трем заданным моментам –

t, ν и t (3) – воспользуемся гиперэкспоненциальным двухфазным распределением [15], параметрами ко-

торого являются математические ожидания t1 и t2 составляющих экспоненциальных распределений и вероятность q формирования случайной величины по первой экспоненте, что позволяет выполнять ап-

проксимацию по трем числовым моментам. Таким образом, задача аппроксимации гиперэкспоненциальным распределением сводится к опре-

делению значений параметров t1, t2 и q в зависимости от известных значений математического ожида-
ния t , коэффициента вариации ν и третьего начального момента t (3) аппроксимируемого закона распределения случайной величины τ.

Математическое ожидание, коэффициент вариации и третий начальный момент гиперэкспоненциального распределения соответственно равны

t  q t1  (1 q) t2 ;



 

ν2





2[q t12

 (1 t2



q)

t22

]



1

;

t(3)  6[q t13  (1 q) t23 ].

Таким образом, имеем систему из трех уравнений с тремя неизвестными t1, t2 и q , аналитическое
решение которой в явном виде с учетом ограничений 0  q  1 , t1  0 , t2  0 не представляется возмож-
ным. Для решения поставленной задачи предлагается итерационный подход, базирующийся на матема-
тических зависимостях, полученных в [15] для аппроксимации по двум моментам:

q



1

2  ν2

;

(1)

t1  1 

1 q 2q

(

ν2

1)

  

t

;

t2  1 

q 2 (1 

q)

(

ν2

1)

 

t



.

(2)

Третий начальный момент гиперэкспоненциального распределения с заданным коэффициентом

вариации

ν

принимает минимальное значение

t (3)
min

 1,5

(1 2 )2

t3

на границе неравенства (1) при

q  2 /(1 ν2 ) , тогда t1  0,5 (ν2 1) t и t2  0 . При q  2 /(1 ν2 ) третий момент увеличивается и стремит-

ся к бесконечности с уменьшением q до нуля. Таким образом, третий момент двухфазного гиперэкспо-

ненциального распределения в зависимости от

q

лежит в интервале от

t (3) min

до бесконечности.

С учетом этого, алгоритм аппроксимации гиперэкспоненциальным вероятностным законом по

трем моментам исходного распределения реализуется на основе итерационного подхода, суть которого в

следующем.
1. По заданному значению коэффициента вариации ν определяется верхняя граница вероятности

qmax  2/(1 ν2 ) .

2.

Рассчитывается

минимально

возможное

значение

третьего

начального

момента

t (3)
min

 1,5 (1

ν2 )2

t3 .

3.

Если

t (3)



t (3)
min

,

то

для

аппроксимации

используется

однофазное

представление

гиперэкспоненци-

ального распределения, что позволяет получить верхнюю оценку при расчетах характеристик функ-

ционирования исследуемой системы, в частности, такой важной характеристики при передаче муль-

тимедийных данных в компьютерных сетях, как джиттер задержки.

4.

Если

t (3)



t (3) min

,

то,

изменяя

значения

q

по методу половинного деления в интервале

[qmax ; 0]

и пе-

ресчитывая всякий раз значения t1 и t2 в соответствии с (2), рассчитываем третий момент гиперэкс-

поненциального

распределения:

t (3) H



6[q t13

 (1 q)t23 ] .

108

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, №2 (90)

Т.И. Алиев

5.

Пункт 4 выполняется до тех пор, пока третий момент

t (3) H

аппроксимирующего гиперэкспоненци-

ального

распределения

не

совпадет

с

заданным

значением

t (3) H

.

Пример. Пусть математическое ожидание, коэффициент вариации и третий начальный момент ап-

проксимируемого распределения соответственно равны t  10 , ν  3 и t(3)  405000 .
Применяя представленный выше алгоритм, определим параметры аппроксимирующего гиперэкспоненциального распределения.

1. Верхняя граница вероятности qmax  2 /(1 ν2 )  0, 2 .

2.

Минимально

возможное

значение

третьего

начального

момента

t (3) min

 1, 5

(1 

ν2 )2

t3

 150 000.

3.

Поскольку

t (3)



t (3)
min

,

то

для

аппроксимации

используется

двухфазное

представление

гиперэкспонен-

циального распределения, при котором q  qmax .

4. Изменяя значение q по методу половинного деления в интервале [qmax ; 0] и пересчитывая значения

t1 и t2 в соответствии с (2), определим, что третий момент гиперэкспоненциального распределения равен t(3)  405000 при q  0,02 , откуда t1  150 и t2  7,14 . 5. Окончательно функция аппроксимирующего распределения примет вид

F(τ)  1 0, 02e0,0067τ  0,98e0,14τ .

Если не учитывать третий момент распределения и выбрать, например, вероятность q  0,15 , при

которой t1  57,61 и t2  1, 60 , то получим функцию распределения вида
F(τ)  1 0,15e0,017τ  0,85e0,626τ . Рассчитывая в соответствии с [4] джиттер задержки в компьютерной сети как 0,999-квантиль для распределений F(τ) и F(τ) , получим:

τ0,999  448 и τ0,999  295 .
Таким образом, рассчитанные значения джиттера задержки различаются более чем в 1,5 раза, что свидетельствует о необходимости учета третьего момента задержки. Очевидно, что при значениях q  0,02 , соответствующих большим значениям третьего момента, эта разница еще более значительна и
может достигать 100% и более.

Аппроксимация распределений с ν  1

При аппроксимации гипоэкспоненциальным распределением k -го порядка, содержащим два типа

экспоненциальных фаз [15] ( k1 фаз первого и k2  k  k1 – второго типа с математическими ожидания-

ми t1 и t2 соответственно) возникает проблема, связанная с определением параметров k1 и k2 аппрок-

симирующего распределения, учитывающего одно

из

условий:

k2

1  ν2

k

или

k1



1 ν2



k

.

Это

приво-

дит к тому, что третий момент такого гипоэкспоненциального распределения изменяется в незначитель-

ных пределах (10%), что не позволяет выполнить аппроксимацию, если третий момент находится вне

этих пределов. Заметим, что третий момент гипоэкспоненциальных распределений с коэффициентами

вариации

0

ν

1

лежит

в

пределах от

t (3) min



t3

до

t (3) max



6t3 ,

т.е. в

шестикратном

диапазоне.

Для увеличения пределов изменения третьего момента можно воспользоваться гипоэкспоненци-

альным распределением, содержащим более двух типов экспоненциальных фаз, причем чем их больше,

тем шире пределы изменений третьего момента. В предельном случае количество типов экспоненциаль-

ных фаз n может совпадать с количеством фаз k : n  k . В этом случае аппроксимация по трем момен-

там сводится к решению следующей системы из трех уравнений с (k  1) неизвестными ( k , t1,, tk ):

k
 ti  t;
i 1 k
 ti2  ν2t 2 ;
i 1









 

.



     
6

k

ti3

 i1



k

1

 

ti

i1 

k
t
j i 1

2 j

  



k2 i 1

 

ti

k 1

 

t

j

j i1

l

k  j 1

tl2

  

 

  t(3) .


Однако это резко усложняет задачу аппроксимации и, в связи с увеличением числа параметров ап-

проксимирующего распределения ( ki и ti , i  1, n ), вносит произвол в определение их значений. Немало-

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, №2 (90)

109

ТРЕХМОМЕНТНАЯ АППРОКСИМАЦИЯ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ...

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

деления общего вида, является невозможность получения функции распределения в явном виде, что, на-

пример, не позволяет выполнить расчет джиттера задержки.

С учетом сказанного для решения задачи аппроксимации распределений с коэффициентом вариа-

ции 0  ν  1 целесообразно использовать распределение Эрланга, позволяющее получить верхнюю гра-

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

по заданному значению коэффициента вариации ν в соответствии с выражением k  1/ ν2  определяет-

ся

порядок

распределения Эрланга,

имеющего

функцию

распределения

вида

Fk

(τ)



1

e

kτ t

k1 (kτ)i i0 i!ti

.

Заключение

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

References

1. Olifer V.G., Olifer N.A. Komp’yuternye seti. Printsipy, tekhnologii, protokoly [Computer networks. Principles, technologies, protocols] 3rd ed. St. Petersburg, Piter Publ., 2006, 944 p.
2. Aliev T.I., Nikulsky I.Y., Pyattaev V.O. Modeling of packet switching network with relative prioritization for different traffic types. The 10th International Conference on Advanced Communication Technology, ICACT-2008. Phoenix Park, South Korea, 2008, art. no. 4494220, pp. 2174-2176. doi: 10.1109/ICACT.2008.4494220
3. Aliev T.I., Muravyeva-Vitkovskaya L.A. Prioritetnye strategii upravleniya trafikom v multiservisnykh komp’yuternykh setyakh [Priority-based strategies of traffic management in multiservice computer networks]. Izv. vuzov. Priborostroenie, 2011, vol. 54, no. 6, pp. 44–48.
4. ITU-T Recommendation Y.1541:2006. Network performance objectives for IP-based services. 5. Aliev T.I. Kharakteristiki distsiplin obsluzhivaniya zayavok s neskol’kimi klassami prioritetov [Characteristics of ser-
vice disciplines with multiple priority classes]. Izvestiya akademii nauk SSSR. Tekhnicheskaya kibernetika, 1987, no. 6, pp. 188–191. 6. Aliev T.I., Muravyeva L.A. System with dynamically varying mixed priorities and an unreliable server. Automation and Remote Control, 1988, vol. 49, no. 7, pp. 897–903. 7. Aliev T.I. Zadacha sinteza system s poteryami [Problems of synthesis of systems with losses]. Izv. vuzov. Priborostroenie, 2012, vol. 55, no. 10, pp. 57–63. 8. Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Optimizatsiya drevovidnoi seti s rezervirovaniem kommutatsionnykh uzlov i svyazei [Optimization of the tree-structured network with redundant of switching nodes and links]. Telekommunikatsii, 2013, no. 2, pp. 42–48. 9. Bogatyrev V.A. An interval signal method of dynamic interrupt handling with load balancing. Automatic Control and Computer Sciences, 2000, vol. 34, no. 6, pp. 51–57. 10. Bogatyrev V.A. Probability estimate of total connectedness of local networks with partial accessibility of redundant trunks. Engineering Simulation, 2000, vol. 17, no. 5, pp. 739–752. 11. Bogatyrev V.A. Protocols for dynamic distribution of requests through a bus with variable logic ring for reception authority transfer. Automatic Control and Computer Sciences, 1999, vol. 33, no. 1, pp. 57–63. 12. Bogatyrev V.A. Increasing the fault tolerance of a multi-trunk channel by means of inter-trunk packet forwarding. Automatic Control and Computer Sciences, 1999, vol. 33, no. 2, pp. 70–76. 13. Bogatyrev V.A. On interconnection control in redundancy of local network buses with limited availability. Engineering Simulation, 1999, vol. 16, no. 4, pp. 463–469. 14. Aliev T.I. Osnovy modelirovaniya diskretnykh system [Fundamentals of simulation of discrete systems]. St. Petersburg, SPbSU ITMO Publ., 2009, 363 p. 15. Aliev T.I. Approksimatsiya veroyatnostnykh raspredelenii v modelyakh massovogo obsluzhivaniya [Approximation of probability distributions in queueing models]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2013, no. 2 (84), pp. 88–93.

Алиев Тауфик Измайлович Taufik I. Aliev

– доктор технических наук, зав. кафедрой, профессор, СанктПетербургский национальный исследовательский университет информационных технологий, механики и оптики (Университет ИТМО), Санкт-Петербург, Россия, aliev@d1.ifmo.ru
– D.Sc., Professor, Department head, Saint Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University), Saint Petersburg, Russia, aliev@d1.ifmo.ru
Принято к печати 30.11.13 Accepted 30.11.13

110

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics

2014, №2 (90)