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

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

ЗАЙЧЕНКО ОЛЕНА ЮРІЇВНА

УДК 681.513

АНАЛІЗ ТА ОПТИМІЗАЦІЯ ПОКАЗНИКІВ ЯКОСТІ

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

Спеціальність 05.13.06 – Автоматизовані системи управління

та прогресивні інформаційні технології

АВТОРЕФЕРАТ

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

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

Київ 2005

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

Роботу виконано в навчально-науковому комплексі “Інститут прікладного системного аналізу” Національного технічного університету України “Київський політехнічний інстітут”

Науковий консультант - | доктор технічних наук, професор

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

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

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

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

заслужений діяч науки і техніки України

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

Інститут проблем реєстрації інформації НАН України, заступник директора

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

Літвінов Віталій Васильович

Інститут проблем математичних машин та систем НАН України, завідувач відділу спеціалізованих обчіслювальних систем

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

Томашевський Валентин Миколайович,

Національний технічний університет України “Київський політехнічний інститут”,

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

Провідна установа: | Інститут кібернетики ім.. В.М. Глушкова НАН України м. Київ, відділ теорії математичних машин та систем:

Захіст відбудеться 4 липня 2005 р. о 15:00 на засіданні спеціалізованої вченої ради Д26.002.03 в Національному технічному університеті України “Київський політехнічний інститут” за адресою: 03056, Київ, просп. Перемоги 37, корп. №35, ауд. №006

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

Автореферат розісланий 1 червня 2005р.

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

д.т.н., професор Новіков О.М.

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

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

Головною метою цієї технології є розробка уніфікованих методів та засобів для передачі різних видів інформації – зображень, аудіоінформації, мультимедійної інформації та даних на понадвисоких швидкостях. Застосування прогресивних середовищ передачі, зокрема оптоволоконних ліній зв’язку, а також ячейок (cells) уніфікованого формату дозволяє досягнути в каналі швидкості 155,52 Мбіт/с, 622,08 та 2488 Мбіт/с.

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

Технологія АТМ є основою для побудови цифрових мереж інтегрального обслуговування (ЦМІО).

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

- CBR (constant bit rate) – передача з постійною швидкістю відео та аудіоінформації;

- VBR (variable bit rate) – передача із змінною швидкістю скомпресованої відео та аудіоінформації;

- ABR (available bit rate) – передача із доступною швидкістю файлів даних;

UBR (unspecified bit rate) – передача із невстановленою швидкістю даних електронної пошти, служби новин, тощо.

Важливою особливістю технології АТМ є її здатність забезпечити необхідний рівень якості обслуговування при передачі інформації. З цією метою встановлено такі показники якості обслуговування (Quality of Service), які використовуються при оцінці якості передачі по каналам різних типів (категорій) трафіку:

- середня затримка в передачі ячейок – Cell Transfer Delay (CTD);

- варіація величини затримки передачі – Cell Delay Variance (CDV);

- частка (ймовірність) втрачених ячейок – Cell Loss Ratio (CLR).

При передачі встановлюються різні значення показників якості для різних категорій сервісу (CBR, VBR, ABR), найбільш жорсткі значення цих показників встановлюються для трафіка CBR, що є найбільш приоритетним. Зокрема величина затримки для передачі відео та аудіоінформації не повинна перевищувати 50 мс, а ймовірність втрати ячейок не більше 0,51%. Спочатку технологія АТМ була розроблена для глобальних мереж, але згодом вона стала все частіше використовуватися і в корпоративних та локальних мережах.

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

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

Оскільки мережі АТМ суттєво відрізняються від звичайних мереж передачі даних, зокрема наявністю різних категорій трафіка (CBR, VBR, ABR та UBR), а також набором показників (CTD, CDV та CLR) то неможливо безпосередньо використовувати моделі та методи аналізу та синтезу, розроблені для традиційних мереж передачі та обробки даних. Це обумовлює необхідність створення нових моделей для аналізу характеристик мереж АТМ, а також синтезу їхньої структури, які б враховували специфіку мереж АТМ, наявність різних категорій трафіку (CBR, VBR, ABR) та встановлених для них різних значень (CTD, CDV, CLR).

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

