Allgemein

Routingprotokolle verwenden verschiedene Algorithmen um für ein Paket den besten Pfad zum Ziel auszuwählen.

Beispiele sind der Diffusion Update Algorithmus1)der von EIGRP verwendet wird, der Bellmann Ford Algorithmus2) oder der Dijkstra Algorithmus Bei den letzten beiden handelt es sich um SPF (Shortest Path First) Algorithmen.
Da IS-IS den Dijkstra Algorithmus verwendet wird im weiteren Verlauf dieser Ausarbeitung nur mehr auf diesen eingegangen.

Dijkstra Algorithmus

Allgemeines

Nette Geschichte zur Entstehung des Dijkstra Algorithmus3)

Der Dijkstra Algorithmus gehört zur Klasse der Greedy Algorithmen4), eine Erweiterung des Dijkstra Algorithmus findet sich im A*-Algorithmus5) welcher um eine Heuristische Suche erweitert wurde.

Um den Dijkstra Algorithmus durchführen zu können muss jeder Knotenpunkt (Router) die Topologie des Netzwerkes kennen, diese wird für gewöhnlich durch Routingupdates aufgebaut und im Arbeitsspeicher (RAM) gespeichert.
Die Topologietabelle ist im gesamten Netzwerksegment identisch, dadurch kann jeder Knotenpunkt eigenständig den optimalen Pfad zu einem Ziel berechnen.
Eine Verbindung zwischen 2 Knotenpunkten verursacht Kosten, diese Kosten werden durch die Metrik angegeben (bei OSPF6) wird z.B. die Bandbreite verwendet).
Sobald eine komplette Topologietabelle aufgebaut ist (das Netzwerk ist Konvergent), ist es möglich den kürzesten Weg zu den einzelnen Zielen zu berechnen und die neu berechneten Routen in die Routing-Tabelle (liegt wiederum im RAM) aufzunehmen, ab diesem Zeitpunkt ist der Router einsatzbereit (er ist im Stande Pakete an das Ziel weiterzuleiten).

Arbeitsweise des Dijkstra Algorithmus:

Bilder von: http://www.steve.gb.com/science/internet.html

Wir gehen von einem kleinen Netzwerk mit 4 Knotenpunkten (A,B,C,D)aus:

http://www.steve.gb.com/images/science/dijkstra0.jpg7)

Jeder dieser Knotenpunkte kennt die gesamte Netzwerktopologie (inkl. den Pfadkosten) und hat somit die Information zur Berechnung der idealen Pfade zum Ziel.
Zur Arbeitsdarstellung von Dijkstra nehmen wir als Startpunkt den Knoten A und suchen den idealen Pfad zum Knoten D.

http://www.steve.gb.com/images/science/dijkstra1.jpg8)

Knoten A hat 2 Nachbarsknoten (B und C), die Pfade und Kosten (zu B sind die Kosten 2 und zu C sind die Kosten 1) werden temporär gespeichert (grün dargestellt).
Da die Kosten zu C geringer sind wird dieser Pfad permanent gespeichert (rot dargestellt):

http://www.steve.gb.com/images/science/dijkstra2.jpg9)

Nun werden die Knoten, die am Knotenpunkt C angeschlossen sind, untersucht.
Zu A sind die Kosten 1, dadurch dass der Pfad zu A bereits bekannt ist (Permanent gespeichert) wird dieser Pfad verworfen, die Kosten von C zu B sind 1, da die Kosten von A zu B (direkter Pfad) allerdings auch 2 sind können wir diesen Pfad ebenso ignorieren. Der einzige neue Pfad zu D mit Kosten 6 wird temporär gespeichert (grün dargestellt).

http://www.steve.gb.com/images/science/dijkstra3.jpg10)

Es wurde nun der kürzeste Weg zu B gefunden (direkte Verbindung von A zu B), diese Verbindung wird nun permanent gespeichert (rot dargestellt), nun untersuchen wir den Knotenpunkt B genauer.
Pfade mit gleichen oder höheren Kosten werden verworfen! Wir erkennen nun dass der Pfad A⇒B⇒D mit den Kosten 5 besser ist als der Pfad A⇒C⇒D mit Kosten 6, somit wird der neue Pfad temporär gespeichert (grün dargestellt) und der Pfad über C verworfen.

http://www.steve.gb.com/images/science/dijkstra4.jpg11)

Da wir nun bereits am Ziel angelangt sind wird nun B⇒D als permanent gespeichert (rot dargestellt) ⇒ der kürzeste Weg von A zu D ist die Summe aller permanenten Verbindungen (A⇒B⇒D).
Der SPF Algorithmus ist somit für dieses Ziel abgeschlossen!!

 
spf_algo.txt · Last modified: 2009/09/13 14:37 (external edit)
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki