Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing-Algorithmus der nach dem Prinzip "Teile deinen Nachbarn mit, wie du die Welt siehst" funktioniert und intern auf dem Bellman-Ford-Algorithmus basiert. Er wird von Routern in paketvermittelten Netzwerken eingesetzt und ist im Internet z. B. als RIP und IGRP implementiert. Distance-Vector Protokolle sind selbstorganisierend, vergleichsweise einfach zu implementieren und funktionieren nahezu ohne jede Wartung. Zu den Nachteilen gegenüber Link-State Protokollen zählen die schlechten Konvergenzeigenschaften und die mangelhafte Skalierbarkeit.

Das prinzipielle Vorgehen eines Distance-Vector-Protokolls ist Folgendes:

1. Erzeuge eine Kostenmatrix, welche Router über welche Nachbarn und zu welchen Kosten erreichbar sind. - Diese Matrix enthält anfangs nur die (bekannten) Kosten zu direkten Nachbarn.
2. Erzeuge eine Aufstellung mit Informationen, welche Router wir zu welchen Kosten am besten erreichen können und schicke sie an alle Nachbarn.
3. Warte auf Aufstellungen dieser Art von anderen Routern, rechne diese dann in die eigene Kostenmatrix ein.
4. Ändern sich dadurch die minimalen Kosten, zu denen wir einen Router erreichen können: fahre mit Schritt 2 fort, sonst mit Schritt 3.

Beispiel

---

Es existieren vier Router A-D und zwischen ihnen folgende Links:

(A)....3....(B) : . : . 23 2 : . : . (C)....5....(D)

Im folgenden sind die Kostenmatrizen der Router zu Beginn und nach jedem vollständigen Austausch von Datenpaketen dargestellt. Dabei ist der beste Pfad zu einem anderen Router jeweils grün, ein neuer bester Pfad - der im nächsten Schritt an die Nachbarn gesendet wird - gelb hinterlegt.

T=0

von A	via A	via B	via C	via D
zu A
zu B		3
zu C			23
zu D

von B	via A	via B	via C	via D
zu A	3
zu B
zu C			2
zu D

von C	via A	via B	via C	via D
zu A	23
zu B		2
zu C
zu D				5

von D	via A	via B	via C	via D
zu A
zu B
zu C			5
zu D

T=1

von A	via A	via B	via C	via D
zu A
zu B		3	25
zu C		5	23
zu D			28

von B	via A	via B	via C	via D
zu A	3		25
zu B
zu C	26		2
zu D			7

von C	via A	via B	via C	via D
zu A	23	5
zu B	26	2
zu C
zu D				5

von D	via A	via B	via C	via D
zu A			28
zu B			7
zu C			5
zu D

T=2

von A	via A	via B	via C	via D
zu A
zu B		3	25
zu C		5	23
zu D		10	28

von B	via A	via B	via C	via D
zu A	3		7
zu B
zu C	8		2
zu D	31		7

von C	via A	via B	via C	via D
zu A	23	5		33
zu B	26	2		12
zu C
zu D	51	9		5

von D	via A	via B	via C	via D
zu A			10
zu B			7
zu C			5
zu D

T=3

von A	via A	via B	via C	via D
zu A
zu B		3	25
zu C		5	23
zu D		10	28

von B	via A	via B	via C	via D
zu A	3		7
zu B
zu C	8		2
zu D	13		7

von C	via A	via B	via C	via D
zu A	23	5		15
zu B	26	2		12
zu C
zu D	33	9		5

von D	via A	via B	via C	via D
zu A			10
zu B			7
zu C			5
zu D

Erläuterung der Vorgänge im Router A:

