Wprowadzenie: Sieciowy GPS

Wyobraź sobie internet jako gigantyczne, rozległe miasto z miliardami adresów. Kiedy wysyłasz e-mail lub odwiedzasz stronę internetową, w zasadzie wysyłasz list (pakiet danych) ze swojego adresu na inny. Jak ten list odnajduje drogę przez labirynt skrzyżowań, autostrad i bocznych uliczek, aby dotrzeć do celu na drugim końcu świata w milisekundy? Odpowiedzią są specjalizowane komputery, które działają jak miejscy listonosze i kontrolerzy ruchu: routery.

Router znajduje się na styku dwóch lub więcej sieci i podejmuje kluczową decyzję, dokąd wysłać każdy przechodzący pakiet. Ale aby podjąć tę decyzję, potrzebuje mapy. Ta "mapa" nazywana jest tablicą routingu i zawiera listę wskazówek: "Aby dotrzeć do sieci X, wyślij pakiet do następnego routera Y."

Ale skąd bierze się ta mapa? Sieć nie jest statyczna; łącza mogą ulec awarii, mogą być dodawane nowe routery, a warunki ruchu mogą się zmieniać. Routery nie mogą polegać na wydrukowanej mapie. Zamiast tego muszą nieustannie uczyć się o układzie sieci i aktualizować własne mapy. Metoda, której używają do nauki i budowy tych tablic, jest zdefiniowana przez algorytm routingu. Ta strona bada fundamentalne "filozofie" stojące za tym, jak routery budują swój obraz świata.

Cel Algorytmu Routingu: Znalezienie „Najlepszej” Ścieżki

W swej istocie, algorytm routingu to zbiór zasad i procedur używanych przez routery do poznawania topologii sieci, dzielenia się tą informacją z innymi routerami i obliczania najlepszej ścieżki (lub ścieżek) do wszystkich osiągalnych miejsc docelowych. Ostatecznym celem jest wypełnienie tablicy routingu wysokiej jakości trasami bez pętli.

Co Czyni Ścieżkę „Najlepszą”? Metryka

Pojęcie „najlepszej” ścieżki nie jest uniwersalne. Jest ono określane przez metrykę. Metryka to wartość liczbowa przypisana do ścieżki, którą algorytm stara się zminimalizować. Jest to „koszt” korzystania z danej trasy. Popularne metryki to:

• Liczba przeskoków: Liczba routerów, które pakiet musi przekroczyć. Prosta, ale nie uwzględnia prędkości łączy.
• Przepustowość: Zdolność łączy do przenoszenia danych. Wyższa przepustowość jest lepsza, więc metryka jest często obliczana jako $1/\text{przepustowość}$.
• Opóźnienie (Latencja): Czas potrzebny na pokonanie łączy przez pakiet.
• Obciążenie: Jak bardzo zajęte są łącza.
• Koszt: Wartość zdefiniowana administracyjnie, często oparta na kombinacji czynników lub kosztach pieniężnych.

Wektor Odległości: Routing przez Plotki

Pierwsza duża rodzina algorytmów routingu to Wektor Odległości. Najlepszą analogią jest „routing przez plotki” lub podążanie za drogowskazami. Każdy router na początku wie bardzo niewiele: zna tylko swoją tożsamość i wie, jak dotrzeć do swoich bezpośrednich, podłączonych sąsiadów (odległość do nich to jeden przeskok lub koszt łącza). Nie ma mapy całej sieci.

Jak To Działa: Dzielenie się Wiedzą

Podstawowa zasada algorytmu Wektora Odległości jest prosta i zdecentralizowana, oparta na algorytmie $\text{Bellmana-Forda}$:

1. Każdy router utrzymuje tablicę routingu, która zawiera listę wszystkich znanych miejsc docelowych, odległość (metrykę) do tego miejsca oraz następny router (next-hop) na ścieżce.
2. Regularnie (np. co 30 sekund) każdy router rozgłasza swoją całą tablicę routingu do swoich bezpośrednio podłączonych sąsiadów.
3. Gdy router otrzymuje tablicę od sąsiada, porównuje otrzymane informacje z własnymi. Dla każdego miejsca docelowego w tablicy sąsiada oblicza nową potencjalną odległość: $d_{\text{nowa}} = d_{\text{sąsiad}} + c_{\text{łącze}}$, gdzie $d_{\text{sąsiad}}$ to odległość sąsiada do celu, a $c_{\text{łącze}}$ to koszt łącza do tego sąsiada.
4. Jeśli ta nowo obliczona odległość jest lepsza (niższa) niż ta, którą ma obecnie w swojej tablicy, aktualizuje swój wpis, ustawiając nową, niższą odległość i wpisując sąsiada, od którego otrzymał aktualizację, jako następny przeskok.

