Міністерство транспорту та зв’язку України

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

Євсєєва Оксана Юріївна

УДК 621.391

МЕТОДИ АДАПТИВНОЇ МАРШРУТИЗАЦІЇ В ГІБРИДНИХ ТЕЛЕКОМУНІКАЦІЙНИХ МЕРЕЖАХ З ГАРАНТОВАНОЮ ЯКІСТЮ ОБСЛУГОВУВАННЯ

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

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

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

Харків – 2004

Дисертацією

є рукопис

Робота виконана

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

Науковий керівник

кандидат технічних наук Лемешко Олександр Віталійович, старший науковий співробітник Харківського національного університету радіоелектроніки

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

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

кандидат технічних наук, старший науковий співробітник Кучеренко Юрій Федорович, начальник відділу – заступник начальника управління Об’єднаного науково-дослідного інституту Збройних Сил

Провідна

установа Український науково-дослідний інститут зв’язку (УНДІЗ) Державного комітету зв’язку та інформатизації України (м. Київ)

Захист відбудеться “16” грудня 2004 р. о 14 годині на засіданні спеціалізованої вченої ради

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

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

Автореферат розісланий “11” листопада 2004 р.

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

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

к.т.н., доцент М.В. Книгавко

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

Актуальність теми. Ефективність функціонування мультисервісної телекомунікаційної мережі (ТКМ) залежить від великої кількості факторів і визначається протоколами різних рівнів, серед яких важливе місце займають задачі мережного рівня і зокрема задачі маршрутизації. Слід зазначити, що теоретичну основу значної більшості сучасних алгоритмів і протоколів маршрутизації складають неадаптивні або локально адаптивні моделі, наприклад, моделі найкоротшого шляху, що обумовлено відносною простотою їхньої реалізації. Протоколи адаптивної маршрутизації, побудовані на даних моделях, наприклад RIP (Routing Information Protocol), OSPF (Open Shortest Path First), IS-IS (Intermediate System to Intermediate System), PNNI (Private Network to Network Interface), забезпечують розрахунок необхідних маршрутів з адаптацією лише до зміни топології ТКМ. Практика свідчить, що використання подібних протоколів призводить до нераціонального використання доступних мережних ресурсів, що, у свою чергу, є причиною їх перевантаження та вимагає впровадження концепцій підвищення якості управління мережними ресурсами, наприклад Traffic Engineering (ТЕ).

Розширення переліку і, що важливо, змісту вимог до телекомунікаційних технологій істотно вплинуло на зміну самої постановки маршрутних задач і факторів, що приймаються до розгляду при їх розв’язанні. Задача маршрутизації має розглядатися як комплексна задача щодо оптимізації доступних мережних ресурсів шляхом їхнього розподілу між потоками, що надходять на обслуговування. Гібридний характер сучасних мереж з інтеграцією різних технологій (у тому числі з різними режимами пакетної комутації), забезпечення гарантованої якості обслуговування (Quality of Service, QoS) з відстеженням не тільки номінальної, але й доступної пропускної здатності трактів передачі, а також багатошляховий спосіб транспортування повідомлень є основними факторами, що визначають необхідність пошуку альтернативних підходів до формулювання та розв’язання маршрутних задач. У результаті набуває актуальності наукова задача щодо оптимізації процесів адаптивної маршрутизації з підтримкою QoS у гібридних ТКМ, розв’язання якої передбачає розробку відповідних моделей і методів маршрутизації.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана у відповідності з положеннями „Концепції розвитку зв’язку України до 2010 року” та „Концепції конвергенції телефонних мереж та мереж з пакетною комутацією в Україні”. Матеріали дисертації знайшли застосування в науково-дослідних роботах. Зокрема в роботі №129-1 „Розробка технології побудови активних телекомунікаційних мереж, методології їх аналізу та синтезу для забезпечення розподілених інформаційно-обчислювальних систем” (держ. реєстр. №0101U005126), яка виконувалась кафедрою телекомунікаційних систем Харківського національного університету радіоелектроніки, та в роботі „Теоретичні дослідження режиму групового використання частотних планів в мережах рухомого стільникового зв’язку стандартів GSM-900/1800” (договір Б–1/4 між відділенням радіоелектроніки та засобів зв’язку Академії інженерних наук України та Харківським державним науково-технічним центром з питань технічного захисту інформації).

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

