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

brief description

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

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

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

Удосконалено метод послідовної маршрутизації на паралельних обчислювальних структурах, який відрізняється від відомих знаходженнямКпаралельних найкоротших маршрутів.
Вперше запропоновано системоаналоговий метод маршрутизації на графах, який відрізняється від відомих використанням системної аналогії, що дає змогу зменшити час знаходження найкоротшого шляху.
Вперше розроблено системоаналоговий алгоритм багатошляхової маршрутизації на паралельних обчислювальних структурах, який відрізняється від відомих паралельно-послідовним способом знаходження багатьох паралельних найкоротших шляхів, що дає змогу зменшити час знаходження найкоротших шляхів та апаратурні витрати.
Установлено, що часова складність запропонованого системоаналогового алгоритму становитьО(L), деL максимальна кількість вузлів уздовж найкоротшого шляху, а ємнісна складність системоаналогового алгоритму оцінюється величиною порядкуО(q), деq кількість вузлів модельованої мережі.
Показано, що запропонований системоаналоговий алгоритм з лінійною оцінкою часової складностіО(L) має істотні переваги порівняно з відомим послідовним алгоритмом Дейкстри, у якого оцінка часової складності порядкуО(q2) і алгоритмом Флойда, що має оцінку часової складності порядкуО(q3), деq кількість вузлів модельованої мережі.
Установлено, що запропонований системоаналоговий алгоритм, який характеризується лінійною залежністю росту ємнісної складності від складності модельованого графа, має значну перевагу перед відомими паралельними алгоритмами, реалізованими на мультипроцесорних системах з оцінкою ємнісної складностіО(q3), деq кількість вузлів модельованої мережі.
Запропоновано узагальнену системоаналогову обчислювальну структуру багатошляхової маршрутизації, яка реалізує системоаналоговий алгоритм пошуку найкоротших шляхів на графах, з топології яких послідовно вилучаються гілки, які належать раніше знайденим найкоротшим маршрутам, що дозволяє знайтиКпаралельних найкоротших маршрутів, що не мають загальних гілок.