Unter Distance Vektor Routing versteht man das Versenden von Routing-Daten unter Routern. Ein jeder Router hat seine eigene Distanz-Tabelle in der er festhält, über welchen Router er eine Nachricht senden muss, die an einen bestimmten Endpunkt gelangen soll. Um diese Verbindungen möglichst optimal zu halten, müssen die Router untereinander kommunizieren, es könnte nämlich stets passieren, dass ein Router ausfällt, oder dass ein neuer hinzukommt. Eine solche Distanz-Tabelle hat beispielsweise folgende Form:

Dx         | Via
Dest.      | A | B | C | D |
-----------|---|---|---|---|
A          | 6 | 7 | 4 | 5 |
B          | 4 | 5 | 6 | 1 |
C          | 2 | 8 | 3 | 3 |
D          | 3 | 6 | 1 | 2 |

Dabei sind die jeweils besten Verbindungen in einer separaten Routing-Tabelle speziell aufgeführt. Dieses Beispiel zeigt die Distanz-Tabelle für den Router X, die Routing-Tabelle-Einträge sind fett hervorgehoben. Um beispielsweise eine Nachricht zum Knoten B zu schicken, bräuchte die Nachricht 6 Zeiteinheiten, wenn sie über den Router C geschickt werden würde. Sie wird aber über den Router D geschickt, weil dort die Kosten nur 1 betragen.

Der Algorithmus funktioniert nun nach einem sehr einfachen Prinzip. Immer wenn ein Router einen neuen Favorit zu irgend einer Destination hat, so meldet er dies seinen Nachbar-Routern. Diese aktualisieren ihre betroffenen Einträge und melden gegebenfalls auch neue Favoriten, usw.

Bekommt der obige Router beispielsweise die Information, dass der Router D nun eine neue, schnellere Verbindung mit Kosten 1 für die Destination A hat, so wird die Tabelle folgendermassen abgeändert:

Dx         | Via
Dest.      | A | B | C | D |
-----------|---|---|---|---|
A          | 6 | 7 | 4 | 3 |
B          | 4 | 5 | 6 | 1 |
C          | 2 | 8 | 3 | 3 |
D          | 3 | 6 | 1 | 2 |

Diese 3 berechnet sich dabei aus der Tatsache, dass die Verbindung von D nach A wie gesagt 1 ist und die Verbindung von X nach D (via D) = 2. Deshalb ergibt sich daraus 1 + 2 = 3.

Der Router wird nun ebenfalls ein Info-Päckchen an seine Nachbarn schicken, in dem Steht, dass der Router A nun mit Kosten 3 erreicht werden kann, wenn man über X routet.

Count to infinity

Der Algorithmus ist grundsätzlich korrekt, es gibt jedoch ein kleines Problem: Das Count-To-Infinity-Problem (Bis-Unendlich-Zählen). Dieses passiert, wenn der einzige Link zu einem Knoten (nennen wir ihn Z) ausfällt. Dann merkt nämlich der Router auf der anderen Seite (nennen wir ihn X), dass das Routen via Z nach Z unendlich lange dauert. Er korrigiert seine Distanz-Tabelle und findet heraus, dass ein anderer Nachbarknoten (nennen wir ihn Y) scheinbar eine nun schnellere Verbindung zu Z hat. Tatsächlich beschreibt dieser Eintrag jedoch die Verbindung X-Y-X-Z, also das routen nach Y hin und wieder zurück zu X und dann nach Z. Dies ist deshalb so, weil der Router Y ja keine Ahnung hat, dass die Verbindung X-Z nicht mehr existiert. Der Router X indes hat keine Ahnung, dass der Router Y dies noch nicht weiss und nimmt deshalb an, es sei eine funktionierende Verbindung.

X teilt also nun seinen Nachbarn mit, dass er eine neue schnellste Verbindung zu Knoten Z hat. Der Knoten Y bekommt dies Nachricht und korrigiert den Eintrag via X nach Z ebenfalls nach oben. Dann sendet er die Neuerung wieder aus, usw. Die Routing-Kosten werden langsam hochgezählt, immer hin und her.

Dies ist nicht nur dann ein Problem, wenn die Verbindung ganz ausfällt, auch wenn sie sich um einige Kostenpunkte erhöht, tritt dieses Problem auf, nur werden die Tabellen irgendwann die korrekten Einträge enthalten.