Зв’язок з науковими програмами, планами, темами. Робота виконувалась згідно з планами наукових досліджень НТУУ “КПІ”, а саме, держбюджетною темою №2464(2000-2002 рр.) “Моделювання, аналіз та проектування комп’ютерних та телекомунікаційних мереж вузівського та міжвузівського рівнів на основі перспективних технологій”, рег. №0100V002050, а також держбюджетною темою №2605(2003-2004 рр.) “Розробка методів та алгоритмів керування трафіком в телекомунікаційних мережах АТМ”, рег. №0103V000144. Участь автора в цих науково-дослідних темах полягала в розробці теоретичних основ проектування мереж, створенні моделей, методів і алгоритмів аналізу та синтезу структур мереж, дослідженні різних методів управління трафіком ABR в мережах АТМ на основі імітаційного моделювання.

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

1) побудова аналітичних моделей для оцінки показників якості () CTD та CLR в мережах АТМ для категорій сервісу CBR, VBR та ABR;

2) вибір оптимальних пропускних спроможностей (ВПС) для різних категорій сервісу при обмеженнях на встановлені показники якості ();оптимальний розподіл потоків для трафіків CBR, VBR та ABR та комбінована задача оптимального вибору пропускних спроможностей та розподілу потоків CBR, VBR та ABR при обмеженнях на встановлені показники якості ;

3) задача знаходження максимального багатопродуктового потоку для трафіків CBR, VBR та ABR в мережах АТМ;

4) розробка методології аналізу та оптимізації живучості мереж АТМ на основі запропонованих показників живучості, що враховують специфіку відповідних категорій (CBR, VBR та ABR);

5) задача синтезу структури мереж АТМ за критерієм вартості при обмеженнях на встановлені значення показників ;

6) динамічні задачі структурного синтезу мереж АТМ, що розвиваються;

7) створення інструментального програмного комплексу для аналізу функціональних характеристик та синтезу структури комп’ютерних мереж АТМ, що реалізує запропоновані методи.

Об’єктом досліджень в роботі є глобальні та корпоративні мережі з технологією АТМ.

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

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

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

Наукові результати, отримані автором, полягають у нижчезазначеному:

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

2) Отримано аналітичні моделі для оцінки показників якості: середній час затримки ячейок (CTD) та ймовірність втрати ячейок (CLR) для категорій сервісу CBR, VBR та ABR в залежності від інтенсивностей вхідних потоків та пропускних спроможностей каналів. Ці моделі є передумовою для постановки і вирішення задач дисертації.

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

4) Сформульовано та досліджено задачу оптимального розподілення потоків для трафіків CBR, VBR та ABR за критеріями CLR та CTD та запропоновано новий метод її розв’язання, який дозволяє для мереж із заданою структурою та пропускними спроможностями (ПС) каналів знайти оптимальний розподіл потоків трафіків CBR, VBR та ABR.

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

6) Вперше сформульовано задачу оцінки показників живучості мереж АТМ та розроблено метод аналізу показників живучості для трафіків CBR, VBR та ABR. Метод використовує запропоновані в роботі показники живучості мереж АТМ і дає можливість аналізувати та оптимізувати мережі за показниками живучості..

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

8) Сформульовано задачу оптимального синтезу структури мереж АТМ за критерієм собівартості при обмеженнях на встановлені значення показників ,і розроблено ефективний генетичний алгоритм синтезу, який дозволяє оптимізувати структуру мережі АТМ при обмеженнях на показники якості для різних категорій сервісу, та проведені його дослідження.

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

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

11) Розроблено імітаційну модель корпоративної мереді АТМ і проведено імітаційне моделювання з різними методами управління трафіком, в результаті якого вибрано раціональний метод управління трафіком та управління буферами в комутаторах.

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

