ДонНТУ   Портал магістрів

Бойко Ганна Андріївна

Факультет комп'ютерних інформаційних технологій і автоматики

Кафедра автоматики та телекомункацій

Спеціальність "Телекомунікаційні системи та мережі"

Розробка та дослідження алгоритмів прогностичного керування навантаженням в мережах мобільного зв’язку

Науковий керівник: к.т.н., доц. Дегтяренко І.В.

Резюме Біографія Реферат

Реферат за темою випускної роботи

Зміст

• Вступ
• 1. Актуальність теми
• 2. Мета і задачі дослідження та заплановані результати
• 3. Огляд досліджень та розробок
• 4. Застосування методу ARFIMA(p,d,q) для прогнозування мультисервісного трафіку
• Висновки
• Перелік посилань

Вступ

Сучасні телекомунікаційні мережі характеризуються зростаючими об’ємами трафіку, що передається, та підвищенням вимог до якості його обслуговування. Протягом останніх п'яти років обсяги світового ринку інформаційних технологій зростають у середньому на 10% на рік при середньому зростанні світової економіки в 3-3,5% (за даними аналітичної групи ТАСС-Телеком) [1]. Згідно з дослідженнями Cisco Visual Networking Index [2], глобальний трафік IP у вісім разів збільшився за останні 5 років, і збільшиться у три рази протягом найближчих 5 років. В цілому, IP-трафік буде зростати на 29 відсотків з 2011 по 2016 рік. На перший план виходять різні IP – послуги: IPTV, VoIP, відео за запитом та ін. Згідно з цими тенденціями, можна припустити, що найближчим часом обсяг IP - трафіку в світі різко збільшиться, а сервіси реального часу будуть займати велику частину цього обсягу. Це призводить до того, що користувачам послуг потрібен канал зв'язку, який задовольнить вимогам QoS. Оскільки різні послуги використовують одні й ті ж канали транспортної мережі, при цьому кожна послуга висуває свої вимоги до каналу зв'язку, виникає задача розподілу ресурсу каналу зв'язку між різними послугами мережі. Статичний розподіл ресурсу каналу, в більшості випадків, призводить до неефективного використання каналу зв'язку, тому керування повинно відбуватися миттєво, в залежності від інтенсивності використання різних послуг. Для високошвидкісних конвергентних мереж постає проблема нерівномірності і нестаціонарності трафіку. Існує необхідність побудови динамічної системі, яка б змогла підлаштовуватися під стрибкоподібне навантаження, враховуючи при цьому його властивості. У даній роботі буде порушена тема можливості складання довгострокових прогнозів, що надалі дозволить проводити стратегічне планування телекомунікаційної мережі з точки зору ефективного використання її ресурсів та запобігання перевантажень, які призводять до втрати інформації.

1. Актуальність теми

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

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

"Самоподібність" являє собою властивість процесу зберігати свою поведінку і зовнішні ознаки при розгляді в різному масштабі [3]. Самоподібний процес виглядає менш згладженим, більш нерівномірним (тобто має більшу дисперсією), ніж чисто випадковий процес. Нерівномірність самоподібного процесу зображена на рис. 1.

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

2. Мета і задачі дослідження та заплановані результати

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

Основні задачі дослідження:

1. Аналіз особливостей сучасних телекомунікаційних мереж та та навантаження.
2. Постановка умов до трафіку, що підлягає прогнозуванню.
3. Вибір методу, яким буде реалізовано прогноз.
4. Визначення порядку вибору параметрів прогнозної моделі.
5. Дослідження прогнозних значень та оцінка ефективності обраного методу.

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

Предмет дослідження: трафік телекомунікаційної мережі.

В рамках магістерської роботи планується отримання актуального наукового результату:

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

3. Огляд досліджень та розробок

Властивість самоподібності є визначною у можливості складання прогнозу мережного трафіку. Аналізу мультисервісного трафіку та підходам до його моделювання присвячено багато робіт за останні 20 років. У 1999 р. описав модель самоподібного пакетного трафіку та визначив вирази для отримання вірогідности втрат пакетів такої моделі Цибаков Б.С. [4]. Також необхідно виділити книги Шелухіна О.І. такі, як, наприклад, "Самоподібність та фрактали. Телекомунікаційний додаток" [5] та "Мультифрактали. Інфокомунікаційні додатки" [6]. Аналізом структури мережного трафіку та визначенням впливу ефекту само подібності на якість обслуговування займався Петров В.В. [7].

Аналітичний огляд методів прогнозування зручно представлений, наприклад, у науковому посібнику Е.Є. Тихонова "Методи прогнозування в умовах ринку" [8]. Авторегресійні моделі досліджені авторами Box E.P.G., Jenkins G.M., Reinsel G.C. у роботі "Time series analysis: forecasting and control" [9]. Модель ARFIMA, що являє собою модель Бокса-Дженкінса з дробовим порядком інтегрованості, детально розглядається Granger, C. W. J.; Joyeux, R [10].

