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

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

Халдун Абдель Карим Ахмад Бесуль

(Йорданія)

УДК 681.3

Спосіб та засоби багатоабонентської доставки

повідомлень у комп'ютерних мережах

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

системи і мережі

А В Т О Р Е Ф Е Р А Т

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

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

Київ-2001 р.

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

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

Науковий керівник: доктор технічних наук, професор Луцький Георгій Михайлович, НТУУ "КПІ", завідувач кафедрою ОТ

Офіційні опоненти: доктор технічних наук, професор Печурін Микола Капітонович, Державний комітет зв'язку та інформатизації України, начальник управління

кандидат технічних наук, доцент Балашов Андрій Юрійович, Київський міжнародний університет цивільної авіації, доцент кафедри Обчислювальних машин, систем та мереж

Головна організація Інститут проблем моделювання в енергетиці НАН України, відділ 9, “Технічна діагностика”

Захист відбудеться "_21_"_травня_ 2001 р. о 14:30 на засіданні спеціалізованої ради Д 26.002.02 у НТУУ "КПІ (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306).

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

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

Автореферат розісланий 20 квітня 2001 р.

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

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась в 1998-2001рр у відповідності з планами науково-дослідницьких робіт кафедри обчислювальної техніки НТУУ “КПІ”: НДР № 0100U000101 “Розробка моделі надпродуктивної масштабованої обчислювальної системи для захисту баз даних в високопродуктивному обчислювальному багатопроцесорному комплексі (супер-ЕОМ) (1998-2001), та в рамках робіт напрямку “Перспективні мережні інформаційні технології, прилади, системи зв'язку”, що виконувались на кафедрі обчислювальної техніки НТУУ “КПІ” в 1997-1999 рр.

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

Об'єктом дослідження є процес доставки повідомлень між абонентами комп'ютерної мережі.

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

Основні задачі дослідження, у відповідності з поставленою метою, полягають у наступному:

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

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

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

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

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

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

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

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

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

2. Розроблено алгоритм формування оптимального дерева Штейнера на основі поділу групи на окремі підгрупи.

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

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

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

Особистий внесок здобувача. Основні результати одержані автором самостійно. Автору належить:

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

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

3. Алгоритм формування оптимального дерева Штейнера на основі поділу групи на окремі підгрупи.

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

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

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

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

1. VШ науково-технічній конференції “Вимірювальна та обчислювальна техніка в технологічних процесах” (25-27 травня 2000 р., м. Хмельницький).

2. IV науково-технічній конференції “Computer Systems and Networks (designing, application, utilization)” (24-26 червня 2000 р., м. Жешов, Польща).

Публікації. Основні результати дисертаційної роботи опубліковані в 5 статтях.

Структура та обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновку та додатку. Загальний обсяг роботі складає 127 сторінок друкованого тексту, 32 малюнка, 5 таблиць, та списку використаної літератури з 87 найменувань.

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

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

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

Багатоабонентська доставка повідомлень розглядається як дві взаємопов'язані задачі:

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

· передача по встановленим маршрутам повідомлень від відправника до одержувача інформації.

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

· вектор дистанцій (distance vector), в основі якого лежить метод динамічного програмування Беллмана;

· стани каналів (link state), що базується на визначенні найкоротшого шляху за допомогою метода Дейкстра.

Проводиться порівняльний аналіз алгоритмів маршрутизації: Беллмана-Флойда, Дейкстра і Форда-Уоршела. Показано, що для великих розряджених графів найбільш ефективним є алгоритм Дейкстра, обчислювальна складність якого при знаходженні шляху між двома вершинами характеризується величиною О(eґ logn), де: n - число вузлів графа, а e- число дуг графа.

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

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

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

При аналізі потоків даних, а також при вирішенні задачі маршрутизації, комп'ютерна мережа представляється у вигляді орієнтованого навантаженого графа: G = (V, U), де: V = {vi | i=1,2,…,n} – множина вершин графа, U ={ui,j | i=1,2,…,n; j=1,2,…,m} – множина дуг графа з вихідною вершиною vi і вхідною вершиною vj. Кожній дузі ui,j графа G = (V, U) ставиться у відповідність деяке значення wi,j її ваги, яке може виражати затримку передачі або вартість передачі, а іноді те й інше: wi,j = (ci,j ,di,j), де: ci,j - вартість, а di,j - затримка передачі інформації в каналі передачі даних між суміжними вузлами. Сумарна затримка інформації на деякому шляху Pm,l визначається як:

,

де: tk - затримка передачі інформації через маршрутизатор.

