Routing

Grundidee und Bedeutung

Routing bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme in Rechnernetzen. Besonders in paketvermittelten Datennetzen muss man Routing und Forwarding unterscheiden: Routing bestimmt den gesamten Weg eines Nachrichtenstroms durch das Netzwerk; Forwarding ist die Entscheidung eines einzelnen Netzknotens, über welchen Nachbarn er eine konkrete Nachricht weiterleitet. Im Alltag werden beide Begriffe oft gemeinsam als „Routing“ bezeichnet.

Routing ist eine Grundlage des Internets. Ohne Routing könnten Netze nicht über ihre Grenzen hinweg miteinander kommunizieren. Hubs und Switches leiten Daten nur im lokalen Netz weiter; Router kennen auch benachbarte Netze und können Pakete zwischen Netzen transportieren. Im Internet findet Routing üblicherweise auf der IP-Schicht statt; im ISO/OSI-Modell gehört es zu den wesentlichen Aufgaben der dritten Schicht.

Bei leitungsvermittelten Verbindungen wird ein Übertragungskanal für die ganze Dauer der Verbindung gewählt, sodass alle Nachrichten denselben Weg nehmen. Bei paketvermittelter Datenübertragung wird der Weg dagegen für jedes Paket von jedem Netzknoten neu bestimmt. Grundsätzlich unterscheidet der Artikel statisches Routing, alternatives Routing und adaptives Routing.

Paketweiterleitung und Tabellen

Beim paketvermittelten Routing werden logisch adressierte Datenpakete aus dem Ursprungsnetz heraus und in Richtung Zielnetz weitergeleitet. Dabei können sie viele Zwischennetze passieren. Kleine Netze werden oft per Hand konfiguriert; das nennt man statisches Routing. Große Netze haben häufig eine komplexe und veränderliche Topologie, also eine Struktur aus Knoten und Verbindungen. Dort wird meist dynamisches Routing verwendet.

Router können die besten Wege nicht für jedes Paket vollständig neu berechnen. Deshalb speichern sie in einer oder mehreren Routingtabellen die bestmöglichen und teilweise weitere Routen zu bestimmten Netzen sowie die dazugehörigen Routing-Metriken. Eine Metrik ist ein Bewertungswert für eine Route. Der beste Weg ist oft der kürzeste Weg; er kann zum Beispiel mit dem Algorithmus von Dijkstra gefunden werden.

Aus der Routingtabelle berechnet ein Router eine Forwardingtabelle. Sie enthält Einträge der Form Zieladressmuster→Ausgabeschnittstelle. Für jedes neu eingetroffene Paket schlägt der Router dort nach, über welche Schnittstelle er es weiterleiten muss.

Routing-Protokolle und Algorithmen

Routing-Protokolle tauschen Routing-Informationen zwischen Netzen aus und ermöglichen Routern, ihre Routingtabellen dynamisch aufzubauen. Traditionelles IP-Routing verwendet Next-Hop-Routing: Ein Router sendet ein Paket an den Nachbarrouter, den er für den günstigsten nächsten Schritt zum Zielnetz hält. Der Router muss nicht den gesamten weiteren Weg kennen.

Dynamisches Routing kann komplex sein, macht das Internet aber flexibel. Seit der Einführung von IP im Jahr 1983 trug es zum exponentiellen Wachstum des Internets bei. Wenn Teile eines Backbones ausfallen, können innerhalb von Sekunden Alternativrouten verbreitet und betroffene Bereiche umgangen werden. Gegen den Ausfall des Standardgateways hilft dynamisches Routing jedoch normalerweise nicht, weil ein Host meist keine Alternative zu diesem ersten Router hat. Dafür wurden HSRP, VRRP und CARP entwickelt.

Routing-Algorithmen arbeiten vor allem nach zwei Grundideen. Link-State-Routing-Protokolle wie OSPF sorgen dafür, dass jeder Router nach einiger Zeit die vollständige Topologie des Netzwerks kennt und sich die kürzesten Wege selbst berechnet. Distanzvektor-Protokolle wie RIP teilen Nachbarn mit, wie „gut“ ein Router an Zielknoten angebunden ist; die Lösung des Kürzeste-Wege-Problems wird dadurch auf mehrere Router verteilt. Pfadvektorprotokolle wie BGP sind eine verallgemeinerte Form der Distanzvektorprotokolle mit verbesserter Schleifenerkennung.

