Diffusing Update Algorithm

Der Diffusing Update Algorithm (kurz DUAL) ist eine Komponente des proprietären Routing-Protokolls EIGRP der Firma Cisco. 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.

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 Schnittstellen an alle Router eines autonomen Systems versendet, werden bei EIGRP sogenannte "Nachbarschaftsbeziehungen" 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:

• Nachbartabelle = enthält Informationen über alle anderen direkt verbundenen Router. Für jedes Protokoll (IP,IPX...) das EIGRP unterstützt existiert eine eigene Nachbartabelle. 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, dass die Route nicht mehr zur Verfügung steht und als "aktiv" markiert. (Siehe unten)
• Topologietabelle = enthält die Informationen über die Kosten jeder möglichen Verbindungen zu jedem Ziel innerhalb des autonomen Systems. Innerhalb der Topologietabelle werden mittels dieser Informationen die primäre und sekundäre Route zu einem Ziel festgelegt. Unter anderem enthält die Topologietabelle folgende Einträge pro Ziel:

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

RD (Reported Distance): 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.

Routenstatus: 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.

• Routingtabelle = 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 Topologietabelle aus und berechnet den 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 Routingtabelle ein. Dieser Router wird von Cisco als "successor" bezeichnet. In der EIGRP Topologietabelle 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 Routingtabelle eingetragen. Dazu muss die RD des "feasible successor" kleiner als die FD des "successors" sein. Ist das nicht der Fall, wird ein möglicher Successor mit Hilfe eines Query-Prozesses gesucht. Dieses Verhalten, diese Bedingungen dienen der Schleifenvermeidung.

Beispiel

Legende:

+ = Router

- oder | = Verbindung

(X) = Kosten der Verbindung

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

Möchte nun ein Client in einem Netzwerk an Router E eine Kommunikation mit einem Client in einem an Router A angeschlossen Netzwerk starten bedeutet dies, dass 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 zusätzlich 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, dass 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 Routingtabelle 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

Literatur

• J.J. Garcia-Lunes-Aceves: Loop-Free Routing Using Diffusing Computations