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

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

АШРАФ АБДЕЛЬ-КАРІМ ХІЛАЛ АБУ-АІН

(Йорданія)

УДК 681.513

СИНТЕЗ СТРУКТУРИ ГЛОБАЛЬНИХ КОМП’ЮТЕРНИХ МЕРЕЖ З ТЕХНОЛОГІЄЮ MPLS

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

АВТОРЕФЕРАТ

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

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

КИЇВ 2007

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

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

м. Київ

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

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

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

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

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

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

Теленик Сергій Федорович,

НТУУ “КПІ”, завідувач кафедри автоматики та управління в технічних системах

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

Печурін Микола Капітонович,

Національний авіаційний університет, професор

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

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

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

Захист відбудеться “11” червня 2007 року о 16.00 годині на засіданні спеціалізованої вченої ради Д 26.002.02 у НТУУ “КПІ” (м. Київ, пр. Перемоги,37, корп.18, ауд.306).

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

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

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

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

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

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

Актуальність теми. Внаслідок значного розширення мультимедійних додатків і телеконференцій, що вимагають все більш високих швидкостей передачі й більш широкої смуги пропускання, виникла необхідність у створенні нової технології, яка б надала єдиний транспортний механізм поверх найрізноманітніших технологій, таких як Ethernet, Frame Relay, IP і забезпечувала високошвидкісну передачу інформації з необхідною якістю обслуговування (Quality of Service - QoS). Відомі комунікаційні технології такі, як ІP, Ethernet, Token Rіng не дозволяють забезпечити задану якість обслуговування та необхідний рівень QoS. Такою технологією є технологія багатопротокольної комутації міток MPLS (Multіprotocol Label Swіtchіng), що прийшла на зміну технології ATM.

MPLS є універсальним вирішенням проблем забезпечення заданого рівня QoS, вона забезпечує високу швидкість передачі, масштабованість, контроль, оптимізацію розподілення трафіку, а також маршрутизацію. Важливою задачею, що виникає при проектуванні мереж MPLS є задача синтезу оптимальної структури мережі при обмеженнях на встановлені показники якості QoS обслуговування для різних класів потоків (Class of Servіce - СoS). Задачі структурного синтезу мереж розглядалися в роботах зарубіжних вчених Л. Клейнрока, Дж. Мартіна, Г. Френка, М. Шварца, а також вітчизняних вчених В.Г. Лазарева, П.І. Братухіна, Ю. П. Зайченко, Г.Ф. Янбиха та інших.

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

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалась згідно з планами наукових досліджень кафедри прикладної математики в рамках держбюджетних тем “Моделювання, аналіз та проектування комп’ютерних та телекомунікаційних мереж вузівського та міжвузівського рівней на основі перспективних мережевих технологій”, номер державної реєстрації 0100U002050, “Розробка моделей, алгоритмів та програмного комплексу для аналізу та оптимізації комп’ютерних мереж з технологією MPLS”, номер державної реєстрації 0107U002219.

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

Мета і задачі досліджень.

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

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

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

2. Постановка і формалізація задачі структурного синтезу мереж з технологією MPLS при обмеженнях на задані значення показників якості (середню затримку і частку втрачених пакетів).

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

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

Об’єктом дослідження є мережі з технологією MPLS.

Предметом дослідження є моделі та алгоритми структурного синтезу мереж з технологією MPLS.

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

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

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

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

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

4. Розробка алгоритму структурного синтезу мережі з технологією MPLS, який на відміну від відомих, враховує наявність заданого остова мережі (backbone).

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

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

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

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

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

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

В роботі [1]: розроблено метод синтезу структури комп’ютерних мереж з технологію MPLS, який відрізняється від відомих – урахуванням різних класів сервісу та введеням показників якості обслуговування.

В роботі [3]: проведено експериментальні дослідження ефективності методу структурного синтезу мереж з технологією MPLS при обмеженнях на показники якості обслуговування.

В роботі [4]: автором розроблено генетичний алгоритм структурного синтезу мереж та проведено його досліджения.

