Routing mit dem
Distanzvektoralgorithmus
Dr. Carsten Mielke
1
Beispiel

Es existieren vier Router A-D.
Zwischen diesen gibt es vier direkte
Verbindungen mit folgenden Kosten
Zwischen Router
und Router
Kosten
A
B
3
A
C
23
B
C
2
C
D
5
2
Aufgabe

Erstellen Sie die vollständigen
Kostenmatrizen der Router A bis D





zu Beginn und
nach jedem vollständigen Austausch von
Datenpaketen dargestellt,
d.h. zu den Zeitpunkten T=0, 1, 2, 3
insgesamt 16 4x4 Matrizen
Dabei ist



der beste Pfad zu einem anderen Router grün
sowie ein neuer bester Pfad – der im nächsten
Schritt an die Nachbarn gesendet wird – gelb
hervorzuheben.
3
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
4
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
5
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
6
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
7
Schwachstelle

Count-To-Infinity-Effekt


Wir gehen dazu davon aus, dass sich der Link von C nach
D drastisch verschlechtert
Wir betrachten die Situation aus der Sicht von Router A






Router A empfängt 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.
Hierbei ist noch nicht berücksichtigt, dass auch dieser Pfad
über B bald teurer werden wird.
Dies geschieht jedoch nur stückweise, da eine indirekte Route
über C und D noch nicht neu berechnet wurde.
Dadurch ändert sich aber wieder der beste Pfad von A, was
gleich wieder B mitgeteilt wird.
Ergebnis: Die Pfadkosten werden langsam hoch gezählt
statt sprunghaft zu steigen. In Distanzvektor-Protokollen
gilt allgemein „bad news travel slow“.
8

Routing - Carsten Mielke