Algorytmy Routingu

Wprowadzenie: algorytmy routingu

Internet łączy wiele sieci i prefiksów adresowych. Gdy wysyłasz wiadomość lub żądasz strony, pakiet przechodzi przez routery, które wybierają kolejny etap przekazywania na podstawie adresu docelowego. Każdy router wykonuje lokalną decyzję i przekazuje pakiet do następnego przeskoku. Routery wykonują te decyzje w warstwie sieciowej.

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ą routingui zawiera listę wskazówek: "Aby dotrzeć do sieci X, wyślij pakiet do następnego routera Y."

Topologia sieci może się zmieniać z powodu awarii łączy, dodania routera lub zmiany konfiguracji. Routery pobierają informacje o osiągalności i aktualizują tablice routingu zgodnie z regułami algorytmu routingu. Algorytm może działać rozproszony, więc każdy router wykonuje obliczenia na podstawie lokalnych danych oraz komunikatów protokołu. W dalszych sekcjach opisano trzy rodziny takich algorytmów.

Cel algorytmu routingu: wybór trasy

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.

Kryteria wyboru trasy: metryka

Ocena trasy zależy od protokołu i jego konfiguracji. Nie każdy protokół interpretuje większą wartość jako gorszą, więc definicję kierunku porównania określa dokumentacja danego protokołu. W protokołach, które minimalizują metrykę, o wyborze decyduje metrykę. Metryka to wartość liczbowa przypisana do ścieżki. W protokołach opartych na minimalizacji opisuje koszt wykorzystania trasy. Przy identycznych wartościach protokół może stosować dodatkowe kryteria wyboru, takie jak identyfikator routera albo kolejność konfiguracji. Przykładowe 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. W uproszczonym modelu wyższa przepustowość może dawać mniejszy składnik kosztu, zapisany jako $1/\text{przepustowość}$. OSPF używa kosztu interfejsu i sumuje go na trasie.
• 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: wymiana metryk

Wektor odległości wymienia między sąsiadami informacje o osiągalnych celach i metrykach. Router zna własne prefiksy oraz sąsiadów, a dodatkowe trasy wyznacza z otrzymywanych wartości. Wpis trasy zawiera zwykle cel, metrykę i następny przeskok, bez kompletnego opisu wszystkich łączy.

Jak działa: wymiana informacji

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. W RIP router wysyła okresowo swoją całą tablicę routingu do bezpośrednio podłączonych sąsiadów, zwykle co 30 sekund. Inne protokoły wektora odległości używają własnych timerów i formatów aktualizacji.
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.

Wymiana informacji z sąsiadami prowadzi do kolejnych aktualizacji tras, wysyłanych okresowo albo po zmianie zgodnie z protokołem. Stabilny stan spójnych informacji routingowych nazywany jest konwergencją.

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

Wektor odległości wolniej reaguje na niektóre awarie łączy niż na poprawę metryki. Zjawisko narastania metryki w pętli nazywa się problemem 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 otrzymuje to ogłoszenie od A i przyjmuje, że A ma ścieżkę do X. Może dotrzeć do A w $1$ kroku, więc 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 mogą krążyć między A i B, a metryka rośnie do wartości uznanej przez protokół za nieskończoność. W RIP domyślna wartość nieskończoności wynosi $16$.

Problem ograniczają mechanizmy takie jak dzielony horyzont (pomijanie trasy w ogłoszeniu wysyłanym przez interfejs, z którego została poznana), zatruwanie trasy i liczniki czasu wstrzymania. W RIP wartość 16 oznacza nieskończoność, więc trasy o liczbie przeskoków od 1 do 15 mogą być używane. Klasycznym protokołem wykorzystującym ten algorytm jest $\text{RIP}$ ($\text{Routing Information Protocol}$).

Stan łącza: baza topologii

Druga główna rodzina, stan łącza, polega na rozpowszechnianiu opisów lokalnych połączeń. Routery w tym samym obszarze utrzymują zgodną bazę topologii i niezależnie obliczają trasy z własnego punktu widzenia. Baza opisuje relacje między routerami, a jej zakres ogranicza liczbę informacji potrzebnych do obliczeń.

Jak działa: baza topologii i najkrótsza ścieżka

Proces stanu łącza obejmuje kilka kroków opartych na algorytmie $\text{Dijkstry}$ i metodzie Najpierw Najkrótsza Ścieżka ($\text{SPF}$):

1. Odkrywanie sąsiadów i kosztów łączy: 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 informacje w obszarze: Router wysyła swój opis stanu łącza do sąsiadów. Otrzymany opis jest zapisywany, a następnie przekazywany dalej zgodnie z regułami protokołu. Ten proces, znany jako zalewanie (flooding), dostarcza routerom w obszarze kopie opisów innych routerów.
4. Zbuduj bazę topologii: Zbierając opisy stanu łącza, każdy router buduje zgodną bazę danych obszaru.
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.

Po zmianie w sieci, na przykład po awarii łącza, router źródłowy aktualizuje opis stanu i rozsyła go zgodnie z protokołem. Pozostałe routery aktualizują bazę i ponownie uruchamiają $\text{SPF}$. Wynikowe drzewo najkrótszych ścieżek jest przekształcane w wpisy przekazywania dla osiągalnych prefiksów. OSPF ($\text{Open Shortest Path First}$) i $\text{IS-IS}$ wykorzystują stan łącza, choć różnią się formatem informacji, typami komunikatów i zakresem zalewania.

Wektor ścieżki: routing między systemami autonomicznymi

Trzecia główna rodzina, wektor ścieżki, służy do wymiany informacji między niezależnie zarządzanymi sieciami zwanymi Systemami Autonomicznymi (AS). W tym modelu wybór trasy może uwzględniać relacje biznesowe, bezpieczeństwo i politykę operatora.

Jak działa: ogłaszanie ścieżki AS

Algorytm wektora ścieżki rozszerza wymianę metryk o listę systemów autonomicznych. Przy przekazywaniu ogłoszenia kolejny AS dopisuje własny numer do atrybutu AS_PATH. Inne atrybuty mogą opisywać źródło, następny przeskok lub preferencję lokalną używaną przy wyborze trasy:

• Routery ogłaszają sieć docelową wraz z pełną ścieżką numerów AS, przez które trasa przebiega, oraz z pozostałymi atrybutami wymaganymi przez protokół.
• 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).”

Zapobieganie pętlom i polityki routingu

Lista ścieżki dostarcza dwóch mechanizmów:

1. Wykrywanie pętli przez AS_PATH: Router skanuje listę ścieżki. Jeżeli znajduje własny numer AS, odrzuca trasę jako potencjalnie zapętloną. BGP wykorzystuje ten mechanizm do zatrzymania ogłoszenia, które wróciło przez własny system autonomiczny.
2. Routing oparty na polityce: Znana lista ścieżki pozwala administratorom wpływać na decyzje routingowe zgodnie z polityką operatora i wymaganiami biznesowymi. 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.”

Decyzje wykorzystują zestaw atrybutów ścieżki oraz polityk lokalnych. Atrybuty mogą wpływać na preferencję trasy, jej rozgłaszanie i akceptację, więc wybór może zależeć od reguł operatora. Współczesnym przykładem protokołu wektora ścieżki jest $\text{BGP}$ ($\text{Border Gateway Protocol}$), używany do routingu między systemami autonomicznymi.