Моделирование трафика в компьютерных сетях с помощью потоков событий

ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

УДК 681.3

Н. Ф. Бахарева

МОДЕЛИРОВАНИЕ ТРАФИКА В КОМПЬЮТЕРНЫХ СЕТЯХ С ПОМОЩЬЮ ПОТОКОВ СОБЫТИЙ

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

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

Введение. Задача анализа производительности сети заключается в определении всех основных узловых и сетевых характеристик. Для ее решения модель задачи должна быть предварительно декомпозирована на отдельные узлы с последующим вычислением характеристик входных и выходных потоков в каждом узле. Далее могут быть вычислены узловые и сетевые характеристики.

В настоящее время не существует аналитических методов для точного определения характеристик потоков в сетевых моделях при произвольных законах распределения времени поступления и обслуживания.

Постановка задачи и подход к ее решению. Пусть имеется открытая сетевая модель с матрицей вероятности передач Р=(р)}, /,) = \,...,п, гдер.,- — вероятность того, что заявка, покидающая узел Б;, поступит в узел 5). Для начала пусть узел представляет собой одноканаль-ную (многоканальную с равновозможным доступом) систему 01/0/1 с бесконечной очередью. Для этой системы определены числовые характеристики случайного времени обслуживания: Тц. — среднее значение времени обслуживания, — его дисперсия. Для внешнего потока

задана совокупность средних значений т о. и дисперсий Б0. времени между соседними заявками д рекуррентного потока, входящего в узел В последующем узел может быть представлен как система массового обслуживания (СМО) с конечной очередью с потерями, а также с конечной очередью без потерь.

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

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

дисперсия и ковариационная функция. Поэтому учет дисперсий (вторых моментов распределений) интервалов времени существенно может улучшить результаты расчетов. Описание потоков на уровне двух первых моментов распределения интервалов времени означает их аппроксимацию непрерывным диффузионным процессом с соответствующими характеристиками [1, 3, 4] либо аппроксимацию законов их распределения известными функциями.

Решением системы уравнений равновесия потоков относительно интенсивности X потоков на входе и выходе каждой системы массового обслуживания сети определяем средние

значения интервалов времени между соседними заявками т = X-1 для каждого потока в сети:

Ь = ^ Р],х/'*=1'."'п' ]=1

где Xо — интенсивность потока в 1-й узел.

Из уравнений (1) следует, что на вход /-го узла в общем случае поступает агрегированный поток (знак суммы) из разреженных потоков (произведение интенсивности на вероятность переходов) с выходов других узлов. В связи с этим подробнее рассмотрим математические операции агрегирования (мультиплексирования) двух потоков и их разрежения (демультиплексирования). При этом в качестве математической модели потока рассматриваем случайный поток событий на оси времени.

Математическая модель мультиплексирования потоков. Предварительно докажем следующее утверждение.

Утверждение 1. Функция распределения интервала времени тЕ результирующего потока при мультиплексировании двух потоков с интенсивностью Хх и X 2 определяется интегральным соотношением:

XX ю ю

