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

Im AODV-Protokoll verwaltet jeder Netzwerkknoten eine Routingtabelle, die Schleifenfreiheit der Routen wird durch eine inkrementierende Sequenznummer erzeugt. In der Routingtabelle sind zusätzlich zur IP-Adresse des nächsten Knotens in Richtung Ziel (Next Hop), die Sequenznummer des Zielknotens, die Distanz zum Zielknoten (Anzahl Hops) und verschiedene Status-Flags gespeichert.

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

AODV ist ein reaktives Routing-Protokoll: Solange gültige Routen zwischen zwei Endpunkten einer Kommunikationsverbindung existieren, ist AODV inaktiv. Erst wenn eine neue Route zu einem (neuen) Ziel erstellt werden muss, wird AODV aktiv: Der Ursprungsknoten sendet eine Anfragenachricht (RREQ) per Broadcast. Eine Route wird bestimmt, wenn der RREQ entweder das Ziel erreicht oder einen Zwischenknoten mit einer Route findet, die „aktuell genug“ ist. Eine Route ist „aktuell 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.

  • RFC3561 – Ad hoc On-Demand Distance Vector Routing. (englisch).