Модифікація алгоритму Дейкстри для реалізації багатошляхової маршрутизації в комп’ютерних мережах
Дата
2026
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Традиційні протоколи маршрутизації, зокрема 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 додатків.
Опис
Ключові слова
маршрутизація, багатошляхова маршрутизація, алгоритм Дейкстри, модифікація алгоритму, альтернативні маршрути, дерево найкоротших шляхів, внутрішньомережеві протоколи, computer networks, routing, multipath routing, Dijkstra's algorithm, algorithm modification, alternative routes, shortest path tree, intra-domain routing protocols., комп'ютерні мережі
Бібліографічний опис
Рябенко, Б. Ю. Модифікація алгоритму Дейкстри для реалізації багатошляхової маршрутизації в комп’ютерних мережах : 123 Комп’ютерна інженерія / Рябенко Борис Юрійович. – Київ, 2026. – 105 с.