НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ“

КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

АХМЕД А.М. ШАРАДКА

(Йорданія)

УДК 681.513

МЕТОД ОПТИМІЗАЦІЇ РОЗПОДІЛЕННЯ ПОТОКІВ В КОМП'ЮТЕРНИХ МЕРЕЖАХ

З ТЕХНОЛОГІЄЮ MPLS

Спеціальність 05.13.13 – обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

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

Київ 2007

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

Роботу виконано в національному технічному університеті України Київському політехнічному інституті на кафедрі прикладної математики,

м. Київ

Науковий керівник: Доктор технічних наук, професор

Зайченко Юрій Петрович,

Інститут прикладного системного аналізу при НТУУ

КПІ, професор кафедри математичних методів

системного аналізу

Офіційні опоненти: Заслужений діяч науки і техніки України,

Доктор технічних наук, професор

Додонов Олександр Георгійович,

Інститут проблем реєстрації інформації

НАН України, заступник директора

Кандидат технічних наук, доцент,

Немченко Володимир Петрович,

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

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

обчислювальної техніки.

Провідна установа: Інститут кібернетики ім. В.М.Глушкова

НАН України, м.Київ, відділ мікропроцесорної техніки.

Захист відбудеться 11 червня 2007 року о 14.30 годині на засіданні спеціалізованої вченої ради Д 26.002.02 у Національному технічному університеті України “Київський політехнічний інститут”

(м.Київ, пр.Перемоги,37, корп.18, ауд.306).

Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати на адресу: пр. Перемоги, 37, м.Київ 03057, вченому секретарю НТУУ “КПІ”.

З дисертацією можна ознайомитися в бібліотеці Національного технічного університету України “Київський політехнічний інститут”

Автореферат розісланий 11 травня 2007 року

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

Кандидат технічних наук, доцент М.М.Орлова

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

Актуальність теми. До сучасних телекомунікаційних технологій висуваються вимоги передачі різних видів інформації (аудіо, відео і даних) по спільним каналам зв'язку за допомогою уніфікованого транспортного механізму і забезпечення при цьому заданої якості обслуговування (Quality of Service – QоS) – а саме середньої затримки і її варіації та долей втрачених пакетів. Існуючі технології такі, як IP, Ethernet, Frame Relay, Token Ring не в змозі забезпечити необхідну якість обслуговування. Перша технологія, яка дозволила забезпечити задану якість обслуговування стала технологія АТМ (Asynchronous Transfer Mode). В ній вперше були введені різні категорії сервісу і показники якості обслуговування. Проте висока вартість комунікаційного устаткування мереж АТМ, а також жорстке обмеження на розмір переданих блоків даних - комірки 53 байти стримують її подальше застосування в сучасних комп'ютерних мережах.

Тому наприкінці 90-х років було створено нову технологію багатопротокольної комутації міток - MPLS (Multiprotocol Label Switching), вільну від недоліків, властивих технології АТМ. Її відмінними особливостями є:

1) введення різних категорій потоків класів обслуговування (Class of Service);

2) можливість забезпечення заданої якості обслуговування QоS для різних категорій;

3) надання єдиного транспортного механізму для передачі різних видів інформації і нарешті, можливість роботи з різними технологіями і протоколами (Frame Relay, Ethernet, IP, ATM).

Важливими задачами, які доводиться вирішувати в процесі побудови мереж MPLS, є задачі аналізу і оптимізації їх характеристик, і зокрема, задачі розподілення потоків (РП) різних класів по каналах і оптимального вибору пропускних спроможностей каналів зв'язку при обмеженнях на задані показники якості. Вперше ці задачі були сформульовані і розв’язані для звичайних глобальних мереж Л. Клейнроком. Далі вони були розвинені в роботах Френка, Фриша, В.М. Вишнєвського, Ю.П. Зайченко, Г.Ф. Янбиха і др.

Для мереж з технологією АТМ комплекс моделей і алгоритмів аналізу і оптимізації був розроблений в роботах О.Ю. Зайченко. Разом з тим специфіка технології MPLS і зокрема наявність різних класів обслуговування, введення їх пріоритетного обслуговування не дозволяє безпосередньо застосувати відомі методи і алгоритми, розроблені для технології АТМ. Аналіз літератури по технології MPLS показав, що в даний час відсутні методи і алгоритми, що дозволяють розв’язувати задачі оптимізації розподілення потоків в мережах MPLS. Тому розробка і дослідження моделей і алгоритмів аналізу і оптимізації характеристик мереж з технологією MPLS представляє актуальну задачу.

