NetCLI

Tag: SPF

  • (T) Wybór najkrótszej trasy OSPF**

    (T) Wybór najkrótszej trasy OSPF**

    Wybór najkrótszej trasy

    Proces wymiany struktur LSA, ma na celu stworzenie spójnej bazy LSDB, względem wszystkich urządzeń znajdujących się w obrębie jednej tej samej strefy (Area). Dzięki czemu możliwe staje się znalezienie najkrótszej trasy prowadzącej do sieci docelowej. Proces ten wygląda następująco:

    • Algorytm SPF analizuje zawartość bazy LSDB w celu znalezienia wszystkich tras prowadzących do sieci docelowej.
    • Dla każdej z znalezionych tras, protokół OSPF kalkuluje koszt dotarcia do sieci docelowej, na podstawie zsumowanych kosztów poszczególnych interfejsów sieciowych na drodze do celu.
    • Algorytm SPF dodaje to tablicy routingu trasę z najniższym kosztem dotarcia do sieci docelowej.
    Koszt interfejsu sieciowego względem protokołu OSPF może być wyświetlony za pomocą komendy [show ip ospf interface].
    Kalkulacja kosztów tras, prowadzących do sieci docelowej

    Kalkulacja najkrótszej trasy (Intra-Area Routes)

    • Podczas analizy bazy LSDB, protokół OSPF:
      • Szuka wszystkich sieci dodanych do bazy LSDB na podstawie struktur LSA typu pierwszego oraz drugiego.
      • Uruchamia algorytm SPF w celu znalezienia wszystkich tras prowadzących do sieci znalezionych w punkcie 1.
      • Kalkuluje koszt każdej trasy na podstawie kosztów interfejsów wyjściowych.
      • Wybiera trasę z najniższym kosztem względem wszystkich sieci znalezionych w punkcie 1
    • W przypadku znalezienia wielu tras o tym samym koście dotarcia do celu, OSPF wykorzystuje wszystkie trasy z pomocą funkcji Load-Balance. Maksymalną liczbę jednocześnie wykorzystywanych tras można skonfigurować za pomocą komendy [maximum-paths 1-32] w trybie konfiguracji protokołu OSPF.
    Zmiana zaszła w strukturze LSA typu pierwszego bądź drugiego wymaga ponownej rekalkulacji algorytmu SFP.

    Kalkulacja najkrótszej trasy (Interarea Routes)

    • Podczas analizy bazy LSDB, protokół OSPF:
      • Szuka najkrótszej trasy dotarcia do rutera ABR, rozgłaszającego struktury LSA typu trzeciego.
      • Dodaje do kosztu dotarcia do rutera ABR, koszt rozgłaszany poprzez strukturę LSA typu trzeciego. Jest to koszt trasy pomiędzy ruterem ABR a siecią docelową.
    • Struktura LSA typu trzeciego zawiera:
      • Adres sieci wraz z maską.
      • Koszt dotarcia z rutera ABR do sieci docelowej.
      • Wartość RID rutera ABR.
    Zmiana zaszła w strukturze LSA typu trzeciego nie wymaga ingerencji algorytmu SFP.

    Intra-Area Routes oraz Interarea Routes na ruterach ABRs

    • Problem
      związany z trasami Intra-Area Routes oraz Interarea Routes, pojawia się w sytuacji,
      w której wiele ruterów ABR łączą ze sobą dwie te same strefy (Area), w
      celu zachowania nadmiarowości.
    • Każdy
      z wyżej wspomnianych ruterów ABR posiada trasę Intra-Area Routes oraz Interarea
      Routes, prowadząca do sieci docelowej. Związku z tym protokół OSPF będzie
      kierował się następującą logiką:
      • Trasa Intra-Area jest zawsze lepsza od trasy
        Interarea Routes, niezależnie od kosztów obydwóch tras.
      • Jeżeli ruter ABR otrzyma strukturę typu trzeciego w strefie Nonbackbone,
        zignoruje ją.
    Trasa Intra-Area oraz Interarea na ruterach ABR

    Licznik użycia algorytmu SFP

    Każdorazowa zmiana struktury LSA typu pierwszego bądź drugiego, wymaga ponownego przeliczenia najkrótszej trasy z wykorzystaniem algorytmu SFP, co zwiększa wartość licznika widocznego pod wydrukiem komendy [show ip ospf].

    # show ip ospf
    …
    Area BACKBONE(0)
    Number of interfaces in this area is 1
    Area has no authentication
    SPF algorithm last executed 2w5d ago
    SPF algorithm executed 2 times
    Area ranges are
    Number of LSA 3. Checksum Sum 0x01101D
    Number of opaque link LSA 0. Checksum Sum 0x000000
    Number of DCbitless LSA 0
    Number of indication LSA 0
    Number of DoNotAge LSA 0
    Flood list length 0

    Kolejność wyboru tras protokołu OSPF (AD, Metric)

    1. Intra-Area (O).
    2. Inter-Area (O IA).
    3. External Type 1 (E1).
    4. External Type 2 (E2).
    5. NSSA Type 1 (N1).
    6. NSSA Type 2 (N2).

    Pozostałe tematy związane z protokołem OSPF

    OSPFv3

  • (T) LSDB (Link-State Database) OSPF**

    (T) LSDB (Link-State Database) OSPF**

    Struktura danych protokołu OSPF

    • Adjacency Database <-> Neighbor Table:
      • Zawiera listę wszystkich ruterów z którymi lokalne urządzenie nawiązało relację sąsiedztwa.
      • Jej zawartość może być wyświetlona za pomocą komendy [show ip ospf neighbor].
      • Jest unikalna względem każdego z ruterów.
    • Link-State Database (LSDB) <-> Topology Table:
      • Posiada informacje o wszystkich ruterach należących do tej samej strefy (Area).
      • Zawiera wartości RID wszystkich ruterów należących do tej samej strefy (Area).
      • Posiada informacje o wszystkich sieciach należących do tej samej strefy (W tym adresy IP oraz maski sieciowe).
      • Jej zawartość może być wyświetlona za pomocą komendy [show ip ospf database].
      • Jest taka sama względem wszystkich ruterów w danej strefie.
    • Forwarding Database <-> Routing Table:
      • Zawiera trasy dodane przez algorytm SPF, na podstawie zawartości bazy Link-State Database (LSDB).
      • Jej zawartość może być wyświetlona za pomocą komendy [show ip route ospf].
      • Jest unikalna względem każdego z ruterów, ponieważ przedstawia sieć protokołu OSPF w postaci drzewa topologii sieciowej, z lokalnym ruterem stanowiącym korzeń.

    Struktury LSA

    • Struktury LSA są wykorzystywane przez protokół OSPF, w celu wymiany informacji dotyczących budowy topologii sieciowej.
    • Poszczególne informacje zawarte w strukturach LSA tworzą bazę danych LSDB (Link State Data Base).
      • LSA Type 1 – Router.
      • LSA Type 2 – Network.
      • LSA Type 3 – Net Summary.
      • LSA Type 4 – ASBR Summary.
      • LSA Type 5 – AS External.
      • LSA Type 6 – Group Membership.
      • LSA Type 7 – External Attributes (NSSA External).
      • LSA Type 8 – Link LSAs (OSPFv3).
      • LSA Type 9 – Intra-Area Prefix LSAs  (OSPFv3).
    • Przed rozpoczęciem procesu wymiany danych zgromad
    • zonych w bazie LSDB, każdy z ruterów rozpoczyna wysyłanie wiadomości DBD zawierających wartości LSID każdej posiadanej przez siebie struktury LSA. Jeżeli sąsiednie urządzenie zorientuje się że nie posiada którejś ze struktur LSA, może o nią poprosić za pomocą zapytania LSR. W odpowiedzi na które, otrzyma wiadomość LSU zawierającą brakujące struktury LSA.

    Algorytm SPF (Shortest Path First)

    • Protokół OSPF w celu wyznaczenia najkrótszej trasy dotarcia do celu, wykorzystuje algorytm „Dijkstra SPF Algorithm”.
    • Algorytm SPF (Shortest Path First) tworzy drzewo, którego korzeniem jest lokalny ruter (Na jego podstawie wyliczana jest najkrótsza trasa dotarcia do każdej znanej sieci). Następnie wyliczone trasy są przekazywane do lokalnej tablicy routingu.

    Zmiana zawartości w rozgłaszanej strukturze LSA

    • Jeżeli po dokonaniu zmiany w topologii sieciowej, struktura LSA np. typu pierwszego przestała być już aktualna, ruter za nią odpowiedzialny zacznie rozgłaszać ją ze zmodyfikowaną wartość wieku (Age), zwiększoną do wartości „Max Age” czyli 3600 sekund. Po czy stworzy a następnie zacznie rozgłaszać nową strukturę LSA, ze zwiększonym numerem sekwencyjnym oraz zresetowanym czasem (Age).

    Pozostałe tematy związane z protokołem OSPF

    OSPFv3