AODV - Ad Hoc On-Demand Distance Vector Routing

AODV maintains routing tables at the nodes so that data packets do not have to contain routes.

Routes are maintained only between nodes that need to communicate.

Operation

Route Requests (RREQ).

When a node re-broadcasts a Route Request, it sets up a reverse path pointing towards the source.

• AODV assumes symmetric (bi-directional) links.

When the destination receives a Route Request, it replies by sending a Route Reply (RREP).

Route Reply travels along the reverse path set-up when Route Request is forwarded.

Each node maintains non-decreasing sequence numbers.

• Sent in RREQ, and RREP messages; incremented with each new message.

• Used to “timestamp” routing table entries for “freshness” comparison.

The intermediate node may return RREP if it has a routing table entry for a destination that is “fresher” than the source’s (or equal to a lower hop count).

Routing table entries assigned “lifetime”, deleted on expiration.

Unique ID included in RREQ for duplicate rejection

Route Requests

Reverse Path Setup

Forward Path Setup

Route Request and Route Reply

Route Request (RREQ) includes the last known sequence number for the destination.

An intermediate node may also send a Route Reply (RREP) provided that it knows a more recent path than the one previously known to the sender.

Intermediate nodes that forward the RREP, also record the next hop to the destination.

A routing table entry maintaining a reverse path is purged after a timeout interval.

A routing table entry maintaining a forward path is purged if not used for an active_route_timeout interval.

Link Failure

A neighbor of node X is considered active for a routing table entry if the neighbor sent a packet within the active_route_timeout interval which was forwarded using that entry.

Neighboring nodes periodically exchange hello messages.

Periodic route response to neighbors acts as hello, installing, and refreshing route.

When the next hop link in a routing table entry breaks, all active neighbors are informed.

Link failures are propagated by means of Route Error (RERR) messages, which also update destination sequence numbers.

Route Error

When node X is unable to forward packet P (from node S to node D) on the link (X,Y), it generates a RERR message.

Node X increments the destination sequence number for D cached at node X.

The incremented sequence number N is included in the RERR.

When node S receives the RERR, it initiates a new route discovery for D using a destination sequence number at least as large as N.

When node D receives the route request with destination sequence number N, node D will set its sequence number to N, unless it is already larger than N.

Local RERR

Used when link breakage occurs.

• Link breakage detected by link-layer ACK, “passive ACK”, AODV “Hello” messages.

Detecting node may attempt “local repair”.

• Send RREQ for the destination from the intermediate node.

Route Error (RERR) message generated.

• Contains a list of unreachable destinations.

• Sent to “precursors”: neighbors who recently sent a packet that was forwarded over a broken link.

  • Propagated recursively