Зв’язок роботи з науковими програмами, планами, темами.

Робота виконувалась згідно з планами наукових досліджень кафедри прикладної математики в рамках держбюджетної теми “Розробка методів та алгоритмів керування трафіком в телекомунікаційних мережах АТМ”, номер державної реєстрації 010U000144 (2003-2004 рр.) та теми “Розробка моделей, алгоритмів та програмного комплексу для аналізу та оптимізації комп’ютерних мереж з технологією MPLS”, номер державної реєстрації 0107U002219 (2006-2007 рр.).

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

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

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

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

2. Постановка і формалізація задачі вибору оптимальних маршрутів і розподілення потоків всіх класів при обмеженнях на задані значения показників якості ? середній час затримки () та частку втрачених пакетів – задача РП.

3. Постановка і формалізація комбінованої задачі оптимального вибору пропускних спроможностей і розподілення потоків (ВПСРП).

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

5. Розробка алгоритму комбінованої задачі ВПСРП, який позволяє одночасно оптимізувати пропускні спроможності каналів зв’язку і знайти розподілення потоків всіх класів.

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

Об'єкт дослідження процеси передачі інформації різних класів в комп'ютерних мережах з технологією MPLS.

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

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

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

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

2. Розроблено метод оптимального розподілу потоків у комп'ютерних мережах MPLS, який дозволяє вибрати маршрути передачі й знайти розподіл потоків різних класів при обмеженнях на задані значення показників якості обслуговування (QoS) - середню затримку й частку втрачених пакетів.

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

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

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

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

Автором отримані наступні результати:

В роботі [1] розроблено математичну модель задачі вибору оптимальних

маршрутів і розподілення потоків (РП) при обмеженнях на задані

показники якості () в мережах MPLS.

В роботі [2] проведено формалізацію комбінованої задачі оптимального вибору

пропускних спроможностей та розподілення потоків (ВПС РП) для

мереж з технологією MPLS.

В роботі [3] розроблено метод розподілення потоків різних класів в мережах з

технологією MPLS.

В роботі [5] автором запропоновано модифікований метод оптимізації

розподілення потоків, в якому враховуються затримки в

маршрутизаторах ().

В роботах [6,7] проведено експериментальні дослідження розроблених алгоритмів РП та ВПСРП, що дозволяють оцінити їхню ефективність

В роботі [8] запропоновано алгоритм оптимізації характеристик мереж при додаткових обмеженнях

В роботі [9] автором проведено дослідження ефективності комбінованого методу ВПСРП.

Апробація результатів роботи

Основні результати роботи були представлені та обговорювались на:

1. VІІ – й Міжнародній науково-технічній конференції “Системний аналіз та інформаційні технології” (28 червня – 2 липня 2005р., м. Київ)

2. Міжнародній науковій конференції “Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій” (18-21 травня 2006р., Євпаторія, Крим).

3. VІІІ – й Міжнародній науково-технічній конференції “Системний аналіз та інформаційні технології” (13-16 вересня 2006р., м. Київ).

4. IV–й Международной научно-практической конференции “Современные информационные технологиив экономике и управлении предприятиями, программами и проектами” (Харьков, ХАИ, 2006).

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

Структура та об’єм дисертації: Дисертація складається із вступу, 4-х розділів, додатку та списку літератури з 161 найменувань, займає 152 сторінок тексту й включає 35 малюнків і 15 таблиць.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

