Анализ СМО общего вида с использованием селектирующих функций

Анализ характеристик сетевых узлов при обработке трафика, обладающего распределениями с тяжелыми хвостами [1- 2; 7; 9] для интервалов времени между поступлениями пакетов и интервалов времени обработки пакетов, связан с решением интегрального уравнения Линдли [3] для систем массового обслуживания типа G/G/1. При этом для упрощения вычислительной процедуры решения уравнения Линдли спектральным методом часто прибегают к аппроксимации плотностей вероятностей гиперэкспоненциальными распределениями, моделируемыми суммами затухающих экспонент [5; 7-8; 10]. Предложенный в [5] метод аппроксимации распределения суммой затухающих экспонент дает неудовлетворительные результаты по точности аппроксимации на «восходящих» ветвях распределений. Кроме того, аппроксимация «восходящих» ветвей распределений приводит к появлению в сумме затухающих экспонент слагаемых с отрицательными коэффициентами, что нивелирует вычислительные преимущества спектрального метода, обусловленные использованием гиперэкспоненциальных распределений.

Аппроксимация распределения Вейбулла

Для иллюстрации данного утверждения рассмотрим задачу аппроксимации распределения Вейбулла, принадлежащего к классу распределений с тяжелыми хвостами, методом, изложенным в [5]. Например, для распределения Вейбулла с параметрами               представленного на рис. 1 пунктиром, аппроксимирующая сумма будет иметь вид

(2) к=\ при некоторых значениях коэффициентов отличающихся друг от друга на несколько порядков [5]. Результат аппроксимации представлен на рис. 1 сплошной линией.

Рис. 1. Аппроксимация распределения Вейбулла: f^ ^И /ехрИ

Как следует из рис. 1, аппроксимация «восходящей» ветви распределения осуществляется с недопустимо большой ошибкой.

Заметим, что для распределений, в которых отсутствует «восходящая» ветвь, например распределение Парето [4], данная проблема не возникает и число слагаемых в аппроксимирующей сумме (2), как правило, может быть выбрано существенно меньше 10 при сохранении достаточной точности аппроксимации.

Метод селектирующих функций

Для рассмотренного распределения Вейбулла выделим два интервала аппроксимации - и где может быть выбрано, например, как Теперь представим в виде «сшитой» функции через кусочно-нелинейные р!« О<х<хо;

[^₂(х), х>х₀;            (3)

I = jG(x)5z(x,X1,X2)(/x справедливо соотно шение

^1(^х) = ^⁰_п^хп ’              (4)

/2=1

К фАА = ^9ке"акХ .          (5)

В (4)-(5) коэффициенты аппроксимации SnA^k определяются соответствующими вычислительными процедурами. Для «сшитой» функции ^с С^) должно выполняться условие нормировки J fc {x)dx = 1. Основным инстру-о ментом «сшивания» является селектирующая функция Sl^X^X^, определяемая как

I = 0,5

— [1 — Is gib — x, )] jG(x)z&

Используя (10) и (8), получаем

. (10)

j/] (5,x^si(x, 0, x0 ^dx + jk (s, x)si (x, x0, 00) = о                                     0

с учетом сопряжения в точках «сшивания» в виде: si Ач, Х_;, х_/+1) = si (х_м, х_;, х_м ) = 0,5. Очевидно, что выражение (3) теперь может быть представлено в виде

/_с (х) = ф_х (x)sz (х, 0, х₀) + ф^ (x)si (х, х₀, со), (7)

а требуемое для решения уравнения Линдли спектральным методом преобразование Лапласа запишется как

= 0,5< J/, (s, x)dx + ^ f_x (s, x)dx - j f_x (s, x^dx > + .°                        ^{0                       A}'o                   .

+ 0,5< - J/? (s, ^XW + J/? (5, x^dx + J/? (⁵, ^XW >. 0                                         0

Вычисляя все интегралы в (11) на основе из- вестных соотношений

Jx”e ^Sxdx = n\s ¹

FA$) = ^fAxK$xdx =

О

^Jo ^xⁿe-^sxdx =

-A 7?! Xfl

= J/^(5, x)si (х, 0, x₀)dx + о

-А и! Xq tS<^

+ j/2(5,x>z(x, х0, со), о где /И2)(5,х) = ^1(2)(х)е"и.

Если ввести в рассмотрение функции

\e"^atXe-^sxdx=——, 0              ^ak + ⁵

\e-atXe-sxdx          - e"1'^0

ak+s

sg(x) = <0,5; х = 0;

sgn (х) =) О,

х < 0;

х = 0;

х<0; (9)

e ^sxdx= —-—e a, +5

sg(x) = l-sg(x),

для преобразования Лапласа Fc (^) получим

^___е-_Иоу »! 4

,и+1            2-1 7,| _с'>-4 + 1

+

¹ _e"^|ai^+5)Vn ^^s

Используем (12) в задаче анализа системы массового обслуживания G/G/1 путем решения интегрального уравнения Линдли спектральным методом [3].

Суть метода заключается в представлении выражения ^(-s)S(s)-l в виде ^(-^й)-!--^, где А(з) и B(s) – пре-

^-й)

образование Лапласа плотностей вероятностей промежутков времени между поступлениями заявок на обслуживание в систему и времени обслуживания заявок в системе, соответственно. При этом функции Ч< и Т должны удовлетворять условиям:

– Ф+й) – аналитическая функция без нулей в области Ней) > 0;