Практичне значення наукових результатів дисертації полягає в тому, що в результаті запропонованих в роботі моделей, методів та алгоритмів створені теоретичні основи для аналізу та оптимізації характеристик та структур комп’ютерних мереж з технологією АТМ, розроблено інструментальний програмний комплекс “АТМ NetBuilder” для проектування глобальних та корпоративних мереж АТМ.

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

1) здійснювати оптимальний вибір пропускних спроможностей каналів зв’язку для мереж із заданою структурою та вхідними потоками CBR, VBR та ABR;

2) оптимально розподіляти потоки трафіків CBR, VBR та ABR в мережі АТМ за критеріями CTD та CLR;

3) знаходити одночасно оптимальні пропускні спроможності та розподілення потоків по каналах зв’язку;

4) аналізувати показники живучості комп’ютерних мереж;

5) знаходити оптимальну структуру комп’ютерної мережі АТМ за критерієм вартості при обмеженнях на показники якості та живучості мереж;

6) оптимальним чином вибирати комунікаційне обладнання мереж АТМ, зокрема типи комутаторів та маршрутизаторів та місця їх розташування.

7) знаходити оптимальний план розвитку структури мереж АТМ при обмеженнях на капітальні витрати на створення мережі по окремих етапах.

В цілому використання створених моделей, алгоритмів та інструментального програмного комплексу (ПК) дозволяє суттєво скоротити час на проектування мереж АТМ, значно знизити капітальні витрати на проекти мереж АТМ за рахунок оптимізації проектних рішень.

Розроблений ПК “АТМ NetBuilder” було використано в проекті розвитку корпоративної мережі НТУУ “КПІ”. В результаті були вибрані типи комутаторів АТМ, місця їх розташування, а також оптимізовано загальну структуру мережі.

Програмний комплекс було використано для проектування структури перспективної комп’ютерної мережі на оптоволоконних каналах для автоматизованої системи “Експрес-УЗм” АО “Укрзалізниці”, що дозволило суттєво скоротити капітальні витрати на побудову корпоративної мережі.

Теоретичні результати дисертації склали основу нового розділу “мережі АТМ” курсу “Комп’ютерні мережі”, а програмний комплекс Net Builder широко використовується в циклі лабораторних робіт з цього курсу в ННК “ІПСА”

Особистий внесок здобувача. В роботах, опублікованих в співавторстві, здобувачу належать: [3]- досліджено умови оптимальності потоку та запропоновані показники живучості мереж, [4] - розроблено алгоритми аналізу живучості та оптимізації характеристик мереж, [5] - запропоновано алгоритм оптимізації мереж по показникам живучості, [10]- виконано дослідження алгоритмів оптимізації характеристик та синтезу структур глобальних мереж, [12] - виконано постановку задачі та розроблено алгоритм розміщення концентраторів, [13] – проведено дослідження методів керування трафіком на основі зворотніх зв’язків, [14] - запропоновано алгоритми аналізу показників якості мереж з технологією АТМ, [17] - виконано аналіз методів управління трафіком ABR “ rate- based”, [19]- запропоновано алгоритм знаходження максимального потоку, [27] - розроблено постановку задачі та алгоритм синтезу структури мережі з комутаторами, [30]- - запропоновано метод аналізу живучості регіональних мереж та проведено його дослідження.

Апробація результатів роботи. Головні наукові та практичні результати в цілому апробовані на міжнародних та національних конференціях, зокрема “Международной конференции по информационным системам и сетям “МКИСИС-96” (С-Петербург, 1996), п’ятій українській конференції з автоматичного управління “Автоматика-98” (Київ, 1998), шостій українській конференції “Автоматика-99” (Харків, 1999), на Міжнародній конференції з управління “Автоматика-2000” (Львів, 2000), на Міжнародній конференції з управління “Автоматика-2001” (Одеса, 2001), на Другому міжнародному конгресі “Розвиток інформаційного суспільства в Україні” (Київ – 2001) (Конгрес – 2001, Київ – 2001), на Міжнародній конференції “Автоматика-2002” (Донецьк, 2002), на міжнародних конференціях “Автоматика-2003” (Севастополь, 2003) та “ Автоматика-2004”( Киів,2004)..