У другому розділі розглядається задача оптимального розподілення потоків в мережах MPLS при обмеженнях на показники якості. В дисертації розглядається задача розподілення потоків різних класів сервісу, яка орієнтована на стаціонарне вхідне навантаження . На основі зібраної інформації від постійних користувачів з зазначенням типу інформації ( аудіо, відео або дані) а також потрібних значень якості обслуговування (QoS), зокрема середньої затримки та бажаної смуги (Мбіт/с) встановлюється клас вхідного потоку і за допомогою розробленого в дисертації метода вирішується задача розподілення потоків. В результаті визначаються оптимальні маршрути передачі. Крім того, визначається максимальна швидкість передачі, яка не повинна бути перевищена джерелом. Між користувачами і мережею встановлюється трафік - контракт (Service Level Agreement), в якому фіксуються узгоджені параметри трафіка. З використанням протокола RSVP резервуються необхідні ресурси маршруту. і на даний сеанс встановлюється тунель від вхідного пограничного маршрутизатора (Border LSR) до вихідного. Вхідний пограничний маршрутизатор керує доступом в мережу і у випадку перевищення дозволеної швидкості відкидає пакети. Тим самим забезпечується стаціонарність вхідного потоку. Ця задача вирішується на етапі оперативного планування роботи мережі MPLS 2-4 рази на добу.

Сформульовано наступну постановку цієї задачі.

Задано мережу у вигляді графа - множина вузлів зв'язку (ВЗ), - множина каналів зв'язку (КЗ), задані пропускні спроможності каналів зв'язку - і матриці вимог в розподіленні потоків всіх класів, де - інтенсивність потоку -го класу, який необхідно передавати з ВЗ у вузол (Кбіт/с).

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

Дану задачу назвемо задачею РП.

У роботі [1] для потоку -го класу приоритету обслуговування і умови, що обслуговування відбувається з відносними приоритетами отримано вираз для - середньої затримки пакетів.

де - сумарна інтенсивність потоку k-го класу, -потік k-го класу в каналі (r,s).

Очевидно для того, щоб дана задача мала змістовний сенс, необхідно, щоб виконувалися наступні відношення нестрогого порядку :

В дисертації розроблено метод розв’язання задачі РП на прикладі потоків К класів. Метод складається з 2К етапів, на кожному з яких розв’язується задача розподілення потоків РП відповідного класу при відповідному обмеженні на Тср,к .

На першому етапі розв’язуємо задачу розподілення потоків класу при обмеженні .

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

k-а ітерація

Нехай проведено (k-1) ітерація і знайдено розподілення потоків. Розглянемо k- ітерацію.

1. Знаходимо умовну метрику: .

2. Вибираємо чергову вимогу з матриці і знаходимо найкоротший шлях в матриці .

3. Перевіряємо можливість передачі вимоги по шляху:

де - резерв по ПС шляху , який визначається згідно формулі (3).

Якщо умова (3) виконується, то розподіляємо потік від вимоги по шляху і знаходимо:

І на крок 1 наступної ітерації. Інакше на крок 4.

4. Шукаємо такий шлях мінімальної довжини з вузла в , для якого виконується умова,

5. Передаємо потік від вимоги і знаходимо новий розподіл потоків:

Вказані ітерації проводимо до повного розподілення потоків вимог класу 1. В результаті отримуємо розподілення потоків РП таке, що.

Переходимо до другого етапу.

На цьому етапі будуємо допустимий потік , який задовольняє обмеженню:

Перш за все перевіряємо умову (4). Якщо вона виконується, то переходимо відразу ж на етап 3. Інакше, на першу ітерацію.

1. Знаходимо умовну метрику:

2. Знаходимо найкоротші шляхи в метриці (5):.

3. Знаходимо потік по найкоротших шляхах в метриці.

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

Якщо умова (6) виконується, то на крок 5, інакше STOP. Задача РП не розв’язна при заданих ПС каналів і матриці ПС .

5. Знаходимо першу вимогу для якої виконується нерівність (7):

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

6. Перевіряємо умову. Якщо ТАК, то кінець другого етапу, інакше і на крок 4, вибираємо наступну вимогу, що задовольняє умові (6).

В результаті обчислення етапу 2 отримуємо допустиме розподілення потоків класу 1, для якого:

На етапі 3 здійснюємо розподілення потоків класу 2, у вільну полосу пропускних спроможностей каналів. Оскільки він виконується аналогічно етапу 1, то його опис опускаємо. Переходимо до етапу 4.

Припустимо, що проведені ітерації етапів 1 та 2, розподілено потоки двох перших класів та знайдено ;

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

Отже, припустимо, що порушене обмеження (10), тоді необхідно оптимізувати розподіл для 2-го класу, причому таким чином, щоб не порушити обмеження (9).

