Distanzvektor-Routingprotokoll

Ein Distanzvektor-Routingprotokoll in Datennetzwerken ermittelt die optimale Route für Datenpakete anhand der Entfernung. Die Entfernung wird dabei durch die Anzahl der Router gemessen , die ein Paket passieren muss; ein Router entspricht einem Hop. Einige Distanzvektor-Protokolle berücksichtigen zusätzlich die Netzwerklatenz und andere Faktoren, die den Datenverkehr auf einer bestimmten Route beeinflussen. Um die beste Route durch ein Netzwerk zu bestimmen, tauschen Router, die ein Distanzvektor-Protokoll verwenden, Informationen untereinander aus, üblicherweise Routingtabellen , Hop-Zähler für Zielnetzwerke und gegebenenfalls weitere Verkehrsinformationen. Distanzvektor-Routingprotokolle erfordern außerdem, dass ein Router seine Nachbarn regelmäßig über Änderungen der Netzwerktopologie informiert .

Distanzvektor-Routingprotokolle verwenden den Bellman-Ford-Algorithmus zur Berechnung der optimalen Route. Eine andere Methode zur Berechnung der optimalen Route in einem Netzwerk basiert auf den Verbindungskosten und wird durch Link-State-Routingprotokolle implementiert .

Der Begriff Distanzvektor bezieht sich darauf, dass das Protokoll Vektoren ( Arrays ) von Distanzen zu anderen Knoten im Netzwerk verarbeitet. Der Distanzvektor-Algorithmus war der ursprüngliche Routing-Algorithmus des ARPANET und wurde mit dem Routing Information Protocol (RIP) in lokalen Netzwerken weiter verbreitet implementiert .

Distanzvektor-Routingprotokolle nutzen den Bellman-Ford-Algorithmus . In diesen Protokollen besitzt kein Router Informationen über die vollständige Netzwerktopologie . Er sendet seinen berechneten Distanzwert (DV) an andere Router und empfängt ähnliche Meldungen von diesen, sofern keine Änderungen im lokalen Netzwerk oder durch benachbarte Router vorgenommen werden. Mithilfe dieser Routing-Meldungen füllt jeder Router seine Routingtabelle. Im nächsten Meldungszyklus sendet ein Router aktualisierte Informationen aus seiner Routingtabelle. Dieser Prozess wird fortgesetzt, bis die Routingtabellen aller Router stabile Werte erreichen .

Einige dieser Protokolle haben den Nachteil einer langsamen Konvergenz.

Beispiele für Distanzvektor-Routingprotokolle:

• Routing Information Protocol (RIP)
• Routing Information Protocol Version 2 (RIPv2)
• Routing Information Protocol Next Generation (RIPng), eine Erweiterung von RIP Version 2 mit Unterstützung für IPv6
• Interior Gateway Routing Protocol (IGRP)
• Erweitertes Interior Gateway Routing Protocol (EIGRP)

Router, die das Distanzvektor-Protokoll verwenden, bestimmen die Entfernung zwischen sich und einem Ziel. Der optimale Datenweg durch ein Datennetzwerk wird anhand der Anzahl der Router (Hops) gemessen, die ein Paket durchlaufen muss, um sein Zielnetzwerk zu erreichen. Einige Distanzvektor-Protokolle berücksichtigen zusätzlich weitere Verkehrsinformationen wie die Netzwerklatenz . Um den optimalen Weg zu ermitteln, tauschen Router regelmäßig Informationen mit benachbarten Routern aus, üblicherweise ihre Routing-Tabelle , die Hop-Anzahl für ein Zielnetzwerk und gegebenenfalls weitere verkehrsbezogene Informationen. Router, die das Distanzvektor-Protokoll implementieren, verlassen sich ausschließlich auf die von anderen Routern bereitgestellten Informationen und analysieren nicht die Netzwerktopologie . ^{[ 1 ]}

