(T) Algorytm DUAL EIGRP

Algorytm DUAL EIGRP

Diffusing Update Algorithm

  • Algorytm DUAL ma na celu:
    • Określenie najlepszej, wolnej od pętli trasy, względem każdej z rozgłaszanych sieci.
    • Określenia zapasowych wolnych od pętli tras, względem każdej z rozgłaszanych sieci.
    • Zapewnienie szybkiej konwergencji (Network Convergence).

Pojęcia dotyczące algorytmu DUAL

  • Protokół EIGRP wykorzystuje algorytm DUAL (Diffusing Update Algorithm), w celu poszukiwania najlepszej trasy wolnej od pętli sieciowych jak i do wykrywania tras zapasowych. Algorytm DUAL wykorzystuje następujące pojęcia:
    • Successor – Pierwszy ruter następnego przeskoku względem trasy Successor route.
    • Successor route – Trasa z najmniejszą wartością metryki, stanowiąca następny przeskok (Next-hop) w drodze do sieci docelowej. Trasa ta znajduje się w zarówno tablicy topologii jak i tablicy routingu.
    • FS (Feasible Successor) – Trasa zapasowa prowadząca do sieci docelowej, spełniającej warunek FC (Feasibility Condition). Widoczna w wydruku komendy [show ip eigrp topology].
    • Nonsuccessor – Trasa zapasowa prowadzącą do sieci docelowej, nie spełniającą warunków FC (Feasibility Condition). Nie jest widoczna w wydruku komendy [show ip eigrp topology] a jedynie za pomocą komendy [show ip eigrp topology all-links].
    • FD (Feasible Distance) – Najniższa wartość metryki, dotarcia do sieci docelowej.
    • RD (Reaported Distance) lub AD (Advertised Distance) – Wartość metryki FD, względem sąsiedniego urządzenia.
    • CD (Computed Distance) – Wartość metryki FD, względem lokalnego urządzenia (Computed Distance = Reaported Distance + koszt połączenia pomiędzy ruterem a sąsiadem).
    • FC (Feasibility Condition) – Warunek dotyczący wyboru trasy zapasowej, prowadzącej do sieci docelowej (Feasible Successor). Wartość Reported Distance rozpatrywanego połączenia zapasowego Feasible Successor, musi być mniejsza niż obecna wartość Feasible Distance trasy głównej Successor.

Tablica topologii a algorytm DUAL

# show ip eigrp topology all-links
EIGRP-IPv4 Topology Table for AS(1)/ID(3.3.3.3)
Codes: P – Passive, A – Active, U – Update, Q – Query, R – Reply, r – reply Status, s – sia Status
P 192.168.100.0/24, 1 successors, FD is 130816, serno 272
        via 10.0.0.1 (130816/128256), GigabitEthernet0/4
        via 172.16.33.2 (27008000/128256), Tunnel1
        via 10.0.0.13 (131072/130816), GigabitEthernet0/1
P 10.0.0.8/30, 2 successors, FD is 3072, serno 91
        via 10.0.0.1 (3072/2816), GigabitEthernet0/4
        via 10.0.0.13 (3072/2816), GigabitEthernet0/1
        via 172.16.33.2 (26880256/2816), Tunnel1
P 192.168.0.0/16, 1 successors, FD is 131072, serno 241
        via 10.0.0.22 (131072/130816), GigabitEthernet0/3
        via 172.16.33.2 (27008768/131328), Tunnel1
        via 10.0.0.18 (133120/128256), GigabitEthernet0/2
P 5.5.5.5/32, 1 successors, FD is 130816, serno 89
        via 10.0.0.22 (130816/128256), GigabitEthernet0/3
        via 172.16.33.2 (27008512/131072), Tunnel1
P 10.0.0.24/30, 1 successors, FD is 3072, serno 88
        via 10.0.0.22 (3072/2816), GigabitEthernet0/3
        via 172.16.33.2 (26880768/3328), Tunnel1

  • Successor route
  • Feasible Successor
  • Nonsuccessor
  • Feasible Distance
  • Reaported Distance
  • Computed Distance

Wartość Fasible Distance

  • Wartość FD (Fasible Distance) określa „historyczną” kopię najniższej wartości Computed Distance względem danej sieci, która jest odnawiana zaraz po zajściu procesu „Active-to-Passive transition”. Tym samym wartość Feasible Distance nie musi być równa obecnie najniższej wartości Computed Distance.
  • Zgodnie z definicją, podczas stanu pasywnego (Passive), wartość Feasible Distance może ulec jedynie zmniejszeniu. Oznacza to że zwiększenie obecnie najniższej wartości Computed Distance (Successor) nie wpłynie na wartość Feasible Distance (Oczywiście zmiana wartości nie może doprowadzić do zamiany roli Successor-a, w takim przypadku wartość Feasible Distance ulegnie zmianie). Przykładową sytuacją takiego zajścia jest lista Offset zwiększającą metrykę o np. 10.
Protokół EIGRP nie rozgłasza wartości FD (Feasible Successor), a jedynie komponenty służące do wyliczania metryki, takie jak Bandwidth oraz Cumulative Delay.
Obliczanie metryki trasy dla protokołu EIGRP

Successor & Feasible Successor

  • Algorytm DUAL przechowuje w tablicy topologii informację o trasach głównych Successor jak i zapasowych Feasible Successor, dzięki czemu może szybko reagować na zmiany zachodzące w topologii sieciowej.
  • Każda sieć zapisana w tablicy topologii znajduje się w określonym stanie (Aktywnym Active bądź pasywnym Passive). Z czego stan pasywny (Passive) oznacza stabilną topologię sieciową, natomiast stan aktywny (Active) zachodzi podczas zmian zachodzących w topologii sieciowej, które związane są z wysyłaniem wiadomości Query oraz wiadomości Replay.
  • Proces przywracania połączenia w przypadku awarii trasy, wygląda następująco:
