IP Routing

In einem gebridgten Netzwerk kann jeder Host in der flachen Hierarchie über eine eigene IP-Adresse erreicht werden. Diese Topologie ist für kleinere Netze durchaus geeignet, stösst aber bei grösseren Netzen schnell an ihre Grenzen, da eben auch keine hierarchische Struktur erstellt werden kann. Das folgenden Bild zeigt ein gebridgtes Netzwerk.

bridging

 

Die beste Wahl, ob grosses oder kleines Netz, ist den IP-Verkehr zwischen den logischen Netzen zu routen.

routing

 

Der Router macht seine Forwarding-Entscheidungen basierend auf dem Inhalt seiner Routing Tabelle, auch genannt forwarding information base (FIB).

routing table

Das Aussehen und die Formatierung einer Routing-Tabelle ist vom Hersteller abhängig. Der Inhalt der meisten Routing-Tabellen gleichen sich aber. Meistens sind Destination-, Route Mask-, Next Hop-, ein Metric- und ein Interface-Feld vorhanden.

Vier verschiedene „type of routes“ können in einer Routing-Tabelle gefunden werden:

  • Host routes: Eine Route zu einem Host mit einer Route-Maske von 255.255.255.255
  • Hierarchical network prefix routes: Eine Route zu einem Netzwerk mit einer Route Maske von grösser/gleich 1 Bit und kleiner/gleich 30 Bit
  • Default route: Eine Route die benutzt wird, wenn keine besonders definierte Route existiert. Dieser Route-Type hat eine Destination- und Route-Maske von 0.0.0.0. Eine Routing Tabelle kann mehrere solcher “Default Routen” beinhalten mit verschiedenen Werten bei den “Next Hops” und “Metric”.
  • Loopback Route: Die Loopback Route hat eine Destination-Adresse von 127.0.0.0 in der Routing Tabelle

 

Die vorangegangene Routing-Tabelle beinhaltete die folgenden Felder:

  • Destination: Die IP-Adresse des Zielnetzwerks oder –host
  • Route Maske: Die Routing Maske definiert, welche Bits der Zieladresse auf die Routing-Entscheidung Einfluss haben
  • Next hop: Die IP-Adresse des Routers, welcher auf dem Weg zum Ziel den nächsten Punkt darstellt
  • Metric: Ein Wert, der die Routing-Entscheidung beeinflusst
  • Type: Ein Wert, der den Route-Type bestimmt: DIR= direct (der Router ist direkt mit dem Zielnetzwerk verbunden) oder REM= remote (das Ziel ist nur über einen anderen Router erreichbar)
  • Source: Das Routing-Protokoll, welchem eine Route zugrunde liegt: MGMT= management (static routes), LOC=Local (direct routes), ICMP (dynamic route created by ICMP), RIP (dynamic route created by RIP), OSPF (dynamic route created by OSPF)
  • Age: Die Zeitdauer in Sekunden, seit der die Route zum letzten Mal refresht worden ist

 

Der Forwarding-Prozess

Erhält der Router ein Paket, überprüft er zuerst das Datagramm, indem er eine Prüfsumme über das erhaltene Paket bildet und danach mit der im IP-Datagramm enthaltenen Prüfsumme vergleicht. Ist die das Paket gültig, wird die Zieladresse des Paketes bestimmt. Ist das Paket für keines der am Router angeschlossenen Netzwerke bestimmt, muss das Paket weitergeleitet werden. Es gibt drei Möglichkeiten:

  • Die Zieladresse ist eine Unicast-Adresse – das können Klasse A, B oder C-Netze sein
  • Die Zieladresse ist eine Broadcast-Adresse
  • Das Ziel ist eine Multicast-Adresse – es handelt sich um eine Klasse D-Adresse

 

Ist die Zieladresse eine Unicast-Adresse, bestimmt der Router, über welches Interface das Paket weitergesendet werden soll und welches die IP-Adresse des “next-hop-routers” ist. Das time-to-live (TTL) Feld wird schrittweise vermindert und überprüft, ob sein Dezimalwert nicht 0 (null) ist. Das Paket wird verworfen, falls der TTL-Wert 0 ist. Das Paket wird wenn nötig fragmentiert und die Link-Layer-Adresse des Ziels bestimmt. Der Router bildet einen Link-Layer-Header und packt das IP-Paket darin ein, um es über das physikalische Medium zu transportieren.

