Обоснование модели простейшего потока, образуемого кадрами сети Ethernet

Федеральное агентство железнодорожного транспорта

«Уральский государственный университет путей сообщения»

 

Кафедра «Информационных технологий

и защита информации»

 

 

 

 

Курсовая работа

По дисциплине: «Средства  и системы технического обеспечения  обработки, хранения и передачи информации»

на тему «Обоснование модели простейшего потока, образуемого кадрами сети Ethernet»

 

 

Выполнил: ст. гр. ИТЗ-310

Пауесов Р.А.

 

Проверил:

Симонович В. Г.

 

 

 

 

Екатеринбург 2011

Оглавление

Введение 3

1.Теоритический  раздел 5

1.1 Определение  простейшего потока. Характеристики  простейшего потока. 5

1.2 Свойство  стационарности. 7

1.3 Свойство  отсутствия последствия. 8

1.4 Проверка  допущений о распределениях. 10

1.4.1 Критерий  согласия WE для проверки достоверности гипотезы об экспоненциальном распределении исследуемой статистики. 11

1.4.2 Использование  критерия согласия χ² для проверки достоверности гипотезы о распределении исследуемой статистики. 12

1.4.3 Схематическое  представление выполнения курсового  проекта. 15

2.Практическое  исследование 16

2.1.1.Проверка  свойства отсутствия последствия 17

2.1.2.Проверка  достоверности гипотезы об экспоненциальном  распределении исследуемой статистики  с помощью критерия согласия  WE 19

2.1.3Проверка  достоверности гипотезы об экспоненциальном  распределении исследуемой статистики  с помощью критерия согласия  χ² 20

2.1.4 Проверка  свойства стационарности 24

Вывод 25

Список использованных источников 26

 

 

Введение

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

       Поскольку  в ЛВС типа Ethernet используется множественный доступ с обнаружением коллизий CSMA/CD, то моменты появления кадров в передающей среде носят случайный характер. Кроме того, на длительность интервала между появлением кадров существенное влияние оказывает число пользователей и интенсивность их работы.  Данные обстоятельства существенно усложняют модель, описывающую поведение входного потока заявок, образуемого кадрами, что непосредственно влияет на выбор математических моделей, используемых для анализа характеристик сети.

       С точки зрения информационной безопасности, для предприятий и организаций, использующих ЛВС типа Ethernet, при передаче информации подлежащей защите, актуально использовать такие оценки показателей обслуживания, как время доступа в сеть, время передачи сообщения по сети и др. Такой анализ позволит:

       - адекватно  оценить объём передаваемых сведений, содержащих информацию, подлежащую  защите;

      - верно выбрать средства сетевой защиты;

      - рационально  оценить объём средств, необходимых  для достижения заданного уровня  защищённости.

      Представленное  методическое пособие является  руководством  для проведения  теоретического исследования распределения  случайной величины – момента  времени появления кадров в  ЛВС типа Ethernet с использованием различных приёмов статистического анализа.

      Целью работы является проверка гипотезы о возможности описания потока, образуемого моментами появления кадров в сети Ethernet моделью простейшего потока.

     Для реализации поставленной цели необходимо решить следующие задачи:

     1.Выбрать согласно  варианту – (порядковый номер  в журнале) исходные данные  для исследования.

     2.Проанализировать  исходные данные на предмет  стационарности потока случайных  событий, используя критерий Краскала-Уоллиса.

     3.Исследовать  поток данных на отсутствие  последствия с помощью критерия  серий и тренда.

     4.На основании  определения о простейшем потоке  данных выдвинуть гипотезу об  экспоненциальном распределении  исследуемой статистики.

     5.Используя  критерий согласия χ² , а также критерий согласия WE, проверить правдоподобность выдвинутой гипотезы.

 