Завданнями дослідження є:

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

- оцінка існуючих підходів до розв’язання маршрутних задач;

- розробка адекватного опису ТКМ, що містить структурну та функціональну моделі процесів інформаційного обміну відповідно до сформульованих вимог;

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

- розробка методів адаптивної маршрутизації з підтримкою QoS в гібридних ТКМ з ієрархічною структурою;

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

- розробка рекомендацій щодо практичної реалізації отриманих результатів.

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

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

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

2. Розроблено метод ієрархічно-координаційної маршрутизації в ТКМ рівня WAN з ієрархічною структурою, новизна якого полягає у використанні принципу передбачення взаємодій на рівні декомпозиції на підмережі (верхній рівень), а на рівні декомпозиції за змінними часу – принципу цільової координації з метою реалізації паралельних обчислень (нижній рівень). Це дозволяє серверу маршрутів верхнього рівня в умовах постійного відстеження поточних значень стану окремих підмереж нижнього рівня цілком визначати порядок маршрутизації на міжмережній ділянці.

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

Практичне значення результатів роботи. Отримані наукові результати мають практичну значимість, оскільки вони можуть бути підґрунтям перспективних протоколів маршрутизації з підтримкою QoS у гібридних ТКМ. Матеріали дисертаційної роботи також використано в навчальному процесі кафедри телекомунікаційних систем ХНУРЕ.

Особистий внесок здобувача. Дисертаційна робота виконана на кафедрі телекомунікаційних систем ХНУРЕ. Основні результати роботи належать особисто автору і повністю опубліковані в фаховій літературі [1–18].

У роботах, виконаних у співавторстві, особисто Євсєєвій О.Ю. належать наступні наукові результати. В роботі [1] автору належить розробка функціональної моделі процесів маршрутизації в телекомунікаційних мережах з гарантованою якістю обслуговування, а також метод розв’язання маршрутної задачі. В [2] автором зроблено огляд літератури по інтелектуальним мережам та системам управління, запропоновано напрямки реалізації принципів інтелектуальних мереж в ТКМ військового призначення. В роботі [3] обрано математичний апарат та проведено аналіз особливостей застосування ієрархічно-координаційних методів до розв’язання задачі електромагнітної сумісності. В роботі [4] автором обґрунтовано вибір математичного апарату, автору належить методологія урахування в рамках математичної моделі ТКМ статичного та динамічного планів розподілу інформації. В [8, 10] розроблена математична модель, уведено розширений структурний вектор, зроблено огляд літератури. В роботах [9, 12] автором отримані умови резервування мережних ресурсів з метою реалізації QoS-маршрутизації. В [14] автору належить секвенційна модель маршрутизації.

Апробація результатів дисертації проводилась на дев’яти наукових конференціях та форумах: VII, VIII, IХ Міжнародних конференціях „Теорія та техніка передачі, прийому й обробки інформації” (м. Туапсе, 2001–2003); конференції „Інформаційні технології Військово-Повітряних Сил у ХХІ сторіччі” (м. Харків, 2001); I Міжнародному радіоелектронному форумі „Прикладна радіоелектроніка. Стан і перспективи розвитку” (м. Харків, 2002); VI Міжнародному молодіжному форумі „Радіоелектроніка та молодь у ХХІ сторіччі” (м. Харків, 2002); V Міжнародній конференції „Еволюція транспортних мереж телекомунікацій. Проблеми побудови, розвитку та управління” (м. Ялта, 2002); I і II Міжнародних науково-практичних конференціях „Проблеми управління мережами та послугами телекомунікацій в умовах конкурентного ринку” (м. Ялта, 2002).