Це робиться наступним чином. Розглянемо задачу: ,

за умови .

Якщо умова (11) не виконується, то стоп, розподілення потоків не може бути покращано, інакше на крок 4.

4. Відшукуємо вимоги () , для яких можливо поліпшити розподілення потоків:

де - віртуальний шлях передачі вимоги, який використовується в поточному розподілі потоків, - найкоротший шлях в метриці, ; - доля спільного трафіка в каналі (), який використовують для передачі інформації між вузлами i та j для потоків F і V – відповідно.

5. Вибираємо першу вимогу (), для якої виконується (12) і намагаємося перенаправити потік вимоги зі шляху на найкоротший шлях

6. Перераховуємо затримку у мережі. Якщо після цього затримка в мережі для трафіка 2-го класу не зменшується, то повертаємо старе значення потоку F2)(k), й ідемо на крок 5 і вибираємо наступну вимогу, для якої виконується умова (12). Інакше ідемо на крок 4.

Повторюємо кроки 4ч6 то того моменту, поки не перестане виконуватись умова (11). Після цього переходимо на крок 7.

Якщо вона виконується, то кінець етапу 4. Переходимо на етап 5, інакше задача не має розвязку.

Отже, нехай, проведені 3 або 4 етапи і розподілені потоки від вимог 1-го та 2-го класів і знайдені.

Мета етапу 5 - розподілити потоки класу 3 згідно матриці так, щоб не порушити при цьому обмеження (9) та (10).

Для цього вирішується задача при обмеженнях (9), (10).

Для вирішення цієї задачі вводимо барєрні функції:

Етап 5 складається з однотипних ітерацій, які аналогічні ітераціям етапу 3.

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

В третьому розділі розглянуто узагальнену задачу оптимального розподілення потоків (РП) в мережах з технологією MPLS при обмеженнях на показники якості обслуговування (QoS), яка відрізняється від попередньої введенням додаткових обмежень на частку втрачених пакетів.

Задано мережу у вигляді графа - множина вузлів зв'язку (ВЗ), - множина каналів зв'язку (КЗ), задані пропускні спроможності каналів зв'язку і матрицї вимог в розподіленні потоків всіх класів, де - інтенсивність потоку k-го класу, який необхідно передавати з вузла у вузол (Кбіт/с).

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

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

Ймовірність втрати пакетів класу в КЗ дорівнює ймовірності стану, коли всі тимчасові канали виділені під потік класу в лінії зв'язку , будуть зайняті та буфер комутатора буде заповнено, і дорівнюватиме:

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

А ймовірність втрачених пакетів -го класу в мережі буде рівна:

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

В дисертації запропоновано метод розв’язання узагальненої задачі РП. Коротко розглянемо його реалізацію на прикладі потоків K класів.

Метод складається з (2K+1) етапів на кожному з яких розв’язується задача РП потоків відповідного класу к по відповідному обмеженню.

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

Етап складається з однотипних ітерацій, на кожній з яких знаходимо розподілення потоків чергової вимоги. Оскільки він співпадає з етапом 1 методу РП, то його опис можна опустити.

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

Він аналогічний етапу 2 базового алгоритму РП і його опис опущено.

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

Якщо (20) виконується, то переходимо до четвертого етапу, інакше на третій етап

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

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

Перша ітерація.

вибираємо з умови.

2. Вибираємо найкоротші шляхи в метриці і знаходимо потік по найкоротших шляхах.

3. Перевіряємо можливість поліпшення розподілення потоку :

Якщо так, то на крок 3, інакше STOP, розподілення потоку не можна покращати і задача РП нерозв’язна.

4. Знаходимо першу вимогу для якої:

де - поточний шлях передачі вимоги () для потоку, - найкоротший шлях для вимоги () у метриці.

5. І перенаправляємо потік вимоги з шляху на шлях і знаходимо нове розподілення потоків:

6. Перевірка умови:

Якщо умова (25) виконується, то кінець етапу 3, інакше на крок 2 наступної ітерації. Кроки 2-4 повторюємо до тих пір, поки умова (25) не почне виконуватися. Якщо після того, як будуть перерозподілені всі вимоги, для яких виконувалась умова (23), умова (25) не почне виконуватись, то СТОП, задача РП нерозв’язна при даних пропускних спроможностях каналів. Інакше переходимо до етапу 4.

