МОДЕЛИРОВАНИЕ ТРАФИКА В КОМПЬЮТЕРНЫХ СЕТЯХ С ПОМОЩЬЮ ПОТОКОВ СОБЫТИЙ
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 681.3
Н. Ф. БАХАРЕВА
МОДЕЛИРОВАНИЕ ТРАФИКА В КОМПЬЮТЕРНЫХ СЕТЯХ С ПОМОЩЬЮ ПОТОКОВ СОБЫТИЙ
На основе математических моделей агрегирования и разрежения потоков событий получены уравнения равновесия потоков, которые описываются на уровне двух первых моментов распределений времени между событиями в них. Полученные уравнения позволяют декомпозировать сетевые модели на отдельные узлы и рассчитывать их характеристики.
Ключевые слова: характеристики распределения потоков, математическое мультиплексирование и демультиплексирование потоков, аппроксимация законов распределений и потоков, уравнения равновесия потоков в сетевых моделях.
Введение. Задача анализа производительности сети заключается в определении всех основных узловых и сетевых характеристик. Для ее решения модель задачи должна быть предварительно декомпозирована на отдельные узлы с последующим вычислением характеристик входных и выходных потоков в каждом узле. Далее могут быть вычислены узловые и сетевые характеристики.
В настоящее время не существует аналитических методов для точного определения характеристик потоков в сетевых моделях при произвольных законах распределения времени поступления и обслуживания.
Постановка задачи и подход к ее решению. Пусть имеется открытая сетевая модель с матрицей вероятности передач P={pij}, i, j = 1,…,n, где pij — вероятность того, что заявка, покидающая узел Si, поступит в узел Sj. Для начала пусть узел представляет собой одноканальную (многоканальную с равновозможным доступом) систему GI/G/1 c бесконечной очередью. Для этой системы определены числовые характеристики случайного времени обслуживания: τµi — среднее значение времени обслуживания, Dµi — его дисперсия. Для внешнего потока задана совокупность средних значений τ0i и дисперсий D0i времени между соседними заявками µ рекуррентного потока, входящего в узел Si. В последующем узел может быть представлен как система массового обслуживания (СМО) с конечной очередью с потерями, а также с конечной очередью без потерь.
Для декомпозиции такой модели на уровне средних значений и дисперсий времени поступления и обслуживания заявок не существует точных методов. Во многих случаях (см., например, работы [1, 2]) пользуются только уравнениями равновесия потоков с учетом их интенсивности λi . Такой подход при произвольных потоках в сети массового обслуживания означает описание случайного потока событий только его средним значением, т.е. математическим ожиданием без учета моментов высшего порядка. Как известно, случайный процесс на практике чаще всего определяется такими характеристиками, как математическое ожидание,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
14 Н. Ф. Бахарева
дисперсия и ковариационная функция. Поэтому учет дисперсий (вторых моментов распреде-
лений) интервалов времени существенно может улучшить результаты расчетов. Описание потоков на уровне двух первых моментов распределения интервалов времени означает их
аппроксимацию непрерывным диффузионным процессом с соответствующими характери-
стиками [1, 3, 4] либо аппроксимацию законов их распределения известными функциями.
Решением системы уравнений равновесия потоков относительно интенсивности λi потоков на входе и выходе каждой системы массового обслуживания сети определяем средние
значения
интервалов времени
между соседними
заявками
τ
=
λ
−1 i
для
каждого
потока
в сети:
n
∑λi = λ0i + pjiλ j , i = 1, ..., n, j=1
(1)
где λ0i — интенсивность потока в i-й узел. Из уравнений (1) следует, что на вход i-го узла в общем случае поступает агрегированный
поток (знак суммы) из разреженных потоков (произведение интенсивности на вероятность переходов) с выходов других узлов. В связи с этим подробнее рассмотрим математические опера-
ции агрегирования (мультиплексирования) двух потоков и их разрежения (демультиплексирования). При этом в качестве математической модели потока рассматриваем случайный поток
событий на оси времени.
Математическая модель мультиплексирования потоков. Предварительно докажем следующее утверждение.
Утверждение 1. Функция распределения интервала времени τΣ результирующего пото-
ка при мультиплексировании двух потоков с интенсивностью λ1 и λ2 определяется интегральным соотношением:
∫ ∫FτΣ
(t )
=
1
−
λ1λ 2 λ1 + λ2
{[1
−
Fτ1
∞
(t)] [1
t
−
Fτ2
(u)]du
+
[1
−
Fτ2
∞
(t)] [1 −
t
Fτ1
(u)]du}
,
(2)
где Fτ j (t) — функция распределения интервалов времени между событиями в потоке j (j=1, 2).
Доказательство. На рис. 1, 2 приведены схемы математического мультиплексирования двух потоков (П), т.е. получения результирующего потока.
τ–1, Dτ1 –τ2, Dτ2
A
–τΣ, DτΣ
Рис. 1 τ1(1) τ1(2) τ1(3)
0
t
τ
1′
t1(1) τ(21)
t
(1) 2
τ
(2) 2
t
(1) 3
τ
(3) 2
t
(1) 4
0
t1(2) t
τ2′
t
(2) 2
t
(2) 3
t
(2 4
)
τ
(1) Σ
τ
(2 Σ
)
τ
(3) Σ
0
t1(2) t
t1(1)
t
(2) 2
t
(1) 2
t
(2) 3
t
(1) 3
t
(2) 4
t
(1) 4
Рис. 2
t П1 t П2 t ПΣ
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Моделирование трафика в компьютерных сетях с помощью потоков событий
15
Введем в рассмотрение следующие события: A — за время t в суммарном потоке не поя-
вится очередное событие ( τΣ > t ); A j — непоявление события в j-м потоке за время t
( τ j > t ), j =1, 2. Кроме того, рассмотрим остаточное время τ′j (j=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 . Вероятность этого равна p(τ2′ > t) p(τ1 > t)λ1 / λΣ . Этот случай показан на рис. 2.
2. Остаточное время τ1′ больше t ( τ1′ > t ) при условии непоявления очередного события в потоке П2 за время (0, t), т.е. при τ2 > t . Вероятность этого равна p(τ1′ > t) p(τ2 > t)λ2 / λΣ .
Из математической теории надежности известно [5], что функция распределения для остаточного времени ξ жизни элемента, т.е. вероятность безотказной работы элемента на ин-
тервале времени (t, t + τ ), до очередного отказа определяется как
∫p(ξ
>
τ)
=
1 T0
∞
[1
τ
−
Fτ
(t )] dt
,
где T0 = 1/ λ — среднее время жизни элемента. Применительно к нашему случаю это будет
вероятность
∞
∫p(τ′j > t) = λ j [1 − Fτ j (u)] du . t
Тогда интересующая нас вероятность события p(τΣ > t) по формуле полной вероятности может быть записана в виде
p(τΣ > t) = p(τ1 > t) p(τ′2 > t)λ1 / λΣ + p(τ2 > t) p(τ1′ > t)λ2 / λΣ ,
(3)
где λ Σ = λ1 + λ2 , а λ j / λΣ представляет собой долю j-го потока в результирующем. Утвер-
ждение 1 доказано.
Теперь, используя функцию распределения (2), можно определить среднее значение τΣ и дисперсию его распределения. Как известно из [5], средние значения интервалов между событиями в потоках равны: τ1 = g1(0), τ2 = g2 (0) :
∞∞
g1 (t) = ∫ [1 − F1 (u)] du g2 (t ) = ∫ [1 − F2 (u )] du .
(4)
tt
Функции g1(0), g2 (0) равны соответствующим средним значениям интервалов времени в
потоках. Несложно показать, что функция плотности распределения вероятности будет сле-
дующей:
fτΣ
(t )
=
Fτ′Σ
(t )
=
λ1λ2 λΣ
[g1(t)g2 (t)]′′ .
Математическое ожидание, т.е. среднее значение интервала между событиями в резуль-
тирующем потоке, будет следующим:
∫ ∫ ∫τΣ
=
∞
t
0
fτΣ (t)dt
=
λ1λ2 λΣ
∞ 0
t
[
g1
(t)g2
(t)]′′dt
=
λ1λ2 λΣ
t[g1(t)g2 (t)]′
∞ 0
∞
− [g1(t)g2 (t)]′dt
0
=
1 λΣ
,
что подтверждает справедливость выражения (2).
(5)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
16 Н. Ф. Бахарева
Определим теперь второй начальный момент распределения интервала τΣ для вычисления дисперсии этой случайной величины:
∫ ∫ ∫M (τΣ2 )
=
∞
t2
0
fΣ (t)dt
=
λ1λ2 λΣ
∞
t2[g1(t)g2 (t)]′′dt
0
=
2
λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt.
Тогда дисперсия времени между событиями в результирующем потоке
(6)
∫D(τΣ )
=
2 λ1λ2 λΣ
∞ 0
g1(t)g2 (t)dt
−
1 λΣ2
.
Из выражения (7) вытекают два важных следствия.
(7)
1. Под интегралом в выражении (6) стоит произведение двух функций, таким образом, в общем случае дисперсию величины τΣ — интервала времени между событиями результи-
рующего потока — нельзя выразить в виде элементарной функции от дисперсий и математических ожиданий составляющих (кроме случая пуассоновских потоков). Таким образом, дис-
персия и моменты высших порядков распределения величины τΣ в этом случае неразложимы. 2. Этот интеграл можно вычислить только при конкретных функциях распределения
Fj(t). Тогда, в условиях неполной информации о потоках, остается единственно возможный путь для его вычисления через элементарные функции — это аппроксимация функций рас-
пределения Fτi (t) , i=1, 2, на уровне двух первых моментов распределения интервалов времени. Таким образом, будем считать, что исходные потоки в сетевых моделях определены на
уровне средних значений τj и дисперсий Dτ j распределения интервалов, и функции распре-
деления Fj(t) будем аппроксимировать по отдельности при cλ j ≤1 и cλ j > 1 (j=1, 2 ).
В качестве примера возьмем два экспоненциально распределенных потока с параметра-
ми λ1и λ2 : F1(t) = 1− e−λ1t , F2(t) = 1− e−λ2t . Тогда по формуле (5) дисперсия величины τΣ будет следующей: DτΣ = 1/ λΣ2 . Это означает, что при мультиплексировании потоков, распределенных по экспоненциальному закону, снова получается пуассоновский поток.
Определение неизвестных параметров аппроксимирующих функций распределе-
ния. В качестве функции распределения в случае cλ j < 1 рассмотрим смещенное экспоненциальное распределение, а в случае cλ j > 1 — гиперэкспоненциальное.
Функция распределения в первом случае
Fj (t) = ⎨⎪⎧⎩⎪10,−te≤xpτ{j−1,(t − τ j1) / τ j2}, t ≥ τ j1,
(8)
а во втором
Fj∗(t) =1− pj exp(−2pjt / τ j ) − (1− pj )exp[−2(1− pj )t / τj ].
(9)
Теперь возникает задача определения неизвестных параметров соотношений (8) и (9).
Для этого определяем функции g j (t) , j=1, 2, из выражений (4) через функции (8) и (9), в за-
висимости от величин cλ j .
Если при этом один поток будет иметь коэффициент вариации меньше единицы, а дру-
гой — больше единицы, то в таком случае функции g j (t) , очевидно, будут скомбинированы
из выражений (8) и (9). Параметры искомых аппроксимирующих функций распределения (8)
и (9) подберем, используя метод моментов, приравняв первые два их момента к соответст-
вующим моментам τ j и Dτ j распределения исходных потоков. Математическое ожидание
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Моделирование трафика в компьютерных сетях с помощью потоков событий
17
и дисперсия случайной величины, распределенной по закону (8), соответственно равны:
τ∗j = τj1 + τj2, Dτ∗j = τ2j2 ( j = 1, 2). Используя метод моментов, найдем параметры функции распределения (8):
τ j1 = τ j − Dτ j , τ j2 = Dτ j .
(10)
Те же операции аналогичным образом проделаем с функцией распределения (8). Математическое ожидание и дисперсия случайной величины, распределенной по этому закону, со-
ответственно равны: τ∗j = τ j , Dτ∗j = τ2j [1 / 2 p j + 1 / 2(1 − p j )] − τ2j . Теперь методом моментов найдем параметры этого распределения:
τj = τj,
(11)
pj = 1/ 2 ±
1/ 4 −
τ
2 j
/[2(Dτ j
+
τ
2 j
)
]
.
(12)
Таким образом, параметры функций распределения Fj∗ (t) , аппроксимирующих законы распределения Fj(t), составляющих результирующего потока, полностью определены для всех
случаев cλ j ≤ 1 и cλ j >1. Тогда, подставив функции g j (t) , j=1, 2, с однозначно определен-
ными их параметрами в выражение (7), и после вычисления всех интегралов можем опреде-
лить дисперсию интервала времени мультиплексированного потока.
Расчет дисперсии распределения величины τΣ . В формулу (6) подставим функции (4)
с найденными ранее параметрами распределения (10). Тогда в случае τ11 < τ21 имеем
∫ ∫M(τΣ2 )
=
2
λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt
=
2
λ1λ2 λΣ
⎪⎧τ11 ⎨
(τ11
⎪⎩ 0
+
τ12
− t)(τ21
+
τ22
− t)dt
+
∫ ∫τ21
+ τ12 (τ21
+
τ22
− t)exp[−(t
− τ11) / τ12 ]dt
+
∞
τ12τ22
exp[−(t
− τ11) / τ12
− (t
⎫ − τ21) / τ22]dt⎪⎬.
(13)
τ11 τ21
⎭⎪
В случае τ11 > τ21
∫ ∫M
(τΣ2
)
=
2
λ1λ2 λΣ
⎪⎧τ21 ⎨ ⎩⎪ 0
(τ11
+
τ12
−
t)(τ21
+
τ22
−
t)dt
τ11 +
τ21
τ22
(τ11
+
τ12
−
t)
exp[−(t
−
τ21)
/
τ22
]dt
+
∫∞
+ τ11
τ12τ22
exp[−(t
−
τ11)
/
τ12
−
(t
−
τ21)
/
⎫ τ22 ]dt ⎬⎪.
⎭⎪
(14)
В случае равенства значений τ11 = τ21 второй интеграл в выражениях (13) и (14) будет
равен нулю. Обозначив интегралы в правых частях выражений (13) и (14) через I1, I2, I3, запишем выражение для искомой дисперсии:
D(τΣ
)
=
M
(τΣ2
)
−
1 λΣ2
= 2 λ1λ2 λΣ
(I1 + I2
+
I3
)
−
1 λΣ2
.
(15)
Теперь те же операции выполним для случая гиперэкспоненциального распределения
составляющих. Для этого функции g j (t) , определяемые выражением (4) при законе распре-
деления (9) с параметрами распределения (11) и (12), подставим в (7) и получим дисперсию
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
18 Н. Ф. Бахарева
величины τΣ при гиперэкспоненциальном распределении составляющих результирующего потока:
∫ ∫ ∫M
(τΣ2 )
=
2
λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt
=
2
λ1λ2 λΣ
τ1τ2 4
⎪⎧∞ ⎨
exp
⎡⎢−2
⎛ ⎜
⎩⎪ 0 ⎣ ⎝
p1 τ1
+
p2 τ2
⎞ ⎟
t
⎤⎥dt
⎠⎦
+
∞ exp ⎡⎢−2 0⎣
p1 τ1
⎛ ⎜
+
⎝
2(1 − p2 ) τ2
⎞ ⎟
t
⎤ ⎥
dt
⎠⎦
+
∫ ∫∞
+
exp
⎡ ⎢
−2
⎛ ⎜
0 ⎣⎝
2(1 − p1) τ1
+
p2 τ2
⎞ ⎟
t
⎤ ⎥
dt
⎠⎦
+
∞
exp
⎡⎢−2
⎛ ⎜
0 ⎣⎝
2(1 − τ1
p1 )
+
2(1 − p2 ) τ2
⎞ ⎟
t
⎤ ⎥
⎠⎦
dt ⎫⎪⎬. ⎪⎭
(16)
Обозначив интегралы в правой части (16) через I1, I2, I3, I4, запишем выражение для дисперсии:
DτΣ
=
2
λ1λ 2 λΣ
(I1′ + I2′
+
I3′
+ I4′ ) −
1
λ
2 Σ
.
(17)
Теперь рассмотрим последний случай, когда одна составляющая результирующего по-
тока имеет коэффициент вариации cλ j < 1, а вторая — cλ j > 1 . Не умаляя общности, в каче-
стве функции g1(t) возьмем соотношение (8), а в качестве функции g2 (t) — (9) с известны-
ми уже параметрами. Тогда, подставив эти функции в (7), получим
∫M (τΣ2 )
=
2 λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt
=
τ11
∫= {(τ11 + τ12 − t)[exp(−2 p2t / τ2 ) + exp(−2(1 − p2 )t / τ2 )](τ2 / 2)}dt +
0
∞
∫+ {τ12 exp[−(t − τ11) / τ12 ][exp(−2 p2t / τ2 ) + exp(−2(1 − p2 )t / τ2 )](τ2 / 2)}dt.
(18)
τ11
Отсюда, обозначив интегралы в правой части (18) через I1′′ и I 2′′ , запишем выражение для искомой дисперсии
DτΣ
= 2 λ1λ2 λΣ
(I1′′+
I2′′)
−
1 λΣ2
.
(19)
Таким образом, используя полученные соотношения (15), (17) и (19), в зависимости от
коэффициентов вариаций составляющих потока, можно определить дисперсию результи-
рующего потока указанным способом.
Исследование точности полученных формул с помощью имитационного моделирования
на широком классе законов распределения показало, что формулы (15) и (17) обеспечивают
приемлемые результаты. В то же время точность аппроксимации выражением (19) хуже, чем
с использованием полученной в [5] формулы:
DτΣ = (λ1/λΣ )3 Dτ1 + (λ2 /λΣ )3 Dτ2 .
(20)
В табл. 1 приведены некоторые результаты сравнения формул (17), (19) и (20) с имита-
ционным моделированием (генерировалось 10 000 случайных интервалов в каждом потоке).
В таблице τ и Dτ — теоретические моменты, τ∗ и Sτ2 — соответствующие статистические
оценки, строка № 1 — законы распределения — равномерные (0,1), cλ j
УДК 681.3
Н. Ф. БАХАРЕВА
МОДЕЛИРОВАНИЕ ТРАФИКА В КОМПЬЮТЕРНЫХ СЕТЯХ С ПОМОЩЬЮ ПОТОКОВ СОБЫТИЙ
На основе математических моделей агрегирования и разрежения потоков событий получены уравнения равновесия потоков, которые описываются на уровне двух первых моментов распределений времени между событиями в них. Полученные уравнения позволяют декомпозировать сетевые модели на отдельные узлы и рассчитывать их характеристики.
Ключевые слова: характеристики распределения потоков, математическое мультиплексирование и демультиплексирование потоков, аппроксимация законов распределений и потоков, уравнения равновесия потоков в сетевых моделях.
Введение. Задача анализа производительности сети заключается в определении всех основных узловых и сетевых характеристик. Для ее решения модель задачи должна быть предварительно декомпозирована на отдельные узлы с последующим вычислением характеристик входных и выходных потоков в каждом узле. Далее могут быть вычислены узловые и сетевые характеристики.
В настоящее время не существует аналитических методов для точного определения характеристик потоков в сетевых моделях при произвольных законах распределения времени поступления и обслуживания.
Постановка задачи и подход к ее решению. Пусть имеется открытая сетевая модель с матрицей вероятности передач P={pij}, i, j = 1,…,n, где pij — вероятность того, что заявка, покидающая узел Si, поступит в узел Sj. Для начала пусть узел представляет собой одноканальную (многоканальную с равновозможным доступом) систему GI/G/1 c бесконечной очередью. Для этой системы определены числовые характеристики случайного времени обслуживания: τµi — среднее значение времени обслуживания, Dµi — его дисперсия. Для внешнего потока задана совокупность средних значений τ0i и дисперсий D0i времени между соседними заявками µ рекуррентного потока, входящего в узел Si. В последующем узел может быть представлен как система массового обслуживания (СМО) с конечной очередью с потерями, а также с конечной очередью без потерь.
Для декомпозиции такой модели на уровне средних значений и дисперсий времени поступления и обслуживания заявок не существует точных методов. Во многих случаях (см., например, работы [1, 2]) пользуются только уравнениями равновесия потоков с учетом их интенсивности λi . Такой подход при произвольных потоках в сети массового обслуживания означает описание случайного потока событий только его средним значением, т.е. математическим ожиданием без учета моментов высшего порядка. Как известно, случайный процесс на практике чаще всего определяется такими характеристиками, как математическое ожидание,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
14 Н. Ф. Бахарева
дисперсия и ковариационная функция. Поэтому учет дисперсий (вторых моментов распреде-
лений) интервалов времени существенно может улучшить результаты расчетов. Описание потоков на уровне двух первых моментов распределения интервалов времени означает их
аппроксимацию непрерывным диффузионным процессом с соответствующими характери-
стиками [1, 3, 4] либо аппроксимацию законов их распределения известными функциями.
Решением системы уравнений равновесия потоков относительно интенсивности λi потоков на входе и выходе каждой системы массового обслуживания сети определяем средние
значения
интервалов времени
между соседними
заявками
τ
=
λ
−1 i
для
каждого
потока
в сети:
n
∑λi = λ0i + pjiλ j , i = 1, ..., n, j=1
(1)
где λ0i — интенсивность потока в i-й узел. Из уравнений (1) следует, что на вход i-го узла в общем случае поступает агрегированный
поток (знак суммы) из разреженных потоков (произведение интенсивности на вероятность переходов) с выходов других узлов. В связи с этим подробнее рассмотрим математические опера-
ции агрегирования (мультиплексирования) двух потоков и их разрежения (демультиплексирования). При этом в качестве математической модели потока рассматриваем случайный поток
событий на оси времени.
Математическая модель мультиплексирования потоков. Предварительно докажем следующее утверждение.
Утверждение 1. Функция распределения интервала времени τΣ результирующего пото-
ка при мультиплексировании двух потоков с интенсивностью λ1 и λ2 определяется интегральным соотношением:
∫ ∫FτΣ
(t )
=
1
−
λ1λ 2 λ1 + λ2
{[1
−
Fτ1
∞
(t)] [1
t
−
Fτ2
(u)]du
+
[1
−
Fτ2
∞
(t)] [1 −
t
Fτ1
(u)]du}
,
(2)
где Fτ j (t) — функция распределения интервалов времени между событиями в потоке j (j=1, 2).
Доказательство. На рис. 1, 2 приведены схемы математического мультиплексирования двух потоков (П), т.е. получения результирующего потока.
τ–1, Dτ1 –τ2, Dτ2
A
–τΣ, DτΣ
Рис. 1 τ1(1) τ1(2) τ1(3)
0
t
τ
1′
t1(1) τ(21)
t
(1) 2
τ
(2) 2
t
(1) 3
τ
(3) 2
t
(1) 4
0
t1(2) t
τ2′
t
(2) 2
t
(2) 3
t
(2 4
)
τ
(1) Σ
τ
(2 Σ
)
τ
(3) Σ
0
t1(2) t
t1(1)
t
(2) 2
t
(1) 2
t
(2) 3
t
(1) 3
t
(2) 4
t
(1) 4
Рис. 2
t П1 t П2 t ПΣ
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Моделирование трафика в компьютерных сетях с помощью потоков событий
15
Введем в рассмотрение следующие события: A — за время t в суммарном потоке не поя-
вится очередное событие ( τΣ > t ); A j — непоявление события в j-м потоке за время t
( τ j > t ), j =1, 2. Кроме того, рассмотрим остаточное время τ′j (j=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 . Вероятность этого равна p(τ2′ > t) p(τ1 > t)λ1 / λΣ . Этот случай показан на рис. 2.
2. Остаточное время τ1′ больше t ( τ1′ > t ) при условии непоявления очередного события в потоке П2 за время (0, t), т.е. при τ2 > t . Вероятность этого равна p(τ1′ > t) p(τ2 > t)λ2 / λΣ .
Из математической теории надежности известно [5], что функция распределения для остаточного времени ξ жизни элемента, т.е. вероятность безотказной работы элемента на ин-
тервале времени (t, t + τ ), до очередного отказа определяется как
∫p(ξ
>
τ)
=
1 T0
∞
[1
τ
−
Fτ
(t )] dt
,
где T0 = 1/ λ — среднее время жизни элемента. Применительно к нашему случаю это будет
вероятность
∞
∫p(τ′j > t) = λ j [1 − Fτ j (u)] du . t
Тогда интересующая нас вероятность события p(τΣ > t) по формуле полной вероятности может быть записана в виде
p(τΣ > t) = p(τ1 > t) p(τ′2 > t)λ1 / λΣ + p(τ2 > t) p(τ1′ > t)λ2 / λΣ ,
(3)
где λ Σ = λ1 + λ2 , а λ j / λΣ представляет собой долю j-го потока в результирующем. Утвер-
ждение 1 доказано.
Теперь, используя функцию распределения (2), можно определить среднее значение τΣ и дисперсию его распределения. Как известно из [5], средние значения интервалов между событиями в потоках равны: τ1 = g1(0), τ2 = g2 (0) :
∞∞
g1 (t) = ∫ [1 − F1 (u)] du g2 (t ) = ∫ [1 − F2 (u )] du .
(4)
tt
Функции g1(0), g2 (0) равны соответствующим средним значениям интервалов времени в
потоках. Несложно показать, что функция плотности распределения вероятности будет сле-
дующей:
fτΣ
(t )
=
Fτ′Σ
(t )
=
λ1λ2 λΣ
[g1(t)g2 (t)]′′ .
Математическое ожидание, т.е. среднее значение интервала между событиями в резуль-
тирующем потоке, будет следующим:
∫ ∫ ∫τΣ
=
∞
t
0
fτΣ (t)dt
=
λ1λ2 λΣ
∞ 0
t
[
g1
(t)g2
(t)]′′dt
=
λ1λ2 λΣ
t[g1(t)g2 (t)]′
∞ 0
∞
− [g1(t)g2 (t)]′dt
0
=
1 λΣ
,
что подтверждает справедливость выражения (2).
(5)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
16 Н. Ф. Бахарева
Определим теперь второй начальный момент распределения интервала τΣ для вычисления дисперсии этой случайной величины:
∫ ∫ ∫M (τΣ2 )
=
∞
t2
0
fΣ (t)dt
=
λ1λ2 λΣ
∞
t2[g1(t)g2 (t)]′′dt
0
=
2
λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt.
Тогда дисперсия времени между событиями в результирующем потоке
(6)
∫D(τΣ )
=
2 λ1λ2 λΣ
∞ 0
g1(t)g2 (t)dt
−
1 λΣ2
.
Из выражения (7) вытекают два важных следствия.
(7)
1. Под интегралом в выражении (6) стоит произведение двух функций, таким образом, в общем случае дисперсию величины τΣ — интервала времени между событиями результи-
рующего потока — нельзя выразить в виде элементарной функции от дисперсий и математических ожиданий составляющих (кроме случая пуассоновских потоков). Таким образом, дис-
персия и моменты высших порядков распределения величины τΣ в этом случае неразложимы. 2. Этот интеграл можно вычислить только при конкретных функциях распределения
Fj(t). Тогда, в условиях неполной информации о потоках, остается единственно возможный путь для его вычисления через элементарные функции — это аппроксимация функций рас-
пределения Fτi (t) , i=1, 2, на уровне двух первых моментов распределения интервалов времени. Таким образом, будем считать, что исходные потоки в сетевых моделях определены на
уровне средних значений τj и дисперсий Dτ j распределения интервалов, и функции распре-
деления Fj(t) будем аппроксимировать по отдельности при cλ j ≤1 и cλ j > 1 (j=1, 2 ).
В качестве примера возьмем два экспоненциально распределенных потока с параметра-
ми λ1и λ2 : F1(t) = 1− e−λ1t , F2(t) = 1− e−λ2t . Тогда по формуле (5) дисперсия величины τΣ будет следующей: DτΣ = 1/ λΣ2 . Это означает, что при мультиплексировании потоков, распределенных по экспоненциальному закону, снова получается пуассоновский поток.
Определение неизвестных параметров аппроксимирующих функций распределе-
ния. В качестве функции распределения в случае cλ j < 1 рассмотрим смещенное экспоненциальное распределение, а в случае cλ j > 1 — гиперэкспоненциальное.
Функция распределения в первом случае
Fj (t) = ⎨⎪⎧⎩⎪10,−te≤xpτ{j−1,(t − τ j1) / τ j2}, t ≥ τ j1,
(8)
а во втором
Fj∗(t) =1− pj exp(−2pjt / τ j ) − (1− pj )exp[−2(1− pj )t / τj ].
(9)
Теперь возникает задача определения неизвестных параметров соотношений (8) и (9).
Для этого определяем функции g j (t) , j=1, 2, из выражений (4) через функции (8) и (9), в за-
висимости от величин cλ j .
Если при этом один поток будет иметь коэффициент вариации меньше единицы, а дру-
гой — больше единицы, то в таком случае функции g j (t) , очевидно, будут скомбинированы
из выражений (8) и (9). Параметры искомых аппроксимирующих функций распределения (8)
и (9) подберем, используя метод моментов, приравняв первые два их момента к соответст-
вующим моментам τ j и Dτ j распределения исходных потоков. Математическое ожидание
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Моделирование трафика в компьютерных сетях с помощью потоков событий
17
и дисперсия случайной величины, распределенной по закону (8), соответственно равны:
τ∗j = τj1 + τj2, Dτ∗j = τ2j2 ( j = 1, 2). Используя метод моментов, найдем параметры функции распределения (8):
τ j1 = τ j − Dτ j , τ j2 = Dτ j .
(10)
Те же операции аналогичным образом проделаем с функцией распределения (8). Математическое ожидание и дисперсия случайной величины, распределенной по этому закону, со-
ответственно равны: τ∗j = τ j , Dτ∗j = τ2j [1 / 2 p j + 1 / 2(1 − p j )] − τ2j . Теперь методом моментов найдем параметры этого распределения:
τj = τj,
(11)
pj = 1/ 2 ±
1/ 4 −
τ
2 j
/[2(Dτ j
+
τ
2 j
)
]
.
(12)
Таким образом, параметры функций распределения Fj∗ (t) , аппроксимирующих законы распределения Fj(t), составляющих результирующего потока, полностью определены для всех
случаев cλ j ≤ 1 и cλ j >1. Тогда, подставив функции g j (t) , j=1, 2, с однозначно определен-
ными их параметрами в выражение (7), и после вычисления всех интегралов можем опреде-
лить дисперсию интервала времени мультиплексированного потока.
Расчет дисперсии распределения величины τΣ . В формулу (6) подставим функции (4)
с найденными ранее параметрами распределения (10). Тогда в случае τ11 < τ21 имеем
∫ ∫M(τΣ2 )
=
2
λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt
=
2
λ1λ2 λΣ
⎪⎧τ11 ⎨
(τ11
⎪⎩ 0
+
τ12
− t)(τ21
+
τ22
− t)dt
+
∫ ∫τ21
+ τ12 (τ21
+
τ22
− t)exp[−(t
− τ11) / τ12 ]dt
+
∞
τ12τ22
exp[−(t
− τ11) / τ12
− (t
⎫ − τ21) / τ22]dt⎪⎬.
(13)
τ11 τ21
⎭⎪
В случае τ11 > τ21
∫ ∫M
(τΣ2
)
=
2
λ1λ2 λΣ
⎪⎧τ21 ⎨ ⎩⎪ 0
(τ11
+
τ12
−
t)(τ21
+
τ22
−
t)dt
τ11 +
τ21
τ22
(τ11
+
τ12
−
t)
exp[−(t
−
τ21)
/
τ22
]dt
+
∫∞
+ τ11
τ12τ22
exp[−(t
−
τ11)
/
τ12
−
(t
−
τ21)
/
⎫ τ22 ]dt ⎬⎪.
⎭⎪
(14)
В случае равенства значений τ11 = τ21 второй интеграл в выражениях (13) и (14) будет
равен нулю. Обозначив интегралы в правых частях выражений (13) и (14) через I1, I2, I3, запишем выражение для искомой дисперсии:
D(τΣ
)
=
M
(τΣ2
)
−
1 λΣ2
= 2 λ1λ2 λΣ
(I1 + I2
+
I3
)
−
1 λΣ2
.
(15)
Теперь те же операции выполним для случая гиперэкспоненциального распределения
составляющих. Для этого функции g j (t) , определяемые выражением (4) при законе распре-
деления (9) с параметрами распределения (11) и (12), подставим в (7) и получим дисперсию
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
18 Н. Ф. Бахарева
величины τΣ при гиперэкспоненциальном распределении составляющих результирующего потока:
∫ ∫ ∫M
(τΣ2 )
=
2
λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt
=
2
λ1λ2 λΣ
τ1τ2 4
⎪⎧∞ ⎨
exp
⎡⎢−2
⎛ ⎜
⎩⎪ 0 ⎣ ⎝
p1 τ1
+
p2 τ2
⎞ ⎟
t
⎤⎥dt
⎠⎦
+
∞ exp ⎡⎢−2 0⎣
p1 τ1
⎛ ⎜
+
⎝
2(1 − p2 ) τ2
⎞ ⎟
t
⎤ ⎥
dt
⎠⎦
+
∫ ∫∞
+
exp
⎡ ⎢
−2
⎛ ⎜
0 ⎣⎝
2(1 − p1) τ1
+
p2 τ2
⎞ ⎟
t
⎤ ⎥
dt
⎠⎦
+
∞
exp
⎡⎢−2
⎛ ⎜
0 ⎣⎝
2(1 − τ1
p1 )
+
2(1 − p2 ) τ2
⎞ ⎟
t
⎤ ⎥
⎠⎦
dt ⎫⎪⎬. ⎪⎭
(16)
Обозначив интегралы в правой части (16) через I1, I2, I3, I4, запишем выражение для дисперсии:
DτΣ
=
2
λ1λ 2 λΣ
(I1′ + I2′
+
I3′
+ I4′ ) −
1
λ
2 Σ
.
(17)
Теперь рассмотрим последний случай, когда одна составляющая результирующего по-
тока имеет коэффициент вариации cλ j < 1, а вторая — cλ j > 1 . Не умаляя общности, в каче-
стве функции g1(t) возьмем соотношение (8), а в качестве функции g2 (t) — (9) с известны-
ми уже параметрами. Тогда, подставив эти функции в (7), получим
∫M (τΣ2 )
=
2 λ1λ2 λΣ
∞ 0
g1(t)g2 (t) dt
=
τ11
∫= {(τ11 + τ12 − t)[exp(−2 p2t / τ2 ) + exp(−2(1 − p2 )t / τ2 )](τ2 / 2)}dt +
0
∞
∫+ {τ12 exp[−(t − τ11) / τ12 ][exp(−2 p2t / τ2 ) + exp(−2(1 − p2 )t / τ2 )](τ2 / 2)}dt.
(18)
τ11
Отсюда, обозначив интегралы в правой части (18) через I1′′ и I 2′′ , запишем выражение для искомой дисперсии
DτΣ
= 2 λ1λ2 λΣ
(I1′′+
I2′′)
−
1 λΣ2
.
(19)
Таким образом, используя полученные соотношения (15), (17) и (19), в зависимости от
коэффициентов вариаций составляющих потока, можно определить дисперсию результи-
рующего потока указанным способом.
Исследование точности полученных формул с помощью имитационного моделирования
на широком классе законов распределения показало, что формулы (15) и (17) обеспечивают
приемлемые результаты. В то же время точность аппроксимации выражением (19) хуже, чем
с использованием полученной в [5] формулы:
DτΣ = (λ1/λΣ )3 Dτ1 + (λ2 /λΣ )3 Dτ2 .
(20)
В табл. 1 приведены некоторые результаты сравнения формул (17), (19) и (20) с имита-
ционным моделированием (генерировалось 10 000 случайных интервалов в каждом потоке).
В таблице τ и Dτ — теоретические моменты, τ∗ и Sτ2 — соответствующие статистические
оценки, строка № 1 — законы распределения — равномерные (0,1), cλ j