Proces postępowania w przypadku utraty trasy głównej „Successor”

Tablica Topologii (Topology Table)

Zawartość Tablicy topologii

  • Tablica topologii protokołu EIGRP, zawiera następujące informacje na temat tras routingu:
    • Adres oraz maskę sieci docelowej.
    • Wartość Fasible Distance.
    • Wartość Reaported Distance 
    • Adres sąsiada rozgłaszającego informacje o danej trasie, wraz z interfejsem do niego prowadzącym.
    • Dodatkowe informacje dotyczące trasy (Flagi, rodzaje sieci i inne).
  • Tablica topologii zawiera sieci lokalne (Bezpośrednio przylegające do rutera) jak i sieci pozyskane za pomocą wiadomości protokołu EIGRP (Takich jak: Update, Query, Replay, SIA-Query oraz SIA-Replay).
  • Sieci zdalne (Remote Networks) pozyskane za pomocą protokołu EIGRP, najpierw wpisywane są do tablicy topologii EIGRP a następnie do lokalnej tablicy routingu.

Proces wymiany informacji zawartych w tablicy topologii

Aby router mógł rozpocząć proces wymiany informacji na temat dostępnych tras routingu, pomiędzy sąsiednimi urządzeniami. Najpierw musi wypełnić zawartość lokalnej tablicy topologii, protokołu EIGRP. W tym celu pobiera informację o sieciach bezpośrednio przyległych do urządzenia, za pomocą komendy [network sieć maska].
  1. Trasy z najniższą metryką FD (Fasible Distance) zawarte w tablicy topologii są przenoszone do lokalnej tablicy routingu, jak i propagowane do sąsiednich urządzeń (sąsiadów protokołu EIGRP), za pomocą wiadomości aktualizacyjnych (Update). Wiadomości te zawierają następujące informacje:
    • Prefix – Adres IP sieci docelowej.
    • Prefix length – Maskę sieci docelowej.
    • Metric components (Bandwidth (Kbps), Delay (Dziesiątki milisekund), Reliability (Domyślnie 1), Load (Domyślnie 255)) – Domyślnie wartości Reliability oraz Load są przesyłane pomiędzy sąsiadami, lecz nie są brane pod uwagę przy wliczaniu metryki protokołu EIGRP.
    • NonMetric items ( MTU, Hop count) – Wartości MTU oraz Hop Count są przesyłane pomiędzy sąsiadami, lecz nie są brane pod uwagę przy wyliczaniu metryki protokołu EIGRP.
  2. W odpowiedzi na otrzymaną wiadomość aktualizacyjną, sąsiednie urządzenie potwierdza otrzymanie wiadomości Update, za pomocą wiadomości potwierdzającej ACK (Acknowledgment). Aby następnie, porównać otrzymaną wartość najniższego pasma (Bandwidth) z wartością lokalną, przypisaną do interfejsu sieciowego na którym została ona odebrana. Jeżeli wartość ta jest mniejsza, zastąpi wcześniej propagowaną. W przypadku opóźnienia (Delay), rozgłaszana wartość stanowi sumę wartość wszystkich opóźnień dla danej trasy routingu. Tym samym wartość lokalnego opóźnienia nie jest nadpisywana, a sumowana z wartością otrzymaną.
  3. Po dokonaniu powyższych zmian, sąsiedni ruter rozpoczyna proces propagowania własnych wiadomości update, na wszystkich interfejsach aktywnych względem danej instancji protokołu EIGRP (Interfejs ten nie może być pasywny [passive interface interfejs]). Ponadto wiadomości aktualizacyjne nie są propagowane na interfejsie, na którym znajduje się ruter, który nadał pierwotną wiadomość Update (Ograniczenie te, wynika z działania domyślnie aktywowanej funkcji Split Horizon).

Wartości czasowe

  • Przy określaniu opóźnienia (Delay) należy zwrócić uwagę na różnice dotyczące sposobu przedstawianiu czasu.
    • Czas podawany w mikrosekundach – Jest wyświetlany za pomocą komend SHOW np. [show ip eigrp topology].
    • Czas podawany w dziesiątkach mikrosekund – Jest wymieniany za pomocą wiadomości aktualizacyjnych (Update) jak i wykorzystywany w przypadku komendy [delay wartość-opóźnienia] względem określonego w komendzie interfejsu sieciowego.
Zawartość wiadomości aktualizacyjnych (Update)

Proces aktualizacji protokołu EIGRP

  • Protokół EIGRP wykorzystuje wiadomości (Update) w celu przesyłania aktualizacji, zgodnie z następującymi zasadami:
    • Podczas pierwszej wymiany danych pomiędzy sąsiadami, następuje pełna wymiana zawartości tablic topologii.
    • Po pierwszej wymianie informacji router wstrzymuje się od wysyłania dalszych aktualizacji. Kontakt pomiędzy sąsiadami jest utrzymywany za pomocą wiadomości powitalnych (Hello).
    • W przypadku wystąpienia zmiany w topologii sieciowej, router wysyła częściową aktualizację (Partial Update) za pomocą wiadomości aktualizacyjnej (Update), zawierającej informacje o zmianach zaszłych w sieci.
    • Po utraceniu łączności z sąsiadem a następnie jej odzyskaniu, następuje pełna wymiana zawartości tablic topologii.
    • W przypadku pełnej jak i częściowej wymiany aktualizacji, wiadomości aktualizacyjne są ograniczane przez funkcje „Split Horizon”, wpływającą na ich zawartość.

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

EIGRPv6

PDFPRINT

Robert T Kucharski

Cisco Network Engineer in GPW.

Dodaj komentarz