Маршрутизація Інтернету: Як пакети знаходять свій шлях

Жоден маршрутизатор не бачить всю мережу

Кожен маршрутизатор в Інтернеті повинен вирішувати, для кожної можливої кінцевої точки, якому сусідові передати пакет – і це потрібно робити без жодної центральної влади, яка б давала відповідь. Два фундаментально різні стратегії вирішують цю проблему: маршрутизація на основі відстаней, де маршрузатори повідомляють лише своїм найближчим сусідам «ось моя поточна відстань до кожного призначення», та маршрутизація стану зв’язків, де кожен маршрузатор оголошує свої прямі з’єднання з усіма, і кожен маршрузатор будує повну карту та обчислює свої маршрути на основі неї.

Відданий вектор: маршрутизація за чутками

Відданий вектор маршрутизатор підтримує лише одне число для кожного пункту призначення — поточну найкраще відому вартість, і періодично повідомляє кожному сусідові про весь цей таблицю. Правило оновлення є розслабленням Беллмана-Форда, яке постійно та розподілено по мережі:

для кожного сусіда n і кожного пункту призначення d: кандидат = вартість(я, n) + відстань_n_до_d якщо кандидат < моя_відстань_до_d: моя_відстань_до_d = кандидат моя_найближча_точка_до_d = n RIP (Routing Information Protocol) є класичним прикладом: метрика — це просто кількість стрибків, і 16 стрибків визначається як недосяжною, що обмежує максимальний розмір мережі RIP. Критичною слабкістю протоколу є проблема нескінченного підрахунку: якщо маршрутизатор втрачає шлях до пункту призначення, сусід, який все ще має застарілий маршрут до нього, може оголосити цей маршрут знову, і обидва маршрутизатори збільшують відстань між ними один обмін за раз замість того, щоб негайно зрозуміти, що пункт призначення відсутній. Заходи пом’якшення, такі як роздільне горизонт (ніколи не рекламуйте маршрут назад до сусіда, з якого ви його дізналися) та зворотний перевертання (рекламуйте його назад, але як нескінченність), зменшують проблему, але не усувають усі випадки.

for each neighbour n and each destination d:
  candidate = cost(self, n) + n.distance_to(d)
  if candidate < my.distance_to(d):
    my.distance_to(d) = candidate
    my.next_hop(d)    = n

Link-state: маршрутизація з повною картою

Роутер на основі link-state робить протилежне: замість обміну відстанями, він розсилає невеликий повідомлення – оголошення про стан зв’язку (LSA), яке описує лише його власні прямі з’єднання та їх вартість, до кожного іншого роутера в районі. Після того, як кожен роутер отримав кожне LSA, кожен незалежно має ідентичну картину всієї топології, і кожен запускає алгоритм найкоротшого шляху Дейкстри на основі цієї карти, з коренем у собі, щоб обчислити свої наступні кроки.

OSPF та IS-IS, два протоколи link-state, які фактично працюють у більшості внутрішніх мереж Інтернету, працюють саме так; OSPF ще більше ділить велику мережу на області, щоб роутер міг використовувати лише повну карту своєї області, обмежуючи таким чином розмір обчислення Дейкстри та розповсюдження LSA.

Розрізати зв’язок: збіжність порівняно

Відмінність між двома проявляється найчіткіше, коли відірвують зв’язок. Маршрутизатор на основі стану зв’язку, розташований поруч із розривом, негайно поширює свіжий LSA (Link State Advertisement), який стверджує "цей зв’язок не працює", інші маршрутизатори отримують його протягом кількох пропусків затримки поширення, і кожен перераховує Dijkstra з виправленою картою — збіжність відбувається швидко та, якщо не втрачено саму поширювальну хвилю, не призводить до циклів маршрутизації. Натомість мережа на основі векторів відстаней повинна дозволити механізму «нескінченності відстані» працювати або покладатися на тригеровані оновлення та зворотний загін для скорочення цього, навіть із цими запобіжними засобами збіжність векторів відстаней після відмови зазвичай повільніша і може тимчасово створювати цикли маршрутизації, яких уникає мережа на основі стану зв’язку, оскільки вона обчислює маршрути з спільного джерела істини.

Що насправді працює в Інтернеті

Всередині однієї мережі (автономної системи) OSPF або IS-IS – обидва протоколи стану зв’язку – є майже універсальним вибором сьогодні; RIP виживає переважно у невеликих устарілих розгортаннях. Між автономними системами, протокол – BGP, який не є чистим вектором відстані або протоколом стану зв’язку, але вектором шляху: поряд з метрикою він рекламує весь ланцюжок автономних систем, які пройшов маршрут, тому маршрутизатор може негайно відхилити будь-який маршрут, шлях якого вже містить сам себе, уникаючи помилки «нескінченний цикл» шляхом того, що робить цикли явно видимими, а не тим, що потрібно виводити з повільно змінюваного числа.

Frequently asked questions

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

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