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

АНДРУШКО ДМИТРО ВОЛОДИМИРОВИЧ

УДК 621.391

Оптимізація методів багатошляхової маршрутизації та розподілу ресурсів в мережах MPLS-TE

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

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

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

Харків – 2007

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

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

Науковий керівник: кандидат технічних наук, доцент Мельнікова Любов Іванівна, Харківський національний університет радіоелектроніки, доцент кафедри телекомунікаційних систем.

Офіційни опоненти: доктор технічних наук, професор Краснобаєв Віктор Анатолійович, Харківський національний технічний університет сільського господарства ім. Петра Василенка, професор кафедри автоматизації та комп’ютерних технологій;

кандидат технічних наук, доцент Руккас Кирило Маркович, Харківський національний університет ім. В.Н. Каразіна, доцент кафедри теоретичної та прикладної інформатики.

Захист відбудеться 28 листопада 2007 р. о 1430 годині на засіданні спеціалізованої вченої ради Д 64.820.01 в Українській державній академії залізничного транспорту Міністерства транспорту та зв’язку України за адресою: 65050, м. Харків, майдан Фейєрбаха, 7.

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

Автореферат розісланий 19 жовтня 2007 р.

Вчений секретар

спеціалізованої вченої ради Д 64.820.01

кандидат технічних наук, доцент Приходько С.І.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Епоха інформаційного співтовариства, яка почалася в середині 70-х років минулого сторіччя, вивела на перший план питання уніфікованого обміну інформацією. Еволюціонуючи від незалежних телефонних мереж та мереж обміну даними між користувачами, наприкінці минулого століття постала необхідність створення єдиної мережної архітектури, яка реалізує три види послуг: передачу мови, відео та даних. Для реалізації багатьох послуг на базі універсального транспорту комітетом ITU-T була запропонована концепція мереж наступного покоління (NGN). Концепція NGN дозволяє надати вільний доступ до послуг і підтримує мобільність клієнтів, саме це дозволяє організувати цілісне та повсюдне надання сервісів користувачам. У якості уніфікованої транспортної технології для побудови NGN використовується протокол IP.

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідження з теми дисертаційної роботи пов'язані з виконанням плану держбюджетних НДР. Так, матеріали дисертаційної роботи використані в НДР кафедри ТКС Г.Р. №0103U004932 і науково-дослідних роботах проведених ХДРНТЦ ТЗІ.

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

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

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

3. Розробка методу оптимального розподілу ресурсів по множині незалежних шляхів у мережах MPLS-TE для стаціонарного режиму роботи та методу розподілу інформаційних потоків для мереж MPLS-TE у критичних режимах роботи.

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

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

Предмет дослідження: мережа NGN в умовах нестаціонарного трафіку.

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

Наукова новизна отриманих результатів:

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

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

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

Практичне значення отриманих результатів.

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

1. Забезпечено більш раціональне використання ресурсів у мережах MPLS-TE, що дозволяє підвищити якість обслуговування інформаційних потоків і збільшити на 15-20% обсяг переданого трафіку.

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

3. Експериментально визначені часові та ймовірнісні характеристики функціонування мережі, які визначають поточний режим роботи.

4. Методи, алгоритми та програмні засоби моделювання розподілу інформаційних потоків у мережі використовуються в навчальному процесі ХНУРЭ в курсі: “Керування й маршрутизація в ТКС”.

Особистий внесок здобувача. Автор самостійно виконав основні теоретичні дослідження та провів імітаційне моделювання. При цьому в роботах, виконаних у співавторстві, авторові належать розробка алгоритму визначення оптимальної кількості шляхів [2,6,8], проведення експериментальних досліджень та статистична обробка результатів експерименту [4], рекурсивна процедура розподілу ресурсів [5,7], огляд графових та потокових математичних моделей багатошляхової маршрутизації на основі математичного програмування [13].

