Konzepte der Internet Technik

5.3.2   Link-State-Routing-Protokolle

Der Hauptnachteil von Distance-Vector-Protokollen ist, daß sie nicht besonders gut in Bezug auf die Größe eines Netzes skalieren. Neben dem Problem des langsamen Konvergierens ist hier vor allem der hohe Bandbreitenbedarf für den Austausch von Routing-Informationen zu nennen. Weil die Routing-Nachrichten nach der initialen Konvergenz einen Eintrag für jedes erreichbare Netz haben, steigt die Nachrichtengröße proportional mit der Anzahl der Netze eines Internet. Da aufgrund des Distance-Vector-Algorithmus jeder Router regelmäßig Routing-Nachrichten auf allen Links überträgt, kann der Anteil der Routing-Protokoll-Kommunikation am Gesamtverkehr durchaus beachtlich werden.

Link-State-Protokolle verfolgen dagegen den Ansatz, daß Informationen über die gesamte Netztopologie an alle Router verteilt werden. Über Link-State-Protokolle werden daher vollständige Topologie-Informationen verteilt, damit alle Router die gleiche Sicht auf das Netz haben. Dazu gehören Informationen über jeden in der Routing-Domäne befindlichen Router sowie über die jeweils von einem dieser Router erreichbaren Links, der link state. Beim Hochfahren eines Routers überträgt ein (durch das Protokoll ausgewählter) Nachbarrouter alle diese Informationen an den neuen Router. Nach dieser anfänglichen (durchaus aufwendigen) Synchronisation der Datenbasen werden dann nur noch Zustandsänderungen übertragen.

Bei Routing-Entscheidungen berechnet jeder Host den kürzesten Weg zu einem Ziel-Host selbst auf der Basis seines Netzplans. Da alle Router vom selben Netzplan ausgehen, fällen alle dieselben Entscheidungen, und es können keine Routing-Schleifen entstehen. (Dies gilt natürlich nur solange, wie der Abgleich der Netzpläne erfolgreich war!)

Ein Router geht wie folgt vor: Anstatt Routing-Nachrichten zu verschicken, die eine Menge von erreichbaren Zielnetzen enthalten, verschickt er Informationen über den Zustand seiner Verbindungen zu den direkten Nachbar-Routern. Dazu testen Router fortlaufend den Zustand der Verbindung untereinander durch Austausch von kurzen Nachrichten (Hello-Protokoll). Eine Verbindung kann entweder funktionstüchtig (up) oder gestört (down) sein.

Um die anderen Router über den Zustand seiner Verbindungen zu Nachbar-Routern zu informieren, überträgt ein Router bei einer Änderung dieses Zustandes Nachrichten an alle benachbarten Router, in denen diese Änderungen beschrieben sind (link state updates). Diese Router überprüfen, ob die Änderung für sie neu ist und verschicken sie dann weiter an ihre Nachbarn, und so weiter, bis die Änderungen die gesamte Routing-Domäne durchflutet haben (flooding).

Jedesmal, wenn ein Router einen solchen Update eines anderen Routers erhält, verwendet er die darin enthaltene Information, um seinen Netzplan zu aktualisieren, indem er Verbindungen als up oder down markiert. Wenn sich der Zustand einer Verbindung ändert, berechnet der Router die Routen neu, indem er den sogenannten Shortest-path-Algorithmus von Dijkstra anwendet. Mit diesem Algorithmus wird der kürzester Weg zu allen Zielen, ausgehend von dem Router selbst berechnet.

Shortest-Path-Algorithmen werden verwendet, um das Problem zu lösen, in einem Graph den “besten” Weg von einem bestimmten Knoten zu einem anderen Knoten zu finden. Die Bedeutung von “bester Weg” hängt dabei von der konkreten Maßeinheit ab, mit der Entfernungen zwischen Knoten in dem Graphen angegeben werden. Ein Graph ist hierbei eine Menge von Knoten und eine Menge von Kanten. Die Kanten verbinden einige Knoten des Graphen miteinander.

Abbildung 9. Ein Graph

Ein Pfad von einem Knoten zu einem anderen Knoten kann dann aus der Verkettung von mehreren Kanten bestehen und über weitere Knoten führen. In Abbildung 9 ist zu erkennen, daß es unter Umständen mehrere Pfade von einem Knoten zu einem bestimmten anderen Knoten geben kann. So führt ein Pfad von A nach C nur über den Knoten B, während ein zweiter über die Knoten B und D nach C führt.

