RFC 3561 AODV Routing Protocol
Mobile Ad Hoc Networking Working Group INTERNET DRAFT 19 June 2002 Charles E. Perkins Nokia Research Center Elizabeth M. Belding-Royer University of California, Santa Barbara Samir R. Das University of Cincinnati
[Link] 2005/2/29
What an ad-hoc routing protocol needs
Multi-hop paths Self-starting Dynamic topology maintenance Loop-free Low consumption of memory, bandwidth Scalable to large node populations Localized effect of link breakage Minimal overhead for data transmission Rapid convergence
AODV: Ad-Hoc On-Demand Distance Vector Routing
Quick loop-free convergence Route creation on demand, localizing the effect of topology changes, and minimizing control traffic. Distance Vector, using Destination Sequence numbers for route updates (on both forward and reverse paths) Triggered updates and minimal latency for route replies two-dim'l metric: <seq#, hop-count>
A destination node increments its own sequence number in two circumstances:
before a node originates a route discovery before a destination node originates a RREP in response to a RREQ
AODV route table entry
Destination IP Address Destination Sequence Number Vaild Destination Sequence Number flag Network Interface Hop Count (number of hops needed to reach destination) Next Hop List of Precursors Lifetime (expiration or deletion time of the route) Other State and routing flag (e.g. valid, invalid, repairable, being repaired)
A node may change the sequence number in the routing table entry
it is itself the destination node, and offers a new route to itself it receives an AODV message with new information about the sequence number for a destination node the path towards the destination node expires or breaks
The route is only updated if the new sequence number
higher than the destination sequence number in the route table the sequence numbers are equal, but the hop count is smaller than the existing hop count in the routing table the sequence number is unknown
AODV Unicast Route Discovery RREQ (route request) is broadcast
Reverse path is set up along the way RREQ message contains < bcast_id; dest_ip; dest_seqno;src_ip; src_seqno; hop_count >
RREP (route reply) is unicast back
From destination if necessary From intermediate node if that node has a recent route
AODV Route Discovery
Time Out Time Out
: RREQ : RREP :Valid Route
AODV Local Route Repair
Data packet be buffered
: RREQ : RREP :Valid Route
: RREQ Data packet be be discarded buffered : RREP :Valid Route :RERR
Route Request (RREQ) Message Format
Route Reply (RREP) Message Format
Route Error (RERR) Message Format
Link Breakage Nodes remember active routes Next hop breaks > neighbors using that route are notified Notification is a RREP with: - metric = - dest_seqno = previous + 1 and is sent to each active neighbor
Ad-hoc Networking Example
Suppose MH1 moves away from MH2 towards MH7, and has active sessions with MH3 and MH6. The following actions occur:
MH2 notices that its link to MH1 is broken MH2 checks its routing table, and finds that its link to MH1 was actively in use by MH3 and MH4. MH2 unicasts an -metric route update, with an incremented destination sequence number, to MH3 and MH4. MH3 may subsequently issue a new route request for MH1. MH4 also notes that its route to MH1 was actively in use, and forwards the -metric route update to MH6. MH6 may subsequently issue a new route request for MH1.
Conclusions
AODV has the following features:
- Nodes store only the routes that are needed - Need for broadcast is minimized - Reduces memory requirements and needless duplications - Quick response to link breakage in active routes - Loop-free routes maintained by use of destination sequence numbers - Scalable to large populations of nodes.