Публікації. За результатами дисертаційної роботи опубліковано 30 праць, з них: монографій – 2, статей в наукових журналах – 21, матеріалів конференцій 7.

У фахових виданнях опубліковано 21 роботу, з яких 11 написано без співавторів..

Структура і обсяг дисертації. Дисертаційна робота викладена на 267 сторінках тексту, ілюстрована рисунками і таблицями на 36 сторінках. Робота складається з вступу, 5 глав, висновків, двох додатків на 10 сторінках, та списку літератури, що включає 136 найменувань і розміщений на 14 сторінках.

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

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

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

На основі апарату систем та мереж масового обслуговування в роботі отримані такі аналітичні моделі для оцінки :

, (1)

, (2)

– пропускна спроможність КЗ, виділена під трафік CBR, – число базових цифрових каналів (64 кбіт/с), виділених під трафік CBR у локальній мережі ; – потік трафіка CBR у КЗ , N – розмір буфера ячейок трафіка CBR, – нормуючий множник.

Розглянемо показники якості трафіків VBR і ABR, що використовують загальну смугу, причому трафік VBR є більш пріоритетним. Відповідно до роботи [6], середні затримки в КЗ для трафіка VBR:

, (3)

для трафіка ABR:

, (4)

і нарешті, величини середніх затримок у мережі АТМ у цілому, усереднені по всіх парах вузлів такі:

, (5)

, (6)

де – величина потоку (трафіка) у каналі категорії VBR, ABR відповідно; , – загальний розмір зовнішнього потоку типу VBR, ABR у мережі АТМ відповідно.

На основі отриманих аналітичних моделей для оцінки показників якості () в дисертації сформульовано та вирішуються наступні задачі аналізу та оптимізації характеристик мереж АТМ:

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

2) оптимального розподілу потоків в мережі (РП);

3) комбінована задача ВПС РП;

4) аналізу показників живучості комп’ютерних мереж.

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

Постановка задачі

Задана структура мережі АТМ у вигляді графа , де – вузли мережі (комутатори АТМ) та – множина дуг (каналів зв’язку). Маємо можливий набір пропускних здатностей (швидкостей передачі) каналів зв’язку , з яких здійснюється вибір, зауважимо, що для мереж АТМ ці швидкості кратні базовій швидкості цифрового каналу 64 Кбіт/с, або каналу – 1,544 Мбіт/с. Відомі також питомі вартості каналів різної пропускної спроможності . Тоді вартість каналу зв’язку довжиною та швидкістю передачі дорівнює .

Нехай також задана матриця вимог в передачі трафіка CBR, де – інтенсивність потоку, який необхідно передати від вузла в вузол (Мбіт/с). Крім того, нехай при заданих віртуальних шляхах передачі трафіка між усіма вузлами визначені величина потоку CBR в каналі зв’язку та вектор потоку .

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

, (7)

і при цьому виконуватимуться такі обмеження:

a) на допустиму середню ймовірність втрати ячейок – CLR

, (8)

b) на допустиму затримку ячейок CBR, середню по мережі

, (9)

та очевидних умовах ;, .

Тут – заданий рівень (%) втрат ячейок CBR, – задана середня затримка ячейок CBR в мережі.

Опис алгоритму для трафіка CBR

Для розв’язання сформульованої вище задачі застосуємо метод послідовного аналізу та відсіву варіантів (ПАВ).

Метод ПАВ складається з двох процедур W1 та W2

Процедура W1:

Вона полягає в відсіві нижніх значень по обмеженнях.

Відсів для каналу (r,s) значення :

а) по першому обмеженню (8) процедура відсіву виглядає так:

. (10)

Тут відсіються всі нижні значення ;

б) по другому обмеженню (9) процедура відсіву має вигляд:

, (11)

тут також відсіюються всі нижні значення , починаючи з деякого.

