Стохастичні моделі та методи аналізу самоподібного мережевого трафіка

Размещено на http://www.allbest.ru/

Харківський національний університет радіоелектроніки

УДК 004.7:519.2

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Стохастичні моделі та методи аналізу самоподібного мережевого трафіка

Радівілова Тамара Анатоліївна

Харків - 2008

Дисертацією є рукопис.

Робота виконана в Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник кандидат технічних наук, доцент Кіріченко Людмила Олегівна, Харківський національний університет радіоелектроніки, доцент кафедри прикладної математики.

Офіційні опоненти:

доктор технічних наук, професор Кривуля Геннадій Федорович, Харківський національний університет радіоелектроніки, завідувач кафедри автоматизації проектування обчислювальної техніки;

доктор технічних наук, професор Соколовський Ярослав Іванович, Національний лісотехнічний університет України, завідувач кафедри обчислювальної техніки і моделювання технологічних процесів.

Захист відбудеться "09" грудня 2008 р. о 13-00 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки, за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитися в бібліотеці Харківського національного університету радіоелектроніки, за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий " 05 " листопада 2008 р.

Вчений секретар спеціалізованої вченої ради Безкоровайний В.В.

Анотації

Радівілова Т.А. Стохастичні моделі та методи аналізу самоподібного мережевого трафіка. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Харківський національний університет радіоелектроніки, Харків, 2008.

Дисертаційна робота присвячена математичному моделюванню та методам дослідження самоподібного мережевого трафіка.

Запропоновано метод знаходження незміщеної оцінки показника Херста з використанням методів нормованого розмаху і зміни дисперсії агрегрегованого ряду. Проведено імітаційне моделювання завантаження каналу й досліджено виникнення черг в буфері для реалізацій мережевого трафіка. У процесі досліджень запропоновано математичну модель самоподібного трафіка, що розглядається як самоподібний випадковий процес, який є функціональним перетворенням фрактального гаусівського шуму. Розроблено метод оцінювання залежності ступеня завантаженості каналу мережі від параметрів трафіка, що проходить, що дозволяє при заданих розмірах буферної пам'яті і пропускної здатності каналу визначати гранично допустиме навантаження даної мережі. Результати імітаційного моделювання дозволили розробити методи прогнозування і запобігання перевантаженням у системах передачі даних.

Ключові слова: самоподібний стохастичний процес, математична модель самоподібного мережевого трафіка, показник Херста, імітаційне моделювання, перевантаження мережі.

Радивилова Т.А. Стохастические модели и методы анализа самоподобного сетевого трафика. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский национальный университет радиоэлектроники, Харьков, 2008.

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

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

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

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

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

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

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

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

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

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

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

Результаты исследований используются в Государственном предприятии "Завод им. В.О. Малышева" при реконфигурации компьютерной сети; в ООО "Харьковские телекоммуникации" и в ООО "Учетно-управляющие системы" при разработке биллинговых систем; в учебном процессе в Харьковском национальном университете радиоэлектроники, что подтверждено соответствующими актами.

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

Radivilova Т.А. Stochastic models and methods for analysis of self-similar network traffic. - Manuscript.

The thesis for a candidate degree in technical science. Specialization 01.05.02 - mathematical modelling and computing methods. - Kharkiv National University of Radioelectronics, Kharkiv, 2008.

The dissertation work is devoted to mathematical simulation and research of self-similar network traffic.

The method of finding the unbiased estimator for the Hurst exponent is offered using the technique of rescaled range and change of variance for an aggregated series. Load of the channel is simulated and the origin of queues in the buffer of a network traffic realization is investigated. Mathematical model of a self-similar traffic is founded and examined. It has been described as a self-similar random process that appears to be some functional transformation of fractal Gaussian noise. The suggested method of estimation for a network channel work-load dependence of the traffic parameters allows us to determine the maximum possible loading of this network at given value of buffer memory and flow capacity of the channel. The results of this imitation design give the base to development of prognostication methods for overcoming the overload in data communication systems.

Keywords: self-similar stochastic process, self-similar network traffic, the Hurst exponent, simulation, network overload.

Загальна характеристика роботи

Актуальність теми. Активний розвиток інформаційних технологій і розширення обсягів інформаційних послуг значною мірою ґрунтується на науково-технологічних розробках у галузі телекомунікаційних мереж. Дослідження показують, що сучасні мережеві технології своїм зростанням випереджають теоретичне та аналітичне розуміння мережевих взаємодій. Важливою особливістю інформаційного трафіка є те, що він належить до самоподібних стохастичних процесів. Для самоподібного трафіка методи розрахунку характеристик комп'ютерної мережі (пропускної здатності каналів, ємності буферів та ін.), засновані на класичних моделях, не відповідають необхідним вимогам і не дозволяють адекватно оцінювати навантаження в мережі.

Існує велика кількість публікацій, присвячених аналізу фрактальних властивостей трафіка. Самоподібні властивості інформаційних потоків виявлені в локальних і глобальних мережах, зокрема, в трафіках Ethernet, ATM, додатках TCP, IP, VoIP. Значний внесок у розвиток теорії самоподібних процесів, дослідження фрактального трафіка та побудову моделей фрактального трафіка внесли B. Mandelbrot, W. E. Leland, M. S. Taqqu, W. Willinger, D. V. Wilson, Vern Paxson, M. Crovella, Б.С. Цибаков, А.Я. Городецький, В.С. Заборовський, В.В. Петров та інші вчені. У той же час ще залишаються невирішеними завдання, пов'язані з аналізом динаміки зміни характеристик мережі в умовах зростаючого обсягу мережевого трафіка. Самоподоба трафіка призвела до появи ряду моделей трафіка на основі самоподібних стохастичних процесів. Однак варто відзначити відсутність універсальної моделі, яка б могла використовуватися для опису фрактальних трафіків різного прикладного характеру, що має суттєве значення для вдосконалення швидкісних мережевих технологій.

Таким чином, актуальною і важливою проблемою є розробка адекватної моделі мережевого трафіка і методів, які б забезпечували отримання оцінок мережевих взаємодій. Задачі, які при цьому виникають, зумовили напрямок досліджень у наданій дисертаційній роботі.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до плану наково-дослідних робіт Харківського національного університету радіоелектроніки у межах договору за замовленням Міністерства освіти і науки України № Ф 25/713 від 03.09.2007 р., держ. реєстрація № 0107U010621 "Аналіз і поведінка систем з великою нелінійністю: синергетичний підхід". Авторка була одним з виконавців робіт за цим договором і досліджувала самоподібні властивості часових рядів.

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

Для досягнення цієї мети необхідно проаналізувати стан проблеми і вирішити такі основні завдання:

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

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

- побудова адекватної моделі самоподібного мережевого трафіка, яка враховувала б основні фактори, що викликають перевантаження телекомунікаційної мережі;

- визначення на основі моделі мережевого трафіка залежності ступеня завантаженості каналу мережі від параметрів трафіка, що проходить;

- розробка методів прогнозування і запобігання перевантажень у мережі;

- практична реалізація розроблених методів і моделей.

Об'єкт дослідження - самоподібні процеси в технічних та економічних системах.

Предмет дослідження - методи дослідження самоподібних часових рядів та моделі самоподібного мережевого трафіка.

Методи дослідження - для вирішення поставлених завдань у роботі використовувалися методи фрактального і статистичного аналізів даних при дослідженні властивостей самоподоби та розрахунку характеристик мережевого трафіка і його модельних аналогів; методи теорії ймовірності та випадкових процесів для побудови математичних моделей самоподібного трафіка; імітаційне моделювання для розробки методів прогнозування і запобігання перевантаженням мережі, перевірки запропонованих моделей, розробки практичних рекомендацій.

Наукова новизна отриманих результатів. У дисертації отримані такі нові наукові і практичні результати:

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

- вперше запропоновано метод прогнозування перевантаження мережі, заснований на розрахунку ступеня завантаженості комутованого каналу зв'язку при моніторингу трафіка. Доведено, що цей метод дозволяє зменшити втрати даних у мережі і збільшити ефективність використання мережевих ресурсів;

- отримав подальший розвиток метод оцінювання залежності ступеня завантаженості каналу мережі від параметрів самоподібного трафіка, який проходить. Це дозволяє при заданих параметрах буферної пам'яті та пропускної здатності комутованого каналу зв'язку визначити гранично припустиме навантаження мережі;

- отримав подальший розвиток фрактальний метод -аналізу, що дало можливість застосувати його до телекомунікаційних мереж. Метод дозволяє визначити такі характерні особливості самоподібних реалізацій: незалежність випадкових даних, наявність циклічних складових і середню довжину неперіодичного циклу, наявність довготермінової і короткотермінової залежності;

- удосконалено метод розрахунку ступеня самоподоби (показника Херста) по часовому ряду, в якому, на відміну від уже існуючих, введені поправочні коефіцієнти, які дозволяють отримати незміщену і більш точну оцінку показника Херста.

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

Розроблені моделі й методи впроваджені на Державному підприємстві "Завод ім. В.О. Малишева", ТОВ "Харківські телекомунікації", ТОВ "Обліково-керівні системи", а також у навчальний процес Харківського національного університету радіоелектроніки, що підтверджено відповідними актами.

Особистий внесок здобувача. Всі результати дисертаційної роботи отримані авторкою самостійно і опубліковані в роботах [1-16]. У роботах, опублікованих у співавторстві, авторці належать наступні результати. У статті [1] авторкою проведено чисельне дослідження оцінки показника Херста методом R/S-аналізу. У статті [2] авторкою проведено чисельний аналіз довгострокової і короткострокової залежності реалізацій трафіка шляхом R/S-аналізу. У статті [3] авторкою запропоновано математичну модель самоподібного трафіка і проведено імітаційне моделювання проходження трафіка через канал зв'язку. У статті [4] авторкою запропоновано метод прогнозування перевантаження каналу. У статті [5] авторкою проаналізовано основні причини виникнення перевантажень в мережі. У статті [6] авторкою запропоновано і промодельовано в системі OPNET методи запобігання перевантаженням мережі. У роботі [8] авторкою поставлені завдання і проведено порівняльний аналіз методів знаходження показника Херста. У роботі [9] авторкою проведено чисельний аналіз довгострокової і короткострокової залежності фінансових часових рядів. У роботі [10] авторкою проведено дослідження властивостей черг в буфері каналу зв'язку. У роботі [11] авторкою отримано функціональну залежність пропускної здатності каналу від параметрів вхідного трафіка. У роботі [12] авторкою отримано функціональну залежність розміру буфера від пропускної здатності каналу і параметрів вхідного трафіка. У роботі [13] авторкою проведено в системі OPNET моделювання функціонування мережі. У роботі [14] авторкою проведено в системі OPNET функціонування методів запобігання перевантаженням мережі.