Тут підсумовування ведеться по всіх вершинах і дугах, що входять у шлях Pm,l.

Затримка в маршрутизаторі є змінною величиною, що залежить від ряду параметрів. З достатнім ступенем достовірності модель маршрутизатора можна представити у вигляді системи масового обслуговування типу M/M/m. У цьому випадку середній час затримки повідомлення в маршрутизаторі дорівнює:

,

де:

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

При використанні групової маршрутизації в графі G = (V, U) (рис.1) виділяється підграф Gs = (Vs, Us), що відповідає групі одержувачів інформації, яка є набором вершин, ідентифікованих унікальною груповою адресою s. У даному випадку група одержувачів інформації являє собою множину Vs = (vi | i=1,2,…,8), а вершина vs П Vs. Діаметр даного підграфа позначимо Ds.

У загальному випадку вершина - джерело може бути, а може і не бути членом групи одержувачів. Множина шляхів від vs до кожної вершини підмножини Vs = (vi | i=1,2,…,8) утворює дерево доставки повідомлень. Коренем цього дерева є вершина vs, а усі його листи є членами групи Gs.

Мінімальною відстанню до групи одержувачів (dmin) будемо називати шлях, мінімальний серед усієї множини шляхів від вершини vs до вершини vi О Vs. У випадку, коли вершина - джерело належить групі одержувачів, мінімальна відстань до групи одержувачів дорівнює нулю, тобто має місце властивість: vs О Vs Ю dmin =0.

Верхня межа затримки групової передачі Th при vs П Vs визначається наступним співвідношенням: Th = T(dmin) + T(Ds), де: T(dmin)- час передачі інформації по шляху dmin; T(Ds) – час передачі інформації по шляху Ds . Розглянемо довільний шлях Ps,i від вершини vs до вершини vi О Vs. У загальному випадку цей шлях Ps,i = (ds,k) + Pk,i , де: vk О Vs і vi О Vs. Потім у якості вершини vk обираємо кінцеву вершину, що відповідає відстані dmin, у цьому випадку маємо: Ps,i = dmin + Pk,i . В свою чергу шлях Pk,i належить множині шляхів підграфа Gs, оскільки vk О Vs і vi О Vs. З цього випливає, що Ds і Pk,i і відповідно: Lh і Ps,i.

У свою чергу нижня межа затримки групової передачі (Ta) визначається відстанню від вершини vs до найбільш віддаленої вершини vi О Vs. Значення верхньої і нижньої меж затримки групової передачі і їх співвідношення з заданим значенням граничної затримки (Ts) дозволяють вибрати оптимальну стратегію побудови дерева доставки.

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

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

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

Розглянемо наступні умови вибору варіанта маршрутизації:

1. Ts і Th. У цьому випадку визначається мінімальний шлях до групи доставки, а власне групова маршрутизація здійснюється всередині групи доставки.

2. Ts < Ta. При цьому співвідношенні не забезпечується необхідний рівень сервісу.

3. Ts = Ta. У цьому випадку стратегія маршрутизації повинна ґрунтуватися на побудові мінімального шляху до найбільш віддаленої вершини групи доставки з наступним підключенням до нього решти вершин vi О Vs так, щоб довжина нового шляху не перевищувала Ts.

4. Th >Ts > Ta. При даній умові можливі різні варіанти маршрутизації.

Крім того, за рахунок поділу підграфа Gs на ряд підграфів, можна використати умови 1. Справді, при поділі підграфа відповідно зменшується діаметр кожного з новоутворених підграфів, що може привести до виконання умови Ts і Th.

На рис. 4 подана область припустимих значень для групи доставки за умови Ts і Th. Тут вершина V8 є найближчою до вершини-джерела (Vs). У даному випадку група доставки ділиться на три підгрупи. Перша підгрупа (G2) утворюється підмножиною, відстань між вершинами якої не перевищує величини (Th – dmin ), тут dmin представляє шлях із вершини Vs до вершини V8. Інші вершини групуються в підмножини аналогічним способом. З вершин, що залишились, вибирається вершина, найближча до вершини Vs , у нашому випадку це вершина V1. Потім формується підгрупа (G1), відстань між вершинами якої не перевищує величину (Th – d1), де d1 - відстань від вершини Vs до вершини V1. Процес формування підмножин продовжується до включення в них останньої з вершин підгрупи доставки.

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

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

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

· Мінімальне розпаралелювання інформаційного потоку.

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

1. Формується склад групи маршрутизації Gs, і визначається діаметр (Ds ) графа цієї групи.

