Simulation Spanning Tree/Dijkstra

Manuskript

In der Simulation wird in Anlehnung an den Bellman-Ford Algorithmus nachgebildet, wie jeder einzelne Knoten nur über den Austausch von Nachrichten (Protocol Data Untis, PDU) an die direkt verbundenen Nachbarn nach und nach Kenntnis über die Erreichbarkeit eines sog. Root-Knotens erhält. Das Simulationsergebnis gibt dann für jeden Knoten den sog. Next Hop auf dem kostengünstigsten Weg zur Root (Spanning Tree) an.
Wird die PDU so erweitert, dass jeder Knoten seinen aktuellen Kenntnisstand über die Erreichbarkeit anderer Knoten mit den damit verbundenen Kosten als Broadcast an die Nachbarn mitteilt, kann daraus in jedem Knoten der Next Hop auf dem günstigsten Weg zu einem beliebig anderen Knoten bestimmt werden.
Anstelle einer Warteschlange zur Bearbeitung der Knoten (wie z.B. beim Dijkstra-Algorithmus) soll die Auswahl, welcher Knoten in der Simulation PDUs an seine Nachbarn sendet, zufallsgesteuert erfolgen. Der nicht deterministische Algorithmus wird abgebrochen, wenn jeder Knoten eine (vorgebbare) Mindestanzahl PDUs gesendet hat. Bei einem zu klein gewählten Wert und größerer Anzahl Knoten, entspricht das Simulationsergebnis evtl. noch nicht dem stabilen Endzustand. Das Ergebnis konvergiert, wenn in der Lernphase jeder Knoten eine genügend hohe Anzahl PDUs von seinen Nachbarn erhält und die PDUs im weiteren Verlauf keine Veränderungen (updates) mehr aufzeigen.

Beispielgraph Beispielgraph Simulationsergebnis


Beispiel mit Schritt für Schritt - Ablauf (pdf): Die Reihenfolge der Knotenbearbeitung ist rein zufällig.


Minimum PDUs send per Node (0 ... 10, 0 for Default): 0