Апробація результатів дослідження. Основні результати проведених досліджень доповідалися й обговорювалися на таких конференціях: науково-практичній конференції "Системний аналіз і управління" (Запоріжжя, 2006); 10-му ювілейному міжнародному молодіжному форумі "Радіоелектроніка і молодь в XXI столітті" (Харків, 2006); 1-й та 2-й міжнародних науково-технічних конференціях "Комп'ютерні науки та інформаційні технології" CSIT-2006, CSIT-2007 (Львів, 2006, 2007); 2-й Міжвузівській науково-технічній конференції молодих учених і студентів "Інформаційні технології в економічних та технічних системах "ІТЕТС-2007" (Кременчук, 2007); 3-й международной молодежной научно-технической конференции "Современные проблемы радиотехники и телекоммуникаций "РТ-2007" (Севастополь, 2007); 8-й и 9-й международных научно-практических конференциях "Современные информационные и электронные технологии" (Одесса, 2007, 2008); 2-й міжнародній науковій конференції "Сучасні інформаційні системи. Проблеми та тенденції розвитку" (Харків-Туапсе, 2007).

Публікації. Основні результати дослідження викладені у 16 друкованих працях, із них 7 статей у виданнях, які входять до переліків ВАК України, 5 публікацій у збірниках доповідей за матеріалами науково-технічних конференцій і 4 публікації у збірниках тез доповідей за матеріалами науково-технічних конференцій.

Структура й обсяг дисертаційної роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, додатка (9 стор.), списку використаних джерел із 111 найменувань (12 стор.), містить 14 таблиць (4 стор.), 62 рисунки (17 стор.) та має обсяг 154 сторінок.

Основний зміст роботи

У вступі стисло розглянуто стан досліджень і проблеми, які виникають через властивості самоподоби у комп'ютерних та телекомунікаційних мережах. Також обґрунтовано актуальність теми дисертації, визначено її відповідність науковим темам і програмам, мету і завдання досліджень, наукову новизну отриманих результатів та їх практичне значення, охарактеризовано особистий внесок здобувача, наведено список публікацій за темою дисертації.

У першому розділі дисертації проаналізовано публікації, присвячені дослідженню фрактальних властивостей трафіка в локальних і глобальних мережах, зокрема, в трафіках Ethernet, ATM, додатках TCP, IP, VoIP. Ці дослідження переконливо доводять, що мережевий трафік належить до самоподібних стохастичних процесів.

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

.

Ряд називається агрегованим.

Стохастичний процес з дискретним часом називається самоподібним у вузькому розумінні з параметром , якщо справджується вираз

(у розумінні рівності розподілів). Стохастичний процес із дискретним часом називається самоподібним у широкому розумінні з параметром , якщо кореляційна функція агрегованого процесу є , тобто, стохастичний процес не змінює свій коефіцієнт кореляції після усереднення за блоками довжини . Самоподібні процеси мають довгострокову залежність, тобто їх кореляційна функція убуває гіперболічно: .

Однією з найважливіших властивостей мережевого трафіка як випадкового процесу є наявність важких хвостів його одновимірних функцій розподілу. Випадкова величина має розподіл з важким хвостом, якщо , тобто, хвіст розподілу спадає за степеневим законом. Параметр визначає ступінь важкості хвоста. Якщо , величина має нескінченну дисперсію, а якщо - її математичне сподівання теж нескінченне. На практиці, такими, що найбільш активно використовуються, є розподіли з важкими хвостами Парето, Коші, Леві та логарифмічно нормальний розподіл.

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

У другому розділі дисертації здійснено порівняльний аналіз оцінювання параметра Херста методами нормованого розмаху та зміни дисперсії агрегованого ряду, які найчастіше застосовуються на практиці. При визначенні параметра Херста часового ряду методом нормованого розмаху використовується таке співвідношення: , де - деяка стала величина, - розмах кумулятивного ряду

,

, - середнє квадратичне відхилення початкового ряду . Метод зміни дисперсії ґрунтується на тому, що для агрегованих часових серій самоподібного процесу дисперсія за великих значень підпорядковується співвідношенню: , .

При виконанні чисельного експерименту моделювався самоподібний випадковий процес із заданим показником . Значення для модельного ряду змінювалися від 0,5 до 0,95, оскільки параметр Херста в реальних трафіках знаходиться у цьому діапазоні. Для отриманого часового ряду розраховувалась оцінка методами -аналізу і методом зміни дисперсії .

