Моделирование сетевого трафика случайным точечным процессом

Моделирование сетевого трафика случайным точечным процессом

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Физико-технический факультет

Кафедра теоретической физики и компьютерных технологий

КУРСОВАЯ РАБОТА

Моделирование сетевого трафика случайным точечным процессом

Работу выполнил

Хозиев Руслан Александрович

Научный руководитель

старший преподаватель

кафедры оптоэлектроники

Н.Р. Рудоман

Краснодар 2015

РЕФЕРАТ

Курсовая работа 24 с., 2 рис., 0 табл., 5 источников, 0 прил.

КОМПЬЮТЕРНЫЕ СЕТИ, ФРАКТАЛЫ, СЕТЕВОЙ ТРАФИК, СЛУЧАЙНЫЕ ТОЧЕЧНЫЕ ПРОЦЕССЫ, МАТЕМАТИЧЕСКИЕ МОДЕЛИ

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

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

В результате работы были выведены формулы, изучены основы моделирования сетевого трафика случайным точечным процессом, сделаны выводы.

Введение

Компьютеры и компьютерные сети стали неотъемлемой частью нынешних методик управления и производства. Вычислительные и коммуникационные возможности современных компьютеров очень возросли, что стало предпосылкой для формирования новейшего класса интегрированных сетевых приложений, таких как интернет-телефония, распознавание голоса, видеоконференция, виртуальная реальность и многих других. Вышеперечисленные приложения работают в интегрированной сетевой среде передачи данных и применяют методы пакетной коммутации. Образованный комплекс сетевых устройств, протоколов и средств управления создаёт базу временной инфраструктуры переработки, хранения и передачи данных высокоскоростных компьютерных телекоммуникаций. В данной сети связь между аппаратами или приложениями проходит путем образования статистически мультиплексируемых виртуальных соединений и перемещения по ним сигналов или сетевых потоков различной природы (например, таких как аудио, видео и компьютерные данные). На свойства этих сигналов значительное влияние оказывают характерные черты устройства сетевой структуры и случайное поведение сигналов в сети.

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

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

1. Моделирование трафика

1.1 Методы формирования моделей

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

Теперь перейдем к определению основных ступеней разработки моделей процессов в сети. Полагаем, что обмен информации происходит между расположенными в пространстве случайно связанными сетью источниками и приемниками. Данное обозначение пользователей является условным, так как в соответствии с определённой ситуацией последние могут быть как источниками, так и приемниками. Методика передачи информации предусматривает, что поток байтов делится на отдельные пакеты (пакетизируется) определённой длины и информация далее передастся на пакетном уровне по дуплексному (двунаправленному) каналу взаимодействия. На приемном конце данные вновь соединяются в поток байтов. Сетевая конфигурация содержит узлы, располагающие в себе сетевые устройства, которые обеспечивают нужные маршруты прохождения пакетов. Транспортировка и распределение информации в сетях совершается пакетными сериями (пачками пакетов). Технология генерации прерывистого потока пачек (сетевого трафика) происходит посредством механизма управления, который осуществляется с помощью протоколов как прикладного, так и транспортного/сетевого уровней (к примеру, протоколами TCP/IP сети Интернет). Назовём особенно значительные причины, которые могут привести к формированию пачечности сетевого трафика. Предположим, что источник-пользователь обслуживает не один приемник. В случае, если даже источник создаёт постоянный поток пакетов, информация до каждого из приемников в связи с ограничениями на скорость работы сетевых устройств (к примеру, из-за лимитированного объема памяти буферов может возникнуть очередь) доставляется пакетными сериями. С позиции приемника-пользователя получаемые данные задерживаются из-за того, их нельзя передать на некоторых временных интервалах. Еще одним показательным примером формирования пачечности сетевого трафика является определяемый вышеперечисленными протоколами механизм установки оценки пропускной способности сети для какой-нибудь пары источник-приемник. Данный механизм осуществляется с помощью проверочных и локальных воздействий (фазы медленного старта TCP-соединения), установки текущего окна перегрузки (разрешенных к передаче числа пакетов до прихода пакетов подтверждения). В силу этого для успешной доставки пакетов нужно ещё потратить время на передачу пакетов подтверждения и повторения передачи утерянных пакетов. Понятно, что на указанном интвервале времени процесс передачи информации замораживается. Также заметим, что из-за непостоянного влияния вышеупомянутых факторов при передаче и распределении информации поведение сетевого графика принимает случайный характер, т.е. трафик в сети образуется случайным образом. Для наглядного толкования перечисленных свойств поведения процессов в сети и поиска путей параметризации этих процессов особо предпочтительным является моделирование сетевого трафика режимом ON/OFF. Давайте разберём протекающий во времени стационарный случайный точечный процесс восстановления, чьи интервалы между точками являются независимыми случайными величинами, которые имеют одинаковую плотность распределения (рис. 1, а). Этому процессу можно придать колебательную форму (рис. 1, б). Пускай началу интервала ON (R > 0) соответствует какая-то точка. Тогда следующая точка будет означать конец интервала и наступление интервала OFF (R = 0). Результатом получится последовательность ON/OFF интервалов, которые будут чередоваться, а их длительности являются случайными, независимыми и для каждого из ON или OFF интервалов одинаковы распределены.

