Algorytmy Kierunkowe Internetu

Żaden router nie widzi całej sieci

Każdy router w Internecie musi zdecydować, dla każdego możliwego celu, do którego sągara przekazać pakiet – i to robi bez centralnego organu, który by mu podawał odpowiedź. Dwa fundamentalnie różne strategie rozwiązują ten problem: routing wektorowy odległości, w którym routery komunikują się jedynie z najbliżsymi sąsiadami, informując, że "moj aktualny zasięg do każdego celu wynosi…", oraz routing stanów połączeń, w którym każdy router ogłasza swoje bezpośrednie połączenia wszystkim innym routerom, a każdy router buduje kompletną mapę i oblicza trasy na jej podstawie.

Wektor odległości: routing oparty na plotkach

Router wektora odległości utrzymuje jeden numer dla każdego celu – jego aktualny najlepszy znany koszt – i okresowo informuje każdego sąsięda o tym całym rozdziale. Zasada aktualizacji to ciągłe, rozproszone relaksacje Bellmana-Ford:

dla każdego sąsięda n i każdej destynacji d: kandydat = koszt(ja, n) + n.odległość_do(d) jeśli kandydat < moja.odległość_do(d): moja.odległość_do(d) = kandydat moja.następny_hop(d) = n RIP (Routing Information Protocol) jest klasycznym przykładem: metryka to po prostu liczba skoków, a 16 skoków jest zdefiniowanych jako niedostępne, co ogranicza maksymalną wielkość sieci RIP. Słabym punktem protokołu jest problem nieskończonego licznika: jeśli router traci trasę do celu, sąsiad, który nadal ma stary szlak do niego, może ogłosić ten szlak z powrotem, a dwa routery zwiększają odległość między nimi jeden wymianą po drugiej zamiast natychmiast zauważyć, że cel jest nieobecny. Rozwiązania takie jak split horizon (nigdy nie reklamuj trasy, którą nauczyłeś się od sąsiada) i poison reverse (reklamuj ją z powrotem jako nieskończoność) zmniejszają problem, ale nie eliminują go całkowicie.

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

Stan linku: routowanie z pełną mapą

Router stanu linku działa w przeciwieństwie: zamiast udostępniać odległości, rozsyła mażego pakiet – ogłoszenie stanu linku (LSA) – opisujące jedynie jego bezpośrednie połączenia i ich koszty, do wszystkich innych routerów w obszarze. Po otrzymaniu każdego LSA przez każdy router, każdy z nich niezależnie posiada identyczną wizję całej topologii i uruchamia algorytm najkrótszej ścieżki Dijkstry na tej wizji, o korzeniu w sobie, aby obliczyć swoje następne hopy. OSPF i IS-IS, dwa protokoły stanu linku, które faktycznie obsługują większość sieci wewnętrznych Internetu, działają dokładnie w ten sposób; OSPF dodatkowo dzieli dużą sieć na obszary, tak że router musi posiadać jedynie pełną mapę swojego obszaru, ograniczając tym samym rozmiar obliczeń Dijkstry i rozsył LSA.

Przecięcie połączenia: konwergencja w porównaniu

Różnica między nimi jest najbardziej widoczna, gdy link ulega awarii. Router stanowy przylegający do przerwy natychmiast rozpyla nową LSA (Link-State Advertisement) oznaczającą "ten link jest zniszczony", a pozostałe routery otrzymują ją w ciągu kilku skoków opóźnienia propagacji, a następnie każdy ponownie oblicza Dijkstrę z poprawioną mapą – konwergencja jest szybka i, o ile wypływ tej informacji nie zostanie utracony, nie powoduje pętli. Sieć wektorowa dystansów musi pozwolić na rozegranie mechanizmu dobiegu do nieskończoności lub polegać na wyzwolonych aktualizacjach i odwrotnej zatruciu, aby je skrócić; nawet z tymi zabezpieczeniami konwergencja sieci wektorowej dystansu po awarii jest generalnie wolniejsza i może transitorowo tworzyć pętle routingu, których unika sieć stanowa, obliczając trasy na podstawie współdzielonej prawdy podstawowej.

Co w rzeczywistości steruje Internetem

Wewnątrz pojedynczej sieci (autonomicznego systemu) OSPF lub IS-IS – oba oparte na linku stanowym – to niemal uniwersalny wybór dzisiaj; RIP przetrwa głównie w niewielkich, historycznych implementacjach. Między autonomic systemami protokołem jest BGP, który nie jest czystym wektorem odległości ani linku stanowym, ale wektorem ścieżki: obok metryki reklamuje pełną sekwencję autonomicznych systemów, przez które przechodzi trasa, więc router może natychmiast odrzucić dowolną trasę, której ścieżka już zawiera się w niej samą, omijając błąd liczenia do nieskończoności poprzez uczynienie pętli bezpośrednio widoczną zamiast czegoś do wnioskowania z powoli zmieniającej się liczby.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Internet Routing i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.