Routing-Algorithmen

Routing-Algorithmen

In paketvermittelnden Netzen wie beispielsweise dem Internet werden Routing-Algorithmen zur Bestimmung der Routing-Tab eilen in den Routern verwendet. Dies wird unter dem Begriff Rou­ting zusammengefaßt. Durch Verwendung dieser Routing-Tab eilen können dann die in einem Router ankommenden Pakete weitergeleitet werden. Das wird dann auch Forwarding genannt.

Eine in der Praxis oft anzutreffende Klassifikation für Routing in paketvermittelnden Netzen ist die zwischen Link-State (LS) und Distance-Vector (DV) Verfahren. Unter der Annahme, daßjeder Router in einem Netz die Adresse seiner Nachbarrouter und auch die Kosten der Links, um diese Nachbarrouter zu erreichen, kennt, sind beide Verfahren in der Lage, ausgehend von einem beliebigen Router im Netz die kostengünstigsten Wege zu allen anderen Routern zu bestimmen. Der wesentliche Unterschied zwischen einem LS- und einem DV-Verfahren kann in etwa folgendermaßen charakterisiert werden:

- In einem LS-Verfahren sammelt jeder Router nur die Informationen über die Kosten, um seine Nachbarrouter zu erreichen, und teilt diese Informationen aber allen anderen Routern des Netzes mit. Bei einem LS-Verfahren werden also wenige Informationen über große Entfernungen übertragen.
- In einem DV-Verfahren sammelt jeder Router Informationen über die Kosten, um alle anderen Router des Netzes zu erreichen, und teilt diese Informationen nur seinen Nach­barroutern mit. Bei einem DV-Verfahren werden also viele Informationen über kurze Ent­fernungen übertragen.

Beide Verfahren sind aber in der Lage, auch in großen Netzen mit vielen Routern die ko­stengünstigsten Wege zu bestimmen.

Ein Vertreter der LS-Verfahren ist beispielsweise der Dijkstra-Algorithmus, während der Bellman-Ford-Algorithmus zu den klassischen DV-Verfahren gezählt werden kann. Es gilt:

- Nach Beendigung eines der beiden Algorithmen sind für den Router, in dem der Algorith­mus abgelaufen ist, die kostengünstigsten Wege zu allen anderen Routern bekannt. Wird nun der Algorithmus simultan in allen Routern des Netzes durchgeführt, dann kennen nach Beendigung des Algorithmus’ alle Router jeweils die kostengünstigsten Wege zu den an­deren Routern. Diese so gewonnenen Informationen werden dann in den Routing-Tab eilen der Router vermerkt.
- Bei sich dynamisch ändernden Kosten der Links in einem Netz müssen die Routing­Algorithmen periodisch durchgeführt werden, um die Routing-Tab eilen der Router an die neuen Gegebenheiten im Netz anzupassen.

Sowohl der Dijkstra- als auch der Bellman-Ford-Algorithmus werden im folgenden als Quelltext einer an PASCAL angelehnten Pseudoprogrammiersprache beschrieben und ihr Ablauf anhand eines kleineren Beispielnetzes illustriert.

Für den Quelltext beider Algorithmen gilt:

- Die einzelnen Router des Netzes sind von 1 bis N durchnumeriert.
- Die Variable start_router bezeichnet den Router, aus dessen Sicht der Algorithmus durch­geführt werden soll. Es werden also für den Router start_router die kürzesten Wege zu allen anderen Routern im Netz bestimmt.
- Die Kosten eines Links zwischen den Routern i und j, mit 1 < i, j < N, sind in den Werten c[iJ] eines zweidimensionalen Arrays, der sogenannten Adjazenzmatrix, gespeichert, wo­bei c[i,j] gleich unendlich (INFINITE) ist, wenn kein Link zwischen den Routern i und j existiert.
- In den Werten des eindimensionalen Arrays kostenf... ] werden für jeden Router die beim aktuellen Iterationsschritt des Algorithmus’ berechneten Kosten, um den Router vom start_router ausgehend zu erreichen, gespeichert.
- In den Werten des eindimensionalen Arrays vorgaenger_router_auf_dem_pfad[...] wird für jeden Router der beim aktuellen Iterationsschritt des Algorithmus’ bestimmte benachbarte Router, über den der Router vom start_router ausgehend erreicht wird, gespeichert. Nach Beendigung des Algorithmus’ können dann mit den Werten dieses Arrays die Pfade vom start_router zu allen anderen Routern im Netz ganz einfach bestimmt werden.

Dijkstra-Algorithmus

Abbildung in dieser Leseprobe nicht enthalten

Hinweis: Damit wird das Element aus der Liste mit minimalen Kosten der Variablen links vom Zuweisungsoperator := zugewiesen und aus der Liste entfernt. Um die Suche nach dem Element mit minimalen Kosten so schnell wie möglich durchführen zu können, sollte anstelle einer Liste z.B. ein Heap verwendet werden.

Bellman-Ford-Algorithmus

Abbildung in dieser Leseprobe nicht enthalten

Hinweis: Damit wird das Element am Kopf der Liste der Variablen links vom Zuweisungsoperator := zugewiesen und aus der Liste entfernt.

Beispielnetz

In der Abbildung 1 ist ein Beispielnetz mit 8 Routern abgebildet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Beispielnetz mit 8 Routern

Die folgende Tabelle gibt die Adjazenzmatrix des Beispielnetzes an. Dabei bedeuten nicht be­schriftete Tabelleneinträge, daßes zwischen den beiden zugeordneten Routern keine Verbindung gibt, die Kosten also unendlich sind.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Adjazenzmatrix des Beispielnetzes

Ausgehend vom Router D sollen nun mit Hilfe des Dijkstra- bzw. des Bellman-Ford-Algorithmus die kürzesten Wege zu allen anderen Routern des Netzes bestimmt werden. In den beiden folgen­den Tabellen bezeichnen die Werte in den mit k(X) beschrifteten Spalten die Kosten, um einen Router X ausgehend vom Startrouter zu erreichen. Die Werte in den mit p(X) beschrifteten Spalten geben dann den Pfad vom Startrouter zum Router X an.

In der folgenden Tabelle 2 ist der Ablauf des Dijkstra-Algorithmus dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Ablauf des Dijkstra-Algorithmus

In der folgenden Tabelle 3 ist der Ablauf des Bellman-Ford-Algorithmus dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Ablauf des Bellman-Ford-Algorithmus