Рисунок 1а - случайный точечный процесс восстановления

Рисунок 1б - колебательная форма процесса восстановления

Рисунок 1в - модель обобщенного сетевого трафика

Уровняем интервал ON с передаваемой серией пакетов, а интервал OFF - с отсутствием передачи пакетов. Высказанные суждения без уточнения пока вида функции распределения ON/OFF интервалов взяты за основу построения модели сетевого трафика. Чтобы упростить решение задачи предположим, что последовательность пакетов в ON интервале имеет регулярный стационарный характер, а сама случайность в сетевом трафике определена лишь статистическим характером ON/OFF интервалов. Один из важнейших этапов в создании моделей сетевого трафика - анализ соответствия поведения этих моделей опытным данным, которые указывают на коррелированность значений трафика в широком временном диапазоне или на протяженную зависимость (ПЗ) его корреляционной функции. По поводу анализа рызных подходов и решений по обнаружению этого соответствия дынных экспериментов, которые сняты на пакетном уровне с разных внутренних коммутаторов в нынешних современных высокоскоростных сетях, написан ряд работ, которые вышли в последнее время. Решающим фактором присутствия данного свойства для рассматриваемой ON/OFF модели является так называемое «тяжелое» распределение, которое определяет тот факт, что вероятности длинных ON и OFF интервалов порядка T (длинных серий пакетов и межсерийных интервалов) могут быть значительными

.

Дисперсии таких интервалов получаются крупными или даже стремятся к бесконечности. В расчетном применении данное затруднение решается с помощью введения ограничений, таких как указание конечных значений пределов интегрирования. Следовательно, дынные, полученные опытным путём, наглядно показывают особенное поведение сетевого трафика, которое не укладывается в границы поведения известных моделей очередей (пуассоновских, марковских, модулированных и т.д.). Для последних моделей коррелированность событий замечается на ограниченных отрезках времени. Таким случайным процессам в отличие от протяженных зависимостей даётся понятие короткопротяженных (КЗ) корреляционных зависимостей. Отметим, что вместе с протяженной зависимостью непосредстенно связанное с ней свойство самоподобия устанавливает фрактальный характер данной функции. Обсуждаемые процессы являются случайными и понятия протяженной зависимости и самоподобия теперь принадлежат к статистикам второго порядка (корреляционной функции, спектральной плотности, дисперсии). Собственно, поведение выборочных значений этих статистик является решающим в разрешении вопроса, имеет ли сетевой трафик фрактальные свойства. Хоть протяженная зависимость и самоподобие различно характеризуют сетевой трафик (в первом случае - «хвост» корреляционной функции, во второй - масштабное поведение этой функции), будем исходить из сложившейся в теории фрактальных процессов эквивалентности этих понятий: протяженная зависимость предполагает наличие самоподобия и наоборот. Уделим внимание специфической особенности понятия самоподобия. Применительно к статистикам второго порядка точечного процесса оно понимается в асимптотическом смысле (асимптотическое подобие второго порядка), т.е. при интервалах наблюдения больше определенного порогового значения (фрактального времени установки) и при агрегировании (суперпозиции) потока данных, что предполагает введение масштабирующих параметров. Суждения, которые высказывались выше, относились к простой ON/OFF модели обмена информации между парой источник - приемник. Бесспорно, чтобы описать работу компьютерной сети более полно и приблизиться к реальным процессам в отдельных узлах этой сети, подходящей является модель, которая предполагает одновременное функционирование многих пар источник - приемник, чему соответствует генерация обобщенного трафика. Модель обобщенного трафика получается в результате агрегирования (суперпозиции) большего числа независимых одинаково распределенных стационарных точечных процессов восстановления (рис. 1, в). Полагая неукоснительное чередование интервалов, получим последовательность этих интервалов по всей совокупности потока точек. Отображая поведение этих случайных интервалов «тяжелым» распределением, получаем обобщенный сетевой трафик, обладающий фрактальными свойствами.

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

