Anhang A - Kürzeste-Wege-Algorithmen
von Bellman/Ford/Fulkerson
Routing Protokolle versuchen, Netzwerk-Leitwege zu berechnen, die dem Kürzeste-Wege-Algorithmus folgen.
Das Berechnen der kürzesten Wege ist ein sehr bekanntes mathematisches Problem mit Anwendungsbereichen, die weit über Computernetzwerke hinausgehen.
Die Distance Vector Routing Protokolle basieren auf dem Bellmann-Ford Algorithmus, der eine verteilte Version des Kürzeste-Wege-Algorithmus darstellt.
Zuerst wird die zentrale Version beschrieben:
Folgende Schritte müssen nun abgearbeitet werden:
1. Initialisiere D[i,j] so, daß D[i,j] = 0 falls i = j, sonst sei D[i,j] = Infinity-Wert
2. Für alle Verbindungen l und alle Zielrechner k setze man i = L[l].s, j = L[l].d und berechne L[l].m + D[j,k].
3. Wenn d kleiner als D[i,k], führe aus D[i,k] = d; H[i,k] = l
4. Wenn mindestens ein D[i,k] verändert wurde, wiederhole Schritt 2. Andernfalls ist die Berechnung beendet.
In der zentralisierten Version berechnet
man alle Leitweg-tabellen zentral für das ganze Netzwerk,
in der verteilten Version des Algorithmus kümmert sich
jeder Rechner nur um einen Teil der Daten: Die Verbindungen, die
bei ihm starten (die Spalten D[i,*] und H[i,*] der Entfernungs-
und der Routing-Matrix). Die Spalte D[i,*] ist ein Entfernungsvektor,
der an jeden Nachbarrechner bei einer Veränderung übergeben
wird. [Hui95, S.78f]
[Anfang] [Inhaltsverzeichnis] [Weiter]