Вдосконалення алгоритмів QOS маршрутизації в мережах з технологією IP/MPLS на основі прогнозу трафіка

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

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

Державний університет інформаційно-комунікаційних технологій

Автореферат

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

05.12.02 - Телекомунікаційні системи та мережі

Вдосконалення алгоритмів QoS маршрутизації в мережах з технологією IP/MPLS на основі прогнозу трафіка

Касимов Рустам Романович

Київ - 2011

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

Робота виконана в Державному університеті інформаційно-комунікаційних технологій Міністерства транспорту та зв'язку України.

Науковий керівник: доктор технічних наук, професор Артеменко Михайло Юхимович, Державний університет інформаційно-комунікаційних технологій, завідувач кафедри телекомунікаційних технологій

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

доктор технічних наук, професор Костік Богдан Ярославович, Дирекція первинної мережі ВАТ “Укртелеком”, директор

кандидат технічних наук, професор Пілінський Володимир Володимирович, Національний технічний університет України "Київський політехнічний інститут", професор кафедри звукотехніки та реєстрації інформації

Вчений секретар спеціалізованої вченої ради Д26.861.01, д.т.н., проф. А.І. Семенко

Анотація

мережа маршрутизація трафік

Касимов Р.Р. Вдосконалення алгоритмів QoS маршрутизації в мережах з технологією IP/MPLS на основі прогнозу трафіка. - Рукопис.

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

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

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

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

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

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

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

Проведено імітаційне моделювання запропонованої методики прогнозування та алгоритмів маршрутизації в мережі IP/MPLS з використанням симулятора мережі NS2, яке показало їх переваги на 3-20% в порівнянні з відомими алгоритмами маршрутизації за такими показниками як пікова завантаженість з'єднувальних ліній та кількість відмов по запитах на встановлення з'єднання.

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

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

Ключові слова: мережа з технологією IP/MPLS, вейвлет аналіз, штучні нейронні мережі, прогнозування трафіка, QoS маршрутизація.

Аннотация

Касымов Р.Р. Усовершенствование алгоритмов QoS маршрутизации в сетях с технологией IP/MPLS на основе прогноза трафика. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 - телекоммуникационные системы и сети. - Государственный университет информационно коммуникационных технологий, Киев, 2011.

Диссертация посвящена совершенствованию алгоритмов маршрутизации в сетях IP/MPLS с использованием прогноза трафика для определения существующих ресурсов и построения таблиц маршрутизации.

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

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

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

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

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

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

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

Ключевые слова: сеть с технологией IP/MPLS, вейвлет анализ, искусственные нейронные сети, прогнозирование трафика, QoS маршрутизация.

Summary

Kasymov R.R. Improvements of QoS routing algorithms in IP/MPLS networks based on traffic forecast

Dissertation on the receipt of scientific degree of candidate of engineering sciences in specialty 05.12.02 - telecommunication systems and networks. - State university of information and communication technologies, Kyiv, 2011.

Dissertation is devoted to improvement of routing algorithms in IP/MPLS networks by using of traffic forecast to estimate of unused network resources.

The method of short term forecasting based on wavelet decomposition and cascade-correlation neural networks usage is introduced. The usage of neural networks for forecasting purposes allows to improve system reliability and forecasting quality.

New approach for usage of adaptive neural-fuzzy interference system for early forecast quality estimation has been introduced. Proposed approach allows to analyze heterogeneous data to estimate their impact on forecasting quality.

Improved heuristic algorithm for maximum flow routing has been developed. The algorithm determines the unused network resources by comparing of traffic demand matrix and existing routing scheme. As a result algorithm allows to improve QoS parameters and reduce the number of request for LSP establishing.

Proposed usage of piecewise-linear penalty functions to engage the available bandwidth as a component of the cost function, which improved the efficiency of a resource utilization of network bandwidth.

Introduction of the developed conceptions and methods in the traffic management systems of the modern telecommunications networks will give possibility to carry out more effective and more accomplished management.

Keywords: IP/MPLS network, wavelet analysis, neural networks, traffic forecasting, QoS routing.

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

