Diffusing Update Algorithm

Der Diffusing Update Algorithm (kurz DUAL) ist eine Komponente des ursprünglich 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 etc.), 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 "passiv" 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. Als "passiv" markierte Routen sind stabil und können zur Datenübermittlung genutzt werden. Als "aktiv" markierte Routen werden neu berechnet oder gerade bei einem Nachbarn angefragt.

• 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 Topologietabelle von EIGRP 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 angeschlossenen Netzwerk starten, bedeutet dies, dass Router E eine Route zu Router A zur Verfügung stellen 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 Route. 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 der Distanz zum Nachbarn 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 (PDF; 1,4 MB)