Stellen Sie sich ein unsichtbares Netz vor, das die Grundlage unserer modernen Kommunikation bildet: das Internet. Aber wie finden Datenpakete ihren Weg durch dieses Labyrinth aus Verbindungen? Dieser Frage widmet sich dieses Buch, indem es tief in die Welt der Routing-Algorithmen eintaucht. Es beleuchtet die fundamentalen Unterschiede zwischen Link-State (LS) und Distance-Vector (DV) Verfahren, zwei konkurrierenden Philosophien der Wegfindung in paketvermittelnden Netzen. Entdecken Sie, wie der Dijkstra-Algorithmus, ein Paradebeispiel für LS-Verfahren, und der Bellman-Ford-Algorithmus, ein Klassiker der DV-Verfahren, Router in die Lage versetzen, die effizientesten Routen zu berechnen. Anhand von anschaulichen Beispielen und einer schrittweisen Erklärung in einer PASCAL-ähnlichen Pseudoprogrammiersprache werden diese komplexen Algorithmen entmystifiziert. Verstehen Sie, wie Router Informationen über ihre Nachbarn austauschen, Kosten bewerten und ihre Routing-Tabellen dynamisch an sich ändernde Netzwerkbedingungen anpassen. Dieses Buch ist ein unverzichtbarer Leitfaden für alle, die sich für die Funktionsweise des Internets interessieren, von Studierenden der Informatik bis hin zu Netzwerkadministratoren. Es vermittelt ein tiefes Verständnis für die Prinzipien des Routings, die die Grundlage für eine zuverlässige und effiziente Datenübertragung bilden. Erforschen Sie die Adjazenzmatrix, lernen Sie die Bedeutung von Kostenberechnungen kennen und verfolgen Sie den Ablauf der Algorithmen anhand eines detaillierten Beispielnetzes mit acht Routern. Werden Sie Zeuge, wie die kürzesten Wege zwischen den Routern ermittelt werden, und gewinnen Sie einen Einblick in die faszinierende Welt der Netzwerkoptimierung. Dieses Buch ist Ihr Schlüssel zum Verständnis der Routing-Algorithmen und ihrer entscheidenden Rolle im Herzen des Internets. Es ist ein Muss für jeden, der die komplexen Mechanismen hinter der scheinbar mühelosen Datenübertragung verstehen möchte. Tauchen Sie ein in die Welt der Netzwerke und entdecken Sie die verborgenen Algorithmen, die unsere digitale Welt verbinden.

Excerpt

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 Routing 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 Nachbarroutern mit. Bei einem DV-Verfahren werden also viele Informationen über kurze Entfernungen übertragen.

Beide Verfahren sind aber in der Lage, auch in großen Netzen mit vielen Routern die kostengü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 Algorithmus 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 anderen 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 RoutingAlgorithmen 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 durchgefü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, wobei 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.