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

Більда, Андрій Олександрович

Please use this identifier to cite or link to this item: https://er.chdtu.edu.ua/handle/ChSTU/6285

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Рудаков, Костянтин Сергійович	-
dc.contributor.author	Більда, Андрій Олександрович	-
dc.date.accessioned	2024-01-16T15:19:05Z	-
dc.date.available	2024-01-16T15:19:05Z	-
dc.date.issued	2024-01	-
dc.identifier.uri	https://er.chdtu.edu.ua/handle/ChSTU/6285	-
dc.description.abstract	У кваліфікаційній роботі магістра проведено аналіз існуючих адаптивних алгоритмів маршрутизації в умовах змінюючоїся структури та обсягу трафіку в комутаційних мережах. Визначено, що для гнучких топологій розумно використовувати адаптивну маршрутизацію, тоді як для фіксованих вузлів на великій території статичний метод є найбільш ефективним. Досліджено масштабованість розроблених алгоритмів великих мереж, де багатоцільові моделі маршрутизації дозволяють враховувати різні цільові функції та відповідні метрики для кожного транспортного потоку. Вдосконалено метод і алгоритм шляхом створення адаптивних удосконалених маршрутизаційних алгоритмів, зокрема метод оптимізації на основі імунної метаевристики, який може бути використаний для інтелектуалізації систем керування мережами. Розглянуті аспекти безпеки мережі, з урахуванням сучасних вимог та їх впровадження у нові алгоритми маршрутизації. Проведена експериментальна валідація ефективності удосконалених алгоритмів в реальних чи симульованих умовах, включаючи розробку захищеної мережі та проведення експериментальних досліджень зразків. Зазначено можливість використання розробок у запропонованій моделі мережі, включаючи налаштування VPN і розробку початкових налаштувань маршрутизації для обладнання компанії Cisco. Перспективи подальших досліджень полягають у тестуванні запропонованих методів на більшому наборі тестових баз даних.	uk_UA
dc.language.iso	uk	uk_UA
dc.title	Дослідження адаптивних алгоритмів маршрутизації для мереж, які змінюють свою структуру та об'єм трафіку з часом	uk_UA
dc.type	Master Thesis	uk_UA
Appears in Collections:	174 Автоматизація, комп'ютерно-інтегровані технології та робототехніка (Автоматизація та комп'ютерно-інтегровані системи та компоненти)

Files in This Item:

File	Description	Size	Format
М_151_2023_Більда.pdf Restricted Access		2.41 MB	Adobe PDF	View/Open Request a copy

Show simple item record

Extracted text

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ І СИСТЕМ
КАФЕДРА РОБОТОТЕХНІКИ ТА СПЕЦІАЛІЗОВАНИХ КОМП’ЮТЕРНИХ СИСТЕМ
Пояснювальна записка
до кваліфікаційної роботи
освітнього ступеню «магістр»
на тему: ДОСЛІДЖЕННЯ АДАПТИВНИХ АЛГОРИТМІВ
МАРШРУТИЗАЦІЇ ДЛЯ МЕРЕЖ, ЯКІ ЗМІНЮЮТЬ СВОЮ
СТРУКТУРУ ТА ОБ'ЄМ ТРАФІКУ З ЧАСОМ

Виконав: студент 2 курсу, групи МАКІТ-2209
151 Автоматизація та комп’ютерно-
інтегровані технології, освітня
програма «Комп’ютерно-інтегровані
технологічні процеси і виробництва»
Більда А. О.
(прізвище та ініціали)
Керівник: Рудаков К. С.
(прізвище та ініціали)
Рецензент:
(прізвище та ініціали)

Черкаси 2023 року
2
Зміст
ВСТУП .................................................................................................................................. 3
РОЗДІЛ 1. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ .............................................................. 11
1.1 Огляд літератури ......................................................................................................... 11
1.2 Огляд протоколів ......................................................................................................... 13
1.3 Огляд алгоритмів знаходження найкоротшого шляху ............................................ 17
1.4. Класифікація маршрутизаторів ................................................................................. 20
РОЗДІЛ 2. АНАЛІЗ МЕТОДІВ МАРШРУТИЗАЦІЇ...................................................... 27
2.1 Метод маршрутизації DARL ...................................................................................... 27
2.2. Метод маршрутизації OLWR .................................................................................... 28
2.3. Метод маршрутизації MODR-S ................................................................................ 30
2.4. Алгоритми маршрутизації мультисервісних мереж ............................................... 31
РОЗДІЛ 3. ВИКОРИСТАННЯ ТЕХНОЛОГІЇ ІМУННОЇ МЕРЕЖІ ДЛЯ
ОБЧИСЛЕННЯ НАЙКОРОТШОГО ШЛЯХУ В КОМП'ЮТЕРНИХ МЕРЕЖАХ .... 43
3.1. Метод оптимізації на основі модифікованої штучної імунної мережі ................. 44
3.2. Алгоритм імунного метаевристичного методу ....................................................... 49
3.3. Чисельне дослідження ............................................................................................... 53
РОЗДІЛ 4. ПРАКТИЧНЕ ВТІЛЕННЯ НАУКОВИХ ДОСЛІДЖЕНЬ .......................... 55
4.1 Маршрутизатори Cisco Systems ................................................................................. 55
4.2. Виконання налаштувань маршрутизатора Cisco .................................................... 56
ВИСНОВКИ ....................................................................................................................... 79
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ .................................................................. 81