Апробація результатів дисертації. Результати досліджень, які включені в дисертацію, доповідалися на міжнародній конференції “ДУІКТ” у 2006р. у м. Києві на 2-ому міжнародному радіоелектронному форумі “Прикладна радіоелектроніка. Стан і перспективи розвитку” МРФ-2005 у м.Харкові, міжнародна конференція “Теорія й техніка передачі, прийому та обробки інформації” в 2005, 2006 рр. м. Харків, а також на міжнародному молодіжному форумі “Радіоелектроніка й молодь в XXI столітті” в 2003, 2004, 2005 та 2006рр. у м.Харкові.

Публікації. За матеріалами дисертації опубліковано 13 робіт, у тому числі 6 робіт у спеціалізованих виданнях ВАК України [1,2,3,4,5,13]. Крім того, матеріали досліджень опубліковані в збірниках праць науково-технічних конференцій [6,7,8,9,10,11,12].

Структура й обсяг дисертації. Дисертація складається з вступу, чотирьох розділів та висновків. Загальний обсяг дисертаційної роботи становить 152 сторінки, з їх 135 сторінок основного тексту, 30 сторінок з рисунками, 7 сторінок з таблицями. Список використаних джерел на 9 сторінках включає 98 найменувань.

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ

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

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

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

, (1)

де - вартість пересилання пакетів по шляху mk. Однак технології маршрутизації по найкоротшому шляху не дозволяють повністю використати доступні мережні ресурси, урахувати обмеження системної політики, а також вимоги до диференційованого обслуговування трафіку, що приводить до неоптимального завантаження мережі та перевантаженню окремих ділянок. У зв'язку з цим в останні кілька років з'явилися нові класи методів маршрутизації: QoS-маршрутизація, Policy-based маршрутизація, маршрутизація з обмеженнями і т.п. З появою концепції мереж наступного покоління були сформульовані нові вимоги до транспортних мереж та обслуговування трафіку. Відповідно до рекомендації комітету ITU-T Y.2001, у якості транспорту повинна використовуватися технологія, у якій розмежовані функції керування та пересилання даних. Цим вимогам задовольняє технологія з мультипротокольною комутацією міток. Проведений аналіз показав, що мережний інжиніринг спрямований на рішення задач оптимізації використання мережних ресурсів. Прогресивним вважається два напрямки рішення цих задач:

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

- методи розподілу навантаження по множині шляхів.

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

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

Рис. 1. - Класифікація математичних моделей маршрутизації

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

, (2)

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

, (3)

де – локальна величина дерева найкоротших шляхів від вузла до вузла . Тоді усунення петель досягається виконанням наступних умов:

, ; (4)

, (5)

де – припустима відстань при обчисленні множини .

При досягненні рівностей

, (6)

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

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

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

, (7)

при , ; (8)

при , ; (9)

; ; . (10)

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

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

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

У третьому розділі розроблена математична процедура оптимальної багатошляхової маршрутизації для рішення завдання трафик інжинірингу в мережах MPLS-TE.

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

Рис. 2 - Структура процедури оптимальної багатошляхової маршрутизації

Особливістю мереж MPLS-TE, є те, що тунель є незалежним найкоротшим шляхом, обраним по максимуму доступної для резервування пропускної здатності. Під незалежним, мається на увазі те, що ресурси, запитані для створення даного тунелю, будуть зарезервовані для обслуговування трафіку тільки цього тунелю. Для маршрутизації обирається множина незалежних найкоротших шляхів (рис. 3), яка може бути використана для пересилання пакетів. Після знаходження найкоротшого маршруту, він виключається з графа. Далі виконується наступний пошук найкоротшого шляху на підграфі, з якого було виключено знайдений шлях. Ця процедура повторюється рекурсивно, доти, поки в мережі існують шляхи від вузла i до вузла j. У результаті рекурсивного виконання алгоритму

Рис. 3 - Приклад розрахунку множини незалежних шляхів

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

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

, (11)

де - потік по мультишляху ij, - мінімальна пропускна здатність незалежного шляху, l, n – суміжні вузли на мультишляху ij, M – множина вузлів, що становлять мультишлях ij, N – множина вершин графа мережі. Отримана множина маршрутів дозволяє максимізувати сумарний потік, який можна передати й домогтися рівномірного завантаження мережі.

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

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