Публікації. Основні положення дисертації висвітлено у 18 роботах, з яких 10 робіт опубліковано в наукових фахових виданнях України [1–9] та за кордоном [13]. Крім того, ці матеріали опубліковані в відомих часописах [10–12] та тезах доповідей на конференціях [14–18].

Структура дисертації. Дисертація складається з вступу, чотирьох розділів та висновків. Загальний обсяг дисертаційної роботи становить 176 сторінок, із них 18 сторінок із рисунками. Список використаних джерел містить 91 найменування на 8 сторінках.

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

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

У першому розділі на підставі аналізу стану та перспектив розвитку телекомунікаційних технологій показано, що основним напрямком їх розвитку є побудова мультисервісних мереж, які здатні обслуговувати різнорідний за типом та вимогами щодо якості обслуговування трафік. За відсутності єдиної універсальної транспортної технології ТКМ носять гібридний характер, що проявляється у реалізації у межах однієї мережі телекомунікаційних технологій з різними режимами пакетної комутації, наприклад IP (Internet Protocol), ATM (Asynchronous Transfer Mode) та MPLS (Multiprotocol Label Switching).

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

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

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

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

(1)

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

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

, (2) , (3)

, (4) , (5)

де , ; – частка пропускної здатності тракту , яку виділено для реалізації статичної маршрутизації; , – частки пропускної здатності тракту , які виділено для реалізації, відповідно, режимів віртуального з’єднання та датаграмного, .

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

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

, (6) , (7) , (8)

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

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

,

де –інтенсивність агрегованого потоку в тракті ; – середня довжина пакета в трафіку .

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

, ,

де – розмір “корзини маркерів” (параметр алгоритму профілювання трафіка); – гарантована швидкість передачі для трафіка , .

У матричній формі система рівнянь (1) набуває вигляду

, (9)

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

В межах моделі (2)–(9) задача маршрутизації була сформульована як оптимізаційна задача щодо визначення маршрутних змінних за наявності обмежень (2)–(9) шляхом мінімізації функціоналу

, (10)

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

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

, (11)

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

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

, (12)

де – матриця, яка містить 0 та 1.

У межах ієрархічного подання цільовий функціонал (10) набуває вигляду

,

. (13)

Таким чином задачу маршрутизації зведено до оптимізаційної задачі щодо мінімізації (13) за наявності обмежень на змінні стану та маршрутні змінні (2) – (8), (11), (12) з метою визначення векторів і .

Проведений аналіз методів розв’язання сформульованої задачі оптимального управління та ієрархічна структура ТКМ визначили пріоритетне використання ієрархічно-координаційних методів розв’язання. Результати порівняльного аналізу основних характеристик ієрархічно-координаційних методів визначили застосування таких комбінацій принципів координації: принцип передбачення взаємодій (ПВ) на рівні декомпозиції на підмережі (задача верхнього рівня, ВР) та принцип цільової координації (ЦК) при декомпозиції за змінними часу з метою реалізації паралельних обчислень (задача нижнього рівня, НР) (метод ПВ-ЦК); принцип оцінки взаємодій (ОВ) на рівні декомпозиції на підмережі (задача ВР) та принцип ЦК на НР (метод ОВ-ЦК).

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

При застосуванні методу ЦК на НР задача (13) набуває вигляду

; ; (14)

,

де – лагранжіан, який отримано з (13) шляхом уведення обмеження (11); – вектор множників Лагранжа для -ї підмережі.

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

(15)

,

де – гамільтоніан для -ї підмережі.

Таким чином, метод ПВ-ЦК передбачає таку послідовність дій:

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

2. Розв’язання на СММ задачі мінімізації за змінними у відповідності до обмежень (2)–(8), (11), (12) при фіксованих .

3. Розсилання отриманого вектора з СММ на всі СМП.

