Размещено на http://www.allbest.ru/

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

"київський політехнічний інститут"

АВТОРЕФЕРАТ

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

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

МОДЕЛІ ТА МЕТОДИ АНАЛІЗУ ХАРАКТЕРИСТИК КОМУНІКАЦІЙНИХ СИСТЕМ ГЛОБАЛЬНИХ КОМП'ЮТЕРНИХ МЕРЕЖ

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

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

Асл Руста-Ехсан

(Ісламська Республіка Іран)

Київ - 1998

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

Робота виконана у Національному технічному університеті України "Київський політехнічний інститут" (НТУУ "КПІ") на кафедрі математичних методів системного аналізу ННК "Інститут прикладного системного аналізу".

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

Зайченко Юрій Петрович.

НТУУ "КПІ", професор кафедри ММСА ННК "ІПСА"

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

Нагорний Леонід Якович.

Київський Міжнародний Університет Цивільної Авіації, завідувач кафедрою ВМСС

кандидат технічних наук, доцент Кулаков Юрій Олексійович.

НТУУ "КПІ", доцент кафедри обчислювальної техніки

Провідна організація: Інститут проблем реєстрації інформації НАН України, м. Київ. Відділ проблемно-орієнтованих інформаційно-обчислювальних систем

Захист відбудеться 28 грудня 1998 р. о 14.30 годині на засіданні спеціалізованої Ради Д 26.002.02 у Національному технічному університеті України "Київський політехнічний інститут" (м. Київ, пр. Перемоги, 37, корп.18, ауд.306)

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

Автореферат розіслано " 26 " листопада 1998 р.

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

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

Для досягнення цієї мети в дисертації вирішені такі задачі:

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

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

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

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

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

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

Автор захищає:

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

метод розподілення потоків в КМ по критерію Т_сер при додаткових обмеженнях;

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

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

централізований алгоритм адаптивної маршрутизації в КМ з комутацією пакетів.

Загальна характеристика роботи

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

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

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

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

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

Наукова новина досліджень. Полягає в такому:

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

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

запропоновано новий алгоритм розподілення потоків в мережах при додаткових обмеженнях;

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

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

Практична цінність. На основі запропонованих в дисертації моделей та алгоритмів створено інструментальний програмний комплекс аналізу комп'ютерних мереж NetBuild. Даний комплекс дозволяє вирішувати задачі аналізу часових характеристик мереж, вибору оптимальних пропускних спроможностей каналів та вузлів, оптимального розподілення потоків при додаткових обмеженнях на затримку між заданими парами вузлів мережі, аналізу показників живучості. Комплекс реалізовано на мові С++ в середовищі Windows 95 і він має гнучкий інтерфейс для роботи проектувальників. Застосування програмного комплексу надає можливості науково-обгрунтованого проектування комп'ютерних мереж, оптимізації характеристик мереж дозволяє скоротити час та вартість проектування. Обґрунтованість та вірогідність наукових висновків та практичних рекомендацій дисертації підтверджується коректним використанням математичного апарату, доведенням ряду теоретичних тверджень (теорем), а також результатами експериментальних досліджень та практичного застосування створеного комплексу.

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

Розроблені автором моделі та алгоритми використовуються в навчальному процесі на кафедрі математичних методів системного аналізу ННК "ІПСА" при НТУУ "КПІ" в курсі "Комп'ютерні мережі".

Апробація роботи. Основні положення дисертації доповідалися та обговорювалися на п'ятій національній конференції "Автоматика-98" (Київ, НТУУ "КПІ", 1998) та Першій Міжнародній конференції "Обчислювальні методи та виробництво: реальність, проблеми, перспективи", Гомель, Білорусія, жовтень 1998.

Публікації. За темою дисертації опубліковано 5 друкованих праць.

Структура та обсяг роботи. Дисертація містить вступ, чотири глави, висновки, список літератури та додатки.

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

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

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

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

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

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

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

Головний зміст роботи

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