• T=0: Wir erzeugen die initiale Kostenmatrix. Sie enthält nur unsere direkten Nachbarn B und C mit den uns bekannten Kosten. Wir schicken daraufhin unsere neuen besten Pfade (B mit Kosten 3, C mit Kosten 23) an unsere direkten Nachbarn
• T=1: Wir haben von den Routern B und C Datenpakete erhalten und wissen jetzt, zu welchen Kosten wir D und wie wir C und B jeweils auch erreichen können. Im Fall der Zielrouter C und D ist das sogar ein neuer bester Pfad, den wir im nächsten Schritt an unsere Nachbarn übertragen werden
• T=2: Wir haben von Router B ein Datenpaket erhalten und wissen jetzt, dass B den Router D günstiger erreichen kann. Wir tragen die Kosten in unsere Matrix ein und werden diesen neuen besten Pfad wieder an unsere Nachbarn verbreiten.
• T=3: Wir haben keine neuen Informationen mehr empfangen; unsere besten Pfade haben sich nicht geändert und wir senden keine neuen Informationen an unsere Nachbarn. Denen geht es genauso - der Algorithmus terminiert.

Probleme

---

Ein Problem des Distance-Vector-Algorithmus, der sogenannte Count-To-Infinity-Effekt, lässt sich an diesem Beispiel auch zeigen. Wir gehen davon aus, dass sich der Link von C nach D drastisch verschlechtert und betrachten die Situation aus der Sicht von Router A:

• Wir empfangen von C die Meldung, dass D über ihn nur noch sehr schlecht zu erreichen ist. Das ändert jedoch nichts an unserem besten Pfad, der ja über B führt.
• Bald bekommen wir aber auch von B die Meldung, dass D über ihn nur noch sehr schlecht zu erreichen sei - die Pfadkosten seien auf 13(!) angestiegen. Dass die Kosten nicht deutlich höher angesetzt wurden liegt daran, dass B ja noch eine indirekte Route kannte, die zu D führt: die Route B-A-B-C-D. Und A gab ja nach bestem Wissen an, er könne D zu den Kosten 10 erreichen.
• Nun haben sich aber unsere Pfadkosten zu D geändert. Weil B den Router D nur noch zu Kosten von 13 erreichen kann, können auch wir D nur noch zu Kosten von 16 erreichen.
• Dadurch ändert sich aber wieder unser bester Pfad, was wir gleich wieder B mitteilen - die Pfadkosten werden langsam hochgezählt statt sprunghaft zu steigen.

Der Count-to-Infinity-Effekt lässt sich durch Einsatz des Split-Horizon-Verfahrens relativ leicht vermeiden: Eine Pfadinformation darf nicht über das selbe Inferface veröffentlicht werden, worüber sie empfangen wurde.

Im Fall von längeren Schleifen ist eine Lösung des Problems nicht mehr trivial. In Distance-Vector-Protokollen gilt allgemein bad news travel slowly. Um auch diesem Problem Herr zu werden, werden das Poisoned-Reverse-Verfahren und so genannte Triggered Updates verwendet: Findet ein Router heraus, dass ein Nachbar nur noch schwer oder gar nicht mehr erreichbar ist, veröffentlicht er diese Tatsache sofort aktiv im Netz.

In einer Abwandlung des Distance-Vector-Algorithmus, dem sogenannten Distance-Path-Algorithmus den z. B. BGP implementiert, ließe sich das Problem von Schleifen leichter lösen. Dieser Algorithmus speichert neben dem nächsten Hop auch noch den gesamten restlichen Pfad zum Zielrouter. So lassen sich neben dem Kriterium "günstigste Route" auch leicht andere Kriterien, z. B. firmenpolitische Maßgaben, umsetzen.

RIP-Versionen

---

Für IPv4 liegen zwei Versionen von RIP vor: RIPv1 und RIPv2. In RIPv1 sind keine Subnetzmasken implementiert.

Für IPv6 wurde RIP angepasst und unter der Bezeichnung RIPng veröffentlicht.

Links

---

RIPv1: RFC1058

RIPv2: RFC2453

RIPng: RFC2080

Algorithmus

Bellman-Ford algorithm