Маршрутизація Пакетів Мережі: Дейкстра, OSPF та BGP в Мініатюрі

Перший шлях: алгоритм Дейкстри

Кожен маршрутизатор у Інтернеті в основному розв’язує задачу пошуку найкоротшого шляху з одного джерела – це задача про найкоротший шлях з одного вузла до всіх інших у графі: вузли – маршрутизатори, ребра – зв’язки, а вага ребра – вартість (часто пов’язана з пропускною спроможністю або налаштованим показником). Алгоритм Дейкстри, опублікований Едсгером Дікстройом у 1959 році, знаходить найдешевші шляхи від одного маршрутизатора до всіх інших маршрутизаторів у мережі з невід’ємними вагами, і це робить без необхідності переглядати шляхи, які вже доведено гірші за ті, що були знайдені.

dist[джерело] = 0; dist[для всіх інших] = нескінченність відвідано = {} поки залишаються невпорядковані вузли: u = невпорядкований вузол з найменшим dist[u] позначити u як відвіданий для кожного сусіда v у u: якщо dist[u] + вартість(u,v) < dist[v]: dist[v] = dist[u] + вартість(u,v) predecessor[v] = u Крок жадібності – завжди розширювати найближчий невпорядкований вузол наступним чином – доведено правильно лише для невід’ємних ваг: коли вузол встановлено, жодне подальше розслаблення через невпорядкований (необхідно далі розташований) вузол не може ніколи дати коротший шлях до нього. Реалізовано з бінарного або Фібоначчі куща для черги пріоритетів, він працює за часом O((V+E) log V), достатньо швидко для перерахунку маршрутів у мережах з тисячами маршрутизаторів при кожному зміні топології.

dist[source] = 0;  dist[all others] = infinity
visited = {}
while unvisited nodes remain:
    u = unvisited node with the smallest dist[u]
    mark u visited
    for each neighbour v of u:
        if dist[u] + weight(u,v) < dist[v]:
            dist[v] = dist[u] + weight(u,v)
            prev[v] = u                       // for path reconstruction

OSPF: Dijkstra всередині єдиної мережі

OSPF (Open Shortest Path First) – це алгоритм Дейкстри, що працює на практиці, всередині єдиної автономної системи (компанії, університету чи власної мережі ISP). Кожен маршрутизатор заливає інформацією інших маршрутизатори свої локальні стани зв’язку — які сусіди він має та за яку вартість — щоб кожен маршрутизатор отримав ідентичну карту всієї топології, а потім незалежно виконує Дейкстру на цій карті для обчислення власного таблиці маршрутизації. Вартість зазвичай обернена до пропускної здатності, тому OSPF природним чином віддає перевагу з’єднанню 10 Гбіт/с перед з’єднанням 100 Мбіт/с, навіть якщо шлях 100 Мбіт/с має менше вузлів.

BGP: маршрутизація між мережами, а не найдешевша траса

Між автономними системами — між провайдерами інтернет-послуг, сутність маршрутизації інтернету замінюється BGP (Border Gateway Protocol), оскільки провайдери не хочуть технічно найкоротшу трасу, вони хочуть трасу, яка поважає бізнес-відносини: трафік клієнта-транзитера надається перевазі над трафіком безкоштовного партнерства, а останнє — плата за транзит у конкурентів. BGP є вектором шляхів, а не стан-з'єднанням: кожен маршрутизатор оголошує повний шлях AS і кожний інший маршрутизатор застосовує локальну політику для вибору серед конкуруючих оголошень, а не спільну функцію витрат.

Що відбувається, коли виходить з ладу зв'язок

Якщо вийти з ладу зв’язок всередині домену OSPF, то всі маршрутизатори перегенерують новий стан-звіт, запускають Dijkstra знову та конвергують на новому дереві найкоротших шляхів – зазвичай менше ніж за секунду на сучасному обладнанні, хоч і не миттєво, що є вікном для появи тимчасових циклів маршрутизації. Конвергенція BGP після відмовості в рази повільніша та може тривати хвилини, оскільки AS-path withdrawals поширюються між усіма маршрутизаторами через інтернет, а маршрутизатори застосовують гамування, щоб запобігти розповсюдженню хвилинних коливань шляхів у глобальну нестабільність.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Network Packet Routing і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.