Розглядається комунікаційна система (КС) розподіленої комп'ютерної мережі, в якій задані структура мережі у вигляді графа , де - множина вузлів мережі, - множина дуг (каналів зв'язку - КЗ) між вузлами x_i та x_j. Задані матриця вимог в передачі інформації H=||h_ij||, , де h_ij - величина потоку (пак\с.), який потрібно передавати від x_i до x_j, набір пропускних спроможностей (ПС) каналів зв'язку та їхніх питомих вартостей , де с_к - питома собівартість одиниці довжини каналу з ПС d_к. Крім того заданий набір можливих потужностей вузлів зв'язку (ВЗ) - ЦКП та їх відповідних вартостей .

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

Як бачимо, на відміну від традиційних постановок цієї задачі (Л. Клейнрок, Ю. Зайченко) ми враховуємо час затримки пакетів в вузлах (ЦКП), а також додаткові обмеження .

Припустимо, що виконуються такі основі припущення:

Вхідні потоки вимог - Пуасоновські.

Час обслуговування в КЗ розподілений за експоненціальним законом із середнім , де - ПС каналу зв'язку .

Виконується така гіпотеза "незалежності" Л. Клейнрока: час обслуговування одного і того ж пакету в різних КЗ - статистично незалежні випадкові величини.

Вважатимемо, що вузол зв'язку r описується моделлю СМО типу М/М/n/1, де n - число вхідних потоків.

В такому разі середня затримка в вузлі (r) описується таким співвідношенням , де - інтенсивність сумарного вхідного потоку у вузол r.

При прийнятих припущеннях математична модель даної задачі матиме такий вигляд:

Знайти такі пропускні спроможності каналів зв'язку та потужності ВЗ , для яких

, (1)при обмеженні

, (2)

та додаткових обмеженнях вигляду

_зад, , (3)

; .

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

Алгоритм ВПС. Алгоритм складається з послідовного застосування двох процедур відсіву та .

Процедура W₁. Вона полягає у відсіві варіантів по обмеженнях. Вибираємо поточний номер КЗ та виконуємо процедуру відсіву по обмеженню (2):

(4)

За цією процедурою відсіюються всі , де - найбільше значення , яке задовольняє (4).

Аналогічним чином виконуємо процедуру відсіву за додатковими обмеженнями (2). Відсів ПС вузла r проходить згідно умови

. (5)

Відсіюються всі значення , де - найбільше значення , для якого виконується нерівність (5).

Процедуру повторюємо з усіма КЗ та вузлами мережі. Далі переходимо до процедури .

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

1. Вибираємо на 1-ій ітерації процедури початкове значення порогу відсіву:

,

де ;

.

2. Відсів значень ПС для КЗ виконуємо згідно з умовою:

. (6)

Відсіюються всі верхні значення ПС , де - мінімальне значення, починаючи з якого виконується (6).

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

Задача розподілення потоків (РП).

Постановка та математична модель задачі.

Задані структура мережі , матриця вимог , пропускні здатності всіх каналів та продуктивності вузлів .

Потрібно розподілити потоки по всім каналам та знайти вектор багатопродуктового потоку , що відповідає , для якого

, (7)

при обмеженнях

, , (8)

де та , .

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

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

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

Позначимо глобальний потік після -ї ітерації.

К1. Вибираємо () із .

К2. Знаходимо метрику

. (9)

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

К3. Розподіляємо потік вимоги по шляху та знаходимо новий розподіл потоків: (10)

При цьому контролюємо виконання обмеження:

. (11)

Якщо умова виконується, то кінець ітерації і . Інакше знаходимо таку частину потоку ^(1), передача якої за шляхом не порушує обмежень (11), а для решти ⁽²⁾ = - ^(1), повторює кроки К1-К3.

Етап 2. На цьому етапі виконуємо розподілення потоків для решти вимог . Для цього використовуємо метод штрафних функцій. Вводиться штрафна функція

, (12)

де

К - зростаюча послідовність штрафів .

