- Count-To-Infinity
-
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. Distanzvektorprotokolle 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.
Inhaltsverzeichnis
Prinzip
Das prinzipielle Vorgehen eines Distanzvektorprotokolls:
- 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.
- Erzeuge eine Aufstellung mit Informationen, welche Router wir zu welchen Kosten am besten erreichen können und schicke sie an alle Nachbarn.
- Warte auf Aufstellungen dieser Art von anderen Routern, rechne diese dann in die eigene Kostenmatrix ein.
- Ä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:
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 88 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 Distanzvektoralgorithmus, 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 bei direkten Schleifen zwischen zwei Routern durch Einsatz des Split-Horizon-Verfahrens relativ leicht vermeiden: Eine Pfadinformation darf nicht über dasselbe Interface veröffentlicht werden, worüber sie empfangen wurde.
Im Fall von längeren Schleifen ist eine Lösung des Problems nicht mehr trivial. In Distanzvektorprotokollen 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 Distanzvektoralgorithmus, 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.
Weblinks
Wikimedia Foundation.
