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

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

Халіль Хамді Атіє Аль Шкерат

(Йорданія)

УДК 681.3

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

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

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

А В Т О Р Е Ф Е Р А Т

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

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

Київ - 2004 р.

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

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

Науковий керівник: | кандидат технічних наук, доцент

Кулаков Юрій Олексійович,

НТУУ "КПІ", доцент кафедри ОТ.

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

Тоценко Віталій Георгійович, Інститут проблем реєстрації інформації НАН України, завідувач відділу надійності та діагностики.

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

Коваленко Анатолій Єпіфанович,

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

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

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

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

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

Автореферат розісланий "_14_"_квітня_ 2004 р.

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в 2000-2003 рр. відповідно до планів науково-дослідних робіт кафедри обчислювальної техніки НТУУ "КПІ": НДР № 0100U000703 "Розробка теорії, методів і засобів побудови обчислювальних систем з масовим розпаралелюванням обчислювального процесу" і в рамках НДР № 0102U000333 "Побудова масштабованих ізоефективних комп'ютерних систем", яка виконується на кафедрі обчислювальної техніки НТУУ "КПІ" в 2002-2004 рр.

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

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

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

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

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

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

3. Теоретичне обґрунтування і розробка способу побудови дерева доставки повідомлень, що забезпечує мінімальну зміну первісного маршруту.

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

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

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

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

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

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

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

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

1.

2.

3.

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

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

2. Четвертій міжнародній науково–практичній конференції "Сучасні інформаційні й електронні технології" (19-23 травня 2003р., м. Одеса).

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

Структура й обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків і додатку. Загальний обсяг роботи складає 125 сторінок друкованого тексту, 47 рисунків, 3 таблиці, і списку використаної літератури з 73 найменувань.

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

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

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

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

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

Більшість відомих способів вибору структури мережі й пропускної спроможності каналів зв'язку використовують потокові моделі, засновані на інтенсивностях Fi,j трафіка в каналах ei,j мережі. Як функцію оптимізації в більшості випадків вибирають вартісну функцію вигляду: , де кожна функція Di,j є монотонно зростаючою. При цьому для обчислення Di,j (F i,j) використовується вираз: де Ci,j пропускна спроможність каналу зв'язку ei,j, tu – затримка обробки і поширення. Передбачається, що трафік потоку, що надходить у будь-який канал ei,j, змінюється тільки через відновлення маршрутів. Таке припущення є коректним, коли зміна трафіка відбувається відносно повільно в порівнянні з середнім часом, необхідним для зменшення черг у мережі, і коли потоки в лініях виміряються шляхом часового усереднення.

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

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

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

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

Комп'ютерна мережа представлена у вигляді навантаженого графа G(V, E), де V= { vi i=1,2…m} - множина вершин графа, E={ei,j i,j=1,2…m}–множина ребер графа. Кожне ребро ei,j графа характеризується вагою wi,j. При розгляді питань маршрутизації у магістральних мережах під вагою wi,j ребра ei,j мається на увазі затримка ti,j одиниці інформації між вузлами мережі vi і vj. Обмеженням виступає значення припустимої затримки td доставки одиниці інформації між довільними вузлами мережі, а як параметр оптимізації розглядається сумарна затримка Ts,r на шляху Ls,r. В даному випадку завдання маршрутизації полягає в знаходженні шляху L(vs,vr)= (es,i, …, ej,r) між вершинами vs і vr для якого виконується умова:

де: Ts,r - сумарна затримка на шляху L(vs,vr).

У якості обмежень на включення ребра ei,j до складу шляху Ls,r розглядаються умови:

· C(i,j) cs, де: C(i,j) - пропускна спроможності каналу; cs - необхідне значення пропускної спроможності для доставки повідомлень шляхом Ls,r.

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

Відповідно до дворівневої структури корпоративної мережі, граф G(V, E) може бути представлений у вигляді графа G0 (V0, E0), що визначає структуру магістральної підмережі, і деякої множини підграфів {Gi(Vi, Ei) i=1,…,n}, що відповідає локальним підмережам корпоративної мережі.