Далі переходимо до знаходження розподілення потоку другого класу таким чином, щоб не були порушені обмеження (19) і (20) для потоку . Для цього виконуємо етапи 4, 5 які аналогічні етапам 2 і 3. При цьому, розподілення потоку знаходимо на залишкових ПС каналів, а щоб не порушувалися обмеження (19) і (20) використовуємо бар'єрну або штрафну функції для потоку .

Аналогічним чином проводимо розподілення потоків всіх наступних класів. При цьому використовуємо метрику (21), яка оптимізує розподіл потоку к-го класу з урахуванням обох критеріїв

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

При вирішенні задачі розподілення потоків різних класів при заданих обмеженнях на значения показників якості і може виявитися, що ця задача не має вирішення через недостатні пропускні спроможності КЗ мережі. Тому для забезпечення заданих QoS при заданих матрицях вимог Н(к) всіх класів необхідно вирішувати одночасно задачі вибору оптимальних ПС і розподілення потоків всіх класів (задача ВПСРП).

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

Тому в третьому розділі розглянуто також наступну постановку задачі ВПСРП.

Задана мережа MPLS із структурою, де – множина вузлів зв'язку мережі (ВЗ); – множина каналів зв’язку (КЗ); задано набір пропускних спроможностей і їх питомих вартостей.

Визначено число класів потоків, задано матриці вимог вхідних потоків, де – інтенсивність потоку, який необхідно передавати з ВЗ в (Мбіт/с). Встановлено вимоги по забезпеченню заданих показників якості (QoS) –.

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

В дисертації розроблено метод вирішення задачі ВПСРП. Метод складається з попереднього етапу і скінченного числа однотипних ітерацій.

На попередньому етапі знаходяться початкові ПС каналів зв'язку і початкове розподілення потоків всіх класів, .

Мета подальших ітерацій – оптимізація ВПС і РП по критерію вартості.

Нехай проведено r ітерацій і знайдені ПС, розподілення потоків і вартість мережі.

1. Розв’язуємо задачу РП по критерію використовуючи алгоритм, запропонований в дисертації, і знаходимо новий потік.

2. Розв’язуємо задачу ВПС по критерію для потоку при обмеженнях, і знаходимо нові пропускні спроможності.

3. Обчислюємо величину критерію і перевіряємо умову. Якщо так, то STOP розподілення потоків і ПС – оптимальні, інакше і на крок 1 наступної ітерації.

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

Відповідно до запропонованих алгоритмів були розроблені програми РП і ВПСРП, які увійшли складовою частиною в програмний комплекс “MPLS NetBuilder” і проведені їх експериментальні дослідження. Всі експерименти проводилися на мережі, яка складається з n = 15 вузлів та m = 23 каналів.

В першій серії експериментів вирішувалася задача РП.

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

Наступний експеримент полягав у збільшенні коефіцієнта K2 для передачі трафіка клас_2. Цей трафік має пріоритет 2, отже він розподіляється в вільну полосу каналу, що лишається після трафіка клас_1, і має вищий пріоритет в порівнянні з наступними класами зокрема класом 3. Результати експерименту наведено на рисунках 1, 2.

В результаті отримуємо наступні результати. Пріоритет трафіка клас_2 вищий за пріоритет трафіка клас_3. Це означає, що першим в каналі розподіляємо трафік клас_2, а потім в решту вільної полоси, яка залишилось – трафік класу 3. В результаті отримуємо, що при збільшенні вхідного потоку клас_2 в каналі залишається мало вільної полоси для трафіка клас_3. Тому першим досягає насичення трафік клас_3, що видно з рисунку 2. Характер затримки для трафіка клас_3 подібний до гіперболічної, що підтверджує теоретичні уявлення про поведінку затримки, що описана формулою (2). Затримка по трафіку клас_2 зростає майже лінійно, що також підтверджує формулу (2).

В другій серії експериментів вирішувалась задача ВПСРП і досліджувалась залежність вартості мережі СУ від обмеження на Тср для потоку класу 2.

Відповідні результати наведені в таблиці 1.

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

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