Відтак задача розподілу потоків для вимог , матиме такий вигляд.

Знайти такий розподіл потоків, для якого досягається

(13)

Задача (13) вирішується алгоритмом, запропонованим в дисертації.

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

, (14) при обмеженні

, (15)

та додаткових обмеженнях вигляду

, , (16)

; ,

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

2. Знаходження максимального потоку в комунікаційних мережах та аналіз живучості

Важливою задачею, що виникає при проектуванні комунікаційних систем розподілених обчислювальних мереж (РОМ) є задача аналізу показників її живучості. Для її розв'язання необхідна розробка адекватних моделей оцінки показників живучості в умовах відмов КЗ та ВЗ.

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

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

Задана комунікаційна мережа G = (X, E), ПС всіх каналів та матриця вимог . Потрібно знайти маршрути передачі всіх пакетів, величини зовнішніх потоків, а також розподілення потоків , для яких

, (17)

при умовах ; (18)

,; (19)

, (20)

,.

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

Теорема 1. Якщо потік є максимальним в мережі G = (X, E), то він є потоком по найкоротшим шляхам в метриці.

l_rs= ,

,

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

, (21) при умовах

, (22) та

, (23)

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

Теорема 2. Вимога домінує при передачі вимогу тоді і тільки тоді, коли для них виконується співвідношення

,

де - знак домінування.

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

Цей метод базується на алгоритмі РП і полягає в послідовному поступовому розподілу потоків від вимог в черзі їх пріоритетів і постійному контролю виконання умов (22) та (23).

3. Задача оцінки показників живучості при додаткових обмеженнях

Метод знаходження максимального потоку в КС використовується для оцінки показників живучості. Будемо оцінювати живучість показником зменшення загальної пропускної спроможності мережі (або еквівалентним зменшенням максимальної величини потоку) при відмовах каналів та вузлів в порівнянні зі станом , коли всі канали та вузли безвідмовні. Нехай - деякий стан мережі, в якому відмовив канал або вузол х_к, а максимальна величина потоку, яку можна передавати в мережі в цьому стані при обмеженнях (22) та (23) дорівнює . Її можна обчислити за допомогою розробленого алгоритму знаходження максимального потоку (МП).

Тоді живучість мережі можна охарактеризувати розподілом ймовірностей

, (24)

де 0,1; 0,2;..; 1,0.

- величина максимального потоку мережі в безвідмовному стані.

- фактична величина максимального потоку, що передається при відмовах.

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

При заданій структурі мережі G = (X, E), пропускних спроможностях всіх КЗ та вузлів , надійнісних характеристиках каналів та вузлів к_Г знайти оптимальне розподілення потоків , та визначити такі показники живучості мережі

; . ,

при виконанні додаткових умов (23).

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

Розглядаємо різні відмовні стани мережі , . (відмови одного або більшого числа КЗ та вузлів). Розраховуємо величини .

Для кожного із станів , користуючись алгоритмом МП знаходимо величину максимального потоку в мережі .

Розраховуємо величину показника живучості за формулою (24).

4. Адаптивна маршрутизація в комп'ютерних мережах

Постановка задачі. Розглядається комунікаційна мережа з комутацією пакетів, задана її структура у вигляді орграфа G={X,E}, де X={x_j} - множина вузлів мережі - центрів комутації пакетів (ЦКП), E={ (r,s) } - множина каналів зв'язку (КЗ) де (r,s) - КЗ, що зв'язує вузли x_r та x_s, матриця вимог H=||h_ij||, де h_ij - інтенсивність потоку (пак/с), який потрібно передавати від x_i до x_j, пропускні здатності КЗ {_rs}.

Основні припущення щодо мережі лишаються тими, що і раніше (гл.1,2).

Розглянемо вузол зв'язку х і позначимо його через J_х - множину сусідніх вузлів, а через J - множину всіх вузлів призначення J={A,B,.,Z}.

Потрібно для кожного вузла х

