Введение 3

Глава 1. Алгоритм определения участков стационарности. 7

1.1. История развития математических моделей потоков. 7

1.2. Модели случайных потоков. 8

1.3. Описание модели асинхронного дважды стохастического потока с конечным числом состояний 11

1.4. Алгоритм определения участков стационарности. 13

1.5. Результаты и выводы к первой главе 17

Глава 2. Исследование качества работы алгоритма определения участков стационарности потока и применение его к реальным данным. 18

2.1. Имитационная модель 19

2.2. Статистические оценки 21

2.3. Проверка работы алгоритма на имитационной модели. 22

2.4. Определение характеристик трафика реальной сети 25

2.5. Результаты и выводы ко второй главе 29

Заключение 31

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

Приложение 1. Значения квадратичных невязок для некоторых экспериментов. 34

Приложение 2. Расчет критерия хи-квадрат для различных моделей потоков 40

Приложение 3. Описание основных классов программной реализации алгоритма. 42

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

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

Компьютерные сети можно представить в виде сложной СМО. В ней можно рассматривать в качестве требований (заявок) пакеты данных, а в качестве обрабатывающих устройств – серверы, коммутаторы и маршрутизаторы. Если подходить к исследованию компьютерной сети с этой стороны, то можно представить ее трафик в виде потока случайных событий (заявок), считая событием поступление пакета на обрабатывающее устройство.

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

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

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

В 90-е гг. американскими учеными Неутсом и Лукантони была введена модель MAP потока с переменной и стохастически изменяемой интенсивностью [1]. Это дало толчок к развитию математического аппарата для описания и анализа случайных потоков в сетях ISDN.

На текущий момент одной из актуальных моделей трафика является дважды стохастический поток событий, по-видимому, впервые введенный Коксом в [2]. В 1964 г. Данная тема получила развитие в работе Кингмена [3]. Для дважды стохастического потока имеют место 2 случайных процесса: во-первых, случайны моменты наступления событий в потоке; во-вторых, интенсивность потока изменяется случайным образом. Сама интенсивность может изменяться непрерывно или дискретно. Особый интерес представляют потоки, интенсивность которых является кусочно-постоянным процессом с конечным числом состояний. Точность таких моделей вполне достаточна для математического анализа потоков. Более сложные разновидности дважды стохастических потоков трудноприменимы на практике, а точность таких моделей намного превышает необходимую в данный момент.

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

Актуальность. Модели различных разновидностей дважды стохастического потока, а также СМО с такими входящими потоками достаточно хорошо исследованы. В этой области существует более 200 научных работ в ведущих мировых изданиях, наработан большой объем теоретического материала. Но до недавнего времени вопрос о соответствии реального трафика той или иной модели оставался за рамками исследований. И лишь недавно стали появляться публикации на эту тему [4,5,6,7,8]. Поэтому представляется важным проводить дальнейшие исследования в этом направлении. В качестве возможных приложений результатов исследования приведем: мониторинг работы сети, оптимизация работы сети, системы обнаружения нарушителей и др.

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

Целью работы является:

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

Задачи работы:

• Построение математической модели дважды стохастического потока событий с конечным числом состояний;

• Создание алгоритма определения участков стационарности потока и интенсивности на них;

• Построение имитационной модели потока, ее реализация и проверка на ней алгоритма;

• Применение модели дважды стохастического потока с конечным числом состояний к статистике сетевого трафика, оценка параметров потока в соответствие с этой моделью;

• Вычисление для выборок полученных оценок статистических характеристик.

[1] Lucantoni D.M., Neuts M.F.

Some steady-state distributions for the MAP/SM/f queue // Com. In Stat. Stoch. Models – 1994. – V. 10. – P.575-598

[2] Cox, D.R.

Some Statistical Methods Connected with Series of Events // J. R. Statist. Soc. Ser. B XVII, 1955, pp. 129-164

[3] Kingman J.F.C.

On doubly stochastic Poisson process// Proceedings of Cambridge Phylosophical Society. - 1964. - V.60. - №4. - P. 923-930.

[4] Беккерман Е.Н., Катаева С.С.

Алгоритм определения участков стационарности МС-потока событий // Мас. обсл.: Матер. межд. конф. «Совр. мат. мет. иссл. инф-выч. сетей». – Минск: БГУ. – Вып 16. – 2001. С. 42-47

[5] Беккерман Е.Н., Катаев С.Г., Катаева С.С. Кузнецов Д.Ю.

Аппроксимация МС-потоком реального потока событий // Вестн. ТГУ. – 2005. - №14. – Прил. – С. 248-253.

[6] Ниссенбаум О.В., Пахомов И.Б.

Аппроксимация сетевого трафика моделью альтернирующего потока событий // Прикладная дискретная математика. Приложение №1. – 2009. – С. 78-79.

[7] Головко Н.И., Каретник В.О., Танин В.Е., Сафонюк И.И.

Исследование моделей систем массового обслуживания в информационных сетях // Сибирский журнал индустриальной математики. — 2008. — T.XI -№ 2(34). -С. 50-58.

[8] Никольский Н.Н.

Адаптивный алгоритм контроля доступа вызовов в сетях пакетной телефонии для кодеков с переменной интенсивностью передачи информации // Автореферат диссертации на соискание ученой степени кандидата технических наук, Москва - 2007 - 168 c.

[9] Erlang, A.-K.

New Alternating-current Compensation Apparatus for Telephonic Measurements // The Journal of the Institution of Electrical Engineers 51, 1913, pp. 261-267

[10] Горцев A.M., Шмырин И.С.

Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в измерениях моментов времени // Автоматика и телемеханика. — 1999. — №1. — С. 52-66.

[11] Васильева Л.А.

Оценивание длительности мертвого времени и параметров асинхронного дважды стохастического потока событий методом моментов // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук, Томск - 2005

[12] Назаров А.А.

Управляемые системы массового обслуживания и их оптимизация. – Томск: Изд-во ТГУ. – 1984. – 234с.

[13] Горцев A.M., Шмырин И.С.

Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в измерениях моментов времени// Автоматика и телемеханика. — 1999. — №1. — С. 52-66.

[14] Нежельская Л. А.

Алгоритм оценивания состояния синхронного МС-потока. // Тр. 11 Белорус. шк.-сем. по мас. обсл. – Минск. – 1995. – стр. 93 – 94.

[15] Васильева Л. А., Горцев А. М.

Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости. // АиТ. – 2002. – № 3. – стр. 179 – 184.

Примечаний нет.