Результати досліджень показали, що, починаючи зі значень , обидва методи дають занижені значення, причому зі збільшенням ця різниця зростає. Вибудовувалася типова залежність середніх оцінок і від значень показника Херста. Суцільна пряма на графіку відповідає істинним значенням . Виходячи з отриманих результатів можна зробити висновок, що оцінки показника Херста мають розподіл, середнє значення якого значно зміщене відносно оцінюваного параметра.

Для кожного із методів були розраховані відповідні поправкові коефіцієнти. Знаючи ці коефіцієнти, можна здійснити перетворення, в результаті якого оцінки становляться незміщеними. Перетворення оцінок параметра виглядає як , де - оцінка, отримана за допомогою одного з методів, - параметри апроксимуючої прямої . Розрахунки значень коефіцієнтів для кожного з методів, отримані з точністю до сотих, складають: для методу , ; для методу дисперсій , .

Чисельний аналіз кореляційної залежності між оцінками параметра Херста, отриманими двома методами, показав, що вони мають слабку лінійну залежність. Для усіх розглянутих випадків коефіцієнти кореляції виявилися значимими і такими, що лежать у діапазоні , тому незміщеною і більш ефективною оцінкою показника Херста є середнє арифметичне двох методів. Вона вираховується як напівсума виправлених незміщених оцінок, отриманих методами -аналізу та зміни дисперсії, і має вибіркову дисперсію не більшу за мінімальну з вибіркових дисперсій оцінок.

У розділі також проведено дослідження структури стохастичного процесу методом розрахунку залежності показника Херста від часу. Зазвичай за одним часовим рядом отримують точкову оцінку показника Херста - число, яке характеризує ступінь довготермінової залежності.

Для дослідження динаміки реалізацій мережевих трафіків у дисертації була модифікована методика, запропонована Е. Петерсом для аналізу фінансових рядів. У цьому випадку показник Херста розглядається як функція числа відліків . Поведінка функції дозволяє досліджувати трафік на наявність неперіодичних циклів і розрахувати середню довжину неперіодичного циклу, перевірити незалежність випадкових даних, визначити довготермінову та короткотермінову залежність і проаналізувати динаміку залишку.

У роботі досліджено ряд реалізацій мережевого трафіка, отриманих при реєстрації трафіка протоколів ТСР і VoIP в тій самій мережі у різний час із різним рівнем навантаження мережі

Аналіз змін показника Херста виявив такі характерні особливості реалізацій: присутня явно виражена довготермінова залежність, відсутні циклічні складові для реалізацій протоколу ТСР. У випадку VoIP прослідковується наявність нерегулярного циклу з періодом , що відповідає характерним сплескам на часовій реалізації.

У всіх досліджуваних реалізаціях була також виявлена авторегресійна залежність. Після усунення короткотермінової залежності показники Херста зменшилися, залишаючись при цьому більшими, ніж 0,5. Отже, можна зробити висновок, що реалізації мають дійсну довготермінову залежність.

Обчислювалися значення параметра Херста до та після усунення короткотермінової залежності, а також коефіцієнти авторегресії 1-го порядку для розглянутих реалізацій (табл. 1).

Таблиця 1 Значення параметра Херста і коефіцієнтів авторегресії

Реалізації трафіка	Початковий	без короткотерм. залежн.	Коеф. авторегресії
VoIP	0,72	0,61	0,6
ТСР - 1	0,8	0,73	0,41
ТСР - 2	0,98	0,95	0,55

Отримані результати дозволяють зробити висновок, що запропонована методика аналізу часових рядів є зручним інструментом дослідження самоподібної структури телекомунікаційних даних.

У третьому розділі дисертації проведено дослідження черг, що утворюються в буфері при проходженні через вузол мережі самоподібного трафіка. Крім того, побудовано математичну модель реального агрегованого трафіка, а також запропоновано метод запобігання перевантаженням у телекомунікаційній мережі, основою якого є прогнозування довжини черги.

За реальний мережевий трафік були обрані дані, які надходять у глобальну мережу Internet із локальної мережі провайдера (Ethernet-кадри протоколу другого рівня, TCP-кадри протоколу четвертого рівня). Проведені в роботі дослідження показали, що дані реалізації мережевих трафіків є самоподібними з показником Херста і мають важкі хвости, у яких параметр важкості хвоста лежить у діапазоні .

Мережі, побудовані на базі TCP/IP, породжують потужні пікові сплески, які викликають значні втрати пакетів навіть тоді, коли сумарна потреба усіх потоків є далекою від максимально припустимих значень. Причому для більших значень потреба в більшому розмірі буфера починає різко зростати уже за незначного навантаження.

У роботі було проведено імітаційне моделювання завантаженості каналу і досліджено виникнення черг у буфері для реалізацій мережевого трафіка. Враховуючи цифровий і пакетний характер сучасних високошвидкісних мереж зв'язку, систему зв'язку можна розглядати як систему масового обслуговування з детермінованим часом обслуговування, кількістю обслуговуваних приладів, що дорівнює пропускній здатності каналу, та чергою, розмір якої обмежується розміром буфера.