1.Теоритический раздел

     1.1 Определение простейшего потока. Характеристики простейшего потока.

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

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

     - стационарность  предполагает независимость вероятностных  характеристик потока от начала  отсчёта или, более конкретно,  если вероятность попадания того или другого числа событий на любой интервал времени будет зависеть только от длины, а не от места расположения на оси 0t;

     - ординарность  – свойство потока, заключающееся  в том, что заявки в нём  появляются по одиночке, а не группами;

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

     Кроме перечисленных  характеристик сами события должны  быть однородными (однотипными)  и появляться одно за другим  в случайные моменты времени.  Если выполняются все вышеперечисленные  условия, то время t между моментами появления соседних событий, в дальнейшем называемое «исследуемая статистика», простейшего потока распределено экспоненциально с параметром λ, то есть интенсивность потока равна математическому ожиданию числа событий, приходящихся на единицу времени:

 

 

λ > 0

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

     Если, используя  традиционные приёмы статистического анализа данных, удастся обосновать возможность применения вышеописанной модели для описания входного потока заявок и потока обслуживания, то исследуемую информационную систему можно представить как систему массового обслуживания (СМО) типа M/M/υ, где М – определяет Марковские свойства потока событий[3]. Данное сокращение означает, что время между появлением заявок на входе системы и время обслуживания заявки распределено показательно, а υ определяет число обслуживающих приборов. Тогда расчёт основных характеристик обслуживания не составит труда, поскольку для такого случая получены чёткие функциональные зависимости, за табулированные для различных значений интенсивностей.

     Для обоснования  применения описанной модели  необходимо проверить выполнение  вышеописанных условий и по  совокупности результатов сделать  вывод о возможности применения  данной модели. Если хотя бы  одно из условий не будет  выполнено, то поток не является  простейшим и использование данной  модели не оправдано.

 

     1.2 Свойство стационарности.

     Для проверки стационарности потока случайных событий воспользуемся критерием Краскала – Уоллиса [4]. Критерий Краскала – Уоллиса используется, когда имеется несколько выборок k с общим числом наблюдений N и требуется определить, являются ли все выборки одинаково распределёнными, т. е. имеют один и тот же тип распределения. Если данная гипотеза подтвердится, то можно с определённым уровнем значимости принять гипотезу о стационарности исследуемого потока.

      Процедура  расчёта критерия состоит в  следующем:

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

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

     3. Рассчитываем значение критерия по следующей формуле:

 

где N – общее число наблюдений,

N₁… N_k – число наблюдений выборки 1… N,

R_k – суммарный ранг k-ой выборки.

     4. Необходимо  проверить значимость полученного  значения критерия Н. Для этого  необходимо задаться уровнем  значимости (обычно α = 0,05) и сравнить  полученное значение с верхней  5%-ой областью распределения χ² с k – 1 степенями свободы. Если полученное значение меньше, то гипотеза о стационарности исследуемого потока верна с уровнем значимости 0,05.

 

     1.3 Свойство отсутствия последствия.

     По определению, отсутствие последствия – это независимость наблюдений, образующих поток. Для обоснования данного факта воспользуемся непраметрическим критерием серий [5], основанным только на свойствах самих наблюдений.

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

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

r_{n/2; 1 – α/2} < r < r_{n/2; α/2}

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

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

     Рассмотрим  последовательность N наблюденных значений случайной величины x(k). Обозначим эти значения символом x_i , где i = 1, 2, 3,… N. Подсчитаем теперь число случаев, когда x_i > x_j при i < j. Каждое такое неравенство называется инверсией. Общее число инверсий обозначим символом  А.

     Дадим следующее общее определение числу А. По ряду значений х₁, х₂,… х_N определим величину

h_ij = 1, при x_i > x_j

h_ij = 0, при других x_i

Тогда

 

где

 

Сравним полученное значение А с табличными значениями.