Distanzvektorprotokolle aktualisieren die Routingtabellen von Routern und bestimmen die Route, über die ein Paket gesendet wird. Der nächste Hop besteht aus der Ausgangsschnittstelle des Routers und der IP-Adresse der Schnittstelle des empfangenden Routers. Die Distanz ist ein Maß für die Kosten, um einen bestimmten Knoten zu erreichen. Die kostengünstigste Route zwischen zwei Knoten ist die Route mit der geringsten Distanz.

Aktualisierungen erfolgen regelmäßig in einem Distanzvektor-Routingprotokoll. Dabei wird die Routingtabelle eines Routers ganz oder teilweise an alle seine Nachbarn gesendet, die für die Verwendung desselben Protokolls konfiguriert sind. Sobald ein Router diese Informationen erhalten hat, kann er seine eigene Routingtabelle entsprechend anpassen und seine Nachbarn darüber informieren. Dieser Prozess wird als „Routing durch Gerüchte“ bezeichnet, da Router auf die Informationen anderer Router angewiesen sind und deren Gültigkeit nicht überprüfen können. Es gibt verschiedene Funktionen, die zur Behebung von Instabilität und fehlerhaften Routinginformationen beitragen können.

Das älteste Routing-Protokoll und zugleich das älteste Distanzvektor-Protokoll ist Version 1 des Routing Information Protocol (RIPv1). RIPv1 wurde 1988 standardisiert. ^{[ 2 ]} Es ermittelt den kürzesten Pfad durch ein Netzwerk ausschließlich anhand der Hops, d. h. der Anzahl der Router, die zum Erreichen des Zielnetzwerks durchlaufen werden müssen. RIP ist ein Interior Gateway Protocol und kann daher in lokalen Netzwerken (LANs) auf internen oder Border-Routern eingesetzt werden. Router mit RIPv1-Implementierung tauschen ihre Routing-Tabellen mit benachbarten Routern aus, indem sie alle 30 Sekunden ein RIPv1-Paket an alle verbundenen Netzwerke senden . RIPv1 ist für große Netzwerke ungeeignet, da es die Anzahl der Hops auf 15 begrenzt. Diese Begrenzung wurde eingeführt, um Routing-Schleifen zu vermeiden, bedeutet aber auch, dass Netzwerke, die über mehr als 15 Router verbunden sind, nicht erreichbar sind. ^{[ 3 ]}

Das für Weitverkehrsnetze (WANs) entwickelte Distanzvektorprotokoll ist das Border Gateway Protocol (BGP). BGP ist ein externes Gateway-Protokoll und wird daher auf Border- und externen Routern im Internet implementiert . Es tauscht Informationen zwischen Routern über eine TCP-Sitzung ( Transmission Control Protocol ) aus. Router mit BGP-Implementierung ermitteln den kürzesten Pfad durch ein Netzwerk anhand verschiedener Faktoren, die nicht die Anzahl der Hops (Hops) betreffen. Administratoren können BGP so konfigurieren, dass bestimmte Routen bevorzugt oder vermieden werden. BGP wird von Internetdienstanbietern (ISPs) und Telekommunikationsunternehmen eingesetzt. ^{[ 4 ]}

Zu den Distanzvektor-Protokollen, die als Hybride bezeichnet werden, da sie Routing-Methoden verwenden, die mit Link-State-Routing-Protokollen assoziiert sind , zählt das proprietäre Enhanced Interior Gateway Routing Protocol (EIGRP). Es wurde in den 1980er Jahren von Cisco entwickelt und sollte im Vergleich zum Link-State-Routing-Protokoll Open Shortest Path First (OSPF) eine bessere Konvergenz und weniger Netzwerkverkehr zwischen Routern bieten. ^{[ 5 ]}

Ein weiteres Beispiel für ein Distanzvektor-Routingprotokoll ist Babel .