Ръ Ц) = 1 - {[1 -

г г

где Рт ] (г) — функция распределения интервалов времени между событиями в потоке / (/=1, 2).

Доказательство. На рис. 1, 2 приведены схемы математического мультиплексирования двух потоков (П), т.е. получения результирующего потока.

-Е, Ог,

Рис. 1

' Т21)

т (2) т 2

т (3) т 2

и,

> П,

> Пу г у

Рис. 2

Введем в рассмотрение следующие события: A — за время t в суммарном потоке не появится очередное событие ( т £ > t ); Aj — непоявление события в j-м потоке за время t

( т j > t ), j = 1, 2. Кроме того, рассмотрим остаточное время т/ (/=1, 2), т.е. время от момента

t до возникновения очередного события в потоке j (рис. 2). Для непоявления события (A/A1) достаточно вместо условия т2 > t выполнения условия т2 > t. Аналогично для непоявления события (A/A2) достаточно выполнения условия т1 > t. Тогда интересующее нас событие A, т.е. т^ > t, распадается на два несовместных события.

1. Остаточное время т2 больше t ( т2 > t ) при условии непоявления очередного события в потоке П1 за время (0, t), т.е. при т1 > t. Вероятность этого равна р(т'2 > t)p(т1 > t)X1 /. Этот случай показан на рис. 2.

2. Остаточное время т1 больше t ( т1 > t ) при условии непоявления очередного события в потоке П2 за время (0, t), т.е. при т2 > t. Вероятность этого равна р(т1 > t)р(т2 > t)À,2 / .

Из математической теории надежности известно [5], что функция распределения для остаточного времени жизни элемента, т.е. вероятность безотказной работы элемента на интервале времени (t, t + т ), до очередного отказа определяется как

1 œ

Р(£ > т) = — j [1 - Ft (t)] dt,

где Г0 = 1/ X — среднее время жизни элемента. Применительно к нашему случаю это будет вероятность

ю

р(т' > г) = -у | [1 - ^у (и)] ёи.

г

Тогда интересующая нас вероятность события р(т£ > г) по формуле полной вероятности может быть записана в виде

р

где ХЕ = + X2, а Xу / X2 представляет собой долю у-го потока в результирующем. Утверждение 1 доказано.

Теперь, используя функцию распределения (2), можно определить среднее значение т £ и дисперсию его распределения. Как известно из [5], средние значения интервалов между событиями в потоках равны: т1 = ^1(0), т2 = й2(0):

ю ю

Й

г г

Функции Й1 (0), й2 (0) равны соответствующим средним значениям интервалов времени в

потоках. Несложно показать, что функция плотности распределения вероятности будет следующей:

4 (г) = (г) = --2 [й1 (г)Й2(г)] V

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

ю 1 1 ю Л 1 ю

тЕ = Гг/ (г)ёг = --2Гг[&($№)?* = --2г[^г^г)]' ю - Г[й1(г)й2(г)]'ёг = — (5) о о о -

что подтверждает справедливость выражения (2).

Определим теперь второй начальный момент распределения интервала тЕ для вычисления дисперсии этой случайной величины:

да ^ ^ да ^ ^ да

м

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

- - да 1 Б

-Е 0 -1

Из выражения (7) вытекают два важных следствия.

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

2. Этот интеграл можно вычислить только при конкретных функциях распределения Fj(t). Тогда, в условиях неполной информации о потоках, остается единственно возможный путь для его вычисления через элементарные функции — это аппроксимация функций распределения р.. (г), /=1, 2, на уровне двух первых моментов распределения интервалов времени. Таким образом, будем считать, что исходные потоки в сетевых моделях определены на

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

^ ]

деления р(г) будем аппроксимировать по отдельности при с^- < 1 и с^- > 1 -=1, 2 ).

В качестве примера возьмем два экспоненциально распределенных потока с параметрами X и X2: *!(0 = 1 -е-^, ¿2(0 = 1 - е 2 . Тогда по формуле (5) дисперсия величины тЕ будет

2

следующей: Бт = 1/ . Это означает, что при мультиплексировании потоков, распределенных по экспоненциальному закону, снова получается пуассоновский поток.

Определение неизвестных параметров аппроксимирующих функций распределения. В качестве функции распределения в случае с^ - < 1 рассмотрим смещенное экспоненциальное распределение, а в случае с^ - > 1 — гиперэкспоненциальное. Функция распределения в первом случае

0, г < т,

Р

1 - ехР{-(г -т-1)/ т-2 } г >т

а во втором

р

Теперь возникает задача определения неизвестных параметров соотношений (8) и (9). Для этого определяем функции й- (г), -=1, 2, из выражений (4) через функции (8) и (9), в зависимости от величин с^ - .

Если при этом один поток будет иметь коэффициент вариации меньше единицы, а другой — больше единицы, то в таком случае функции й - (г), очевидно, будут скомбинированы

из выражений (8) и (9). Параметры искомых аппроксимирующих функций распределения (8) и (9) подберем, используя метод моментов, приравняв первые два их момента к соответствующим моментам т- и Бт. распределения исходных потоков. Математическое ожидание

и дисперсия случайной величины, распределенной по закону (8), соответственно равны:

Т =ТУ1 +Т/2,

пределения (8):

В*. = т22 (л = 1,2). Используя метод моментов, найдем параметры функции рас-

т л = Т

Ч

Вт

т л 2 ^

л -1 \ л

Те же операции аналогичным образом проделаем с функцией распределения (8). Математическое ожидание и дисперсия случайной величины, распределенной по этому закону, соответственно равны: т* =т ., В*. = т2[1/2р. +1/2(1 - р.)] — т2. Теперь методом моментов

найдем параметры этого распределения:

тл =тл

р. = 1/21/4 — "т. /[2(Вт. + )].

Таким образом, параметры функций распределения (^) , аппроксимирующих законы

распределения составляющих результирующего потока, полностью определены для всех случаев с^. < 1 и Сх. >1. Тогда, подставив функции gj (/), .= 1, 2, с однозначно определенными их параметрами в выражение (7), и после вычисления всех интегралов можем определить дисперсию интервала времени мультиплексированного потока.

Расчет дисперсии распределения величины т2 . В формулу

с найденными ранее параметрами распределения (10). Тогда в случае 1ц < 121 имеем

М(т2) = 2]gl(t)g2(t)Л = 2

%1%2 "17

-11

| (т11 +т12 — t)(т21 +т22 — +

1-21 ю

| т12(т21 +т22 — t)exP[—(t — тп)/т12Л + | т12т22 ехР[—(t — т11)/т12 — (t — т21)/т22Л

21

В случае 1ц > т

21

М(т2) = 2 %%2

2

%

"¿1 -11

I (т11 +т12 — t)(т21 +т22 — 0Л + | т22(т11 +т12 — t)exP[— (t — т21)/т22Л +

| т12т22 еХР[—(t — т11)/т12 — ( — т21)/т22]Л?

11

В случае равенства значений тп = 121 второй интеграл в выражениях (13) и (14) будет

равен нулю. Обозначив интегралы в правых частях выражений (13) и (14) через 11, /2, /3, запишем выражение для искомой дисперсии:

2^ 1 _ ^ 1

Дт2) = М (т2)—= 2 %%2(/1 +12 + /3)—-1-.

^2 %2 ^2

%2

%2 2 %2 Теперь те же операции выполним для случая гиперэкспоненциального распределения составляющих. Для этого функции gj ^), определяемые выражением (4) при законе распределения (9) с параметрами распределения (11) и (12), подставим в (7) и получим дисперсию

о

X

21

т

величины т2 при гиперэкспоненциальном распределении составляющих результирующего потока:

( 2(1 - р2) ^

М (т|) = 2 М2| g2(t) Л = 2 М2 ^ П ехр ^ 0 ^ 4 Ы

„о

-2

^ Р1 , Р2 ^

V ч 12;

А +1

ехр

о

-2 Р1 т1

( 2(1 - Р1) Р2

-2

т1

т2

о

-2

т1

т2

А \.

Обозначив интегралы в правой части (16) через 11, /2, /3, /4, запишем выражение для дис-

персии:

Б = 2 Ьк

^ 2 ^Е

ХЕ

Теперь рассмотрим последний случай, когда одна составляющая результирующего потока имеет коэффициент вариации Сх^ < 1, а вторая — С^^ > 1. Не умаляя общности, в качестве функции ^) возьмем соотношение (8), а в качестве функции Ь2 ^) — (9) с известными уже параметрами. Тогда, подставив эти функции в (7), получим

XXю

М (т! ) = 2^ | ^) ь2^) А =

X

!

о

4 1

I {(Т11 +Т12 -1)[ехр(-2p2t / Т2) + ехр(-2(1 - р^^ / т2)](т2 /2)}^ +

| {Т12 exp[-(t - тп) / Т12 ][ехр(-2Р21 / Т2) + ехр(-2(1 - Р2)t / Т2 )](т2 / 2)}dt.

Отсюда, обозначив интегралы в правой части (18) через /" и /'2, запишем выражение для искомой дисперсии

Х1Х 2

Бт = 2

Т! X

(/Г+ /2') -

1

X!

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

Исследование точности полученных формул с помощью имитационного моделирования на широком классе законов распределения показало, что формулы (15) и (17) обеспечивают приемлемые результаты. В то же время точность аппроксимации выражением (19) хуже, чем с использованием полученной в [5] формулы:

БТе =

В табл. 1 приведены некоторые результаты сравнения формул (17), (19) и (20) с имитационным моделированием (генерировалось 10 000 случайных интервалов в каждом потоке). __2

В таблице т и Бт — теоретические моменты, т и £т — соответствующие статистические оценки, строка № 1 — законы распределения — равномерные (0,1), Схj <1, использована формула (18); 2 — законы распределения — равномерный (0,1) и экспоненциальный с Х =2, использована формула (18); 3 — законы распределения — экспоненциальные с Х =2, использована формула

2

БТе = 1/ Хе ; 4 — законы распределения — гиперэкспоненциальный с функцией плотности

т

/(г) = (2р2 /т)ехр{—2рг /т} + [2(1-р)2 /т]ехр{-2(1-р)г/т}, гдер=0,8873, т =1,0, с^ = 2, и равномерный (0,2), с^2 <1, использована формула (19); 5 — законы распределения — гиперэкспонен-

2 2 циальные с функцией плотности /(г) = (2р" / т)ехр{-2рг / т} + [2(1 - ру / т]ехр{-2(1 - р)г / т},

гдер=0,8873; т =1,0; с^^ = 2, использована формула (20); 6 — законы распределения — Вей-

булла с функцией плотности /(г) = р-ага~1в~1 /в / Г(а) с а = 0,5427; в = 1; схj = 2, использована формула (20). Как видно из табл. 1, все результаты, кроме первого случая с равномерными законами, укладываются в статистическую погрешность 5 %.

_Таблица 1

№ т/ V Эт1/ 4 т2 / Ъ Эт 2 / 4 _ _* Ъ / Ъ / 4

1 0,500/0,499 0,083/0,083 0,5/0,5 0,083/0,083 0,25/0,25 0,021/0,037

2 0,500/0,499 0,083/0,084 0,500/0,497 0,250/0,247 0,250/0,248 0,042/0,046

3 0,5/0,5 0,250/0,251 0,500/0,499 0,250/0,249 0,250/0,253 0,0625/0,0628

4 1,000/1,001 4,000/3,996 1,000/0,996 0,333/0,333 0,5/0,5 0,204/0,246

5 1,000/1,023 4,000/4,026 1,000/1,011 4,000/4,012 0,500/0,502 1,000/1,013

6 1,738/1,720 12,09/12,20 1,738/1,730 12,09/12,42 0,869/0,867 3,02/2,86

Математическая операция разрежения потока и вывод уравнений равновесия потоков в сетевых моделях. Рассмотрим теперь задачу вероятностного разрежения (просеивания) потоков.

Утверждение 2. Пусть имеется точка демультиплексирования потока (точка В на рис. 3), в которой заявки с вероятностью р уходят из потока („просеянный" поток П2 на рис. 3). Назовем эту операцию с потоком р-преобразованием. Тогда среднее значение и дисперсия времени между соседними событиями в „просеянном" потоке

Тр = т / р,

Этр = д / р + т 2(1 - р)/р2.

^ . . . (22) Доказательство. Представим поток событий с параметрами ("г, Эт ), где т, Эт — среднее значение и дисперсия времени между соседними событиями, как последовательность случайных точек {г} на оси времени. Случайные интервалы времени между ними обозначим соответственно через тьт2,т3,....

При разрежении П1 случайный интервал времени в П2 — тр равен: т1 — с вероятностью р; (т +12) — с вероятностью рд;

П,

П1

(т1 + т2 + т3)— с вероятностью рд2,.-., (т +...+тг) — с вероят-

V Этр

1-р

П3

Рис. 3

ностью pд ' и т.д.

Здесь вероятность q= 1 - р. Заметим, что р-преобразование потока является его разрежением по случайному закону, в отличие от детерминированного „просеивания" при получении потока Эрланга из простейшего потока.

Определим математическое ожидание величины т с учетом того факта, что поток ре-

куррентный, т.е. M(тi) = M(т), M(т2) = M(т2):

M

d

d

/=1

= рМ (т)-

dq 1

dq 1 - д

(1 - <)2

= М (т)/ р.

2

Для определения дисперсии £>т вычислим второй начальный момент М(т р ):

от

М(тр) = РЕ кМ (т2) + (к2 - к)(М (т))2

к=1

Ч -1 = РЕ[кД + к2(М(т))2]/-1 =

к=1

= рВх Е кч -1 + Р(М(т))2 Е к2 Чк-1 = А / Р + (1 + ч)(М(т))2 / Р2.

к=1 к=1

2

Из полученных соотношений для М(т ) и М(тр ) следует справедливость выражений

(21) и (22). Утверждение 2 доказано.

Следствие. Полученное из формул (21) и (22) выражение для квадрата коэффициента

2 2

вариации просеянного потока Ср = рс + ч позволяет судить о характере распределения этого потока. Как видно из последнего выражения, разрежение (Р-преобразование) исходного потока существенно влияет на его закон распределения. При этом для пуассоновского потока его свойство сохраняется.

Замечание. Для проверки справедливости выражений (21) и (22) также использовалось имитационное моделирование. Случайные интервалы генерировались по экспоненциальному, равномерному и нормальному законам распределения (число испытаний 10 000). Результаты имитационного моделирования, приведенные в табл. 2, полностью подтверждают справедливость утверждения 2 для любых законов распределения: строка № 1 — закон распределения — экспоненциальный с X =2, Р=0,2, ч=0,8; 2 — закон распределения — экспоненциальный с X =0,5, Р=0,2, ч=0,8; 3 — закон распределения — равномерный с о=1, Ь=3, Р=0,2, ч=0,8; 4 — закон распределения — нормальный с тт =2, от =0,5, Р=0,2, ч=0,8; 5 — закон распределения — Вейбулла с а = 0,5427, в = 1, коэффициент вариации Сх = 2, Р=0,2, ч=0,8; 6 — закон распределения — Вейбулла с а = 0,3487, в = 1, коэффициент вариации Сх = 4, Р=0,2, ч=0,8. Следовательно, формулы (21) и (22) в отличие от формул вычисления дисперсии результирующего потока, являются точными. Относительная погрешность моделирования здесь также не превышает 5 %.

Таблица 2

№ т / т * Бт / 5т2 т т т / т* Р Р Бтр / < т / т* ч ч Бтч / <

1 0,500/0,498 0,250/0,249 2,500/2,491 6,250/6,121 0,625/0,622 0,390/0,389

2 2,00/2,01 4,00/4,01 10,00/9,96 100,00/99,33 2,50/2,51 6,250/6,308

3 2,000/2,001 0,333/0,333 10,00/9,99 81,67/84,23 2,50/2,51 1,666/1,703

4 2,000/1,993 0,250/0,249 10,00/9,98 80,25/80,59 2,500/2,497 38,75/38,26

5 1,740/1,754 12,09/11,88 8,69/8,55 120,85/121,34 2,170/2,207 16,05/15,88

6 5,095/5,240 415,25/422,09 25,48/25,90 2595,4/2670,8 6,37/6,54 527,17/546,51

Определение дисперсии распределения интервалов между событиями в выходных потоках узлов. Прежде чем перейти к выводу уравнений равновесия потоков относительно их дисперсий, вернемся к структуре узла сетевой модели (рис. 1), из которой видно, что на вход /-го узла в общем случае поступает агрегированный поток из разреженных потоков с выходов других узлов. Для этого необходимо знать дисперсии распределения интервалов между событиями в выходных потоках. Для этого воспользуемся результатами [4].

Утверждение 3. Пусть т^к, Бвых, , — соответственно средние значения и дисперсии времени между заявками в выходном потоке из СМО 01/0/\/ю и обслуживания. Тогда справедливы следующие аналитические выражения для определения "Гых, Аых:

Твых =тц+ Ро,

^вых = D^ + Р0D{ + p0

где p0 — вероятность того, что обслуженная заявка оставляет СМО пустой, т х и Dx — среднее значение и дисперсия остаточного времени , в течение которого СМО ожидает поступления непосредственно следующей заявки, т.е. времени простоя СМО.

Теперь, по аналогии с уравнениями равновесия потоков на уровне их средних значений (1), можно записать уравнения равновесия относительно их дисперсий:

Авх = ДП0г

Здесь D(nj^Пj) — дисперсия попарно мультиплексируемых выходных потоков Пj_i иПj

от (-1)-го и j-го узлов, поступающих на вход /-го узла после их р-преобразования с дисперсиями (см. формулу (22)):

Dnj = —

pji Pji^j

Вычислить эти дисперсии можно с помощью соотношений (15), (17) и (20) в зависимости от значений коэффициентов вариаций составляющих. В уравнениях (25) параметр Doi = D(no.) означает дисперсию времени в потоке По. от внешнего источника, поступающего на вход i-го узла. Тогда решение уравнений (1), (25) совместно (26) и (24) позволяет декомпозировать сетевую модель на отдельные узлы на уровне двух первых моментов распределения потоков для последующего расчета их характеристик.

Полученные математические результаты по математическому мультиплексированию двух различных потоков реализованы в виде процедуры Multipl (el1, el2, dv1, dv2, dmu, er), где входные параметры el1, el2, dv1, dv2 — соответственно интенсивность ^2 и дисперсия DT1, DT2 двух агрегируемых потоков. Выходные параметры dmu, er — соответственно дисперсия результирующего потока DT и код ошибки. Данная процедура входит в программную

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

1. Сеть массового обслуживания считаем экспоненциальной и, решив систему уравнений (1), определяем интенсивность потоков на входе и выходе каждого узла. Следовательно, будут определены средние значения и дисперсии интервалов времени в потоках на входе и выходе каждого узла.

2. Используем метод двумерной диффузионной аппроксимации процессов функционирования систем массового обслуживания и уточняем дисперсии входных и выходных потоков по формуле (25) совместно с соотношениями (24) и (26).

3. Определяем все основные узловые и сетевые характеристики.

Заключение. В классической литературе по теории массового обслуживания недостаточно внимания уделено вычислению моментных характеристик мультиплексированных (агрегированных) и демультиплексированных (разреженных) потоков. Например, в монографии [6] приводятся формулы для дисперсии результирующего потока в случае предельного пуас-соновского потока, а разреженного — в случае потоков Пальма. Следует заметить, что приведенные в настоящей работе результаты справедливы для любых стационарных потоков.