Виконавши процедуру W1 з усіма каналами (r,s) отримаємо відсічену знизу підмножину варіантів . Далі переходимо до процедури W2.

Процедура W2:

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

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

Процедура відсіву для каналу (r,s) має вигляд

(12)

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

Крок 1 повторюємо з усіма каналами (r,s). Позначимо отримані підмножини варіантів . Тут можливі такі випадки:1) , де – множина варіантів після виконання процедури W1, тобто відсіву немає. Тоді необхідно перейти на процедуру W2, використовуючи поріг .

2) , та тобто відбулося скорочення числа варіантів. Тоді перехід на процедуру W1.

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

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

Аналогічний алгоритм розроблено для вирішення задачі ВПС для трафіків VBR та ABR [6]. Збіжність алгоритмів ВПС випливає зі збіжності методу ПАВ.

Вибір маршрутів передачі й оптимальний розподіл потоків у мережах з технологією АТМ

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

Постановка задачі

Задано структуру мережі у вигляді орграфа G=(X,E), X={xj}, – множина вузлів мережі – комутаторів; E={(r,s)} – множина каналів зв’язку (дуг), матриці вимог у передачі трафіка VBR , трафіка CBR і трафіка ABR , де інтенсивність потоку ячейок (cell/c), який необхідно передати від вузла i до вузла j. Для CBR, VBR і ABR задані відповідно пропускні спроможності каналів , де – число базових цифрових каналів типу DS0 (=64 Кбит/с) або DS1 (=1,544 Мбит/с), організованих у КЗ (r, s).

Потрібно вибрати такі маршрути передачі і знайти розподіл потоків для трафіку VBR і ABR , при яких забезпечується мінімум імовірності втрати ячейок VBR:

(13)

при обмеженні на середню затримку ячейок VBR:

(14)

і на середню затримку ячейок ABR

, (15)

де , визначаються за формулами (5), (6).

Опис алгоритму

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

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

На третьому етапі робимо розподіл потоків трафіку ABR F(2) з урахуванням знайденого розподілу F(1). Нарешті, на четвертому етапі проводимо оптимізацію РП F(1) і F(2) за критерієм (13) при обмеженнях (14), (15) [6].

1 етап

На цьому етапі проводимо попередній розподіл потоку F(1).

k-а ітерація

Нехай уже проведені (k-1) ітерації і знайдено розподіл потоку .

1. Знаходимо умовну метрику для всіх дуг:

, .

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

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

. (16)

Якщо умова (16) виконується, то на крок 4, інакше на крок 5.

4. Розподіляємо потік вимоги по шляху і знаходимо

k = k+1 і на крок 1 наступної ітерації.

5. Якщо (16) не виконується, то знаходимо такий маршрут передачі вимоги з ik до jk , для якого

.

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

2 етап

Його ціль – побудувати допустимий потік F(1)VBR, що задовольняє обмеженням

. (17)

Перевіряємо умову (17). Якщо вона виконується, то відразу на третій етап, інакше на 1у ітерацію.

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

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

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

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

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

. (18)

Якщо (18) виконується, то на крок 5, інакше stop, задача не розв’язується при заданих ПС каналів {rs}.

5. Відшукуємо вимоги (ik, jk), для яких виконується умова

, (19)

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

6. Вибираємо першу вимогу (i1, j1), для якої виконується умова (19), і перенаправляємо потік вимоги на найкоротший шлях:

(20)

7. Перевіряємо виконання умови . Якщо так, то кінець 2го етапу, інакше і перехід на крок 1 наступної ітерації.

У результаті виконання етапу 2 одержимо допустимий розподіл потоків VBR, що задовольняє умові (17)

3 етап

Ціль третього етапу – розподіл потоків для вимог ABR і обчислення потоків . Для того, щоб при цьому розподілі не порушити обмеження (17), введемо бар’єрну функцію:

, де . (21)

Етап 3 складається з однотипних ітерацій.