У роботі показано, що довжина черги в буфері визначається трьома основними параметрами ділянки трафіка: інтенсивністю трафіка, параметром Фано і показником Херста. Більші значення параметра Фано відповідають більшому розсіянню значень вхідного потоку, який навіть за невеликої інтенсивності створює чергу. Показник Херста передбачає, що за високими значеннями процесу з більшою ймовірністю також будуть слідувати високі, що не дозволяє достатньо швидко звільнитися буферу.

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

При проведенні імітаційного моделювання середня завантаженість системи змінювалася від 70% до 95%. Досліджувалася залежність середнього розміру черги в буфері від величини завантаженості каналу.

Дослідження, проведені в роботі, довели, що при завантаженості системи на 80-90%, середня черга в буфері перевищує інтенсивність ділянки трафіка у сотні разів.

Значення середньої інтенсивності реалізації трафіка довжиною відліків, оцінки показників Фано і Херста , а також значення середньої довжини черги , що виникає в буфері при завантаженні системи на 90%, і параметри важкості хвоста для черг наведено в табл. 2.

Завданням моделювання самоподібного трафіка є ґенерація часового ряду з такими ж статистичними характеристиками (величина і частота сплесків, інтенсивність трафіка) як у реального трафіка. Основними критеріями адекватності моделі трафіка вважаються статистичні характеристики черг, які виникають в буфері каналу зв'язку: середні значення та параметри ваги хвоста для черг, що утворяться в буфері нескінченного розміру, середні втрати даних, які відбуваються, коли буфер має заданий кінцевий розмір.

Таблиця 2 Параметри реального трафіка

Реалізація
Osi (1)	4500	5900	0,8	540159	5,4	0,45
Tcp (2)	4200	7200	0,81	470564	7,2	0,35
Osi (3)	3700	7100	0,82	410256	4,4	0,27
Osi (4)	2700	5200	0,78	251368	3,5	0,31

Як випадковий процес, який має фрактальні властивості, часто розглядається фрактальний броунівський рух (ФБР). Гаусівський процес називається фрактальним броунівським рухом з параметром , якщо приріст випадкового процесу має гаусівський розподіл , де - коефіцієнт дифузії, тобто,

.

Фрактальний броунівський рух з параметром збігається з класичним броунівським рухом. Прирости ФБР мають властивості самоподоби у вузькому розумінні і називаються фрактальним гаусівським шумом (ФГШ). Існує кілька методів побудови ФБР для випадку дискретного часу. Одним із найчастіше використовуваних є метод послідовного випадкового складання Фосса, який призводить до ФБР за будь-якого розділення.

Теоретично ФГШ може вважатися моделлю агрегованого самоподібного трафіка з певним показником Херста та з відповідною довготерміновою залежністю. Однак ця модель має суттєві недоліки: нульове середнє і відсутні важкі хвости, тобто, характерні для мережевого трафіка потужні пікові сплески. У наданій роботі запропоновано підхід, який ґрунтується на функціональному перетворенні ФГШ:

,

де - ряд приростів ФБР із заданим параметром на інтервалі часу ; - параметри, які регулюють частоту і величину сплесків.

Це перетворення зберігає довготермінову залежність випадкового процесу і переводить його в самоподібний процес з важкими хвостами. Оскільки приріст ФБР має нормальний розподіл , з дисперсією

,

то має логарифмічно нормальний розподіл. У роботі доведено наступне твердження.

Твердження. Нехай - ряд прирісту ФБР з параметром самоподоби на інтервалі часу . Випадковий процес, який є експонентою ФГШ , являє собою самоподібний випадковий процес у вузькому розумінні з тим же параметром Херста .

Визначення параметрів модельного процесу з реалізації реального трафіка здійснюється наступним способом. Нехай і - оцінки інтенсивності і параметра Фано для реального трафіка довжиною , модель якого необхідно побудувати. Теоретичні вирази для і , з урахуванням числових характеристик логарифмічно нормального розподілу, мають вигляд:

і .

Прирівнявши оцінки до їх теоретичних виразів, знайдемо значення параметрів і :

.

Алгоритм побудови модельної реалізації трафіка включає такі етапи:

- маючи реалізацію реального мережевого трафіка, знаходяться оцінки його характеристик , и ;

- за методом Фосса будується на інтервалі ФБШ з показником ;

- отримується ряд приростів з дисперсією ;

- обчислюються параметри і ;

- із ряду приростів отримується модельна реалізація трафіка.

У роботі було проведено моделювання мережевого трафіка для реалізацій, параметри яких представлені в табл. 3. Модельні реалізації були отримані за описаним вище алгоритмом. Для перевірки адекватності моделі досліджувалися черги , які виникають у буфері нескінченного розміру при проходженні через СМО модельних реалізацій. Чисельний аналіз черг показав, що черга є статистично самоподібною реалізацією з тим же показником Херста, як і вхідна реалізація. Параметр важкості хвоста для черг, що виникають у буфері, близький (з похибкою ~5%) до параметра черг для вихідних реальних трафіків. Перевірялася гіпотеза про рівність середніх значень черг у буфері нескінченного розміру для реального і модельного трафіка та розраховувались середні втрати даних, які відбуваються, коли буфер має заданий кінцевий розмір.

