МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

ЛУЦЬКИЙ МАКСИМ ГЕОРГІЙОВИЧ

УДК 004.4 (043.3)

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

інформації у мобільних системах та мережах

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

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

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

КИЇВ 2004

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

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

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

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

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

доктор технічних наук, професор Жуков Ігор Анатолійович, Національний авіаційний університет МОН України, директор Інституту інформатики Національного авіаційного університету МОН України,

кандидат технічних наук, доцент Коваленко Анатолій Єпіфанович, Національний університет харчових технологій МОН України, завідувач кафедри інформатики.

Провідна установа

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

Захист відбудеться “10 ” червня 2004 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.062.01 в Національному авіаційному університеті МОН України за адресою: 03164, м. Київ, пр. Космонавта Комарова, 1.

З дисертацією можна ознайомитись у бібліотеці Національного авіаційного університету МОН України за адресою: 03164, м. Київ, пр. Космонавта Комарова, 1.

Автореферат розісланий “ 05 ” травня 2004 р.

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

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

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

Єременко В.С.

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

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

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

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

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

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

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

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

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

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

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

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

Предметом дослідження є клас мобільних комп'ютерних систем і мереж.

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

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

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

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

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

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

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

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

1.

2.

3.

4.

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

Апробація роботи. Основні результати дисертаційної роботи обговорювалися на VІІІ науково-технічній конференції “Вимірювальна й обчислювальна техніка в технологічних процесах” (25-27 травня 2000 р., м. Хмельницький), III Міжнародній науково-технічній конференції “АВІА -2001” (Національний авіаційний університет, Київ, Україна), V Міжнародній науково-технічній конференції “АВІА -2003” (Національний авіаційний університет, Київ, Україна).

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

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

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

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

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

Багатоабонентська доставка інформації розглядається як дві взаємозалежні задачі:

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

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

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

а) MST (мінімального дерева Штейнера);

б) SPT (дерева найкоротшого шляху);

в) CMT (обмеженого дерева багатоадресної передачі).

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

Алгоритми SPT може далі бути класифіковане як дерево на ядрі, дерево на джерелі і гібридне дерево. Приклади протоколів SPT на джерелі – DVMRP і MOSPF. У той час як MST мінімізує витрати, SPT на джерелі мінімізує затримки між кінцями шляху. Були запропоновані такі різновиди дерева на ядрі, такі як дерево на груповому ядрі і дерево на динамічному ядрі. Наприклад, протоколи RIM і HMR являють собою гібридні протоколи, що сполучають характеристики протоколів на ядрі і протоколів на джерелі. У свою чергу протокол маршрутизації RBM сполучає характеристики протоколу маршрутизації RIM і протоколу резервування ресурсів RSVP.

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

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

Дерево на ядрі (CBT) використовує підхід, при якому всі багатоадресні з'єднання мають загальне “розділене дерево”.

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

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

У загальному випадку, комп'ютерні мережі можна представити у виді навантаженого графа G(V, E), де V= { vii=1,2…m}- множина вершин графа, E={ei,ji,j=1,2…m}- множина ребер графа. Кожне ребро ei,j графа характеризується вагою wi,j. При розгляді питань маршрутизації і розподілу потоків як обмеження вводиться значення припустимої затримки td доставки пакетів між довільними вузлами мережі, а як критерій оптимізації розглядається сума ваг W ребер, що утворять даний шлях. Суму ваг шляху прийнято ототожнювати з його вартістю.

У випадку багатоабонентській доставки повідомлень із джерелом у вершині vs і множиною вершин Vm = { vii=1,2…n}, які визначають групу АС, одержувачів інформації, завдання маршрутизації полягає в перебуванні дерева Ts = (Vs, Es ) доставки повідомлень для який виконується умова:

, (1)

де: Ws - вага всіх ребер дерева доставки повідомлень.

Як обмеження на включення ребра ei,j до складу дерева Ts розглядаються умови:

· Bi,j bs, де: Bi,j - значення пропускної здатності каналу; bs - необхідне значення пропускної здатності для багатоабонентської доставки повідомлень по дереву Ts.

· td tm , де: td – значення припустимої затримки передачі пакетів; tm – максимальна затримка передачі пакетів між вузлами дерева багатоабонентської передачі даних.