Також варто виділити деякі кваліфікаційні роботи магістрів ДонНТУ, що стосуються даної теми. Принципам моделювання самоподібного трафіку присвячена робота Жалейко Є.В. [11]. Також, властивостями мультисервісного трафіку займається Шепеленко А.Г. [12]. В роботі Чекункова О.С. [13] досліджується система балансування навантаження у конвергентній телекомунікаційній мережі з прогнозуванням трафіку на основі нейромережі та авторегресійної моделі.

4. Застосування методу ARFIMA(p,q,d) для прогнозування мультисервісного трафіку

Застосування методів прогнозування дозволяє заздалегідь дізнатись, яку пропускну здатність потрібно буде виділити для обслуговування трафіку, що надходить. Існує декілька загальновизнаних методів прогнозування часових рядів. Методи Бокса-Дженкінса (ARIMA), на відміну від інших методик прогнозування часових рядів, не передбачають якої-небудь чіткої моделі для прогнозування даної часової серії. Задається лише загальний клас моделей, що описують часовий ряд і що дозволяють якось виражати поточне значення змінної через попередні. Потім алгоритм, підстроюючи внутрішні параметри, сам обирає найбільш адекватну модель прогнозування. Підхід ARFIMA дозволяє прогнозувати процеси з довгостроковою пам’яттю, тобто може бути використаний для прогнозування трафіку, що має залежність між досить віддаленими в часі спростереженнями. Для реалізації цього методу оцінюється стаціонарність процесу, при необхідності, ряд перетворюється на стаціонарний, потім визначаються параметри авторегресійної складової p, ковзного середнього q (за поведінкою нормованої АКФ) і дрібно-інтегровані складової d (за методом Віттла) [3, 14].

ARFIMA(p,q,d)-модель може бути описана так [3]:

Першим кроком при створенні ARFIMA(p,q,d)-моделі є визначення параметрів p, q, і порядку інтегрованості ряду d. Параметр d може приймати усі значення від 0 до1. Випадок d=0 відповідає короткій пам'яті ряду, тоді як при d=1 можна зробити висновок про нескінченну пам'ять. Для визначення параметра d для ARFIMA-моделі використовується метод Віттла (Whittle), заснований на трансформації вхідних даних за рахунок їх апроксимації. Метод заснований на пошуку мінімуму функції R(d) за формулою:

Основна проблема в процесі прогнозування часових рядів полягає у визначенні параметрів даної моделі. При розрахунку p і q використовуються характеристики нормованої АКФ. Іншими словами, будується ARMA(p,q)-модель досліджуваного часового ряду із заданими параметрами, а потім будується нормована АКФ для цієї реалізації. По поведінці АКФ приймають рішення про найбільш кращий вибір пари p і q. Бажаною поведінкою нормованої АКФ є її швидке затухання. При цьому також оцінюється ефективність збільшення коефіцієнта загасання АКФ при зміні параметрів p і q в причину того, що великі їх значення приводять до збільшення обчислювального процесу. Тому перевага віддається моделям із найменшими значеннями цих параметрів. Обчислені параметри авторегресійної складової і ковзного середнього можна використовувати в усіх вищенаведених моделях. Алгоритм щодо вибору оптимального швидкого затухання нормованої автокореляційної функції будується на розрахунку площі фігури АКФ, яка повинна бути мінімальною.

В якості трафіку для аналізу було обрано трафік HTTP запитів до веб-сервера космічного центру Кеннеді, NASA протягом 1 місяця [15]. При розгляданні трафіку без агрегації залежність наступного значення від попереднього майже неможливо помітити. Тому проаналізуємо реалізацію з різними періодами агрегації, де залежність стає суттєвою. Найбільший показник параметру Херста (0,9) отримано для трафіку с періодом дискретизації рівним 6 годинам. Агреговані дані представлені на рис. 2.

Як бачимо, трафік, агрегований с періодом дискретизації 6 годин, має помітну добову та тижневу циклічність. Отже, маємо нестаціонарне навантаження, что характеризується властивостями самоподібності та довгостроковою пам’яттю. Для даних умов найбільш придатною моделлю прогнозування є ARFIMA(p,q,d).

Для вибору параметрів авторегресійної складової p та ковзного середньго q була знайдена площа нормованої АКФ для кожної пари параметрів: p[1; 10] та q[1; 10].

На рис. 3 видно, що найменша площа, яку займає АКФ, отримана для значень p=6, q=10. Значення параметра d для моделі ARFIMA розраховується з використанням методу Віттла і залежить від вхідних даних. Розраховане значення q=0,161. З використанням розрахованих значень параметрів моделі ARFIMA, отримано прогонзне значення трафіку с періодом дискретизації 6 годин протягом місяця та порівняно з графіком реального навантаження (рис. 4).