В загальному випадку, для вершини vsV1 підграфа G1 = (V1,E1) і вершини vrV2 підграфа G2 = (V2,E2), а також граничних вершин vkV1 ( ek,i , v iV0) і vmV2 ( em,j ,vjV0 ), шлях L(vs,vr) визначається виразом: L(vs,vr) = L1(vs,vk)+ L0(vk,vm) + L1(vm,vr) . Відповідно сумарна затримка Ts,r шляху L(vs,vr) дорівнює:

При перебуванні вершини джерела чи приймача всередині магістральної мережі відповідний доданок у виразі (2) відсутній. Наприклад, при vsV0 шлях L(vs,vr) = L0(vs,vm) + L1(vm,vr), відповідно:

При перебуванні джерела і приймача в одній локальній мережі, тобто при vsV1 і vrV1 , шлях L(vs,vr) = L1(vs,vr) , а величина Ts,r дорівнює:

Якщо швидкість передачі інформації в локальних підмережах вища швидкості передачі інформації в глобальних мережах, при L0(vs,vm) = L1(vm,vr), де: L0(vs,vm) - довжина шляху на ділянці глобальної мережі; L1(vm,vr) - довжина шляху на ділянці локальної мережі, виконується умова:

При розташуванні джерела й адресата в різних локальних мережах на значній відстані один від одного: .

В цьому випадку Ts,r Tk,m і, відповідно:

