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]

[Abbildungsverzeichnis] [Literaturverzeichnis]