За наведеним графіком можна побачити високу якість прогнозу із використанням моделі ARFIMA. Тривалість достовірного прогнозу для моделі складає більше 85 відліків з періодом дискретизації 6 годин, тобто 510 годин або 21 добу. Це підтверджує, що ARFIMA-моделі є вкрай зручним інструментом аналізу таких часових рядів із довгостроковою пам’яттю. Для більшої наглядності результату на рис. 5 приведений графік помилки прогнозування.

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

Висновки

Розглянуто використання алгоритма ARFIMA для трафіку HTTP запитів до веб-сервера космічного центру. Аналіз трафіку виявив його фрактальні властивості (схожість АКФ при різних періодах дискретизації), циклічність та наявність довгострокової залежності при повільно затухаючій АКФ. Був визначений показник самоподібності для агрегації з періодом дискретизації 6 годин – параметр Херста дорівнює 0,9, що доводить високу ступінь самоподібності процесу. Обрані параметри моделі ARFIMA p=6 і q=10 на основі площі АКФ, розрахований параметр d=0,161 за методом Віттла та здійснена програмна реалізація моделі. Запропонований алгоритм дає достовірний прогноз протягом 21 дня, що говорить про ефективність використання методу ARFIMA для прогнозування трафіку телекомунікаційних мереж, що мають високий рівень самоподібності та довгосторокову залежність.

Перелік посилань

1. Рейтинг ТАСС-Телеком [електронний ресурс], 2012. – Режим доступу: http://tasstelecom.ru/news/one/14078.
2. Cisco Visual Networking Index: Forecast and Metodology, 2011-2016 [електронний ресурс]. – Режим доступу: http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_c11-481360_ns827_Networking_Solutions_White_Paper.html.
3. Костромицкий А.И. Подходы к моделированию самоподобного трафика / А.И. Костромицкий, В.С. Волотка // Восточно-Европейский журнал передовых технологий. – 2010.
4. Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса/ Цыбаков Б.С. – Радиотехника-№5, 1999 г.
5. Шелухин О.И. Самоподобие и фракталы. Телекоммуникационные приложения/ Шелухин О.И., Осин А.В., Смольский С.М. – М.: ФИЗМАТЛИТ. 2008. – 368 с.
6. Шелухин, О. И. Мультифракталы. Инфокоммуникационные приложения приложения / О. И. Шелухин . – М.:Горячая Линия –Телеком, 2011. – 578 с.
7. Петров В.В. Структура телетрафика и алгоритм обеспечения качества обслуживания при влиянии эффекта самоподобия : Диссертация на соискание ученой степени кандидата технических наук / Петров В.В. — М., 2004. — 199 с.
8. Тихонов Э. Я. Методы прогнозирования в условиях рынка: Учебное пособие./ Тихонов Э. Я. – Невинномысск, 2006.– 221 с.
9. Box E.P.G. Time series analysis : forecasting and control / Box E.P.G., Jenkins G.M., Reinsel G.C. — Prentice-Hall, 1994. — 598 p.
10. Granger, C.W.J. An Introduction to Long-Memory Time Series Models and Fractional Differencing [Текст] / C.W.J. Granger, R. Joyeux // Journal of Time Series Analysis. – 1980. – N 1(1).
11. Жалейко Е.В. Методы моделирования самоподобного трафика/ Жалейко Е.В.//Материалы 7-й Международной молодежной научно-технической конференции «Современные проблемы радиотехники и телекоммуникаций» (направление №2 – «Телекоммуникационные системы и сети»). – Севастополь, 2011.
12. Шепеленко А. Г. Спосіб оцінки параметра Херста для трафіку IP-мереж /Шепеленко А. Г. Дегтяренко І. В.// Вісник Вінницького політехнічного інституту. – Вінниця, 2007. – №5(157). – С. 157-160.
13. Чекунков О.С. Дослідження системи прогнозування навантаження на елементи телекомунікаційної мережі, побудованої на основі нейронної мережі прямого поширення/ Чекунков О.С. – Матеріали збірника наукових праць ХІI науково?технічної конференції аспірантів та студентів «Автоматизація технологічних об’єктів та процесів. Пошук молодих». – Донецьк, 2012. – С. 114-117.
14. Перцовский О.Е. Моделирование валютных рынков на основе процессов с длинной памятью: Препринт WP2/2004/03 – М.: ГУ ВШЭ, 2003. – с. 15-17.
15. Two traces contain two month's worth of all HTTP requests to the NASA Kennedy Space Center WWW server in Florida [електроний ресурс]. – Режим доступа: http://ita.ee.lbl.gov/html/contrib/NASA-HTTP.html..