Побудувати такі маршрутні таблиці T=||t_mn|| та P=||p_ij|| де i є J_x, j є J, щоб

Т_ij = S?t_rsа min,

(r,s) є {М_ij},

де м_ij - множина шляхів від вузла x_i до вузла x_j, t_rs - затримка в КЗ (r,s).

2. Корегувати матриці P та Т так, щоб при довільному змінюванні матриці вимог H=||h_ij||, відмовах каналів та вузлів і відповідно поточних навантажень каналів зв'язку забезпечити виконання умови T_ijаmin.

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

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

Для опису даного алгоритму розглянемо фрагмент мережі, виберемо ЦКП в вузлі А. Позначимо множину індексів каналів, що виходять з ЦКП А J_A, тоді J_A={i_x, i_y, i_z}, де і_к - індекс фізичного каналу, що зв'язує вузол ЦКП А з вузлом k є {x,y,z}.

В ЦКП містяться такі маршрутні таблиці: основна таблиця маршрутизації Т1=||p_ij|| i є J_A, j є J, де J_A - множина каналів, що виходять з вузла А, J={j} - множина адресів (індексів) вузлів призначення, p_ij ^{(A) -} приоритет канала і для передачі інформації у вузол j із вузла А. Основна таблиця будується і корегується на основі допоміжної таблиці сумарних затримок Т2 та таблиці найкоротших маршрутів Т3. Таблиця Т2=||T_ij ^(A) ||, i є J_A, j є J, складається з середніх сумарних затримок при передачі пакетів із вузла і А у вузол j по каналу i. Крім того, в Т2 міститься додатковий стовпець t_срі, де t_срі - середня затримка в доставці пакетів по каналу і, яка може оцінюватися за величиною середнього завантаження в каналі - r_i. Зокрема при фіксованій довжині пакета (кадру) і швидкості передачі в КЗ і m_i біт/c маємо:

.

По таблиці Т2 будується таблиця мінімальних маршрутів, куди записуються мінімальні елементи відповідних стовпців T_j ^(A) _min = min T_ij ^(A).

А також номер відповідного каналу і_j ^(A) = argmin T_ij ^(A), j є J, що визначає оптимальний маршрут передачі пакетів із вузла А у вузол призначення j.

На підставі Т2 заповнюється таблиця Т1 таким чином:

Проглянемо j-тий стовпець Т2 і проранжуємо величини T_ij, по зростанню, хай T_i1j ^(A) T_i2j ^(A) . T_ikj ^(A). Тоді перевизначимо j-тий стовпець Е1 за правилом P_i1j=0, P_i2j=1, P_i3j=2, і т.п.

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

На попередньому етапі будуються початкові таблиці Т1, Т2, Т3 для початкового моменту часу t0. Через заданий інтервал часу Т в момент t1=t0+T, збирається поточна статистика по всіх КЗ ЦКП А, зокрема по величинах завантажень ri (Т) в момент t1, обчислюється затримка в каналі і середній час в КЗ

.

Знаходимо Dti (t1) = ti (t1) - ti (t0) i є J.

Порівнюємо величину Dti (t1) із заданим порогом T_tⁱ. Якщо |Dti (t1) | T_t^i, то корекція таблиць не виконується. Якщо |Dti (t1) | >T_tⁱ то коригуємо і-ту строку таблиці Т2.

На основі інформації в таблиці Т2 коригується таблиця Т1 і перевіряється таблиця Т3. Якщо елементи табл. Т3 вузла не змінюються, тобто T_j^X (t1) = T_j^X (t0), то цей вузол далі ніяких операцій не виконує. В протилежному випадку ЦКП розсилає по вихідним каналам службову інформацію всім сусіднім вузлам про свої нові затримки у вигляді службових пакетів формату {T_j^X (t1); i_j^X (t1) }.

На основі запропонованого алгоритму була реалізована програма імітаційного моделювання для мережі з комутацією пакетів з протоколом Х.25. Результати моделювання адаптивного алгоритму маршрутизації та його порівняльного аналізу з статичним алгоритмом містяться в дисертації.