1.2 Случайные точечные процессы. Методы определения статистик

Как следует из первого раздела, процесс формирования моделей сетевого трафика основывается на идеях и понятиях теории случайных точечных процессов (потоков). Такой процесс образуют неразличимые события (точки), которые выпадают по случайным законам на временной оси. Осуществление случайного точечного процесса на временной оси t можно представить в виде неубывающей ступенчатой функции, которая принимает неотрицательные целочисленные значения, а моменты её роста (смены состояния) являются случайными, и величина ступенек из-за условия ординарности равна единице (рис. 2).

Рисунок 2 - Реализация случайного точечного процесса

Данный точечный процесс аналитически можно показать в виде

(1)

где единичная функция

Дальше, чтобы описать поведения сетевого трафика, рассматривают специальный класс случайных точечных процессов - потоки восстановления, для которых случайные временные интервалы независимы и имеют одинаковое распределение вероятностей. Параметры потоков восстановления можно получить, привлекая известные в теории случайных процессов функциональные преобразования: характеристический θ(v, T) и производящий L(u, T) функционалы. Характеристический функционал (ХФ) является обобщением Фурье-преобразования плотности вероятности конечномерного случайного процесса {ξ(ti), i = 1, 2, ..., n} при неограниченном увеличении числа отсчетов процесса, соответствующих моментам времени ti(0, T), n → ∞, и определяется отношением [1]

 (2),

где М{} это операция определения математического ожидания; v(t) - вспомогательная действительная функция.

ХФ может быть представлен на интервале (0, Т) в виде разложения в функциональные ряда относительно моментных mn(t) и корреляционных kn(t) функций n-го порядка:

Сравнивая выражения (3) и (4), получим соотношения, связывающие моментные и корреляционные функции:

Чтобы описывать точечные процессы, используют локальные характеристики: моментные fn() и корреляционные gn() функции, которые назовем соответственно функциями плотности и корреляции плотности n-го порядка. Функция плотности n-го порядка fn(t1,...,tn) характеризует совместную вероятность появления n точек в каждом из неперекрывающихся подынтервалов ∆ti безотносительно к появлению дополнительного числа точек на остальных ∆t - подынтервалах интервала (0, Т):

pn = fn(t1, …, ti, …, tn)∆t1 … ∆ti … ∆tn 0(∆t),

где ∆t = max ∆ti,

Функция f1(t) имеет особенное значение и называется интенсивностью точечного процесса (средней скоростью счета). Функции корреляции плотности внедряются, если существуют статистические связи между моментами появления точек. Например, для функций второго порядка можно записать

g2(t1, t2) = f2(t1, t2) - f1(t1)f2(t2).

Функция f2(t1, t2) характеризует совместную вероятность появления точек вблизи моментов t1 и t2 и при разнесении аргументов стремится к произведению сомножителей f1(t1)f1(t2), каждый из которых характеризует вероятность независимых событий. Следовательно, функция g2(t1, t2) при разнесении аргументов стремится к нулю, что означает ослабление корреляционных связей. Указанные системы функций можно получить из производящего функционала (ПФ), который по определению имеет вид [2]

(7),