2. Визначається місце розташування джерела відносно групи маршрутизації. Якщо vs П Vs, то здійснюється перехід до пункту 4. При vk О Vs здійснюється перехід до пункту 3.

3. Розподіл групи маршрутизації на підгрупи. Подальші операції розглядаються щодо кожної з підгруп маршрутизації. На рис. 5 показано результат розподілу групи маршрутизації на окремі підгрупи.

4. Обчислення мінімальної відстані Pm(vs, vi Ѕvi О Vs ) і Th .

5. Порівнюються Th і Ts. Якщо Ts і Th, то здійснюється перехід до пункту 6, інакше - до пункту 7.

6. Виконується процедура формування дерева доставки до однієї підгрупи у вигляді дерева Штейнера, подібного до дерева, показаного на рис. 3.

7. Виконується процедура формування дерева доставки, що включає декілька підгруп маршрутизації (рис. 4). Перехід до пункту 8.

8. Завершення алгоритму.

Рис.5

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

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

1. За допомогою алгоритма Дейкстра визначається вершина vi О Vs з мінімальним значенням шляху Pm(vs, vi Ѕ vi О Vs ). Ця вершина є найближчою до вершини-джерела інформації.

2. Для вершини vs перевіряється умова: Th < Ts. Якщо умова не виконується, то вершина vi вважається недосяжною, формування дерева доставки завершується. При виконанні умови перехід до пункту 3.

3. Розглядаючи вершину vi у якості вихідної вершини, формується множина вершин Vi = ( vj Ѕ Pm(vs, vi)+ Pm(vi, vj) < Ts ), що складають Gi підгрупу доставки повідомлень. Після включення в підгрупу Gi усіх допустимих вершин здійснюється перехід до пункту 4.

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

5. На шляху Pm(vs, vi Ѕvi О Vs ) вибирається вершина vj П Vi з мінімальною дугою ui,j , тобто здійснюється крок назад на шляху Pm(vs, vi Ѕvi О Vs ).

6. Для вершини vj перевіряється умова: Th < Ts. Якщо умова не виконується, то вершина vj вважається не досяжною і здійснюється перехід до пункту 5. При виконанні умови – перехід до пункту 7.

7. Вершина vj вибирається в якості нової вихідної вершини для маршрутизації, потім здійснюється перехід до пункту 1.

8. Завершення процедури формування дерева доставки.

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

У четвертому розділі розглядаються питання групової маршрутизації передачі. На основі аналізу відомих методів групової маршрутизації запропоновано комбінований алгоритм групової маршрутизації, який в порівнянні з відомими алгоритмами дозволяє підвищити ефективність комп'ютерних мереж у режимі багатоабонентської доставки повідомлень. Проведений у рамках дисертаційної роботи аналіз методів і засобів групової маршрутизації мультимедійних даних показав, що існуючі протоколи дають гарні результати роботи на обмеженому колі задач. У роботі показано, що серед відомих протоколів найбільш ефективними є ССЕТ(Constrained Cheapest Edge Tree), CSPT (Constrained Shortest Path Tree) і SPT ( Shortest Path Tree) , причому кожний - у визначеному діапазоні застосування. З урахуванням цього і на основі даних протоколів розроблено комбінований алгоритм групової маршрутизації, що містить у собі наступні процедури:

1. Виконується модифікована процедура маршрутизації, що базується на алгоритмі Дейкстра SPT (яка використовується на першому кроці протоколу ССЕТ).

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

3. Якщо не всі вузли були досягнуті на попередньому кроці, то комбінується дерево найкоротших шляхів до цих вузлів з деревом найбільш дешевих шляхів. Отримане рішення не перевищує обмеження на затримку. Це останній крок протоколу CSPT.

4. Розраховується вартість обчислення маршруту відповідно протоколу ССЕТ.

5. Розраховується вартість дерева SPT, отриманого за допомогою алгоритму Дейкстра.

6. Розраховується вартість дерева мінімальної вартості CSPT із додатковими шляхами за алгоритмом SPT.

7. Вибирається найбільш дешеве дерево з розглянутих.

Часова складність запропонованого алгоритму в основному визначається рівнем часової складності протоколу ССЕТ.

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

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

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

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

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

Головні наукові і практичні результати роботи полягають у наступному:

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

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

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

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

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

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

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

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

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

1. Халдун Абдел Карим Ахмад Бесуль. Оценка времени задержки передачи информации в виртуальных сетях. // Вимірювальна та обчислювальна техніка в технологічних процесах. -1999. -№2. -С. 110-113.