Звідси випливає, що в даному випадку основну увагу необхідно приділяти питанням побудови оптимального шляху на графі G0 (V0, E0). При переміщенні мобільного абонента між локальними підмережами, представленими відповідно підграфами G1 = (V1,E1) і G2 = (V2,E2), у графі G0 (V0, E0) відбувається зміна початкового шляху L0(vk,vm) новим шляхом L1(vk,vl). Гранична вершина vi підграфа G2 = (V2,E2), визначається за умовою vkV2 (ek,i,viV0). Припустимо, що шлях L0(vk,vm) складається з множин ребер EL0={ei,jL0(vk,vm), а шлях L1(vk,vl) складається з множин ребер EL1={ei,jL0(vk,vm). В результаті переміщення мобільного абонента деяка множина ребер Em EL0 заміняється новою множиною ребер El EL1. Об'єднання цих множин утворить множину Es ребер, що бере участь у процесі реконфігурації шляху. Потужність множини Es характеризує часову складність процедури реконфігурації вихідного шляху. Множина Es визначається наступним виразом:

Якщо шляхи L0(vk,vm) і L1(vk,vl) не співпадають, то EL0 EL1 =. В цьому випадку потужність множини Es буде максимальною. При формуванні маршруту L1(vk,vl) за рахунок продовження вихідного маршруту L0(vk,vm) потужність QS множини Es буде мінімальною. Припустимо, що в результаті зміни маршруту додається ребро ei,j. В цьому випадку множину ребер EL1={ EL0, ei,j} можна представити у вигляді EL1= EL0 {ei,j}. Таким чином: Es= (EL0 (EL0 {ei,j}))\ (EL0 (EL0 {ei,j})) =(EL0 ei,j)\ EL0 = {ei,j}.

При переміщенні мобільного абонента між декількома локальними мережами формується множина шляхів { Li(vk,vj) i=0,…,(n-1); j=p,…q} між початковою вершиною vk і вершинами множини Vr = { vj j=p,…q}, що відповідають переміщенню мобільного абонента. У даному випадку:

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

де: QLi - потужність множини ELi. Значення коефіцієнта ks змінюється в межах (0 1). При ks 0 реконфігурація буде мінімальною. При ks =1 шлях перебудовується повністю. Як випливає з виразу (9), ks 0 при QS 0. В свою чергу, величина QS визначається кількістю ребер, що формують шлях між вершинами vp і vq. Значення QS буде мінімальним тільки для найкоротшого шляху між вершинами vp і vq. Потім сформуємо найкоротший шлях від початкової вершини до найближчої вершини з множини вершин приймачів інформації. В результаті з множини шляхів буде сформоване остове дерево STk(Vk,Ek) з початковою вершиною vk і мінімальним значенням ks. Таким чином, задача формування маршрутів доставки інформації за критерієм часової складності ремаршрутизації зводиться до задачі побудови остового дерева з мінімальним числом ребер. Вирішення цієї задачі зручно розпочинати зі знаходження найкоротшого шляху від вершини vk до найближчої вершини vm Vr.

Алгоритм формування дерева

1. За допомогою алгоритму Дейкстри визначається мінімальний шлях L0(vk,vm) від вершини vk до найближчої вершини vm Vr.

2. Вершина vm вилучається із множини Vr і включається в множину EL0, тобто vm Vr vm EL0.

3. Серед решти вершин множини Vr визначається вершина vi Vr , найближча до однієї з вершин vj EL0. За умови, що шлях L0(vk,vm) мінімальний, вершиною vj виступатиме вершина vm.

4. Формується шлях L1(vk,vi) = L0(vk,vm)+ em,i.

5. Вершина vi вилучається із множини Vr і включається в множину EL1, тобто vi Vr vi EL1.

6. Серед решти вершин множини Vr визначається вершина vi+1 Vr , найближча до однієї з вершин vj EL0 або vl EL1.

7. При ei,j > ei,l формується шлях L1(vk,vi+1) = L1(vk,vl)+ el,i+1 інакше подовжується шлях L0(vk,vi+1)= L0(vk,vm)+ ej,i+1.

8. Вершина vi+1 вилучається із множини Vr і включається в множину EL1 або множину EL0.

9. При Vr перехід до пункту 6.

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

В даному випадку формуються два шляхи L0(vk,vp) і L1(vk,vq) від вершини vk до крайніх вершин vp і vq. У випадку, коли в якості однієї з вершин vp чи vq виступає vm, формується тільки один шлях L0(vk,vp) або L0(vk,vq).

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

Для врахування обмеження на затримку передачі в пунктах 3 і 6 алгоритму формування дерева доставки при виборі вершини дерева, до якої підключаться нова вершина, додатково перевіряється умова td tm. При виконанні цієї умови виконується підключення вершини. В протилежному випадку як претендент на підключення вибирається наступна вершина раніше сформованого дерева і так далі. У кращому випадку, як і без врахування умови td tm , буде сформований тільки один шлях, що зв'язує усі вершини множини Vr з вершиною vk. У гіршому випадку, при жорстких обмеженнях на затримку передачі, дерево доставки може бути сформоване тільки за умови EL0 EL1 … EL(n-1) =. При цьому задача реконфігурації віртуального каналу зводиться до повної ремаршрутизації.

Даний результат може бути узагальнений на випадок, коли і вершина vs переміщується. У цьому випадку дерево STk(Vk,Ek) доповнюється новими вершинами з множини Vs .

Алгоритм формування дерева доставки може бути використаний і для випадку, коли джерело ( вершина vs) переміщується. В цьому випадку в рамках підграфа G0 (V0, E0) формується множина Vs = { vz z=k,…h}, що відображає переміщення vs. В результаті дерево STk(Vk,Ek) доповнюється новими вершинами з множини Vs V0 . Підключення вершин vz Vs здійснюється відносно вершини vk у відповідності до приведеного вище алгоритму.

В третьому розділі розглядаються питання формування віртуальної структури корпоративної мережі. На рівні магістральної підмережі підграфа G0 (V0, E0) ця задача зводиться до задачі об'єднання остових підграфів у єдиний підграф Gd (Vd, Ed), оптимальний з точки зору обраних критеріїв та обмежень. На рівні локальних мереж дана задача зводиться до задачі формування віртуальних підмереж з мінімальним потоками між підмережами. При цьому враховується область переміщення мобільного абонента. Вихідними даними є інтенсивність інформаційних потоків, характер переміщення й імовірність перебування мобільного абонента у тій чи іншій локальній мережі. Задача вирішується щодо всіх мобільних абонентів, які входять до складу корпоративної мережі, при цьому замість одного дерева формується множина дерев доставки ST0 ={ STk(Vk,Ek) k=1,2,…,m}.

Задача зводиться до об'єднання множини дерев доставки ST0 у підграф Gd (Vd, Ed) , що задовольняє наступним вимогам:

При об'єднанні дерев STk(Vk,Ek) виникає задача розподілу потоків. З цією метою для кожного ребра ei,j дерева STk(Vk,Ek) передачі інформації будемо використовувати наступний коефіцієнт завантаження Ri,j

З урахуванням виразу (12), коефіцієнт завантаження R всього дерева доставки повідомлень:

Далі визначимо варіацію коефіцієнта завантаження мережі:

де Np– кількість ребер дерева доставки. Для оптимального завантаження мережі необхідно, щоб 0.

В роботі пропонується наступний алгоритм формування підграфа доставки повідомлень Gd (Vd, Ed) в рамках підграфа G0 (V0, E0) .

Алгоритм об'єднання множини дерев в підграф.

1. Початок.

2. У множині ST0 ={ STk(Vk,Ek) k=1,2…m} дерев доставки вибираємо дерево STi(Vi,Ei) з максимальним діаметром Di.

3. Надаємо значення Dmax = Di.

4. Приймаємо Gd (Vd, Ed) = STi(Vi,Ei).

5. Формуємо множину ST0 = ST0 \ STi(Vi,Ei).

6. Серед дерев STi(Vi,Ei) ST0 обираємо дерево STj(Vj,Ej) з максимальним значенням Ed Ej.

7. Доповнюємо граф Gd (Vd, Ed) множиною вершин Vj і множиною ребер Ej .

8. При виконанні умови (11) переходимо до пункту 11.

9. Між кінцевими вершинами перевантаженої ділянки шляху формуємо додатковий шлях.

10. Множина ребер Ed доповнюється новими ребрами.

11. Граф перевіряється на надмірність, здійснюється оптимізація структури графа.

12. ST0 = ST0 \ STj(Vj,Ej).

13. Якщо ST0 , то переходимо до пункту 5.

14. Кінець.

В деяких випадках, структура сформованого графа Gd (Vd, Ed) може виявитися однозв'язаною, тоді як умови забезпечення надійності вимагають, щоб вона була двозв'язаною і не містила висячих вершин і ребер зчленування. З цією метою до вершин зі ступенем рівним одиниці додаються нові ребра. Результатом може стати надлишкова структура, оптимізація якої здійснюється шляхом вилучення ребер у вершинах зі ступенем більше двох, з урахуванням виразів (11) і (14).

Формування локальних віртуальних підмереж здійснюється на основі ряду критеріїв, серед яких одним з основних є відношення інтенсивності зовнішніх потоків до інтенсивності внутрішніх потоків. Як обмеження тут можуть виступати обмеження на діаметр графа і завантаження каналів передачі даних. Запропоновано й обґрунтований алгоритм формування локальних віртуальних підмереж з урахуванням відносини k інтенсивності i+ внутрішніх потоків до інтенсивності i- зовнішніх потоків підграфа Gi(Vi, Ei). Як обмеження виступають обмеження на діаметр підграфа і завантаження каналів передачі даних. Основною операцією алгоритму є послідовне формування множин Vi з k > 1. Як перший елемент множини V1 вибирається вершина vi з максимальною інтенсивністю потоків. Потім з вершин множини V\V1 вибирається вершина vj з максимальним значенням k щодо множини {V1, vi }. На другому і наступному кроках аналогічно здійснюється включення чергових вершин vi V\V1 у множину V1. Процес формування множини V1 закінчується при відсутності вершин vi V\V1 зі значенням k > 1.

В четвертому розділі на прикладі технології АТМ розглядаються питання організації і підтримки віртуальних каналів. На основі аналізу відомих способів організації передачі даних, а також, з огляду на характерні особливості мобільних корпоративних мереж, розроблено адаптивний алгоритм маршрутизації. Формування шляху здійснюється в рамках віртуальної підмережі з мінімальною кількістю ребер, що сформована з урахуванням можливого переміщення мобільного абонента. Це дозволяє скоротити час і підвищити ефективність процедури маршрутизації. Формування дерева доставки STk(Vk,Ek) в рамках віртуальної підмережі здійснюється аналогічно алгоритму1, з урахуванням імовірності перебування мобільного абонента у тій чи іншій локальний підмережі. Це дозволяє сформувати шлях передачі інформації, з мінімальною часовою складністю його реконфігурації. На рис. 1 і рис. 2 наведені значення часової складності ремаршрутизації при різних способах формування дерева доставки інформації і різних мережевих топологіях. В якості початкової структури обрана повнозв'язана структура. Кожна нова структура формується з попередньої, шляхом вилучення окремих ребер у попередній структурі.

На рис. 1 представлена залежність часової складності при формуванні дерева доставки з трьома рівнями. На рис. 2 – для дерева з 10 рівнями. Як випливає з рис. 1 і рис. 2, зі збільшенням числа рівнів ефективність запропонованого способу перевищує ефективність способу, заснованого на алгоритмі Дейкстри.

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

де: tp,g - час передачі комірок по ребру ep,g на шляху LZ (vk,vm) переміщення мобільного абонента між зовнішніми маршрутизаторами і vm суміжних локальних підмереж. Оптимізація маршруту, а також виключення його зациклення здійснюється шляхом реконфігурації (переключення) раніше доданих ділянок шляху. На основі аналізу відомих схем переключення, в роботі пропонується схема адаптивного переключення, що є модифікацією схеми безрозривного переключення на базі аналізу переміщення мобільного абонента. На основі запропонованого способу ремаршрутизації розроблено адаптивний алгоритм маршрутизації. Проведено дослідження ефективності обраних рішень у залежності від мобільності мобільного абонента, їх концентрації й інтенсивності трафіка. Для оцінки ефективності використовувався коефіцієнт ефективності, що дорівнює відношенню числа передач пакетів даних до загального числа передач: KЭФ=VД/V0. Для оцінки завантаження використовувався коефіцієнт завантаження, що дорівнює відношенню загального числа передач до сумарної пропускної спроможності мережі: КЗ=V0/W.

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

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

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

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

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

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

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

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

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

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

1. Халиль Х. А. Аль Шкерат. Алгоритмы маршрутизации в мобильных сетях // Гірнича електромеханіка та автоматика: Наук.- техн. Зб. – 2002. – Вип. 69. – С. 94 - 100.

2. Кулаков Ю.А., Гайдукова Л., Халиль Х. А. Аль Шкерат. Способы повышения эффективности качества обслуживания (QoS) в многофункциональных сетях // Вісник НТУУ “КПІ” Інформатика, управління та обчислювальна техніка. – 2002. - № 39. - С. 132 - 141. – автору належить алгоритм підвищення якості обслуговування в комп'ютерних мережах

3. Кулаков Ю.А., Халиль Х. А. Аль Шкерат. Формирование структуры корпоративной сети // Гірнича електромеханіка та автоматика: Наук.- техн. Зб. – 2003. – Вип. 70. – С. 86 - 91. - автором запропоновано засіб формування структури корпоративної мережі.

4. Кулаков Ю.А., Халиль Х.А. Аль Шкерат. Процедура обмена управляющей информацией при перемещении абонентских систем мобильной сети // Вестник НТУ “ХПИ” сборник научных трудов, тематический выпуск “Энергетика и преобразовательная техника”. – 2004. - № 4. - С. 97 - 102. – автору належить аналіз процедур та засобів обміну управляючою інформацією.

5. Кулаков Ю.А. , Аль-Офейшат Хусейн Ахмед Ал-Фади, Халиль Х. А. Аль Шкерат. Способы повышения эффективности виртуальных соединений в мобильных компьютерных сетях. Труды четвертой международной научно-практической конференции "Современные информационные и электронные технологии" (19–23 мая 2003 г. г. Одесса. Украина). – автором запропоновано алгоритм підвищення ефективності віртуальних з’єднань.

6. Кулаков Ю.А. , Аль-Офейшат Хусейн Ахмед Ал-Фади, Халиль Х. А. Аль Шкерат. Обеспечение требуемого качества обслуживания в мобильных сетях. Вимірювальна та обчислювальна техніка в технологічних процесах: збірник матеріалів конференції. (Випуск № 10 (2003) 28 -31 травня 2003 р. М. Хмельницький). ). – автором запропоновано засіб забезпечення заданої якості обслуговування.

АНОТАЦІЇ

Халіль Хамді Атіє Аль Шкерат. Спосіб і засоби організації віртуальних підмереж в мобільних корпоративних мережах. – Рукопис.

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

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

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

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

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

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

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

Халил Хамди Атие Аль Шкерат “Способ и средства организации виртуальных подсетей в мобильных корпоративных сетях ” Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети. Национальный технический университет Украины “ Киевский политехнический институт”, Киев 2004.

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

Корпоративная сеть состоит из локальных сетей, связанных между собой магистральной подсистемой передачи данных. В соответствие с этим граф G(V, E), отражающий структуру корпоративной сети, представлен в виде подграфа G0 (V0, E0), определяющего структуру магистральной подсети, и некоторого множества подграфов {Gi(Vi, Ei) i=1,…,n}, соответствующего локальным подсетям корпоративной сети. Таким образом, задача синтеза структуры корпоративной сети подразделяется на задачу синтеза магистральной подсети и локальных подсетей. Приведен краткий обзор и анализ известных методов синтеза локальных сетей и подсети связи с точки зрения эффективности использования их для синтеза структуры мобильной корпоративной сети. В качестве основного параметра оптимизации структуры мобильной корпоративной сети рассматривается время реконфигурации виртуальных соединений.

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

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

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

Рассмотрены вопросы формирования виртуальной структуры корпоративной сети на уровне магистральной сети и локальных подсетей. На уровне магистральной подсети задача сводиться к объединению множества деревьев доставки информации в рамках подграфа G0 (V0, E0). Задача решается относительно всех мобильных абонентов, входящий в состав корпоративной сети, при этом формируется множество деревьев доставки ST0 ={ STk(Vk,Ek) k=1,2…m}. Затем осуществляется объединение множества деревьев доставки ST0 в подграф Gd (Vd, Ed) , удовлетворяющий следующим требованиям:

Предложен и обоснован алгоритм формирования локальных виртуальных подсетей с учетом отношения k интенсивности i+ внутренних потоков к интенсивности i- внешних потоков подграфа Gi(Vi, Ei). В качестве ограничений выступают ограничения на диаметр подграфа и загрузка каналов передачи данных. Основной операцией алгоритма является последовательное формирование множеств Vi с k > 1. В качестве исходного множества V1 выбирается вершина vi с максимальной интенсивностью потоков. Затем из вершин множества V\V1 выбирается вершина vj с максимальным значением k относительно множества {V1, vi }. На втором и последующих шагах аналогичным образом осуществляется включение очередных вершин в множество V1. Процесс формирования множества V1 заканчивается при отсутствии вершин vi V\V1 со значением k > 1.

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

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

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

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

Khalil Hamdi Ateyeh Al Shqeerat, “Methods and means of networking the Virtual Sub-networks in Mobile Corporative Networks”. The dissertation is submitted to obtain the Scientific Degree of Candidate of Technical Science on specialty 05.13.13 – computers, computing systems and networks. National Technical University of Ukraine “Kiev Polytechnic Institute”, Kiev 2004

Dissertational work dedicated to development and research of methods and means directed at increasing the productivity of Mobile Corporative Networks owing to the effective networking of Virtual Sub-Networks.

A new approach to formation of the Mobile Corporative Networks structure, which allows for the necessity of the Virtual Channel reconfiguration in connection with displacement of subscriber systems, has been proposed and substantiated.

An algorithm of delivery tree construction, allowing a reduction of re-routing time, has been proposed and substantiated.

An adaptive algorithm of routing, which, in comparison with the known algorithms, allows an increase of the Mobile Computer Networks operating benefits owing to reduction of re-routing time, has been substantiated and developed.

Practically, the results coming from this work enable to significantly increase the operating benefits of wireless computer networks.

Keywords: the mobile corporative network, a routing, virtual path, virtual network.