У загальному випадку не залежно від місця розташування джерела виконуються умови: Bs Vs V; Es E. Якщо джерело не належить групі багатоабонентської доставки повідомлень, то vs Bs і Bs Vs, інакше vs Bs і Bs Vs . Множина вершин V0= Vs Bs , є допоміжною і забезпечує зв’язність вершин дерева Ts. Потужність множини Ts впливає на тимчасову складність процедури багатоабонентської доставки повідомлень. Зі зменшенням потужності множини Ts тимчасова складність багатоабонентської доставки повідомлень знижується.

При значному віддаленні джерела від групи одержувачів інформації доцільно задачу формування дерева багатоабонентської доставки інформації розбити на задачу формування найкоротшого шляху L(vs,v0) від вершини джерела до найближчої вершини v0, що входить до складу групи одержувачів інформації, і задачу формування структури групи одержувачів інформації з кореневою вершиною v0. У цьому випадку вага ребер Ws дерева багатоабонентської доставки інформації містить у собі вагу ребер WL шляху до групи багатоабонентської доставки інформації і вагу ребер W0 усередині групи:

(2)

При перебуванні вершини джерела у середині групи доставки множин V0 = і L(vs,v0) =0, а величина Ws дорівнює:

. (3)

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

(4)

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

У випадку групової багатоабонентської доставки повідомлень як джерело може виступати кожна АС, що входить до складу групи багатоабонентська доставки повідомлень, тобто виконується умова vs Bs і Bs = Vs . У цьому випадку замість одного дерева формується множина дерев багатоабонентської доставки { Ts s=1,2…m}.

Таким чином, задача групової багатоабонентська доставки повідомлень складається у перебуванні множині дерев доставки {Ts s=1,2…m}для кожного з вузлів групи Bs, що задовольняють наступним вимогам:

(5)

за умови: та td tm.;

де: .

Задача визначення множини дерев доставки {Ts s=1,2…m}за умови (5) є узагальненням задачі побудови дерева Штейнера, і також є NP-повною. Як правило, для розв’язання задач даного типу використовуються евристичні методи. При цьому знаходиться деяке рішення, що задовольняє заданим обмеженням, у даному випадку це умова (2). Множину дерев доставки, що задовольняють даній умові, назвемо прийнятним рішенням задачі групової багатоабонентській доставки повідомлень.

У якості одного з критеріїв оцінки якості розподілу потоків у мережі розглядається рівномірність розподілу потоків. Для цього визначимо коефіцієнт завантаження Ki,j для кожного ребра дерева групової багатоабонентської доставки повідомлень:

. (6)

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

. (7)

У даному випадку достатньою умовою припустимого шляху між вершиною і будь-якою вершиною vi Vm є:

Lmax = Lmin,k +Eк , (8)

де: Lmax - максимально припустима довжина шляху; Lmin,k - відстань від джерела до найближчої вершини vк групи багатоабонентської доставки.

З урахуванням умови (1) стратегія формування дерева багатоабонентської доставки полягає в наступному:

1. Знаходиться за допомогою алгоритму Дейкстра мінімальний шлях Lmin,k до найближчої вершини vк Vm.

2. Визначаються найкоротші шляхи у середині підграфа Gm =(Vm, Em) між вершиною vк і всіма іншими вершинами vi Vm.

При Lmax Lmin,k +Eк стратегія побудови множини припустимих шляхів між вершиною 1 і множиною вершин v1 полягає в наступному:

1.За допомогою методу Дейкстра знаходиться мінімальний шлях Lmin,q до найбільш віддаленої вершини vq Vm.

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

У загальному випадку тимчасова складність алгоритму Дейкстра для перебування шляху між вершинами 1 і 1 V1 дорівнює O(rЧlog n), де: n- кількість вершин, а r- кількість ребер графа G = (V, E). У даному випадку тимчасова складність алгоритму Дейкстра перебування шляху до найближчої вершини групи багатоабонентської доставки буде дорівнювати O( (r-r1)log(n-n1)), де: r1 – кількість ребер, n1 – кількість вершин у підграфі Gm =(Vm, Em) багатоабонентської доставки.

Стійкість віртуальних з'єднань

Стійкість маршруту будемо оцінювати за допомогою коефіцієнта стійкості маршруту:

k= (T0 –TS)/T0, (9)