2. Халдун Бесуль. Задача разбиения multicast групп // Вісник національного технічного університету України “КПІ”, Інформатика, управління та обчислювальна техніка. - 2001. -№ 35. –С. 3-8.

3. Ю.А. Кулаков, Халдун Бесуль. Алгоритмы маршрутизации мультимедийных данных в компьютерных сетях. // Вимірювальна та обчислювальна техніка в технологічних процесах. -1999. -№4. -С. 104-108.

4. Ю.А. Кулаков, Халдун Бесуль. Стохастическая модель задержек блоков данных в коммутационных узлах. // Вісник національного технічного університету України “КПІ”, Інформатика, управління та обчислювальна техніка. - 2000. -№ 34. –С. 26-30.

5. Кулаков Ю.А., Халдун Бесуль. Комбинированный способ маршрутизации мультимедийных данных в компьютерных сетях // Вимірювальна та обчислювальна техніка в технологічних процесах. -2000. -№1. -С. 88-90.

Халдун Абдел Карім Ахмад Бесуль. Спосіб та засоби багатоабонентської доставки повідомлень у комп'ютерних мережах. – рукопис.

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

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

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

Халдун Абдел Карим Ахмад Бесуль. Способ и средства многоабонентской доставки сообщений в компьютерных сетях. - рукопись.

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

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

· формирование маршрутов доставки информации и распространение маршрутной информации;

· передача по установленным маршрутам сообщений от отправителя к получателю информации.

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

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

Для наиболее характерных протоколов групповой маршрутизации CSPT (Constrained Shortest Path Tree) и CCET (Constrained Cheapest Edge Tree), а также для предложенного в работе комбинированного способа маршрутизации разработаны алгоритмы их реализации. Проведен сравнительный анализ эффективности разработанных алгоритмов. С этой целью с помощью модели Доара генерировалось множество сетевых топологий, используя которые осуществлялась оценка временных параметров рассматриваемых алгоритмов. Результаты моделирования показали, что при практически равной временной сложности алгоритмов, комбинированный способ дает лучшие показатели стоимости и времени передачи информации.

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

Вводится понятие верхней (Th ) и нижней (Ta) границ задержки групповой передачи. Th = T(dmin) + T(Ds), где: T(dmin)- задержка в передачи информации по пути dmin; Ds – диаметр группы доставки; T(Ds) – задержка в передачи информации по пути Ds. Соотношение верхней границы задержки и предельно допустимой задержки (Ts) позволяют выбрать оптимальную стратегию построения дерева доставки:

1. Ts і Th. В этом случае определяется минимальный путь до группы доставки, а собственно групповая маршрутизация осуществляется внутри группы доставки.

2. Ts < Ta. При этом соотношении не обеспечивается требуемый уровень сервиса.

3. Ts = Ta. В этом случае стратегия маршрутизации должна основываться на построении минимального пути к наиболее удаленной вершине группы доставки с последующим подключению к нему остальных вершин vi О Vs, так, чтобы длина нового пути не превышала Ts.

4. Th >Ts > Ta. При данном условии возможны различные стратегии маршрутизации. Кроме того, за счет разбиения подграфа Gs на ряд подграфов можно использовать стратегию 1. В самом деле, при разбиении подграфа соответственно уменьшается диаметр каждого из вновь образованных подграфов, что может привести к соблюдению условия Ts і Th.

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

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

Предлагается и обосновывается целесообразность представления отдельных групп доставки в виде виртуальных подсетей. Это позволяет сократить время маршрутизации в коммутационных узлах.

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

Khaldoun Abdel-Kareem Ahmad Besoul the methods and means of multicast in computer networks. - The manuscript.

The dissertation on competition of a scientific degree of Cand.Tech.Sci. On a specialty 05.13.13 - computers, systems and networks. National technical university of Ukraine “ The Kiev polytechnical institute”, Kiev 2001.

The dissertation is devoted to development of a methods and means of multicast in computer networks with the purpose of increase of their productivity. On the basis of the analysis of known algorithms of group routing the combined algorithm, which allows to increase efficiency of computer networks in a mode of multi-user data transmission is developed. The new approach is offered and the algorithm of decomposition of groups of multicast in which basis the algorithm of construction of optimum tree Steiner lays is developed, in view of restrictions on size of a delay of transfer of the information. Increase of efficiency of functioning of computer networks is achieved due to minimization of information streams, including exception of duplication of streams through a network of data transmission.

Key words: computer networks, multicast, multicast routing, a tree of delivery, decomposition of groups of delivery.