| | |
| Titel: | Routing im Internet. | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
2. Routing-Algorithmen in der Theorie
Routing-Algorithmen entscheiden, in welche Richtung Daten weitergeleitet werden. Dabei müssen sie zusätzlich zu dieser Grundfunktion die Routing-Tabelle, also die Grundlage für die Entscheidungsbildung, ständig aktualisieren.2.1 Anforderungen und Eigenschaften
Im Idealfall sind Routing-Algorithmen einfach, fair, optimal, stabil usw. Am Beispiel des Internets sieht man recht leicht, wie wichtig Stabilität ist. Über Jahre hinweg werden andauernd neue Netzwerke angehängt und zusätzlich fallen tausende Rechner aus. Trotzdem ist das Internet für fast alle Teilnehmer fast immer verfügbar.Bei der Optimalität gibt es schon mehr Schwierigkeiten. Man weiß ja nicht einmal, was überhaupt optimal ist. Ist es besser die Anzahl der Knoten möglichst gering zu halten, oder sollte man lieber versuchen die zurückgelegte Entfernung zu minimieren.
Bevor der jeweilige Netzwerkbetreiber letztendlich festlegt, was er als optimal betrachten will, sollte er sich noch Gedanken über die Fairness machen. Versucht er z.B. in Abb. 2.1.1 einen möglichst großen Datendurchsatz zu erreichen wird eventuell A von A' abgeschnitten. Das ist natürlich nicht fair.
Oft wird unter anderem deshalb die Minimierung der Knotenanzahl auf einem Weg als optimal gewählt
Abb. 2.1.1 Fairness - Prinzip
2.2 Statische Algorithmen
Statische Algorithmen werden heute eher seltener verwendet, deshalb hier nur ein kurzer Überblick.Die nonadaptiven Algorithmen basieren im Wesentlichen alle auf dem gleichen Grundprinzip. Zuerst beschafft sich der Router Informationen über die Struktur des gesamten Netzwerks. Dann entwirft er mit Hilfe dieser Information einen Senkenbaum. Ein Senkenbaum ist ein Baum, der alle optimalen Wege von einer festen Quelle zu allen anderen Senken beschreibt . Im letzten Schritt kann er dann mit dem Senkenbaum seine Routing-Tabelle belegen.
Der kürzeste Pfad
Der bekannteste Algorithmus zur Berechnung des kürzesten Pfades von einem zu allen anderen Knoten stammt von Dijkstra und ist in Abb. 2.2.1 dargestellt. Der Algorithmus hat einen Aufwand von O(n^2), wobei n für die Anzahl der Knoten steht. Mit ein paar in der Abbildung nicht enthaltenen Tricks lässt sich der Aufwand allerdings auf O (nlogn) reduzieren.
Abb. 2.2.1 Kürzester Pfad Algorithmus
Zurück zur Themenseite:
StudyPaper.com/Startseite/Computer/Internet
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