4. Розв’язання на кожному СМП задачі НР, а саме задачі мінімізації (13) за змінними при фіксованих , та обмеженнях (2) – (8), (11). Для цього застосовується принцип ЦК, який передбачає таке:

4.1. Формування вектора множників .

4.2. Мінімізація (15) за змінними та обмеженнях (2) – (8).

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

4.4. Передача отриманих змінних до СММ.

5. Розв’язання на СММ задачі мінімізації (13) за змінними при
фіксованих та наявності обмежень (2)–(8), (11), (12).

6. За умови досягнення функцією (13) свого оптимуму або якщо вичерпано час на розв’язання задачі маршрутизації формування на підставі поточних значень маршрутних змінних маршрутних таблиць, які з СММ через СМП буде розіслано усім маршрутизаторам мережі. У протилежному разі перехід до 3.

Метод ПВ-ЦК має такі властивості: реалізує роздільне управління маршрутами всередині та поміж підмережами, забезпечує адаптивну маршрутизацію з підтримкою QoS, відвертає можливість перевантаження, знаходить такі значення маршрутних змінних, які можуть бути реалізовані у будь який час. Метод передбачає постійне відстеження на СММ стану підмереж.

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

Метод ОВ-ЦК передбачає таку послідовність дій:

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

2. Розв’язання на СММ задачі мінімізації функціонала за змінними відповідно до зібраної інформації та обмежень (2)–(8), (11), (12). Отримані значення трактуються як оцінки взаємодій .

3. Розсилання вектора оцінки взаємодій з СММ на всі СМП.

4. Розв’язання на СМП задачі (13) за змінними та відповідно до принципу ЦК при обмеженнях (2)–(8), (11) та з урахуванням отриманих оцінок (). Застосування ЦК передбачає таке:

4.1. Формування вектора множників .

4.2. Мінімізацію (15) за змінними та при обмеженнях (2) – (8) з урахуванням оцінок для кожного часового інтервалу .

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

5. Пересилання отриманих на СМП змінних та до СММ.

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

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

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

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

, (16) , (17)

де – продуктивність мережі на -у часовому інтервалі; – пропускна здатність мережі на -у інтервалі; – величина сумарного навантаження, що надходить до мережі на -у інтервалі; – обсяг навантаження, що надходить до вузлів мережі; – число трактів передачі в ТКМ.

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

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

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

Як показало моделювання, реалізація властивостей прогнозування моделі маршрутизації дозволяє підвищити продуктивність ТКМ (рис.2) в середньому на 14–18% в залежності від структури мережі. З ростом темпи приросту знижаються, що дозволяє зробити висновок про обмеження . Поведінка моделі в умовах високого завантаження (рис.3) доводить, що реалізація властивостей прогнозування дозволяє не тільки підвищити продуктивність мережі, але й уникнути перевантаження (якщо це короткочасний стрибок навантаження) або зсунути час входження у цей режим.

Порівняння якості функціонування ТКМ з маршрутизацією за алгоритмом найкоротшого шляху (пунктирні лінії на рис. 4) та запропонованого підходу (суцільні лінії на рис. 4) продемонструвало виграш у продуктивності для неповнозв’язних структур з 5 та 7 близько 30%, який зростає для структур більшої розмірності до 40–45% .

Експериментальне дослідження методів ієрархічно-координаційної маршрутизації продемонструвало:

а) високу збіжність методів, що пропонуються. Кількість циклів мінімізації, необхідних для отримання оптимального значення, складає 2–4 для ПВ-ЦК, 5–8 для ОВ-ЦК та може бути зменшена за рахунок вибору як початкових значень вектору маршрутних змінних результатів розв’язання задачі на попередньому кроці (до 1–3 та 4–6 відповідно);

б) зближення методів ПВ-ЦК та ОВ-ЦК в умовах високої стабільності вхідного навантаження, що свідчить про доцільність переходу в цих умовах на метод ОВ-ЦК, який не потребує постійного оновлення на СММ інформації про поточний стан мережі, чим дозволяє знизити обсяги службового трафіка;

