Protokół Najkrótszej Ścieżki (OSPF)

Wprowadzenie: RIP i OSPF jako odmienne modele routingu

Protokół Informacji o Trasach (RIP) wymienia z sąsiadami informacje o znanych sieciach i metrykach. Router buduje obraz topologii z danych otrzymywanych od kolejnych sąsiadów, więc zmiana trasy może propagować się powoli. Metryka RIP opiera się na liczbie przeskoków i nie rozróżnia przepustowości łączy. Dla większych sieci potrzebny jest protokół, który szybciej reaguje na zmiany i uwzględnia pełniejszy opis topologii.

OSPF (Open Shortest Path First) stosuje inny model. Routery w jednym obszarze rozgłaszają stan własnych interfejsów i na tej podstawie utrzymują zgodną bazę danych topologii. Każdy router niezależnie uruchamia algorytm SPF, aby wyznaczyć ścieżki o najmniejszym łącznym koszcie do znanych miejsc docelowych. Zgodność bazy ogranicza zależność decyzji od pojedynczego sąsiada.

W IPv4 OSPF jest przenoszony bezpośrednio przez IP z numerem protokołu 89, bez warstwy UDP. OSPF jest protokołem typu , co zwykle ułatwia skalowanie i skraca konwergencję względem protokołów wektora odległości. OSPF jest otwartym, niezastrzeżonym standardem oraz . Stosuje się go w sieciach korporacyjnych i operatorskich do routingu wewnątrz jednego systemu autonomicznego.

Metryka OSPF: koszt interfejsu i przepustowość

RIP porównuje trasy przede wszystkim liczbą przeskoków. OSPF przypisuje każdemu interfejsowi wartość metryki nazywaną kosztem, a router wybiera trasę o najmniejszej sumie tych wartości.

Koszt OSPF jest dodatnią wartością liczbową przypisaną do interfejsu. Niższy koszt oznacza preferowaną trasę, a kilka tras o tej samej wartości może zostać użytych jako ścieżki równokosztowe. RFC pozostawia sposób wyznaczania kosztu implementacji. W Cisco IOS domyślna wartość referencyjna wynosi 100 Mb/s, a koszt wylicza się na podstawie przepustowości interfejsu:

\text{Koszt} = \frac{\text{Przepustowość Referencyjna}}{\text{Przepustowość Interfejsu}}

Przepustowość referencyjna jest konfigurowalnym parametrem implementacji. Przepustowość interfejsu opisuje prędkość łącza, na przykład 10 Mb/s dla Ethernetu, 100 Mb/s dla Fast Ethernetu i 1000 Mb/s dla Gigabit Ethernetu. Całkowity koszt ścieżki jest sumą kosztów interfejsów wychodzących na tej ścieżce. Jawnie skonfigurowany koszt interfejsu może zastąpić wartość wyliczoną, dlatego parametry powinny być spójne na wszystkich routerach. Implementacja może zaokrąglać wynik zgodnie z własnymi regułami. Wzór stanowi konwencję implementacyjną, nie uniwersalne wymaganie OSPF.

Przykład: Wybór Szybszej Ścieżki

Rozważmy pakiet wysyłany z sieci przy Routerze A do sieci przy Routerze D. Przyjmijmy, że w konfiguracji użyto przepustowości referencyjnej 1 Gb/s (1000 Mb/s).

Ścieżka 1 (A -> B -> D): Wykorzystuje łącza Gigabit Ethernet.
- Koszt łącza A->B: $\frac{1000 \text{ Mb/s}}{1000 \text{ Mb/s}} = 1$
- Koszt łącza B->D: $\frac{1000 \text{ Mb/s}}{1000 \text{ Mb/s}} = 1$
- Całkowity Koszt dla Ścieżki 1 = 2
Ścieżka 2 (A -> C -> D): Wykorzystuje łącza Ethernet o przepustowości 10 Mb/s.
- Koszt łącza A->C: $\frac{1000 \text{ Mb/s}}{10 \text{ Mb/s}} = 100$
- Koszt łącza C->D: $\frac{1000 \text{ Mb/s}}{10 \text{ Mb/s}} = 100$
- Całkowity Koszt dla Ścieżki 2 = 200

OSPF wybiera ścieżkę o najniższym całkowitym koszcie, więc w tym przykładzie wybierze Ścieżkę 1. Przy takiej konfiguracji łącza o większej przepustowości otrzymują niższy koszt niż łącza 10 Mb/s. W RIP sama liczba przeskoków mogłaby wskazać inną trasę.

Działanie OSPF: sąsiedztwa, LSDB i SPF

OSPF buduje tablicę routingu w trzech powiązanych etapach: wykrywa sąsiadów, synchronizuje informacje o stanie łączy i oblicza trasy na podstawie bazy LSDB.

1. Odkrywanie sąsiadów i nawiązywanie relacji (protokół Hello)

Router wysyła pakiety "Hello" przez interfejsy, na których działa OSPF. Odbiór pakietów od drugiego routera oraz zgodność parametrów, takich jak identyfikator obszaru, maska sieci i liczniki czasu, pozwalają utworzyć relację sąsiedztwa. Nie każda para sąsiadów synchronizuje pełną bazę, ponieważ zakres tej synchronizacji zależy od typu sieci i roli routera.

2. Budowanie mapy (wymiana bazy danych stanu łączy)

Po nawiązaniu relacji routery synchronizują informacje o topologii. Pakiety aktualizacyjne zawierają . LSA opisuje między innymi połączenie Routera X z Routerem Y przez interfejs o koszcie 10 oraz z Routerem Z przez interfejs o koszcie 5.