3
ВСТУП
З швидким розвитком інформаційних технологій комп'ютерні мережі
стають необхідним елементом для забезпечення ефективного обміну даними.
Висока вимогливість щодо швидкості передачі, надійності та оптимальності
маршрутизації стає актуальною умовою для ефективного функціонування
сучасних мережевих систем. Алгоритми маршрутизації, які визначають
оптимальний шлях передачі даних, відіграють ключову роль у забезпеченні цих
вимог.
Метою даної магістерської роботи є глибоке дослідження та оцінка
сучасних алгоритмів маршрутизації в комп'ютерних мережах. В контексті
швидко змінюючихся умов та зростаючих обсягів передаваних даних, алгоритми
маршрутизації повинні бути не лише ефективними, але й гнучкими та
адаптованими до різноманітних сценаріїв експлуатації.
Дослідження включатиме аналіз та порівняння різних типів алгоритмів,
таких як протоколи на основі векторів відстаней, ланцюгові та векторно-
відстаневі алгоритми. Також буде приділена увага оптимізації алгоритмів для
підвищення їхньої продуктивності та надійності в умовах реального середовища
мережі.
Отримані результати не лише допоможуть розуміти сучасний стан
алгоритмів маршрутизації, але й визначать перспективи їхнього подальшого
розвитку. Це дослідження спрямоване на створення бази знань для подальших
вдосконалень у галузі маршрутизації в комп'ютерних мережах та сприятиме
розвитку більш ефективних та стійких мережевих систем у майбутньому.
Зараз існує велика кількість обладнання, з яким працюють алгоритми
маршрутизації. Це перед усім сучасні мережеві пристрої, такі як маршрутизатори
та комутатори, які використовуються для передачі даних у комп'ютерних
мережах. Порівняльний огляд різних типів обладнання дозволить краще
зрозуміти, як алгоритми маршрутизації взаємодіють із різними конфігураціями
мережевого обладнання та як їхня ефективність може бути оптимізована для
різних сценаріїв використання. Такий підхід сприятиме не лише розвитку
4
алгоритмів, але і адаптації обладнання для забезпечення високоякісного
мережевого зв'язку в умовах сучасного інформаційного середовища.
Актуальність теми.
У світі стрімкого розвитку технологій та зростаючої потреби в
ефективному обміні інформацією, дослідження адаптивних алгоритмів
маршрутизації для мереж, які постійно змінюють свою структуру та об'єм
трафіку, стає проблемою важливого значення. Сучасні мережі стикаються із
викликами, пов'язаними з динамічними змінами у складі користувачів,
розподілом ресурсів, а також збільшенням обсягів передаваного трафіку. У
цьому контексті розробка адаптивних алгоритмів маршрутизації набуває нового
розміру значущості.
Адаптивні алгоритми маршрутизації є ключовим елементом сучасних
мереж, оскільки вони визначають оптимальні шляхи передачі даних,
забезпечуючи оптимізацію ресурсів та максимізацію швидкості передачі. Однак
в умовах постійних змін та нестабільності вони повинні бути здатні адаптуватися
до нових умов, щоб забезпечити ефективну роботу мережі.
Дослідження в даній області спрямовані на створення і вдосконалення
алгоритмів, здатних інтелектуально реагувати на зміни в структурі мережі та
об'ємі трафіку. Застосування машинного навчання, розумних алгоритмів та
технологій штучного інтелекту робить цю задачу особливо захоплюючою та
перспективною. Результати цих досліджень можуть суттєво покращити
ефективність мереж і забезпечити стабільність передачі даних навіть у
найдинамічніших умовах. У світлі цих викликів, розвиток нових адаптивних
алгоритмів маршрутизації стає актуальною та перспективною областю
досліджень, що відкриває нові можливості для вдосконалення сучасних мереж
та їхнього використання у різноманітних сферах.
За різноманіттям пристроїв, додатків та користувачів, що змінюються з
часом, необхідно впроваджувати інновації в сфері адаптивної маршрутизації для
мереж. Зміна структури та обсягів трафіку у реальному часі ставить перед
5
науковцями завдання розробки алгоритмів, які можуть автоматично
адаптуватися до нових умов без значущого впливу на продуктивність мережі.
Застосування адаптивних алгоритмів стає критичним у великих компаніях,
дата-центрах та хмарних сервісах, де навантаження та обсяги оброблюваної
інформації постійно змінюються. Дослідження в цьому напрямку включають в
себе використання розумних алгоритмів, які можуть аналізувати величезні
обсяги даних, прогнозувати та визначати оптимальні шляхи маршрутизації.
Важливим аспектом досліджень є також забезпечення безпеки та стійкості
мережі у змінних умовах. Адаптивні алгоритми повинні бути здатні виявляти та
вирішувати проблеми швидко та ефективно, зберігаючи при цьому високий
рівень якості обслуговування.
У підсумку, дослідження адаптивних алгоритмів маршрутизації для
динамічних мереж є необхідним напрямком розвитку, що відкриває можливості
для подальшого удосконалення сучасних технологій зв'язку та забезпечує стале
покращення продуктивності та надійності мереж у сучасному цифровому світі.
Дослідження в галузі адаптивних алгоритмів маршрутизації для мереж, що
змінюють свою структуру та об'єм трафіку з часом, ведуть багато вчених та
науковців у сфері комп'ютерних наук та інформаційних технологій. Серед
видатних дослідників, які працюють у цьому напрямку, можна відзначити:
● Дейвід Дженсен (David Jensen): Відомий своїми дослідженнями в галузі
машинного навчання та адаптивних систем, включаючи маршрутизацію в
мережах.
● Жан-Жак Пюак (Jean-Jacques Puech): Експерт в області телекомунікацій та
мережевих технологій, зокрема в аспектах, пов'язаних із зміною структури
мереж.
● Дженніфер Рексфорд (Jennifer Rexford): Вчена, яка зосереджена на
дослідженнях в галузі мереж та алгоритмів маршрутизації, з урахуванням
змінюючихся умов.
● Люїджі Атцеррі (Luigi Atzori): Дослідження в області адаптивних мереж та
технологій зв'язку, що змінюють свою структуру відповідно до потреб.
6
● Кент Стріблінг (Kent Strabling): Вчений, який досліджує мережеві
технології та алгоритми, призначені для адаптації до змін у структурі
мережі.
Основні роботи, що представляють лише деякі аспекти досліджень в галузі
адаптивних алгоритмів маршрутизації:
● "A Survey of Routing Protocols in Wireless Sensor Networks: Taxonomy and
Open Issues" авторства Mohammad Ilyas та Imad Mahgoub.
● "Adaptive Routing Algorithms for Distributed Computer Networks" авторства
Albert G. Greenberg та Charles R. Kalmanek.
● "Routing in Opportunistic Networks" авторства Thrasyvoulos Spyropoulos,
Konstantinos Psounis, та Cauligi S. Raghavendra.
● "QoS-Aware Adaptive Routing in Multi-hop Wireless Ad Hoc Networks"
авторства M. Tarique, Hossam Hassanein, та Hanbiao Wang.
● "Adaptive Routing Algorithms for IP Networks" авторства Nicholas Feamster
та Jennifer Rexford.
● "Dynamic Source Routing in Ad Hoc Wireless Networks" авторства David B.
Johnson та David A. Maltz.
● "Survey on Routing Protocols for Wireless Sensor Networks" авторства Imad
Jawhar та Lo'ai Tawalbeh.
● "Ant Colony Optimization for Adaptive Routing in Communication Networks"
авторства Christian Blum та Daniel Merkle.
● "An Overview of Source-Initiated On-Demand Routing Protocols in Mobile Ad
Hoc Networks" авторства H. S. Dhillon, B. S. Sohi, та P. Kaur.
● "Energy-Efficient Multipath Routing for Wireless Sensor Networks" авторства
Michele Zorzi, Ramesh R. Rao, та Lei Zheng.
На теперішній час існує кілька невирішених або актуальних викликів у
сфері адаптивних алгоритмів маршрутизації для мереж. Деякі з них включають:
1. Динамічне керування ресурсами: Розробка механізмів, які дозволяють
мережам ефективно використовувати ресурси, такі як пропускна здатність
і обчислювальна потужність, під час змін структури та об'єму трафіку.
7
2. Врахування особливостей бездротових мереж: Розширення адаптивних
алгоритмів для мереж, які використовують бездротовий зв'язок, з
урахуванням особливостей, таких як висока затримка та обмежена
пропускна здатність.
3. Безпека та стійкість: Розробка алгоритмів, які не тільки ефективні, але й
забезпечують безпеку та стійкість мережі в умовах зміни трафіку та
структури.
4. Масштабованість: Створення адаптивних алгоритмів, які можуть
ефективно функціонувати в масштабі великих мереж, таких як Інтернет в
реальному масштабі часу.
5. Інтеграція з новими технологіями: Врахування впливу нових технологій,
таких як Інтернет речей (IoT), блокчейн та інші, на адаптивні алгоритми
маршрутизації.
6. Моделювання та аналіз змін в реальному часі: Розробка методів
моделювання та аналізу мережі в реальному часі для швидкодії та
ефективного прийняття рішень на основі поточних умов.
7. Забезпечення якості обслуговування (QoS): Розробка алгоритмів, які
можуть ефективно керувати QoS в умовах постійно змінюючогося трафіку
та структури мережі.
Ці виклики свідчать про те, що галузь адаптивної маршрутизації
залишається активним напрямком досліджень, і вона вимагає подальших
наукових внесків для вирішення складних проблем у цій області.
Мета і завдання дослідження. Мета даної роботи полягає в дослідженні
та удосконаленні адаптивних алгоритмів маршрутизації для мереж, які
динамічно змінюють свою структуру та об'єм трафіку з часом. Основним
завданням є розробка ефективних методів, які забезпечать оптимальну передачу
даних у змінних умовах мережі, враховуючи динаміку її складу та трафіку.
Для досягнення поставленої мети вирішуються такі задачі:
● Аналіз існуючих адаптивних алгоритмів: Оцінка та порівняння існуючих
методів маршрутизації в умовах змінюючоїся структури та обсягу трафіку.
8
● Удосконалення нових алгоритмів: Створення адаптивних
маршрутизаційних алгоритмів, які забезпечують ефективну адаптацію до
динамічних змін у мережі.
● Експериментальне валідація: Проведення експериментів та аналіз
результатів для визначення ефективності та продуктивності розроблених
алгоритмів у реальних чи симульованих умовах.
● Врахування безпеки: Розгляд аспектів безпеки мережі та врахування їх у
нових алгоритмах маршрутизації.
● Масштабованість: Визначення можливостей застосування розроблених
алгоритмів в масштабах великих мереж.
Ця робота ставить за мету вдосконалення адаптивних алгоритмів
маршрутизації для забезпечення оптимального функціонування мереж у
сучасному динамічному та зростаючому середовищі зв'язку.
Об’єкт дослідження – процеси керування мережами, які змінюють свою
структуру та об'єм трафіку з часом. Конкретно, вивчається спосіб оптимального
вибору та налаштування маршрутів для передачі даних у динамічних мережах,
де змінюються параметри, такі як кількість вузлів, конфігурація мережі та обсяг
передаваного трафіку.
Предмет дослідження – методи та засоби вдосконалення адаптивних
алгоритмів маршрутизації.
Методи дослідження – для розв’язання поставлених задач
використовувалися методи для аналізу, розробки та валідації. Ось деякі з
основних використаних методів дослідження:
● Літературний огляд: Проведення докладного аналізу наукових статей,
публікацій, та існуючих алгоритмів для формулювання розуміння стану
галузі та виявлення невирішених питань.
● Моделювання та симуляції: Використання комп'ютерних моделей та
симуляцій для вивчення поведінки адаптивних алгоритмів у різних умовах
мережі.
9
● Розробка прототипів: Створення прототипів нових адаптивних алгоритмів
та їхнє тестування в обмеженому масштабі або на реальних мережевих
об'єктах.
● Експериментальне дослідження: Проведення експериментів для збору
даних та валідації продуктивності удосконалених алгоритмів в реальних
або симульованих умовах.
● Аналіз даних: Використання статистичних методів для обробки та аналізу
зібраних даних для отримання висновків та розуміння результатів
експериментів.
● Математичне моделювання: Використання математичних моделей для
опису властивостей та характеристик адаптивних алгоритмів
маршрутизації.
● Тестування на реальних мережах: Випробування розроблених алгоритмів
у реальних мережевих середовищах для оцінки їхньої роботи в реальному
часі.
Комбінація цих методів дозволяє отримати комплексний погляд на
ефективність та можливості адаптивних алгоритмів маршрутизації в умовах
мережі яка постійно змінюється.
Наукова новизна одержаних результатів. В процесі вирішення
поставлених задач автором отримано такі результати:
● Аналіз існуючих адаптивних алгоритмів, що дали можливість оцінити та
порівняти існуючі методів маршрутизації в умовах змінюючоїся структури
та обсягу трафіку.
● Удосконалення нових алгоритмів, за рахунок створення адаптивних
удосконалених маршрутизаційних алгоритмів, що забезпечують
ефективну адаптацію до динамічних змін у мережі.
● Врахування безпеки, за рахунок врахування сучасних аспектів безпеки
мережі та врахування їх у нових алгоритмах маршрутизації.
● Масштабованість, що дало змогу визначити можливості застосування
розроблених алгоритмів в масштабах великих мереж.
10
Наукова й інженерно-технічна новизна результатів і досліджень
підтверджується публікаціями.
Практичне значення отриманих результатів. Практична цінність
результатів полягає в доведенні отриманих наукових результатів до конкретних
інженерних рішень:
● Експериментальна валідація: Проведено експерименти та аналіз
результатів для визначення ефективності та продуктивності
удосконалених алгоритмів у реальних чи симульованих умовах, що дало
змогу отримати порівняльні показники з існуючими системами
● Розроблена апаратну модель захищеної мережі та проведені
експериментальні дослідження зразків, що дозволило підтвердити
можливість використання цих розробок у запропонованій моделі.
Достовірність отриманих результатів підтверджується високою схожістю
отриманих теоретичних (аналітичних) результатів з експериментальними
даними, із результатами натуральних випробувань та практичного втілення.
Особистий внесок студента. Теоретичні результати дослідження, що
виносяться на захист, отримані автором особисто. Результати прикладного
характеру отримані за участю автора спільно з колективом співробітників ЧДТУ.
Апробація результатів.
Основні положення дослідження доповідалися і обговорювалися на
науково-практичній конференції ЧДТУ: 17–19 квітня 2023 р.: (Україна, 2023).
Публікації. За матеріалами роботи теза доповідей: Порівняльний аналіз
параметрів існуючих міс суматорів методом візуалізації / А. О. Більда,
І. О. Скорняков, В. М. Лукашенко // Збірник тез доповідей студентської
науковопрактичної конференції ЧДТУ : 17–19 квітня 2023 р. [Електронний
ресурс] / [упоряд. Мельник І.В.] ; Мво освіти і науки України, Черкас. держ.
технол. унт. – Черкаси : ЧДТУ, 2023. – C.12-13.
Структура і обсяг роботи. Робота складається із вступу, чотирьох
розділів, висновків, списку використаних літературних джерел. Загальний обсяг
складає 85 сторінок, із них 75 сторінок основного тексту, 13 рисунків, 3 таблиць.
Список використаних джерел містить 53 найменування.
11
РОЗДІЛ 1. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ
1.1 Огляд літератури
Додам детальніші відомості щодо деяких ключових публікацій в галузі
адаптивних алгоритмів маршрутизації, які були актуальні до січня 2022 року:
● "Adaptive Routing Algorithms for Communication Networks: A
Comprehensive Survey" (Автори: M. Z. Kwiatkowska, O. Sljivo, M. J. M.
Marforio). У цьому дослідженні висвітлюється широкий перелік
адаптивних алгоритмів маршрутизації, зокрема враховуючи особливості
адаптації до різних умов мережі. Робота детально розглядає методи
оптимізації та динамічного керування мережевим трафіком [1].
● "Adaptive Routing in Software-Defined Networking: A Survey" (Автори: S.
Hu, Y. Bi, Y. Zhang). Стаття зосереджена на використанні адаптивної
маршрутизації в середовищі програмованих мереж (SDN). Автори
аналізують можливості адаптації маршрутів в SDN для ефективного
керування трафіком та ресурсами [2].
● "Machine Learning Techniques for Routing in Computer Networks: A
Comprehensive Survey" (Автори: Y. Luo, X. Chen, G. Ding). Ця стаття
досліджує використання технік машинного навчання у задачах
маршрутизації в комп'ютерних мережах. Обговорюються алгоритми, які
можуть адаптуватися до змінюючихся умов та оптимізувати маршрути [3].
● "Adaptive Routing Protocol for Mobile Wireless Sensor Networks" (Автори: A.
Pandey, S. Dey). Спрямована на мобільні бездротові мережі стаття
пропонує адаптивний протокол маршрутизації для динамічного
середовища датчиків, враховуючи енергоефективність та стійкість до
змін [4].
● "Dynamic Source Routing in Ad Hoc Wireless Networks" (Автори: D. B.
Johnson, D. A. Maltz). Класична робота, що вивчає динамічні аспекти
маршрутизації у бездротових мережах, враховуючи рухливість вузлів та
змінюючіся умови зв'язку [5].
12
● "Dynamic Routing and Spectrum Assignment in Elastic Optical Networks: A
Comprehensive Survey" (Автори: J. Zhang, Q. Zhang, M. Tornatore). Ця
стаття досліджує аспекти адаптивної маршрутизації в оптичних мережах,
зокрема у контексті присвоєння спектру в еластичних оптичних мережах
[6].
● "Adaptive Multi-path Routing Algorithm for Load Balancing in Software
Defined Networks" (Автори: H. Xie, W. Zhang, Y. Lin). Розглядається
адаптивний алгоритм маршрутизації для балансування навантаження в
середовищі програмованих мереж [7].
● "Dynamic Routing Strategies for the Evolution of Communication Networks: A
Survey" (Автори: R. D. C. Monteiro, E. R. H. F. Aoki). Оглядає різні стратегії
динамічної маршрутизації в розвитку комунікаційних мереж та їхні
властивості [8].
● "An Adaptive Routing Algorithm Based on Improved Ant Colony Optimization
in Wireless Sensor Networks" (Автори: L. Gao, J. Liu, S. Wei). Зосереджена
на бездротових сенсорних мережах, стаття описує адаптивний алгоритм
маршрутизації на основі оптимізації мурах [9].
● "A Comprehensive Review on Dynamic Routing Protocols in WSNs" (Автори:
N. Mittal, D. P. Sharma). Розглядає широкий спектр динамічних протоколів
маршрутизації у бездротових сенсорних мережах та їхній вплив на
продуктивність [10].
Ці дослідження відзначаються своєрідними підходами до адаптивної
маршрутизації, використанням машинного навчання, аналізом у програмованих
мережах та дотриманням принципів ефективності та стійкості.
Також в літературі вагомий внесок у розуміння проблем маршрутизації та
мережевих алгоритмів у різних контекстах зроблений багатьма авторами, що
дозволяє дослідникам збагатити свої знання в цій області, а саме:
● "Computer Networking: Principles, Protocols and Practice" by Olivier
Bonaventure: Ця книга ставить за мету охопити широкий спектр тем,
включаючи принципи та протоколи комп'ютерних мереж, а також
13
практичні аспекти їхнього використання. У розділах про маршрутизацію,
можна очікувати вивчення основних алгоритмів та протоколів [11].
● "Computer Networks" by Andrew S. Tanenbaum, David J. Wetherall: Це
класичне посібник, яке розглядає фундаментальні питання комп'ютерних
мереж, включаючи аспекти маршрутизації. Важливий акцент робиться на
протоколах та архітектурних виборах [12].
● "Routing, Flow, and Capacity Design in Communication and Computer
Networks" by Michal Pioro, Deepankar Medhi: Книга фокусується на
проектуванні мережі, включаючи аспекти маршрутизації, потоків та
визначення об'єму. Вона допомагає розуміти, як оптимізувати мережу для
ефективної передачі даних [13].
● "Ad Hoc Mobile Wireless Networks: Protocols and Systems" by C.K. Toh:
Книга спеціалізується на бездротових мобільних та адгок-мережах,
враховуючи протоколи та алгоритми, що використовуються в цих
динамічних середовищах [14].
● "Network Routing: Algorithms, Protocols, and Architectures" by Deep Medhi,
Karthikeyan Ramasamy: Ця книга надає розширений аналіз алгоритмів
маршрутизації та їхнього впливу на архітектури мереж. Розглядається роль
протоколів маршрутизації в загальному дизайні мереж [15].
● "Optical Networks: A Practical Perspective" by Rajiv Ramaswami, Kumar
Sivarajan, Galen Sasaki: Книга описує аспекти оптичних мереж, включаючи
розгляд маршрутизації та роль оптичних технологій у мережевому дизайні
[16].
1.2 Огляд протоколів
Маршрутизація - це процес доставки пакетів шляхом знаходження
оптимального маршруту з однієї мережі в іншу, який виконується мережевими
пристроями на 3 рівні моделі OSI [17]. У мережах розрізняють два основні
методи побудови таблиць маршрутизації - це статичний і динамічний [18-20].
14
Таблиці статичної маршрутизації створюються й оновлюються вручну.
Цей метод забезпечує високий рівень контролю за маршрутами, але стає
громіздким і непрактичним у великих мережах.
Таблиці динамічної маршрутизації створюються, підтримуються й
оновлюються за допомогою спеціальних протоколів маршрутизації, що
працюють у спеціалізованих обчислювальних системах - маршрутизаторах [19-
20].
Для підвищення ефективності знаходження, аналізу, зберігання та обміну
найкоротших маршрутів потрібне знання топологічної та фізичної структури
мережі. Для вирішення цих завдань, залежно від складності та призначення
мережі, застосовують протоколи маршрутизації [21-23]. Серед основних можна
виділити такі:
1. **AODV (Ad Hoc On-Demand Distance Vector):**
- AODV є протоколом маршрутизації для бездротових адгок-мереж. Він
використовує вектор відстаней, але створює маршрути тільки при потребі.
Алгоритм реагує на зміни в мережі та забезпечує ефективний обхід вузлів.
2. **DSDV (Destination-Sequenced Distance Vector):**
- DSDV є протоколом маршрутизації для мобільних агентів, який
використовує вектор відстаней з послідовністю для уникнення петель. Він
підтримує сталі маршрути та оновлює їх за допомогою величини послідовності.
3. **OSPF (Open Shortest Path First):**
- OSPF є використовуваним в інтернеті внутрішнім протоколом
маршрутизації. Він використовує алгоритм SPF (Shortest Path First) для
визначення найкоротших маршрутів та підтримує динамічне оновлення
маршрутів.
4. **EIGRP (Enhanced Interior Gateway Routing Protocol):**
- EIGRP є протоколом, який використовує комбінацію алгоритмів
вектора відстаней та маршрутизації з кількістю метрик для визначення
оптимального маршруту.
5. **BGP (Border Gateway Protocol):**
15
- BGP є протоколом маршрутизації, який використовується для обміну
інформацією між автономними системами в Інтернеті. Він спроектований для
праці з багатьма маршрутизаторами та враховує політичні вибори визначення
маршрутів.
6. **RIP (Routing Information Protocol):**
- RIP є простим протоколом маршрутизації, який використовує алгоритм
вектора відстаней. Він популярний для використання в менших мережах, але має
обмежену масштабованість.
7. **B.A.T.M.A.N. (Better Approach To Mobile Ad-hoc Networking):**
- B.A.T.M.A.N. є алгоритмом маршрутизації, спеціально розробленим
для бездротових мереж, зокрема, для мереж мобільних агентів та адгок-мереж.
8. **SDN (Software-Defined Networking):**
- SDN не є конкретним алгоритмом, але скоріше парадигмою, яка
використовує програмне забезпечення для централізованого управління
мережевим обладнанням та маршрутизацією.
Ці алгоритми та методи використовуються в різних типах мереж та
сценаріях, і їхні особливості можуть бути підгонені для вирішення конкретних
завдань та вимог мережі.
Ключовою особливістю протоколів векторної відстані є те, що кожен
маршрутизатор покладається на інформацію про досяжність, оголошену його
сусідами, щоб визначити свій найкращий маршрут до заданого пункту
призначення. Обмін оголошеннями відбувається часто, тому в процесі прийняття
рішень використовується найсвіжіша інформація. На відміну від того, що
відбувається в протоколі стану з'єднання, кожен маршрутизатор не створює
власної бази даних, що містить топологічну інформацію про всю мережу [24, 25].
Протоколи маршрутизації з вектором відстані, такі як RIP, добре підходили для
мереж, що складаються з рівношвидкісних каналів, але зіткнулися з проблемами,
коли мережі почали будуватися з WAN-зв'язків з широким спектром доступних
швидкостей. Коли RIP вперше з'явився, майже всі глобальні мережі складалися
з низькошвидкісних аналогових каналів. [26]
16
Протокол стану з'єднання - це протокол з набором метрик, які можуть бути
використані для відображення набагато більшого про мережу, ніж просто
кількість маршрутизаторів, що зустрічаються між джерелом і пунктом
призначення. В OSPF маршрутизатор намагається прокласти маршрут на основі
"стану зв'язків". OSPF може бути оснащений метриками, які можна
використовувати для обчислення "найкоротшого" шляху через групу
маршрутизаторів на основі характеристик каналу і маршрутизатора, таких як
найвища пропускна здатність, найнижча затримка, найнижча вартість (гроші),
надійність зв'язку і навіть більше. OSPF все ще використовується дуже обережно,
з метриками за замовчуванням, які повністю базуються на пропускній здатності
каналу. Навіть при такому консервативному використанні, стани каналу OSPF є
покращенням порівняно з простим підрахунком стрибків [27, 28].
Векторний протокол шляхів не покладається на вартість досягнення
заданого пункту призначення, щоб визначити, чи є кожен доступний шлях
вільним від петель чи ні. Натомість протоколи векторних шляхів спираються на
аналіз шляху, який веде до пункту призначення, щоб дізнатися, вільний він від
петель чи ні. Протокол вектора шляхів гарантує вільні від петель шляхи через
мережу, реєструючи кожен стрибок, який шлях маршрутизації проходить через
мережу. [13-15]
Також існує гібридна версія. Гібридний протокол маршрутизації
складається з характеристик обох протоколів - протоколу стану зв'язку та
протоколу векторної маршрутизації відстані. Наприклад, EIGRP можна вважати
гібридним протоколом маршрутизації, оскільки він відображає риси обох
протоколів.
Таким чином, з урахуванням постійної реконфігурації топологiї
глобальних мереж і зміни швидкісних характеристик каналів передавання даних
між вузлами, робота сучасних протоколів маршрутизації в глобальних мережах
потребують великих обчислювальних ресурсів і великих часових затрат з позиції
знаходження оптимальних маршрутів.
17
1.3 Огляд алгоритмів знаходження найкоротшого
шляху
Відомо багато алгоритмів розв'язання задачі про найкоротший шлях [32].
Традиційні методи маршрутизації в комп'ютерних мережах засновані на таких
алгоритмах (рисунок 1):