За допомогою моделювання були проведені експерименти, в яких кожна з модельних реалізацій мала таке ж середнє значення, значення параметра Фано та значення показника Херста, що й реалізації трафіків (табл. 3). Очевидно те, що модельні реалізації породжують черги, близькі за розмірами до черг, які виникають при проходженні реального трафіка. Гіпотеза про рівність середніх значень черг в буфері для реального і модельного трафіка у кожному випадку була прийнята з рівнем значності .

Була побудована залежність середнього розміру буферної пам'яті при зміні завантаженості системи від 70% до 95% для досліджуваних модельних реалізацій трафіків. Виходячи з усього перерахованого вище для проведення практичних досліджень поведінка реальних і модельних трафіків в каналі зв'язку вважається ідентичною.

Таблиця 3 Параметри модельного трафіка

Реалізація
Osi (1)	4430	5850	0,8	570000	5,9	0,41
Tcp (2)	4100	7260	0,86	440000	6,7	0,36
Osi (3)	3710	7130	0,82	350000	4,1	0,29
Osi (4)	2740	5280	0,78	210000	3,8	0,33

Математична модель самоподібного трафіка дозволяє проводити імітаційне моделювання із заданими розмірами буферної пам'яті і пропускної здатності каналу. Дослідження, проведені в роботі, показали, що для мінімізації втрат при завантаженості системи на 80-90% розмір буфера повинен перевищувати інтенсивність ділянки трафіка в сотні разів.

Результати чисельного експерименту дозволили для відомого значення пропускної здатності і отриманих параметрів вхідного потоку даних визначити середній розмір буферної пам'яті, необхідний для нормального проходження (втрати даних не перевищують 4%) ділянки трафіка довжиною відліків через комутатор і/або для відомого значення буферної пам'яті визначити необхідну пропускну здатність каналу .

Для узагальнення результатів при проведенні досліджень були використані такі нормовані параметри: відношення параметра Фано до інтенсивності трафіка і відношення інтенсивності трафіка до пропускної здатності каналу .

Отримані залежності дозволяють при заданих розмірах буферної пам'яті і пропускної здатності каналу визначати ступінь завантаженості каналу як , де величина являє собою середній розмір буферної пам'яті, необхідний для нормального проходження ділянки трафіка через комутатор. Шляхом моніторингу вхідного трафіка, розрахувавши ступінь завантаженості каналу відповідно до отриманих модельних результатів, можна її прогнозувати і не допускати перевантаження мережі, управляючи буферами каналів і/або потоками даних.

У роботі запропоновано такий метод запобігання перевантаженням комутованого каналу зв'язку шляхом моніторингу вхідного трафіка:

- у часовому ряді, який відповідає трафіку, що надходить на вхід комутатора, виділяємо вікно фіксованої довжини і для нього знаходимо оцінки інтенсивності , параметра Фано і показника Херста ;

- формуємо прогноз розміру буферної пам'яті , необхідного для нормального проходження цієї ділянки трафіка через вузол зв'язку і/або розмір необхідної пропускної здатності каналу ;

- якщо розрахункова буферна пам'ять перевищує розмір наявного буфера і/або розрахунковий розмір пропускної здатності каналу перевищує наявний, то необхідне системне управління розміром буфера вузла зв'язку, пропускної здатності каналів або потоками даних;

- пересуваємо вікно довжини уперед на задану величину зсуву і здійснюємо прогноз наступного значення , і т.д.

Прогнозуючи появу перевантаження, можна виділити необхідний розмір буферної пам'яті і/або пропускну здатність каналу . Якщо обрахований розмір буфера більший за існуючий , то система виділяє необхідний розмір буферної пам'яті. Також визначається необхідний розмір пропускної здатності каналу із отриманих даних. Якщо необхідний розмір пропускної здатності каналу більший, ніж у наявного , то система виділяє необхідний ресурс , розподіливши при цьому другому каналу усю пропускну здатність, що залишилася.

У четвертому розділі дисертації наведені результати чисельних і натурних експериментів, які полягали в дослідженні розроблених моделей і методів.

Модель і методи були випробувані на тестовій модельній мережі, створеній у середовищі мережевого емулятора OPNET Modeler, а потім у реальних комп'ютерних і телекомунікаційних мережах. Розроблені модель самоподібного трафіка і метод прогнозування перевантажень у мережі перевірялися при різних режимах роботи комп'ютерних і телекомунікаційних мереж та при різному навантаженні на них.

Дослідження довели, що запропонована модель надає можливості генерувати агрегований самоподібний трафік і досліджувати його вплив на завантаженість мережі. Така модель дозволяє адекватно розраховувати необхідні характеристики мережі (розмір буфера, пропускну здатність каналів, затримки в мережі та ін.). Проведені імітаційне моделювання та реальні експерименти показали, що запропонований метод прогнозування перевантаження ефективно працює при інтенсивному навантаженні в мережі.

Запропоновані в роботі модель й методи були впровадженні на Державному підприємстві "Завод ім. В.О. Малишева", у ТОВ "Харківські телекомунікації", у ТОВ "Обліково-керівні системи".

