Routing

Routing [ˈraʊtɪŋ] (amerik.)/[ˈruːtɪŋ] (brit.) oder Verkehrslenkung bezeichnet in der Telekommunikation 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 Verfahren unterschieden:

• feste Verkehrslenkung
• alternative Verkehrslenkung
• adaptive Verkehrslenkung

Routing von Paketen

Beim paketvermittelten Routing wird dafür gesorgt, dass logisch adressierte Pakete aus dem Ursprungs-Netz heraus kommen und in Richtung ihres Ziel-Netzes weitergeleitet werden. Routing ist die Basis des Internet. Ohne Routing würde das Internet nicht existieren und alle Netze wären autonom. Die Datenpakete können dabei viele verschiedene Zwischen-Netzwerke auf dem Weg zu ihrem Ziel passieren. Routing ist eine wesentliche Aufgabe der dritten Schicht des OSI-Modells.

Hubs und Switches leiten Daten nur im lokalen Netzwerk weiter, wohingegen der Router auch Nachbar-Netzwerke 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 Netzwerks kennen. In kleinen Netzwerken kann das Routing sehr einfach sein und wird oft per Hand konfiguriert. Man spricht dann auch von statischem Routing. Große Netzwerke 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 Routingtabelle die bestmögliche Route zu bestimmten Netzwerken und die dazugehörigen Routing-Metriken.

Der kürzeste Weg kann zum Beispiel mit dem Algorithmus von Dijkstra gefunden werden.

Source Routing

In lokalen Netzen wird häufig das sogenannte Source Routing verwendet. Die sendende Station trägt die Adresse des nächsten Netzknotens in den Kopf der Nachricht ein. Jeder folgende Netzknoten adressiert den darauffolgenden Knoten direkt im Kopf der Nachricht. Dieses Verfahren wird z.B. im Usenet Mail Service verwendet.

Routing-Protokoll

Routing-Protokolle sorgen für den Austausch von Routing-Informationen zwischen den Netzwerken 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 nächsten am 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, kommt das Paket trotzdem früher oder später am Ziel an.

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 Netzteile weiträumig umgangen werden.

Dem Ausfall des Standardgateways, das ist meist der erste Router vom Sender aus gesehen, wirkt dynamisches Routing jedoch nicht entgegen. Hierfür wurden HSRP, VRRP und CARP entwickelt. Da ein Host im Normalfall keine Alternative zum Standardgateway hat, ist dies der wichtigste Router der Route.

Routing-Algorithmen

Routing-Algorithmen benutzen zwei grundlegende Verfahrensweisen:

• Teile deinen Nachbarn mit, wie die Welt aussieht:Distanzvektor-Protokolle wie z.B. das Routing Information Protocol (RIP).
• Teile der Welt mit, wer deine Nachbarn sind: Link-State-Routing-Protokolle wie z.B. OSPF

Weiterhin können Routing-Algorithmen im wesentlichen nach Ihrer Zentralisation und Ihrer Dynamik beurteilt werden:

• Zentralisation: Wo ist der Algorithmus lokalisiert? Zentral in einem Netzkontrollzentrum oder dezentral verteilt auf die Vermittlungsknoten?
• Dynamik: Ist das Verfahren nicht adaptiv, d.h. die Routingtabelle in dem Vermittlungsknoten bleibt über längere Zeit konstant, verglichen mit der Verkehrsänderung. Oder ist das Verfahren adaptiv, d.h. die Routingentscheidungen hängen vom Zustand des Netzes ab. (Topologie,Lastverhältnisse)

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:

• zentralisiertes Routing
• Static-Routing
• Delta-Routing
• Broadcast-Routing
• Hot Potato
• Backward Lerning, verteiltes adaptives Routing (RIP, OSPF, IS-IS...)

Die Verfahren im Einzelnen

Statisches Routing:

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 Wichtung. Vor Weiterleitung eines Paketes wird der entsprechende Eintrag aus der Tabelle gewählt und auf eine der möglichen Leitungen gegeben. Die Wichtung wiederspiegelt hier die Wahrscheinlichkeit, das 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 Zustandinformationen und berechnet aufgrund dieser Kenntnis über das gesamte Netz die optimale Weglänge zwischen allen Knoten. Danach übermittelt das RCC jedem Knoten eine Routingtabelle, anhand der Knoten seine Routing-Entscheidungen trifft.

Vorteil:

• RCC hat theoretisch die vollständige Übersicht und kann somit 'perfekte' Entscheidungen treffen
• Knoten müssen keine aufwendigen Berechnungen durchführen

Nachteil:

• Berechnung dauert für große Netze u.U. sehr lange
• Ausfall des RCC lähmt das ganze Netz (sofern kein Back-up Rechner)
• globale Inkonsistenzen mgl., da Knoten nahe am RCC wesentlich früher die neuen Routingtabellen erhalten als die weiter entfernten
• starke Belastung des RCC durch die zentrale Funktion

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
• Hot Potato
• Backward Learning
• Delta-Routing

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:

• Erkennung von Duplikaten von Paketen, durch Nummerierung der Pakete
• Kontrolle der Lebensdauer von Paketen durch zählen der zurückgelegten Teilstrecke (hops)
• Selektives Fluten (Weiterleitung nicht auf allen, sondern nur auf einigen Leitungen)
• Random Walk (zufällige Auswahl einer Leitung)

Hot Potato

Jeder Knoten versucht, eingehende Pakete so schnell wie mgl. 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:

• Auswahl der besten Übertragungsleitung nach statischem Verfahren, solange deren Warteschlangenlänge unter einer bestimmten Schwelle bleibt.
• Auswahl der Übertragungsleitung mit der kürzesten Warteschlange, falls deren Gewicht zu niedrig ist. (siehe stat. Routing weiter oben)

