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

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

МАРТИНОВА Оксана Петрівна

УДК 004.7 (043.3)

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

05.13.13 – Обчислювальні машини, системи та мережі

Автореферат

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

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

Київ – 2004

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

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

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

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

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

доктор технічних наук, професор

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

кандидат технічних наук, старший науковий співробітник Чемерис Олександр Анатолійович, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, вчений секретар.

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

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

Захист відбудеться “ 15 ” жовтня 2004 р. о . 1300 годині на засіданні спеціалізованої вченої ради Д 26.062.07 Національного авіаційного університету за адресою: 03058, м. Київ, просп. Космонавта Комарова, 1.

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

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

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

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

кандидат технічних наук Алєксєєва Л.О.

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

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

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

Останнім часом поряд із традиційними комп'ютерними даними велику частку трафіку складають мультимедійні дані.

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

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

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

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

Зв’язок роботи з науковими програмами, планами,
темами. Робота виконувалась у рамках наукових досліджень Центрального НДІ навігації і управління при реалізації НДР “Транспорт” та НДДКР № 4924/07-2-99 від 22.07.99 р. “Розробка засобів картографування врожайності” (Технічне забезпечення системи точного землеробства), шифр “Міус”, № держ. реєстр. 0199U004525, яка виконується ЦНДІ НіУ в рамках “Програми виробництва технологічних комплексів машин і обладнання для агропромислового комплексу на 1998 – 2005 роки”, схваленої постановою КМ України № від 30.03.1998 р. Тематика дисертації пов'язана також з науковими дослідженнями в Національному авіаційному університеті при виконанні держбюджетної НДР “Дослідження принципів побудови паралельних обчислювальних структур для розв'язання задач великої розмірності” за номером державної реєстрації № U003737.

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

Для досягнення поставленої мети в дисертації були розв'язані такі задачі:

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

2. Розробка системоаналогового методу маршрутизації на графах.

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

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

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

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

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

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

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

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

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

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

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

Отримані результати дисертаційної роботи були впроваджені в Центральному НДІ навігації і управління при реалізації НДР “Транспорт” та НДДКР № 4924/07-2-99 від 22.07.99 р. “Розробка засобів картографування врожайності”, (Технічне забезпечення системи точного землеробства) шифр “Міус”. Результати досліджень також включено до навчального курсу “Організація інформаційно-обчислювальних процесів і систем”, що викладається на кафедрі комп’ютерних систем Житомирського військового інституту радіоелектроніки.

Особистий внесок здобувача. У роботах, написаних у співавторстві, автору належать: метод побудови паралельних структур для знаходження багатьох маршрутів [1]; дослідження і аналіз особливостей передачі мультимедійних даних та властивостей мультимедійних технологій [2, 3, 7, 9, 10]; системоаналоговий алгоритм моделювання паралельних маршрутів [4]; системоаналоговий метод багатошляхової маршрутизації на графах [5, 13, 14]; системоаналоговий принцип моделювання та управління [6]; реалізація системоаналогового методу та алгоритму [8]; дослідження особливостей методів доступу в локальних мережах [11]; алгоритм роботи прозорого моста [12].

Апробація результатів дисертації. Основні результати роботи доповідались та обговорювались на Міжнародній науковій конференції студентів та молодих учених “Авіація, космонавтика, електронні системи та технології” (Національний авіаційний університет, Київ, Україна, 2002), IV Міжнародній науково-технічній конференції “АВІА-2002” (Національний авіаційний університет, Київ, Україна, 2002), V Міжнародній науково-технічній конференції “АВІА-2003” (Національний авіаційний університет, Київ, Україна, 2003), IV Міжнародній молодіжної науково-практичної конференції “Людина і космос” (Дніпропетровськ, Україна, 2004), Міжнародній науковій конференції студентів та молодих учених “ПОЛІТ-2003” (Національний авіаційний університет, Київ, Україна, 2003), науково-технічній конференції “Наукові проблеми розробки, модернізації та застосування інформаційних систем космічного і наземного базування” (Житомирський військовий інститут радіоелектроніки, Житомир, Україна, 2004), VI Міжнародній науково-технічній конференції “АВІА-2004” (Національний авіаційний університет, Київ, Україна, 2004).