In vielen Anwendungen ist es interessant, in einem solchen Graph den kürzesten Pfad von einem Knoten zu einem anderen Knoten zu finden. Wie bereits angedeutet, ist es möglich, die Entfernung zwischen zwei Knoten in bestimmten Maßeinheiten anzugeben. Dabei können Kanten jeweils verschiedene Entfernungswerte aufweisen. Die “Länge” einer Kante wird dabei auch Gewichtung genannt. Abbildung 10 hebt den kürzesten Pfad vom Knoten A zum Knoten C unter Berücksichtigung der Kantengewichtung hervor.

Abbildung 10. Der kürzeste Pfad von A nach C

Ein Graph wie in Abbildung 10 dargestellt kann natürlich auch anders notiert werden. Für viele Anwendungen reicht es aus, einfach die Menge der Kanten mit ihren Start- und Endknoten und gegebenfalls der Gewichtung anzugeben, wie in folgendem Beispiel:

Tabelle 1.

A --> B 3
B --> C 5
B --> D 1
D --> C 2

In diesem einfachen Beispiel ist es kein Problem, den kürzesten Pfad von A nach C zu bestimmen. Da die Menge der Knoten und die Menge der Kanten sehr klein sind, kann man einfach die Entfernungswerte der einzelnen Kanten für jeden möglichen Pfad (es sind nur zwei) addieren und dann den kürzesten Pfad durch einen Vergleich der Summen bestimmen. In größeren Netzen, die aus vielen Knoten und Kanten bestehen und in denen es viele verschiedene Pfade gibt, um von einem Knoten zu einem bestimmten anderen Knoten zu gelangen, gestaltet sich die Suche nach dem kürzesten Pfad schon deutlich aufwendiger.

Mit Shortest-Path-Algorithmen wird nun versucht, den Suchprozeß so zu systematisieren, daß er möglichst effizient durchgeführt werden kann und eine möglichst geringe Komplexität aufweist. Das bedeutet, er soll möglichst gut mit der Anzahl von Knoten und Kanten skalieren und nicht bei größeren Netzen um viele Größenordnungen aufwendiger als bei kleineren Netzen sein.

Der bekannteste Shortest-Path-Algorithmus ist Dijkstras Algorithmus, der von Edsger Wybe Dijkstra entwickelt wurde, um in einem Netz alle kürzesten Pfade von einem Knoten zu allen anderen Knoten zu finden. Dieser Algorithmus funktioniert folgendermaßen:

  1. T sei die Menge der Knoten, zu denen noch kein kürzester Pfad gefunden wurde. Zu Anfang ist T die Menge aller Knoten.

  2. Jeder Knoten dieser Menge erhält ein Attribut, das die Entfernung zum Ausgangsknoten (dieser sei hier A genannt) angibt. Zunächst wird dieser Wert für alle Knoten auf unendlich gesetzt. Der Entfernungswert von A zu A wird mit 0 angenommen.

  3. Jeder Knoten erhält außerdem ein Attribut, das den Vorgängerknoten auf dem Weg von A zu dem jeweiligen Knoten angibt, sofern vorhanden. Zunächst ist der Wert für dieses Attribut für alle Knoten unspezifiziert.

  4. Von allen Knoten aus T wird derjenige mit dem kürzesten Entfernungswert ausgewählt (dies ist zunächst A, weil A der einzige Knoten ist, dessen Entfernung zu Anfang nicht unendlich ist).

  5. Sei der gewählte Knoten Kg. Dieser Knoten wird aus der Menge T entfernt.

  6. Jede Kante, die von Kg zu einem Knoten Kp führt, der noch in T enthalten ist, wird daraufhin untersucht, ob der aktuelle Entfernungswert für Kp größer als die Summe der Entfernungswerte von Kg und der Gewichtung der Kante von Kg zu Kp ist. (Für Knoten, die bislang noch nicht berücksichtigt wurden, ist der Entfernungswert ja unendlich, deswegen trifft da die Bedingung immer zu). Wenn dies der Fall ist, wird als Entfernungswert für Kp der kürzere Wert eingetragen und als Vorgänger von Kp wird Kg notiert.

  7. Wenn T nicht leer ist, wird der Algorithmus wieder bei Punkt 4 fortgeführt.

Als Ergebnis erhält man eine Menge von Knoten, zu denen jeweils die Gesamtentfernung und der Vorgängerknoten auf dem kürzesten Pfad angegeben ist, d.h., die kürzesten Wege zu allen Knoten sind bekannt. Die Funktionsweise des hier etwas abstrakt definierten Algorithmus läßt sich an einem kleinen Beispiel veranschaulichen:

Abbildung 11. Shortest Path nach Dijkstra (1)