Der Bellman-Ford-Algorithmus verhindert keine Routing-Schleifen und leidet unter dem Count-to-Infinity-Problem . Dieses Problem besteht darin, dass B, wenn Router A meldet, dass ein Pfad existiert, nicht wissen kann, ob dieser Pfad über B selbst führt. Stellen Sie sich dazu ein Subnetz mit der Struktur A–B–C–D–E–F vor, dessen Metrik zwischen den Routern die Anzahl der Sprünge ist. Angenommen, Router A fällt aus. Im Vektoraktualisierungsprozess stellt B fest, dass die Route zu A (Distanz 1) nicht mehr existiert – B erhält jedoch keine Vektoraktualisierung von A. Das Problem ist, dass B auch eine Aktualisierung von C erhält, C aber noch nicht weiß, dass A nicht existiert. Daher meldet C B, dass A nur zwei Sprünge von C entfernt ist (C → B → A). Da B nicht weiß, dass der Pfad von C nach A über B selbst führt, aktualisiert es seine Tabelle mit dem neuen Wert „B → A = 2 + 1“. Später leitet B das Update an C weiter, und da A über B erreichbar ist (aus Sicht von C), beschließt C, seine Tabelle auf „C zu A = 3 + 1“ zu aktualisieren. Dies breitet sich langsam im Netzwerk aus, bis es unendlich wird (in diesem Fall korrigiert sich der Algorithmus aufgrund der Relaxationseigenschaft von Bellman-Ford selbst).

RIP verwendet die Split-Horizon- Methode mit Poison-Reverse-Verfahren, um die Wahrscheinlichkeit von Schleifenbildung zu verringern, und eine maximale Anzahl von Hops, um dem „Count-to-Infinite“-Problem entgegenzuwirken. Diese Maßnahmen verhindern die Bildung von Routing-Schleifen in einigen, aber nicht in allen Fällen. ^{[ 6 ]} Das Hinzufügen einer Haltezeit (Verweigerung von Routenaktualisierungen für einige Minuten nach einem Routenrückzug) verhindert die Schleifenbildung in nahezu allen Fällen, führt aber zu einer deutlichen Verlängerung der Konvergenzzeiten.

In jüngerer Zeit wurden eine Reihe schleifenfreier Distanzvektorprotokolle entwickelt – bekannte Beispiele sind EIGRP , DSDV und Babel . Diese vermeiden in allen Fällen Schleifenbildung, weisen jedoch eine höhere Komplexität auf, und ihre Verbreitung wurde durch den Erfolg von Link-State-Routingprotokollen wie OSPF verlangsamt .

In diesem Netzwerk haben wir 4 Router A, B, C und D:

Wir markieren den aktuellen Zeitpunkt (oder die aktuelle Iteration) des Algorithmus mit T und beginnen (zum Zeitpunkt 0, T=0) mit der Erstellung von Distanzmatrizen für jeden Router zu seinen direkten Nachbarn. Beim Aufbau der untenstehenden Routingtabellen wird der kürzeste Pfad grün und ein neuer kürzester Pfad gelb hervorgehoben. Graue Spalten kennzeichnen Knoten, die keine Nachbarn des aktuellen Knotens sind und daher in seiner Tabelle nicht als gültige Richtung berücksichtigt werden. Rot markiert ungültige Einträge in der Tabelle, da sie Distanzen von einem Knoten zu sich selbst oder über sich selbst angeben.

• G. Malkin (November 1998). RIP Version 2. Network Working Group. doi : 10.17487/RFC2453 . STD 53. RFC 2453 .Internetstandard 53. Ersetzt RFC  1723 und 1388. Aktualisiert durch RFC  4822 .
• „Ein Pfadfindungsalgorithmus für schleifenfreies Routing“, JJ Garcia-Luna-Aceves und S. Murthy, IEEE/ACM Transactions on Networking, Februar 1997
• „Erkennung ungültiger Routing-Ankündigungen im RIP-Protokoll“, D. Pei, D. Massey und L. Zhang, IEEE Global Communications Conference (Globecom), Dezember 2003

• Abschnitt „Link-State versus Distance Vector“, archiviert am 14.12.2010 in der Wayback Machine im Kapitel „Routing Basics“ im Cisco „Internetworking Technology Handbook“
• Abschnitt 5.2 „Routing-Algorithmen“ in Kapitel „5 DIE NETZWERKSCHICHT“ aus „Computernetzwerke“, 5. Auflage von Andrew S. Tanenbaum und David J. Wetherall