Досліджувана локальна мережа заводу ім. В.О. Малишева складається з 97 робочих станцій. У ході експерименту було виявлено найбільш критичну ділянку мережі, на якій час проходження даних найбільший і 80-90% загальної кількості даних втрачається саме на ній. Під час експерименту проводилося динамічне управління пропускною здатністю каналів та управління розміром буферної пам'яті вузлів за допомогою методу прогнозування, описаного у розділі 3.

Використання методів динамічного розподілу пропускної здатності і управління розміром буферної пам'яті дозволило знизити кількість втрачених даних майже у два рази.

За однакового обсягу інформації, що передається, втрати при передачі самоподібного трафіка помітно знизилися (з 5% до 3%), помітно зменшилися затримки і зросла швидкість передачі даних (табл. 4).

Таблиця 4 Значення реалізацій трафіків

Параметр	Ділянка мережі без управління	Модельна мережа без управління	Модельна мережа з управлінням	Ділянка мережі з управлінням
Макс. швидкість передачі, Мбіт/с	92,46	92,2	98,71	98,65
Мін. затримка, мс	0,54	0,33	0,098	0,092
Макс. затримка, мс	1,45	1,48	0,52	0,51
Макс. значення втрат пакетів, %	4,4	4,5	3,1	3

Використання методів прогнозування й запобігання перевантаженням в локальних мережах ТОВ "Харківські телекомунікації" і в ТОВ "Обліково-керівні системи" дозволило оптимізувати управління трафіком шляхом динамічного розподілення мережевих ресурсів.

Результати експериментів були реалізовані в локальній мережі заводу ім. В.О. Малишева і принесли такий ефект: підвищення утилізації каналів передачі даних за рахунок перенаправлення найбільш критичних інформаційних потоків на менш завантажені альтернативні канали привело до зменшення на 10% втрат даних в мережі.

Висновки

Дисертаційну роботу присвячено математичному моделюванню та методам дослідження самоподібного мережевого трафіка. У процесі досліджень запропонована математична модель самоподібного трафіка. Результати імітаційного моделювання дозволили розробити методи прогнозування та запобігання завантаженням в системах передачі даних.

Аналіз отриманих в дисертаційній роботі наукових і практичних результатів дозволяє зробити такі висновки:

1. Проведено обзор і аналіз сучасного стану теорії самоподібного мережевого трафіка, розглянуто основні поняття, методи дослідження, математичні моделі трафіка на основі самоподібних стохастичних процесів.

2. Проведено порівняльний аналіз оцінювання параметра Херста як ступеня самоподоби випадкового процесу. Запропоновано метод знаходження незміщеної оцінки показника Херста з використанням методів нормованого розмаху і зміни дисперсії агрегованого ряду. Даний метод, на відміну від уже існуючих, дозволяє отримати незміщену оцінку показника Херста, яка має вибіркову дисперсію не більшу, ніж мінімальна із вибіркових дисперсій оцінок.

3. Отримав подальший розвиток -аналіз стосовно телекомунікаційних даних. Показник Херста розглядається як функція числа часових відліків, що дозволяє визначити такі характерні особливості реалізацій мережевого трафіка: незалежність випадкових даних, наявність циклічних складових і середню довжину неперіодичного циклу, наявність довготермінової і короткотермінової залежності.

4. Шляхом імітаційного моделювання досліджено характеристики самоподібного трафіка, які викликають появу перевантажень при проходженні трафіка через комутований канал зв'язку. Моделювання проходження трафіка через вузол зв'язку показало, що значущими є три характеристики процесу: інтенсивність, параметр Фано і показник Херста. Проведено аналіз впливу кожного параметра на розмір середньої довжини черги в буфері каналу зв'язку.

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

6. Проведено імітаційне моделювання і розроблено метод оцінювання залежності ступеня завантаженості каналу мережі від параметрів трафіка, який проходить, що, на відміну від існуючих методів, дозволяє при заданих розмірах буферної пам'яті і пропускної здатності каналу визначати гранично допустиме навантаження даної мережі. Аналіз результатів імітаційного моделювання довів, що розроблена математична модель трафіка є адекватною.

7. Запропоновано методи прогнозування та запобігання перевантаженям у мережі. Результати чисельного експерименту дозволили для відомого значення пропускної здатності і отриманих параметрів вхідного потоку даних визначити середній розмір буферної пам'яті, необхідний для нормального проходження ділянки трафіка через комутатор і/або для відомого значення буферної пам'яті визначити необхідну пропускну здатність каналу та за необхідності перенаправляти потоки даних.

8. За допомогою системи OPNET проведено імітаційне моделювання розроблених методів і моделей, яке виявило можливість прогнозування перевантажень мережі й управління потоками даних, що надходять на вузол зв'язку, дозволяючи зменшити втрати даних на 5-10%, зменшити затримки передачі даних на 30-40%, збільшити швидкість передачі даних на 5-10% та уникнути перевантаження буферної пам'яті у вузлах зв'язку.

9. Результати досліджень використовуються на Державному підприємстві "Завод ім. В.О. Малишева" при реконфігурації комп'ютерної мережі; в ТОВ "Харківські телекомунікації" і ТОВ "Обліково-керівні системи" при розробці білінгових систем; а також у навчальному процесі Харківського національного університету радіоелектроніки, що підтверджено відповідними актами.