Wir wollen alle von A ausgehenden kürzesten Pfade ermitteln. Nach dem dargestellten Algorithmus wird dazu in der ersten Runde zunächst A selbst betrachtet (einziger Knoten mit nicht-unendlichem Entfernungswert). Hierzu werden gemäß Schritt 6 alle von A ausgehenden Kanten untersucht (Abbildung 11). Für die entsprechenden Knoten B und D wird eine neue kürzeste Entfernung eingetragen und A als Vorgänger vermerkt. A wird zuvor aus der Menge der noch zu betrachtenden Knoten entfernt.

Abbildung 12. Shortest Path nach Dijkstra (2)

Abbildung 12 stellt das Vorgehen im zweiten Schritt dar. Hier wird zunächst der Knoten mit dem geringsten Entfernungswert ermittelt, in diesem Fall also B, und aus der Menge der noch zu betrachtenden Knoten entfernt. Dann werden die direkt mit B verbundenen Knoten betrachtet. Dabei kann A ausgenommen werden, weil der kürzeste Pfad zu A schon bekannt ist. Für C wird ein neuer Entfernungswert für einen Pfad, der über B führt, eingetragen. Bei D stellt sich heraus, daß ein Pfad über B kürzer wäre (Entfernungswert 7) als der bisher angenommene (direkt über A mit dem Entfernungswert 8). Deshalb wird der neue, kleinere Wert sowie B als Vorgänger eingetragen.

Abbildung 13. Shortest Path nach Dijkstra (3)

In der nächsten Runde gibt es noch zwei zu betrachtende Knoten (C und D). Da für beide der Entfernungswert 7 ermittelt wurde, wird einfach einer ausgewählt und aus der Menge der noch zu betrachtenden Knoten entfernt, in diesem Fall C. Der einzige Knoten, der direkt mit C verbunden ist und noch zu betrachten wäre, ist D. Da aber ein Pfad zu D über C einen größeren Entfernungswert aufweist (7+3) als der bisher ermittelte (7), bleiben die für D ermittelten Werte erhalten, wie aus Abbildung 13 ersichtlich.

Abbildung 14. Shortest Path nach Dijkstra (4)

Schließlich wird in Abbildung 14 noch Knoten D behandelt und als letzter Knoten aus der Menge der noch zu betrachtenden Knoten entfernt. Da keine weiteren noch zu betrachtenden Knoten mehr vorhanden sind, terminiert die Abarbeitung des Algorithmus an dieser Stelle.

Wenn man nun, wie in Abbildung 15 dargestellt, nur noch die kürzesten Pfade von A zu allen anderen Knoten betrachtet und Kanten, die dafür nicht benötigt werden, außer Acht läßt, entsteht der Shortest Path Tree für A. In der Graphtheorie ist ein Baum ein gerichteter, azyklischer Graph, das heißt, man kann ihn nur in einer Richtung traversieren und Schleifen sind ausgeschlossen. Aus einem Shortest Path Tree können Router beim Link-State-Routing eine Routing-Tabelle ableiten.

Abbildung 15. Shortest Path Tree

Der Vorteil des Link-State-Routing ist, daß jeder Router die Routen selbst auf der Basis von Topologiewissen und erhaltenen Statusinformationen berechnet. Ein Router ist dadurch nicht abhängig von Berechnungen anderer Router, wodurch die Wahrscheinlichkeit, daß eine Konvergenz erreicht werden kann, viel höher als beim Distance-Vector-Verfahren ist. Link-State-Protokolle sind auch im Fehlerfall leichter zu analysieren, weil die Statusinformationen direkt, ohne Zwischeninterpretation übertragen und zur Erstellung eines lokalen Netzplans verwendet werden. Da Link-State-Routing-Nachrichten nur Zustandsinformationen über direkte Verbindungen zwischen Routern enthalten, hängt die Größe der Nachrichten nicht unmittelbar von der Anzahl der erreichbaren Netze ab. Aus diesen Gründen skalieren Link-State-Algorithmen im allgemeiner besser als Distance-Vector-Algorithmen.

Ein Nachteil von Link-State-Routing-Protokollen ist der erhöhte Rechenaufwand bei der Berechnung der Shortest Path Trees. Da diese Berechnung nach jeder Topologie-Änderung, im allgemeinen nach dem Empfang von Link-State-Aktualisierungen, durchgeführt wird, kann bei größeren Netzen ein nicht zu vernachlässigender Aufwand entstehen. Darüberhinaus basiert das Verfahren darauf, daß jeder Router eine komplette Datenbasis unterhält, die die Netztopologie widerspiegelt. Das heißt, auch die Anforderungen in Bezug auf Speicherplatz in Routern können bei größeren Netzen recht hoch werden (dies war allerdings sicher früher ein gewichtigeres Argument als heute).

Kommentare (0)

Ihr Kommentar

Name