Algorithmen lassen sich außerdem nach Zentralisation und Dynamik beurteilen. Zentralisation fragt, ob das Verfahren in einem Netzkontrollzentrum oder verteilt auf die Vermittlungsknoten liegt. Dynamik fragt, ob Routingtabellen über längere Zeit konstant bleiben oder sich adaptiv an Topologie und Last anpassen. Dabei entsteht ein Zielkonflikt: Zentrale, nicht adaptive Verfahren belasten das Netz weniger mit Routingnachrichten, verwenden aber eher veraltete oder unvollständige Informationen. Adaptive und verteilte Verfahren verbreiten bessere Netzinformationen, verursachen aber mehr Nachrichtenverkehr.

Wichtige Verfahren

Beim statischen Routing enthält jeder Knoten eine Tabelle mit Einträgen für mögliche Zielknoten. Darin steht, welche Übertragungsleitung die beste, zweitbeste usw. ist, jeweils mit einer Gewichtung. Das Verfahren ist einfach und nicht adaptiv.

Beim zentralisierten Routing gibt es ein Routing Control Center (RCC). Jeder Knoten sendet periodisch Zustandsinformationen dorthin, etwa aktive Nachbarn, Warteschlangenlänge oder Verkehrsmenge seit der letzten Meldung. Das RCC berechnet mit seiner Gesamtübersicht optimale Wege und verteilt Routingtabellen. Vorteile sind theoretisch perfekte Entscheidungen und wenig Rechenaufwand für die Knoten. Nachteile sind lange Berechnungen in großen Netzen, die starke Belastung des RCC, mögliche globale Inkonsistenzen und die Gefahr, dass ein Ausfall des RCC das ganze Netz lähmt, falls kein Backup vorhanden ist.

Beim isolierten Routing entscheidet jeder Knoten nur anhand selbst gesammelter Informationen; Routing-Informationen werden nicht ausgetauscht. Dazu zählen Broadcast Routing, Hot Potato, Backward Learning und Delta Routing. Beim Broadcast Routing wird ein Paket an alle Knoten gesendet. Eine einfache Variante ist das Fluten: Jedes eingehende Paket wird auf allen Leitungen weitergegeben, außer auf der Leitung, über die es kam. Eindämmung ist durch Duplikaterkennung, Hop-Zähler, selektives Fluten oder Random Walk möglich.

Hot Potato leitet Pakete so schnell wie möglich weiter, oft über eine freie oder besonders kurze Warteschlange. Das ermöglicht schnelle Entscheidungen, geringen Rechenaufwand und gute Leitungsauslastung. Bei steigender Last wird das Routing aber weniger optimal, und Pakete können im Kreis laufen. Backward Learning nutzt im Paket gespeicherte Informationen über den Quellknoten und einen Hop-Zähler. Ein Knoten lernt daraus, über welchen Eingang andere Knoten mit minimaler Hopzahl erreichbar sind. Problematisch sind nicht optimale Lernperioden und der Konflikt zwischen schneller Anpassung und stabilen Einträgen.

Delta Routing kombiniert zentralisiertes und isoliertes Routing. Jeder Knoten misst periodisch Kosten seiner Übertragungsleitungen, etwa Verzögerung, Auslastung oder Kapazität, und sendet sie an das RCC. Das RCC berechnet die k besten Wege von Knoten i zu Knoten j für alle Knoten i, j, wobei nur Wege mit unterschiedlicher erster Leitung berücksichtigt werden. Ein Knoten kann dann zwischen äquivalenten Wegen zufällig oder nach aktuellen Kosten wählen.

Beim verteilten adaptiven Routing tauscht jeder Knoten periodisch Routing-Informationen mit Nachbarn aus. Einträge können Hops bis zum Ziel, geschätzte Verzögerung in Millisekunden oder die geschätzte Zahl wartender Pakete entlang des Weges enthalten. Dazu gehören Distance Vector Routing und Link State Routing.

Metriken und Protokollklassen