Ist die Zieladresse eine Broadcast-Adresse, muss der Router bestimmen, ob es sich um einen “limited broadcast” oder um einen “directed broadcast” handelt. Handelt es sich um einen “limited broadcast” (255.255.255.255), kann das Paket nicht an ein anderes Interface weitergeleitet werden, es kann aber vom Router selbst verwendet werden. Ist das Datagramm ein “directed broadcast”, wird es wie eine Unicast-Adresse behandelt und zum Zielnetzwerk weitergeleitet, wo es einen Broadcast zu allen Hosts macht.

 

Bestimmen der optimalen Route

Erreicht ein Paket den Router, das weitergeleitet werden muss, ist es zuerst einmal nötig, das Interface und die Adresse des „next-hop Routers“ zu bestimmen, über den das Paket weitergeleitet werden soll. Ist das Paket für ein Netzwerk bestimmt, welches direkt an einem Interface des Routers angeschlossen ist, gibt es keinen „next-hop Router.
Für jedes IP-Interface, das auf dem Router definiert ist, muss die Netzwerkmaske bezogen auf die IP-Adresse des Routers und des Zielpaketes angewendet werden. Sind die Netzwerkteile der Adressen gleich, ist das Zielnetzwerk lokal und der Router muss das Paket nicht weiterleiten. In diesem Fall muss der Router die Hardwareadresse der Zieladresse bestimmen und das Paket am entsprechenden Port ausgeben.

Muss das Datagramm weitergeleitet werden, muss eine Prozedur(en) definiert werden, um auf einfache Weise den an meisten geeigneten Port sowie die IP-Adresse des „next-hop Routers“ herauszufinden. Diese Prozeduren reduzieren die gesamte Routingtabelle auf einige wenigen Routen. Diese Prozeduren werden auch „pruning rules“ genannt.

Regel 1: Basic Match
Vor der Anwendung dieser Regel entsprechen die „working set of route entries“ (die Möglicherweise zur Anwendung kommenden Routen) allen Einträgen in der Routingtabelle. Für jeden Eintrag in der Routing-Tabelle wird jetzt die Route Maske auf die Zieladresse des Datagrammes und den korrespondierenden Eintrag in der Routing Tabelle angewendet. Alle Einträge, ausgenommen diejenigen, in welchen der maskierte Teil der Netzwerkadresse in der Zieladresse und dem Eintrag in der Routingtabelle gleich sind, werden von den „working set of route entries“ entfernt. Default Routen werden nicht entfernt.

Regel 2: Longest Match
Nach der Anwendung der ersten Regel werden die übriggebliebenen Routen auf die Länge ihrer Route-Maske untersucht. Die Routen mit der längsten Maske verbleiben in der „working set of route entries“.

Regel 3: Weak Type of Service
Die meisten Router unterstützen diese Funktion nicht, obwohl neuere Routing-Protokolle wie OSPF diese Funktion unterstützen. Der IP-Header enthält ein Feld – das TOS (Type of Service)-Feld, welches „precedence“ und „type of service“-Funktionen bietet. Diese TOS-Flags können beeinflussen, wie Routing-Entscheidungen gefällt werden. Es sind die folgenden Flags:

D – Delay
T - Throughput
R – Reliability
C – Cost

Die drei Bits, welche das „precendece“-Feld bilden, beinflussen die Behandlung des Paketes, während es sich in der Queue des Routers befindet. Das „precedence“-Feld erlaubt es dem Router, einige Pakete bei der Weiterleitung bevorzugt zu behandeln. Da das „precedence“-Feld nur das „Queing“ beeinflusst, sollte es nicht benutzt werden, um die Route-Entscheidung zu beeinflussen.

Jede Route in der Routingtabelle kann ein TOS-Feld beinhalten. Die dritte Regel wird jetzt folgendermassen angewendet:
Die TOS-Flags (Bits 3-6 im TOS-Feld) im IP-Datagramm werden mit den TOS-Feldern bei den in Frage kommenden Routen verglichen. Wird eine (oder mehrere) Übereinstimmung gefunden, werden alle Routen ausser dieser (oder diesen) von den „working set of route entries“ gelöscht. Wird keine Übereinstimmung gefunden, werden alle Routen mit Ausnahme derjenigen, bei denen das „type of service“-Feld 0000 beträgt, von den „working set of route entries“ gelöscht.