Публікації. Основні результати дисертації викладено в 14 наукових працях, із них 6 – у фахових виданнях [1-6] та 8 – у матеріалах конференцій [7-14].

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, що містять основні результати, списку використаної літератури з 93 найменувань, двох актів впровадження, 28 рисунків та 4 таблиць – всього на 149 сторінках. Основний текст дисертації викладено на 129 сторінках.

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

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

У першому розділі розглянуто особливості передавання мультимедійної інформації в комп'ютерних мережах. Установлено, що головною особливістю мультимедійного трафіку є наявність твердих вимог до синхронності переданих повідомлень. Мультимедійний трафік, що передає голос або зображення, має високу чутливість до затримок передавання даних. У зв'язку з цим для перетворення сучасних комп'ютерних мереж у мультимедіа-інфраструктуру необхідно виключити перевантаження комп'ютерної мережі шляхом оптимізації маршрутів передавання даних від вузла-джерела вузлу-адресату по декількох паралельних найкоротших маршрутах, що забезпечує зменшення тимчасового запізнювання в процесі передавання даних. У цьому напрямі виконано аналіз рішення задачі багатошляхової маршрутизації в комп'ютерних мережах. Серед задач маршрутизації виділено задачі одношляхової і К-шляхової маршрутизації, де К > 1 визначає кількість маршрутів, що зв'язують джерело даних з адресатом. Розглянуто відомі методи й алгоритми рішення задач одношляхової і К-шляхової маршрутизації. Аналіз відомих методів і алгоритмів знаходження найкоротших шляхів між парою вузлів “джерело – адресат” показав, що часова складність рішення задачі про найкоротший шлях
на ЕОМ алгоритмом Дейкстри складає О(q2), а алгоритмом Флойда – О(q3), де q – кількість вузлів комп'ютерної мережі. Застосування цих алгоритмів для рішення задач маршрутизації мультимедійної інформації для складних комп'ютерних мереж майже неможливо через тривалий час рішення задачі про найкоротший шлях. У зв'язку з цим обґрунтовано необхідність розробки паралельних методів, алгоритмів і обчислювальних засобів для рішення задач маршрутизації в комп'ютерних мережах. Проведений аналіз відомих паралельних методів, алгоритмів і обчислювальних засобів для рішення задач про найкоротший шлях виявив головний недолік відомих паралельних обчислювальних засобів, зв'язаний з рішенням тільки задачі одношляхової маршрутизації. Серед робіт з рішення задачі одношляхової маршрутизації на паралельних обчислювальних засобах слід зазначити роботи відомих учених академіка Г.Є. Пухова, В.В. Васильєва, В.Л. Баранова, А.Г. Додонова, І.А. Жукова, Г.М. Луцького, О.І. Стасюка і їх учнів.

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

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

Комп'ютерна мережа моделюється графом, що топологічно подібний до комп'ютерної мережі. Кожній гілці графа привласнюється вага, яка дорівнює часовій затримці під час передавання даних по каналу, що моделюється цією гілкою графа. Граф, у свою чергу, моделюється паралельною обчислювальною структурою, топологічно йому подібною. Граф мережі моделюємо паралельною структурою, що складається з моделей гілок (МГ) і моделей вузлів (МВ), з'єднаних відповідно до топології мережі. Реалізуємо функцію затримки сигналу на час, пропорційний вазі ребра графа в моделях гілок, до складу яких уведемо формувач часового інтервалу (ФЧІ). У моделі вузла виділимо перший сигнал, що надійшов у цей вузол, а в моделі гілки зафіксуємо за допомогою індикатора гілки (ІГ) факт надходження першого сигналу через цю гілку у модель вузла. Узагальнену модель фрагмента графа, що складається з пучка m гілок, які входять в один вузол, зображено на рис.1. Кожна модель гілки містить інформаційний вхід , інформаційний вихід , індикаційні входи , та індикаційні виходи , .

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

Рис. 1. Узагальнена модель фрагмента графа для двохшляхової
мар-шрутизації

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

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

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

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

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

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

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

Рис. 2. Узагальнена структура реалізації методу багатошляхової маршрутизації: БК – блок керування

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

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

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

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

(1)

де – вага l-ої гілки s-го фрагмента, – вага r-го вузла фрагмента графа, з'єднаного з l-ою гілкою s-го фрагмента. Топологія графа визначає схему з'єднання його фрагментів, яку можна описати співвідношенням:

. (2)

Умова стаціонарного стану:

