ns-cbrp.tar.gz

Mobile Ad Hoc Networking Working Group Charles Perkins INTERNET DRAFT Sun Microsystems 20 November 1997 Ad Hoc On Demand Distance Vector (AODV) Routing draft-ietf-manet-aodv-00.txt Status of This Memo This document is a submission by the Mobile Ad Hoc Networking Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the manet@itd.nrl.navy.mil mailing list. Distribution of this memo is unlimited. This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (North Europe), ftp.nis.garr.it (South Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Abstract The Ad Hoc On-Demand Distance Vector (AODV) routing protocol is intended for use by mobile nodes in an ad hoc network characterized by frequent changes in link connectivity to each other caused by relative movement. It offers quick adaptation to dynamic link conditions, low processing and memory overhead, low network utilization, and establishment of routes between sources and destination which are loop free at all times. It makes use of destination sequence numbers, which are a novel means of ensuring loop freedom even in the face of anomalous delivery of routing control messages, and which solve classical problems associated with distance vector protocols, including the problem of ''counting to infinity''. Perkins Expires 20 May 1998 [Page i]  Internet Draft AODV 20 November 1997 Contents Status of This Memo i Abstract i 1. Introduction 1 2. Overview 2 3. AODV Terminology 3 4. Route Request Message Format 4 5. Route Reply Message Format 5 6. Node Operation 5 6.1. Maintaining Route Utilization Records . . . . . . . . . . 5 6.2. Generating Route Requests . . . . . . . . . . . . . . . . 6 6.3. Forwarding Route Requests . . . . . . . . . . . . . . . . 6 6.4. Generating Route Replies . . . . . . . . . . . . . . . . 7 6.5. Generating Hello Messages . . . . . . . . . . . . . . . . 8 6.6. Initiating Triggered Route Replies . . . . . . . . . . . 8 6.7. Detecting Link Breakage . . . . . . . . . . . . . . . . . 9 7. Configuration Parameters 9 8. Extensions 10 9. Security Considerations 10 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 also defines timely responses to link breakages. 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). Perkins Expires 20 May 1998 [Page 1]  Internet Draft AODV 20 November 1997 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 itself for any usable 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 always selects one with the greatest sequence number. Another feature of AODV is that link breakages cause immediate notifications to be sent to the affected set of nodes, but only that set. 2. Overview Route Requests (RREQs) and Route Replies (RREPs) are the two message types defined by AODV. These message types are handled by UDP, and normal IP header processing applies. So, for instance, the requesting node is expected to use its IP address as the source IP address for the messages. The range of dissemination of broadcast RREQs can be 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 uses a broadcast RREQ to find a route to the destination. A route can be determined when the request reaches either the destination itself, or an intermediate node with a fresh enough route to the destination. The route is made available by unicasting a RREP back to the source of the RREQ. Since each node receiving the request keeps track of a route back to the source of the request, the RREP Reply can be unicast back from the destination to the source, or from any intermediate node that is able to satisfy the request back to the source. If a RREP is broadcast to the limited broadcast address (255.255.255.255), and has a TTL of one, and a destination address of the node itself with metric 0, then it is received by all the node's neighbors, and treated by them as a "hello" message. This hello message is a local advertisement for the continued presence of the node. Neighbors that are using routes through the broadcasting node will continue to mark the routes as valid. If hello messages from a particular node stop coming, the neighbor can assume that the node has moved away. When that happens, the neighbor will mark the link to the node as broken, and may trigger a notification to some of its other neighbors that the link has broken. Perkins Expires 20 May 1998 [Page 2]  Internet Draft AODV 20 November 1997 Since AODV is a routing protocol, it deals with route table management. AODV assumes the following fields exist in each route table entry: - Destination IP Address - Destination Sequence Number - Hop Count - Next Hop - Lifetime This information must be kept even for ephemeral routes, such as are created to temporarily keep track of reverse paths towards nodes originating RREQs. 3. AODV Terminology This section defines terminology used with AODV that is not alre