Router und Protokolle, welche das „Type of Service“-Routing nicht unterstützen, setzen die TOS-Flags auf 0000.

Regel 4: Best Metric
Die Route mit dem besten Metric-Feld wird verwendet – alle anderen werden von der „working set of route entries“ gelöscht.

Regel 5: Vendor Policy
Nach der Anwendung dieser vier Regeln, sollten sich die in Frage kommenden Routen auf eine Route oder einige wenige reduziert haben. Kommen immer noch mehrere Routen in Frage, wird die Entscheidung, welche Route jetzt gewählt werden soll, dem Routerhersteller überlassen. Er definiert für diesen Fall eine Vorgehensweise, z.B. soll die am wenigstens benutzte Route verwendet werden.

Nach der Anwendung aller dieser Regeln sollten noch eine oder aber keine Route in den „working set of route entries“ vorhanden sein. Ist keine Route vorhanden, wird das Paket verworfen und ein ICMP-Error generiert. Im anderen Fall wird das Paket in ein Link-Layer-Protokoll verpackt und an die Hardwareadresse des „next-hop Routers“ weitergeleitet.

 

Dynamic Routing Protocols

Es gibt verschiedene Klassifikationen innerhalb der Routing-Protokolle. Man unterscheidet zwischen „interior“- und „exterior“ Routing-Protokollen, sowie zwischen „link-state“- und „distance-vector“-Protokollen.

Interior-Routing-Protokolle werden in Intranets verwendet, die unter der Kontrolle eines oder mehrerer Administratoren stehen. Exterior-Routing-Protokolle routen Pakete innerhalb des Internets. Wie schon erwähnt gibt es auch noch das „distance vector“- sowie das „link-state“ Protokoll.

Ein „distance-vector routing protocol“ verfolgt Abstände (hop count or cost). Ein „link state routing protocol“ verfolgt die Anwesenheit direkter Nachbarn und sendet Updates über seine Nachbarn an alle seine Nachbarn. Mehrere Interior Routing Protokolle werden heute in einem TCP/IP-Netzwerk verwendet. So z.B. RIPv1, RIPv2, OSPF, IGRP und E-IGRP. RIP und OSPF sind die am meisten verwendeten Protokolle. RIP ist ein „distance-vector routing protocol“, wogegen OSPF ein „link-state routing protocol“ ist. RIP liefert bei einem Update keine Subnetz-Informationen mit, wogegen OSPF dies tut.

 

RIP

RIP steht für Routing Information Protocol. Die erste Version wurde 1988 entwickelt – es ist aufgrund seines Alters das am weitesten verbreitete Protokoll. Es ist einfach im Gebrauch und einfach in der Implementation. Drei Dinge sind zu tun. Als erstes werden das „route broadcast“ und das „update interval“ festgelegt. Als nächstes müssen die Nachbar-Router definiert werden. Als drittes und letztes muss RIP eingeschaltet werden.

Wie schon erwähnt, liefert RIP bei einem Update keine Infos über Subnetzmasken mit. Erhält also ein Router einen RIP-Update, werden nur die Subnetzmasken von Netzwerken richtig gesetzt, die auf einem Interface des Routers definiert sind. Für eine Netzwerkadresse, die auf keinem Interface des Routers definiert ist, vermutet der Router dann einfach die zugehörende Netzwerkmaske, also z.B. bei einer Klasse C-Adresse die Maske 255.255.255.0.

 

Open Shortest Path First (OSPF)

OSPF ist ein komplizierteres Protokoll als RIP. OSPF kann sehr vielseitig konfiguriert werden. Einige Konfigurations-Optionen:

  • OSPF areas
  • area route summarization
  • enbabling OSPF on arouter or on specific interfaces
  • virtual links
  • metrics
  • importation of routing information from other routing protocols
  • exportation of routing information from other routing protocols
  • OSPF interface timers, such as hello interval and the dead interval
  • Authentication

