4    Routing Protokolle

 
4.1 ALLGEMEIN 
4.2 ROUTING IN AD HOC NETZWERKEN
        4.2.1 Distance-Vector-Routing-Protokolle
        4.2.2 Link-State-Routing-Protokolle
        4.2.3 On-Demand Routing Protokolle
        4.2.4 Zusammenfassung
[prev]
Inhalt
[next]

4.1 Allgemein

In einem Netzwerk kennt ein beliebiger Teilnehmer, der ein IP-Datenpaket senden will zwar die Adresse des Empfängers, nicht aber den Weg dorthin. Jede Station auf dem Weg des Datenpakets zum Empfänger muss eine Entscheidung über die Wahl des weiteren Weges fällen. Dieser Vorgang wird als Routing bezeichnet. Die Wahl einer bestimmten Route ist von verschiedenen Kriterien abhängig. Der Sender kann diese Aufgabe z.B. auch einem Standard-Router übergeben, der für die Zustellung von Datenpaketen in andere Netze zuständig ist.
Zwischen zwei Hosts liegen oft mehrere Router. Jeder dieser Router verfügt über eine so genannte Routing-Tabelle. Auf Grund derer wird die nächste Station für das Datenpaket bestimmt.
Ein Routing-Algorithmus legt ein Verfahren fest, nach dem diese Routing-Tabellen in den beteiligten Routern aufgebaut werden. Außerdem legt der Algorithmus eine eindeutige Metrik fest, nach derer der nach bestimmten Kriterien optimale Weg zwischen Quelle und Ziel bestimmt wird.
Grundsätzlich unterscheidet man statisches (nicht-adaptives) und dynamisches (adaptives) Routing.

 

Statisches Routing

Statische Routing-Algorithmen sind eigentlich keine Algorithmen, sondern genau genommen tabellarische Zuordnungen, die der Netzwerk-Administrator bei der Einrichtung des Netzwerks macht. An diesen Zuordnungen ändert sich nichts, es sei denn, der Administrator nimmt eine Änderung vor. Algorithmen, die statische Router verwenden, sind einfach zu entwerfen und eignen sich gut für Umgebungen in denen der Datenverkehr im Netzwerk relativ vorhersehbar ist und die Netzstruktur sich einfach gestaltet. Der Nachteil beim statischen Routen liegt aber eben in dieser Starrheit. Ändert sich z.B. die Netzstruktur, muss der Administrator alle Routing-Tabellen manuell aktualisieren. Unter Linux kann man z.B. mit „iproute“ bzw. „iproute2“ Routing-Tabellen einrichten und verändern.
 

Dynamisches Routing

Die meist vorherrschenden Algorithmen sind jedoch dynamische Routing-Algorithmen. Diese passen ihre Routing-Tabellen dynamisch an die jeweilige Netzwerksituation an, indem sie Routing-Aktuallisierungsnachrichten, welche die Gesamte oder nur Teile der Routing-Tabelle enthalten, von anderen Routern auswerten. Wenn eine solche Nachricht eine Änderung am Netzwerk mitteilt, werden die Routen durch die Routing-Software erneut berechnet und es werden neue evtl. Routing-Aktualisierungsnachrichten versendet um die Routing-Tabellen zu aktualisieren.

Gerade bei Ad Hoc Netzwerken ist das wichtig, da solche Netzwerke häufig eine hohe Dynamik besitzen und sich die Netzwerkstruktur und somit die Routing-Tabellen sehr schnell ändern können.
 
 
 

4.2 Routing in Ad Hoc Netzwerken

Die dynamischen Routing-Protokolle, welche auch in Ad Hoc Netzwerken eingesetzt werden lassen sich in sich nach ihren jeweiligen Routing-Strategie in drei Gruppen einteilen.

4.2.1 Distance-Vector-Routing-Protokolle

Beim Distance-Vector-Routing führt jeder Router eine Routing-Tabelle, auf deren Grundlage er die beste bekannte Entfernung zu jedem Ziel und die zu benutzende Route zu diesem Ziel ermittelt. Die Einträge in der Tabelle umfassen zwei Teile, nämlich die bevorzugte Ausgangsleitung zu einem bestimmten Ziel und die geschätzte Zeit bzw. Entfernung (z.B. in Hops) zu diesem Ziel. Aktualisiert werden die Routing-Tabellen, indem von Zeit zu Zeit jeder Router an jeden Nachbarn eine Liste mit den geschätzten Entfernungen jedes bekannten Ziels sendet. Anhand der empfangenen Daten können die Router ihre Ziele neu berechnen.
Das Problem dieses Verfahrens liegt in seiner langsamen Konvergenz d.h. die Routing-Tabellen ändern sich bei einer Veränderung im Netzwerk nur langsam. Außerdem ergibt sich durch den Austausch der Routing-Tabellen ein großer Protokolloverhead, der vor allem bei größeren Netzen zu einem enormen Verlust an Bandbreite führen kann.
Ein Beispiel für Distance-Vector-Routing-Protokolle ist DSDV (Destination-Sequenced Distance-Vector-Routing).

 