Eine Routing-Metrik ist ein numerischer Wert, mit dem ein Routing-Algorithmus Routen vergleichen kann. Metriken können Datenübertragungsrate, Verzögerung, Hop Count, Pfadkosten, Last, MTU, Verlässlichkeit und Kommunikationskosten berücksichtigen. Wenn Distanz die entscheidende Metrik ist, wird die Route mit dem kleinsten Wert gewählt. Nicht immer bedeutet ein kleinerer Wert aber „besser“, da zum Beispiel höhere Bandbreite durch einen höheren Metrik-Wert dargestellt werden kann. RIP verwendet beispielsweise nur den Hop-Count und berücksichtigt damit etwa die Bandbreite nicht.

Distance-Vector-Protokolle beschreiben Erreichbarkeit durch Entfernung und Richtung. Die Metrik wird in der Anzahl zu passierender Knoten ausgedrückt; üblicherweise wird der Bellman-Ford-Algorithmus verwendet. Bei Topologieänderungen berechnen Router betroffene Wege neu und verbreiten Änderungsmeldungen. In der Praxis konvergiert dieses Verfahren bei vielen Routern wegen des Count-To-Infinity-Problems oft zu langsam. RIP gehört zu dieser Klasse.

Link-State-Protokolle geben Routern einen vollständigen Überblick über die Topologie einer Area. Jeder Router besitzt dieselbe Topologie-Datenbank, vergleichbar mit einem Stadtplan, und berechnet mit dem Shortest-Path-First-Algorithmus von Dijkstra optimale Pfade. Hellopakete stellen Kontakt zu Nachbarroutern her. Link-State-Updates werden bei Topologiewechseln gesendet, etwa wenn ein Router neu entdeckt wird, ausfällt, sich Verbindungskosten ändern oder periodisch alle 30 Minuten. OSPF und IS-IS gehören dazu.

Hierarchisches Routing teilt große Netze in Regionen. Knoten kennen vor allem ihre eigene Region; besondere Knoten dienen als Schnittstellen zu anderen Regionen. In sehr großen Netzen sind weitere Hierarchien wie Regionen, Cluster, Zonen oder Gruppen möglich.

Routing im Internet

Im Internet unterscheidet man Intradomain-Routing und Interdomain-Routing. Intradomain-Routing findet innerhalb eines autonomen Systems (AS) statt und verwendet Interior Gateway-Protokolle (IGP). Dabei steht meist die technisch effiziente Nutzung des Netzwerks im Vordergrund, typischerweise entlang kürzester Pfade. Die Optimierung des Routings unter Berücksichtigung des realen Datenübertragungsbedarfs heißt Traffic Engineering.

Interdomain-Routing bezeichnet Routing zwischen autonomen Systemen. Es verwendet Exterior Gateway-Protokolle (EGP), fast immer BGP. Da es zwischen Providern stattfindet, steht häufig die finanziell effiziente, profitorientierte Nutzung im Vordergrund. Ein autonomes System gibt nicht allen Nachbarn dieselben Routeninformationen. Welche Informationen ausgetauscht werden, wird zuerst vertraglich festgelegt und dann in Routern konfiguriert; das nennt man Policy-basiertes Routing.

Beim IP-Routing innerhalb eines gemeinsamen Netzes wird nach ARP beziehungsweise NDP die zur IP-Adresse passende MAC-Adresse verwendet. Liegen Sender und Empfänger in verschiedenen Netzen, wird ein Router benötigt. Auf jedem Abschnitt ändert sich die Schicht-2-Adressierung: Ziel-MAC und Quell-MAC werden jeweils für den nächsten Hop angepasst. Die IP-Adressen, Ports und Nutzdaten bleiben dagegen auf Schicht 3 unverändert, bis das Paket sein Zielnetz erreicht. Hin- und Rückroute müssen nicht identisch sein.

Router verwenden oft gleichzeitig Protokolle verschiedener Klassen. IGPs wie IGRP/EIGRP, OSPF, IS-IS, RIP oder R-SMLT tauschen Informationen innerhalb eines autonomen Systems aus. EGPs regeln Routing zwischen autonomen Systemen; BGP, seit 2002 in Version BGP4, ist weltweit der De-facto-Standard, während das alte EGP veraltet ist. Ad-hoc-Routing-Protokolle werden in Netzen mit wenig oder keiner Infrastruktur genutzt, etwa OLSR im mobilen Bereich und AODV in kleineren Netzen mit hauptsächlich statischem Traffic. Wenn Protokolle widersprüchliche Routen liefern, entscheidet eine vorher festgelegte Priorisierung, die Administrative Distanz.