Home Technologie siecioweRouting & Switching OSPF – Routing w oparciu o link state | teoria
ospf open shortest path first

OSPF – Routing w oparciu o link state | teoria

Rafał Rudewicz

OSPF Dynamiczny routing typu link-state

Ospf (ang. Open Shortest Path First) to obecnie jeden z najchętniej wybieranych protokołów IGP. Oznacza to, że służy on do trasowania – lub inaczej routowania – pakietów w ramach jednego systemu autonomicznego, podobnie jak ma to miejsce w przypadku EIGRP. Współcześnie stosujemy OSPF w wersji 2 dla ipv4 oraz w wersji 3 dla ipv6. 

Swoją popularność zawdzięcza, że od początku:

  • Wykorzystanie algorytmu SPF do wybierania najkorzystniejszej trasy
  • Sporym możliwościom optymalizacji dzięki:
    • 5 różnym rodzajom obszarów (normal, stub, totally stub, not so stubby, totally not so stubby)
    • 7 różnym pakietom LSA (link state update)
    • Hierarchizacji routerów w danym obszarze
  • Możliwości uwierzytelniania sąsiadów (md5)

Nawigacja w Twoim aucie korzysta z dokładnie tego samego algorytmu – SPF – wyboru najlepszej trasy.

Wszystko dzięki Panu o nazwisku Dijsktra, dzięki stary! 😉

OSPF był od początku protokołem otwartym, który działał na sprzęcie każdego vendora. W przeciwieństwo do wspomnianego już EIGRP, który przez pewien czas był wyłącznie dostępny dla routerów Cisco.

 Protokół routingu na podstawie stanu łącza

OSPF razem z IS-IS należy do grupy protokołów routingu typu link-state. Oznacza to, że każdy router w danym obszarze – zwanym area – posiada identyczną bazę topologii, na podstawie której wybiera najkorzystniejszy wpis do tablicy routingu. Z tego powodu wynika jednak pewien minus. Wraz ze wzrostem liczby routerów w danym obszarze liczba przesyłanych pakietów znacząco wzrasta.

W celu ograniczenia tego zjawiska routery są dzielone hierarchicznie na obszary. Z centralnie umieszczonym obszarem 0 (ang. area 0, backbone), przez który muszą przechodzić wszystkie informacje. OSPF jest protokołem link state jedynie wewnątrz obszaru, informacje o podsieciach są rozsyłane przez routery brzegowe – ABR i ASBR – w formie zsumaryzowanej informacji (gotowych ścieżek). Oznacza to, że między obszarami OSPF zachowuje się jak protokół distance-vector.

Podstawowymi cechami odróżniającymi go od protokołów typu distance-vector są:

– metryki/koszty przejścia pakietu przez dany link
– oszczędność pasma uaktualnienia wysyłane jedynie w przypadku zmiany stanu łącza, a nie w formie okresowych rozgłoszeń
– szybka konwergencja – zdolność do uzyskania stanu stabilnego po wykryciu zmiany w drzewie połączeń sieciowych;
– struktura hierarchiczna – zastosowanie obszarów w celu zmniejszenia liczby przesyłanych pakietów, z centralnie położonym obszarem 0 (backbone)
– wsparcie dla VLSM (Variable Length Subnet Mask) – cecha niektórych protokołów trasowania umożliwiająca podzielenie i rozróżnianie podsieci z już istniejących sieci
– możliwość uwierzytelniania sąsiadów – przyległych routerów w rozumieniu konkretnej instancji OSPF

Koszt i metryka OSPF

Koszt danego linku obliczamy poprzez podzielenie referencyjnej przepustowości (wartość referencyjna może być dowolnie skonfigurowana) przez przepustowość interfejsu. W danym obszarze wszystkie routery muszą mieć taką samą wartość referencyjną, najlepiej najszybszego interfejsu.

Koszt = Referencyjna przepustowość / przepustowość interfejsu
Przykład: Koszt = 100Mbps/ 100Mbps = 1

Kiedy potrzebujesz większej kontroli nad ruchem w Twojej sieci, możesz ręcznie skonfigurować koszt na każdym z interfejsów.

Gdy router zakończy obliczanie kosztów dla każdej z tras do podsieci, (suma wszystkich kosztów interfejsów po drodze do celu) umieszcza trasę z najniższym kosztem w tablicy routingu. Należy pamiętać, że kiedy do danej podsieci prowadzi więcej niż jedna ścieżka o takim samym koszcie, możliwe jest zastosowanie load-balancigu realizowanego przez CEF (Cisco Express Forwarding).

Topologie sieci w OSPF

W celu ciągłego utrzymania relacji sąsiedztwa, routery OSPF wysyłają pakiety Hello. Sposób komunikacji między nimi, jest zależny od rodzaju topologii. Wyróżniamy 5 rodzajów topologii: point-to-point, point-to-multipoint, Broadcast Multiaccess, Nonbroadcast Multiaccess, Virtual Links.

Point to Point Network