, (12)

де m - номер шляху, - вартість (затримка) пересилання по шляху ij, - максимальний потік по шляху ij, n – число незалежних шляхів у заданій мережі.

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

, (13)

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

У проведеному експерименті ваги критеріїв приймалися рівними 0,5. Для кожного з розглянутих графів, завдання оптимізації вирішувалося при різних зв'язностях. У кожному експерименті зв’язність мережі змінювалася від 10% до 100% відносно кількості вузлів у мережі.

Для перевірки запропонованої методики було проведено математичне моделювання. На рис. 4 а-б, наведені криві для графів розміром 50 і 100

Рис. 4 - Рішення задачі багатокритеріальної оптимізації для графа розмірністю 50 (а) і 100 (б) вузлів

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

, (14)

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

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

(15)

при наступних обмеженнях:

(16)

(17)

(18)

, (19)

де - величина потоку, спрямованого по i-му шляху, , Q – потік, що надходить у мережу, - максимальний потік по i-му шляху, - ранг j-го шляху потоку Q , .

Для перевірки запропонованої процедури було проведено імітаційне моделювання для ділянки мережі, у якому є 5 незалежних найкоротших шляхів від джерела до одержувача з використанням пакета Matlab 6.5. У якості моделі навантаження у вузлі s використовувалося джерело трафіку з нормальним розподілом і М.О., рівним 10. Для аналізу запропонованого алгоритму, у вузлі s проводився розподіл потоку(рис. 5 а-б).

Рис. 5 - Розподіл навантаження по шляхах без оптимізації (а) та з оптимізацією (б)

без процедур оптимізації та із застосуванням оптимізації На рис. 6-а представлене середнє значення величини потоку по i-му шляху. Як видно, у випадку оптимального розподілу навантаження, середнє завантаження шляху становить 52% (рис. 6 а-б), а максимальне значення завантаження становить 58%. На відміну від цього, при використанні розподілу навантаження без оптимізації, кілька шляхів завантажуються повністю, при цьому інші простоюють (6 а-б).

а) б)

Рис. 6 – Середнє значення потоку по шляху (а) і значення параметра

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

, (20)

де S – зв’язність мережі, n – кількість вузлів, - час виконання елементарної операції процесором маршрутизатора. Таким чином, пропоновану процедуру можливо використовувати в мережах великого розміру із числом вузлів N=100 і вище, при цьому навіть при зв’язності S=50% час рішення не перевищує припустимий (50мс). Аналіз процедури показав, що використання пропонованого алгоритму дозволяє істотно знизити навантаження на окремі ділянки мережі та провести оптимізацію навантаження, розподіливши трафік по оптимальній кількості шляхів. Як показало імітаційне моделювання, в окремих випадках використання пропонованої багатошляхової схеми маршрутизації дозволяє знизити загальне навантаження на 40% на деякі шляхи завдяки перерозподілу трафіку.

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

Для дослідження особливостей критичних режимів роботи мережі, був проведений натурний експеримент, на базі устаткування компанії Сisco Systems. У ході експерименту вимірювалися основні мережні характеристики - втрати та затримки пакетів, у випадку нестабільного режиму роботи мережі. Результати експерименту наведені на рис. 7-8.

На рис. 7-8 по осі абсцис відкладене значення затримки фізичної лінії, уведеної для імітації нестабільної роботи. Значне збільшення імовірності втрати на ділянці 2мкс - 4мкс, пов'язане з погіршенням характеристик фізичного рівня. З погляду кінцевого устаткування цей канал зв'язку буде працездатним, однак, з огляду на значні втрати в ньому (80%-90% при затримці 4мкс) виконувати передачу інформації по ньому не можливо.

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

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

Рис. 7 - Ймовірності втрат пакетів: розмір пакета 1024 байт (а), 512 байт (б)

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

Рис. 8 - Абсолютні затримки пакетів у мережі, що моделювалася: розмір пакета 1024 байт (а), 512 байт (б).

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