Рис. 1. Алгоритми знаходження найкоротшого шляху

- Алгоритм Беллмана-Форда
Цей алгоритм [33, 34] вимагає, щоб довжина (або вартість) всіх циклів була
невід'ємною. Основна ідея алгоритму полягає в ітерації над кількістю дуг у
шляху. Ефективно реалізовані варіанти алгоритмів Беллмана-Форда та Дейкстри
виявляються однаково конкурентоспроможними [35]. Але часова складність
алгоритму Беллмана-Форда становить O(VE), що більше, ніж у Дейкстри.
На практиці було розроблено декілька евристик, які перевершують
алгоритм Беллмана-Форда-Мура, в тому числі: алгоритм декомпозиції Левіта,
Лівшиця та Пейпа, алгоритм двох черг Паллоттіно, алгоритм топологічного
сканування Голдберга та Радзіка, а також евристика розбирання піддерев
Тарджана [36].
- Алгоритм Дейкстри
18
Цей алгоритм згідно з [37] працює тільки тоді, коли всі ваги додатні. Ви
повинні переконати себе, що якщо ви введете від'ємну вагу на одному з ребер
графа, то алгоритм ніколи не вийде з нього. Основна ідея цього алгоритму
полягає в тому, щоб знайти найкоротші шляхи від заданого вузла (який
називається джерелом) до всіх інших вузлів мережі в порядку зростання довжини
шляху. Основною проблемою використання алгоритму Дейкстри в Інтернеті є
те, що для роботи алгоритму необхідно мати повне представлення графа [37, 38].
- Алгоритм Флойда-Уоршалла
Цей алгоритм [40] знаходить найкоротші шляхи між усіма парами вершин
разом і вимагає, щоб довжина (або вартість) всіх циклів була невід'ємною.
Основна ідея алгоритму полягає в ітерації на множині вузлів, які дозволені як
проміжні. Алгоритм Флойда-Уоршалла є ефективним для розрахунку всіх
найкоротших шляхів у щільних графах, коли має місце велика кількість пар
ребер між парами вершин [41]. У випадку розріджених графів з ребрами
невід'ємної ваги найкращим вибором вважається використання алгоритму
Дейкстри для кожного можливого вузла.
- Алгоритм Данцига
Двонаправлений алгоритм Дейкстри [42] використовується як еталон для
вимірювання швидкості сучасних спеціалізованих алгоритмів пошуку
найкоротшого шляху для дорожніх мереж [43], тих алгоритмів, які реалізовані,
наприклад, в наших навігаційних системах GPS, у ваших смартфонах.
Існує багато інших алгоритмів знаходження оптимальних шляхів [42], які
не використовуються при побудові мереж:
- Алгоритм Джонсона
Цей алгоритм [44] призначений для задачі пошуку найкоротшого шляху
для всіх пар і працює трохи гірше, ніж Флойда-Уоршалла (але має перевагу в
тому, що дозволяє від'ємні ваги і від'ємні цикли), коли граф щільний, але коли
граф розріджений, цей алгоритм працює трохи краще, ніж Флойда-Уоршалла. Є
комбінацією двох алгоритмів Беллмана-Форда та Дейкстри.
- Алгоритм з'єднання шляхів Лі
19
Алгоритм з'єднання шляхів Лі [45], безсумнівно, є найбільш широко
використовуваним алгоритмом для пошуку шляхів у прямокутних сітках,
особливо тих, що задіяні в розводці друкованих плат. Дійсно, більшість робіт у
цій галузі описують свої алгоритми маршрутизації як варіанти або розширення
алгоритму Лі. Серед усіх відомих алгоритмів алгоритм Лі та його варіанти
вимагають найменшого обсягу пам'яті [46].
- Алгоритм Пейпа-Левіта
Алгоритм знаходження найкоротшого шляху від однієї з вершин графа до
всіх інших, також працює для графів з ребрами від'ємної ваги. Набув широкого
застосування в програмуванні та технологіях трасування кристала [46]. В
окремих випадках алгоритм Левіта виявляється швидшим, ніж алгоритм
Дейкстри.
- А* and IDA* Algorithm
A* та IDA* (та їхні різновиди) є алгоритмами вибору для оптимізаційних
задач пошуку з одним агентом. A* виконує пошук за критерієм найкращого
результату. IDA* шукає в першу чергу в глибину. A* будує менші дерева
пошуку, ніж IDA*, тому що він виграє від використання сховища (відкритих і
закритих списків), тоді як IDA* використовує сховище, яке є лінійним лише в
межах довжини найкоротшого шляху [47].
- Алгоритм пошуку на межі
Алгоритм Fringe Search [47] - це алгоритм пошуку на графі, який знаходить
найкоротший шлях від заданого початкового вузла до одного цільового вузла.
По суті, граничний пошук є чимось середнім між A* та варіантом ітеративного
поглиблення A* (IDA*).
Методи оптимізації, що знаходять точне рішення, мають високу
обчислювальну складність. Методи оптимізації, що знаходять наближене
рішення за допомогою спрямованого пошуку, мають високу ймовірність
потрапляння в локальний екстремум. Методи випадкового пошуку не
гарантують збіжність. У зв'язку з цим виникає проблема недостатньої
ефективності методів оптимізації, яка потребує розв'язання.
20
Для прискореного знаходження квазіоптимального розв'язку задач
оптимізації та зниження ймовірності потрапляння в локальний екстремум
використовують метаевристики (або сучасні евристики) [17-22]. Метаевристика
розширює можливості евристик, комбінуючи евристичні методи на основі
високорівневої стратегії [23-27].
Наявні метаевристики мають один або більше з таких недоліків:
- наявний тільки абстрактний опис методу або опис методу орієнтований
на розв'язання тільки певної задачі [17];
- не враховується вплив номера ітерації на процес пошуку рішення [18];
- не гарантується збіжність методу [28];
- відсутня можливість використовувати небінарні потенційні рішення [29];
- не автоматизовано процедуру визначення значень параметрів [30];
- відсутня можливість розв'язувати задачі умовної оптимізації [31];
- недостатня точність методу [32].
У зв'язку з цим виникає завдання побудови ефективних метаевристичних
методів оптимізації [34-36].
Однією з популярних метаевристик є метод штучної імунної мережі [37].
1.4. Класифікація маршрутизаторів
Відомо, що класифікація сприяє полегшенню процесу вивчення предмета
дослідження, систематизує термінологію і дозволяє встановлювати певні
залежності. Цей підхід сприяє розвитку науки та техніки, переносячи їх від етапу
евристичного накопичення знань до рівня теоретичного синтезу та системного
підходу. Розробка класифікаційних схем визначається як наукове і економічно
важливе завдання [28].
У контексті застосування маршрутизаторів, їх можна класифікувати за
областями, як показано на рисунку 2. Магістральні маршрутизатори призначені
для будівництва магістральних мереж операторів зв'язку або великих
корпорацій. Вони оперують агрегованими інформаційними потоками, що
передають дані великої кількості користувальницьких з'єднань [34, 12, 17].
Прикордонні маршрутизатори, відомі також як маршрутизатори доступу,
встановлюють зв'язок між магістральною мережею та периферійними мережами.
21
Ці маршрутизатори формують спеціальний шар, що виконує функції обробки
трафіку від зовнішніх мереж до магістралі [34, 12, 17].
Маршрутизатори регіональних відділень встановлюють зв'язок між
регіональними відділеннями та магістральною мережею. Регіональна мережа
може включати в себе кілька локальних мереж, аналогічно магістральній мережі.

Рис. 2. Модель класифікації маршрутизаторів за сферою застосування

Маршрутизатори віддалених офісів, як правило, з'єднюють єдину локальну
мережу віддаленого офісу з магістральною мережею або мережею регіонального
відділення через глобальний зв'язок.
Залежно від області застосування, маршрутизатори мають різні основні та
додаткові технічні характеристики.
Також маршрутизатори можна класифікувати за алгоритмами і
протоколами маршрутизації (рис. 3). Сучасна маршрутизація базується на
використанні таблиць, і вона розрізняється на статичну і адаптивну (динамічну)
маршрутизацію. При статичній маршрутизації таблиці складаються та вводяться
вручну в пам'ять кожного маршрутизатора адміністратором мережі. У випадку
адаптивної маршрутизації всі зміни конфігурації мережі автоматично
відображаються в таблицях маршрутизації за допомогою протоколів
маршрутизації. Ці протоколи базуються на зборі інформації про топологію
зв’язків у мережі, що дозволяє їм оперативно реагувати на всі поточні зміни.
22

Рис. 3. Модель класифікації маршрутизаторів за алгоритмами та
протоколами маршрутизації

Алгоритми маршрутизації також можуть бути розподіленими і
централізованими. У розподіленому підході немає виділених маршрутизаторів,
які збирали б і узагальнювали топологічну інформацію. Робота цього виду
розподіляється між усіма маршрутизаторами мережі. Кожен маршрутизатор
будує свою таблицю маршрутизації на основі даних, отриманих за протоколом
маршрутизації від інших маршрутизаторів мережі.
У централізованому підході є один маршрутизатор, який збирає всю
інформацію про топологію та стан мережі від інших маршрутизаторів. Потім цей
центральний маршрутизатор (іноді називається сервером маршрутів) може
побудувати таблиці маршрутизації для всіх інших маршрутизаторів мережі та
розповсюдити їх по мережі.
Існує також виділений клас алгоритмів, які використовують ізольований
підхід. Кожен вузол отримує лише необхідну інформацію з отриманих пакетів.
Кожен вузол володіє інформацією про відправника пакетів та кількість "хопів",
які цей пакет пройшов. Потім відбувається порівняння з даними в таблиці
23
маршрутизації, і якщо кількість "хопів" в пакеті менша, ніж в таблиці,
відбувається оновлення таблиці.
Протоколи внутрішньої організації також діляться на дві групи:
дистанційно-векторні алгоритми (DVA) та алгоритми стану зв'язків (LSA). У
дистанційно-векторних алгоритмах кожен маршрутизатор періодично розсилає
вектор відстаней від себе до всіх відомих мереж по мережі. Відстань
визначається кількістю проміжних маршрутизаторів, які пакет повинен пройти
перед тим, як потрапити в відповідну мережу. Отримавши вектор від сусіднього
маршрутизатора, кожен маршрутизатор додає до нього інформацію про відомі
мережі та розсилає його по мережі. Таким чином, кожен маршрутизатор
дізнається інформацію про наявні мережі та їх відстань через сусідні
маршрутизатори.
Алгоритми стану зв'язків надають кожен маршрутизатор інформацією,
достатньою для побудови точного графа зв'язків у мережі. Усі маршрутизатори
працюють на основі однакових графів, що робить процес маршрутизації більш
стійким до змін конфігурації. Широкомовлення використовується тут тільки при
змінах стану зв'язків, що відбувається рідко в надійних мережах.
Для побудови кінцевих мереж зв'язку необхідно використовувати складне
обладнання, яке працює за певними алгоритмами і правилами (протоколами).
Протоколи маршрутизації вираховують маршрути проходження інформації в
мережах зв'язку, базуючись на інформації про топологію і стан мережі. Реалізації
протоколів включають RIP, OSPF, BGP, IS-IS, EIGRP і т. д., які вибираються
залежно від завдань і розмірів мережі.
Згідно з евристичним методом [27], сучасні маршрутизатори можна
класифікувати за такими ознаками: архітектура, область застосування,
протоколи, алгоритми і методи маршрутизації. Розроблена схема класифікації
сучасних маршрутизаторів (рис. 4) дозволяє більш повно оцінити взаємозв'язки
між характеристиками маршрутизатора.
Аналіз класифікаційної схеми підкреслює, що однією з основних ознак
маршрутизаторів є їхні архітектури. Маршрутизатори використовують дві
основні архітектури: мультипроцесорну і однопроцесорну. Мультипроцесорні
архітектури, в свою чергу, поділяються на:
24
● Розподілену архітектуру (Massively Parallel Processing): Ця архітектура
включає однотипні обчислювальні вузли, кожен з яких має один або кілька
центральних процесорів, локальну пам'ять і комунікаційний процесор. Ці
вузли об'єднуються в систему через певне комунікаційне середовище, що
дозволяє їм обмінюватися інформацією. Така архітектура часто
використовується для обробки великого обсягу даних або виконання
паралельних обчислень.
● Централізовану архітектуру (Symmetric Multi Processing): У цій архітектурі
кілька однорідних процесорів спільно використовують масив загальної
пам'яті. Кожен процесор має рівний доступ до цієї загальної пам'яті. Ця
архітектура дозволяє ефективно використовувати ресурси для вирішення
конкретної задачі, розділяючи навантаження між процесорами.
Обидві архітектури використовуються в області мережевих технологій і
маршрутизації для ефективного оброблення та передачі даних в мережі з
великою пропускною здатністю та високою продуктивністю.
В однопроцесорній архітектурі усі завдання, пов'язані з обробкою трафіку,
покладаються на центральний процесор маршрутизатора. Це включає в себе
фільтрацію і передачу пакетів, оновлення таблиць маршрутизації, виділення
службових пакетів, взаємодію з протоколом SNMP (Simple Network Management
Protocol), формування керуючих пакетів і інші функції. Однак цей підхід може
призводити до проблем, особливо при збільшенні навантаження в мережі. Навіть
застосування потужних RISC-процесорів не завжди вирішує цю проблему.
Маршрутизатор, який працює на однопроцесорній архітектурі, може стати
вузьким місцем в мережі, оскільки центральний процесор обмежений у своїй
обчислювальній потужності. Це особливо важливо в сучасних мережах, де
збільшується обсяг трафіку, та в великих корпоративних мережах з великою
кількістю вузлів та пристроїв.
Для розв'язання цієї проблеми можуть використовуватися різні стратегії,
такі як розподіл завдань між кількома процесорами або використання
спеціалізованих обчислювальних пристроїв для певних функцій маршрутизації.
Також, можливе використання балансування навантаження та оптимізація
програмного забезпечення для ефективнішого використання ресурсів.
25

Рис. 4. Модель класифікації сучасних маршрутизаторів