O sieciach punkt-punkt mówimy, gdy dwa routery są połączone ze sobą bezpośrednio. Medium transmisyjne jest używane tylko do komunikacji między nimi. Ponieważ relacja przylegania jest jednoznacznie określone i nie ma potrzeby przeprowadzania elekcji DR i BDR. Porty szeregowe domyślnie mają ustawiony network type jako Point-to-Point. Interfejsy ethernetowe nawet jeśli są połączone ze sobą bezpośrednio kablem, wymagają zmiany network type na point-to-point.

Point to Multipoint Network

Sieci point to multipoint występują wtedy, gdy jeden interfejs łączy się w wieloma innymi. Taką grupę połączeń traktujemy jako sieć point to point zawartą w jednym interfejsie. Nie występuje konieczność elekcji DR i BDR.

Broadcast Multiaccess Network

Do sieci wielodostępowych zaliczamy między innymi sieci Ethernet. W takim modelu dozwolone jest rozsyłanie informacji do wszystkich hostów w sieci, a medium jest współdzielone. W związku, z czym niezbędny jest wybór DR oraz BDR, aby zapobiec tworzeniu się dużej ilości połączeń przylegania. 

Nonbroadcast Multiaccess Network

Sieci point-to-multipoint, które z jakiegoś powodu nie pozwalają na rozsyłanie pakietów broadcastowych i multicastowych nazywamy właśnie sieciami typu nonbroadcast multiaccess. Fizycznie taka sieć jest realizowana w połączeniach point-to-point i konieczna jest elekcja DR i BDR. Pakiety LSA rozsyłane są na adresy unicastowe.

Virtual Links

Każdy obszar w danej sesji OSPF powinien przylegać bezpośrednio do obszaru 0 (obszaru backbone). Jednak zdarza się, że nie ma takiej możliwości i wtedy należy utworzyć wirtualne połączenie poprzez obszary pośredniczące, tak aby docelowo osiągnąć relacje przylegania z obszarem backbone.

Poglądowy schemat gdzie tworzone są relacje DR-BDR oraz DRother

Nawiązywanie relacji przylegania

Kiedy dołączymy nowy router do obszaru, nie wystarczy podłączyć go do sieci, aby otrzymał on wszelkie informacje i miał pełną tablicę topologi sieci. Niezbędne jest wcześniejsze zsynchronizowanie tablic topologii oraz wyliczenie nowych tras na routerach w danym obszarze. Pierwszym krokiem w tym procesie jest nawiązanie relacji przylegania. Routery przyjmują wtedy kolejno stany:

  1. Down state – Router wysyła na multicastowy adres 224.0.0.5 (AllSPFRouters) pakiety Hello, oznajmiając swoją obecność w sieci. Pola adresów DR i BDR w danym obszarze zawierają wartość 0.0.0.0
  2. Init state – Router oczekuje na odpowiedź od innych routerów pracujących w tym samym obszarze. Okres oczekiwania zazwyczaj stanowi czterokrotną wartość timera pakietu Hello (na routerach Cisco jest to 10 sekund). Z odebranych pakietów router dowiaduje się o adresach DR i BDR. Jeżeli nie otrzyma takiej informacji, rozpoczyna proces wyboru nowego DR’a oraz BDR’a. Router z najwyższym ID zostaje wybrany na DR. Zwycięzca elekcji dodaje nowy router do swojej tablicy topologii oraz w odpowiedzi wysyła swoje ID wraz z listą wszystkich znanych mu sąsiadów.
  3. Two-way state – Nowodołączany router widzi swoje ID w uzyskanej liście sasiadów. Wynikiem tego jest nawiązanie poprawnego sąsiedztwa między routerami.
  4. Exstart state – Bazując na adresie IP, router o wyższym adresie uzyskuje pierwszeństwo rozpoczęcia procedury wymiany informacji.
  5. Exchange state – Routery wymieniają się pakietami DDP (Database description packet). Ponieważ nowy router nie ma żadnej wiedzy o topologi obszaru, poza bezpośrednio sąsiadującymi urządzeniami. Uzyskuje ją od DR, który wysyła serię pakietów DDP zawierających informacje o obszarze. Przyłączone sieci nazywane sa linkami (links).
  6. Loading state – Ponieważ pakiety DDR zawierają tylko zsummaryzowane informacje o połączeniach, nowy router może potrzebować dodatkowych informacji o konkretnym łączu. Wysyła wtedy zadanie LSR (Link state request) do DR i oczekuje odpowiedzi w postaci pakietu LSU (Link state update).
  7. Full state – Wszystkie routery mają taką samą bazę topologii oraz znają wszystkie linki w danym obszarze.

