2. Routing
Die Entscheidung, wohin Daten-Pakete (Briefe) weiterzuleiten sind, deren Empfänger nicht direkt erreichbar ist, hängt von verschiedenen Kriterien ab.
Der Entscheidungsfindungs-Prozess ist recht kompliziert und kann auf verschiedene Arten und zu verschiedenen Zeiten ausgeführt werden und auf Informationen beruhen, die auf unterschiedliche Weise zu unterschiedlichen Zeiten erworben wurden und unterschiedlich bewertet werden.
2.1 Ort der Entscheidung
2.1.1 Absender
In machen Netzwerken wird sogenanntes "Source-Routing" unterstützt, bei dem der Absender eines Paketes einen Weg durch das Netzwerk auswählt (bzw. bei einem Route-Server anfordert) und diesen Weg dann im Kopf des Paketes mit überträgt. Jeder Knoten des Netzwerkes, der dieses Paket erhält, schaut im Paket-Kopf nach, an wen er das Paket weiterleiten soll.
2.1.2 Zentral
Vor allem bei verbindungsorientierten Netzwerk-Protokollen gibt es eine (oder mehrere) zentrale Instanz (sogenannte Routing-Server), die für jede neue Verbindung einen Weg durch das Netzwerk auswählt und gegebenenfalls auch alle beteiligten Netz-Knoten von der neuen Verbindung und deren Weg in Kenntnis setzt.
2.1.2 Dezentral
In den meisten paketorientierten Netzwerken (wie z.B. im Internet und auch bei dem Beispielnetzwerk Briefpost) ist jeder Knoten ein Router für alle diejenigen Pakete, die er empfängt aber von ihm nicht zustellbar sind. Er sucht daher nach einem geeigneten Knoten, an den er dieses Paket weiterleiten kann.
2.2 Zeit der Entscheidung
2.2.1 Pro Verbindung
Bei verbindungsorientierter Datenübertragung (z.B. X25, ISDN ...) wird beim Verbindungsaufbau die Übertragungsstrecke ausgewählt und auch reserviert, so dass alle Dateneinheiten (z.B. Timeslots im ISDN oder Pakete im X25) denselben Weg zurücklegen.
2.1.2 Pro Packet
Bei verbindungsloser Datenübertragung wird für jedes Datenpaket einzeln (und meistens von den anderen unabhängig) der Weg ausgewählt. So kann es passieren, dass zwei aufeinanderfolgende Pakete vom selben Absender zum selben Empfänger auf unterschiedlichen Wegen zum Empfänger geleitet werden und sich dabei auch noch überholen.
2.3 Informationsquellen
2.3.1 Statisch
Alle Routing-Informationen werden durch den Administrator vorgegeben, verwaltet und auch nur von ihm verändert. Veränderungen, Ausfälle werden nur dem Administrator angezeigt, der dann selbst entscheidet, ob und welche Maßnahmen eingeleitet werden müssen.
2.3.2 Pseudo-statisch
Routing-Informationen werden durch den Administrator vorgegeben und auch nur von ihm verändert. Zusätzlich wird aber noch der lokale Netzwerkzustand und die Erreichbarkeit direkt-verbundener Router berücksichtigt.
2.3.3 Dynamisch
Routing-Informationen werden automatisch (und kontinuierlich) zwischen Routern ausgetauscht. Von Änderungen dieser Informationen werden somit alle Router in Kenntnis gesetzt, die dann selbst entscheiden, welche sie davon übernehmen.
2.4 Entscheidungskriterien (Metric)
2.4.1 Hop-Count
Die Anzahl der an der Übertragung beteiligten Router ist in vielen Netzwerken ein ausschlaggebendes Kriterium (siehe Shortest-Path). Beispielsweise wird im Novell-Netzwerk nur anhand dieses Kriteriums entschieden, dagegen in Internet-Implementationen meist anhand einer Kombination aus Anzahl der Knoten und der Übertragungskapazität.
\subsubsection{Capacity}2.4.2 Capacity
Die Übertragungskapazität einer Verbindung zwischen zwei Routern. Sie wird im Internet (und in vielen anderen Netzwerken) als positive Zahl angegeben, wobei ein niedriger Wert eine hohe Kapazität repräsentiert, z.B. 1 (sehr hohe Kapazität) und 100 (sehr niedrige Kapazität).
2.4.3 Delay
Die Verzögerungszeit, mit der das Paket beim Empfänger ausgeliefert wird (s. Minimum-Delay). Die Zeit ist sowohl von der Übertragungskapazität als auch von der Auslastung einer Verbindung abhängig. Da sich die Auslastung einer Verbindung (oder eines Routers) sehr schnell ändert, wird im Allgemeinen der Mittelwert der letzten Zeit gebildet. Die Erfassung und Auswertung der Auslastung entfernter Knoten ist daher nicht einfach und nicht unbedingt ein Abbild der momentanen Situation.
2.4.4 Cost
Die bei der Übertragung entstehenden (Leitungs-) Kosten. Meistens sind Verbindungen mit hoher Übertragungs-Kapazität und geringer Verzögerung teurer als Leitungen mit geringer Kapazität.
2.4.5 Reliability
Die Übertragungssicherheit (Anzahl der Übertragungsfehler) spielt heutzutage immer weniger eine Rolle, da (trotz höherer Bandbreiten) die Leitungen immer sicherer werden.
2.5 Algorithmen
Je nachdem welche Anforderungen an das Netzwerk gestellt werden, werden verschiedene Algorithmen angewendet, um eine möglichst optimale Entscheidung zu treffen. Allgemein übliche Algorithmen werden hier kurz dargestellt.
2.5.1 Shortest-Path
Das Ziel ist, den kürzesten Übertragungsweg zum Empfänger zu finden und somit möglichst wenig andere Router mit diesem Paket zu belasten. Wichtigstes Entscheidungskriterium ist daher der HopCount.
2.5.2 Minimum-Delay
Das Ziel ist, das Paket möglichst schnell (d.h. mit minimaler Verzögerung) beim Empfänger abzuliefern. Über wie viele Router das Paket dabei geleitet wird, und wie hoch die dabei entstandenen Leitungskosten sind, ist dabei weniger relevant.
2.5.3 Distance- Vector-Routing
Jeder Router hat ein Abbild des kompletten Netzwerkes gespeichert. Er kennt alle Verbindungen zwischen den Routern und kann daher den optimalen Weg errechnen.
Der Nachteil dabei ist jedoch die Komplexität der Rechnung und die Menge der Verbindungsdaten, die gespeichert werden müssen. In einem Netzwerk mit z.B. 100 Routern müsste jeder Router eine Matrix mit 100 mal 100 Spalten (also 10.000 Einträge) verwalten. Alleine das (automatische) Austauschen der Routinginformationen würde einen großen Teil der Übertragungskapazität beanspruchen.
2.5.4 Link-State-Routing
Der Router kennt nur die Richtung, in der eine bestimmte Adresse zu erreichen ist.
Veränderungen in der Erreichbarkeit von Netzwerken, werden nur den unmittelbar benachbarten Routern mitgeteilt. In großen Netzwerken (wie dem weltweit verteilten Internet) ist das die Regel.
2.5.5 Backward-Learning
In symmetrischen Netzwerken, in denen zwischen zwei Knoten der Übertragungsweg in der einen Richtung genauso gut ist wie in der entgegengesetzten Richtung, wird ein Paket in diejenige Richtung geschickt, aus der schon einmal Pakete von der gesuchten Adresse empfangen wurden. Wurden dagegen von dieser Adresse noch keine Pakete empfangen, so wird das Paket in alle Richtungen (außer der, aus der es gekommen ist) gesendet. Falls das Paket den Empfänger auf einer der Verbindungen erreicht hat, wird dieser (wahrscheinlich) eine Antwort schicken (natürlich auf der Verbindung, von der er es empfangen hat. Ist erst einmal ein Paket den Hin- und Rückweg durchlaufen, wissen alle beteiligten Router beim nächsten Mal, wohin sie es weiterleiten müssen.
Der Nachteil dabei ist jedoch, dass Veränderungen (z.B. Ausfall eines Routers) katastrophale Folgen haben, da nicht erkannt wird, dass die Pakete jetzt einen anderen Weg gehen müssen.