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
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