Нехай проведено k ітерацій етапу 3 і знайдено розподіл потоків трафіку ABR від перших k вимог, що позначимо .

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

. (22)

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

3. Розподіляємо потік від вимоги :

4. , перехід до наступної ітерації.

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

Позначимо отриманий у результаті потік ABR через .

4 етап

На цьому етапі виконуємо остаточну оптимізацію розподілу трафіків VBR і ABR за критерієм і обмеженнями (14), (15).

Перевіряємо виконання умов:

; (23)

. (24)

Утворимо бар’єрну функцію

, (25)

якщо виконується умова (23) і штрафну функцію, якщо не виконується

. (26)

Введемо аналогічну бар’єрну функцію чи штрафну функцію для трафіку ABR.

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

Зафіксуємо розподіл і переходимо до 2ї частини етапу 4. Тут оптимізуємо розподіл потоку ABR F2 так, щоб при цьому не порушувалося обмеження по потоку VBR.

Аналіз показників живучості мереж із технологією АТМ

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

Однією із задач роботи є створення відповідного інструментарію (апарата) для оцінки живучості комп’ютерних мереж із новою технологією АТМ.

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

Оцінка показників живучості мережі

Отже, нехай – загальна величина потоку трафіка CBR, VBR, ABR відповідно в мережі в цілком безвідмовному стані при заданих обмеженнях на показники .

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

.

Імовірність відмови вузла задається аналогічним виразом.

Будемо оцінювати живучість мережі АТМ комплексним (векторним) показником – величиною максимального потоку трафіків CBR – ; VBR – і ABR – , який можна передати при відмовах її елементів.

Оскільки для трафіка CBR у кожному КС виділяється фіксована смуга (частка загальної ПС), то для нього можна ввести такий показник живучості:

(27)

при умовах (обмеженнях):

, (28)

. (29)

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

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

а) показник . (30)

при умовах

; (31)

; (32)

б) та показник (33)

при умовах, що .

Методика оцінки показників живучості мереж

Опишемо запропоновану в дисертації методику оцінки показників живучості (30)-(33) [9].

1.

2.

(34)

і при обмеженнях, що

; (35)

. (36)

Для цього використовуємо спеціальний алгоритм знаходження максимального потоку (ЗМП) для суміші потоків VBR+ABR. Це робиться таким чином.

Вирішуємо спочатку задачу ЗМП тільки для потоку VBR

при обмеженнях (35) і (36).

Нехай , де ; ; ; ; ; .

3.

і виконуються такі обмеження

Зафіксуємо знайдене рішення і позначимо його через .

4.

(37)

5.

. (38)

При обчисленні показників живучості мережі АТМ багаторазово використовується алгоритм знаходження максимального потоку для трафіка CBR і суміші трафіків VBR і ABR. Нижче розглядається відповідна постановка задачі й алгоритм її вирішення.

Задача знаходження максимального потоку (ЗМП) для трафіка CBR у мережі АТМ

Постановка задачі

Задані: структура мережі , матриця вимог для трафіка CBR; , ПС усіх каналів зв’язку . Припустимо, що відмовив КЗ – у стані . Потрібно визначити такий розподіл потоків у мережі трафіка CBR, при якому максимізується величина сумарного зовнішнього потоку CBR переданого в мережі при обмеженнях на імовірність втрати ячейок і , тобто

(39)

при умовах (28), (29)_ та

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

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

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

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

Теорема 1. Нехай – оптимальний потік, при якому жорстким є обмеження (28), а (29) не є жорстким, тобто , тоді це потік по найкоротших шляхах у метриці

. (40)

Якщо жорстким є обмеження (29), то умовна метрика вибирається так:

. (41)

В дисертації доведено необхідність та достатність умов теореми 1, що встановлює властивість максимального потоку.

Теорема 2. Вимога домінує (тобто ) в оптимальному рішенні тоді і тільки. тоді, коли , де – довжина найкоротшого шляху в одній з метрик (40), (41).

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