В роботі [5]: автором запропоновано метод структурного синтезу мереж з технологію MPLS та розміщення маршрутизаторів при заданій структурі опорної мережі.

В роботі [6]: автором проведено дослідження алгоритму оптимізації структури мереж MPLS при обмеженнях на середній час доставки.

В роботах [7,9]: автором досліджено алгоритм структурного синтезу мереж при обмеженнях на показники якості обслуговування та живучості мереж.

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

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

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

2) Першій науково-практичній конференції “Математичне та імітаційне модулювання – МОДС ‘2006”, Київ, 2006.

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

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

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

Структура й об’єм дисертації. Дисертація складається із вступу, 4-х розділів, додатку та списку літератури з 169 найменувань, займає 132 сторінки тексту й включає 51 малюнок і 10 таблиць.

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

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

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

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

Задано множину вузлів мережі - маршрутизаторів MPLS (так званих LSR – Label Switching Routers), їх розміщення по території регіону, набір пропускних спроможностей (ПС) каналів зв’язку, із яких ведеться синтез та їх питомі вартості на одиницю довжини, визначені класи обслуговування CoS (Class of Service) , відомі матриці вхідних потоків для всіх класів ;, де – інтенсивність потоку k-го класу, якій потрібно передавати із вузла i до вузла j за одиницю часу (Кбіт/с).

Крім того, введені обмеження на показники якості QoS для кожного класу k у вигляді обмеження на середню затримку і на частку втрачених пакетів (packet loss rate) .

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

Побудуємо математичну модель даної задачі синтезу.

Потрібно знайти:

У роботі Ю.П. Зайченко та Ахмеда А.М. Шарадка для потоку k-го класу, при умовах, що вхідні потоки Пуасоновські, обслуговування класів потоків відбувається з відносними пріоритетами в порядку зменшення номеру класу (тобто) , а час обслуговування розподілений експоненціально при заданому наборі ПС каналів і розподіленню потоків було отримано відповідний вираз для середньої затримки потоку -го класу.

Ймовірність того, що не відбудеться втрати пакетів -го класу ні в одному з каналів мережі, буде дорівнювати: .

А ймовірність (частка втрачених комірок) -го класу дорівнюватиме:

де визначається співвідношенням (6):

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

Потрібно знайти такі ПС і розподілення потоків, при яких.

Дана задача синтезу відноситься до класу комбінаторних задач дискретного програмування і являється NP-повною задачею. Тому для її розв’язку в роботі пропонується генетичний метод структурного синтезу.

Метод складається із двох етапів: попереднього та основного.

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

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

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

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

(k+1) ітерація.

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

1. З ймовірністю, обернено пропорційною, вибираємо структуру для модифікації.

У якості вибираємо: . (8)

2. Для структури визначаємо множину КЗ-претендентів на видалення за умовами збереження заданої зв'язності і множину КЗ-претендентів на введення.

3. Для КЗ множини) обчислюємо показник неефективності:

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

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

5. Порівняння. Якщо, (10)

то покладемо і записуємо структуру замість в популяцію П. І кінець ітерації). Інакше на крок 6.

6. Аналізуємо множину КЗ -, для яких розраховуємо показники ефективності від введення в структуру КЗ

7. З ймовірністю вибираємо з множини і вводимо його в структуру . Отримуємо структуру

8. Для структури розв’язуємо задачу ВПС РП, використовуючи алгоритм ВПС РП і знаходимо нові ПС, а також вартість нової мережі:.

9. Перевіряємо умову: якщо, то фіксуємо структуру, записуємо структуру замість в поточну популяцію П. Кінець ітерації.

10. В іншому випадку відновлюємо колишню структуру і видаляємо КЗ із списку претендентів: та із структури.

11. Перевіряємо умову Якщо ТАК, то на крок 7 і вибираємо новий канал із списку претендентів на введення.

12. Відновлюємо початкову структуру і видаляємо із списку претендентів на видалення.

