Rechnernetze

Feste Wegetabellen

Bei diesem Verfahren werden vor der Inbetriebnahme eines Netzes die optimalen Wege in festen Wegetabellen abgelegt. Dazu muss die Topologie sowie eine Gewichtung der Verbindungsleitungen gegeben sein; außerdem sollte die mittlere zu erwartende Belastung bekannt sein, um zu verhindern, dass einzelne Leitungen überlastet werden. Als Optimalitätskriterien können hier die Länge des Verbindungsweges oder die Kosten der Nutzung der Verbindungsleitung einfließen.

Die grundlegende Idee zur Berechnung des optimalen Weges besteht darin, einen Graphen des Netzes zu erstellen, in welchem die Knoten die IMPs, und die Kanten zwischen den Knoten die Leitungen repräsentieren. Zur Berechnung der Wegetabellen wird dann nach einem der genannten Bewertungskriterium der optimale Weg zwischen jeder Quelle und jeder Senke bestimmt.

Zur Demonstration dieses Verfahrens wird für das im Bild dargestellte Netz mit 8 Knoten beispielhaft die Erstellung einer Wegetabelle vorgeführt.

Sei D_qs(w) die Zielfunktion bei der Wahl des Wegs w zwischen den Knoten q und s. Für alle möglichen Wegen w zwischen einer Quelle q und einer Senke s gibt es einen oder mehrere optimale Wege, so dass für deren Bewertungskriterium gilt

Mit Hilfe dieser Wege kann dann ein Quelle-Senken-Baum definiert werden, der alle optimalen Wege von einer festen Quelle zu allen anderen Senken beschreibt.

Als Bewertungskriterium für den optimalen Weg soll in diesem Beispiel die Distanz zwischen zwei Knoten verwendet werden, wobei die Distanz benachbarter Knoten im Netz den Wert 1 erhalten soll. Damit erhalten wir für den Quellknoten 5 die folgenden optimalen Wege W_5i^opt.

Unter dem Quelle-Senken-Baum für einen Quellknoten q verstehen wir den Baum, der nur noch optimale Wege für q umfasst. Für unser Beispiel erhalten wir als Quelle-Senken-Baum für den Quellknoten 5

Aus dem Quelle-Senken-Baum lässt sich unmittelbar erkennen, dass jeder Teilweg eines optimalen Weges gleichfalls ein optimaler Weg ist. Führt ein optimaler Weg W_ij^opt über zwei Knoten r und s: {r,s}⊂W_ij^opt, so ist der optimale Weg zwischen r und s der Teilweg von W_ij^opt,der von r nach s führt.

Aus dieser Überlegung ergibt sich, dass der weitere Weg eines Pakets unabhängig von seinem Ursprung ist. Ein Paket in Knoten r, welches nach Knoten j soll, wird zwischen r und j über den gleichen Pfad weitergereicht wie ein Paket, welches von i nach j soll (und über r geführt werden muss). Daher braucht jeder Knoten für die Wegfindung nur das Ziel eines Pakets zu kennen, nicht jedoch die Quelle. Das vereinfacht die Speicherung der Routinginformation, sowie die Auswahl der Ausgangsleitung. Systeme, deren Verhalten nicht von der Vorgeschichte abhängt, werden auch als Markov-Systeme bezeichnet. Im folgenden soll die Wegetabelle für das oben gezeigte Netz angegeben werden, indem für jeden Knoten (wie zuvor für den Knoten 5) ein Quelle-Senken-Baum angegeben wird. Die Tabelle der opimalen Wege besitzt folgende Einträge:

Aufgrund der vorher gezeigten Markov-Eigenschaft muss nur in jedem Knoten i die entsprechende Spalte der Wegfindungstabelle gespeichert werden. Dieser Wegefindungsvektor besitzt den Eintrag für den nächsten Knoten, auf dem das Paket oder Datagramm auf dem Weg zur Senke (Zielknoten) weiterzuleiten ist. Der Wegefindungsvektor für den Knoten 3 besitzt dann folgende Einträge:

Bisher gingen wir davon aus, dass der optimale Weg zwischen zwei Knoten unmittelbar bestimmt werden kann. Dieses ist jedoch nicht der Fall, wenn die Anzahl der zu verbindenden Knoten im Rechnernetz sehr groß ist und die Gewichtung der Kanten sehr unterschiedlich. Aus diesem Grund wurden Algorithmen entwickelt, mit denen die optimalen Wege eines Graphen mit einer gegebenen Anzahl von Knoten und festgelegter Bewertung der Kanten effizient ermittelt werden können. Diese Verfahren werden allgemein als 'Shortest Path Algorithms' bezeichnet. Eines der bekanntesten Verfahren ist der Algorithmus von Dijkstra.

Um eine gleichmäßige Auslastung der Verbindungsleitungen zu gewährleisten, kann das Verfahren der festen Wegetabellen so modifiziert werden, dass der Verkehr zwischen einer Quelle und einer Senke nicht nur über einen einzigen Verbindungsweg geführt wird, sondern dass mehrere Alternativen bereitstehen. Diese Technik, die zwischen zwei Knoten mehr als einen Verbindungsweg vorsieht, wird Mehrfach-Leitwegbestimmung (multipath routing, bifurcated routing) genannt. Zur Durchführung des Verfahrens wird die Wegetabelle um zusätzliche Spalten, in denen die alternativen Wege angegeben sind, erweitert. Die Auswahl der einzelnen Alternativen erfolgt dann in der Regel zufallsgesteuert, wodurch zugleich Prioritäten für einzelne Wege festgelegt werden können.

Die Entscheidung über die Weiterleitung des Pakets oder eines Datagramms verläuft folgendermaßen: Im ersten Schritt wird aus der entsprechenden Zeile der Wegetabelle, die durch den Zielknoten bestimmt werden kann, der Vektor für die alternativen Wege gesucht. Danach erfolgt die Berechnung einer Zufallszahl z zwischen 0 und 1, mit der die entsprechende Ausgangsleitung bestimmt werden kann (z.B. Ausgangleitung 1 für 0 = z < 0,3; Ausgangsleitung 2 für 0,3 = z < 0,7 und Ausgangsleitung 3 für 0,7 = z < 1); durch diese Gewichtung der Ausgangsleitungen können die Topologie, die unterschiedliche Leistungsfähigkeit der einzelnen Verbindungsleitungen und andere Netzparameter berücksichtigt werden.

Ein weiterer Vorteil der Mehrfach-Leitwegbestimmung besteht darin, dass unterschiedliche Arten des Datenverkehrs (Terminalsitzungen, Dateitransfer) auf verschiedenen Verbindungsleitungen, die für die jeweils benötigte Verbindungsart besonders geeignet sind, übertragen werden können. In diesem Fall wird die jeweilige Ausgangsleitung dann nicht mittels einer Zufallszahl, sondern aufgrund der Art des Datenverkehrs bestimmt. Darüber hinaus kann die Verfügbarkeit des Netzwerks erhöht werden, da bei Ausfall einer Verbindungsleitung oder eines Knotens auf eine andere Verbindung ausgewichen werden kann. Voraussetzung dafür ist allerdings die Unabhängigkeit der Verbindungswege.