, (3)

j = 1, 2, … , q,

де – вага j-го вузла графа;

q – кількість вузлів графа;

Т – момент часу досягнення стаціонарного стану;

?t – час виконання одного кроку паралельних обчислень у всіх вузлах графа.

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

Системоаналогова обчислювальна структура зображена на рис. 3.

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

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

Рис. 3. Системоаналогова обчислювальна структура

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

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

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

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

1. Одношляхова маршрутизація на САОС.

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

3. Перехід до п. 1, якщо кількість найкоротших шляхів менша від потрібної.

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

Рис. 4. Узагальнена системоаналогова структура багатошляхової маршрутизації

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

Дано оцінку ефективності системоаналогових обчислювальних структур. У запропонованих обчислювальних структурах оцінки часової і ємнісної складності мають однаковий порядок O(L) і O(q). Збалансованість цих оцінок дозволяє одержати позитивний ефект або за часовою, або за ємнісною складністю порівняно з мультипроцесорними обчислювальними системами (МОС), у яких реалізуються паралельні алгоритми з тісно зв'язаними оцінками часової і ємнісної складності.

На рис. 5 зображено графік зміни оцінки часової складності lg В залежно від складності модельованої мережі, оцінюваної величиною lg q, де q – кількість вузлів модельованої мережі. У таблиці, зображеній праворуч від графіка часової складності, наведено орієнтований розрахунок часу рішення задачі маршрутизації на ЕОМ для двох випадків:

– швидкодія ЕОМ – 106 оп./с.;

– швидкодія ЕОМ – 1010 оп./с.

Рис. 5. Графік зміни оцінки часової складності

Графік O(q) (рис. 5) відповідає оцінці часової складності САОС, графік O(q2) описує характер зміни часової складності алгоритму Дейкстри, O(q3) – алгоритму Флойда на ЕОМ. У таблиці праворуч від графіка O(q) наведено орієнтовані дані за часом рішення задачі маршрутизації на САОС для випадків використання елементів з тактовою частотою f1 = 500 МГц і f2 = 50 Мгц. Графік часової складності побудовано у діапазоні зміни аргументу lg. Цей діапазон охоплює перспективні комп'ютерні мережі з кількістю вузлів більше 100.

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

Рис. 6. Графік залежності оцінок ємнісної складності

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

Дійсно, моделювання мереж у вигляді двомірної решітки з кількістю вузлів q = 103 Ч 103 потребує для реалізації МОС кількості мікропроцесорів q3 = 1018. Така оцінка апаратурних витрат викликає сумнів щодо реалізації МОС навіть з урахуванням перспективи розвитку засобів мікроелектроніки.

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

ВИСНОВКИ

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

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

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

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

4. Установлено, що часова складність запропонованого системоаналогового алгоритму становить О(L), де L – максимальна кількість вузлів уздовж найкоротшого шляху, а ємнісна складність системоаналогового алгоритму оцінюється величиною порядку О(q), де q – кількість вузлів модельованої мережі.

5. Показано, що запропонований системоаналоговий алгоритм з лінійною оцінкою часової складності О(L) має істотні переваги порівняно з відомим послідовним алгоритмом Дейкстри, у якого оцінка часової складності порядку О(q2) і алгоритмом Флойда, що має оцінку часової складності порядку О(q3), де q – кількість вузлів модельованої мережі.

6. Установлено, що запропонований системоаналоговий алгоритм, який характеризується лінійною залежністю росту ємнісної складності від складності модельованого графа, має значну перевагу перед відомими паралельними алгоритмами, реалізованими на мультипроцесорних системах з оцінкою ємнісної складності О(q3),
де q – кількість вузлів модельованої мережі.

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

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

1. Жуков І.А., Мартинова О.П. Метод побудови паралельних структур для пошуку альтернативних маршрутів у комп’ютерних мережах // Вісник НАУ. – К.: НАУ, 2004. –
№ 1. – С. 14-17.

2. Жуков И.А., Мартынова О.П. Особенности передачи данных мультимедиа в компьютерных сетях // Проблеми інформатизації та управління. – К.: НАУ, 2002. – Вип.5. – С. 121-124.

3. Мартынова О.П. Организация многоадресной маршрутизации для передачи мультимедийной информации // Проблеми системного підходу в економіці. – К.: НАУ, 2003. – Вип.5. – С. 80-85.