Перевірка умови? Якщо ТАК, то на крок 1, відновивши множину.

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

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

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

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

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

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

Спочатку оцінимо витрати на рішення задачі РП. Витрати на одноразовий розподіл потоків матриці - складають .

З урахуванням повторного перерозподілу потоків при забезпеченні QоS - верхня межа об'єму додаткового обсягу обчислень -де б [0,1] – частка тих вимог, які потребують перерозподілу.

Тоді верхня межа загальних витрат на рішення задачі РП складе:

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

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

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

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

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

Її постановка наступна. Задано множину вузлів мережі , початкову структуру (остов) мережі, де - вузли остова, - канали зв’язку остова мережі. Задано матриці вимог вхідних потоків для всіх класів сервісу, а також набір пропускних спроможностей та їх питомих вартостей.

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

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

В дисертації запропоновано алгоритм синтезу структури мережі при заданому остові (backbone), який є розвитком загального алгоритму структурного синтезу. У вищенаведеній постановці задачі структурного синтезу припускалось, що місця розміщення маршрутизаторів мережі LSR задані, і потрібно було синтезувати мережу мінімальної вартості при обмеженнях на задані значення QоS. У більш загальному випадку, розміщення маршрутизаторів не задане, а відомо лише розміщення абонентів мережі – джерел і споживачів інформації, і потрібно одночасно знайти розміщення LSR, вибрати їх типи, а також синтезувати магістральну мережу між ними найкращим чином.

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

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

Математична модель даної задачі має наступний вигляд:

Введемо наступні змінні:

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

1 етап. Розміщення LSR і синтез абонентської мережі.

1. Знаходження прив'язок всіх абонентів до відповідних LSR в пункті і оцінка ПС абонентських каналів .

2.Оцінка економічної доцільності встановлення LSR в пункті і переведення неекономічних LSR в розряд абонентських пунктів (АП).

3. Переприв’язка незадіяних вільних АП до сусідніх найближчх LSR і оцінка ефекту від їх підключення.

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

2 етап. Синтез початкової магістральної мережі і оцінка її характеристик.

3 етап. Оптимізація структури магістральної мережі при обмеженнях на встановлені значення QоS.

В дисертації наведено детальний опис розробленого метода.

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

Експерименти проводились на мережі, яка включала в себе 15 вузлів (мала мережа) рис1 и рис2, а також на мережі з 25 вузлів (середня мережа) рис4. При цьому використовувалося три класи сервісів. Допустимі затримки трафіка: клас1 - 0,00005 с., клас 2 - 0.0015 с., клас 3 - 0.003 с.

У першій серії експериментів варіювалися інтенсивності вхідних потоків різних класів шляхом зміни коефіцієнта пропорційності k. Для цього базові матриці вимог для різних класів H помножувались на коефіцієнт k. При цьому величина k варіювалася в діапазоні 0.2-2. Нижче приведені деякі з отриманих результатів.

Як видно із приведених результатів, вартість мережі зростає по закону близькому до лінійного в залежності від об’ємів вхідних трафіків. Цей характер залежності легко пояснити. Чим більші інтенсивності вхідних потоків, тим більшими повинні бути пропусні спроможності каналів і тим дорожчою буде мережа. На рис.3 наведено також вартість мережі заданої структури (при к=1), для якої оптимізовані пропускні спроможності та розподіл потоків, відповідна крива проходить вище за криву з оптимізованою структурою, що дає змогу оцінити ефективність запропонованого методу синтезу структури мережі.

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

Отримані результати для трафіка категорії класу сервісу 2 приведено в таблиці 1.

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

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

Синтезовану оптимальну структуру мережі для k=1 приведено на рис.4. ЇЇ вартість становить 27906,52 тис. у.о.

Рис.4. Оптимізована структура мережі для 25 вузлів

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

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

1. Побудови найкоротшого дерева Ісау-Вільямса.

2. Побудови найкоротшого циклу (задача комівояжера).