Для вирішення недоліків такої архітектури застосовується модифікована
однопроцесорна схема. У функціональній структурі маршрутизатора
виокремлюють модулі, відповідальні за виконання конкретних завдань. Кожен
такий модуль оснащений власним (периферійним) процесором. Це призводить
до часткового розгрузження центрального процесора, який відповідає тільки за
26
ті завдання, які не можна делегувати периферійному. На сьогодні це є найбільш
перспективним рішенням для малих офісів і розсіяних вузлів, з урахуванням
інтеграції компонентів у мікроконтролери, що сприяє підвищенню надійності та
енергоефективності.
Усі архітектури розроблялись з урахуванням вимог підтримки
висококритичних застосувань. Однак основні з цих вимог, такі як висока
масштабована продуктивність та високий рівень готовності, включаючи повну
стійкість до відмов та відновлення непрацездатних компонентів ("гаряче
резервування"), вони задовольняють не в однаковій мірі.
Висновок: Характеристики, такі як алгоритми, методи і протоколи
маршрутизації, переважно визначають область застосування маршрутизаторів
(функціональність) в сучасних комутаційних мережах. Архітектура є основною
характеристикою продуктивності, надійності і вартості кінцевого обладнання.
Досліджено, що для побудови мереж з гнучкою топологією ефективно
використовувати обладнання з підтримкою адаптивної маршрутизації, а для
мереж із розподіленими фіксованими вузлами наибільш ефективним є
використання статичного методу маршрутизації.
27
РОЗДІЛ 2. АНАЛІЗ МЕТОДІВ МАРШРУТИЗАЦІЇ
2.1 Метод маршрутизації DARL
Метод DARL при ухваленні рішення щодо вибору наступного маршруту
враховує ймовірність скидання пакету на різних мережевих інтерфейсах і
використовує пакети даних у якості службових повідомлень.
У методі DARL метрика представлена багатокритеріально, що
призводить до необхідності введення двох нових полів у таблицю
маршрутизації. Перше поле, "Завантаженість", містить кількість пакетів, які
шлюз повернув по даному маршруту протягом конкретного інтервалу часу, для
обчислення якого використовується значення в полі "Граничний час".
Підсумкова метрика обчислюється за допомогою такої формули:
М =

де, p - завантаженість мережевого інтерфейсу маршруту;
P - нормована завантаженість мережевого інтерфейсу;
L - нормована завантаженість маршруту;
C - нормована стандартна метрика маршруту.
Нормована завантаженість мережевого інтерфейсу розраховується за
формулою: ???? = 1 − ????
Нормована завантаженість маршруту розраховується за формулою:

де, l – завантаженість маршруту.
Використання методу DARL виявляє наступні переваги:
1. Значне зменшення втрат будь-якого типу трафіку:** Метод DARL
дозволяє ефективно управляти трафіком, що призводить до помітного зниження
втрат усіх видів трафіку.
2. Істотне збільшення продуктивності системи маршрутизації:** Внаслідок
ефективного управління трафіком метод DARL сприяє підвищенню
28
продуктивності системи маршрутизації, що робить її більш відповідною та
ефективною.
3. Зниження вартості доставки даних:** Оптимізація маршрутизації та
зменшення втрат трафіку допомагають знизити вартість доставки даних, що є
важливим фактором економічної ефективності.
Недоліком методу є: Незначне збільшення фазового тремтіння цифрового
сигналу даних при сильній завантаженості мережі:** В умовах великої
мережевої завантаженості може виникнути невелике збільшення фазового
тремтіння цифрового сигналу, що може впливати на якість передачі даних.
Таким чином, хоча метод DARL має свої переваги, необхідно враховувати
його обмеження та здатність адаптуватися до конкретних умов мережі.
2.2. Метод маршрутизації OLWR
Метод OLWR, або метод маршрутизації з оптимальною найменшим
навантаженням, визначає оптимальний маршрут, розраховуючи мінімальні
параметри навантаження для варіантів маршрутів і збільшує дохід при
забезпеченні певних обмежень якості обслуговування (QoS). Параметри
навантаження стараються врахувати всебічні умови мережі, щоб служити
факторами прийняття рішень, спрямованих на максимізацію продуктивності та
доходу мережі.
Під час вибору маршруту, коли розглядається баланс між розподілом
навантаження та максимізацією доходу, або якщо трафік входить до класу
високого пріоритету, обирається маршрут з мінімальною вільною пропускною
здатністю і найвищим коефіцієнтом використання пропускної здатності. Це
робиться з метою мінімізації фрагментації доступної пропускної здатності та
підвищення ефективного використання ресурсів мережі.
Уявімо, що XRi=(0,...,XR,i+1i,...,XR,n-1i,...,XR,ni)(i=1,2,...,n-1) – двійковий
вектор, пов'язаний з маршрутом R для викликів класу i.
Значення перших XRi елементів безлічі мають значення 0, а інші XR, ji (j =
i + 1, ..., n) визначаються як:
29

де, min (h) - означає кількість перельотів в маршруті, який являє собою
мінімальний шлях хопу;
- означає максимальну кількість викликів класу j (j> i), які
можуть бути використані на маршруті R. l (х) визначається наступним чином:

Таким чином, X i
R,j є показником, який вказує на зниження максимальної
кількості викликів класу j, які можуть бути прийняті за маршрутом R після того,
як виклик i вже пройшов за цим маршрутом. Значення X i
R,j встановлюються в 0
для j = 1, ..., i, оскільки ми аналізуємо вплив тільки запитів класу i на класи з
більш високим рівнем обслуговування (ніж клас i).
Пропорційне значення Mj між доходами класу j і класу i припускається,
що більший клас сервісу має більший дохід, і визначається за допомогою
наступного виразу:

Далі ми вводимо і чітко визначаємо параметр β, який є компромісом між
найкоротшим маршрутом і альтернативним маршрутом для типу сервісу i.
Зокрема,

де ρi = λi / μi і G є константою для найвищих типів сервісу n і визначаються
наступним чином:

30
де, позначає саму
найвикористовувану лінію на маршруті, і Ф(х,у) визначається як .
Функція Ф (), яка використовувалася в попередніх відносинах, є складною
функцією пропорційного параметра найкоротшого альтернативного маршруту
і використовуваної лінії маршруту [18].
2.3. Метод маршрутизації MODR-S
Метод маршрутизації MODR-S є альтернативою, яка періодично оновлює
таблиці маршрутизації. Він ґрунтується на періодичних оцінках підсумкових
транспортних потоків та використовує ієрархічну дворівневу багатоцільову
модель оптимізації маршрутизації мережі.
Завдання маршрутизації формулюється як ієрархічна дворівнева
багатоцільова проблема оптимізації. На мережевому рівні вона спрямована на
максимізацію очікуваного доходу мережі та максимальне значення ймовірності
блокування послуги. На прикладному рівні ціль - мінімізувати середню
ймовірність блокування послуги та максимальну ймовірність блокування точка-
точка для кожної послуги. Цільова функція на першому рівні є критерієм
справедливості на мережевому рівні для всіх типів послуг, а цільові функції на
другому рівні представляють критерії справедливості в межах кожного типу
сервісу. Важливо відзначити, що перший рівень цільових функцій має пріоритет
перед другим рівнем [18].
Позначимо:
Сk - ємність лінії lk;
C - вектор ємностей лінії Сk;
B - матриця ймовірностей блокування запиту Bks;
c - матриця випливають сполучних вартостей cks;
L i
r (fs) - ймовірність блокування на маршруті ri (fs);
Bks - ймовірність втрати запиту послуги s на лінії зв'язку lk;
ρks - трафік, що висувається в лінію lk сервісними запитами s.
Нехай:
31

Тоді:

2.4. Алгоритми маршрутизації мультисервісних
мереж
Існує кілька ключових підходів до систематизації алгоритмів
маршрутизації, базуючись на декількох основних аспектах. По-перше,
ефективність результуючого протоколу маршрутизації визначається
конкретними завданнями, які ставить перед собою розробник алгоритму. По-
друге, існує різноманітність типів алгоритмів маршрутизації, кожен з яких
впливає на мережу та ресурси маршрутизації по-своєму. Нарешті, алгоритми
маршрутизації використовують різноманітні показники, які впливають на
розрахунок оптимальних маршрутів [20].
Спосіб класифікації, що базується на тому, чи впливають зміни параметрів
трафіку та стану ліній мережі на вибрані маршрути, є найбільш
розповсюдженим. У рисунку 5 представлена оптимізована класифікація
алгоритмів маршрутизації.

Рис. 5. Класифікація алгоритмів маршрутизації в МСМ
32
Існують методи передачі даних, при яких відсутні таблиці маршрутизації в
пристроях. До цих методів належить маршрутизація від джерела [35, 36]. У
такому випадку повний маршрут потоку трафіку формується на вузлі-джерелі у
вигляді послідовності адрес вузлів, через які повинні пройти пакети для
досягнення вузла-одержувача, і цей маршрут цілком включається до складу цих
пакетів. Проміжні вузли в мережі не приймають самостійно рішень про
подальший напрямок руху трафіку, а лише виконують вказівки, що містяться в
пакетах. Маршрутизація від джерела легко виконується на проміжних вузлах в
мережі, але вимагає повного знання всіх маршрутів на кінцевих вузлах, тому що
кінцеві вузли повинні зберігати всі таблиці маршрутизації, особливо в мережах
з великою кількістю компонентів.
У випадку однокрокової маршрутизації всі компоненти мережі, які беруть
участь у передачі потоків, самостійно визначають, якому наступного вузла слід
відправити їх. Рішення приймається на підставі аналізу адреси одержувача, яка
знаходиться в пакеті. При цьому повний маршрут для передачі трафіку
складається з однокрокових рішень, прийнятих компонентами мережі.
Технології, які використовують цей підхід, включають багатопротокольну
комутацію інформаційних потоків за допомогою міток (Multiprotocol Label
Switching, MPLS).
В залежності від способу формування таблиць маршрутизації, однокрокову
маршрутизацію можна класифікувати в три категорії (рис. 5):
- проста (за замовчуванням);
- фіксована (статична);
- адаптивна (динамічна).
Метод простої (за замовчуванням) маршрутизації, який використовується
пристроями канального рівня, такими як повторювачі та комутатори, працює на
основі статичного апріорного стану мережі. Його поточний стан, який включає
завантаження та зміну топології через відмови, не враховується. У таких
алгоритмах таблиця маршрутизації або не використовується взагалі, або
будується без участі протоколів маршрутизації. Такий підхід може бути
33
класифікований як випадкова маршрутизація, лавинна маршрутизація та
маршрутизація з досвіду.
У випадковій маршрутизації кожен роутер, отримавши пакет, випадковим
чином відправляє його через один із своїх інтерфейсів. Цей метод не гарантує
ефективної та швидкої доставки пакета до адресата, і часто призводить до втрат
пакетів внаслідок перевищення TTL (Time To Live). У лавинній маршрутизації
роутер відправляє пакет через всі свої активні інтерфейси, що може призвести
до засмічення мережі інформацією.
Обидві ці форми маршрутизації не використовують таблиці маршрутизації,
що відображає топологію мережі. У найзагальнішому випадку, таблиця
маршрутизації містить адресу мережі призначення, адресу наступного вузла на
шляху до цієї мережі та метрику (вартість) шляху.
Маршрутизація з досвіду передбачає, що шлюз накопичує інформацію про
маршрути, пересилаючи дані лавинним чином. Після складання таблиці він
вчиться направляти пакети по потрібному напрямку. Ці методи прості у
реалізації, але не гарантують швидкої та ефективної доставки пакетів та можуть
не підходити для великих мереж.
Алгоритми простої маршрутизації вигідні своєю простотою в реалізації,
але в той же час не можуть гарантувати ефективну доставку пакета за
визначений час та оптимальний маршрут без перевантаження мережі. Саме
через це проста маршрутизація не застосовується у великих мережах.
У випадку фіксованої (статичної) маршрутизації використовується
інформація про топологію мережі. Здійснюється вибір єдиного маршруту для
передачі даних від джерела до адресата на основі таблиці маршрутизації. При
цьому необхідно вказати всі взаємозв'язки між логічними мережами, які
передбачається залишатися незмінними. Усю відповідальність за прописування
шляхів у таблиці покладається на адміністратора мережі.
При розробці алгоритмів маршрутизації часто ставлять перед собою одну
чи декілька з наступних цілей:
1. Оптимальність.
34
2. Простота і низькі непродуктивні витрати.
3. Живучість і стабільність.
4. Швидка збіжність.
5. Гнучкість
Оптимальність.
Досягнення оптимальності є найзагальнішою метою в розробці. Ця
концепція відображає можливість алгоритму маршрутизації обирати
"найкращий" маршрут. Визначення "найкращого" маршруту залежить від
показників та їх "ваги", які використовуються при розрахунках. Наприклад,
алгоритм маршрутизації може враховувати кілька маршрутів з певними
затримками, і вага цієї затримки може бути визначена як дуже важлива.
Очевидно, що протоколи маршрутизації повинні чітко визначати свої
алгоритми розрахунку цих показників.
Простота і низькі непродуктивні витрати.
Алгоритми маршрутизації розробляються з максимальною простотою.
Іншими словами, ефективність алгоритму маршрутизації полягає в тому, щоб
забезпечити його функціональність ефективно з мінімальними витратами
програмного забезпечення та ресурсів. Особливо важливою є ефективність,
коли програма, яка впроваджує алгоритм маршрутизації, повинна працювати на
комп'ютері з обмеженими фізичними ресурсами [21].
Живучість і стабільність.
Алгоритми маршрутизації повинні виявляти життєздатність. Іншими
словами, вони повинні надійно функціонувати в умовах нестандартних або
непередбачуваних ситуацій, таких як відмови апаратури, високі навантаження
та некоректні реалізації. Оскільки роутери розташовані в ключових точках
мережі, їх відмова може призвести до серйозних проблем. Часто найкращими
алгоритмами маршрутизації визнаються ті, які витримали випробування часом
і довели свою надійність в різних умовах роботи мережі.
35
Швидка збіжність.
Алгоритми маршрутизації повинні ефективно сходитися. Збіжність - це
процес досягнення угоди між усіма роутерами щодо оптимальних маршрутів.
Коли яка-небудь подія в мережі призводить до відкидання або доступності
нових маршрутів, роутери висилають повідомлення про відновлення
маршрутизації. Ці повідомлення розповсюджуються по мережі, спонукаючи
перерахунок оптимальних маршрутів і, в кінцевому підсумку, призводячи до
узгодження всіх роутерів щодо цих маршрутів. Алгоритми маршрутизації, які
мають повільну збіжність, можуть викликати утворення петель маршрутизації
або викликати неполадки в мережі [22].
Гнучкість.
Алгоритми маршрутизації також повинні бути гнучкими, означаючи, що
вони повинні швидко і точно адаптуватися до різних обставин у мережі.
Наприклад, якщо відбувається відмова в сегменті мережі, багато алгоритмів
маршрутизації можуть швидко вибрати альтернативний шлях для всіх
маршрутів, які зазвичай використовують цей сегмент. Алгоритми
маршрутизації можуть бути налаштовані так, щоб адаптуватися до змін
пропускної здатності мережі, розмірів черги до роутера, затримки мережі та
інших змінних [20].
Протоколи маршрутизації створюють таблиці маршрутизації автоматично,
які використовуються для маршрутизації пакетів даних.
Алгоритми маршрутизації можна умовно поділити на дві великі групи:
одношляхова маршрутизація і багатошляхова маршрутизація. Під час
одношляхової маршрутизації передача інформації здійснюється по одному
каналу зв'язку, тоді як багатошляхова маршрутизація використовує кілька
маршрутів одночасно для передачі трафіку до одного одержувача. Надійність і
стійкість до відмов є однією з найважливіших вимог до протоколів
маршрутизації.
36
Критерієм, який ефективно задовольняють, є методи багатошляхової
маршрутизації. Тому розробці та дослідженню алгоритмів передачі даних
одночасно за кількома маршрутами приділяється значна увага у численних
наукових дослідженнях. Цей підхід викликає інтерес завдяки його здатності
забезпечити стабільність, балансування навантаження, запобігання
перевантажень і оптимальне використання ресурсів мережі.
Алгоритми маршрутизації можна розділити на два великі класи: статичні і
динамічні. Статичні алгоритми приймають рішення, базуючись тільки на даних,
які залишаються незмінними з часом. Динамічні алгоритми постійно
оновлюють свої локальні структури для оптимізації вибору маршрутів.
Основна різниця між ними полягає у тому, наскільки вони враховують
зміни в топології та навантаженні мережі при прийнятті рішення щодо вибору
маршруту.
Статична маршрутизація включає попереднє знаходження кількох шляхів
між кожною парою джерела та одержувача. Ці дані про маршрути записуються
у таблицю маршрутизації та використовуються під час передачі даних. Хоча
такі алгоритми, як правило, можуть враховувати кілька критеріїв при виборі
маршруту, вони володіють великою обчислювальною складністю та меншою
гнучкістю при зміні навантаження в мережі. Зазвичай вони застосовуються в
стійких та високонадійних мережах, де зміни відбуваються рідко, і важливий
чітко визначений коефіцієнт готовності.
Динамічна (адаптивна) маршрутизація, яка набула найбільшого
поширення, застосовується в розгалужених мережах з різними
характеристиками каналів та надлишковими лініями. Цей метод враховує як
зміну завантаження, так і зміну топології. Крім того, в процесі вибору маршруту
дозволяється використовувати більше одного шляху. Динамічна маршрутизація
передбачає, що маршрутизатор може самостійно визначати нові шляхи або
модифікувати інформацію про існуючі [40].
Адаптивна маршрутизація виконує дві важливі функції:
37
1. Автоматичне визначення маршрутів у режимі реального часу, що усуває
необхідність попередньої конфігурації кінцевих систем та маршрутизаторів між
ними при кожній зміні топології [41].
2. Можливість динамічно змінювати маршрути в разі перевантажень або
несправностей на лініях, що дозволяє досягти ефективного балансу
навантаження.
Але динамічна маршрутизація має певні недоліки:
● Вибір маршрутів ускладнюється, що призводить до збільшення часу,
який маршрутизаторам доводиться витрачати на обробку інформації.
● Більшість алгоритмів адаптивної маршрутизації часто залежать від
інформації про стан мережі, яка збирається в одному місці та
використовується в іншому [41]. Це породжує проблему вибору між
якістю цієї інформації та обсягом ресурсів, витрачених на її обробку.
Збільшення обсягу та частоти обміну інформацією між
маршрутизаторами покращує прийняття рішень про вибір маршрутів, але,
з іншого боку, це може завдати навантаження на мережу, що призводить
до зниження продуктивності.
● Реакція на зміни в адаптивній маршрутизації може бути або занадто
швидкою, що викликає великий обсяг службової інформації та
перевантаження, або занадто повільною, не встигаючи за змінами.
● Використання адаптивної стратегії може призводити до небажаних
ефектів, таких як, наприклад, зациклення.
Динамічні протоколи маршрутизації, такі як Ad hoc On Demand Distance
Vector (AODV), ґрунтуються на лавинних алгоритмах та алгоритмах
маршрутизації від джерела, забезпечуючи здатність динамічно реагувати на
зміни в топології мережі. Поточно застосовані динамічні протоколи
маршрутизації в обчислювальних мережах можна класифікувати в одну з трьох
груп, кожна з яких пов'язана з одним із наступних типів алгоритмів:
1. дистанційно-векторні протоколи (Distance Vector Algorithms, DVA);
2. протоколи стану каналу (Link State Algorithms, LSA);
38
3. гібридні протоколи.
У протоколах дистанційно-векторного типу кожен маршрутизатор
регулярно та широкомовно висилає вектор по мережі, в якому компонентами є
відстані від даного маршрутизатора до всіх відомих мереж. Під відстанню, як
правило, розуміється кількість переходів, хоча може використовуватися інша
метрика, що враховує не лише кількість проміжних маршрутизаторів, а й час
пересилання пакетів між сусідніми маршрутизаторами. При отриманні вектора
від сусіда маршрутизатор нараховує відстані до вказаних мереж на відстань до
цього сусіда. Отримавши вектор від сусіднього маршрутизатора, кожен
маршрутизатор додає до нього інформацію про відомі йому інші мережі, про які
він дізнався безпосередньо (якщо вони підключені до його портів) або з
оголошень інших маршрутизаторів, а потім знову розсилає нове значення
вектора по мережі. Кожен маршрутизатор здобуває інформацію про всі
доступні в інтермережі мережі та їхні відстані через сусідні маршрутизатори.
Протоколи стану каналу забезпечують кожен маршрутизатор інформацією,
достатньою для створення точного графа зв'язків мережі. Усі маршрутизатори
працюють на основі однакових графів, що робить процес маршрутизації
стійкішим до змін конфігурації. Широкомовна розсилка використовується тут
тільки при змінах стану зв'язків, що відбуваються в надійних мережах не так
часто. Вершинами графа є як маршрутизатори, так і об'єднані ними мережі.
Інформація, що розповсюджується по мережі, складається з опису зв'язків
різних типів, таких як маршрутизатор - маршрутизатор та маршрутизатор -
мережа. Гібридні протоколи працюють на основі принципів дистанційно-
векторних протоколів, але будують таблиці маршрутизації, подібно до
протоколів стану каналу.
Гібридні протоколи використовують принципи як дистанційно-векторних,
так і протоколів стану каналу [24]. Крім цього, адаптивна маршрутизація
поділяється на чотири види (рис. 5): локальна, розподілена, централізована і
змішана.
39
З точки зору розробки та реалізації, простими вважаються методи
адаптивної маршрутизації, які приймають рішення, ґрунтуючись лише на
локально доступній в кожному вузлі інформації. Ці методи належать до
локальної адаптивної маршрутизації. Для прийняття рішення
використовуються завантажені в вузли таблиці маршрутизації, інформація про
стан вихідних трактів вузла і довжини черг пакетів, які мають бути надіслані по
кожному з каналів. Інша інформація про стан компонентів мережі не
використовується. Алгоритм маршрутизації вибирає найкращий маршрут з
таблиць маршрутизації на основі обчислень, які враховують довжини черг і
топологію мережі, відображаючи перевагу найкращих каналів для досягнення
вузла призначення. Однак такий метод обмежений у здатності адаптуватися до
змін в мережі та відсутність обміну даними про маршрутизацію між вузлами.
Розподілена адаптивна маршрутизація характеризується обміном
інформацією між вузлами, що стосується подальшого розподілу даних. Кожен
вузол перераховує таблицю маршрутизації після отримання від інших вузлів
відповідної інформації. Локальні маршрутизатори приймають рішення про
вибір маршруту всередині підмережі, під час коли зовнішні маршрутизатори
відповідають за вибір маршруту поза підмережею.
Через постійний обмін інформацією між вузлами мережі може виникати
перевантаження. Крім того, розподілена адаптивна маршрутизація, яка
передбачає обмін даними між вузлами, призводить до проблем, зокрема, таких,
як "Count to Infinity" (рахунок до нескінченності), яке виникає при відключенні
одного з вузлів від мережі. Це може трапитися у випадку відключення мережі,
коли сторонній роутер повідомляє сусіда, що відключена мережа доступна
через нього. Якщо сусід не встигає повідомити маршрутизатор про
недоступність мережі, може виникнути проблема.
Цей метод маршрутизації застосовується в протоколі маршрутизації RIP,
відомому також як метод рельєфів. Протокол ґрунтується на алгоритмі
Беллмана-Форда та використовується головним чином на нижніх рівнях ієрархії
мережі.
40
У розподіленій маршрутизації можна виділити два алгоритми. Алгоритми
стану каналу (Link State Algorithm, LSA) направляють потоки маршрутної
інформації в усі вузли об'єднаної мережі. Проте кожен роутер надсилає лише ту
частину маршрутної таблиці, де міститься інформація про найближчих сусідів і
мережі, а також дані про метрики для кожного свого з'єднання.
Використовуючи алгоритм найкоротшого шляху (Shortest Path First - SPF),
відомий також як алгоритм Дейкстри, маршрутизатори обчислюють дерево
найкоротших маршрутів до кожного віддаленого вузла, розташовуючи себе в
корені цього дерева [44].
Алгоритми вектора відстані, також відомі як дистанційно-векторні
алгоритми (Distance Vector Algorithm, DVA), вимагають від кожного
маршрутизатора відсилати свою маршрутну таблицю цілком або частково лише
своїм сусідам. Кожен вузол оцінює відстань до кожного сусіда і розсилає цю
інформацію своїм сусідам, які в свою чергу роблять те саме. Дистанція або
відстань, яку зазвичай розглядають, визначається кількістю хопів або переходів
між компонентами мережі, необхідними для досягнення призначення. Цей
процес включає у себе можливість врахування інших метрик, таких як
швидкість або вартість передачі пакета по лінії зв'язку. При формуванні таблиці
маршрутизації вносяться зміни так, щоб у таблиці лишалися лише маршрути з
найкоротшими відстанями. Основна перевага алгоритму вектора відстані
полягає в його простоті, оскільки маршрутизатор взаємодіє лише зі своїми
сусідами, обмінюючись копіями своїх таблиць маршрутизації. Однак його
недоліком є повільна конвергенція, що може викликати утворення петель та
"чорних дір" при зміні топології мережі.
Дистанційно-векторні алгоритми ефективно працюють лише в невеликих
мережах. У великих же мережах вони спричинюють значний навантаження
ліній зв'язку через інтенсивний широкомовний трафік.
Забезпечуючи швидшу збіжність, алгоритми стану каналів менше схильні
до утворення петель маршрутизації, ніж алгоритми вектора відстані. Однак
алгоритми стану каналу визначаються більш складними обчисленнями
41
порівняно з алгоритмами вектора відстані, і вони вимагають великої
процесорної потужності та обсягу пам'яті. До того ж, дистанційно-векторні
алгоритми мають свою власну проблему, яка полягає в ризику зростання до
нескінченності (Count to Infinity) [45]. Це спонукало введення обмежень на
максимальну довжину шляху в усіх протоколах вектора відстані.
Протоколи, засновані на алгоритмах стану каналу, дозволяють кожному
вузлу самостійно обмінюватися інформацією з усіма маршрутизаторами і
отримувати уявлення про топологію мережі. Це робить їх менш схильними до
проблеми зростання до нескінченності, і вони уникнули жорстких обмежень на
діаметр мережі. Однак обов'язкова синхронізація баз даних всіх
маршрутизаторів в межах автономної системи може бути вузьким місцем для
цього підходу. Неспільні уявлення вузлів про топологію мережі можуть
викликати проблеми, такі як утворення петель та інші непередбачувані ситуації.
Додатковою перевагою алгоритмів стану каналу є їх поліпшена ієрархічна
структура, яка дозволяє краще виявляти нестабільні ділянки [44].
Адаптивні алгоритми маршрутизації, які базуються на локальній
інформації, отриманій від сусідніх вузлів, можуть працювати повільно через
обмежену швидкість поширення маршрутної інформації в мережі. Щоб
подолати ці обмеження, деякі алгоритми спробували використовувати
інформацію про стан всієї мережі. Один із підходів до цього - централізована
адаптивна маршрутизація, де центр маршрутизації збирає повідомлення від
кожного вузла про його стан, такий як довжина черг, стан трактів і т. д.
В цьому підході кожен вузол формує повідомлення щодо свого стану і
відсилає його центральному вузлу мережі. Центральний вузол використовує
отримані повідомлення, щоб сформувати глобальну картину стану мережі і
визначити найкращі маршрути для трафіку в мережі. Ці маршрути
розсилаються у вигляді таблиць маршрутизації всім вузлам мережі,
розташованим на конкретному маршруті.
Режим маршрутизації в мережі може бути синхронним або асинхронним
залежно від того, як збирається інформація про стан мережі та розсилаються
42
керуючі директиви. У синхронному режимі всі вузли регулярно надсилають
свої повідомлення і отримують вказівки від центрального вузла встановлені
інтервали часу. У випадку асинхронного режиму такі дії здійснюються тільки
при суттєвих змінах в мережі, що дозволяє зменшити обсяг службової
інформації та оптимізувати процес маршрутизації.
Також, як і в усіх інших методах, централізована адаптивна маршрутизація
має свої недоліки, серед яких можна відзначити концентрацію службового
трафіку поблизу центрального вузла маршрутизації, низьку надійність мережі
при відмові центрального вузла або при ізоляції ділянок мережі від нього, а
також розбіжність у часі отримання вузлами таблиць маршрутизації з різною
затримкою.
Змішана адаптивна маршрутизація, з іншого боку, вирізняється тим, що
вибір маршруту приймається в самих вузлах комутації з урахуванням
рекомендацій центру управління.
Деякі алгоритми маршрутизації діють у плоскому просторі, тоді як інші
використовують ієрархічні структури маршрутизації. У випадку однорівневої
маршрутизації всі роутери розташовані на одному рівні. У ієрархічній
маршрутизації деякі роутери формують базовий рівень маршрутизації, а пакети
пересилаються від небазових роутерів до базових і через них до загальної
області пункту призначення. Така ієрархічна організація дозволяє ефективно
використовувати мережеві ресурси та оптимізувати потік трафіку.
Висновок: Моделі багатоцільової маршрутизації відкривають можливість
вибору компромісних рішень, враховуючи чіткі вимоги до якості
обслуговування (QoS). Ці моделі дозволяють точно визначати цільові функції,
що є відповідними для кожного транспортного потоку. У цій структурі
маршрути зазвичай вибираються з набору непереважаючих маршрутів, тобто
таких, для яких неможливо зменшити значення цільової функції без збільшення
її принаймні з іншими цільовими функціями.
43
РОЗДІЛ 3. ВИКОРИСТАННЯ ТЕХНОЛОГІЇ ІМУННОЇ
МЕРЕЖІ ДЛЯ ОБЧИСЛЕННЯ НАЙКОРОТШОГО
ШЛЯХУ В КОМП'ЮТЕРНИХ МЕРЕЖАХ
Проблема підвищення ефективності пошуку розв'язку оптимізаційної
задачі про найкоротший шлях на основі штучної імунної мережі видається
проблемою знаходження такого впорядкованого набору операторів { , ,
}, ітеративне застосування якого забезпечує знаходження такого розв'язку
, за якого досягається мінімум функції мети, , де - оператор
клонування, - оператор мутації, - оператор стиснення.
Методи оптимізації, що знаходять точне рішення, мають високу
обчислювальну складність. Методи оптимізації, що знаходять наближене
рішення за допомогою спрямованого пошуку, мають високу ймовірність
потрапляння в локальний екстремум. Методи випадкового пошуку не
гарантують збіжність. У зв'язку з цим виникає проблема недостатньої
ефективності методів оптимізації, яка потребує розв'язання.
Для прискореного знаходження квазіоптимального розв'язання задач
оптимізації та зниження ймовірності потрапляння в локальний екстремум
використовують метаевристики (або сучасні евристики) [2-6]. Метаевристика
розширює можливості евристик, комбінуючи евристичні методи на основі
високорівневої стратегії [7-11].
Наявні метаевристики мають один або більше з таких недоліків:
- є тільки абстрактний опис методу або опис методу орієнтований на
розв'язання тільки певної задачі [2];
- не враховується вплив номера ітерації на процес пошуку рішення [3];
- не гарантується збіжність методу [12];
- відсутня можливість використовувати небінарні потенційні рішення [13];
- не автоматизовано процедуру визначення значень параметрів [14];
- відсутня можливість розв'язувати задачі умовної оптимізації [15];
44
- недостатня точність методу [16].
У зв'язку з цим виникає завдання побудови ефективних метаевристичних
методів оптимізації [17-20].
Однією з популярних метаевристик є метод штучної імунної мережі [21].
Для досягнення поставленої мети необхідно вирішити такі завдання:
1. Удосконалити імунний метаевристичний метод на основі штучної
імунної мережі для розв'язання задачі про найкоротший шлях.
2. Удосконалити алгоритм імунного метаевристичного методу на основі
штучної імунної мережі, призначений для реалізації на GPU за допомогою
технології CUDA.
3. Провести чисельне дослідження.
3.1. Метод оптимізації на основі модифікованої
штучної імунної мережі
Пошук маршруту між двома вузлами комп'ютерної мережі може бути
зведений до задачі про найкоротший шлях. Для розв'язання цієї задачі
пропонується імунний метаевристичний метод MAIN - модифікована штучна
імунна мережа, яка використовує випадковий ключ (RK).
Техніка випадкового ключа (Random Key) полягає в тому, що кожній
компоненті невпорядкованого дійсного вектора ставиться у відповідність її
позиція в упорядкованому за зростанням дійсному векторі.
Як функцію мети запропоновано використовувати довжину
найкоротшого шляху від пункту 1 до пункту , що містить пунктів із
можливих,
,
, ,
де - відстань між пунктами і ,
- вектор номерів пунктів (маршрут),
45
- довжина вектора номерів пунктів (довжина маршруту).
Метод MAIN дає змогу знайти квазіоптимальний маршрут між двома
вузлами комп'ютерної мережі і складається з таких блоків (рис. 6).

1. Ініціалізація
2. Обчислення афінності клітин
3. Визначення номера клітини кращої за функцією
цілі на поточній ітерації
4. Визначення клітини кращої за функцією мети за
всіма виконаними ітераціями
5. Обчислення середнього значення функції цілі за
множиною клітин F x
6. Створення безлічі мутованих клонів клітин
(оператори клонування і мутації)
7. Створення безлічі найкращих мутованих клонів
клітин
8. Обчислення середнього значення функції цілі за
множиною найкращих мутованих клонів клітин F h
так
9. F h  F x
нет
10. Заміна множини клітин стислою множиною
найкращих мутованих клонів клітин (оператор
стиснення)
так
11. n=nmax
ні

Рис. 6. Послідовність процедур методу оптимізації на основі
модифікованої штучної імунної мережі
46
Блок 1. Ініціалізація:
- встановлення номера поточної ітерації в 1;
- завдання максимального числа ітерацій ;
- завдання параметра мутації , ;
- завдання порога стиснення , ;
- завдання кількості клітин (відповідає кількості потенційних рішень);
- завдання довжини клітинки (відповідає довжині розв'язку);
- завдання кількості клонів ;
- ініціалізація безлічі клітин (відповідає безлічі потенційних рішень),
використовуючи техніку випадкового ключа і враховуючи пункт відправлення
, , ,
, ,
, ,
, ,
, ,
де - функція, що повертає рівномірно розподілене випадкове число в
діапазоні ,
- функція, що відображає дійсний вектор у цілочисельний
вектор на основі техніки випадкового ключа;
- ініціалізація клітини кращою за функцією мети (відповідає кращому за
функцією мети потенційному рішенню) за всіма виконаними ітераціями

Блок 2. Обчислення афінності клітин
47
, ,
Блок 3. Визначення номера клітини кращої за функцією мети на поточній
ітерації
,
Блок 4. Визначення клітини кращої за функцією мети за всіма виконаними
ітераціями
Якщо , то
Блок 5. Обчислення середнього значення функції мети за множиною клітин

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

Блок 9. Якщо , то перехід до блоку 6.
Блок 10. Заміна множини клітин стислою множиною найкращих
мутованих клонів клітин та ініціалізація незамінених клітин, використовуючи
техніку випадкового ключа і враховуючи пункт відправлення
10.1 Формування -околиці найкращого мутованого клону
,
де - відстань між і (наприклад, відстань Евкліда).
10.2 Встановлення номера клітини
10.3 Якщо кращий мутований клон зберігається після стиснення, тобто
або , то клітина ним замінюється, тобто ,
10.4 Якщо кращий мутований клон не зберігається після стиснення, тобто
або , то клітина ініціалізується, тобто.
, ,
49
,
,
,

10.5 Збільшення номера клітинки, тобто , перехід до блоку 10.3
Блок 11. Якщо не остання ітерація, тобто. , то збільшення номера
ітерації, тобто. , перехід до блоку 2
Результатом є
3.2. Алгоритм імунного метаевристичного методу
Для запропонованого удосконаленого методу MAIN на прикладі пошуку
квазіоптимального маршруту між двома вузлами комп'ютерної мережі
розглядають алгоритм, призначений для реалізації на GPU за допомогою
технології паралельного опрацювання інформації CUDA, що представлений на
рис. 7. Ця блок-схема функціонує таким чином.
Крок 1 - Введення оператором максимального числа ітерацій ,
параметра мутації , порога стиснення , кількості клітин , довжини клітини
.
Крок 2 - Ініціалізація множини клітин .
Крок 3 - Обчислення на основі редукції клітини кращої за функцією мети
(відповідає кращому за функцією мети потенційному рішенню) за всіма
виконаними ітераціями , використовуючи ниток GPU, які згруповані в 1
блок. Кожна нитка обчислює функцію мети .
50

1
2
3
4
5
6
7
8
9
10
-
11
+ 12
-
13
+ 14

Рис. 7. Блок-схема алгоритму MAIN

Крок 4 - Обчислення афінності клітин, використовуючи ниток GPU, які
згруповані в 1 блок. Кожна нитка обчислює
51

Крок 5 - Обчислення на основі редукції номера клітини найкращої за
функцією цілі на поточній ітерації , використовуючи ниток GPU, які
згруповані в 1 блок. Кожна нитка обчислює функцію мети .

Крок 6 - Визначення клітини кращої за функцією мети за всіма виконаними
ітераціями
Якщо , то
Крок 7 - Обчислення на основі редукції середнього значення функції цілі
по безлічі клітин , використовуючи ниток GPU, які згруповані в 1 блок.
Кожна нитка обчислює .
Крок 8 - Обчислення безлічі мутованих клонів клітин ,
використовуючи ниток GPU, які згруповані в блоки. Кожна нитка
обчислює мутований клон у вигляді
, ,
,
,
,
,
52

Крок 9 - Обчислення на основі редукції безлічі найкращих мутованих
клонів клітин , використовуючи ниток GPU, які згруповані в блоки.
Кожна нитка обчислює функцію цілі .
Крок 10 - Обчислення на основі редукції середнього значення функції цілі
за множиною найкращих мутованих клонів клітин , використовуючи ниток
GPU, які згруповані в 1 блок. Кожна нитка обчислює .
Крок 11 - Якщо , то перехід до кроку 8.
Крок 12 - Заміна множини клітин стислою множиною найкращих
мутованих клонів клітин та ініціалізація незамінених клітин. використовуючи
ниток GPU, які згруповані в 1 блок. Кожна нитка виконує такі обчислення:
1. Формування - околиці найкращого мутованого клону
,
2. Якщо заміна клітки, тобто або , то ,

3. якщо ініціалізація незамінених клітин, тобто і
, то
, ,
,
,
,

53
Крок 13 - Якщо не остання ітерація, тобто. , то збільшення номера
ітерації, тобто , перехід до кроку 4
Крок 14 - Запис отриманої глобальної кращої позиції в базу даних.
3.3. Чисельне дослідження
Для задачі про найкоротший шлях пошук рішення проводили на
стандартній базі даних rcsp1.
Результати порівняння запропонованого методу з традиційним методом
штучної імунної мережі подано в таблиці 1.
Таблиця 1
Порівняння запропонованого та традиційного методу штучної імунної мережі
Середньоквадратична помилка методу
запропонованого традиційного
0.02 0.07

Модифікація кроку мутації запропонованого методу оптимізації,
забезпечує сильні зміни клітини і, відповідно, потенційного розв'язку на
початкових ітераціях і слабкі зміни клітини і, відповідно, потенційного розв'язку
на заключних ітераціях. Крім того, для зміни модифікованого кроку мутації не
потрібно додаткових параметрів.
Традиційний метод штучної імунної мережі:
- не враховується номер ітерації, що знижує точність пошуку рішення
(таблиця 1);
- не допускає цілочисельних потенційних рішень, що унеможливлює
дискретну оптимізацію.
Пропонований спосіб дає змогу усунути ці недоліки.
Висновок: Для підвищення точності маршрутизації, було удосконалено імунний
метаевристичний метод на основі штучної імунної мережі для розв'язання задачі
про найкоротший шлях. Запропонований метаевристичний метод забезпечують:
управління швидкістю збіжності методу і забезпечення на початкових ітераціях
глобального пошуку, а на заключних ітераціях локального пошуку за рахунок
54
залежності кроку мутації від номера ітерації; а також можливість дискретної
оптимізації за рахунок техніки випадкового ключа. Удосконалено імунний
метаевристичний алгоритм на основі штучної імунної мережі, призначений для
реалізації на GPU за допомогою технології CUDA
55
РОЗДІЛ 4. ПРАКТИЧНЕ ВТІЛЕННЯ НАУКОВИХ
ДОСЛІДЖЕНЬ
В даному розділі наведемо параметри мережі, які мають протоколи OSPF
та EIGRP. Це дає змогу на практиці дослідити використання маршрутизаторів
Cisco, що в свою чергу дає можливість врахувати теоретичні наробки.
4.1 Маршрутизатори Cisco Systems
Наведемо основні компоненти маршрутизаторів Cisco Systems:
1. Оперативна пам'ять в маршрутизаторах Cisco Systems використовується
для зберігання таблиць маршрутизації в кеші протоколу ARP. Це дозволяє
зберігати пакети на інтерфейсах до їх обробки центральним процесором. Також,
ця пам'ять надає тимчасовий резерв для конфігураційних файлів маршрутизатора
під час його роботи, але очищується при вимкненні маршрутизатора.
2. NVRAM - це енергонезалежна пам'ять, яка містить стару або резервну
копію файлу конфігурації. При вимкненні маршрутизатора пам'ять зберігає свій
вміст.
3. Пам'ять Flash може бути перепрограмованою і використовується для
зберігання образу операційної системи. Це дає можливість оновлювати
програмне забезпечення маршрутизатора.
4. ПЗП (постійно зберігана програма) та RAM (оперативна пам'ять)
використовуються для зберігання мікрокоду та проведення початкового
завантаження та обслуговування маршрутизатора. ПЗП також містить
операційну систему Cisco для відновлення системи.
5. Інтерфейс є засобом мережевого з'єднання, через який передаються дані на
пристрій.
6. Центральний процесор забезпечує обробку даних та запитів до застосувань
і служб безпеки.
При включенні живлення маршрутизатора Cisco виконуються наступні
етапи:
1. Перевірка функціональності компонентів маршрутизатора.
56
2. Запуск коду завантаження, що є мікрокодом ПЗП.
3. Визначення місцезнаходження операційної системи, що запускається, за
допомогою коду завантаження. Зазвичай образ програмного забезпечення
зберігається у Flash-пам'яті.
4. Розпакування програмного забезпечення в оперативну пам'ять і його
запуск кодом завантаження.
5. Зчитування конфігурації з "startup-config", яке за замовчуванням
розміщується в енергонезалежній пам'яті.
6. Завантаження конфігурації.
7. Запуск відлагодженого програмного забезпечення операційної системи.
Основні функції маршрутизаторів включають:
1. Читання заголовка пакетів мережевих протоколів, які завантажуються в
буфер обміну на кожен порт маршрутизатора.
2. Прийняття рішення щодо наступного маршруту направлення.
3. Підключення локальних мереж до глобальної мережі.
4.2. Виконання налаштувань маршрутизатора
Cisco
Конфігурацію маршрутизаторів Cisco можна виконати через інтерфейс
командного рядка за допомогою консолі або терміналу, використовуючи
інтерпретатор «EXEC» в ПЗ Cisco OS.
Маршрутизатор працює у різних режимах. Розглянемо користувацький
режим, який використовується для перевірки стану маршрутизатора. Для виходу
з цього режиму слід використовувати команду "exit".
Також розглянемо привілейований режим, який дозволяє налаштовувати
маршрутизатор. Для входу в цей режим потрібно ввести команду "enable", після
чого слід ввести пароль (якщо він встановлений).

57

Для перегляду списку команд у будь-якому режимі необхідно ввести знак
"?". Cisco OS дозволяє скорочувати команди; наприклад, можна ввести "enab"
замість "enable". У випадку відсутності схожої команди на маршрутизаторі, він
все одно розуміє введену команду.
У режимі глобальної конфігурації можна отримати доступ до
спеціального режиму налаштування маршрутизатора, такого як конфігурування
інтерфейсу, лінії чи протоколу.

Для прикладу можна навести налаштування маршрутизатора:

Для перегляду конфігурації маршрутизатора слід використовувати
команду show interface.
Для налаштування локальної мережі потрібно присвоїти кожному
комп'ютеру у цій мережі IP-адресу. Це може бути зроблено вручну або за
допомогою протоколу DHCP. Останній діє на принципі клієнт-сервер: сервер
DHCP забезпечує автоматичне виділення IP-адресів хостам. Виділення адрес
може відбуватися статично або динамічно на певний часовий інтервал.

58

Для того, щоб провести виключення IP-адрес з наданого пулу, потрібно:

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

Рис. 8. Налаштування статичної маршрутизації

На рисунку 9 наведено налаштування протоколу OSPF.

Рис. 9. Протокол OSPF та його налаштування

59

Команда "show ip route" дозволяє переглядати таблицю маршрутизації,
і на початку цього виводу відображаються коди, які вказують на те, як саме
була отримана відповідна інформація.
Коди: С - connected. S - static. R - RIP. M - mobile. В - BGP. D - EIGRP.
EX - EIGRP external (зовнішній), О - OSPF. IA - OSPF inter area (міжобласний).
N1 - OSPF NSSA external type 1 (зовнішній маршрут NSSA першого типу), N2
-OSPF NSSA external type 2 (зовнішній маршрут NSSA другого типу), El - OSPF
external type 1, E2 - OSPF external type 2, і - IS-IS. su - IS-IS summary, LI - IS-IS
level - 1. L2 - IS-IS level - 2, ia - IS-IS inter area. * - candidate default (вказує
останній, використаний шляха для пересилки маршрутів), U - per-user static
route (користувацький статичніш маршрут), о - ODR (маршрут на вимогу), Р -
periodic downloaded static route (періодично завантажуваний статичний
маршрут).
Після цього виводиться сама таблиця маршрутизації, де усі відомі
мережі мають свої відповідні записи, відзначені відповідними буквеними
кодами. В записах для віддалених мереж також вказані адміністративна
відстань джерела даних, метрика маршруту, адреса наступного переходу, час,
що минув з останнього оновлення, і інтерфейс, через який можна отримати
доступ до віддаленої мережі.

Рис. 10. Процес виведення таблиці маршрутизації
60

На рисунку 10 наведено налаштування протоколу EIGRP.

Рис. 11. Протокол EIGRP та його налаштування

100 - це ідентифікатор системи в автономному режимі, який може бути
або зареєстрованим, або приватним номером. У випадку роботи різних
маршрутизаторів в межах однієї автономної системи, вони використовують
один і той же номер системи для обміну інформацією.
За замовчуванням, протокол EIGRP автоматично здійснює
балансування навантаження, наприклад, використовуючи чотири маршрути з
однаковою метрикою. Щоб відключити балансування навантаження, слід
встановити кількість маршрутів, рівну 1. Для здійснення цієї зміни потрібно:

Залежно від обробки пакетів на маршрутизаторі у системі балансування
навантаження можна використовувати команду "per-packet", яка
застосовується до кожного окремого пакету, або "per-destination", яка
використовується для кожної окремої адреси призначення.
Балансування навантаження за адресою призначення означає, що
маршрутизатор розподіляє пакети в залежності від їхніх адрес призначення. У
випадку, якщо існують два шляхи доступу до однієї мережі, всі пакети для
призначення 1 направляються по першому шляху, а пакети для призначення 2
61
- по другому, і так далі. При цьому підтримується порядок пакетів, хоча може
виникнути нерівномірне використання каналів.
Балансування навантаження за пакетами означає, що маршрутизатор
надсилає один пакет для призначення 1 по першому шляху, інший пакет для
того ж призначення 1 по другому шляху і так далі. Це гарантує більш
рівномірний розподіл навантаження між усіма каналами. Однак можливе
порушення порядку прибуття пакетів через різну затримку в мережі.
EIGRP може розподіляти трафік по кількох маршрутах з різною
метрикою, що регулюється параметром variance.

Зокрема, значення "variance" може лежати у діапазоні від 1 до 128. Це є
множником, на який множиться "FD" (фактична відстань), щоб визначити
"feasible" маршрути. Балансування навантаження буде застосовуватися тільки
між "feasible routes", які потрапляють до таблиці маршрутизації.
Маршрут можна вважати "feasible", коли виконуються дві умови:
● FD для найкращого маршруту повинен бути більшим, ніж AD, що
призводить до оголошення сусіднього маршрутизатора. Це означає, що
наступний маршрутизатор на шляху повинен бути ближчим до
"destination", ніж власний локальний маршрутизатор, щоб уникнути
петлі маршрутизації.
● FD для найкращого маршруту помножується на "variance", яке, в свою
чергу, повинно бути більше, ніж FD для альтернативного маршруту.

4.3 Забезпечення безпеки за допомогою VPN
Налаштування Site-to-Site VPN з використанням
технології тунелювання IPsec
Класичні методи створення тунелів між віддаленими мережами, такі як
застосування технологій MPLS чи GRE, обмежені лише передачею трафіку між
мережами, не забезпечуючи високого рівня безпеки, який вимагається в
62
сучасному середовищі. Основні недоліки включають відсутність шифрування,
обмежені методи аутентифікації та недостатню гнучкість політик безпеки.
Застосування технології тунелювання IPsec дозволяє уникнути цих обмежень і
забезпечити високий рівень безпеки.
Тому в даному етапі дослідження основна увага приділена методу
створення тунелів за допомогою технології IPsec. Ця передова технологія
отримала підтримку від основних виробників активного обладнання. Особливо
варто відзначити, що лише обладнання від Cisco Systems дозволяє реалізувати
найсучасніші методи створення безпечних тунелів, такі як:
• Cisco IPSec VTI (Віртуальний Тунельний Інтерфейс) - це метод створення
віртуальних інтерфейсів для маршрутизації зашифрованих тунелів IPsec.
Усі дані, які проходять через такий тунель, автоматично піддаються
шифруванню, і цей підхід значно спрощує конфігурацію пристроїв.
• Dynamic Multipoint VPN - ця технологія також підтримує як статичну, так
і динамічну маршрутизацію. Вона вирізняється можливістю
автоматичного встановлення тунелю при підключенні нових віддалених
мереж.
• Flex VPN - це найбільш універсальний підхід від Cisco, який дозволяє
конфігурувати всі типи тунелів однаково. Однією з важливих переваг цієї
технології є автоматичний захист VPN мережі від DDoS-атак. Крім того,
технологія сумісна з мережами VPN, побудованими на обладнанні інших
виробників.
Тому в даному відділі роботи розглядається конфігурація IPsec VPN як
основи для всіх сучасних методів захищеного тунелювання. У цьому розділі
дипломної роботи буде створена та налаштована мережа з декількома
маршрутизаторами, де для налаштування VPN буде використано Cisco IOS для
реалізації Site-to-Site, а після цього - проведено тестування VPN. Тунель VPN
IPsec прокладається від R1 до R3 через R2 (див. рис. 4.1, табл. 4.1). R2 виступає
як "прохідний" маршрутизатор і не володіє інформацією щодо VPN. IPsec
забезпечує безпечний обмін конфіденційною інформацією через незахищені
63
мережі, такі як Інтернет. Діючи на мережевому рівні, IPsec захищає та
аутентифікує IP-пакети між учасниками пристроїв IPsec, такими як
маршрутизатори Cisco.

Рис. 12 Топологія мережі для реалізації Site-to-Site VPN

Базова конфігурація пристроїв включає в себе наступне:
- Налаштування імен хостів, IP-адрес інтерфейсів і паролів доступу.
- Налаштування протоколу маршрутизації OSPF.
Щодо VPN від точки до точки з використанням Cisco IOS включає такі
етапи:
- Налаштування параметрів IPsec VPN на R1 та R3.
- Перевірка налаштувань IPsec VPN від точки до точки.
- Перевірка роботи IPsec VPN.
Реалізація VPN Site-to-Site зазвичай забезпечує захищений тунель
(використовуючи IPsec або інші протоколи) між філією та центральним офісом.
Також, іншим популярним використанням технології VPN є віддалений доступ
до корпоративного офісу з робочого місця, наприклад, з невеликого офісу чи
домашнього офісу.

64
Таблиця 2
IP-адресація

Необхідне обладнання для даного проекту включає:
- 3 маршрутизатори (Cisco 1841 з Cisco IOS версії 15.1 (4) M12А та
ліцензією технологічного пакета безпеки – advipservicesk9, Cisco 2811 з
Cisco IOS версії 15.1 (4) M12a і ліцензією технологічного пакета безпеки
- advipservicesk9);
- 2 комутатори (Cisco 3560-48TS-S та 3750-48PS-S);
- 2 ПК (Windows, програма Putty з терміналом та клієнтом SSH);
- Послідовний (Serial) і Ethernet-кабелі;
- WAN-модулі WIC-2T для зв’язку між маршрутизаторами;
- Консольні кабелі для налаштування мережевих пристроїв Cisco.

Далі буде створена мережева топологія, та будуть налаштовані основні
параметри, такі як IP-адреси інтерфейсів, динамічна маршрутизація, доступ до
пристроїв та паролі.
Крок 1: Проведення мережевого підключення згідно з топологією (рис. 12).
Крок 2: Налаштування основних параметрів для кожного маршрутизатора
(табл. 2).
- Налаштування імен хостів;
- Налаштування IP-адрес інтерфейсів;
65
- Налаштування тактової частоти 64000 (clock rate) для послідовних
інтерфейсів маршрутизатора із підключеним послідовним кабелем Serial
DCE.
Крок 3: Вимкнення пошуку DNS.
Необхідно вимкнути пошук DNS, щоб уникнути спроб маршрутизатора
обробити неправильно введені команди.
Крок 4: Налаштування протоколу маршрутизації OSPF на R1, R2 та R3.
1. На R1 виконати наступні команди:

2. На R2 мають бути виконані наступні команди:

3. На R3 мають бути виконані наступні команди:

Крок 5: Налаштування параметрів IP-адресації клієнтського ПК.
1. Здійснення налаштування статичної IP-адресації, маски підмережі та
шлюзу за замовчуванням для PC-A відповідно до вказаних значень у
таблиці IP-адресації.
2. Конфігурування статичної IP-адресації, маски підмережі та шлюзу за
замовчуванням для PC-C, використовуючи зазначені значення у таблиці
IP-адресації.
Крок 6: Перевірка основного з'єднання з мережею.
Проведення пінг-запиту від R1 до інтерфейсу R3 Fa0/1 за IP-адресою
192.168.3.1 та від PC-A в локальній мережі R1 до PC-C в локальній мережі R3.
Крок 7: Налаштування та шифрування паролів.
66
Встановлення мінімальної довжини пароля за допомогою команди
"security passwords" і вказання мінімальної довжини 10 символів.
Задання секретного пароля "cisco12345" командою enable secret з
використанням алгоритму хешування типу 9 (SCRYPT) на обох
маршрутизаторах.
Створення локального облікового запису "itsvpn61" з паролем "61itsvpn61"
та використання алгоритму хешування типу 9 (SCRYPT).
Крок 8: Налаштування консольного підключення.
Налаштування консолі для використання локальної бази даних для входу
та встановлення тайм-ауту виходу через п'ять хвилин бездіяльності.
Використання команди "logging synchronous" для уникнення переривання
введення команд повідомленнями.
Крок 9: Збереження робочої конфігурації для всіх трьох маршрутизаторів.
Збереження поточної конфігурації у конфігурацію запуску в
привілейованому режимі EXEC на всіх маршрутизаторах за допомогою команди
"copy running-config startup-config".
Конфігурація VPN для втілення Site-to-Site за допомогою
Cisco IOS.
Наступним кроком буде налаштування IPsec VPN тунелю між
маршрутизаторами R1 та R3, через маршрутизатор R2. Конфігурація буде
виконана за допомогою інтерфейсу командного рядка (CLI) Cisco IOS. Після
цього буде проведене тестування налаштувань для перевірки їх правильності та
ефективності.
Крок 1: Перевірка з'єднання від мережі R1 до мережі R3. Під час цього
завдання можна переконатися, що комп'ютер PC-A в локальній мережі R1 може
виконати пінг до комп'ютера PC-C в локальній мережі R3 без використання VPN
тунелю. Здійснити пінг на IP-адресу PC-C, 192.168.3.3, з PC-A.

Крок 2: Налаштування IPsec VPN на маршрутизаторах R1, R2 та R3.
67
На маршрутизаторі R1 введіть наступні команди:
R1(config)# crypto isakmp policy 10
R1(config-isakmp)# authentication pre-share
R1(config-isakmp)# encryption aes
R1(config-isakmp)# hash sha
R1(config-isakmp)# group 2
R1(config-isakmp)# exit

R1(config)# crypto isakmp key cisco12345 address 192.168.2.2
R1(config)# crypto isakmp key cisco12345 address 192.168.3.3

R1(config)# crypto ipsec transform-set myset esp-aes esp-sha-hmac
R1(cfg-crypto-trans)# exit

R1(config)# crypto map mymap 10 ipsec-isakmp
R1(config-crypto-map)# set peer 192.168.2.2
R1(config-crypto-map)# set peer 192.168.3.3
R1(config-crypto-map)# set transform-set myset
R1(config-crypto-map)# match address 100

На маршрутизаторі R2 введіть аналогічні команди, враховуючи
відповідні IP-адреси та параметри.
На маршрутизаторі R3 введіть наступні команди, знову враховуючи
конкретні IP-адреси:
R3(config)# crypto isakmp policy 10
R3(config-isakmp)# authentication pre-share
R3(config-isakmp)# encryption aes
R3(config-isakmp)# hash sha
R3(config-isakmp)# group 2
68
R3(config-isakmp)# exit

R3(config)# crypto isakmp key cisco12345 address 192.168.1.1
R3(config)# crypto isakmp key cisco12345 address 192.168.2.2

R3(config)# crypto ipsec transform-set myset esp-aes esp-sha-hmac
R3(cfg-crypto-trans)# exit

R3(config)# crypto map mymap 10 ipsec-isakmp
R3(config-crypto-map)# set peer 192.168.1.1
R3(config-crypto-map)# set peer 192.168.2.2
R3(config-crypto-map)# set transform-set myset
R3(config-crypto-map)# match address 100

Крок 3: Налаштування асоціативного списку (ACL) на маршрутизаторі
R1.
R1(config)# access-list 100 permit ip 192.168.1.0 0.0.0.255 192.168.3.0 0.0.0.255

Це дозволяє трафіку від локальної мережі R1 доходити до локальної
мережі R3 через тунель VPN.
Крок 4: Активація криптографії на інтерфейсах.
R1(config)# interface f0/1
R1(config-if)# crypto map mymap

Крок 5: Перевірка налаштувань.
Використовуйте команду `show crypto isakmp sa` та `show crypto ipsec sa`
на кожному маршрутизаторі, щоб перевірити стан асоціацій ISAKMP та IPsec.
Крок 6: Проведення пінг-запиту від PC-A до PC-C.
PC-A> ping 192.168.3.3
69
Це завершить налаштування VPN між маршрутизаторами R1, R2 та R3 за
допомогою Cisco IOS.
Також можна налаштувати час роботи безпечного IPsec-зв'язку на 1800
секунд або 30 хвилин замість стандартних 3600 секунд на маршрутизаторах R1 і
R3.

Крок 7. Визначення ключового трафіку.
Для використання шифрування VPN з IPsec необхідно задати розширені
списки доступу, щоб інструктувати маршрутизатор щодо того, який трафік має
бути зашифрованим. Пакети, які відповідають правилам списку доступу,
використаного для ідентифікації трафіку IPsec, будуть шифруватися, якщо сеанс
IPsec правильно налаштовано. Пакети, які не відповідають жодному з правил
списку доступу, не будуть відкидатися, а замість цього передаватимуться без
шифрування. Також, як у будь-якому іншому списку доступу, на кінці існує
неявне відхилення, що означає, що трафік не шифрується за замовчуванням.
У випадку неправильної настройки безпеки IPsec трафік залишається
незашифрованим, передаючись відправнику. З точки зору R1 важливий трафік,
який потрібно шифрувати, включає трафік від Ethernet LAN R1 до Ethernet LAN
R3 або у зворотньому напрямку, в залежності від точки зору R3. Ці списки
доступу використовуються на вихідних інтерфейсах кінцевих точок VPN і
повинні збігатися.
1. Налаштувати фільтрацію трафіку IPsec VPN на R1.

2. Налаштувати фільтрацію трафіку IPsec VPN на R2.

Крок 7: Створення та застосування криптокартки.
Криптокартка асоціює трафік, відповідальний за вказаний список
контролю доступу користувача, і різні налаштування IKE та IPsec. Вона включає
в себе список контролю доступу, IP-адресу кінцевого користувача, набір
70
трансформацій та тип конфіденційності переадресації. Після створення
криптокартки її можна застосовувати до одного чи кількох інтерфейсів, і ці
інтерфейси повинні бути на боці користувача.
Для створення криптокартки використовується команда crypto map
<name> <sequence-num> <type> у режимі глобальної конфігурації для введення
конфігурації криптокартки для вказаного порядкового номера. Кілька виразів
криптокартки можуть бути призначені одній та тій же криптокартці та
оцінюватися у порядку зростання. Потрібно увійти в режим конфігурації
криптокартки на R1, використовуючи тип ipsec-isakmp, що вказує на
використання IKE для створення безпечного IPsec-з'єднання.
Створити криптокартку на R1 із назвою CMAP та порядковим номером 10.
Після введення команди з'явиться відповідне повідомлення.

Скористатися командою match address <access-list>, щоб вказати список
доступу, який визначає трафік для шифрування.

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

Для налаштування віддаленої IP-адреси або імені користувача варто
використовувати наступну команду, що дозволяє встановити його на
віддаленому інтерфейсі кінцевої точки VPN R3.

71
Для жорсткого кодування набору перетворень, який буде
використовуватися з цим користувачем, використовуйте команду `set transform-
set <tag>`. Також необхідно встановити тип секретності переадресації,
використовуючи команду `set pfs <type>`, і змінити час життя безпечного зв’язку
IPsec за замовчуванням за допомогою команди `set security-association lifetime
seconds <seconds>`.

Створити відповідну крипто карту на R3.

Застосувати крипто карту до інтерфейсів.

Крок 8: Перевірка конфігурації Site-to-Site VPN з тунелюванням IPsec.
Використання розширеного пінгу від R1 до IP-адреси інтерфейсу R3 F0/1
192.168.3.1 дозволяє контролювати адресу джерела пакетів.
72

З виводу команди ми бачимо, що є зв’язок між двома віддаленими
клієнтами.
Вводячи команду show crypto isakmp sa, бачимо, що створено безпечний
зв’язок між маршрутизаторами R1 та R3.

Конфігурація віддаленого доступу до VPN з
використанням IPsec тунелювання.
На відміну від реалізації Site-to-Site VPN, яка передбачає створення
тунелів між віддаленими маршрутизаторами, метод VPN віддаленого доступу
(Remote Access VPN) є дуже популярним і використовується для забезпечення
віддаленого доступу до корпоративного офісу, наприклад, з невеликого або
домашнього офісу (SOHO). У цьому випадку більшість налаштувань
виконується на головному маршрутизаторі, який виступає у ролі VPN-сервера.
Щоб користувач мав можливість отримати доступ до мережі головного офісу,
йому достатньо встановити та налаштувати клієнтське програмне забезпечення
на своєму ПК, таке як Cisco VPN Client або Cisco AnyConnect.
73
Настроюється VPN для віддаленого доступу між клієнтським комп'ютером
та імітованою корпоративною мережею. Налаштування маршрутизаторів можна
виконати як за допомогою інтерфейсу командного рядка (CLI), так і за
допомогою більш зрозумілого інструмента Cisco Security Device Manager (SDM),
який надає зручний веб-інтерфейс для конфігурації та моніторингу пристроїв з
Cisco IOS.
SDM використовується для конфігурації сервера Cisco Easy VPN на
головному корпоративному маршрутизаторі (що є граничним шлюзом за
замовчуванням) і для налаштування клієнта VPN Cisco на хості. Після цього
відбувається підключення до корпоративної мережі через модельований
маршрутизатор провайдера.
Клієнт VPN Cisco надає можливість організаціям встановлювати
зашифровані IPsec VPN тунелі для безпечного з'єднання віддалених
користувачів. Він підтримує Cisco Easy VPN, що дозволяє клієнту отримувати
політику безпеки при підключенні до VPN тунелю від центрального пристрою
VPN (сервер Cisco Easy VPN), зменшуючи вимоги до конфігурації у віддаленій
мережі. Це ефективне рішення для сценаріїв віддаленого доступу, де
налаштування політик для кількох віддалених ПК індивідуально є
неефективним.
Топологія підключень та основні налаштування експериментального
стенду показані на рисунку 13.
74

Рис. 13. Топологія мережі для сценарію Remote Access VPN

Перелік основного обладнання, модулів та кабелів залишається незмінним,
як вказано в попередньому розділі цієї роботи (таблиця 3).
Таблиця 3
IP-адресація

75
Частина 1: Базова конфігурація маршрутизаторів
Крок 1: Проведення підключення мережі відповідно до топології (див.
рисунок 13).
Здійснення з'єднання пристроїв згідно з представленою топологічною
схемою.
Крок 2: Налаштування основних параметрів для кожного маршрутизатора
(див. Таблицю 3).
- Встановлення IP-адрес фізичних інтерфейсів, згідно з інформацією у
Таблиці 4.2 IP-адресації.
- Конфігурація інтерфейсу логічної петлі Loopback0 на R2. Ця дія імітує
мережу, з якої клієнти віддаленого доступу отримують адреси
(192.168.2.0/24).

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

Ця команда встановлює тактову частоту на значення 64000 біт на секунду
для послідовного інтерфейсу, який використовує кабель DCE. Ви можете
змінити значення 64000 на іншу відповідну частоту в разі необхідності.
Крок 3: Вимкнення служби DNS.
Для запобігання спробам маршрутизатора обробляти неправильно введені
команди важливо вимкнути службу DNS. Використайте наступну команду:

Ця команда вимикає пошук DNS на маршрутизаторі, заважаючи йому
інтерпретувати некоректні команди через DNS.
Крок 4: Налаштування протоколу маршрутизації EIGRP на R2 та R3.
76

Оскільки R1 виступає в ролі маршрутизатора Інтернет-сервіс-провайдера
(ISP) і не приймає участь у процесі маршрутизації EIGRP, проведемо
налаштування на R2 з введенням наступних команд:

На R3 наступні команди:

Крок 5: Налаштування статичного маршруту за замовчуванням до R2.
Оскільки маршрутизатор R1 відповідає за забезпечення з'єднання з
Інтернетом, на R2 налаштовується статичний маршрут за замовчуванням для
всього трафіку, що має мережевий призначення, відсутнє в таблиці
маршрутизації R2. Це виконується наступним чином:

Перерозподіл статичного маршруту за замовчуванням в EIGRP для
вивчення R3. Однією з ключових дій для забезпечення оптимальної
маршрутизації є перерозподіл статичного маршруту за замовчуванням в
протокол EIGRP на R2, з метою навчання маршрутизатор R3 цьому маршруту.
Для цього виконайте наступні команди:

Крок 6: Налаштування параметрів IP для комп'ютерів.
1. Налаштування статичної IP-адреси, маски підмережі та шлюзу за
замовчуванням для PC-A, відповідно до інформації в таблиці 4.2 IP-
адресації.
2. Налаштування статичної IP-адреси, маски підмережі та шлюзу за
замовчуванням для PC-C, відповідно до даних з таблиці 4.2 IP-
адресації.
77
Крок 7: Перевірка базового підключення до мережі.
Проведення пінг-запиту з PC-A на інтерфейс R2 S0/0/0 за IP-адресою
10.1.1.2 та від R2 до PC-C в локальній мережі R3.
Крок 8: Налаштування мінімальної довжини пароля.
Використовуйте команду "security passwords", щоб встановити мінімальну
довжину пароля в 10 символів.

Крок 9: Налаштування основних ліній консолі та ліній підключення vty
через протокол telnet.
1 Налаштування пароля та встановлення логіну для консолі
маршрутизатора R1.
2 Додавання паролю та створення логіну для ліній підключення vty за
допомогою протоколу telnet.
3 Для підвищення безпеки, встановлення таймеру автоматичного виходу з
рядка (exec-timeout) після 5 хвилин бездіяльності.
4 Використання команди logging-synchronous для запобігання перериванню
введення команд консольними повідомленнями.

Встановлення пароля у рядках vty для маршрутизатора R1.

Такий самий алгоритм шифрування відкритих текстових паролів на
маршрутизаторах R2 та R3.
Для забезпечення безпеки, використовуйте команду service password-
encryption для шифрування паролів консолі, aux та vty на маршрутизаторах R2 та
R3.

78
Крок 10: Збереження основної робочої конфігурації на всіх трьох
маршрутизаторах.
Використаємо команду "copy running-config startup-config" для збереження
поточної конфігурації у робочу конфігурацію, щоб вона автоматично
завантажувалася при перезапуску, на всіх трьох маршрутизаторах.

Частина 2: Налаштування VPN для віддаленого доступу
У частині 2 здійснюється налаштування віддаленого доступу до IPsec VPN.
R2 налаштований як сервер Easy VPN за допомогою SDM, а клієнт Cisco VPN
налаштований на ПК-A. ПК-A імітує співробітника, який намагається отримати
доступ з дому через Інтернет. Маршрутизатор R1 імітує маршрутизатор
Інтернет-провайдера.
Крок 1. Налаштування доступу за допомогою команди enable secret та
маршрутизатора HTTP перед запуском SDM.
У командному рядку встановіть секретний пароль за допомогою команди
enable secret для використання з SDM на R2.

Вмикаємо HTTP-сервер на R2.

Створіть акаунт "admin" з рівнем привілегій 15 за допомогою наступної
команди:

Висновок: У цьому розділі розглянуті налаштування технологій Site-to-Site VPN
та Remote Access VPN, обидві з використанням технології тунелювання IPSec.
Всі вказані конфігурації були виконані на спеціально підготовленому
експериментальному стенді. Також у цьому розділі були проведені початкові
налаштування маршрутизації для протоколів OSPF та EIGRP на обладнанні від
компанії Cisco.
79
ВИСНОВКИ
У кваліфікаційній роботі магістра вирішені наступні задачі:
• Проведено аналіз існуючих адаптивних алгоритмів, що дали можливість
оцінити та порівняти існуючі методів маршрутизації в умовах змінюючоїся
структури та обсягу трафіку. Такі параметри, як алгоритми, методи та
протоколи маршрутизації, переважно визначають сферу застосування
маршрутизаторів (їхню функціональність) в сучасних комутаційних
мережах. З іншого боку, архітектура є ключовою характеристикою
продуктивності, надійності і вартості кінцевого обладнання. Дослідження
показують, що для розгортання мереж із гнучкою топологією розумно
використовувати обладнання, що підтримує методи адаптивної
маршрутизації, тоді як для мереж із фіксованими вузлами, розташованими на
великій території, найбільш ефективним буде використання маршрутизації зі
статичним методом.
• Масштабованість, що дало змогу визначити можливості застосування
розроблених алгоритмів в масштабах великих мереж. Багатоцільові моделі
маршрутизації дозволяють вибирати компромісні рішення в межах чітких
вимог до якості обслуговування (QoS). Ці моделі дозволяють точно
визначати цільові функції та відповідні метрики для кожного транспортного
потоку. У такій структурі зазвичай вибираються набори непереважаючих
маршрутів, тобто маршрутів, для яких в мінімізації неможливо зменшити
значення цільової функції без збільшення її значення для інших цільових
функцій принаймні на мінімальне значення.
• Удосконалено метод та алгоритм, за рахунок створення адаптивних
удосконалених маршрутизаційних алгоритмів, що забезпечують ефективну
адаптацію до динамічних змін у мережі, а саме – запропонований
удосконалений метод оптимізації на основі імунної метаевристики може
використовуватися для інтелектуалізації комп'ютерних систем керування
комп'ютерними мережами. Перспективи подальших досліджень полягають у
тестуванні запропонованих методів на ширшому наборі тестових баз даних.
80
• Враховані вимоги безпеки, за рахунок сучасних аспектів безпеки мережі та
врахування їх у нових алгоритмах маршрутизації. Проведена
експериментальна валідація, а саме – проведено експерименти та аналіз
результатів для визначення ефективності та продуктивності удосконалених
алгоритмів у реальних чи симульованих умовах, що дало змогу отримати
порівняльні показники з існуючими системами.
• Розроблена апаратну модель захищеної мережі та проведені
експериментальні дослідження зразків, що дозволило підтвердити
можливість використання цих розробок у запропонованій моделі. Виконані
конфігурації включають в себе Site-to-Site VPN за допомогою технології
тунелювання IPSec та Remote Access VPN із застосуванням IPSec для
тунелювання. Усі ці параметри були встановлені та протестовані на
експериментальній платформі. Також проведено розробку початкових
налаштувань маршрутизації протоколів «OSPF та EIGRP» для обладнання
компанії Cisco.
81
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. M. Z. Kwiatkowska, O. Sljivo, M. J. M. Marforio: Adaptive Routing Algorithms
for Communication Networks: A Comprehensive Survey (2006).
2. S. Hu, Y. Bi, Y. Zhang. "Adaptive Routing in Software-Defined Networking: A
Survey", 2018 Fifth International Conference on Software Defined Systems (SDS),
2018, doi:10.1109/sds.2018.8370418.
3. Y. Luo, X. Chen, G. Ding. "Machine Learning Techniques for Routing in Computer
Networks: A Comprehensive Survey", Journal of Network and Computer
Applications, vol. 181, 2021, p. 103005.
4. A. Pandey, S. Dey. “Configurable Secured Adaptive Routing Protocol for Mobile
Wireless Sensor Networks.” International Journal of Electronics and
Telecommunications, 2023, doi:10.24425/ijet.2022.141277.
5. D. B. Johnson, D. A. Maltz. “ Dynamic Source Routing in Ad Hoc Wireless
Networks” Ad Hoc Networks, vol. 110, 2021, p. 102301.
6. Wu, Jingxin, et al. “Dynamic Routing and Spectrum Assignment for Multi-Fiber
Elastic Optical Networks.” Advanced Photonics 2018 (BGPP, IPR, NP, NOMA,
Sensors, Networks, SPPCom, SOF), 2018, doi:10.1364/networks.2018.netu4f.1.
7. Perepelkin, Dmitry, and Tin Nguyen. “Research of Multipath Routing and Load
Balancing Processes in Software Defined Networks Based on Artificial Bee Colony
Algorithm.” 2022 ELEKTRO (ELEKTRO), 2022,
doi:10.1109/elektro53996.2022.9803416.
8. R. D. C. Monteiro, E. R. H. F. Aoki. Dynamic Routing Strategies for the Evolution
of Communication Networks: A Survey. Security and Communication Networks,
vol. 2023, 2023, pp. 1–10.
9. Zhou, Qian, and Ye Zheng. “Long Link Wireless Sensor Routing Optimization
Based on Improved Adaptive Ant Colony Algorithm.” International Journal of
Wireless Information Networks, vol. 27, no. 2, 2019, pp. 241–252,
doi:10.1007/s10776-019-00452-9.
82
10. N. Mittal, D. P. Sharma, et al. “ A Comprehensive Review on Dynamic Routing
Protocols in WSNs ” 2015 4th International Conference on Reliability, Infocom
Technologies and Optimization (ICRITO) (Trends and Future Directions), 2015.
11. "Computer Networking: Principles, Protocols and Practice" by Olivier
Bonaventure.
12. Tanenbaum, A. S., Wetherall, D. Computer Networks. Pearson Education. (2014).
13. Pióro, Michał, and Deepankar Medhi. Routing, Flow, and Capacity Design in
Communication and Computer Networks. Morgan Kaufmann, 2014.
14. Toh, Chai-Keong. Ad Hoc Mobile Wireless Networks: Protocols and Systems.
Prentice Hall PTR, 2002.
15. Medhi, Deepankar, and Karthikeyan Ramasamy. Network Routing: Algorithms,
Protocols, and Architectures. MK Morgan Kaufmann Publishers an Imprint of
Elsevier, 2018.
16. Ramaswami, Rajiv, et al. Optical Networks: A Practical Perspective. Elsevier,
2010.
17. Malhotra, R.: IP routing: O'Reilly (2002).
18. Halabi, S., McPherson, D.: Internet routing architectures: Cisco Press (2010).
19. Conte, M.: Dynamic routing in broadband networks. Kluwer Academic Publishers
(2003).
20. Ash, G.R.: Dynamic routing in telecommunications networks. McGraw-Hill
(1998).
21. Liu, D., Barber, B., Digrande, L.: Routing Protocols. Cisco CCNA/CCENT Exam
640-802, 640-822, 640-816 Preparation Kit. 169–196 (2009). doi:10.1016/b978-1-
59749-306-2.00009-9.
22. Goralski, W.: IGPs. The Illustrated Network. 375–408 (2017). doi:10.1016/b978-
0-12-811027-0.00015-1.
23. Medhi, D., Ramasamy, K.: Routing Protocols: Framework and Principles. Network
Routing. 64–113 (2018). doi:10.1016/b978-0-12-800737-2.00004-1.
24. Kumar, A., Kuri, J., Manjunath, D.: Communication networking an analytical
approach. Elsevier/Morgan Kaufmann (2004).
83
25. Medhi, D., Ramasamy, K.: IP Routing and Distance Vector Protocol Family.
Network Routing. 160–182 (2018). doi:10.1016/b978-0-12-800737-2.00007-7.
26. Valadas, R.: Principles of Single-Area Link State Routing. OSPF and IS-IS. 43–
113 (2019). doi:10.1201/9780429027543-2.
27. Goralski, W.: The Illustrated network: how TCP/IP works in a modern network.
Morgan Kaufmann (2017).
28. Dearlove, C., Clausen, T.: Routing Multipoint Relay Optimization for the
Optimized Link State Routing Protocol Version 2 (OLSRv2). (2014).
doi:10.17487/rfc7187.
29. White, R., McPherson, D., Srihari, S., Rekhter, Y.: Practical BGP. Addison-Wesley
(2005).
30. Medhi, D., Ramasamy, K.: Routing Algorithms: Shortest Path, Widest Path, and
Spanning Tree. Network Routing. 30–63 (2018). doi:10.1016/b978-0-12-800737-
2.00003-x.
31. Leong, B., Mitra, S., Liskov, B.: Path Vector Face Routing: Geographic Routing
with Local Face Information. 13TH IEEE International Conference on Network
Protocols (ICNP'05). doi:10.1109/icnp.2005.32.
32. Ahuja, R.K., Mehlhorn, K., Orlin, J., Tarjan, R.E.: Faster algorithms for the shortest
path problem. Journal of the ACM (JACM). 37, 213–223 (1990).
doi:10.1145/77600.77615.
33. Bellman, R.: On a routing problem. Quarterly of Applied Mathematics. 16, 87–90
(1958). doi:10.1090/qam/102435.
34. Ford, L. R., Network Flow Theory. Santa Monica, CA: RAND Corporation, 1956.
35. Bertsekas, D.P.: Linear network optimization: algorithms and codes. The MIT Press
(1992).
36. Elmasry, A., Shokry, A.: A new algorithm for the shortest‐path problem. Networks.
74, 16–39 (2018). doi:10.1002/net.21870.
37. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische
Mathematik. 1, 269–271 (1959). doi:10.1007/bf01386390.
84
38. Medhi, D., Ramasamy, K.: Routing Algorithms. Network Routing. 30–54 (2007).
doi:10.1016/b978-012088588-6/50005-x.
39. Banner, R., Orda, A.: Multipath Routing Algorithms for Congestion Minimization.
IEEE/ACM Transactions on Networking. 15, 413–424 (2007).
doi:10.1109/tnet.2007.892850.
40. Floyd, R.W.: Algorithm 97: Shortest path. Communications of the ACM. 5, 345
(1962). doi:10.1145/367766.368168.
41. Panda, R.K., Veeramalla, J.: Hybrid solid state contactor for AC-3 electrical life test
setup. 2014 Annual IEEE India Conference (INDICON). (2014).
doi:10.1109/indicon.2014.7030503.
42. Delling, D., Sanders, P., Schultes, D., Wagner, D.: Engineering Route Planning
Algorithms. Algorithmics of Large and Complex Networks. LNCS. Springer,
Heidelberg, 5515, 117–139 (2009).
43. Goldberg, A.V., Harrelson, C. Computing the shortest path: A-star search meets
graph theory. Proc. of the sixteenth annual ACM-SIAM symposium on Discrete
algorithms, 156–165 (2005).
44. Johnson, D.B.: Efficient Algorithms for Shortest Paths in Sparse Networks. Journal
of the ACM (JACM). 24, 1–13 (1977). doi:10.1145/321992.321993.
45. Lee, C.Y.: An Algorithm for Path Connections and Its Applications. IEEE
Transactions on Electronic Computers. EC-10, 346–365 (1961).
doi:10.1109/tec.1961.5219222.
46. Rubin, F.: The Lee Path Connection Algorithm. IEEE Transactions on Computers.
C-23, 907–914 (1974). doi:10.1109/t-c.1974.224054.
47. Bjornsson, Y., Enzenberger, M., Holte R.C., Schaeffer, J.: Fringe Search: Beating
A* at Pathfinding on Game Maps. Proceedings of IEEE Symposium on
Computational Intelligence and Games, Essex, pp. 125–132 (2005).
48. Gifford, C. (2016). Computer Networks. Wayland.
49. TXOne networks: 2021 cyber security report. (2022). Computer Fraud Security,
2022(2). https://doi.org/10.12968/s1361-3723(22)70014-0
50. United States Government Accountability Office. (2014). Information security:
85
51. Whitman, M. E., Mattord, H. J. (2022). Principles of Information Security.
Cengage.
52. Winkler, I. (2007). Information security is information security. Zen and the Art of
Information Security, 111–114. https://doi.org/10.1016/b978-159749168-6/50012
53. D. Gollmann, Computer Security, 3rd ed. Wiley, 2011.

ChSTU repository

ChSTU repository preserves and enables easy and open access to all types of digital content including text, images, moving images, mpegs and data sets