в) доцільність реалізації процедур координації особливо для структур з високим ступенем зв’язності на міжмережних ділянках. Введення процедур координації на міжмережних ділянках в межах методу ПВ-ЦК дозволяє підвищити продуктивність мережі на величину від 15–20% (для структури рис.5,г) до 50–65% (для структури рис.5,а) відносно випадку відсутності координації (рис.6). Це досягається за рахунок усунення втрат, що виникають внаслідок нераціонального використання міжмережних ресурсів або їх перевантаження. Введення координації залежить від ступеня зв’язності мережі і є необхідним, наприклад, для мережі з 8-ми вузлів при співвідношенні зв’язності всередині та поміж підмережами не більше двох (рис.5,а-б).

ВИСНОВКИ

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

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

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

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

4. На підставі запропонованих моделей маршрутизації в ТКМ здійснено їхнє ієрархічне представлення і розроблено методи ієрархічно-координаційної маршрутизації на базі комплексного застосування до розв’язання сформульованої задачі декомпозиційних принципів. Методи орієнтовано на використання в ТКМ рівня WAN з ієрархічною структурою. Метод маршрутизації ПВ-ЦК ґрунтується на розв’язанні оптимізаційної задачі за допомогою принципів координації передбачення взаємодій (ПВ) на рівні декомпозиції за підмережами та цільової координації (ЦК) на рівні декомпозиції за змінними часу. Це дозволяє серверу маршрутів мережі в умовах постійного відстеження поточних значень стану окремих підмереж нижнього рівня повністю визначати порядок маршрутизації на міжмережній ділянці. Метод ОВ-ЦК базується на використанні принципу оцінки взаємодій (ОВ) на рівні декомпозиції за підмережами, а принципу ЦК – на рівні декомпозиції за змінними часу. Це дозволяє серверу маршрутів мережі за рахунок відстеження лише граничних і/або середніх значень параметрів стану підмереж нижнього рівня формувати обмеження, які запобігають перевантаженню міжмережних ресурсів, а функція саме маршрутизації перекладається на маршрутизатори підмереж нижнього рівня.

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

- зростання продуктивності за умов реалізації запропонованих методів маршрутизації порівняно зі статичним планом розподілу інформації на 10–30% для неповнозв’язних структур з 5 та 7, який зростає для структур більшої розмірності до 40–45%;

- запобігання локальним перевантаженням і боротьбу з глобальними перевантаженнями в мережі в цілому;