A_N; 1 – α/2 < A < A_N; α/2

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

 

     1.4 Проверка допущений о распределениях.

     Статистическая  проверка допущения о распределении  позволяет объективно оценить,  обеспечивает ли принятая модель  достаточно точное описание наблюдаемых  данных. Обычно проверка включает  в себя следующие основные  этапы:

     - На основании  полученных данных вычисляется  некоторое число, называемое критерием  согласия.

     - Определяется  вероятность получения вычисленного  критерия при условии , что модель выбрана правильно. Часто это выполняется путём обращения к таблице распределения критерия.

     - Если вероятность  получить вычисленное значение  критерия мала, мы заключаем, что  принятая статистическая модель не даёт правильного описания данных. Малой считается вероятность, равная 0,1; 0,5, или меньше. Если вероятность получения вычисленного критерия не мала, то данные не дают оснований считать, что принятая модель не подходит.

     Следует чётко  представлять, что эта методика  позволяет отвергнуть модель  как неправильную, но не позволяет  доказать, что модель верна. Исход  статистического испытания зависит  от количества имеющихся данных: чем больше данных, тем больше  шансов отвергнуть неправильную  модель. Если данных мало, то часто  бывает невозможно установить  неадекватность даже такой модели, которая существенно отличается  от принятой.

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

 

     1.4.1 Критерий согласия WE для проверки достоверности гипотезы об экспоненциальном распределении исследуемой статистики.

     Критерий согласия WE ориентирован на проверку достоверности гипотезы об экспоненциальном распределении исследуемой статистики [6].

     Вычисление  критерия производится по следующей  формуле:

 

     Вычисленный  таким образом критерий сравнивается  с 95%-процентилем, представляющим собой двусторонний доверительный интервал. Если расчётное значение критерия не попадает в соответствующий интервал, то вероятность того, что наблюдаемое значение взято из экспоненциально распределённой совокупности, меньше 0,05. Объём выборки, для которой производится вычисление критерия WE, невелик – от 7 до 35, что, как показывает практика, вполне достаточно.

 

     1.4.2 Использование критерия согласия χ² для проверки достоверности гипотезы о распределении исследуемой статистики.

     Наиболее гибкой методикой оценки допущений о распределении является проверка с помощью критерия χ² [5,7]. Для применения этого критерия полученные данные группируются по интервалам частот и сравниваются с ожидаемым числом наблюдений для принятого распределения. На основе этого сравнения вычисляется критерий, который приближённо следует распределению χ² только в том случае, если модель выбрана правильно. Если модель выбрана неправильно, то значение критерия превысит значение случайной величины, распределённой по закону χ². Основным преимуществом этого критерия является его гибкость. Его можно легко использовать для проверки допущения о любом распределении.

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

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

     В общем  случае проверка с помощью  χ² производится следующим образом:

    1. Нахождение оценок для каждого из неизвестных параметров принятого распределения.

    2. Деление полученных  данных на k интервалов и определение вероятности попадания в каждый интервал случайной величины, имеющей принятое распределение. Существует 2 метода выполнения этой работы. Первый из них применяется в том случае, когда данные первоначально были распределены по интервалам или могут быть разбиты по этим интервалам естественным образом. Это будет иметь место в случае дискретного распределения. Второй метод применяется, когда данные первоначально не разбиваются на интервалы.

     Метод 1. Число интервалов k, на которые разбиваются полученные данные, подчиняются требованию, чтобы для принятой модели ожидаемое число наблюдений в каждом интервале было не меньше пяти [1]. Пусть CL_i и CU_i обозначают соответственно нижнюю и верхнюю границы i-го интервала. Затем для нахождения оценки,

P(CL_i ≤ x < CU_i),

i = 1, 2,… k, т. Е. вероятности попадания случайного наблюдения в каждый из интервалов, используется принятое значение распределения.

     Метод 2. В данном случае выбор k более произволен. Когда число наблюдений N велико (например, более 200) [1], одно из возможных правил состоит в выборе в качестве k целого числа, ближайшего к:

k = 4[0,75(N – 1)²]^0,2

     При средних значениях N правило выбора k состоит в выборе как можно большего значения k при условии, что оно не должно превышать N/5.

     Границы интервалов x₁, x₂,…x_k определяются с помощью теоретического распределения (с использованием оценок параметров) так, что

P(x ≤ x₁) = 1/k

