Diffusing Update Algorithm

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


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Diffusing Update Algorithm — Saltar a navegación, búsqueda DUAL (por sus siglas en inglés Diffusing Update Algorithm) es un algoritmo para la actualización de rutas usado por el protocolo de enrutamiento EIGRP, gracias al cual se logra su excepcional y rápida convergencia de …   Wikipedia Español

  • Diffusing update algorithm — DUAL, the Diffusing Update ALgorithm, is the algorithm used by Cisco s EIGRP routing protocol to ensure that a given route is recalculated globally whenever it might cause a routing loop. According to Cisco, the full name of the algorithm is DUAL …   Wikipedia

  • Enhanced Interior Gateway Routing Protocol — (EIGRP) is a Cisco proprietary routing protocol loosely based on their original IGRP. EIGRP is an advanced distance vector routing protocol, with optimizations to minimize both the routing instability incurred after topology changes, as well as… …   Wikipedia

  • Abreviations en informatique D — Abréviations en informatique D DAC (et DACL) : Discretionary access control (List), Contrôle d accès discrétionnaire, contrôle d accès personnalisé à une ressource (fichier ou autre) DADS (et DADS U) : En France, Déclaration Automatisée …   Wikipédia en Français

  • Abréviations En Informatique D — DAC (et DACL) : Discretionary access control (List), Contrôle d accès discrétionnaire, contrôle d accès personnalisé à une ressource (fichier ou autre) DADS (et DADS U) : En France, Déclaration Automatisée des Données Sociales Unifiée… …   Wikipédia en Français

  • Abréviations en informatique D — DAC (et DACL) : Discretionary access control (List), Contrôle d accès discrétionnaire, contrôle d accès personnalisé à une ressource (fichier ou autre) DADS (et DADS U) : En France, Déclaration Automatisée des Données Sociales Unifiée… …   Wikipédia en Français

  • Abréviations en informatique d — DAC (et DACL) : Discretionary access control (List), Contrôle d accès discrétionnaire, contrôle d accès personnalisé à une ressource (fichier ou autre) DADS (et DADS U) : En France, Déclaration Automatisée des Données Sociales Unifiée… …   Wikipédia en Français

  • EIGRP — Das Enhanced Interior Gateway Routing Protocol (EIGRP) ist ein 1994 von Cisco veröffentlichtes proprietäres Routing Protokoll. Bei EIGRP handelt es sich um eine verbesserte Version des früheren IGRP, zu welchem weiterhin Kompatibilität besteht.… …   Deutsch Wikipedia

  • Dual — may refer to: Dual (mathematics), a notion of paired concepts that mirror one another Dual (category theory), a formalization of mathematical duality . . . see more cases in Category:Duality theories Dual (grammatical number), a… …   Wikipedia

  • Amorphous computing — refers to computational systems that use very large numbers of identical, parallel processors each having limited computational ability and local interactions. The term Amorphous Computing was coined at MIT in 1996 in a paper entitled [http://www …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”