Для оцінки ефективності запропонованого методу РП MPLS було проведено його порівняльні експерименти із методом РП, який розроблено для мереж передачі даних Л. Клейнроком. Оскільки метод РП не розрахований на передачу потоків різних класів приорітету, його було дороблено відповідним чином. Спочатку знаходилось розподілення потоків для класу_1 за критерієм. Далі у залишок пропускної спроможності всіх каналів зв’язку– було розподілено потік класу_2. Потім у полосу каналів, що лишилася, розподілявся потік для класу_3. Проведено експерименти в яких варіювався коефіціент для передачі трафіка класа_2. Відповідні результати для класів 2 та 3 наведено в таблиці 2.

Порівняння результатів свідчить, що для трафіка вищого пріоритету клас_2 значення критерія приблизно однакові для обох методів, проте для трафіка класа_3 (нижчого пріоритету) результати, отримані запропонованим методом, значно кращі--пізніше настає момент насичення для потоку класу_ 3 в порівнянні з алгоритмом РП.

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

Далі було проведено порівняння методу ВПCРП, запропонованого в дисертації, з методом ВПСРП для мереж АТМ. В експериментах варіювався коефіціент пропорційності трафіка k.

Отримані результати – залежність вартості мережі для обох методів наведена на рис 4.

Аналіз отриманих результатів свідчить про переваги запропонованого методу в порівняні з відомим методом ВПСРП АТМ.

Висновки

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

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

Основні наукові результати дисертації полягають у наступному:

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

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

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

4. Запропоновані методи і алгоритми РП і ВПС РП реалізовані в програмному комплексі MPLS і проведено їх експериментальні дослідження. Проведено також їх порівняльний аналіз з відомими методами, розробленими для мереж АТМ, що дало змогу оцінити ефективність запропонованих методів.

Основні результати роботи, відображені в наступних публікаціях

1. Зайченко Ю.П., Ахмед А.М. Шарадка. Задача распределения потоков различных классов в сети с технологией MPLS // Вісник національного технічного університету України „КПІ”, сер. Інформатика управління та обчислювальна техніка. -2005. -Вип.43. С.113-123 – автором запропоновано метод розподілу потоків різних класів в мережах MPLS.

2. Зайченко Ю.П, Ахмед А.М. Шарадка. Анализ и оптимизация характеристик сетей MPLS по заданным показателям качества // Электроника и связь. - 2006. -№2. - С.72-74 – автору належить розробка алгоритму вибору пропускних спроможностей та розподілу потоків при обмеження на значення показників якості.

3. Зайченко Ю.П., Ахмед А.М. Шарадка. Оптимизация характеристик сетей MPLS при дополнительных ограничениях на показатели качества обслуживания // Вісник національного технічного університету України „КПІ”, сер. Інформатика управління та обчислювальна техніка. -2006. -Вип.45. С.189-197 – автором проведено експериментальні дослідження методу розподілу потоків при додаткових обмеженнях на значення показників якості.

4. Ахмед А. М. Шарадка. Обобщенная задача распределения потоков в cетях MPLS и алгоритм её решения // Электроника и связь. - 2006. - №5. - С.75-78. автором розроблено алгоритм розподілу потоків з урахуванням обмежень на середній час доставки та частку втрачених пакетів.

5. Зайченко Ю.П., Ахмед А.М. Шарадка. Оптимизация распределения

потоков в сетях с технологией MPLS с учетом задержки в маршрутизаторах

// Электроника и связь. -2007. -№1. -С.80-83. автором запропоновано модифікований метод оптимізації розподілення потоків, в якому враховуються затримки в маршрутизаторах ().

6. Зайченко Ю.П., Ахмед А.М. Шарадка. Оптимизация распределения потоков в сетях с технологией MPLS // Матеріали VII міжнародної науково-технічної конференції „Системний аналіз та інформаційні технології”, 28 червня-2 липня 2005р. Київ. -2005. -С.119. - автором проведено експериментальні дослідження ефективності алгоритму розподілу потоків в мережах MPLS.

7. Зайченко Ю.П., Ахмед А. М. Шарадка. Оптимизация выбора пропускных

Способностей и распределения потоков и сетях с технологией MPLS Матеріали міжнародної науково-технічної конференції „Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій”15-18 травня 2006 р. Євпаторія, Крим. - С.28 – автором запропоновано алгоритм оптимального вибору пропускних спроможностей та розподілення потоків різних класів.

8. Зайченко Ю.П., Ахмед А.М. Шарадка. Оптимизация характеристик сетей MPLS при дополнительных ограничениях на показатели качества обслуживания// Матеріали міжнародної науково-технічної конференції „Системний аналіз та інформаційні технології”, 13-16 вересня 2006р. Київ. - С.74-76.

9. Зайченко Ю.П., Ахмед А.М. Шарадка. Оптимизация характеристик компьютерных сетей с технологией MPLS // IV – й международной научно-практической конференции Современные информационные технологиив экономике и управлении предприятиями, программами и проектами, Харьков, ХАИ, 2006. - С.46-47 - автором проведено дослідження ефективності комбінованого методу ВПСРП.

Анотації

Ахмед А.М. Шарадка. Метод оптимізації розподілення потоків в комп’ютерних мережах з технологією MPLS. Рукопис.

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

Дисертацію присвячено розробці і дослідженню методів і алгоритмів оптимального розподілення потоків (РП) різних класів сервісу, а також вибору пропускних спроможностей каналів зв'язку (ВПС) в мережах з технологією MPLS.

Сформульовано задачу розподілення потоків різних класів в мережах MPLS при забезпечениі заданих значення показників якості QoS – середньої затримки і частки втрачених пакетів і розроблено ії математичну модель.

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

Сформульовано узагальнену задачу оптимального розподілення потоків різних класів сервісу при обмеженнях на показники якості – середню затримку і частку втрачених пакетів і розроблено алгоритм її розв’язання.

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

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

Ахмед А.М. Шарадка. Метод оптимизации распределения потоков в компьютерных сетях с технологией MPLS.– рукопись.

Диссертация на соискание ученой степени кандидата кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети.– Национальный технический университет Украины ”Киевский политехнический институт”, Киев, 2007.

Диссертация посвящена разработке и исследованию методов и алгоритмов оптимального распределения потоков (РП) различных классов сервиса, а также выбора пропускных способностей каналов связи (ВПС) в сетях с технологией MPLS при ограничениях на установленные значения показателей качества обслуживания (QoS) – среднюю задержку и долю потерянных покетов.

Основная цель разработки – повышение эффективности использования коммуникационных ресурсов сетей с технологией MPLS за счёт оптимизации распределения потоков различных классов при ограничениях на заданные значения показателей качества обслуживания (QоS).

В работе получены аналитические оценки для показателей качества (QoS)сервиса – средней задержки и доли потерянных пакетов в сетях с технологией MPLS для различных классов сервиса.

Сформулирована постановка и разработана математическая модель задачи распределения потоков различных классов в сетях с технологией MPLS при условии обеспеченно заданных значений показателей качества (QoS) – средней задержки и доли потеряных пакетов, отличающаяся от известных учетом специфики технологии MPLS.

Разработан метод РП в компьютерных сетях с технологией MPLS позволяющий выбрать маршруты передачи и найти распределение потоков различных классов сервиса (CoS) при обезпечении средней задержки в доставке пакетов. Метод использует специальную метрику и обеспечивает передачу потоков по кратчайшим путям в данной метрике. Сначала распределяется потоков класса 1 с наивысшим приоритетом по кратчайшим путям в условной метрике .

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

Сформулирована постановка обобщенной задачи РП при ограничении на заданные значения показателей качества и разработан метод ее решения, позволяющий найти оптимальное распределение потоков всех классов при ограничении на заданные значения показателей качества (QoS)- среднюю задержку в доставке и долю потерянных пакетов

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

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

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

Проведены сравнительные эксперементальные исследования предложенного метода РП MPLS с известным методом РП для сетей АТМ. Проводилось также сравнение предложенного метода ВПСРП для сетей MPLS с известным алгоритмом ВПСРП для сетей АТМ. Проведенные эксперименты позволяют оценить эффективность предложенных методов.

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

Применение комплекса повышает эффективность использования коммуникационных ресурсов за счёт принятия оптимальных проектных решений.

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

Ahmed A.M. Sharadqah. Method of optimization of Flows distribution in