Backward Learning

Bei diesem Verfahren müssen folgende Informationen im Paket gespeichert werden:

• Identifikation des Quellknotens
• Zähler der mit jeder zurückgelegten Teilstrecke (hop) um eins erhöht wird

Wenn ein Knoten nun ein Paket erhält, kann er die Hopanzahl erkennen und weiß über welchen Eingang er es erhalten hat. Damit kann jeder Knoten aus den erhaltenen Paketen schließen, über welchen Weg er die anderen Knoten mit der minimalen Anzahl an Hops erreichen kann. Ein Eintrag in der Routingtabelle wird ersetzt, wenn ein Paket mit einer niedrigeren Hopanzahl den Knoten erreicht, als in der Tabelle eingetragen ist. Die Einträge werden ober auch dann aktualiseirt, wenn eine gewisse Zeit lang kein Paket mehr mit einer bestimmten Hopanzahl von dem jeweiligen Knoten erhalten wurde. Es werden also in festen Zeitabständen Lernperioden zugelassen, in denen bessere Einträge mit schlechteren überschrieben werden, wenn diese eine gewisse Zeit alt sind.(Dann muß man davon ausgehen, dass die bessere Verbindung nicht mehr existiert und die nächstbeste wählen) Daraus ergeben sich folgende Probleme:

• wärend der Lernperiode ist das Routing nicht optimal
• bei kurzen Lernperioden (Einträge werden schneller zum schlechteren aktualisiert) nehmen viele Pakete Wege unbekannter Qualität
• bei langen Lernperioden ergibt sich ein schlechtes Anpassungsverhalten an die Situation im Netz

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 k besten Wege von Knoten i zu Knoten j (a für alle Knoten i,j), 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 Routin-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:

• Anzahl Hops
• Geschätzte Verzögerung in Millisekunden
• Geschätzte totale Anzahl von Paketen, die entlang des Weges warten

Diese Schätzungen werden gewonnen aus der Zeit/Entfernung zu den Nschbarn (z.B.: mittles speziellen Echo-Paketen mit Zeitstempel) und/oder Schätzungen der Nachbarn. Ein Austausch der Routing-Informationen kann entweder synchron in bestimmten Aktualisierungsintervallen oder asynchron bei signifikanten Änderungen erfolgen. Zu diesem Verfahren gehören unter Anderem das:

• Distance Vector Routing
• Link State Routing

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:

• Entdecken neuer Nachbarn mittels HELLO-Paket
• Messung der Verzögerung bzw. der Kosten zu jedem Nachbarn, mittels ECHO-Paket
• Erstellung eines LINK-STATE-Pakets mit allen gelernten Daten (Sender,Liste der Nachbarn mit Verzögerung, Alter...),welches periodisch oder ereignisgesteuert (z.B.: neuer Nachbar, Ausfall,....) erzeugt wird
• Versenden dieses Pakets an alle Nachbarn (prinzipiell mittels Fluten, aber mit Verfeinerung: Vernichten von Duplikationen, Zerstören der Information nach gewissem Alter etc.)
• Berechnung des kürzesten Pfades zu allen anderen Routern (z.B.:Dijkstra)

Dieses Verfahren ist sehr rechenaufwendig, aber Optimierungen dieses Verfahrens existieren und gehören dann zu der jeweiligen Topologie usw. des Netzes.

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 mgl.(Regionen,Cluster,Zonen,Gruppen,...)

Metrik

Eine Routing-Metrik ist ein Wert, mit dessen Hilfe ein Routing-Algorithmus feststellen kann, ob eine Route im Vergleich zu einer anderen besser ist. (Bei mehreren möglichen Routen wird eine Route mit kleiner Distanz im Sinne der Metrik bevorzugt.) Metriken können Informationen wie z.B. Bandbreite, Verzögerung, Hop Count, Pfadkosten, Last, MTU, Verlässlichkeit und Kommunikationskosten berücksichtigen. In der Routing-Tabelle werden nur die bestmöglichen Routen gehalten, während Link-State- oder topologische Datenbanken alle anderen Informationen beinhalten.

Interior Gateway Protokolle (IGP) - Exterior Gateway Protokolle (EGP)

Abhängig davon, ob der Router Teil eines autonomen Systems ist oder gar dessen Grenze bildet, verwendet er Routing-Protokolle aus verschiedenen Klassen:

• Ad hoc Routing-Protokolle werden in Netzwerken mit wenig oder keiner Infrastruktur verwendet.
  • OLSR findet meist Verwendung im mobilen Bereich
• Interior Gateway Protocols (IGPs) tauschen Routing-Informationen in einem einzelnen autonomen System aus. Häufig verwendet werden:
  • IGRP/EIGRP (Interior Gateway Routing Protocol/ Enhanced IGRP)
  • OSPF (Open Shortest Path First)
  • RIP (Routing Information Protocol)
  • IS-IS (Intermediate System to Intermediate System)

• Exterior Gateway Protocols (EGPs) regeln das Routing zwischen verschiedenen autonomen Systemen. Dazu gehören:
  • EGP (mit dem alten Exterior Gateway Protocol wurden früher die Internet-Backbones verbunden. Es ist inzwischen veraltet)
  • BGP (Border Gateway Protocol: seit 2002 in der Version BGP4)

Siehe auch

• CIDR Classless Inter-Domain Routing
• NAT (Network Address Translation)
• MPLS Multiprotocol Label Switching
• XORP
• Problem des Handlungsreisenden
• Kürzeste-Wege-Algorithmus von Dijkstra