Rechnernetze (10) : Pfadermittlung : Globaler Link-State-Algorithmus

Für die Pfadermittlung sind zwei Verfahren gebräuchlich: ein dynamischer globaler Link-State-Algorithmus, welcher hier besprochen wird und ein dynamischer dezentraler Distanzvektor-Algorithmus.

Globaler Link-State-Algorithmus

Voraussetzung für den Algorithmus ist, dass alle Knoten alle Informationen über die Netzwerktopologie und die Verbindungskosten vorliegen haben. Dies wird in der Praxis dadurch erreicht, dass jeder Knoten die Informationen über die Kosten der an ihn angeschlossenen Verbindungen in sogenannten Link-State-Broadcast-Nachrichten an alle anderen Knoten verschickt.
Wenn alle Knoten alle ihre Link-State-Broadcast-Nachrichten verschickt haben, dann hat jeder Knoten die komplette Information über die Netzwerktopologie und die Verbindungskosten vorliegen. Damit kann nun jeder Knoten die billigsten Pfade zu allen anderen Knoten berechnen.

Dijkstras iterativer Algorithmus [1] berechnet den billigsten Pfad von einem gegebenen Knoten (der Quelle Q) zu allen anderen Knoten im Netzwerk. Nach der k-ten Iteration wurden die billigsten Pfade zu k Zielknoten berechnet. Diese k Pfade haben die k billigsten Kosten in der Menge aller billigsten Pfade zu
den k Zielknoten.

Berechnung des billigsten Pfades mit Dijkstras Algorithmus

Für folgendes Beispiel gilt:

• c(i,j) >= 0 bezeichnet die Kosten der direkten Verbindung von Knoten i zu Knoten j. Falls keine direkte Verbindung existiert, dann ist c(i,j) = unendlich

• d_i bezeichnet die Kosten des Pfades vom Quellknoten Q zum Zielknoten i, der in dieser Iteration die billigsten Kosten hat

• P_i bezeichnet den Vorgängerknoten (einen Nachbarn von Knoten i) auf dem gegenwärtig billigsten Pfad vom Quellknoten zum Zielknoten i.

• S bezeichnet die Menge der Knoten, bei denen die billigsten Pfade vom Quellknoten bereits bekannt sind.

Der Algorithmus besteht aus einer Initialisierung und der Iteration. Nach der Beendigung des Algorithmus sind die billigsten Pfade vom Quellknoten zu allen anderen Knoten bekannt.

• Der Initialisierungsvorgang

S = {} /*Q ist der Quellknoten, an dem die Berechnung ausgeführt wird */
Für alle Knoten i des Netzwerkes
begin
    if i direkter Nachbar von Q 
    then d_i = c(Q,i) : P_i = Q;
    else d_i = unendlich;
end

• Die Iteration

Wiederhole solange, bis alle Knoten des Netzwerkes in S sind
begin
    Finde ein i welches sich nicht in S befindet mit d_i=min{d_j}
    Füge i zu der Menge S hinzu
    Update d_i für alle direkten Nachbarn von i
        if d_i + c(i,j) < d
        then d_j = d_i + c(i,j) : P_j = i;
        /* die neuen Kosten von j sind entweder die alten Kosten oder die bekannten billigsten Kosten nach i plus den Kosten von i nach j */
end

Wir betrachten nun das Netzwerk in folgender Abbildung und berechnen die billigsten Pfade vom Quellknoten A zu allen möglichen Zielknoten. Die Ergebnisse für jeden Iterationsschritt sind in der Tabelle dargestellt.

Die Netzwerktopologie

Tabelle mit den kürzesten Pfaden

Bei Terminierung des Algorithmus liegt für jeden Knoten sein Vorgänger auf dem billigsten Pfad vom Quellknoten vor. Für jeden Vorgänger kennen wir außerdem dessen Vorgänger. So können wir die gesamten Pfade vom Quellknoten zu allen Zielknoten rekonstruieren.

Quelle
[1] https://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Melissa.pdf, p. 4ff. [letzter Zugriff : 23.12.2019, 17:15]