- Ad-hoc On-demand Distance Vector
-
Der Ad-hoc On-demand Distance Vector-Routingalgorithmus (AODV) ist ein Algorithmus zum Weiterleiten von Daten durch ein mobiles Ad-hoc-Netz. Das Protokoll gehört zu den topologiebasierten, reaktiven Routingverfahren, d. h. Routen zu bestimmten Zielen werden erst bei Bedarf ermittelt.
Funktionsweise
Jeder Netzwerkknoten pflegt eine eigene, monoton wachsende Sequenznummer, wodurch die Schleifenfreiheit der Routen garantiert wird. In jedem Knoten werden Routeninformationen in einem Routenverzeichnis gepflegt. Dazu merkt sich jeder Knoten die IP-Adresse des nächsten Knotens in Richtung Ziel (Next Hop). Weiterhin sind in einem Eintrag unter anderem die Sequenznummer des Zielknotens, die Distanz zum Zielknoten (Anzahl Hops), verschiedene Status-Flags verzeichnet.
Eine AODV-Operation benötigt verschiedene Netzwerknachrichten, um Daten durchs Netzwerk zu verteilen. Der Algorithmus definiert dazu verschiedene Nachrichtentypen: Route Requests (RREQ), Route Replies (RREP) und Route Errors (RERR).
Solange die Endpunkte einer Kommunikationsverbindung gültige Routen zueinander haben, spielt AODV keine Rolle. Wenn eine Route zu einem neuen Ziel benötigt wird, sendet der Ursprungsknoten eine Anfragenachricht (RREQ) per Broadcast. Eine Route wird bestimmt, wenn der RREQ entweder das Ziel erreicht oder einen Zwischenknoten mit einer Route findet, die „frisch genug“ ist. Eine Route ist „frisch genug“, wenn der Routeneintrag gültig ist und die eingetragene Zielsequenznummer mindestens so groß ist wie die Zielsequenznummer in der Anfragenachricht. Diese Route wird per Antwortnachricht (RREP) Unicast zurück an den Ursprung der RREQ geschickt. Dazu hat jeder Knoten, der die Anfrage empfangen und weitergeleitet hat, den Knoten gespeichert, von dem er die RREQ-Nachricht erhalten hat.
Knoten beobachten den Verbindungsstatus der Nachbarknoten in aktiven Routen. Wenn eine Unterbrechung der Verbindung festgestellt wird, wird eine Fehlernachricht (RERR) zur Benachrichtigung des Linkbruchs gesendet. Diese Nachricht gibt die Knoten an, die nicht mehr länger durch die kaputte Verbindung erreichbar sind. Dieser Benachrichtigungsmechanismus wird durch Listen von „aktiven Nachbarn“ (Knoten, die innerhalb einer Zeitspanne ein Paket zur Weiterleitung an das Ziel empfangen haben) in den Routeneinträgen ermöglicht.
Weblinks
Wikimedia Foundation.