где М{} обозначает операцию определения математического ожидания по числу n и моментам t появления точек на интервале (0, Т); u(t) - вспомогательная действительная функция.

ПФ выражается через функции fn() и gn() в форме функциональных рядов

Сравнивая выражения (8) и (9), можно прийти к аналогичным по форме, что и для моментных и корреляционных функций, соотношениям, связывающим fn() и gn():

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

ξ(t) =, (12)

где {ti} - координаты появления точек на временной оси; дельта-функция

Произведя замену exp jv(ti) = u(ti) + 1, имеем

(13)

Но выражение справа от знака равенства формулы (13) является ПФ (7). На основании изложенного можно получить соотношение, связывающее ХФ и ПФ:

θ(v, T) = L{exp [jv(t) - 1]}.

Используя эту формулу, а также выражения ХФ (4) и ПФ (9), после логарифмирования приходим к следующему соотношению:

Разложим экспоненциальные члены в ряд по степеням v(t) и, приравнивая члены с одинаковыми степенями, получим

k1(t) = g1(t);

k2(t1, t2) = g1(t1) δ(t1 - t2) - g2(t1, t2);

k3(t1, t2, t3) = g1(t1) δ(t1 - t2) δ(t1 - t3) + g2(t1, t3) δ(t1 - t2) +

+ g2(t2, t3) δ(t2 - t1) + g2(t1, t2) δ(t1 - t3) + g3(t1,t2, t3); (14),

где δ() - дельта-функция.

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

Дальнейшее толкование будет проводиться в пределах корреляционной теории и для стационарных процессов. Это значит, что, во-первых, исследуются статистики не выше второго порядка (математическое ожидание, корреляционная функция, дисперсия, спектральная плотность). Во-вторых, из-за условия стационарности указанные характеристики не зависят от текущего времени: математическое ожидание имеет постоянное значение, а корреляционная функция зависит от разности аргументов τ = t2 - t1. Для этого случая корреляционные функции первого (математическое ожидание) и второго порядков случайной интенсивности на основании (14) записываются в виде

ki = gi = fi = λ = const; (15)

k2(τ) = λδ(τ) + g2(τ), (16)

где λ - принятое в теории фрактальных процессов обозначение интенсивности точечного процесса.

Как уже ранее отмечалось, функция корреляции плотности отражает наличие статистических связей между моментами появления точек. Учет этой функции приводит к разным моделям точечных процессов, в том числе и к тем, которые описывают поведение сетевого трафика. Отметим, что для пуассоновского точечного процесса из-за статистической независимо- сти моментов появления точек g2(τ) = 0 и статистики случайной интенсивности принимают вид

k1 = λ, k2(τ) = λδ(τ).

Используя (11), с учетом f2(t1, t2) = f(t2|t1) f1(t1) представим функцию g2(τ) в виде

g2(τ) = f2(t1, t2) - f12 = λ [f (t2|t1) - λ] = λ[f (τ) - λ],

так как для стационарных процессов f(t2|t1) = f(t2 - t1) = f(τ).

Условная функция плотности f(τ) характеризует вероятность появления точки в окрестности момента времени t2 при условии существования точки в момент t1, t2 > t1. Ее можно определить из интегрального уравнения восстановления, которое для стационарных точечных процессов имеет вид[3]

(17)

Здесь ψ(τ) - плотность распределения вероятностей временных интервалов между точками. Таким образом, задаваясь этой функцией, можно из уравнения (17) определить условную функцию плотности f(τ), а на основании ее - функцию g2(τ) и соответственно корреляционную функцию случайной интенсивности k2(τ) (16).

По этой функции находят остальные статистики сетевого трафика: спектральную плотность случайной интенсивности, а также корреляционную функцию и дисперсию числа отсчетов. Если для функции ψ(τ) существует преобразование Лапласа - ψ(s), то, применяя к обеим частям уравнения (17) это преобразование, после упрощений получаем

. (18)

Осуществляя обратное преобразование, определяют по F(s) условную плотность f(τ). Можно предложить более общий путь определения этой функции. Учитывая |ψ(s)| < 1, соотношение (18) представим как сумму бесконечно убывающей геометрической прогрессии с первым членом и знаменателем, равными ψ(s):  .