Значення наведеного навантаження кожного шляху визначається:

, (21)

де - пропускна здатність каналу зв'язку між вузлами i і j, - відповідне навантаження в момент часу t . Нехай - заданий потік інформації з вузла i у вузол j. Якщо між вузлами i та j існує прямий зв'язок, то наведений потік інформації з вузла i у вузол j визначається відношенням

(22)

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

, (23)

де n – число вузлів у мережі, .

У початковий k-й момент часу наведений потік з i-го вузла в j-й може бути представлений

(24)

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

(25)

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

(26)

(27)

Як показують результати лабораторного моделювання, цей формалізований метод також несе частку суб'єктивізму через (27). Тому на практиці можна обійтися більше простим методом обчислення (25). У наступний (k+1)-й момент часу здійснюється перехід процедури на наступний крок, при цьому враховується значення наведеного потоку на попередньому кроці. Таким чином, приходимо до рекурсивної процедури оцінки стану:

(28)

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

Рис. 9 - Збіжність алгоритму для мереж розміром 5, 10, 15 вузлів

Для мережі з 5 вершин, процедура перерозподілу трафіку збігається на 5 кроці. У випадку мережі з 10 вершин збіжність спостерігається на 9 кроці. У випадку графа з 15 вершин збіжність спостерігається на 11 кроці. Отже, можна зробити вивід про те, що час збіжності запропонованої процедури лінійно залежить від кількості вершин.

Для пропонованої процедури була проведена оцінка обчислювальної складності. На рис. 10 наведені криві залежності часу рішення задачі розподілу ресурсів від розмірності мережі для математичної моделі Галлагера й пропонованої евристичної процедури. Показано, що час перерозподілу потоків, у випадку використання запропонованої процедури може бути визначеним вираженням:

, (29)

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

Рис. 10 - Залежність часу рішення завдання від розмірності мережі: 1 - модель Галлагера, 2 - пропонована евристична процедура ре маршрутизації

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

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

ВИСНОВКИ

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

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

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

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

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

5. Враховуючи обмеження на час перерозподілу потоків (50мс), для вирішення задачі маршрутизації у критичному режимі була обґрунтована необхідність використування процедур, які мають низьку обчислювальну складність.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Андрушко Д.В. Перспективы использования технологии MPLS/GMPLS для построения широкополосных сетей // Радиотехника, Всеукр. Межвед. Научн.-Техн. Сб. 2004. Вып. 138; с. 11—14.

2. Мельникова Л.И., Андрушко Д.В., Горяева С.Н. Многопутевая маршрутизация с использованием оптимального алгоритма распределения сетевых ресурсов для сетей MPLS-TE// Радиотехника, Всеукр. Межвед. Научн.-Техн. Сб. 2006. Вып. 144; с. 35-38

3. Андрушко Д.В., Методика определения оптимального числа маршрутов для решения задачи трафик инжиниринга в сетях MPLS-TE // Радиотехника, Всеукр. Межвед. Научн.-Техн. Сб. 2007. Вып. 148; с. 72—76

4. Мельникова Л.И., Андрушко Д.В., Демченко М.Н., Результаты экспериментальных исследований сетевых параметров передачи IP трафика в технологии MPLS-TE // Радиотехника, Всеукр. Межвед. Научн.-Техн. Сб. 2006. Вып. 144; с. 131-135.

5. Андрушко Д.В., Фурсова О.Б., Андрушко Ю.В. Оптимизация перераспределения ресурсов в сетях MPLS-TE при быстрой ремаршрутизации // Восточно-европейский журнал передовых технологий. Вып. 1/2 (25), с. 15-19. 2007

6. Андрушко Д.В., Андрушко Ю.В., Алгоритм поиска множества независимых кратчайших путей для сетей MPLS-TE // Тез. Докл. Первой международной научной конференции “Глобальные информационные системы. Проблемы и тенденции развития” 3-6 октября 2006г., с. 358-359.