Припустимо, що проведено (k-1) ітерацію і розподілено потік від (k-1)-ї вимоги, знайдено розподіл із величиною потоку .

k-а ітерація

1) Розглядаємо вимоги, що залишилися нерозподіленими .

2) Обчислюємо умовну метрику:

. (42)

3) Шукаємо найкоротші шляхи для усіх вимог і знаходимо : .

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

. (43)

5) Перевіряємо умову повного розподілу потоку вимог : якщо ,то вважаємо , інакше і на крок 6.

6) Розподіляємо потік від вимоги і знаходимо новий розподіл потоків:

(44)

7) Перевіряємо виконання обмежень на показники якості (28) та (29). Якщо обидві умови (28) і (29) виконуються, то: . і перехід до наступної ітерації. Інакше, на крок 8.

8) Якщо або , то stop. Поток F(k) – максимальний з величиною .

9) Якщо або , то на крок 10.

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

11) Якщо , то стоп. В іншому випадку, зменшуємо величину потоку останньої вимоги до такого значення , при якому будуть виконуватися обмеження (28) і (29). Тоді і кінець роботи алгоритму. Тобто , згідно з теоремою 1.

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

Структурний синтез глобальних мереж з технологією АТМ за заданими показниками якості обслуговування

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

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

Постановка задачі

Задано: місця розміщення кінцевих користувачів (кінцеві станції АТМ), комутаторів мережі АТМ, матриці вимог у передачі інформації: , , ,

набір пропускних спроможностей КЗ мережі АТМ і їх питомих вартостей на одиницю довжини канала. Потрібно знайти таку структуру мережі , пропускні спроможності всіх КЗ і розподіл усіх потоків трафіків CBR, VBR і ABR, для яких мінімізується загальна вартість мережі при обмеженнях на задані показники якості () різних типів трафіку: , і , і .

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

Математична модель даної задачі синтезу має наступний вид. Знайти таку структуру мережі і пропускні спроможності каналів та розподіл потоків трафіків CBR , VBR _ і ABR _ при яких забезпечується:

, (45)

при умовах

, (46)

, (47)

, (48)

, (49)

, (50)

Потоки , і являють собою багатопродуктові потоки трафіків CBR, VBR і ABR відповідно, сумісні з матрицями , і .

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

1)

2)

Опис алгоритму синтезу

З огляду на багатоекстремальный комбінаторний характер задачі синтезу (45) – (50) для її рішення пропонується генетичний алгоритм глобальної оптимізації, що складається з наступних етапів [8].

Попередній етап.

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

Опис (k+1)-ї ітерації.

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

Випадковим образом, з ймовірностями, обратнопропорційними , вибирається структура .

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

1.

2.

. (51)

3.

4.

, (52)

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

6. Якщо обрано режим , то використовуючи імовірнісний механізм визначаємо з ймовірністю Prs канал, що видаляється з мережі. Одержуємо структуру .

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

6.2. Визначаємо величину критерію , порівнюємо і . Якщо <, то заміняємо структуру на . Покладемо і записуємо в послідовність локально-ефективних структур . У протилежному випадку видаляємо КЗ з множини претендентів на видалення: і знову переходимо на виконання k-ї ітерації.

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

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

Зазначену послідовність кроків на (k+1)-й ітерації повторюємо доти, поки не одержимо нову структуру , для якої буде виконуватися умова локальної оптимізації і на цьому кінець ітерації.

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

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

Синтез корпоративної мережі з комутаторами

Постановка задачі

Задані: корінь дерева (кореневий сегмент ), множина вузлів мережі (абонентських пунктів – АП) {}, координати вузлів обсяги інформації, що генеруються у кожному з них , набір пропускних спроможностей (ПС) каналів зв'язку (КЗ) та їх питомих вартостей , набір типів комутаторів (КМ). Причому характеризується вартістю , числом портів і продуктивністю .

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

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

Потрібно знайти такі , а також структуру мережі , для яких

(53)

при умовах

, (54)

, (55)

, (56)

Якщо , то , (57)

де (54) –