P(x ≤ x₂) = 2/k,… P(x ≤ x_{k -1}) = (k – 1)/k

     Нижняя граница первого интервала и верхняя граница последнего интеграла являются соответственно наименьшим и наибольшим значениями, которые может принимать случайная величина, В этом случае границы интервалов установили таким образом, что для каждого интервала вероятность попадания случайной величины в данный интервал оценивается как 1/k.

     3. Умножение  каждой вероятности попадания  наблюдений в интервал на объём  выборки N. Получили математическое ожидание E_i числа наблюдений в каждом интервале для принятой теоретической модели. Применяя первый метод, E_i находят умножением вероятности на N. Для второго метода:

E_i = N/k,     i = 1, 2, … k.

     4. Если данные  не были предварительно табулированы, подсчитаем число наблюдений  в каждом интервале. Обозначим  это число как m_i, где i = 1, 2,… k. В противном случае находим m_i непосредственно подсчётом.

     5. Вычисляем  критерий χ²

 

      При использовании  второго метода это выражение  немного проще и имеет вид:

 

     6. Сравнить  вычисленное значение χ² с табличным значением, выбирая число степеней свободы r.

R = k – r – 1,

где k – число рассматриваемых интервалов;

r – число параметров распределения.

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

P[χ² > χ²_кр(α; r)] = α[1]

     Таким образом, правосторонняя критическая область определяется неравенством

χ² > χ²_кр(α; r),

а область принятия нулевой  гипотезы – неравенством

χ² < χ²_кр(α; r)

     По таблице  распределения χ² найдём критическую точку χ²_кр(α; r).

     Если χ²_набл < χ²_кр – нет основания отвергать гипотезу, т. е. гипотеза верна, но если наоборот, т. е. χ²_набл < χ²_кр, гипотезу отвергаем. Большие значения χ² означают, что анализируемые данные противоречат принятой модели. В этом случае полезно сравнить фактические частоты с ожидаемыми, чтобы увидеть, какие интервалы оказывают наибольшее влияние на величину χ². Это сравнение показывает характер отклонений от принятой модели.

 

     1.4.3 Схематическое представление выполнения курсового проекта.

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

Вывод о правдоподобности выдвинутой гипотезы

Проверка отсутствия последствия

Критерий

тренда

Критерий

серий

&

χ²

Критерий

согласия WE

Проверка стационарности потока

Проверка стационарности потока

Критерий

Краскала-Уоллиса

Проверка гипотезы о возможности  описания потоков кадров сети Ethernet моделью простейшего потока

  

2.Практическое исследование

Выборка

04.04.2000	11:15:13	1541	04.04.2000	11:17:52	2388
04.04.2000	11:15:19	1722	04.04.2000	11:17:58	2199
04.04.2000	11:15:25	1412	04.04.2000	11:18:01	776
04.04.2000	11:15:28	905	04.04.2000	11:18:04	3040
04.04.2000	11:15:34	1390	04.04.2000	11:18:07	3025
04.04.2000	11:15:41	898	04.04.2000	11:18:10	128
04.04.2000	11:15:47	971	04.04.2000	11:18:13	2064
04.04.2000	11:15:50	1371	04.04.2000	11:18:22	1975
04.04.2000	11:15:56	2338	04.04.2000	11:18:26	1796
04.04.2000	11:15:59	64	04.04.2000	11:18:29	2574
04.04.2000	11:16:02	2106	04.04.2000	11:18:36	3557
04.04.2000	11:16:08	1033	04.04.2000	11:18:39	2073
04.04.2000	11:16:11	971	04.04.2000	11:18:46	1547
04.04.2000	11:16:17	1366	04.04.2000	11:18:53	2008
04.04.2000	11:16:23	5058	04.04.2000	11:18:57	1759
04.04.2000	11:16:29	1219	04.04.2000	11:19:04	5247
04.04.2000	11:16:33	1146	04.04.2000	11:19:07	2669
04.04.2000	11:16:39	1321	04.04.2000	11:19:12	1460
04.04.2000	11:16:45	1869	04.04.2000	11:19:17	4593
04.04.2000	11:16:48	3633	04.04.2000	11:19:24	1403
04.04.2000	11:16:54	2450	04.04.2000	11:19:27	5441
04.04.2000	11:17:03	1747	04.04.2000	11:19:33	2144
04.04.2000	11:17:06	2585	04.04.2000	11:19:39	4809
04.04.2000	11:17:09	3239	04.04.2000	11:19:42	1902
04.04.2000	11:17:15	1946	04.04.2000	11:19:48	2034
04.04.2000	11:17:20	2514	04.04.2000	11:19:54	4123
04.04.2000	11:17:26	3539	04.04.2000	11:20:20	1995
04.04.2000	11:17:32	2668	04.04.2000	11:20:03	2553
04.04.2000	11:17:38	4947	04.04.2000	11:20:09	2269
04.04.2000	11:17:41	1644	04.04.2000	11:20:16	1670
04.04.2000	11:17:44	437	04.04.2000	11:20:19	2028
04.04.2000	11:17:47	2408	04.04.2000	11:20:26	1678

 

 