Експериментальні дослідження

На основі запропонованих в дисертації моделей та алгоритмів був розроблений програмний комплекс NetBuild на мові С++ в операційному середовищі Windows 95, що реалізує алгоритми аналізу часових характеристик та живучості розподілених обчислювальних мереж і проведені експериментальні дослідження.

В процесі експериментів вирішувалися задачі аналізу часових характеристик РП, ВПС та ВПС РП з урахуванням додаткових обмежень на час затримки пакетів між заданими вузлами мережі. В процесі експериментів з алгоритмом РП були знайдені залежності , k=0.11.2 без додаткових обмежень та з їх урахуванням. В результаті експериментів з програмою ВПС РП було знайдено залежність (вартість мережі від загальної ПС мережі) при варіаціях додаткових обмежень. Крім того, проведені експериментальні дослідження алгоритму аналізу показників живучості мереж. Проведені експерименти підтвердили працездатність та ефективність запропонованих методів та алгоритмі аналізу та оптимізації характеристик мереж.

Пакет NetBuild було використано для аналізу характеристик глобальної комп'ютерної мережі Міносвіти України при виконанні ескізного проекту мережі. В результаті застосування пакету були знайдено часові характеристики мережі, її вартість в залежності від загальної пропускної спроможності при різних обмеженнях на Т_сер, а також розподілення потоків.

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

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

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

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

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

алгоритм часова характеристика живучість

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

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

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

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

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

1. Зайченко Ю.П., Эхсан Асл Руста. Анализ и оптимизация временных характеристик распределенных вычислительных сетей при дополнительных ограничениях. // "Проблемы информатизации и управления". Сб. н. тр., вип.3. - К.: КМУГА, 1998, с.327-343.

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

2. Ехсан Асл Руста. Задача розподілу потоків в комунікаційних мережах при додаткових обмеженнях на час доставки пакетів. // Наукові вісті НТУУ "КПІ", 1998, №2, c.40-45.

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

3. Зайченко Ю.П., Эхсан Асл Руста. Анализ показателей живучести коммуникационных сетей с ограничениями на время доставки. // "Проблеми підвищення ефективності інфраструктури": Зб. н. пр. - К.: КМУЦА, 1998, с.118-130.

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

4. Зайченко Ю.П., Зайчикова О.В., Эхсан Асл Руста. Алгоритмы адаптивной маршрутизации в коммуникационных сетях. // "Проблеми підвищення ефективності інфраструктури": Зб. н. пр. - К.: КМУЦА, 1998, с.130-144.

Запропоновано централізований алгоритм адаптивної маршрутизації в коммуникаційних мережах.

5. Зайченко Ю.П., Эхсан Асл Руста. Анализ временных характеристик распределенных вычислительных сетей. В сб. докладов 5-й национальной конференции "Автоматика-98", Киев, 1998. c111-116.

Анатоції

Запропонований алгоритм ВПС РП при додаткових обмеженнях.

Ехсан Асл Руста

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

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

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

Эхсан Асл Руста

Модели и методы анализа временных характеристик и живучести коммуникационных сетей.

Работа является рукописью на соискание научной степени кандидата технических наук по специальности 05.13.13 - вычислительные машины, системы и сети. Киев, 1998, Национальный технический университет Украины "КПИ".

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

Ehsan Asl Rusta

Models and methods of analysis of communication systems of global computer networks.

This scientific work is a manuscript of Ph. D. dissertation submitted for getting the Ph. D. degree in the speciality 05.13.13 - computers, computer systems and networks. Kiev, 1998, National Technical University of Ukraine "KPI"

The goals of the thesis are to develop new models, algorithms and software tools for analysis and optimization of global computer networks characteristics. The suggested models and methods enable to introduce additional constraints on mean packets delays between the given pairs of nodes and optimize the performance characteristics of global computer networks.

Размещено на Allbest.ru