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

Скорочена інформація про документ
dc.contributor.advisorМартинова, Оксана Володимирівна
dc.contributor.authorРябенко, Борис Юрійович
dc.date.accessioned2026-06-08T11:57:15Z
dc.date.available2026-06-08T11:57:15Z
dc.date.issued2026
dc.description.abstractАктуальність теми. Традиційні протоколи маршрутизації, зокрема OSPF, спираються на алгоритм Дейкстри й обирають єдиний оптимальний маршрут, що веде до нерівномірного розподілу навантаження та знижує відмовостійкість мережі. Існуючі підходи до багатошляхової маршрутизації потребують багаторазового запуску алгоритму для кожної пари вузлів окремо, що суттєво збільшує обчислювальні витрати. Розробка алгоритму, здатного формувати множину альтернативних маршрутів для всієї мережі за один прохід, є актуальною науковою і практичною задачею. Об'єктом дослідження є процес маршрутизації в комп'ютерних мережах та побудова множинних маршрутів у внутрішньомережевих протоколах. Предметом дослідження є алгоритми багатошляхової маршрутизації та методи побудови альтернативних маршрутів, а також оцінка їх ефективності за показниками швидкодії, використання пам'яті та часу доставки пакетів. Мета роботи: проаналізувати існуючі алгоритми маршрутизації та підходи до побудови множинних маршрутів; дослідити обмеження класичних алгоритмів пошуку найкоротших шляхів у задачах багатошляхової маршрутизації; розробити модифікацію алгоритму Дейкстри, що одночасно формує основне дерево найкоротших маршрутів та додаткове дерево альтернативних шляхів; оцінити ефективність запропонованого підходу в контексті внутрішньомережевих протоколів маршрутизації. Наукова новизна полягає в наступному: 1. Запропоновано модифікацію алгоритму Дейкстри, яка за один прохід будує основне та альтернативне дерева маршрутів. 2. Удосконалено підхід до багатошляхової маршрутизації: множина маршрутів формується в межах усієї мережі без багаторазового запуску алгоритму для окремих пар вузлів. 3. Виконано порівняльний аналіз запропонованого підходу та існуючих алгоритмів за показниками швидкодії, використання пам'яті та часу доставки пакетів. Практична цінність. Запропонована модифікація алгоритму Дейкстри формує основні та альтернативні маршрути за один прохід, що забезпечує рівномірний розподіл навантаження та підвищує відмовостійкість без значного збільшення обчислювальних витрат. Розроблений підхід може бути застосований у внутрішньомережевих протоколах маршрутизації, при проєктуванні та оптимізації комп'ютерних мереж, а також у навчальному процесі при вивченні алгоритмів маршрутизації. Апробація роботи. Основні положення і результати роботи представлено на таких наукових заходах: XVII Наукова конференція магістрантів та аспірантів ПМК-2024, Київ, 20–22 листопада 2024; XVIII всеукраїнська науково-практична web-конференція аспірантів, студентів та молодих вчених, Кривий Ріг, 25–27 березня 2025; The 8th International Conference on Computer Science, Engineering and Education Applications (ICCSEEA2025), онлайн-конференція, Львів, 21–22 червня 2025; XVIII Наукова конференція магістрантів та аспірантів ПМК-2025, Київ, 19–21 листопада 2025. Структура та обсяг роботи. Магістерська дисертація складається зі вступу, чотирьох розділів, висновків, переліку використаних джерел та додатків. У вступі обґрунтовано актуальність теми, сформульовано мету, об'єкт і предмет дослідження, визначено наукову новизну та практичну цінність результатів. У першому розділі проведено аналіз підходів до маршрутизації в комп'ютерних мережах: розглянуто моделі та метрики якості маршрутів, класифікацію багатошляхових методів, алгоритмічні підходи до побудови множинних маршрутів та їх обмеження. У другому розділі формалізовано задачу маршрутизації, обґрунтовано необхідність модифікації класичних алгоритмів, представлено розроблену модифікацію алгоритму Дейкстри та проаналізовано її обчислювальну складність. У третьому розділі описано два компоненти розробленого програмного комплексу: консольний додаток для алгоритмічного тестування та настільний симулятор мережі для моделювання процесів маршрутизації з візуалізацією передавання пакетів. У четвертому розділі наведено результати експериментального дослідження модифікованого алгоритму за показниками повноти побудови додаткового дерева маршрутів, швидкодії та використання пам'яті, а також виконано порівняння з існуючими алгоритмами та проведено моделювання передачі пакетів у різних сценаріях навантаження. У висновках підсумовано основні результати роботи. Робота викладена на 95 сторінках, містить 40 рисунків, 8 таблиць, 6 додатків.
dc.description.abstractotherRelevance of the topic. Traditional routing protocols, including OSPF, rely on Dijkstra's algorithm and select a single optimal route, which leads to uneven load distribution and reduces network fault tolerance. Existing multipath routing approaches require running the algorithm repeatedly for each pair of nodes, which significantly increases computational costs. Developing an algorithm capable of constructing a set of alternative routes for the entire network in a single pass is therefore a relevant scientific and practical problem. Object of research is the routing process in computer networks and the construction of multiple routes in intra-domain routing protocols. Subject of research is multipath routing algorithms and methods for constructing alternative routes, as well as the evaluation of their efficiency in terms of execution speed, memory usage, and packet delivery time. Objective of the work: to analyze existing routing algorithms and approaches to constructing multiple routes; to investigate the limitations of classical shortest path algorithms in multipath routing problems; to develop a modification of Dijkstra's algorithm that simultaneously constructs a primary shortest path tree and an additional alternative path tree; to evaluate the efficiency of the proposed approach in the context of intra-domain routing protocols. Scientific novelty: 1. A modification of Dijkstra's algorithm is proposed, which constructs both the primary and alternative route trees in a single pass. 2. The multipath routing approach is improved: a set of routes is constructed across the entire network without running the algorithm repeatedly for individual pairs of nodes. 3. A comparative analysis of the proposed approach and existing algorithms is performed in terms of execution speed, memory usage, and packet delivery time. Practical value. The proposed modification of Dijkstra's algorithm constructs primary and alternative routes in a single pass, ensuring balanced load distribution and improved fault tolerance without a significant increase in computational costs. The developed approach can be applied in intra-domain routing protocols, in the design and optimization of computer networks, and in educational settings for studying routing algorithms. Approbation of the work. The main findings and results of the work were presented at the following scientific events: XVII Scientific Conference of Master's and Postgraduate Students PMK-2024, Kyiv, November 20-22, 2024; XVIII All-Ukrainian Scientific and Practical Web Conference of Postgraduate Students, Students and Young Scientists, Kryvyi Rih, March 25-27, 2025; The 8th International Conference on Computer Science, Engineering and Education Applications (ICCSEEA2025), online conference, Lviv, Ukraine, June 21-22, 2025; XVIII Scientific Conference of Master's and Postgraduate Students PMK-2025, Kyiv, November 19-21, 2025. Structure and scope of the work. The master's thesis consists of an introduction, four chapters, conclusions, a list of references, and appendices. The introduction substantiates the relevance of the topic, formulates the objective, object and subject of research, and defines the scientific novelty and practical value of the results. The first chapter analyzes routing approaches in computer networks, covering route quality models and metrics, classification of multipath methods, and algorithmic approaches to constructing multiple routes along with their limitations. The second chapter formalizes the routing problem, justifies the need to modify classical algorithms, presents the developed modification of Dijkstra's algorithm, and analyzes its computational complexity. The third chapter describes two components of the developed software package: a console application for algorithmic testing and a desktop network simulator for modeling routing processes with packet transmission visualization. The fourth chapter presents the results of experimental evaluation of the modified algorithm in terms of additional route tree coverage, execution speed, and memory usage, as well as a comparison with existing algorithms and packet transmission simulations under various load scenarios. The conclusions summarize the main results of the work. The work is presented on 95 pages and contains 40 figures, 8 tables, 6 appendices.
dc.format.extent105 с.
dc.identifier.citationРябенко, Б. Ю. Модифікація алгоритму Дейкстри для реалізації багатошляхової маршрутизації в комп’ютерних мережах : 123 Комп’ютерна інженерія / Рябенко Борис Юрійович. – Київ, 2026. – 105 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/81528
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectмаршрутизація
dc.subjectбагатошляхова маршрутизація
dc.subjectалгоритм Дейкстри
dc.subjectмодифікація алгоритму
dc.subjectальтернативні маршрути
dc.subjectдерево найкоротших шляхів
dc.subjectвнутрішньомережеві протоколи
dc.subjectcomputer networks
dc.subjectrouting
dc.subjectmultipath routing
dc.subjectDijkstra's algorithm
dc.subjectalgorithm modification
dc.subjectalternative routes
dc.subjectshortest path tree
dc.subjectintra-domain routing protocols.
dc.subjectкомп'ютерні мережі
dc.titleМодифікація алгоритму Дейкстри для реалізації багатошляхової маршрутизації в комп’ютерних мережах
dc.typeMaster Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Riabenko_magistr.pdf
Розмір:
2.33 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (СПСКС)
Магістерські роботи