7. Андрушко Д.В., Фурсова О.Б., Андрушко Ю.В., Оптимизация перераспределения ресурсов в сетях MPLS-TE при быстрой ремаршрутизации // Тез. докл. 11-го Международного молодёжного форума “Радиоэлектроника и молодёжь в ХХI веке” 10-12 апреля 2007 г., Харьков. с. 86.

8. Андрушко Д.В., Фурсова О.Б., Андрушко Ю.В., Экспериментальные исследования сетевых параметров при различных режимах работы сети // Тез. докл. Первой научно-техн. конференции, “Проблемы телекоммуникаций” 25-27 апреля 2007, Киев. с. 196-197.

9. Андрушко Д.В., Модели качества обслуживания в сетях с мультипротокольной коммутацией меток // Тез. докл. 9-го Международного молодёжного форума “Радиоэлектроника и молодёжь в ХХI веке” 10-12 апреля 2005 г. Харьков. с. 82.

10. Андрушко Д.В., Предоставление гарантированных сервисов в Best-effort сетях // Сб. Тезисов докладов по материалам международной научной конференции “Теория и техника передачи, приема и обработки информации” 2003 г. Харьков. с. 4.

11. Андрушко Д.В., Перспективы использования технологии MPLS для построения широкополосных IP-сетей // Материалы 8-го Международного молодёжного форума “Радиоэлектроника и молодёжь в XXI веке”, 10-12 апреля 2004, Харьков. с. 65.

12. Андрушко Д.В., Исследование эффективности использования дисциплин управления очередями заявок при совместной передаче речи и данных в IP-сетях // Материалы 7-го Международного молодёжного форума “Радиоэлектроника и молодёжь в XXI веке”, 10-12 апреля 2003, Харьков. с. 110.

13. Поповский В.В., Лемешко А.В., Мельникова Л.И., Андрушко Д.В., Обзор и сравнительный анализ основных моделей и алгоритмов многопутевой маршрутизации в мультисервисных телекоммуникационных сетях // Прикладная радиоэлектроника, 2005; т. 4, выпуск 4, с.372-382.

АНОТАЦІЯ

Андрушко Д.В. Оптимізація методів багатошляхової маршрутизації та розподілу ресурсів у мережах MPLS-TE. - Рукопис.

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

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

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

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

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

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

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

АННОТАЦИЯ

Андрушко Д.В. Оптимизация методов многопутевой маршрутизации и распределения ресурсов в сетях MPLS-TE. – Рукопись.

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

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

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

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

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

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

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

abstract

Andrushko D.V. Optimization of multipath routing and resource distribution methods for MPLS-TE networks. - Manuscript.

Ph.D. thesis by speciality 05.12.02 - telecommunication systems and networks. Kharkov National University of Radio Electronics, Kharkov, 2007.

The Ph.D. thesis is devoted to optimization of multipath routing and resource distribution methods for MPLS-TE networks for efficiency of network resources usage increasing.

The classification of existent mathematical models of routing completed. Analysis shown, it is impossible resolve traffic engineering task using only single class of models. Moreover, it is necessary take into account current network mode.

A method of multipath routing was developed for stationary network mode on the basis of graph and streaming models. A multicriterion task provides a way for obtaining optimal number of paths for traffic serving. It was shown usage of the proposed methods increase traffic quality serving on 15-20% on networks up to
100 nodes.

On real equipment an experiment for investigation of critical network modes was completed. It was shown that it is necessary to use reroute procedures with low calculation complexity and which provides traffic rerouting with delays less than 50 ms.

For critical network mode heuristical procedure of traffic rerouting was proposed. The completed analysis shown N-step convergence of proposed model.

Key words: next generation networks, traffic engineering, multipath routing, resource distribution, multiprotocol label switching networks.

Підп. до друку 02.10.07. Формат 60х841/16. Спосіб друку – ризографія.

Умов. друк. арк. 1,2. Тираж 100 прим.

Зам. № 2-797. Ціна договірна.

ХНУРЕ, 61166, Харків, просп. Леніна, 14

Віддруковано в навчально-науковому
видавничо-поліграфічному центрі ХНУРЕ
Харків, просп. Леніна, 14