Differences

This shows you the differences between two versions of the page.

spf_algo [2009/09/13 14:37] (current)
Line 1: Line 1:
 +======Allgemein======
 +
 +Routingprotokolle verwenden verschiedene Algorithmen um für ein Paket den besten Pfad zum Ziel auszuwählen. \\
 +
 +Beispiele sind der __Diffusion Update Algorithmus__((http://de.wikipedia.org/wiki/Diffusing_Update_Algorithm))der von EIGRP verwendet wird, der __Bellmann Ford Algorithmus__((http://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus)) 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 Algorithmus((http://www.manderby.com/mandalex/d/dijkstra.php))
 +
 +Der Dijkstra Algorithmus gehört zur Klasse der __Greedy Algorithmen__((http://de.wikipedia.org/wiki/Greedy-Algorithmus)), eine Erweiterung des Dijkstra Algorithmus findet sich im __A*-Algorithmus__((http://de.wikipedia.org/wiki/A%2A-Algorithmus)) 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 OSPF((http://de.wikipedia.org/wiki/OSPF)) 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:
 +
 +{{dijkstra0.jpg|http://www.steve.gb.com/images/science/dijkstra0.jpg}}((http://www.steve.gb.com/images/science/dijkstra0.jpg))
 +
 +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.
 +
 +{{dijkstra1.jpg|http://www.steve.gb.com/images/science/dijkstra1.jpg}}((http://www.steve.gb.com/images/science/dijkstra1.jpg))
 +
 +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):
 +
 +{{dijkstra2.jpg|http://www.steve.gb.com/images/science/dijkstra2.jpg}}((http://www.steve.gb.com/images/science/dijkstra2.jpg))
 +
 +
 +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).
 +
 +{{dijkstra3.jpg|http://www.steve.gb.com/images/science/dijkstra3.jpg}}((http://www.steve.gb.com/images/science/dijkstra3.jpg))
 +
 +
 +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.
 +
 +{{dijkstra4.jpg|http://www.steve.gb.com/images/science/dijkstra4.jpg}}((http://www.steve.gb.com/images/science/dijkstra4.jpg))
 +
 +
 +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