3. Побудови комбінованим алгоритмом – найкоротше дерево + найкоротший цикл.

Результати експериментів наведено в таблиці 3 (в тис. у.о.).

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

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

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

Аналіз отриманих структур дозволяє зробити висновок про стійкість базової структури мережі при варіюванні вхідних потоків в широкому діапазоні (к=0,2-2), що свідчить про високу якість отримуваних рішень.

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

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

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

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

Відповідний графік залежності приводиться на рис.5.

Рис.5. Залежність вартості оптимізованої структури від інтенсивності для різних методів синтезу

Висновки

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

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

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

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

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

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

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

6. Проведено порівняльний аналіз запропонованого методу структурного синтезу мереж з відомим, що дозволяє оцінити його ефективність. В результаті оптимізації структури вартість мережі знижується в середньому по множині експериментів на (10- 20) %.

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

1. Ю.П. Зайченко, А.С. Аникиев, Мохаммедреза Моссавари, Ашраф Абдель-Карим Хилал Абу-Аин. Синтез структуры глобальних компьютерных сетей с технологией MPLS при ограничениях на показатели качества и живучести // Электроника и связь.- 2006.- № 2. - с. 68-71.- автору належить розробка алгоритму синтезу структури комп’ютерних мереж з технологію MPLS.

2. Ашраф Абдель-Карим Хилал Абу-Аин. Структурная оптимизация компьютерных сетей с технологией MPLS при ограничениях на показатели качества обслуживания // Электроника и связь.- 2006.- №5. - с. 71-74.

3. Зайченко Ю.П., Ашраф Абдель-Карим Хилал Абу-Аин. Исследования алгоритма структурной оптимизации сетей MPLS при ограничениях // Вісник національного технічного університету України „КПІ”, сер. Інформатика управління та обчислювальна техніка. 2006.- Вип. 45.с.180-188. - автором проведено експериментальні дослідження ефективності алгоритму структурного синтезу мереж MPLS.

4. Зайченко Е.Ю., Зайченко Ю.П., Ашраф Абдель-Карим Хилал Абу-Аин. Структурный синтез компьютерных сетей с технологией MPLS // Системні дослідження та інформаційні технології. 2006. №4.– с. 65-70 - автором проведено розробку та дослідження генетичного алгоритму структурного синтезу мереж. – автором запропоновано метод структурного синтезу мереж та розміщення маршрутизаторів при заданій структурі опорної мережі.

5. Зайченко Ю.П., Ашраф Абдель-Карим Хилал Абу-Аин. Синтез структуры сети с технологией MPLS с размещением маршрутизаторов LRS и заданной структуре опорной сети // Электроника и связь.- 2007.- №1.– с. 65-70.

6. Зайченко Ю.П., Ашраф Абдель-Карим Хилал Абу-Аин. Оптимизация структуры компьютерных сетей с технологией MPLS при ограничениях на показатели качества обслуживания // Тези доповідей Першої науково-практичної конференції “Математичне та імітаційне моделювання систем МОДС ‘2006”. – с. 96. – автором проведено дослідження алгоритму оптимізації структури мереж MPLS при обмеженнях на середній час доставки.

7. Зайченко Ю.П., Е.Ю. Зайченко, Мохаммадреза Моссавари, Ашраф Абдель-Карим Хилал Абу-Аин. Оптимизация структуры корпоративных сетей с технологией MPLS по показателям качества обслуживания и живучести // Труди Міжнародної наукової конференції „Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій” (18-21 травня 2006р., Євпаторія, Крим). – с. 30. - автором досліджено алгоритм структурного синтезу мереж при обмеженнях на показники якості обслуговування та живучості мереж.

8. Зайченко Ю.П., Ашраф Абдель-Карим Хилал Абу-Аин. Оптимизация структуры компьютерных сетей с технологией MPLS // Труды IV–й международной научно-практической конференции “Современные информационные технологиив экономике и управлении предприятиями, программами и проектами”(Харьков, ХАИ, 2006).- с. 48-49 – автором проведено дослідження алгоритму структурного синтезу мереж при додаткових обмеженнях.