Актуальність теми. Останнє десятиліття відзначилось стрімким розвитком мережі Інтернет та появою і розповсюдженням нових мультимедіа сервісів, що працюють у режимі реального часу, таких як Інтернет-телефонія, відео конференції, відео за вимогою та інші. Обмеження стандартного ІР протоколу по підтримці лише одного класу обслуговування (best-effort service) дозволяють використовувати його в сервісах, що не є чутливими до параметрів затримки, втрати пакетів чи таких, що можуть реагувати на перевантаження, зменшуючи швидкість передачі. Прикладом таких сервісів можуть бути HTTP, FTP, E-Mail, Telnet та інші. Натомість вимоги сервісів реального часу до гарантованої якості обслуговування потребують застосування принципово нових засобів маршрутизації, контролю та забезпечення параметрів якості обслуговування (Quality of Service - QoS). Результатом розвитку комунікаційних технологій на шляху до забезпечення зростаючих вимог QoS стала поява цілого ряду технологій, серед яких широкого комерційного успіху та практичного застосування знайшла технологія мультипротокольної комутації міток (Multiprotocol Label Switching - MPLS) ) завдяки високій гнучкості та наявності механізмів агрегації та керування трафіком (Traffic Engineering -ТЕ). Механізми трафік інженерії, стандартизовані як розширення технології MPLS, забезпечили можливість оптимізації використання мережних ресурсів для надання традиційних і створення нових послуг. Завдяки цьому MPLS-TE на сьогоднішній день є базовою платформою для побудови мереж NGN і надання нових послуг.

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

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

Питанню забезпечення підтримки параметрів QoS в мережах MPLS приділяється багато уваги. Над питаннями створення методів маршрутизації в телекомунікаційних мережах працювали такі вчені та дослідники, як Бертсекас Д., Галагер Р., Зайченко Ю.П., Френк Г., Фріш И., Барбер Д., Поповський В.В. та інші.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи безпосередньо пов'язана з виконанням програми розвитку галузі телекомунікацій України в частині побудови системи управління телекомунікаційними мережами, науково-дослідної роботи Державного університету інформаційно-комунікаційних технологій (ДУІКТ) на тему: «Методи оптимального управління різнорідними телекомунікаційними мережами» (номер державної реєстрації № 0107U011932).

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

Для досягнення поставленої мети вирішуються такі основні науково-технічні задачі:

порівняльний аналіз і дослідження методів та концепцій побудови систем керування трафіка в мережах з технологією IP/MPLS;

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

розробка методики оцінки точності прогнозу трафіка;

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

розробка централізованої системи маршрутизації в мережах з технологією IP/MPLS;

проведення імітаційного моделювання методики прогнозування та запропонованих алгоритмів з використанням програмних симуляторів мережі.

Об'єктом досліджень є телекомунікаційні мережі з технологією IP/MPLS.

Предметом досліджень - методи прогнозування і алгоритми маршрутизації трафіка мультисервісної мережі.

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

Наукова новизна одержаних результатів полягає в наступному.

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

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

Запропоновано вдосконалений евристичний алгоритм для offline маршрутизації в мережі IP/MPLS, відмінністю якого від відомих є підвищення рівня якості сервісу за рахунок використання ресурсів телекомунікаційної мережі, знайдених на основі аналізу прогнозу та поточної схеми маршрутизації.

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

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

Практичне значення одержаних результатів полягає в наступному.

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

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

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

Результати дисертаційної роботи знайшли застосування в науково-дослідній роботі Державного університету інформаційно-комунікаційних технологій на тему: «Методи оптимального управління різнорідними телекомунікаційними мережами» номер державної реєстрації № 0107U011932 (акт впровадження від 10.11.2011 ), а також в навчальному процесі ДУІКТ при викладанні дисциплін (акт впровадження від 10.11.2011).

Особистий внесок здобувача. В дисертаційній роботі особисто автором проведено дослідження та одержано такі результати: в [1] виконано аналіз систем керування трафіком в мережах IP/MPLS; в [2] - проведений аналіз вибору глибини вейвлет декомпозиції в залежності від показника Херста; в [3] розроблена методика прогнозування трафіка з використанням вейвлет декомпозиції та штучних нейронних мереж; в [4] вдосконалений алгоритм маршрутизації за максимальним потоком; в [5] запропоновано використання кусково-лінійної функції штрафу на зайняття доступної смуги пропускання як компоненти функції вартості; в [13] - вдосконалений евристичний алгоритм маршрутизації та представлені результати імітаційного моделювання.

Апробація роботи. Основні теоретичні та практичні результати досліджень доповідалися автором особисто на дев'яти Міжнародних Науково-технічних конференціях і семінарах, а саме:

XXVIII МНТК “Проблеми електроніки” (НТУУ КПІ, м. Київ, 2008 р.);

ІІІ, V МНТК “Проблеми телекомунікацій ” (НТУУ КПІ, м. Київ, 2008, 2010);