Dzięki temu procesowi dzielenia się plotkami z sąsiadami, wiedza o topologii sieci stopniowo rozprzestrzenia się od routera do routera, aż wszystkie routery poznają najlepsze ścieżki do wszystkich miejsc docelowych. Ten ostateczny, stabilny stan nazywany jest konwergencją.

Przykład: Problem „Liczenia do Nieskończoności”

Podejście oparte na „plotkach” ma słynną i znaczącą wadę. Działa dobrze, gdy dodawane są łącza lub poprawiają się metryki, ale reaguje bardzo wolno i problematycznie na awarie łącz. Jest to znane jako problem Liczenia do Nieskończoności.

Rozważmy prostą sieć: Router A jest podłączony do Routera B, który jest podłączony do Sieci X. Metryką jest liczba przeskoków.

1. Stan Stabilny: B ogłasza, że może dotrzeć do X z metryką $1$ (bezpośrednio podłączone). A otrzymuje tę informację, dodaje własny koszt $1$, aby dotrzeć do B, i instaluje trasę do X przez B z metryką $2$.
2. Awaria Łącza: Łącze między B a X ulega awarii. B nie ma już trasy do X.
3. Rozprzestrzenia się Zła Plotka: Zanim B poinformuje A o awarii, okresowa aktualizacja od A dociera do B. Tablica A mówi: "Mogę dotrzeć do Sieci X w $2$ krokach".
4. Pętla Routingu: B słyszy tę plotkę od A. B myśli: "Wow, A ma ścieżkę do X! Mogę dotrzeć do A w $1$ kroku, więc moja nowa ścieżka do X prowadzi przez A z kosztem $2+1=3$". B aktualizuje swoją tablicę, aby wskazywała na A.
5. Rozpoczyna się Liczenie: W następnej aktualizacji A informuje B o swojej trasie (koszt $2$). B aktualizuje swój koszt na $3$. Następnie A słyszy od B (koszt $3$) i aktualizuje swój koszt na $4$. Potem B słyszy od A (koszt $4$) i aktualizuje na $5$. Pakiety przeznaczone dla X są teraz uwięzione w pętli, odbijając się między A i B, podczas gdy metryka powoli rośnie do nieskończoności.

Aby temu przeciwdziałać, opracowano mechanizmy takie jak Dzielony Horyzont (nieogłaszanie trasy z powrotem przez interfejs, z którego została ona poznana), Zatruwanie Trasy i Liczniki Czasu Wstrzymania. Klasycznym protokołem wykorzystującym ten algorytm jest $\text{RIP}$ ($\text{Routing Information Protocol}$).

Stan Łącza: Każdy Dostaje Pełną Mapę

Druga główna rodzina algorytmów, Stan Łącza, przyjmuje fundamentalnie inne podejście. Zamiast polegać na informacjach z drugiej ręki od sąsiadów, celem jest, aby każdy router posiadał kompletną i identyczną mapę całej topologii sieci. Każdy router działa wtedy jak własny GPS, niezależnie obliczając najlepszą trasę ze swojej perspektywy do każdego możliwego celu.

Jak To Działa: Budowanie Mapy i Znajdowanie Najkrótszej Ścieżki

Proces Stanu Łącza można podzielić na kilka kluczowych kroków, opartych na algorytmie $\text{Dijkstry}$ (Najpierw Najkrótsza Ścieżka - $\text{SPF}$):