Осуществляя обратное преобразование Лапласа, получаем , где ψk(τ) определяется через интеграл свертки

Применяя к корреляционной функции (16) Фурье-преобразование (формула Хинчина - Винера), получаем спектральную плотность центрированной составляющей случайной интенсивности

(19)

Приведем еще одно определяемое с помощью уравнения восстановления и формулы Хинчина - Винера выражение спектральной плотности этой составляющей случайной интенсивности [4]

(20)

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

(21)

При анализе рассматриваемых в этом и следующем разделах моделей используются статистики числа отсчетов (приращений) точечного процесса на интервалах заданной длительности Т (счетные статистики). Обозначим число выпавших на интервале (tn, tn - T) точек через Хn. Сместим этот интервал на kT (k ≥ 1) и обозначим число выпавших на интервале (tn + k, tn + k - T) точек через Хn + k. Корреляционная функция числа отсчетов в разнесенных на время, равное kT, указанных интервалах определяется соотношением

C(k, T) = M{Xn Xn + k} - (λT)2. (22)

Дисперсия числа отсчетов равна при

= 0 D(T) = C(0, T). (23)

Процедуры определения статистик (22) и (23) опираются на интегральные соотношения, которые связывают искомые функции и процессы с известными статистическими характеристиками. Предварительно получим выражение статистик для непрерывного времени. Пусть ξ(t) - стационарный случайный процесс с известными математическим ожиданием m1 и корреляционной функцией k2(u).

Математическое ожидание и корреляционная функция от этого процесса на заданном интервале (t, t - T) соответственно равны[5]:

Соотношение, связывающее на основании формулы Хинчина - Винера корреляционную функцию и спектральную плотность, имеет вид

После подстановки полученного выражения в k2x(ϑ) и интегрирования имеем

Как следует из полученного выражения, интегралу от процесса ξ(t) с известной корреляционной функцией k2(τ) соответствует процесс с корреляционной функцией k2x(ϑ) и спектральной плотностью[6]

 (24)

Подставив в соотношение для k2x(ϑ) выражение (19) , получим

После замены ϑ - t = τ (ϑ > u) интеграл в квадратных скобках оказывается табличным и равным Т - τ при τ < Т и нулю при τ > Т. Присоединяя к полученному результату значение этого интеграла для области u > ϑ, получаем окончательное выражение для корреляционной функции и дисперсии:

сетевой трафик случайный

При определении статистических характеристик числа отсчетов на интервалах заданной длительности Т исходное интегральное соотношение для дискретного времени t1, t2, ..., tn, ... имеет вид , где ξ(t) - случайная интенсивность или случайный импульсный поток (12) с известными математическим ожиданием, корреляционной функцией k2(τ) и спектральной плотностью S(ω). Интервал между отдельными отсчетами ϑ оказывается кратным длительности Т и равным kT, где k - параметр смещения.

На основании изложенного, учитывая обозначения для счетных статистик, имеем:

Заключение

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

В данной работе был проанализирован способ моделирования сетевого трафика случайным точечным процессом, рассчитаны различные формулы, и вся информация была систематизирована.

Список литературы

Статистические проблемы выделения потока сигналов из шума / И.А. Большаков. - М. : Сов. радио, 1969.

Коммутация и маршрутизация IP/IPX трафика / М.В. Кульгин, АйТи. - М.: Финансы и статистика, 2004. - 512 с.: ил.

Вычислительные системы, сети и телекоммуникации / А.П. Пятибратов, Л.П. Гудыно, А.А. Кириченко - М. : КНОРУС, 2013. - 376 с. : ил.

Современные компьютерные сети. 2-е изд. / В. Столлингс. - СПб.: Питер, 2003. - 783 с.: ил. (Серия «классика Computer Science»).

Аппаратные средства локальных сетей. Энциклопедия / М. Гук, - СПб.: Питер, 2004. - 573 с.: ил.

Компьютерные сети. Принципы, технологии, протоколы / В.Г. Олифер, Н. А. Олифер. - СПб.: Питер, 2001. - 672 с.: ил.