- підвищення продуктивності з 30 до 80 % при спільному використанні в мережі різних режимів пакетної комутації (із встановленням і без установлення з'єднання);

- високу збіжність методів ієрархічно-координаційної маршрутизації (необхідне число циклів мінімізації у методі ПВ-ЦК складає від 2 до 4 у залежності від інтервалу прогнозування та 5–8 у методі ОВ-ЦК, які можуть бути знижені);

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

- зближення методів ПВ-ЦК та ОВ-ЦК в умовах стабільності вхідного навантаження та доцільність переходу в цих умовах на метод ОВ-ЦК, який не потребує частого оновлення на СММ інформації про поточний стан мережі, чим дозволяє знизити обсяги службового трафіка;

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

6. За результатами проведених експериментальних досліджень розроблений комплекс практичних рекомендацій щодо реалізації запропонованих моделей і методів маршрутизації. Рекомендації стосуються найкращих варіантів реалізації синтезованих моделей і методів маршрутизації в сучасних ТКМ з вибором величин їх основних параметрів.

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

1. Лемешко А.В., Евсеева О.Ю., Гема Н.И. Динамическая маршрутизация в пакетных сетях с гарантированным качеством обслуживания // Радиотехника: Всеукр. межвед. науч.-техн. сб. – 2001. – Вып. 123. – С. 45–50.

2. Лемешко А.В., Евсеева О.Ю. Интеллектуализация системы управления телекоммуникационной сетью ВВС // Авіаційно-космічна техніка і технологія: Зб. наук. праць. – 2001. – Вип. 22. – С. 148–152.

3. Лемешко А.В., Евсеева О.Ю. Диакоптические и иерархическо-координационные методы в решении проблемы ЭМС для группировки радиоэлектронных средств связи // Праці УНІІРТ. – 2001. – №2. – С. 8–10.

4. Лемешко А.В., Евсеева О.Ю. Функциональная модель адаптивной маршрутизации комбинированного типа // Радиотехника: Всеукр. межвед. науч.-техн. сб. – 2002. – Вып. 127.– С. 152–158.

5. Евсеева О.Ю. Динамическая маршрутизация в гибридных телекоммуникационных сетях // Радиотехника: Всеукр. межвед. науч.-техн. сб. – 2002. – Вып. 128. – С. 86–90.

6. Евсеева О.Ю. Экспериментальное исследование динамической модели адаптивной маршрутизация в датаграммных телекоммуникационных сетях // Радиотехника: Всеукр. межвед. науч.-техн. сб. – 2003. – Вып. 133. – С. 20–26.

7. Евсеева О.Ю. Решение задачи иерархическо-координационной маршрутизации в телекоммуникационных сетях методом предсказания взаимодействия // Открытые информационные и компьютерные интегрированные технологии. –Харьков: НАКУ “ХАИ”, 2003. – Вып.21. – С. 102–111.

8. Поповский В.В., Лемешко А.В., Евсеева О.Ю. Симплициальная модель оценки структурной сложности телекоммуникационных систем // Восточно–Европейский журнал передовых технологий. – 2003. – №5(5). – С. 48–51.

9. Лемешко А.В., Евсеева О.Ю., Беленков А.Г. Обеспечение гарантированного качества связи при решении задач сетевого уровня ЭМВОС // Восточно–Европейский журнал передовых технологий. – 2003. – №6(6). – С. 30–33.

10. Евсеева О.Ю., Лемешко А.В. Оценка связности и структурной сложности телекоммуникационных систем с использованием математического аппарата q-анализа // Вісник Українського будинку економічних та науково-технічних знань.– 2002.– №1.–С. 119–123.

11. Евсеева О.Ю. Математическое моделирование гибридной маршрутизации в пакетных сетях // Вісник Українського будинку економічних та науково-технічних знань.– 2002. – №2.– С. 95–100.

12. Евсеева О.Ю., Лемешко А.В., Беленков А.Г. Обеспечение системности решений маршрутных задач с поддержкой QoS в мультисервисных сетях связи // Вісник Українського будинку економічних та науково-технічних знань. – 2003.– №2.– С. 85-90.

13. Евсеева О.Ю. Особенности процессов маршрутизации в сетях с различными режимами пакетной коммутации // Проблемы транспорта. – 2003.– Вып. 8.– С. 289–294.

14. Евсеева О.Ю., Лемешко А.В. Секвеционная маршрутизация в иерархических телекоммуникационных системах // 7-я Международная конференция “Теория и техника передачи, приема и обработки информации”: Сб. научных трудов. – Харьков: ХТУРЭ, 2001.– С. 44–45.

15. Евсеева О.Ю. Математическая модель динамической маршрутизации в мультисервисных сетях // 6-й Международный молодежный форум “Радиоэлектроника и молодежь в ХХІ веке”: Сб. научных трудов. Ч. 1. – Харьков: ХНУРЭ, 2002. – С. 193–194.

16. Евсеева О.Ю. Симплициальная модель структурной живучести телекоммуникационной системы // 8-я Международная конференция “Теория и техника передачи, приема и обработки информации”: Сб. научных трудов. – Харьков: ХНУРЭ, 2002.– С. 66–68.

17. Евсеева О.Ю. Исследование устойчивости методов управления маршрутизацией в телекоммуникационных сетях // 1-й Международный радиоэлектронный форум “Прикладная радиоэлектроника. Состояние и перспективы развития” МРФ-2002: Сб. научных трудов. Ч. 1. – Харьков: АН ПРЭ, ХНУРЭ, 2002. – С. 470–471.

18. Евсеева О.Ю. Метод предсказания взаимодействия в задачах иерархическо-координационной маршрутизации в телекоммуникационных сетях // 9-я Международная конференция “Теория и техника передачи, приема и обработки информации”: Сб. тезисов докладов по материалам Международной научной конференции. – Харьков: ХНУРЭ, 2003.– С. 12–13.

АНОТАЦІЯ

Євсєєва О.Ю. Методи адаптивної маршрутизації в гібридних телекомунікаційних мережах з гарантованою якістю обслуговування. – Рукопис.

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

Дисертацію присвячено пошуку нових підходів до розв’язання маршрутних задач у телекомунікаційних мережах (ТКМ) і розробці на їхній підставі методів адаптивної маршрутизації з підтримкою гарантованої якості обслуговування в гібридних ТКМ. Було сформульовано основні вимоги до методів маршрутизації у сучасних ТКМ, серед яких є вибір маршруту з урахуванням QoS-вимог потоків та прагнення до збалансованого використання наявних мережних ресурсів, адаптивність до змін умов функціонування, орієнтування на використання у гібридних мережах та мережах ієрархічної структури. Відповідно до них було розроблено динамічну функціональну модель ТКМ в просторі стану та розроблено методи ієрархічно-координаційної маршрутизації. Підґрунтям для методів маршрутизації є розв’язання оптимізаційної задачі за допомогою комплексного використання різних декомпозиційних принципів на верхньому та нижньому рівнях: принципів передбачення взаємодій та цільової координації в методі маршрутизації ПВ-ЦК і принципів оцінки взаємодій та цільової координації у методі маршрутизації ОВ-ЦК.

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

SUMMARY

Evseeva O. Yu. Methods of adaptive routing in hybrid telecommunication networks with guaranteed quality of service. - Manuscript.

Dissertation for the candidate’s degree of technical science in a specialty 05.12.02 - Telecommunication systems and networks. – Ukrainian State Academy of a Railway Transport, Kharkov, 2004.

The dissertation is devoted to the research of the new approaches to the decision of the problems of routing in telecommunication networks (TN) and to the development of the methods of adaptive routing on their basis with the support of the guaranteed quality of service (QoS) in hybrid TN. The basic requirements to the methods of routing in modern TN are formulated as: choice of a route in accordance with the QoS-requirements of flows, the attempt to balanced usage of the available network resources, the adaptability to the changes of functioning conditions, the orientation to the usage in hybrid networks and networks with hierarchical structure. According to the requirements the dynamic functional model of TN in space of conditions and the methods of hierarchical - coordination routing are developed. The solution of optimization problem by means of complex using of various decomposition principles at the upper and lower levels are in the basis of routing methods. These principles are: principles of interaction prediction and purpose coordination in the routing method IP-PC and principles of interaction estimation and purpose coordination in the routing method IE-PC.

Key words: telecommunication network, guaranteed quality of service, routing, model in space of conditions, hierarchical -coordination routing methods.

АННОТАЦИЯ

Евсеева О.Ю. Методы адаптивной маршрутизации в гибридных телекоммуникационных сетях с гарантированным качеством обслуживания. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 – Телекоммуникационные системы и сети. –Украинская государственная академия железнодорожного транспорта, Харьков, 2004.

Диссертационная работа посвящена поиску новых подходов к решению маршрутных задач в телекоммуникационных сетях (ТКС) и разработке на их основе методов адаптивной маршрутизации с поддержкой гарантированного качества обслуживания в гибридных ТКС.

Показано, что основным направлением развития ТКС являются мультисервисные сети, в качестве ключевых моментов при построении которых выступают обслуживание разнородного по типу и требованиям трафика, а также гарантированное обеспечение требуемого уровня качества обслуживания (Quality of Service, QoS). В условиях отсутствия единой