Routery zalewają LSA w zakresie określonym przez typ ogłoszenia. Po zakończeniu synchronizacji routery należące do tej samej instancji i obszaru powinny mieć zgodną bazę danych stanu łączy (LSDB). Każdy z nich dysponuje wtedy tym samym opisem topologii właściwym dla danego obszaru. LSA mają numery sekwencyjne, wiek i sumę kontrolną, więc router może rozpoznać nowszą wersję oraz usunąć wygasłe dane.

3. Obliczanie najlepszych tras (algorytm SPF)

Na podstawie LSDB każdy router niezależnie uruchamia algorytm Shortest Path First (SPF), oparty na algorytmie Dijkstry. Umieszcza siebie w korzeniu drzewa i wykorzystuje koszty łączy, aby obliczyć ścieżki o najmniejszym koszcie do miejsc docelowych.

Wynikiem obliczeń SPF jest drzewo najkrótszych ścieżek. Router wybiera z niego trasy bez pętli i umieszcza je w tablicy routingu. Zgodna LSDB prowadzi do spójnych decyzji w obrębie obszaru. Po awarii łącza router rozgłasza nowe LSA, a pozostałe routery aktualizują LSDB i ponownie wykonują obliczenia, co prowadzi do sieci.

Skalowalność przez hierarchię obszarów OSPF

W dużej sieci, obejmującej tysiące routerów, zalewanie LSA i obliczenia SPF na dużej LSDB zwiększają zużycie pamięci oraz procesora. Częste zmiany pojedynczego łącza mogą też generować wiele aktualizacji. OSPF ogranicza ten zakres przez podział domeny na obszary.

OSPF stosuje hierarchię opartą na obszarach (ang. areas). Obszar jest logiczną grupą routerów i sieci, dla której utrzymuje się odrębną bazę topologii. ABR przekazuje między obszarami trasy podsumowane w LSA typu summary, a trasy zewnętrzne są opisywane osobno przez ASBR.

Dwuwarstwowa hierarchia

Domena OSPF obejmuje specjalny obszar szkieletowy (obszar 0) oraz obszary inne niż szkieletowy. Obszary inne niż szkieletowy powinny mieć połączenie z obszarem 0. Jeśli fizyczna ciągłość szkieletu jest przerwana, można użyć łącza wirtualnego. Obszar 0 przenosi ruch między obszarami i dystrybuuje informacje podsumowujące.

Podział na obszary daje kilka praktycznych korzyści:

Mniejszy narzut: LSA o zasięgu obszaru są rozsyłane wewnątrz własnego obszaru. Router w Obszarze 11 nie przechowuje szczegółowej topologii Obszaru 10, więc zmniejszają się ruch aktualizacyjny i rozmiar LSDB.
Szybsze obliczenia SPF: Mniejsza LSDB ogranicza liczbę węzłów analizowanych przez SPF i może zmniejszyć obciążenie procesora.
Ograniczenie zmian: Zmiana LSA o zasięgu obszaru nie wymusza ponownego obliczenia topologii w każdym innym obszarze. Skutki niestabilnego łącza pozostają w większym stopniu lokalne.

Role routerów OSPF

Podział na obszary wyróżnia następujące role routerów:

Router wewnętrzny: Router, którego wszystkie bezpośrednio podłączone sieci należą do jednego obszaru.
Router szkieletowy: Router mający interfejs w obszarze 0. Każdy ABR jest także routerem szkieletowym, jeśli ma połączenie z obszarem 0.
Router brzegowy obszaru (ABR): Router dołączony do wielu obszarów. Utrzymuje osobne dane dla tych obszarów, podsumowuje ich topologię i rozgłasza informacje między obszarem 0 a obszarami pozostałymi.
Router graniczny systemu autonomicznego (ASBR): Router wymieniający informacje z innym systemem autonomicznym albo redystrybuujący trasy z zewnętrznego źródła, na przykład BGP, RIP lub tras statycznych.

DR i BDR w sieciach wielodostępowych

W sieciach wielodostępowych, takich jak Ethernet, wiele routerów może współdzielić jeden segment. OSPF wykorzystuje na takim segmencie router wyznaczony i zapasowy router wyznaczony, aby ograniczyć liczbę pełnych relacji.

Liczba potencjalnych relacji

Załóżmy 10 routerów podłączonych do jednego segmentu Ethernet. Gdyby każda para musiała synchronizować bazę bezpośrednio, liczba potencjalnych relacji wynosiłaby $\frac{n(n-1)}{2}$ , czyli 45 dla 10 routerów. Pełne synchronizacje wszystkich par zwiększałyby liczbę komunikatów i powtórzeń LSA.

Wybór DR i BDR

Dla każdego segmentu wielodostępowego OSPF wybiera router wyznaczony (DR) oraz zapasowy router wyznaczony (BDR). Wybór uwzględnia priorytet interfejsu, a przy remisie identyfikator routera. Zmiana DR jest ograniczana, aby nie powodować częstej przebudowy relacji.

Zamiast pełnej synchronizacji każdej pary działa następujący model:

Pozostałe routery segmentu, zwane DROther, tworzą pełną relację z DR i BDR. Między sobą pozostają w stanie 2-Way.
Gdy DROther wysyła aktualizację, kieruje ją multicastowo do grupy DR i BDR.
DR rozsyła aktualizację do pozostałych routerów segmentu, aby ich LSDB pozostały zsynchronizowane.
BDR utrzymuje relacje i aktualną LSDB, więc po awarii DR może przejąć jego funkcję bez tworzenia wszystkich relacji od początku.

DR i BDR ograniczają liczbę pełnych relacji oraz ruch związany z synchronizacją na segmencie wielodostępowym. Na łączu punkt-punkt, gdzie uczestniczą dwa routery, wybór DR i BDR nie jest potrzebny.