1. Odkryj Sąsiadów i Koszty Łącz: Każdy router najpierw odkrywa swoich bezpośrednio podłączonych sąsiadów i określa koszt (metrykę) łącza do każdego z nich.
2. Utwórz Pakiet Stanu Łącza (LSP): Każdy router pakuje te informacje: swój identyfikator, listę sąsiadów i koszt do każdego z nich, w małą wiadomość zwaną Pakietem Stanu Łącza (LSP).
3. Rozpowszechnij LSP do Wszystkich Routerów: Router wysyła swoje LSP do wszystkich swoich sąsiadów. Każdy sąsiad, który otrzymuje LSP, zapisuje kopię, aktualizuje własną mapę i przekazuje LSP do wszystkich swoich sąsiadów (z wyjątkiem tego, od którego je otrzymał). Ten proces, znany jako zalewanie (flooding), zapewnia, że każdy router w obszarze szybko otrzymuje kopię LSP każdego innego routera.
4. Zbuduj Pełną Bazę Topologii: Zbierając wszystkie LSP, każdy router buduje identyczną bazę danych, która stanowi kompletną mapę sieci.
5. Uruchom Algorytm Najpierw Najkrótsza Ścieżka ($\text{SPF}$): Mając kompletną mapę, każdy router uruchamia algorytm $\text{SPF}$ ($\text{Dijkstry}$), umieszczając siebie w korzeniu drzewa i obliczając najkrótszą ścieżkę do każdego innego węzła i sieci. Wynikiem jest kompletne drzewo najlepszych tras.
6. Wypełnij Tablicę Routingu: Z obliczonego drzewa najkrótszych ścieżek router wyodrębnia najlepsze trasy i instaluje je w swojej tablicy routingu.

Gdy nastąpi zmiana w sieci (np. awaria łącza), tylko routery bezpośrednio dotknięte zmianą tworzą i rozsyłają nowe LSP. Wszystkie pozostałe routery otrzymują aktualizację, modyfikują swoje mapy i ponownie uruchamiają algorytm $\text{SPF}$. Powoduje to znacznie szybszą konwergencję niż w przypadku Wektora Odległości. Wybitnymi protokołami używającymi tego algorytmu są $\text{OSPF}$ ($\text{Open Shortest Path First}$) i $\text{IS-IS}$.

Wektor Ścieżki: Routing oparty na Polityce

Trzecia główna rodzina algorytmów, Wektor Ścieżki, jest przeznaczona dla zupełnie innej skali: całego globalnego internetu. Przy routingu między ogromnymi, niezależnie zarządzanymi sieciami zwanymi Systemami Autonomicznymi (AS), „najlepsza” ścieżka jest często definiowana nie przez najniższą metrykę, ale przez relacje biznesowe, kwestie bezpieczeństwa i polityki.

Jak To Działa: Ogłaszanie Pełnej Ścieżki

Algorytm Wektora Ścieżki to modyfikacja Wektora Odległości z kluczowym ulepszeniem:

• Zamiast ogłaszać tylko cel i metrykę odległości, routery ogłaszają sieć docelową wraz z pełną ścieżką numerów AS, przez które trasa przebiega.
• Na przykład router w AS 1 może ogłosić swojemu sąsiadowi w AS 2: „Mogę dotrzeć do Sieci Z przez ścieżkę (AS 1).”
• AS 2 następnie ogłasza swojemu sąsiadowi w AS 3: „Mogę dotrzeć do Sieci Z przez ścieżkę (AS 2, AS 1).”

Wbudowane Zapobieganie Pętlom i Kontrola Polityki

Ten prosty mechanizm zapewnia dwie potężne funkcje:

1. Solidne Zapobieganie Pętlom: Wykrywanie pętli jest trywialne. Jeśli router otrzymuje aktualizację trasy i widzi w liście ścieżki numer własnego AS, wie, że trasa jest pętlą i natychmiast ją odrzuca. To całkowicie eliminuje problem „liczenia do nieskończoności”.
2. Routing oparty na Polityce: Ponieważ znana jest pełna ścieżka, administratorzy mogą stosować zasady (polityki) w celu wpływania na decyzje routingowe w oparciu o logikę biznesową, a nie tylko prostą metrykę. Na przykład:
   • „Nie akceptuj tras przechodzących przez AS mojego konkurenta.”
   • „Preferuj trasy poznane od mojego głównego dostawcy tranzytowego nad zapasowym.”
   • „Nie ogłaszaj moich wewnętrznych sieci klienckich innym dostawcom tranzytowym.”

Podejmowanie decyzji opiera się na złożonym zestawie atrybutów ścieżki, a nie na pojedynczej wartości kosztu. Jedynym protokołem, który używa tego algorytmu, jest $\text{BGP}$ ($\text{Border Gateway Protocol}$), protokół routingu Internetu.