OSPF ist ein „link-state routing protocol. Kommt ein neuer Router zu einem OSPF basierenden Netzwerk hinzu, wird eine Datenbank mit anderen Routern im Netzwerk ausgetauscht. Diese Datenbank bildet die Netzwerktopologie ab. Basierend auf den Informationen, die in dieser Datenbank enthalten sind, wird die Routingtabelle aufgebaut. Von jetzt an steht der Router in Kontakt mit seinen Nachbarn. Verliert der Router den Kontakt zu seinem Nachbarn, merkt dies der Nachbar unverzüglich und sendet eine Info zu allen OSPF-Routern, dass er keinen Kontakt mehr zu seinem Nachbarn hat. Alle Router passen jetzt ihre Datenbanken den neuen Gegebenheiten an.
Einer der Vorteile die OSPF gegenüber RIP hat, besteht darin, dass die link-state Datenbank Informationen über alle Subnetze beinhaltet, die die verschiedenen Routen benutzen.

Wird ein Interface als „down“ markiert, müssen andere Router davon benachrichtigt werden und die Routingtabellen müssen neu berechnet werden. Um diese Broadcasts und Neuberechnungen der Tabellen möglichst gering zu halten, werden sogenannte Areas definiert. Eine Area ist die Grenze für solche link-state Benachrichtigungen. Ein OSPF-Router innerhalb dieser Grenze enthält die vollständige Topologie der Area plus einige zusätzliche Infos über die Grenze der Area hinaus. Daneben existieren noch „area border router“. Diese Router dienen als Gateways zwischen Backbone Areas und anderen, nicht Backbone Areen.

 

ospf with areas

 

Statisches Routing

RIP und OSPF sind Beispiele von dynamischen Routing-Protokollen. Dabei müssen ständig Informationen zwischen den einzelnen Routern ausgetauscht werden. Dieser Informationsaustausch ist die Basis für die Konstruktion der Routing-Tabellen.

Eine statische Route dagegen wird von einem Netzwerkadministrator definiert und ändert sich nicht bis zu einer erneuten Intervention des Administrators. Eine statische Konfiguration kann die folgenden Vorteile haben:

  • Kein Traffic Overhead dank statischem Routing. Das Routing-Update in einem RIP-Netzwerk kann ziemlich viel Verkehr erzeugen
  • Statische Routen können in OSPF importiert werden
  • Statische Routen können einfacher sein als komplizierte, dynamische Routen

 

Es gibt auch einige Gründe, auf ein statisches Routing zu verzichten oder es auf ein Minimum zu beschränken:

  • Statisch ist statisch - in einem Fehlerfall können statische Routen nicht einfach dynamisch geändert werden
  • Die Konfiguration ist eine mühevolle und schwierige Arbeit

 

ICMP Routing

ICMP, das Internet Control Message Protokoll verwendet einen Nachrichtentyp, mit dessen Hilfe Pakete vom einem nicht-optimalen Weg auf einen optimalen Weg umgeleitet werden können. Dieser Nachrichtentyp ist bekannt als ICMP Redirect.

icmp redirect

  • Type: Der Wert ist 5 für eine Redirect Nachricht
  • Code: 0 für einen Netzwerk-Redirect, 1 für einen Host-Redirect, 2 für TOS und Netzwerk-Redirect und 3 für TOS und Host-Redirect
  • Checksum: Selbsterklärend
  • Router IP Adresse: Die IP-Adresse des Routers, der eine bessere Route zum Ziel kennt als die ursprünglich benutzte

 

Direktes Routing

Wann immer ein Router oder eine Workstation ein Paket zu einem Device in einem IP-Netzwerk, das lokal auf einem Router oder einer Workstation definiert ist, schickt, muss die IP-Adresse in die entsprechende Hardware-Adresse des Zielortes umgesetzt werden.

In einem physikalischen Netzwerk, das mehrfachen Zugriff erlaubt, müssen Mechanismen bestehen, mit denen IP-Adressen auf Hardware-Adressen abgebildet werden können und umgekehrt. In einem Ethernet heissen diese Protokolle ARP (Address Resolution Protocol) und Reverse ARP (RARP).

IP Router leiten Pakete aufgrund ihrer Informationen in den Routing-Tabellen über die IP-Netzwerke weiter. Muss das Paket an den nächsten Router (next hop) weitergeleitet werden, muss das IP-Datagramm zunächst vom Router in ein Link-Layer Header eingepackt werden und danach an die Hardware-Adresse des “next hop” geschickt werden. Das gleiche Vorgehen gilt, falls das Zielnetzwerk lokal am Interface eines Routers definiert ist.

RFC 826 beschreibt ARP, während RFC 903 RARP definiert.