9. Зайченко Ю.П., Зайченко Е.Ю., Аникиев А.С., Мохаммедреза Моссавари, Ашраф Абдель-Карим Хилал Абу-Аин. Синтез структуры глобальных компьютерных сетей с технологией MPLS при ограничениях на показатели качества // Труди VІІІ – й Міжнародної науково-технічній конференції „Системний аналіз та інформаційні технології” (13-16 вересня 2006р., м. Київ). – с.77-81. – автором проведено експериментальні дослідження алгоритму структурного синтезу мереж при обмеженнях на показники якості обслуговування.

Анотації

Ашраф Абдель–Карім Хілал Абу–Аін. Синтез структури глобальних комп'ютерних мереж з технологією MPLS.- Рукопис.

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

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

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

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

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

Ключові слова: мережі MPLS, структурний синтез, генетичний алгоритм, показники якості (QoS).

Ашраф Абдель–Карим Хилал Абу–Аин. Синтез структуры глобальных компьютерных систем с технологией MPLS.- Рукопись.

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

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

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

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

Метод состоит из двух этапов: предварительного и основного. На предварительном этапе генерируется начальная структура сети заданной связансти. На основном этапе, состоящем из конечного числа однотипных итераций, осуществляется оптимизация текущей структуры. При этом используются идеи генетического метода оптимизации. Создается популяция из N структур. На текущей итерации случайным образом из популяции выбирается одна из структур . Используя полученные критерии предпочтительности, каналы – претенденты на удаление и ввод ранжируются. Выбирается канал – претендент на удаление и претендент на ввод и осуществляется процедура замены ветвей (каналов).

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

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

Этот метод состоит из трех этапов.

1 этап – размещение LSR и синтез абонентской сети.

2 этап – расчёт матриц требований входящих потков, синтез начальной структуры магистральной сети связи.

3 этап – оптимизация структуры магистральной сети при ограничениях на установленные значения QoS.

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

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

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

В ходе экспериментов варьировались интенсивности входящих потоков и исследована чувствительность критерия стоимость сети и вариации интенсивности. В результате анализа полученных структур после оптимизации сделан вывод об устойчивости базовой структуры сети (backbone) при вариации интенсивности входящих потоков в широком диапазоне ().

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

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

Для оценки эффективности предложенного генетического метода структурного синтеза проведены его сравнительные экспериментальные исследования с методом замены ветвей. В целом, как показывают многочисленные проведенные эксперименты, в результате оптимизации стоимость снижается в среднем на 10 - 20%.

Ключевые слова: сети с технологией MPLS, структурный синтез, генетический алгоритм, показатели качества (QoS).

Ashraf Abdel-Karim Helal Abu-Ein. Global computer networks structural synthesis with MPLS technology – manuscript. The dissertation for Ph.D. degree on specialty 05.13.13 – computers, systems and networks. – National Technical University of Ukraine “Kiev Polytechnic Institute”, Kiev, 2007.

The dissertation is dedicated to elaboration and investigations of methods and algorithms of structural synthesis of MPLS Computer networks.

The problem of MPLS networks structural synthesis by cost criterion under the constraints on established QoS values – mean packets delay and packets loss ratio was formulated.

The method of MPLS networks structure synthesis was elaborated which enables to optimize network structure by cost criterion under constraints on given QoS values. The method utilizes the ideas of genetic optimization. The method of MPLS networks structural synthesis was also suggested, which allows to find optimal network structure and location of MPLS routers (LSR).

The algorithm of MPLS networks structure synthesis with the given initial backbone network was also elaborated. The suggested algorithms were implemented and software kit was designed.

The experimental investigations of the suggested algorithms of MPLS networks structural synthesis were carried out and the efficiency of the suggested algorithms in comparison with known “branches add and delete” method was performed.

Key words: MPLS networks, structural synthesis, genetic algorithm, quality of service (QoS).