4. Жуков И.А., Мартынова О.П. Системоаналоговое моделирование на графах параллельных маршрутов в сетях // Проблеми інформатизації та управління. – К.: НАУ, 2004. – Вип.10. – С. 40-45

5. Жуков І.А., Мартинова О.П. Системоаналоговий метод багатошляхової маршрутизації на графах // Вісник Технологічного університету Поділля. – Хмельницький, 2004, Т.2(60), № 2. – Ч.1. – С. 38-42.

6. Жуков И.А., Баранов В.Л., Фролова Е.Г., Мартынова О.П. Системоаналоговое моделирование многокритериального управления смещенными дифференциальными преобразова- ниями // Вісник Кременчуцького державного політехнічного університету. – Кременчук, 2003. – Вип. 3. – С. 53-56.

7. Мартынова О.П., Лисовая И.В. Применение современных мультимедийных технологий в учебном процессе // Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти: Зб. наук. пр. – К.: Європейський університет, 2003. – Ч. 2. – С. 44-47.

8. Мартинова О.П. Методи перетворення зображення при передачі в комп’ютерних мережах // Інформаційно-діагностичні системи: Матеріали IV Міжнародної науково-технічної конференції “АВІА – 2002”. – К.: НАУ, 2002. – Т.1. – С. 14.45-14.46.

9. V. Levistky, O. Martinova. The Features of transferring multimedia data in computer networks / Авіація, космонавтика, електронні системи та технології: Тези доп. Міжнародної наукової конференції студентів та молодих вчених (англійською мовою). – К.: НАУ, 2002. – С. 74-75.

10. Мартинова О.П. Организация мультимедийного трафика в сети АТМ // Інформаційно-діагностичнісистеми: Матеріали V Міжнародної науково-технічної конференції “АВІА – 2003”. – К.: НАУ, 2003. – Т.1. – С. 14.25-14.28.

11. Мартынова О.П. Методы доступа в локальных сетях при передаче мультимедийной информации / Человек и космос: Тез. докл. IV Международной молодежной научно-практической конференции. – Днепропетровск, 2004. – С. .

12. Мартинова О.П. Застосування прозорого моста для підвищення продуктивності мережі // Наука і молодь: Зб. наук. пр. Міжнародної наукової конференції студентів та молодих учених “Політ-2003”. – К.: НАУ, 2003. – С. 131-134.

13. Жуков И.А., Мартынова О.П. Системоаналоговый метод поиска альтернативных маршрутов в компьютерных сетях / Наукові проблеми розробки, модернізації та застосування інформаційних систем космічного і наземного базування: Тези доповідей ХІV Науково-технічної конференції. – Житомир, 2004. – Ч.1.– С. 110.

14. Мартынова О.П. Параллельные средства решения задачи альтернативной маршрутизации в компьютерных сетях // Інформаційно-діагностичні системи: Матеріали VІ Міжнародної науково-технічної конференції “АВІА – 2004”. – К.: НАУ, 2004. – Т.1. – С. 13.49-13.52.

АНОТАЦІЇ

Мартинова О.П. Паралельні обчислювальні структури для рішення задач маршрутизації в комп'ютерних мережах. – Рукопис.

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

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

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

Мартынова О.П. Параллельные вычислительные структуры для решения задач маршрутизации в компьютерных сетях. – Рукопись.

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

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

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

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

Martynova O.P. Parallel computing structures for the decision of problems of routing in computer networks. – Manuscript.

The dissertation on competition of a scientific degree of Candidate Technical Science on a speciality 05.13.13 - Computers, systems and networks. – National aviation university Ministry of Education and Science of Ukraine, Kiev, 2004.

The dissertation is devoted to development of parallel computing structures for the decision of problems of multitravelling routing in computer networks.

The method of consecutive multitravelling routing on the parallel computing structures constructed on the basis of a method of time analogy and structural similarity of topology of a network and computing structure is offered.

The generalized structure of realization of multitravelling routing on parallel computing structure of the time analogy constructed on the basis of a method is offered. With the purpose of increase of speed of parallel computing structures it is offered system – analogues a method and algorithm of routing on the column, modelling a computer network. Are developed system – analogues computing structures for multitravelling routing.

The estimation of efficiency system – analogues computing structures is given.

Key words: parallel computing structure, system – analogues computing structure, multitravelling routing, computer networks.