Routing (amerik.)/[ (brit.), Wegewahl oder Verkehrslenkung bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze. Insbesondere in paketvermittelten Datennetzen ist hierbei strenggenommen zwischen den beiden verschiedenen Prozessen Routing und Forwarding zu unterscheiden: Das Routing bestimmt den gesamten Weg eines Nachrichtenstroms durch das Netzwerk; das Forwarding beschreibt hingegen den Entscheidungsprozess eines einzelnen Netzknotens, über welchen seiner Nachbarn er eine vorliegende Nachricht weiterleiten soll.
Häufig werden jedoch Routing und Forwarding unter dem Begriff „Routing“ miteinander vermengt; in diesem Fall bezeichnet Routing ganz allgemein die Übermittlung von Nachrichten über vermaschte Nachrichtennetze.
Die Vermittlungstechnik bezeichnet mit dem Begriff Verkehrslenkung (engl.: routing) die Auswahl der Wegeabschnitte beim Aufbau von Nachrichtenverbindungen, die unter Berücksichtigung von Kriterien wie kürzeste Entfernung etc. erfolgen kann. Handelt es sich um eine leitungsvermittelte Verbindung, wird ein Übertragungskanal für die gesamte Zeit der Verbindung ausgewählt, und alle Nachrichten werden über denselben Weg geleitet. Handelt es sich dagegen um eine paketvermittelte Datenübertragung, wird der Weg für jedes Paket von jedem Netzknoten neu bestimmt.
Prinzipiell werden drei Herangehensweisen unterschieden:
Hubs und Switches leiten Daten nur im lokalen Netz weiter, wohingegen der Router auch benachbarte Netze kennt. Dieser Artikel beschreibt Routing auf eine Hardware-unabhängige Art. Für Informationen über Router selbst siehe den Router-Artikel.
Um zu wissen, wohin Pakete gesendet werden sollen, muss man die Struktur des Netzes kennen. In kleinen Netzen kann das Routing sehr einfach sein und wird oft per Hand konfiguriert. Man spricht dann auch von statischem Routing. Große Netze können eine komplexe Topologie haben, die sich möglicherweise häufig ändert, was unter anderem das Routing zu einer komplexen Angelegenheit macht. Hier wird in der Regel ein dynamisches Routing angewandt.
Da Router die besten Routen im Verhältnis zur Anzahl der zu bewegenden Pakete nur sehr langsam berechnen können, merken sie sich in einer oder mehreren Routingtabellen die bestmöglichen, teilweise auch weitere Routen zu bestimmten Netzen und die dazugehörigen Routing-Metriken. Der bestmögliche Weg ist normalerweise der kürzeste Weg; er kann zum Beispiel mit dem Algorithmus von Dijkstra gefunden werden.
Basierend auf den Einträgen in der oder den Routingtabelle(n) berechnet ein Router eine sogenannte Forwardingtabelle; sie enthält einfach Einträge der Form Zieladressmuster→Ausgabeschnittstelle. In seiner Forwardingtabelle schlägt ein Router dann für jedes neu eingetroffene Paket nach, über welche Schnittstelle er das Paket weiterleiten muss.
Ein beliebtes Beispiel ist das Dynamic Source Routing; hierbei erfährt die sendende Station durch die Route Discovery eine gültige Route zur Zielstation. Diese Route wird in den Header eines jeden Paketes zur Zielstation eingetragen und jeder Zwischenknoten ist verpflichtet, das Paket entlang dieser Route weiterzuleiten. Die korrekte Weiterleitung kann in drahtlosen Netzen auch durch den vorigen Hop-Knoten kontrolliert werden (mithören).
Routing-Protokolle sorgen für den Austausch von Routing-Informationen zwischen den Netzen und erlauben es den Routern, ihre Routing-Tabellen dynamisch aufzubauen. Traditionelles IP-Routing bleibt einfach, da Next-Hop-Routing benutzt wird: Der Router sendet das Paket an denjenigen Nachbar-Router, von dem er glaubt, dass er am günstigsten zum Zielnetz liegt. Um den weiteren Weg des Pakets braucht sich der Router nicht zu kümmern. Selbst wenn er falsch lag und das Paket nicht an den „optimalen“ Nachbarn gesendet hat, sollte das Paket trotzdem früher oder später am Ziel ankommen.
Obwohl dynamisches Routing sehr komplex werden kann, macht es das Internet sehr flexibel und erlaubte das exponentielle Wachstum des Internets seit der Einführung von IP im Jahre 1983. Wenn Teile der Backbones ausfallen (so geschehen z. B. im Sommer 2002, als der Carrier KPNQwest sein europaweites Glasfasernetz wegen Insolvenz abschalten musste), können innerhalb von Sekunden Alternativrouten propagiert werden und die betroffenen Netzbereiche weiträumig umgangen werden.
Dem Ausfall des sogenannten Standardgateways, das ist meist der erste Router vom Sender aus gesehen, wirkt dynamisches Routing jedoch nicht entgegen. Da ein Host im Normalfall keine Alternative zum Standardgateway hat, ist dies der wichtigste Router der Route. Zur Lösung dieses Problems wurden HSRP, VRRP und CARP entwickelt.
Routing-Algorithmen benutzen zwei grundlegende Verfahrensweisen:
Weiterhin können Routing-Algorithmen im wesentlichen nach Ihrer Zentralisation und Ihrer Dynamik beurteilt werden:
Aus diesen Punkten ergibt sich ein Zielkonflikt, da zwar zentrale,nicht adaptive Verfahren das Netz selber weniger mit Routingnachrichten belasten, aber möglicherweise veraltete und/oder unvollständige Informationen über den Zustand des Netzes benutzen. Je adaptiver und verteilter die Routingverfahren sind, desto besser sind die Informationen über das Netz. Aber desto mehr wird dieses auch durch den Austausch von Nachrichten zum Routen belastet. Hier gibt es nun eine Vielzahl von Algorithmen, die einen Unterschiedlichen Grad von Zentralisation und Dynamik aufweisen:
Dieses Verfahren ist nicht adaptiv, sehr einfach und daher viel benutzt. Jeder Knoten unterhält eine Tabelle mit einer Zeile für jeden möglichen Zielknoten. Eine Zeile enthält n Einträge, welche die beste, zweitbeste usw. Übertragungsleitung für dieses Ziel ist zusammen mit einer Gewichtung. Vor Weiterleitung eines Paketes wird der entsprechende Eintrag aus der Tabelle gewählt und auf eine der möglichen Leitungen gegeben. Die Gewichtung spiegelt hier die Wahrscheinlichkeit wieder, dass diese Leitung gewählt wird.
Zentralisiertes Routing:
Zentralisiertes Routing stellt ein adaptives Verfahren dar. Es existiert im Netz ein Routing Control Center (RCC), an welches jeder Knoten periodisch Zustandsinformationen sendet. (z. B.: Liste aller aktiven Nachbarn, aktuelle Warteschlangenlänge, Umfang an Verkehr seit letzter Meldung, ...) Das RCC sammelt die Zustandsinformationen und berechnet auf Grund dieser Kenntnis über das gesamte Netz die optimale Weglänge zwischen allen Knoten. Danach übermittelt das RCC jedem Knoten eine Routingtabelle, anhand welcher der Knoten seine Routing-Entscheidungen trifft.
Vorteil:
Isoliertes Routing
Bei dieser Art der Routingverfahren, entscheidet jeder Knoten nur auf Grund der Informationen, die er selber sammelt. Es findet kein Austausch von Routing-Informationen statt. Die Anpassung an Änderungen des Verkehrs oder der Topologie des Netzes (durch z. B.: Ausfall von Knoten) kann hier also nur mit beschränkten Informationen erfolgen. Zu den isolierten Routing-Verfahren zählen:
Broadcast Routing
Beim Broadcast Routing wird ein Paket an alle Knoten gesendet. Hierbei unterscheiden sich zwei Varianten: Einmal das für jeden Knoten ein gesondertes Paket erstellt wird und zum anderen das Fluten. Das Fluten ist hierbei das einfachste Verfahren und ist nicht adaptiv. Jedes eingehende Paket wird auf jeder Übertragungsleitung weitergegeben, außer auf derjenigen, auf welcher es eintraf. Hierbei können auch Maßnahmen zur Eindämmung der Flut getroffen werden, wie:
Hot Potato
Jeder Knoten versucht, eingehende Pakete so schnell wie möglich weiterzuleiten (Sie behandeln das Paket wie eine heiße Kartoffel, daher der Name). Hierbei wird die Übertragungsleitung mit der kürzesten Warteschlange gewählt. Es gibt auch Kombinationen dieses Verfahrens mit denen des statischen Routing:
Backward Learning
Bei diesem Verfahren müssen folgende Informationen im Paket gespeichert werden:
Delta Routing
Dieses Verfahren stellt eine Kombination zwischen zentralisiertem und isoliertem Routing dar. Hierbei misst jeder Knoten periodisch die Kosten jeder Übertragungsleitung (z. B.: eine Funktion der Verzögerung, Auslastung, Kapazität, ...) und sendet diese an das RCC. Das RCC berechnet nun die besten Wege von Knoten zu Knoten (a für alle Knoten , ), wobei nur Wege berücksichtigt werden die sich in ihrer initialen Leitung unterscheiden. Das RCC sendet an jeden Knoten die Liste aller äquivalenten Wege für alle Bestimmungsorte. Zum aktuellen Routing kann ein Knoten einen äquivalenten Weg zufällig wählen, oder auf Grund aktuell gemessener Kosten entscheiden. Das namensgebende Delta stammt hier aus der Funktion mit der ermittelt wird, ob zwei Wege als äquivalent anzusehen sind.
Verteiltes adaptives Routing
Bei diesem Verfahren tauscht jeder Knoten periodisch Routing-Informationen mit jedem seiner Nachbarn aus. Auch hier unterhält jeder Knoten eine Routing-Tabelle, die für jeden anderen Knoten im Netz einen Eintrag enthält. In dieser Tabelle sind die bevorzugte Übertragungsleitung für diesen Knoten, sowie eine Schätzung zu Zeit oder Entfernung zu diesem Knoten enthalten:
Distance Vector Routing
Ein verteiltes, adaptives Routing, welches als RIP früher im Internet benutzt wurde. Hierbei speichert jeder Router eine Tabelle mit der besten Entfernung (z. B.: Anzahl hops, Verzögerung in ms) zu jedem Ziel und dem dazugehörigen Ausgang. In der Praxis hat dieses Verfahren eine zu langsame Konvergenz zu einem konsistenten Zustand für viele Router, auf Grund der "Count-to-infinity"-Problematik.
Link State Routing
Ein verteiltes, adaptives Routing, welches als OSPF und IS-IS im Internet eingesetzt wird. Dabei findet folgender Algorithmus Anwendung:
Hierarchisches Routing
Die Grundlage des Hierarchischen Routings ist die Aufteilung großer Netze in Regionen. Die Knoten einer Region haben nur Routing-Informationen über ihre eigene Region. In jeder Region existiert zumindest ein ausgezeichneter Knoten, welcher als Schnittstelle zu den anderen Regionen dient. In sehr großen Netzen sind weitere Hierarchien auf Grund zunehmender Größe der Netze möglich (Regionen,Cluster,Zonen,Gruppen, ...).
Der Administrator versucht, durch geschicktes Konfigurieren des Routings das durch das Netzwerk übertragene Datenvolumen zu maximieren. Dieses Optimieren des Routings unter Berücksichtigung des real vorhandenen Datenübertragungsbedarfes zwischen verschiedenen Teilen des Netzwerkes nennt man Traffic Engineering.
Dabei können Routingprotokolle auch miteinander interagieren. Beispielsweise können neue Routen aus dem IGP zum EGP exportiert werden. Auch andere Fälle sind denkbar: Ändert sich, z. B. durch den Ausfall eines Links, die IGP-Metrik für einen Pfad a⇝b innerhalb des AS' X, so kann X die Metrikänderung auf alle EGP-Pfade a⇝b⇝Y, a⇝b⇝Z usw. übertragen. Es ist auch denkbar, dass sich einige Routen, welche ein Router von verschiedenen Routingprotokollen gelernt hat, gegenseitig widersprechen; in solchen Fällen regelt eine vorher definierte Priorisierung („administrative distance“) die letztendliche Entscheidung des Routers.
| Routing- Protokoll | Routing- Algorithmus | Shortest Path- Algorithmus | Einsatz | Metrik | Anmerkungen |
|---|---|---|---|---|---|
| BGP | Path-Vector | Bellman-Ford | EGP | Policies | de Facto-Standard, verhindert Schleifen |
| RIP | DV | Bellman-Ford | IGP | Hop-Count | Count-to-Infinity-Problem |
| OSPF | LS | Dijkstra | IGP | * | hierarchisches Routing |
| IS-IS | LS | Dijkstra | IGP | * | ISO-Standard, vglb. mit OSPF |
| EIGRP | DV | DUAL | IGP | * | Cisco-Standard |
Computernetzwerk | Telekommunikation
Směrování | Δρομολόγηση | Routing | Encaminamiento | Reititys | Routage | ניתוב | Routing | ルーティング | Routing | Encaminhamento | Маршрутизация | Routing | 路由