2.1.1.Проверка свойства отсутствия последствия

1.1Расчёт критерия  серий при общем числе наблюденных  значений N = 64.

       Просматривая  данные выборки, определим среднее  значение наблюдений. Среднее значение  равно 2209,141. Будем считать, что наблюденные значения более 2209,141 имеют знак (+), а менее 2209,141 – знак (-), результаты приведены в таблице 1.

Таблица 1

Число		Серия	Число		Серия	Число		Серия	Число		Серия
1541	-		1146	-		2388	+	12	2669	+	18
1722	-		1321	-		2199	-		1460	-	19
1412	-		1869	-	5	776	-	13	4593	+	20
905	-		3633	+		3040	+		1403	-	21
1390	-		2450	+	6	3025	+	14	5441	+	22
898	-		1747	-	7	128	-		2144	-	23
971	-		2585	+		2064	-		4809	+	24
1371	-	1	3239	+	8	1975	-		1902	-
2338	+	2	1946	-	9	1796	-	15	2034	-	25
64	-		2514	+		2574	+		4123	+	26
2106	-		3539	+		3557	+	16	1995	-	27
1033	-		2668	+		2073	-		2553	+
971	-		4947	+	10	1547	-		2269	+	28
1366	-	3	1644	-		2008	-		1670	-	29
5058	+	4	437	-	11	1759	-	17	2028	-
1219	-		2408	+		5247	+		1678	-

 

Из таблицы видно, что  я получил 29 серии, представляющие последовательность 64 наблюденного значения. Выполним проверку при уровне значимости α = 0,05. Выдвинем гипотезу о независимости значений:

r_{32; 0,975} < r ≤ r_{32; 0,025}

 

22 < r ≤ 39

 

Результаты расчёта критерия серий показали, что выдвинутая мною гипотеза об отсутствии последствия  входящего потока, образуемого кадрами  сети Ethernet, принимается с уровнем значимости 0,05, так как найденное значение r = 29 входит в интервал между 22 и 39.

 

 

 

1.2Расчёт критерия  тренда при общем числе анализируемых  значений N =64.

        Проверим последовательность наблюденных значений на наличие тренда при уровне значимости α = 0,05. Полученные данные представлены в таблице 2.

 

Таблица 2

Число		Число		Число		Число
1541	18	1146	3	2388	20	2669	11
1722	22	1321	3	2199	18	1460	1
1412	16	1869	12	776	1	4593	11
905	5	3633	38	3040	22	1403	0
1390	13	2450	26	3025	21	5441	11
898	4	1747	9	128	0	2144	6
971	4	2585	28	2064	13	4809	9
1371	10	3239	32	1975	8	1902	2
2338	33	1946	12	1796	6	2034	4
64	0	2514	24	2574	15	4123	6
2106	28	3539	30	3557	16	1995	2
1033	4	2668	26	2073	11	2553	4
971	3	4947	33	1547	2	2269	3
1366	6	1644	6	2008	7	1670	0
5058	47	437	1	1759	4	2028	1
1219	4	2408	21	5247	17	1678	-