– Ч^й) – аналитическая функция без нулей в области Re(^) <  D для некоторого D > О;

- lim —tl^l - i дЛЯ Re(5) > 0 -

,v| >v. Т_й)

- lim —^±— = 1 для Re(s) <  D . й=" ^

Если функция T+ (s) найдена, то характеристическая функция времени ожидания заявки в очереди ф+й) может быть определена в виде r ^(s)

lim— ф (5) = ^^,

Ч^й)

время ожидание в очереди г-^Ф.ИЬ ds

Аппроксимация распределений для анализа системы G/G/1

Рассмотрим применение рассмотренного метода аппроксимации распределений для анализа системы G/G/1. Пусть плотность вероятностей времени обслуживания заявок в системе определяется распределением Вейбулла f k^) с параметрами a = 1,5 и P = 1. Методом селектирующих функций заменим J M на fc W ’ а для плотности вероятностей интервалов времени между поступлениями заявок выберем распределение Парето ab“

W = ^, «>0,b>0, x>0, с параметрами a = 0,5 и b = 1,9.

Пусть плотность fe (-К) на интервале (0, x₀ - 0,5) аппроксимируется полиномом третьей степени согласно (4) при N = 3, 9, = 0; 0₂ = 3,573; 9₃ = -4,167 и суммой затухающих экспонент согласно процедуре [5] на интервале йо’”) с параметрами к = 3, S,=0,64; я =3,318; S₃ = -3,885 и a, = 0,89; a₂ = 1,78; a₃ = 2,68. Результат данной аппроксимации представлен на рис. 2. Абсолютная погрешность аппроксимации при этом есть H(x) = 0,061.

Рис. 2. Аппроксимация распределения Вейбулла:

2W И .fExp(x)

Плотность ^П ("^^ при a = 0,5 и b = 1,9 аппроксимируем суммой затухающих экспонент в виде 2п^ = Цр_т^е"“" с параметрами;

M =3, p_v =0,042; p, =-0,612;

p₃ = 1,752; q_x = 0,32; q₂ = 0,65; q₃ = 0,97 .

Результат аппроксимации представлен на рис. 3. Погрешность аппроксимации 7?(jt) = 0,048 •

Рис.3. Аппроксимация распределения Парето:

/(-й ^И КхДх')

Преобразование Лапласа для Ун (^0 будет м р иметь вид Fn^-Ъ— и, соответственно, м          "z=1 q™ + 5

Осуществив простые, но достаточно объемные преобразования, для выражения Fn(-s)Fc^-l при выбранных значениях параметров аппроксимации распределений можно получить

FnHFc^^ =

=-----------------------------------------x

/(a, + s)(a₂ + s)(a₃ + sXq_v -s)(q₂ -sXq₃ ^-s)

x [s10 + s 9 £, (a, 9, 9, p, q^ +581\ (a, 9, 9, p, q, e-®0) + (14) + s\(a,9,9, p,q,e"sl°) + • • • s • r8 (a, 9, 9,p,q,e"iA") + +ЦоМр^, где kj, i = 1;2, и p, 7=1,2,...8 – коэффициенты, зависящие от параметров используемых распределений, причем эти коэффициенты зависят также от величины e ы°, что делает характеристическое уравнение выражения в квадратных скобках нелинейным и, соответственно, усложняет нахождение его корней. Например, численное значение коэффициента p определяется как r3 =O,5-l,5e"°'5$. Аналогично выглядят и остальные коэффициенты М = 1,2, ...8. Наличие множителя e °'5$ в каждом коэффициенте fj является следствием использования полиномиальной аппроксимации «восходящего» участка распределения Вейбулла.

Так как структура всех коэффициентов r„j = \,2,..^ одинакова, используя разложение '                                       _ »         zk экспоненты в ряд в виде ^-1>-^P не-k=o        k\ трудно свести нелинейное уравнение (13) к линейному виду, решая которое численно, можно получить представление FhI-sXAsVV в виде

V (5)

F_n(-_Sx_cx-^XX- Такая возможность со-^{n c} ^.(s)

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

+ l,85s2 -2,2s+ 8,9 = 0.

для можно

^(S)

Обозначая корни характеристического уравнения через s*,i = 1, 2,   9, записать

^M ^ ^(s)

П^-^,’)

s⁴(aj +s)(a₂ +s)(a, +sXq_t ~s)(q₂ ~ХЯз ~^s)

Выделяя в (15) по вышеизложенным условиям функции ^(5) и ^(s) и формируя O₊(s) согласно (13), получаем значение среднего времени ожидания заявки в очереди T = 0,053 с (размерность T определяется размерностью величин ^ak ^И Чт )•

Точность полученного решения определяется точностью аппроксимации распределений при решении уравнения Линдли спектральным методом. Метод селектирующих функций позволил заменить распределение Вейбулла ^ (*v) «сшитым» распределением /с (^X) ’ состоящим из двух участков: «восходящий» участок (с положительным значением производной), который допускает простую аппроксимацию в виде полинома невысокой степени, и «нисходящий» участок (с отрицательным значением производной), аппроксимация которого осуществляется суммой затухающих экспонент с малым числом слагаемых в сумме. Такая аппроксимация обладает, как показано в работе, существенно меньшей погрешность по сравнению со случаем, когда используется единая аппроксимация распределения суммой затухающих экспонент. «Сшитое» распределение позволяет легко получить его преобразование Лапласа, что в конечном итоге сводит решение задачи к определению корней линейного алгебраического уравнения численным методом.