aodv-uu-0.9.tar.gz_AODV ad hoc

Network Working Group C. Perkins Request for Comments: 3561 Nokia Research Center Category: Experimental E. Belding-Royer University of California, Santa Barbara S. Das University of Cincinnati July 2003 Ad hoc On-Demand Distance Vector (AODV) Routing Status of this Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2003). All Rights Reserved. Abstract The Ad hoc On-Demand Distance Vector (AODV) routing protocol is intended for use by mobile nodes in an ad hoc network. It offers quick adaptation to dynamic link conditions, low processing and memory overhead, low network utilization, and determines unicast routes to destinations within the ad hoc network. It uses destination sequence numbers to ensure loop freedom at all times (even in the face of anomalous delivery of routing control messages), avoiding problems (such as "counting to infinity") associated with classical distance vector protocols. Table of Contents 1. Introduction ............................................... 2 2. Overview .................................................. 3 3. AODV Terminology ........................................... 4 4. Applicability Statement .................................... 6 5. Message Formats ............................................ 7 5.1. Route Request (RREQ) Message Format ................... 7 5.2. Route Reply (RREP) Message Format ..................... 8 5.3. Route Error (RERR) Message Format ..................... 10 5.4. Route Reply Acknowledgment (RREP-ACK) Message Format .. 11 6. AODV Operation ............................................. 11 6.1. Maintaining Sequence Numbers .......................... 11 6.2. Route Table Entries and Precursor Lists ............... 13 Perkins, et. al. Experimental [Page 1]  RFC 3561 AODV Routing July 2003 6.3. Generating Route Requests ............................. 14 6.4. Controlling Dissemination of Route Request Messages ... 15 6.5. Processing and Forwarding Route Requests .............. 16 6.6. Generating Route Replies .............................. 18 6.6.1. Route Reply Generation by the Destination ...... 18 6.6.2. Route Reply Generation by an Intermediate Node ........................................... 19 6.6.3. Generating Gratuitous RREPs .................... 19 6.7. Receiving and Forwarding Route Replies ................ 20 6.8. Operation over Unidirectional Links ................... 21 6.9. Hello Messages ........................................ 22 6.10 Maintaining Local Connectivity ........................ 23 6.11 Route Error (RERR) Messages, Route Expiry and Route Deletion .............................................. 24 6.12 Local Repair .......................................... 26 6.13 Actions After Reboot ................................. 27 6.14 Interfaces ............................................ 28 7. AODV and Aggregated Networks ............................... 28 8. Using AODV with Other Networks ............................. 29 9. Extensions ................................................. 30 9.1. Hello Interval Extension Format ....................... 30 10. Configuration Parameters ................................... 31 11. Security Considerations .................................... 33 12. IANA Considerations ........................................ 34 13. IPv6 Considerations ........................................ 34 14. Acknowledgments ............................................ 34 15. Normative References ....................................... 35 16. Informative References ..................................... 35 17. Authors' Addresses ......................................... 36 18. Full Copyright Statement ................................... 37 1. Introduction The Ad hoc On-Demand Distance Vector (AODV) algorithm enables dynamic, self-starting, multihop routing between participating mobile nodes wishing to establish and maintain an ad hoc network. AODV allows mobile nodes to obtain routes quickly for new destinations, and does not require nodes to maintain routes to destinations that are not in active communication. AODV allows mobile nodes to respond to link breakages and changes in network topology in a timely manner. The operation of AODV is loop-free, and by avoiding the Bellman-Ford "counting to infinity" problem offers quick convergence when the ad hoc network topology changes (typically, when a node moves in the network). When links break, AODV causes the affected set of nodes to be notified so that they are able to invalidate the routes using the lost link. Perkins, et. al. Experimental [Page 2]  RFC 3561 AODV Routing July 2003 One distinguishing feature of AODV is its use of a destination sequence number for each route entry. The destination sequence number is created by the destination to be included along with any route information it sends to requesting nodes. Using destination sequence numbers ensures loop freedom and is simple to program. Given the choice between two routes to a destination, a requesting node is required to select the one with the greatest sequence number. 2. Overview Route Requests (RREQs), Route Replies (RREPs), and Route Errors (RERRs) are the message types defined by AODV. These message types are received via UDP, and normal IP header processing applies. So, for instance, the requesting node is expected to use its IP address as the Originator IP address for the messages. For broadcast messages, the IP limited broadcast address (255.255.255.255) is used. This means that such messages are not blindly forwarded. However, AODV operation does require certain messages (e.g., RREQ) to be disseminated widely, perhaps throughout the ad hoc network. The range of dissemination of such RREQs is indicated by the TTL in the IP header. Fragmentation is typically not required. As long as the endpoints of a communication connection have valid routes to each other, AODV does not play any role. When a route to a new destination is needed, the node broadcasts a RREQ to find a route to the destination. A route can be determined when the RREQ reaches either the destination itself, or an intermediate node with a 'fresh enough' route to the destination. A 'fresh enough' route is a valid route entry for the destination whose associated sequence number is at least as great as that contained in the RREQ. The route is made available by unicasting a RREP back to the origination of the RREQ. Each node receiving the request caches a route back to the originator of the request, so that the RREP can be unicast from the destination along a path to that originator, or likewise from any intermediate node that is able to satisfy the request. Nodes monitor the link status of next hops in active routes. When a link break in an active route is detected, a RERR message is used to notify ot