де: Ts – час сеансу обміну (необхідний час віртуального з'єднання); T0 – час життя маршруту, що залежить від стійкості обраного шляху.

Розглянемо питання стійкості шляху передачі інформації в мобільних мережах. Для цього представимо всю множину АС і вузли комутації у виді зв'язаного графа G = (V, E), на якому визначений підграф Gm = (Vm, Em), множини вузлів Vm =(v11, v12,…,v17), який відповідає multicast групі.

Як правило, видалення деякого ребра в графу зв’язності мобільної мережі зв'язано з переміщенням суміжної йому АС. Кожній вершині vi графа G = (V, E) зіставимо величину p(vi), що представляє собою імовірність чи видалення переміщення вершини vi . Відповідно величина q(vi) = 1- p(vi) характеризує стійкість вершини vi . У загальному випадку стійкість Qm підграфу Gm=(Vm,Em), визначається наступним виразом:

(10)

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

Попередньо розглянемо питання формування максимально стійкого шляху від джерела multicast (вершини v1) до деякої вершини vj Г(Vm), де: Vm – множин вершин multicast групи.

При формуванні максимально стійкого шляху можна використовувати алгоритм перебування мінімального шляху методом Дейкстра. У даному випадку метрика розглядається як стійкість шляху. У результаті роботи алгоритму формується деяка множина вершин VS до якої, на кожному кроці обчислення, додається вершина з множини Г(VS)={vj V\VS} вершин, суміжних з вершинами множини VS .

Алгоритм полягає в наступному:

1. Формується підмножина VS ={v1}.

2. Для усіх вершин vj Г (v1), обчислюємо S1,j = q(e1,j) і формуємо множину B={ bj} упорядкованих пар bj= (v1, S1,j) .

3. Серед вершин множини суміжності Г (v1), знаходимо вершину vj V\VS, з максимальним значенням S1,j і включаємо її до множини VS

4. Для усіх вершин vj Г (VS), обчислюємо S1,j = S1,i Ч q(ei,j) і формуємо множину B={ bj} упорядкованих пар bj= (vi, S1,j) . При цьому з двох пар bj вибирається пара з максимальним значенням S1,j.

5. Серед вершин множини суміжності Г (VS), знаходимо вершину vj V\VS, з максимальним значенням S1,j і включаємо її до множини VS .

6. Якщо V\VS , тоді перехід до пункту 4, інакше алгоритм завершує свою роботу.

У результаті формується шлях між вершинами v1 і vm з максимальним значенням S1,m.

У мобільних мережах з відносно низькою стійкістю віртуальних з'єднань пропонується формувати стійкий підграф багатоадресної доставки повідомлень. В основу формування стійкого підграфа може бути покладений приведений вище алгоритм формування максимально стійкого шляху. Основна відмінність полягає в тім, що при формуванні множини B={bj} упорядкованих пар bj= (vi, S1,j) для кожної вершини vj вибирається декілька пар bj з найбільшими значеннями S1,j, сума яких прагне до одиниці. Таким чином, замість одного шляху формується граф доставки повідомлень. Потім на даному підграфі методом лавинообразної маршрутизації здійснюється передача інформації.

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

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

Розглянемо питання формування групи багатоабонентської доставки на прикладі мережі представленої на рис. 1. У даному випадку групу багатоабонентської доставки можуть формувати вузли vi M0. Зокрема групу багатоабонентської доставки з вершиною джерела v1 і множиною одержувачів G1= {МТ2 , МТ5 , МТ6 , МТ7} складають вершини vi FG1= {v4, v6, v8, v9}. Вершини v8 і v9 у даному випадку є закінченими (листовими), тому що до них безпосередньо підключаються БС. За аналогією з процедурою формування оптимального дерева доставки повідомлень формуються наступні форвардингові таблиці для вершин множині FG1.

Форвардингова група може бути отримана в результаті процедури лавинообразного формування форвардингової групи. Суть пропонованого способу полягає в наступному.

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

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

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

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

ВИСНОВКИ

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

Основними науковими і практичним результатами дисертаційної роботи є:

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

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

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

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

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

1. Луцкий М. Г. Способы построения деревьев многоабонентской передачи информации в мобильных компьютерных сетях //Вісник національного технічного університету України “КПИ”, Інформатика, управління та обчислювальна техніка, 2003. –№ 39. –С. 24-30.

2. Луцкий М.Г. Повышение эффективности многоадресной передачи информации в мобильных компьютерных сетях // Вісник національного технічного університету України “КПИ”, Інформатика, управління та обчислювальна техніка, 2003. –№ 40. –С. 156-160.

3. Луцкий М. Г. Многоадресная передача информации в мобильных компьютерных сетях, // Вісник Кременчуцького державного політехнічного університету: Вип. 3/2003(20). ? С.22-26.

4. Луцкий М.Г. Формирование оптимального дерева многоабонентской доставки сообщений // Научные труды Донецкого национального технического университета. Выпуск 73. Серия: “Информатика, кибернетика и вычислительная техника” (ИКВТ-2003): - Донецк: ДонНТУ, 2003. С. 155-162. 

5. Луцкий М. Г., Рудаков В. Э. Модифицированный алгоритм динамической маршрутизации для эпизодических компьютерных сетей // Вісник національного технічного університету України “КПИ”, Інформатика, управління та обчислювальна техніка, 2003. –№ 40. –С. 67-75. – автором запропоновано алгоритм маршрутизації.

6. M. Mazurek, M.H. Loutskii, P. Dymora: Poprawa parametrow wielokanalowych sieci magistralowych klient-server // Zeszyty Naukowe Politechniki Rzeszowsiej, Rzeszow 2003, pp 41-53. –автором запропоновано засіб аналізу комп’ютерної мережі.

7. Луцкий М. Г., Аль Рабабах Мохамед Абдель-Кадер Использование виртуальных подсетей для маршрутизации информации в мобильных сетях // Вимірювальна та обчислювальна техніка в технологічних процесах: збірник матеріалів конференції. (Випуск № 10 (2003), 28 -31 травня 2003р. м. Хмельницький).

АНОТАЦІЇ

Луцький М.Г. Організація багатоабонентської доставки інформації у мобільних системах та мережах.– Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – “Автоматизовані системи управління та прогресивні інформаційні технології”– Національний авіаційний університет МОН України, Київ, 2004.

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

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

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

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

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

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

Луцкий М.Г. Организация многоабонентской доставки информации в мобильных системах и сетях.– Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – “Автоматизированные системы управления и прогрессивные информационные технологии”– Национальный авиационный университет МОН Украины, Киев, 2004.

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

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

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

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

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

Показано, что при значительном удалении источника от группы получателей информации целесообразно задачу формирования дерева многоабонентской доставки информации разбить на задачу формирования кратчайшего пути L(vs,v0) от вершины источника до ближайшей вершины v0, входящей в состав группы получателей информации, и задачу формирования структуры группы получателей информации с корневой вершиной v0. В этом случае вес ребер Ws дерева многоабонентской доставки информации включает в себя вес ребер WL пути до группы многоабонентской доставки информации и вес ребер W0 внутри группы.

В случае многоабонентской доставки сообщений с источником в вершине vs и множеством вершин Vm = { vii=1,2…n}, определяющих группу АС, получателей информации, задача маршрутизации состоит в нахождении дерева Ts = (Vs, Es ) доставки сообщений для которого выполняется условие:

,

Рассмотрен общий случай групповой многоабонентской доставки сообщений, при котором в качестве источника может выступать любая АС, входящая в состав группы многоабонентской доставки сообщений, то есть выполняется условие vs Bs и Bs = Vs . В этом случае вместо одного дерева формируется множество деревьев многоабонентской доставки { Ts s=1,2…m}.

Задача групповой многоабонентской доставки сообщений состоит в нахождении множества деревьев доставки {Ts s=1,2…m} для каждого из узлов группы Bs, которые удовлетворяют заданным требованиям.

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

Рассмотрен вопрос формирования максимально устойчивого пути от источника многоабонентской доставки до ближайшей вершины группы многоабонентской доставки.

При формировании максимально устойчивого пути используется алгоритм нахождения минимального пути методом Дейкстра. В данном случае в качестве метрики рассматривается устойчивость пути. В результате работы алгоритма формируется некоторое множество вершин VS к которому, на каждом шаге вычисления, добавляется вершина из множества Г(VS)={vj V\VS} вершин, смежных с вершинами множества VS . В мобильных сетях с относительно низкой устойчивостью виртуальных соединений предлагается формировать устойчивый подграф многоадресной доставки сообщений. В основу формирования устойчивого подграфа может быть положен алгоритм формирования максимально устойчивого пути.

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

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

Lutskiy M.G. – Organization of multi-user information delivery in mobile systems and networks. –Manuscript.

The dissertation on competition of a scientific Candidate's degree in Technical Science on specialty 05.13.06 – "Automated control systems and progressive information technologies".– National aviation university of MES of Ukraine, Kiyv 2004.

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.