Diffusing Update Algorithm

aus Wikipedia, der freien Enzyklopädie

Der Diffusing Update Algorithm (kurz DUAL) ist eine Komponente des cisco-proprietären Routing-Protokolls EIGRP. Er ist zuständig für die Routenberechnung. Der von Cisco angegebene vollständige Name des Algorithmus ist "DUAL finite-state machine" (DUAL FSM).

Mittels DUAL wird bei Benutzung von EIGRP ein schleifenfreies (loop-free) Routing innerhalb eines autonomen Systems erstellt. DUAL reagiert auf Veränderungen innerhalb der Routingtopologie dynamisch und passt die Routingtabellen der Router automatisch auf veränderte Gegebenheiten an.

[Bearbeiten] Funktionsweise

DUAL nutzt für die Routenberechnung drei von EIGRP in jedem Router separat erstellte Tabellen. Diese Tabellen werden auf Basis von EIGRP zwischen den Routern ausgetauschten Informationen erstellt. Dies ähnelt dem Informationsaustausch mittels eines Link-State Routing Protokolls. Im Gegensatz zu Link-State Übertragungen, bei denen jeder Router die "Link States" - d. h. den Status (aktiv/inaktiv) sowie die Bandbreite seiner Interfaces an alle Router eines autonomen Systems versendet, werden bei EIGRP sogenannte "neighbour relationships" aufgebaut. Über diese Nachbarschaften werden nur die Informationen von Router zu Router übermittelt, die die Gegenstelle benötigt.

Die drei Tabellen und deren Funktion im Einzelnen:

• neighbour table = enthält Informationen über alle anderen direkt verbundenen Router. Für jedes Protokoll (IP,IPX...) das EIGRP unterstützt existiert ein eigener neighbour table. Für jeden Nachbar wird ein Eintrag mit Beschreibung der Netzwerkschnittstelle und Adresse angelegt. Zudem wird ein Timer initialisiert, der in bestimmten Abständen überprüft ob die Verbindung mit dem Nachbarn noch aktiv ist. Dies wird mittels sogenannter "Hello" Pakete realisiert. Wird ein "Hello" Paket nicht während einer bestimmten Zeitspanne beantwortet, wird angenommen das die Route nicht mehr zur Verfügung steht und als "aktiv" markiert. (Siehe unten)
• topology table = enthält die Informationen über die Kosten jeder möglichen Verbindungen zu jedem Ziel innerhalb des autonomen Systems. Innerhalb der topology table werden mittels dieser Informationen die primäre und sekundäre Route zu einem Ziel festgelegt. Unter anderem enthält die topology table folgende Einträge pro Ziel:

FD (Feasible Distance): Dies ist die beste berechnete Distanz zu einem Ziel innerhalb des autonomen Systems.

RD (Reported Distance): Dies ist die Distanz zu einem Ziel, die als Information von einem Routernachbar übertragen wurde. Für jeden Nachbarn existiert eine eigene RD vom Nachbarn zum gewünschten Ziel.

route status: eine route ist entweder als "aktiv" oder "passiv" markiert. "passiv" markierte Routen sind stabil und können zur Datenübermittlung genutzt werden. "Aktiv" markierte Routen werden neu berechnet und/oder stehen nicht zur Verfügung.

• routing table = enthält die jeweils beste (metrikbezogen, also in diesem Fall die "kostengünstigste") Verbindung zu einem Ziel

DUAL wertet die von anderen Routern empfangenen Daten innerhalb der topology table aus und berechnet primären und redundanten Netzwerkpfad. Der Primäre Pfad ist normalerweise der Pfad mit den niedrigsten Kosten um das Ziel zu erreichen, der redundante Pfad der Pfad mit den zweitniedrigsten Kosten. Alle Pfade werden vorgehalten, aber nur einer dieser Pfade wird auch aktiv genutzt. Somit werden Schleifen automatisch vermieden.

Um Anfragen an ein bestimmtes Ziel über den Primären Pfad abzuwickeln trägt DUAL den Nachbarn auf dem primären Pfad als Gateway aller Anfragen auf das Ziel in die routing table ein. Dieser Router wird von Cisco als "successor" bezeichnet. In der EIGRP routing table hält DUAL zudem den Nachbarn der zweitbesten Verbindung an ein Ziel als sogenannter "feasible successor" vor. Fällt die Route zu dem als "successor" vorgesehenen Router aus, wird dieser "feasible successor" anstatt des "successors" in die routing table eingetragen.

[Bearbeiten] Beispiel

Legende:

+ = Router

- oder | = Verbindung

(X) = Kosten der Verbindung

     A    (2)    B    (1)    C
     + - - - - - + - - - - - +           
                 |           |
              (2)|           | (3)         
                 |           |
                 + - - - - - +
                 D    (1)    E

Ein Client in einem Netzwerk an Router E fragt beispielsweise einen Client in einem an Router A angeschlossen Netzwerk an. Dies bedeutet, das Router E eine Route zu Router A zur Verfügung stehen muss.

Diese Route wurde folgendermaßen berechnet:

Die direkten Nachbarn von E sind D und C.

DUAL fragt also die Reported Distance(RD) von C und D nach A ab. Dies produziert folgende Resultate:

Ziel: Router A

via D: RD(4)

via C: RD(3)

Die Route via C ist also, wenn DUAL nur die Distanz der Nachbarn in die Routingentscheidungen einbeziehen würde, die Günstigste. Im nächsten Schritt wird also die Distanz zwischen Nachbar und dem Router selbst noch mit in die Kalkulation einbezogen. Die Summe aus Reported Distance plus Distanz zum Nachbar wird als Feasible Distance (FD) festgelegt und für die Priorisierung der Routen als Grundlage verwendet:

Ziel: Router A

via D: RD(4), FD(5)

via C: RD(3), FD(6)

Somit stellt DUAL fest, das die Route via D die insgesamt kostengünstigste Route ist. Die Route via D wird also als "successor" markiert, mit passivem Status versehen und in die routing table zur Verwendung eingetragen. Die Route via C wird als "feasible successor" vorgehalten.

Ziel: Router A

via D: RD(4), FD(5) successor

via C: RD(3), FD(6) feasible successor