Моделирование трафика компьютерной сети

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

ХАРАКТЕРИСТИКИ РАСПРЕДЕЛЕНИЯ ПОТОКОВ / МАТЕМАТИЧЕСКОЕ МУЛЬТИПЛЕКСИРОВАНИЕ И ДЕМУЛЬТИПЛЕКСИРОВАНИЕ ПОТОКОВ / АППРОКСИМАЦИЯ ЗАКОНОВ РАСПРЕДЕЛЕНИЙ И ПОТОКОВ / УРАВНЕНИЯ РАВНОВЕСИЯ ПОТОКОВ В СЕТЕВЫХ МОДЕЛЯХ / CHARACTERISTICS OF FLOWS DISTRIBUTION / MATHEMATICAL MULTIPLEXING AND DEMULTIPLEXING OF FLOWS / APPROXIMATION OF DISTRIBUTION LAWS AND FLOWS / EQUILIBRIUM EQUATIONS FOR FLOWS IN NETWORKS MODELS

Аннотация научной статьи по математике, автор научной работы — Бахарева Надежда Федоровна

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

Похожие темы научных работ по математике , автор научной работы — Бахарева Надежда Федоровна

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

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

Расчёт коэффициентов трения и времён релаксации ионов водных растворов KCl и СsCl в зависимости от параметров состояния

Traffic Modeling in Computer Network with the Use of Flow of Events

On the base of mathematical models of aggregating and decimation of events flow, equations are derived for equilibrium flows described by the two first moments of time distribution between the events. The equations allows for decomposition of network models into separate units and calculation of the units characteristics.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство. На рис. 1, 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 + т ), до очередного отказа определяется как

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

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

р(тЕ > г) = р(т1 > г)р(т2 > г)- / -Е + р(т2 > г)р(т1 > г)-2 / -Е, (3)

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

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

Й (г) = |[1 — ^ (и) ] ёи g2 (г) = |[1 — и) ]ёи . (4)

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

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

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

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

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

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

м(т2) = \ г2& т = -р\ г\ЕХ(г)Е2($Ш = 2-р\ й(0й2(г) А. (6)

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

— — да 1 Б (тЕ) = 2-^ | й (г) g 2 (г )Ш — — (7)

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

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

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

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

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

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

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

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

р(г) = 1 -р- ехр(-2р-г/т-)-(1 -р-)ехр[-2(1 -р-)г/т-]. (9)

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

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

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

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

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

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

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

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

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

Расчет дисперсии распределения величины т2 . В формулу (6) подставим функции (4)

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

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

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

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

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

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

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

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

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

Источник