Список опублікованих праць за темою дисертації

1. Кириченко Л.О. Cравнительный анализ методов оценки параметра Xерста самоподобных процессов / Л.О. Кириченко, Т.А. Радивилова, М.И. Синельникова // Системи обробки інформації. - 2005. - Вип. 8(48). - С. 36-40.

2. Кириченко Л.О. Исследование долгосрочной зависимости сетевого трафика методом R/S-анализа / Л.О. Кириченко, Т.А. Радивилова // Автоматизированные системы управления и приборы автоматики. - 2006. - Выпуск 135. - С. 51-55.

3. Кириченко Л.О. Исследование влияния самоподобия трафика при проектировании фрагмента сети / Л.О. Кириченко, Т.А. Радивилова // Нові технології. - 2007. - № 1-2. - С. 124-129.

4. Кириченко Л.О. Алгоритм предупреждения перегрузки компьютерной сети путем прогнозирования средней длины очереди / Л.О. Кириченко, Т.А. Радивилова, А.В. Стороженко // Збірник наукових праць Харківського університету повітряних сил. - 2007. - № 3(15). - С. 94-97.

5. Карпухин А.В. Самоподобие в информационных системах / А.В. Карпухин, Л.О. Кириченко, Т.А. Радивилова // Прикладная радиоэлектроника. - 2008. - T. 7. - № 1. - С. 54-64.

6. Kirichenko L. Analysis of network performance under selfsimilar system loading by computer simulation / L. Kirichenko, Т. Radivilova // Бионика интеллекта. - 2008. - № 1(68). - C. 158-161.

7. Radivilova T. Modelling of advancing of a self-similar network traffic in communication channel / T. Radivilova // Восточно-европейский журнал передовых технологий. Информационные технологии и системы управления. - 2007. - № 4/2 (28). - С. 12-15.

8. Радивилова Т.А. Некоторые статистичесские характеристики оценок параметра Херста / Т.А. Радивилова, М.И. Синельникова // Радіоелектроніка і молодь в XXI ст. : 10-й ювілейний міжнар. молодіжний форум, 10-12 квіт. 2006 р.: матеріали конф. - Харків, 2006. - С. 511.

9. Кириченко Л.О. Выявление долгосрочной и краткосрочной зависимости временных рядов путем R/S-анализа / Л.О. Кириченко, Т.А. Радивилова // Дні науки: "Системний аналіз і управління" : наук.-практ. конф., 5-6 жовт. 2006 р.: зб. тез доповідей. - Запоріжжя, 2006. - Т. 3. - С. 29-31.

10. Кириченко Л.О. Моделирование прохождения самоподобного сетевого трафика через канал связи / Л.О. Кириченко, Т.А. Радивилова // Современные информационные и электронные технологии: 8-я междунар. науч.-практич. конф., 21-25 мая 2007 г.: труды конф. - Одесса, 2007. - С. 121.

11. Кириченко Л.О. Управление параметрами сети на основе мониторинга входной нагрузки / Л.О. Кириченко, Т.А. Радивилова // Сучасні інформаційні системи. Проблеми та тенденціц розвитку: 2-а міжнар. наукова конф., 2-5 жовт. 2007 р.: матеріали конф. - Харків-Туапсе, 2007. - С. 89-90.

12. Кіріченко Л.О. Управління параметрами мережі на основі моніторингу вхідного навантаження / [Кіріченко, Т.А. Радівілова, О.О. Стрілець, Є. С. Ієвлєв] // Комп'ютерні науки та інформаційні технології "CSIT-2007" : міжнар. наук.-техн. конф., 27-29 верес. 2007 р.: матеріали конф. - Львів, 2007. - С. 206-209.

13. Карпухин А.В. Исследование продуктивности сети и возникновения перегрузки при самоподобной нагрузке с помощью OPNET Modeler / А.В. Карпухин, Л.О. Кириченко, Т.А. Радивилова // Современные информационные и электронные технологии: 9-я междунар. науч.-практич. конф., 19-23 мая 2007 г.: труды конф. - Одесса 2008. - С. 102.

14. Kirichenko L. Improvement quality of network service under selfsimilar loading / L. Kirichenko, Т. Radivilova, О. Karpukhin // Стратегия качества в промишленности и образовании: 4-я междунар. конф., 30 мая-6 июня., 2008 г.: материалы конф. - Варна, 2008. - C. 612-615.

15. Радівілова Т.А. Моделирование самоподобного трафика с заданными характеристиками / T. А. Радівілова // Современные проблемы радиотехники и телекоммуникаций "РТ-2007": 3-я междунар. молод. науч.-техн. конф., 17-21 апр. 2007 г.: материалы конф. - Севастополь, 2007. - С. 210.

16. Radivilova T. R/S-analysis of networking traffic for revealing long-term and short-term dependence / T. Radivilova // Комп'ютерні науки та інформаційні технології "CSIT-2006" : 1-a міжнар. наук.-техн. конф., 28-30 верес. 2006 р.: матеріали конф. - Львів, 2006. - С. 59-61.

Размещено на Allbest.ru

...