UK 
EnglishDefault
Polski🌐 Маршрутизація мережевих пакетів
Маршрутизатори виконують справжню маршрутизацію Дейкстри для пошуку найкоротшого шляху до призначення. Змінюйте вартість каналів, вимикайте маршрутизатори чи канали й спостерігайте, як вибір шляху у стилі OSPF та BGP наживо перенаправляє пакети.
Про цю симуляцію
Інтернет — це граф маршрутизаторів, з'єднаних каналами, і кожен пакет, що проходить через нього, потребує рішення на кожному переході: який сусід наблизить його до пункту призначення? Внутрішні протоколи шлюзу, як-от OSPF, розв'язують це маршрутизацією за станом каналів: кожен маршрутизатор розсилає вартість своїх локальних каналів усій області, тож усі маршрутизатори отримують ідентичну карту топології, і кожен незалежно виконує алгоритм Дейкстри від себе, щоб побудувати дерево найкоротших шляхів до всіх точок. Зовнішні протоколи шлюзу, як-от BGP, натомість використовують маршрутизацію за вектором шляху між автономними системами: маршрутизатор не бачить весь граф, а лише шляхи, які анонсують його сусіди, і обирає між ними за політикою — атрибутами на кшталт довжини AS-шляху чи локального пріоритету, — а не сумуванням суто числової метрики.
Ця симуляція виконує справжній алгоритм Дейкстри на черзі з пріоритетами над живим, редагованим графом із дев'яти маршрутизаторів і вісімнадцяти зважених каналів — тут немає жодного заздалегідь намальованого шляху. Оберіть джерело й призначення, змініть вартість каналів і перемикайтеся між вибором у стилі OSPF (найдешевша сумарна вартість) та BGP (найменше переходів, вартість — як критерій розв'язання нічиєї), щоб побачити, як ці дві філософії розходяться на одній і тій самій топології. Клацніть на маршрутизатор чи канал, щоб вивести його з ладу: алгоритм перезапускається з нуля над топологією, що залишилася, а змодельована затримка збіжності відображає реальний час, який мережа витрачає на розсилку оголошень про стан каналів і перерахунок дерев найкоротших шляхів, перш ніж трафік знову зможе текти.
Поширені запитання
Як алгоритм Дейкстри насправді знаходить найкоротший шлях?
Алгоритм Дейкстри підтримує набір попередніх відстаней від джерела, ініціалізованих нескінченністю, окрім самого джерела (нуль), і повторно вилучає ще не відвідану вершину з найменшою попередньою відстанню з черги з пріоритетами. Він «релаксує» кожне ребро цієї вершини — якщо прохід через неї дає коротший шлях до сусіда, відстань сусіда оновлюється. Коли відвідано всі досяжні вершини, попередні відстані стають оптимальними, і найкоротший шлях до будь-якого призначення можна відновити, проходячи покажчики попередників у зворотному напрямку.
Що таке OSPF і як він використовує Дейкстру?
OSPF (Open Shortest Path First) — це внутрішній протокол шлюзу за станом каналів, що використовується всередині однієї адміністративної мережі. Кожен маршрутизатор розсилає оголошення про стан каналів, що описують його прямі з'єднання та їхню вартість; коли всі маршрутизатори погоджуються на єдиній базі даних стану каналів, кожен незалежно виконує алгоритм Дейкстри, вкорінений у собі, щоб обчислити найкоротший шлях до кожного іншого маршрутизатора. Оскільки всі маршрутизатори використовують однаковий вхідний граф і той самий детермінований алгоритм, вони всі сходяться до узгоджених, безпетльових маршрутів.
Чим BGP принципово відрізняється від OSPF?
BGP (Border Gateway Protocol) — це протокол за вектором шляху, що працює між автономними системами — окремими мережами під різним адміністративним контролем, наприклад різними інтернет-провайдерами. Маршрутизатор BGP не обчислює найкоротші шляхи над спільною топологією; він лише дізнається конкретні шляхи, які анонсують його сусіди, і обирає один за допомогою процесу прийняття рішень на основі політики (локальний пріоритет, довжина AS-шляху, походження та інші атрибути), а не суто мінімізації вартості. Це дозволяє провайдеру віддавати перевагу комерційно вигіднішому, але довшому маршруту над дешевшим — те, що чистий алгоритм найкоротшого шляху виразити не може.
Чому збіжність маршрутизації після збою займає час?
Коли канал чи маршрутизатор виходить з ладу, суміжні з ним маршрутизатори мають виявити збій, згенерувати нові оголошення про стан каналів (або відкликати маршрути BGP), розповсюдити цю інформацію по мережі, і кожен маршрутизатор має перерахувати своє дерево найкоротших шляхів, перш ніж трафік безпечно зможе використовувати нові маршрути. Цей цикл «виявлення–розсилка–перерахунок» не миттєвий — збіжність OSPF зазвичай триває від часток секунди до кількох секунд, тоді як збіжність BGP у глобальному інтернеті може займати від десятків секунд до хвилин, бо оновлення поширюються від переходу до переходу між автономними системами. Мінімізація цього розриву — реальна, актуальна область досліджень у мережевій інженерії.
Що відбувається з пакетами, що вже в польоті, коли канал виходить з ладу?
Пакети, вже спрямовані на несправний канал, просто відкидаються — протоколи маршрутизації не мають способу відкликати пакет у польоті. Нові пакети, що входять у мережу під час вікна збіжності, все ще можуть пересилатися застарілими маршрутами, доки не поширяться оновлені дерева найкоротших шляхів, що може спричинити тимчасові петлі чи «чорні діри». Лише коли таблиця маршрутизації кожного маршрутизатора відображатиме нову топологію, трафік надійно піде за перерахованим маршрутом.
Чи може виникнути петля маршрутизації під час збіжності мережі?
Так. Якщо два суміжні маршрутизатори оновлюють свої таблиці маршрутизації в різний час, один із них може ненадовго вказувати на інший, вважаючи, що той усе ще має чинний шлях, створюючи тимчасову петлю, доки обидва не зійдуться до однакового бачення топології. Протоколи за станом каналів, як-от OSPF, порівняно стійкіші до петель, бо кожен маршрутизатор обчислює на основі ідентичної карти, тоді як протоколи за вектором відстані більш схильні до тимчасових петель — це одна з ключових причин, чому дизайн за станом каналів став домінувати у великих мережах.
Що таке вартість каналу або метрика фізично?
Вартість (або метрика) каналу — це число, що представляє, наскільки «дорого» його використовувати — OSPF традиційно виводить її з оберненої пропускної здатності, хоча інженери можуть також зважувати її за затримкою, надійністю чи грошовою вартістю транзиту. Дейкстрі байдуже, що представляє це число, аби воно було адитивним і невід'ємним; зміна вартості каналу змінює, які шляхи найдешевші, не торкаючись фізичної топології — саме так оператори мереж керують трафіком у продакшені.
Чому реальні мережі використовують і внутрішній, і зовнішній протокол?
Жодна окрема автономна система не бачить топологію всього інтернету, і жоден оператор не хоче, щоб чужа мережа одноосібно вирішувала його внутрішні маршрути. Внутрішні протоколи, як-от OSPF, оптимізують маршрутизацію всередині мережі, яку оператор повністю контролює й якій довіряє, використовуючи точні метрики вартості. Зовнішні протоколи, як-от BGP, з'єднують десятки тисяч незалежних мереж за допомогою політики, а не довіри, бо операторам AS потрібно дотримуватися бізнес-відносин і вони не можуть розкривати свою внутрішню топологію для глобального обчислення найкоротшого шляху.
Чи все ще використовують алгоритм Дейкстри в масштабі інтернету сьогодні?
Так — OSPF і його родич IS-IS обидва досі виконують Дейкстру (або тісно пов'язаний алгоритм SPF) внутрішньо, і вони залишаються стандартом внутрішньої маршрутизації в інтернет-провайдерів, дата-центрах і корпоративних мережах. Сучасні реалізації використовують інкрементний SPF, який перераховує лише уражену частину дерева найкоротших шляхів після невеликої зміни топології замість повторного запуску всього алгоритму — це один з головних важелів скорочення часу збіжності у великих мережах.