Rodzaje pakietów LSA

  • Router-link (LSA typ 1) – wszystkie linki, które posiada dany router wraz z listą wszystkich
    sąsiadów. Rozsyłany tylko wewnątrz obszaru. Wysyłany przez każdy router uczestniczący w procesie OSPF.
  • Network-link (LSA typ 2) – Wysyłana przez DR lista wszystkich routerów w danym obszarze dla których służy jako DR i z którymi utrzymuje sąsiedztwo. Rozsyłany tylko wewnątrz obszaru.
  • Summary link (LSA typ 3) – przesyłane między obszarami, sumaryzuje informacje o sieciach w danym
    obszarze. Tworzy je ABR.
  • Summary link (LSA typ 4) – przesyłana między obszarami, informacjach o tym gdzie znajduje się ASBR. W pakiecie LSA 4 znajduje się informacjach o ABR który wysłał pakiet oraz o ASBR do którego można dotrzeć dzięki niemu.
  • External link (LSA typ 5) – informacje o redystrybuowanych sieciach. Rozsyłają je ASBRy.
    Wyróżniamy 2 podtypy:  
    • Typ 1 – metryka jest sumą kosztu dojścia po OSPF i metryki zewnętrznego protokołu;
    • Typ 2 – metryka jest tylko kosztem zewnętrznego protokołu;
  • NSSA External Link (LSA typ 7) – typ specjalnie stworzony dla obszarów NSSA, przeznaczony do przenoszenia informacji o redystrybuowanych sieciach. Analogicznie jak LSA 5 ma 2 typy. Tworzy je ASBR.

O czym należy pamiętać przy sumaryzacji?

Router ABR dokonuje sumaryzacji na granicy jednego lub więcej obszarów w danej instancji OSPF. Z kolei ASBR dokonuje sumaryzacji i redystrybucji na granicy systemu autonomicznego zwanego AS. Pamiętaj, że sumaryzować możemy tylko podsieci, które przylegają do obszaru i które router ma w swojej tablicy routingu.

Krótkie podsumowanie odnośnie sumaryzacji:

  • Sumaryzacji mogą dokonywać tylko ABRy i ASBRy.
  • Można sumaryzować do dowolnego rozmiaru podsieci (podsieć ma oczywiście rozmiar potęgi cyfry 2).
  • Sumaryzację należy skonfigurować ręcznie, uważnie rozplanowując sieć przy podziale na obszary.

Rodzaje obszarów w OSPF

  • Backbone Area – obszar ten nazywany jest też Area 0. Wszystkie obszary muszą przylegać do tego obszaru bezpośrednio lub poprzez Virtual Link. Rosyłane w nim są wszystkie rodzaje pakietów LSA, przy czym Type 7 LSA konwertowane jest do Type 5 LSA.
  • Standard Area – obszar przyłączony do obszaru 0. Każdy router posiada pełną wiedzę na temat topologii obszaru, do którego należy oraz bazę topologiczną.
  • Stub Area – obszar, w którym nie są akceptowalne informacje o innych podsieciach pochodzące z redystrybucji (z innych protokołów routingu) poprzez blokadę pakietów LSA typu 5. Dozwolona jest wymiana informacji z innymi obszarami w obrębie jednej instancji OSPF. Chcąc wysłać pakiety do innych podsieci (poza OSPF), wykorzystujemy default route. W obszarze stub nie może występować ASBR.
  • Totally Stub Area – obszar który nie akceptuje żadnych pakietów LSA zawierających zsumaryzowane informacje o innych podsieciach (pakiety LSA 3,4,5) pochodzących z poza obszaru TSA. Pakiety do podsieci poza obszarem OSPF wysyłamy poprzez default route.
  • Not So Stubby Area (NSSA) –  Obszary te nie akceptują informacji z redystrybucji, co oznacza, że blokadę pakietów LSA typu 4 i 5, dozwolone są za to informacje summaryzacyjne. Informacja o trasach z innych obszarów rozpropagowywana jest wewnątrz obszaru NSSA za pomocą pakietów LSA 7. Informacje o trasach z obszaru NSSA do innych rozsyłane są tylko przez routery ABR po konwersji na LSA typ 5. W NSSA w odróżnieniu od obszaru stub może występować ASBR.

Obszary typu stub oraz totally stubby nie akceptują pakietów LSA 5. Z tego powodu nałożone są na nie pewnie ograniczenia.

Niedozwolone są następujące działania:

  • Przekazywanie informacji o scieżkach spoza danego obszaru
  • Tworzenie wirtualnych połączeń (virtual links)
  • Redystrybucja tras z innych i do innych protokołów routingu
  • Brak routerów działajacych jako ASBR
  • Wszystkie routery w tym obszarze muszą być typu stub
  • Obszary te nie mogą być obszarami 0 (obszar backbone)

Możesz być również zainteresowany tymi artykułami:

2 komentarze

Szuwarek 11 listopada 2019 - 07:36

Router-link (LSA typ 1) i Network-link (LSA typ 2) zamieniły ci się miejscami opisy.

Odpowiedź
Rafał Rudewicz 11 listopada 2019 - 12:12

Z tego co widzę opisy są dobrze umiejscowione, może coś się źle wczytało.

Odpowiedź

Zostaw komentarz

Na blogu inna sieć wykorzystuję "ciasteczka". Lubię ciastka, a Ty? Lubię ciastka! Chcę wiedzieć więcej