Distanzvektoralgorithmus

Grundidee und Bedeutung

Der Distanzvektoralgorithmus, auch Distanzvektor-Routing oder Distance Vector Routing genannt, ist ein dynamisches Routingverfahren für paketvermittelte Netzwerke. Router verwenden ihn, um selbstständig geeignete Wege zu anderen Routern beziehungsweise Netzwerken zu bestimmen. Das Verfahren basiert intern auf dem Bellman-Ford-Algorithmus.

Das Grundprinzip lautet: „Teile deinen Nachbarn mit, wie du die Welt siehst.“ Jeder Router kennt zunächst nur die Kosten zu seinen direkten Nachbarn. Durch den Austausch dieser Informationen kann er schrittweise auch entfernte Ziele erreichen. Distanzvektorprotokolle sind selbstorganisierend, vergleichsweise einfach zu implementieren und benötigen nahezu keine Wartung. In IP-Netzen wird das Verfahren beispielsweise durch RIP und IGRP umgesetzt. Eine andere grundlegende Klasse von Routingprotokollen sind Link-State-Protokolle.

Ablauf und Kostenbewertung

Der Router arbeitet in mehreren wiederkehrenden Schritten:

• Er erstellt eine Kostenmatrix. Sie enthält zunächst nur die bekannten Kosten zu direkten Nachbarn und die Information, über welchen Nachbarn ein Ziel erreichbar ist.
• Er erstellt eine Aufstellung der besten bekannten Wege zu anderen Routern und sendet diese an alle direkten Nachbarn.
• Er empfängt die Aufstellungen der Nachbarn und trägt die darin enthaltenen Informationen in seine eigene Kostenmatrix ein.
• Ändern sich dadurch die minimalen Kosten zu einem Ziel, verbreitet er die neuen besten Wege erneut. Gibt es keine Änderung, wartet er auf weitere Informationen.

Die Kosten einer Route werden als Metrik bezeichnet. Jedes Routingprotokoll kann eine andere Metrik verwenden. RIP nutzt als einzigen Kostenwert die Anzahl der Router bis zum Ziel, den sogenannten Hop-Count. Die Bandbreite einer Verbindung wird bei RIP daher nicht berücksichtigt.

Beispiel mit vier Routern

Im Beispiel gibt es die Router A, B, C und D mit Punkt-zu-Punkt-Verbindungen. Die Kostenmatrizen werden zu den Zeitpunkten T=0, T=1, T=2 und T=3 betrachtet. Für jedes Ziel wird der jeweils günstigste bekannte Pfad ausgewählt. Nicht betrachtete Felder stehen für die Distanz eines Routers zu sich selbst oder für nicht mögliche beziehungsweise nicht gepflegte Kombinationen.

Router A entwickelt seine Routinginformationen folgendermaßen:

• T=0: Die initiale Kostenmatrix enthält nur die direkten Nachbarn B und C. A kennt B mit Kosten 3 und C mit Kosten 23. Diese beiden besten Pfade werden an die direkten Nachbarn gesendet.
• T=1: A erhält Informationen von B und C. Dadurch kennt A nun auch Wege zu D und zusätzliche Wege zu B und C. Für C und D entstehen neue beste Pfade, die A im nächsten Austausch weitergibt.
• T=2: A erfährt von B, dass B D günstiger erreichen kann. A übernimmt den neuen Weg zu D mit Kosten 10 und verbreitet diese Änderung erneut.
• T=3: Es treffen keine Informationen mehr ein, die die besten Pfade verändern. Deshalb sendet A keine neuen Informationen. Auch die anderen Router haben keine Änderungen mehr; der Algorithmus terminiert.

Das Beispiel zeigt, dass sich die vollständigen Routinginformationen schrittweise durch das Netzwerk ausbreiten. Jeder Router verbessert seine eigene Sicht auf das Netzwerk anhand der Meldungen seiner Nachbarn.

Count-To-Infinity und Gegenmaßnahmen

Ein wichtiges Problem ist das Zählen bis Unendlich, der sogenannte Count-To-Infinity-Effekt. Er entsteht, wenn Router nach einer Verschlechterung oder einem Ausfall eines Links veraltete, indirekte Wege für gültig halten und sich gegenseitig immer höhere Kosten mitteilen.

Im Beispiel verschlechtert sich die Verbindung von C nach D stark. Aus Sicht von A geschieht Folgendes:

• C meldet A, dass D über C nur noch sehr schlecht erreichbar ist. A behält zunächst seinen besten Weg über B bei.
• Danach meldet auch B, dass D über B nur noch zu Kosten 13 erreichbar sei. Diese Kosten werden als „13 = 3 + 10 = 3 + 3 + 2 + 5“ angegeben. B verwendet dabei noch eine indirekte, tatsächlich problematische Route über A: B–A–B–C–D. A hatte zuvor mitgeteilt, D zu Kosten 10 erreichen zu können.
• Weil B D nun nur noch zu Kosten 13 erreicht, erhöht A seine eigenen Kosten zu D auf 16.
• A teilt die Änderung wieder B mit. Die Kosten steigen dadurch schrittweise an, anstatt sofort auf einen eindeutig unbrauchbaren Wert zu springen.

Bei direkten Schleifen zwischen zwei Routern kann Split Horizon helfen. Dabei darf eine Pfadinformation nicht über dasselbe Interface veröffentlicht werden, über das sie empfangen wurde. Bei längeren Schleifen ist die Lösung schwieriger, weil sich Erhöhungen der Kosten in Distanzvektorprotokollen nur langsam verbreiten. Deshalb werden zusätzlich Poison Reverse und Triggered Updates eingesetzt.

Eine verwandte Abwandlung ist der Distance-Path-Algorithmus, den beispielsweise BGP implementiert. Er speichert neben dem nächsten Hop auch den gesamten restlichen Pfad zum Zielrouter. Dadurch lassen sich Schleifen leichter erkennen und neben der günstigsten Route auch andere Kriterien, etwa firmenpolitische Maßgaben, berücksichtigen.

Triggered Updates und RIP-Versionen

Normalerweise sendet ein Router die ihm bekannten Routen in einem festen Zeitintervall an seine Nachbarn. Bei RIP geschieht dies standardmäßig alle 30 Sekunden. Bei aktivierten Triggered Updates sendet der Router eine Teilinformation sofort, sobald sich die Metrik einer von ihm verwalteten Route ändert, beispielsweise aufgrund einer Meldung eines Nachbarn.

Triggered Updates sollen zusammen mit Split Horizon Routingschleifen und den Count-To-Infinity-Effekt begrenzen. Durch die schnelle Weitergabe geänderter, nur teilweise übertragener Routeninformationen sollen veraltete Informationen nicht lange im Netzwerk verbleiben.

Für IPv4 gibt es zwei RIP-Versionen: RIPv1 und RIPv2. RIPv1 unterstützt keine Subnetzmasken. Für IPv6 wurde RIP angepasst und unter der Bezeichnung RIPng veröffentlicht.