🌐 Trasowanie pakietów sieciowych — Dijkstra OSPF i wybór trasy BGP

Algorytm Dijkstry utrzymuje zestaw tymczasowych odległości od źródła, zainicjalizowanych na nieskończoność z wyjątkiem samego źródła (zero), i wielokrotnie wyciąga nieodwiedzony węzeł o najmniejszej tymczasowej odległości z kolejki priorytetowej. 'Rozluźnia' każdą z krawędzi tego węzła — jeśli przejście przez nią daje krótszą ścieżkę do sąsiada, odległość sąsiada jest aktualizowana. Gdy każdy osiągalny węzeł został odwiedzony, tymczasowe odległości są optymalne, a najkrótszą ścieżkę do dowolnego celu można odczytać, przechodząc wskaźniki poprzedników wstecz.

OSPF (Open Shortest Path First) to protokół bramy wewnętrznej stanu łącza używany wewnątrz pojedynczej sieci administracyjnej. Każdy router rozgłasza ogłoszenia stanu łącza opisujące jego bezpośrednio połączone łącza i ich koszty; gdy wszystkie routery zgadzają się co do tej samej bazy danych stanu łącza, każdy z nich niezależnie uruchamia algorytm Dijkstry zakorzeniony w sobie, by obliczyć najkrótszą ścieżkę do każdego innego routera. Ponieważ każdy router używa tego samego grafu wejściowego i tego samego deterministycznego algorytmu, wszystkie zbiegają do spójnych, wolnych od pętli tras.

BGP (Border Gateway Protocol) to protokół wektora ścieżki działający między systemami autonomicznymi — oddzielnymi sieciami pod różną kontrolą administracyjną, takimi jak różni dostawcy internetu. Router BGP nie oblicza najkrótszych ścieżek na wspólnej topologii; poznaje tylko konkretne ścieżki rozgłaszane przez swoich sąsiadów i wybiera jedną, używając procesu decyzji politycznej (preferencja lokalna, długość ścieżki AS, pochodzenie i inne atrybuty), a nie czystej minimalizacji kosztu. To pozwala dostawcy internetu preferować komercyjnie korzystniejszą, ale dłuższą trasę nad tańszą, czego czysty algorytm najkrótszej ścieżki nie może wyrazić.

Gdy łącze lub router ulega awarii, routery przylegające do niego muszą wykryć awarię, wygenerować nowe ogłoszenia stanu łącza (lub wycofać trasy BGP), rozgłosić tę informację po sieci, a każdy router musi przeliczyć swoje drzewo najkrótszej ścieżki, zanim ruch będzie mógł bezpiecznie korzystać z nowych tras. Ten cykl wykrycia-rozgłoszenia-przeliczenia nie jest natychmiastowy — zbieżność OSPF to zwykle poniżej sekundy do kilku sekund, podczas gdy zbieżność BGP w globalnym internecie może zająć dziesiątki sekund do minut, ponieważ aktualizacje propagują się przeskok po przeskoku między systemami autonomicznymi. Minimalizowanie tej luki to prawdziwy, ciągły obszar badań inżynierii sieciowej.

Pakiety już zaangażowane na uszkodzonym łączu są po prostu odrzucane — protokoły trasowania nie mają sposobu na odwołanie pakietu w połowie lotu. Nowe pakiety wchodzące do sieci podczas okna zbieżności mogą wciąż być przekazywane wzdłuż nieaktualnych tras, dopóki zaktualizowane drzewo najkrótszej ścieżki się nie rozprzestrzeni, co może powodować tymczasowe pętle lub czarne dziury. Dopiero gdy tablica trasowania każdego routera odzwierciedla nową topologię, ruch niezawodnie podąża za przeliczoną trasą.

Tak. Jeśli dwa sąsiednie routery aktualizują swoje tablice trasowania w różnym czasie, jeden może krótko wskazywać na drugi, wierząc, że nadal ma ważną ścieżkę, tworząc tymczasową pętlę, dopóki oba nie zbiegną do tego samego widoku topologii. Protokoły stanu łącza, takie jak OSPF, są stosunkowo odporne na pętle, ponieważ każdy router oblicza z identycznej mapy, podczas gdy protokoły w stylu wektora odległości są bardziej podatne na przejściowe pętle — kluczowy powód, dla którego projekt stanu łącza zdominował duże sieci.

Koszt (lub metryka) łącza to liczba reprezentująca, jak 'drogie' jest jego użycie — OSPF konwencjonalnie wyprowadza ją z odwrotności przepustowości, podczas gdy inżynierowie mogą też ważyć ją opóźnieniem, niezawodnością lub kosztem tranzytu pieniężnego. Dijkstrze nie zależy na tym, co reprezentuje liczba, tylko na tym, że jest addytywna i nieujemna; zmiana kosztu łącza zmienia, które ścieżki są najtańsze, bez dotykania fizycznej topologii, co jest dokładnie tym, jak operatorzy sieci kierują ruch w produkcji.

Żaden pojedynczy system autonomiczny nie widzi całej topologii internetu, a żaden operator nie chce, by obca sieć jednostronnie decydowała o jego wewnętrznych trasach. Protokoły wewnętrzne, takie jak OSPF, optymalizują trasowanie wewnątrz sieci, którą operator w pełni kontroluje i której ufa, używając precyzyjnych metryk kosztu. Protokoły zewnętrzne, takie jak BGP, sklejają dziesiątki tysięcy niezależnych sieci razem, używając polityki zamiast zaufania, ponieważ operatorzy AS muszą egzekwować relacje biznesowe i nie mogą ujawniać swojej wewnętrznej topologii globalnym obliczeniom najkrótszej ścieżki.

Tak — OSPF i jego kuzyn IS-IS oba nadal uruchamiają Dijkstrę (lub blisko powiązany algorytm SPF) wewnętrznie i pozostają standardem trasowania wewnętrznego u dostawców internetu, w centrach danych i sieciach korporacyjnych. Nowoczesne implementacje używają przyrostowego SPF, który przelicza tylko dotkniętą część drzewa najkrótszej ścieżki po niewielkiej zmianie topologii zamiast uruchamiać cały algorytm od nowa, co jest jedną z głównych dźwigni używanych do skrócenia czasu zbieżności w dużych sieciach.