VІ, VІІ МНТК студентства та молоді «Світ інформації та телекомунікацій - 2009, 2010» (ДУІКТ, м. Київ, 2009, 2010);

ІV, V, VІ Міжнародній науково-технічній конференції (МНТК) “Сучасні інформаційно-комунікаційні технології (COMINFO'2008, 2009, 2010)” (АР Крим, м. Ялта-Лівадія, 2008, 2009, 2010 р.);

МНПК «Актуальні питання регулювання у сфері телекомунікацій та користування радіочастотним ресурсом». (м. Київ, 2010).

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

Структура та обсяг дисертації. Робота складається зі вступу, чотирьох розділів, висновку, переліку використаної літератури та додатків. Загальний обсяг роботи складає 179 сторінок друкованого тексту, який у тому числі містить 147 сторінок основного тексту, 15 сторінок з рисунками та 4 сторінки з таблицями, 12 сторінок списку використаних джерел (125 найменувань) та 22 сторінок додатків.

2. Основний зміст

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

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

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

На рис. 1 представлені основні типи та підходи до побудови систем MPLS-TE:

Рис. 1. Основні типи та підходи до побудови систем MPLS-TE

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

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

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

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

У другому розділі досліджено алгоритми прогнозування трафіка, представлена методика побудови прогнозу трафіка з оцінкою його якості на ранньому етапі, розглянуті питання побудови репрезентативної навчальної вибірки, запропоновано використання системи нейронечіткого висновку (Adaptive Neural-Fuzzy Interference System - ANFIS) в якості експертної системи для визначення точності прогнозу шляхом оцінки різнорідних релевантних даних.

Проаналізовані основні складові трафіка, визначено, що у загальному випадку мережний трафік можна представити виразом:

(1)

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

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

, (2)

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

, (3)

та вейвлет коефіціенти обраховуються за формулою

. (4)

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

низькочастотна (рівень апроксимації ), що відображає тренд-сезонні зміни;

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

високочастотні (рівні деталізації ) відносяться до випадкової компоненти.

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

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

час навчання ШНМ каскадно корельованої архітектури набагато меньший порівняно з алгоритмами прямого та зворотного поширення помилки, що дозволяє використовувати систему для аналізу більших об'ємів даних;

підсумкова структура ШНМ не містить надлишкових елементів і є достатньою для апроксимації вхідних даних з заданою точністю;

у випадку зміни параметрів трафіка або його флуктуацій ШНМ легко адаптує власну структуру в процесі донавчання.

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

при ініціації системи в якості еталонного обираємо часовий ряд (ЧР), що представляє часову залежність трафіка за добу;

для кожної нової вибірки обчислюємо значення метрики (евклідова відстань );

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

вибираємо з бази даних (БД) ЧР, метрика яких відрізняється від знайденої на задану величину;

формуємо кластер зі знайдених даних, у центрі якого розміщуємо досліджуваний ЧР;

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

перенавчаємо цільову ШНМ.

При формуванні навчальної вибірки для ШНМ даним, що подаються на вхід мережі, ставимо у відповідність бажане значення на виході ШНМ. Аналітично алгоритм формування навчальної вибірки можна записати наступним чином:

(5)

де - кількість входів ШНМ, - розмір навчальної вибірки.

Блок-схема вдосконаленої методики прогнозування телекомунікаційного трафіка представлена на рис. 2.

Рис. 2. Блок-схема методики прогнозування

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

Результат прогнозування часової залежності трафіка вузла PDSN мережі CDMA-450 представлено на рис. 3.

Рис. 3. Результат прогнозування трафіка вузла PDSN мережі CDMA-450

Прогнозування трафіка вузла PDSN мережі CDMA-450 виконувалось з використанням інформації про нормовану завнатженість зовнішнього інтерфесу вузла, що надходила з інтервалом в 15 хвилин. Середньоквадратична похибка прогнозування склала 5,367%, що дозволяє зробити висновок про високу точність прогнозу отриманого при використані запропонованої методики.

Залежність середньої помилки прогнозування та структури ШНМ каскадно-корельованої архітектури від кількості входів ШНМ представлені в табл. 1.

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

Вейвлет коефіцієнти	Кількість входів
	12	16	20	24	28	32
C5	0,0162/36	0,0151/11	0,0169/12	0,0177/19	0,0171/21	0,0191/35
W1	0,0281/63	0,0334/67	0,0279/61	0,0288/57	0,0264/58	0,0271/58
W2	0,0274/64	0,0269/59	0,0258/60	0,0274/59	0,0263/62	0,027/59
W3	0,0293/68	0,0291/59	0,0281/57	0,0533/54	0,0306/58	0,0829/102
W4	0,1205/49	0,0656/49	0,0423/49	0,0347/53	0,0372/92	0,04/42
W5	0,0980/42	0,0841/43	0,081/40	0,0698/45	0,1094/44	0,0732/102

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

Застосування методики дозволяє виконувати прогнозування часової залежності трафіка з прийнятною точністю для використання отриманих результатів в задачі маршрутизації. Розроблено програмне забезпечення, що реалізує представлену методику прогнозування з використанням мови програмування perl та бібліотеки Fast Artificial Neural Network Library (http://leenissen.dk/fann/), що розповсюджується за ліцензією GNU GPL.

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

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

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

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

визначаємо різницю прогнозованих значень трафіка з'єднувальних ліній та їх пропускних здатностей : ,;

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

для формування матриці доступних з'єднань, визначаємо лінії пропускна здатність яких перевищує значення прогнозованого трафіка ():

.

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

Для кожного елементу за допомогою алгоритму Дейкстри знаходимо маршрут з мінімальною метрикою.

Визначаємо максимальний потік через знайдений маршрут як

.

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

Повертаємось в пункт 1 за наявності нерозподіленого трафіка в і доступної пропускної здатності ліній для вузла .

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

Вартість виділення смуги пропускання:

, (6)

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

Вартість комутації:

, (7)

де - питома вартість комутації в мережі.

Вартість передачі сигнальної інформації:

, (8)

де - питома вартість передачі сигнальної інформації в мережі.

Вартість затримки передачі пакетів:

, (9)

де - питома вартість затримки передачі пакетів в мережі.

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

, (10)

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

 (11)

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

. (12)

Коефіцієнти узгодження ділянок кусково-лінійної функції, визначаються за рекурентною формулою:

. (13)

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



Рис.4. Графік штрафної функції заданого вигляду

Таким чином, вартісна функція тракту визначається у вигляді зваженої суми:

(14)

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

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

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

З графу видаляємо всі з'єднання, для яких та формуємо робочий граф .

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

Обраховуємо вартість знайдених маршрутів, застосовуючи вираз (14), та обираємо в якості оптимального маршрут з найменшою вартістю.

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

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

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

Четвертий розділ присвячений дослідженню аспектів побудови централізованої системи маршрутизації в мережах з технологією IP/MPLS та проведенню імітаційного моделювання запропонованих алгоритмів маршрутизації за допомогою симуляторів мережі.

Проведений аналіз існуючих архітектурних схем побудови централізованих систем маршрутизації. Сформована структурна схема централізованої системи маршрутизації зображена на рис. 5.



Рис. 5.Структурна схема централізованої системи маршрутизації

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

Проаналізовані існуючі програмні пакети для симуляції мереж з підтримкою протоколу MPLS та його розширень MPLS-TE. Визначена структура імітаційної моделі для проведення тестування. Для генерування трафіка застосований алгоритм з випадковим зміщенням проміжних точок (Random Midpoint Displacement, RMD), що дозволяє формувати трафік з регульованими фрактальними властивостями.

Проведено імітаційне моделювання запропонованих методики прогнозування та алгоритмів маршрутизації з використанням стимулятора мережі NS2. Результати імітаційного моделювання представлено на рис. 6-8.



Рис. 6. Пікове завантаження з'єднувальних ліній

Рис. 7. Кількість запитів на повторне встановлення LSP

Рис. 8. Кількість відмов по запитах на встановлення з'єднання

Узагальнені дані за отриманими результатами імітаційного моделювання представлено в табл. 2.

Таблиця 2. Оцінка результатів імітаційного моделювання

Тип тесту	Алгоритм
	OSPF	MIRA	TEAM	Alg#1*	Alg#2*
Пікове завантаження з'єднувальних ліній (-3%)	0,95	0,74	0,7	0,72	0,68
Кількість запитів на повторне встановлення LSP (-17%)	420	198	168	147	139
Кількість відмов по запитах на встановлення з'єднання (-20%)	0,23	0,117	0,109	0,084	0,112

* - Alg#1 - алгоритм маршрутизації за максимальним потоком та Alg#2 - вдосконалений евристичний алгоритм маршрутизації.

За результатами імітаційного моделювання можна зробити висновок, що застосування запропонованих алгоритмів маршрутизації в мережах з технологією IP/MPLS дозволило отримати виграш на 3-20% за такими показниками як пікова завантаженість з'єднувальних ліній та кількість відмов по запитах на встановлення з'єднання, та відповідно покращити якість послуг, що надаються.

Висновки

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

При цьому отримані такі основні теоретичні та науково-практичні результати.

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

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

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

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

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

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

Проведено імітаційне моделювання запропонованої методики прогнозування та алгоритмів маршрутизації в мережі IP/MPLS з використанням симулятора мережі NS2, яке показало їх переваги на 3-20% за такими показниками як пікова завантаженість з'єднувальних ліній та кількість відмов по запитах на встановлення з'єднання в порівнянні з відомими алгоритмами маршрутизації.

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

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

1. Артеменко М.Е., Касымов Р.Р. Интеллектуальная система управления трафиком в сетях мобильной связи //Электроника и связь. Темат. вып. “Проблемы электроники”. - 2008. -Ч. 1.-С. 223-226.

2. Артеменко М.Е, Касымов Р.Р. Использование вейвлетов для повышения качества прогноза телекоммуникационного трафика // Зв'язок. -2010. № 3.- С. 57-60.

3. Артеменко М.Е., Касымов Р.Р. Прогнозирование временных рядов для задач управления с использованием аппарата нейронных сетей и вейвлет анализа // Холодильна техніка і технологія.-2010. № 3.- С. 74-76.

4. Артеменко М.Е., Касымов Р.Р. Алгоритм маршрутизации телетрафика по максимальному потоку с использованием прогнозирующих моделей // Вісник ДУІКТ. -2010. № 3.-С. 231-235

5. Касимов Р.Р. Алгоритм маршрутизації в мережі MPLS з використанням прогнозуючих моделей// Зв'язок. -2010. № 4.-С. 63-68.

6. Артеменко М.Е., Касымов Р.Р. Система динамической оптимизации с нейросетевым предсказанием объема трафика /Збірник тез доповідей ІV Міжнародної науково-технічної конференції студентства і молоді “Світ інформації та телекомунікацій - 2008”.-К.: ДУІКТ, 2008 -С. 64-65.

7. Артеменко М.Е., Касымов Р.Р. Система управления мультисервисной сетью с динамической оптимизацией и прогнозированием объема трафика /Тези доповідей ІV Міжнародної науково-технічної конференції “Сучасні інформаційно-комунікаційні технології (COMINFO'2008)”.-К.: ДУІКТ, 2008 -С. 120-121.

8. Артеменко М.Е., Касымов Р.Р. Использование вейвлетов для повышения качества прогноза /Збірник тез доповідей V Міжнародної науково-технічної конференції студентства і молоді “Світ інформації та телекомунікацій - 2009”. - К.: ДУІКТ, 2009 -С. 43-44.

9. Артеменко М.Е., Касымов Р.Р. Прогнозирование трафика в телекоммуникационной сети /Збірник тез доповідей VІ Міжнародної науково-технічної конференції студентства і молоді “Світ інформації та телекомунікацій - 2009”.-К.: ДУІКТ, 2009 -С. 34-35.

10. Артеменко М.Е., Касымов Р.Р. Система краткосрочного прогнозирования телекоммуникационного трафика на базе каскадной нейронной сети. Науково-технічний симпозіум «Нові технології в телекомунікаціях»": Збірник тез. К.: ДУІКТ, 2010. - С. 38-39.

11. Артеменко М.Ю., Касимов Р.Р. Розробка алгоритму QoS маршрутизації в мережах MPLS /Матеріали VІІ наукової конференції «Сучасні тенденції розвитку технологій в інфокомунікаціях та освіті» (Матеріали конференції).-К.: ДУІКТ, 2010.-С. 63-68.

12. Артеменко М.Ю., Касимов Р.Р. Вибір оптимального місцезнаходження центру керування мережею на базі векторного синтезу та теорії графів / Тези доповідей VI Наукової конференції «Сучасні тенденції розвитку технологій в інфокомунікаціях та освіті».-К: ДУІКТ, 2010.-С. 95-96.

13. Артеменко М.Е., Касымов Р.Р. Алгоритм маршрутизации телетрафика по максимальному потоку с использованием прогнозирующих моделей /Збірник тез доповідей МНПК «Актуальні питання регулювання у сфері телекомунікацій та користування радіочастотним ресурсом», 2010.-С. 11-12.

14. Касимов Р.Р. Алгоритм багатошляхової маршрутизації в мережі MPLS з використанням прогнозуючих моделей /Тези доповідей VІ Міжнародної науково-технічної конференції “Сучасні інформаційно-комунікаційні технології (COMINFO'2010)”.-К.: ДУІКТ, 2010 -С. 120-121.

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

...