4.2.2 Link-State-Routing-Protokolle

Beim Link-State-Routing werden nicht die gesamten Routing-Tabellen ausgetauscht, sondern jeder Router sendet nur den Teil seiner Routing-Tabelle, der den Status der Verbindungen zu seinen Nachbarroutern beschreibt. Um den Zustand dieser Verbindungen zu prüfen, sendet der Router zusätzlich periodische kurze Nachrichten an seine Nachbarn. Die so erhaltenen Informationen über den Status der Verbindungen werden nun an alle Router, also nicht nur an seine Nachbarn, wie beim Distance-Routing verschickt. Die Router sammeln wiederum alle ankommenden Statusnachrichten und verwendet sie zur Berechnung der kürzesten Pfade zu allen Routern.
Der Vorteil dieses Verfahrens liegt darin, dass die Bandbreite im Vergleich zum Distance-Vektor-Routing durch weniger Routing-Overhead etwas besser genutzt werden kann, jedoch ist der Algorithmus zur Berechnung der Routing-Tabellen sehr Rechen- und Speicherintensiv.
Ein Beispiel für Distance-Vector-Routing-Protokolle ist GSR (Global-State-Routing).

 

4.2.3 On-Demand Routing Protokolle

Ein Lösungsansatz um den hohen Routing-Overhead in den vorherigen Fällen zu vermeiden sind die  On-Demand Routing-Protokolle, welche wie der Name schon sagt nur bei Bedarf tätig werden. Das On-Demand Routing-Protokoll ermittelt nicht für jeden Teilnehmer die Route zu jedem beliebigen Ziel, sondern Routen werden erst bei Bedarf ermittelt, indem der Sender zunächst eine Anfrage verschickt um die Route zu ermitteln. Der Empfänger antwortet hierauf, indem er z.B. ein Paket über die gewählte Route zurück schickt.
Beispiele für On-Demand Routing-Protokolle sind DSR (Dynamic Source Routing) und AODV (Ad Hoc On-Demand Distance Vector).

4.2.4 Zusammenfassung

In Tabelle 8 sind die wesentlichen Merkmale und Eigenschaften einiger Routing-Protokolle gegenübergestellt.
 
Routing-Protokoll
DSDV
GSR
DSR
AODV
Routing Mertic
Kürzester Pfad
Kürzester Pfad
Kürzester Pfad
Kürzester Pfad
Netzwerk-topologie
Flach
Flach
Flach
Flach
Update-Maßnahmen
Proactive:

Versenden von periodischen Updates an alle Nachbar-Router

Proactive: 

Versenden von periodischen Updates an alle Router

Reactive:
 
 

Nur bei Bedarf

 

Reactive:
 
 

Nur bei Bedarf

 

Bekannte Teilnehmer
Gesamtes Netzwerk
Gesamtes Netzwerk
Nur nach Verbindungs-aufbau
Nur nach Verbindungs-aufbau
Routing-Aktivitäten
Nächsten hop zum Ziel aus der Routing-tabelle entnehmen
keine
Ermitteln der Route
Ermitteln der Route
Typ von Control-Paketen
Routing-Tabelle mit allen Zielen mit Entfernung und Sequenznr.
Routing-Tabelle mit Zielen in unmittelbarer Nachbarschaft
Route-Request / Route-Reply
Route-Request / Route-Reply
Routing-Overhead
Sehr viel
Viel
Relativ wenig
Relativ wenig
Rechen- und Speicherintensität
Hoch
Sehr Hoch
Gering
Gering
Verzögerung bei Paketübertragung
Keine
Keine
Ja
Ja
Konvergenz
Sehr langsam
Langsam
Schnell
Schnell
Behandlung von Fehlern
Aktualisieren der Routing-Tabelle
Aktualisieren der Routing-Tabelle
Senden von Fehler-meldungen
Senden von Fehler-meldungen

Tabelle 8


 


[prev]
Inhalt
[next]