Mobile Ad Hoc Networking Working Group Charles E. Perkins INTERNET DRAFT Nokia Research Center 26 Jan 2004 Elizabeth M. Belding-Royer University of California, Santa Barbara Ian D. Chakeres University of California, Santa Barbara Ad hoc On-Demand Distance Vector (AODV) Routing 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@ietf.org mailing list. Distribution of this memo is unlimited. This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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." The list of current Internet-Drafts can be accessed at: http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at: http://www.ietf.org/shadow.html. 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 unicast route determination 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. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page i] Internet Draft AODV 26 Jan 2004 Contents Status of This Memo i Abstract i 1. Introduction 1 2. Overview 2 3. AODV Terminology 3 4. Applicability Statement 4 5. Message Formats 4 5.1. Route Request (RREQ) Message Format . . . . . . . . . . . 5 5.2. Route Reply (RREP) Message Format . . . . . . . . . . . . 6 5.3. Route Error (RERR) Message Format . . . . . . . . . . . . 8 5.4. Route Reply Acknowledgment (RREP-ACK) Message Format . . 8 6. AODV Operation 9 6.1. Maintaining Sequence Numbers . . . . . . . . . . . . . . 9 6.2. Creating and Updating Route Table Entries . . . . . . . . 10 6.3. Generating Route Requests . . . . . . . . . . . . . . . . 12 6.4. Receiving Route Requests . . . . . . . . . . . . . . . . 13 6.5. Generating Route Replies . . . . . . . . . . . . . . . . 13 6.6. Receiving Route Replies . . . . . . . . . . . . . . . . . 14 6.7. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 14 7. Performance Improvements 15 7.1. Operation over Unidirectional Links . . . . . . . . . . . 15 7.2. Hello Messages . . . . . . . . . . . . . . . . . . . . . 16 7.3. Maintaining Local Connectivity . . . . . . . . . . . . . 17 7.4. Generating Route Error Messages . . . . . . . . . . . . . 18 7.5. Receiving Route Error Messages . . . . . . . . . . . . . 18 7.6. Intermediate Node Route Replies . . . . . . . . . . . . . 19 7.6.1. Generating Gratuitous Route Replies . . . . . . . 20 7.7. Actions After Reboot . . . . . . . . . . . . . . . . . . 20 8. AODV and Aggregated Networks 21 9. IPv6 Operation 22 10. Extensions 22 10.1. Lifetime Extension Format . . . . . . . . . . . . . . . . 23 Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page ii] Internet Draft AODV 26 Jan 2004 11. Configuration Parameters 23 12. Security Considerations 24 13. IANA Considerations 26 14. Acknowledgments 26 A. Draft Modifications 28 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. One distinguishing feature of AODV is its use of a destination sequence number for each routing table entry. The destination sequence number is maintained by each node and is 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. This revised version of AODV incorporates some new performance enhancements and simplifies the requirements for implementations based on experience gained during the development of RFC 3561 [3]. In this document, AODV always refers to the protocol being specified in this document, not the Experimental Protocol as specified in RFC 3561. Of course, there is a great deal of similarity between RFC 3561 and this revised version of AODV. Unfortunately, there are also certain points of incompatibility which became necessary so that AODV could operate in a network where some nodes do not implement all the performance enhancing (but still optional) features. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 1] Internet Draft AODV 26 Jan 2004 2. Overview Route Requests (RREQs), Route Replies (RREPs) and Route Errors (RERRs) are message types defined by AODV. These message types are received via UDP (on port 654), 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. Fragmentation is typically not required. When a route to a new destination is needed, the node broadcasts a RREQ to find a route to the destination. 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. A route can be determined when the RREQ reaches a node that offers reachability to the destination (e.g., the destination itself). The route is made available by unicasting a RREP back to the origination of the RREQ. For nodes monitoring the link status of next hops for active routes, when a link break in an active route is detected, the broken link is invalidated and a RERR message is typically transmitted to notify other nodes that the loss of that link has occurred. The RERR message indicates the destination that is no longer reachable by way of the broken link. AODV is a routing protocol, and hence it deals with routing table management. Routing table information must be kept for all known routes. AODV uses the following fields with each routing table entry: - Destination IP Address - Hostid Size - Destination Sequence Number - Next Hop IP Address - Lifetime (expiration or deletion time of the route) - Hop Count (number of hops to reach the destination) - Network Interface - Other state and routing flags (e.g., active, inactive) Managing the sequence number is crucial to avoiding routing loops. A destination becomes unreachable when a link breaks or it is deactivated. When these conditions occur, the route is invalidated by operations involving the sequence number and marking the routing table entry state as inactive. See Section 6.1 for details. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 2] Internet Draft AODV 26 Jan 2004 3. AODV Terminology This protocol specification uses conventional meanings [1] for capitalized words such as MUST, SHOULD, etc., to indicate requirement levels for various protocol features. This section defines other terminology used with AODV that is not already defined in [4]. active route A route towards a destination that has a routing table entry that is marked as active. Only active routes can be used to forward data packets. broadcast Transmitting to the IP Limited Broadcast address, 255.255.255.255. destination An IP address to which data packets are to be transmitted. The IP address of the destination node for a typical data packet appears in the designated field of the IP header. forwarding node A node that agrees to forward packets destined for another node. The node retransmits the packets to a next hop that is closer to the unicast destination along a path previously established by AODV that has been set up using control messages. inactive route A route that has expired, denoted by a state of inactive in the routing table entry. An inactive route is used to store previously active route information, such as the sequence number, for an extended period of time. An inactive route cannot be used to forward data packets, but it can provide information useful when processing other control messages (e.g. future RREQ messages). originating node A node that initiates an AODV route request message. For instance, the node that initiates a Route Discovery process and first broadcasts the RREQ message is called the originating node of the RREQ message. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 3] Internet Draft AODV 26 Jan 2004 sequence number A monotonically increasing number that is maintained by each node. It is used by other nodes to determine the freshness of routing information obtained from AODV protocol messages about the originating node. The sequence number zero (0) is reserved and represents an unknown sequence number. 4. Applicability Statement The AODV routing protocol is designed for mobile ad hoc networks with populations of tens to thousands of mobile nodes. AODV can handle low, moderate, and high mobility rates, as well as a variety of data traffic levels. AODV is designed for use in networks where the nodes can all trust each other, either by use of preconfigured keys or because it is known that there are no malicious nodes. AODV has been designed to reduce the dissemination of control traffic and eliminate overhead on data traffic in order to improve scalability and performance. A recent study [5] has indicated that, for networks of limited size, reliable communication can be managed by nodes that implement only a very limited number of AODV features. For instance, in networks of 50 nodes, the performance does not suffer very much even if nodes only implement RREQ and RREP, without any RREPs from intermediate nodes. Thus, we have revised the original AODV specification so that many features are no longer mandated, even if they are strongly recommended for all general purpose ad hoc network nodes. Networks of nodes that only implement the mandated specification may not be useful except for certain limited scenarios, and may even effectively consume more power than when the nodes contain the congestion control and latency reduction features recommended in Section 7. 5. Message Formats In this section, the formats for the basic AODV messages are specified. RREQ and RREP messages MUST be implemented by all AODV nodes. RERR and RREP-ACK messages SHOULD be implemented, but there may be cases where nodes can be built for certain limited deployments that do not need to have the features enabled by those messages. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 4] Internet Draft AODV 26 Jan 2004 5.1. Route Request (RREQ) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |D|G| Reserved | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RREQ~ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path Node IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path Node Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (additional path node IP address and sequence number pairs) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Request message is illustrated above, and contains the following fields: Type 1 D Destination-only flag. If set a intermediate node may not respond to this RREQ (see Section 7.6). G Gratuitous Route Reply flag. Indicates whether a gratuitous RREP should be sent to the destination (see Section 7.6). This flag should be set for bi-directional traffic, such as TCP. Reserved Sent as 0; ignored on reception. Hop Count The number of hops from the originating node to the node handling the request. This field also indicates the number of accumulated path node IP addresses and sequence numbers in the RREQ. RREQ ID A sequence number uniquely identifying the particular RREQ when taken in conjunction with the originating node's IP address. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 5] Internet Draft AODV 26 Jan 2004 Destination IP Address The IP address of the destination for which a route is desired. Destination Sequence Number The latest sequence number received by the originator for any route towards the destination. Originator IP Address The IP address of the originating node that issued the Route Request. Originator Sequence Number The current sequence number of the originating node. Path Node IP Address The IP address of the first node along the path from the Originator to the Destination. Path Node Sequence Number The Sequence Number of the first node along the path from the Originator to the Destination. 5.2. Route Reply (RREP) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |A|Reserved | APN Cnt |Hostid Sz| Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path Node IP Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Path Node Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (additional path node IP address and sequence number pairs) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Reply message is illustrated above, and contains the following fields: Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 6] Internet Draft AODV 26 Jan 2004 Type 2 A RREP Acknowledgment required. See Section 7.1. Reserved Sent as 0; ignored on reception. APN Count The number of accumulated path nodes appended to the RREP. Hostid Size The Hostid Size field supplies information that is needed to determine those nodes within a destination's subnet that are reachable via the same route. For example, a Hostid Size of eight (8) is equivalent to a subnet prefix of 255.255.255.0. For a host route, the Hostid Size is set to zero (0), which is equivalent to a subnet mask of 255.255.255.255. Hop Count The number of hops from the originating node to the destination node. Destination IP Address The IP address of the destination node. Destination Sequence Number The sequence number associated with the destination node. Originator IP Address The IP address of the node that originated the RREQ for which the route is supplied. Originator Sequence Number The current sequence number of the originating node. Path Node IP Address The IP address of the first node along the path from the Originator to the Destination. Path Node Sequence Number The Sequence Number of the first node along the path from the Originator to the Destination. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 7] Internet Draft AODV 26 Jan 2004 5.3. Route Error (RERR) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | DestCount | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination IP Address (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination Sequence Number (1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | (more node IP address and sequence number pairs as needed) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Error message is illustrated above, and contains the following fields: Type 3 Reserved Sent as 0; ignored on reception. DestCount The number of unreachable destinations included in the message; MUST be at least 1. Unreachable Destination IP Address The IP address of the destination that has become unreachable due to a broken link. Unreachable Destination Sequence Number The sequence number in the route table entry for the destination listed in the previous Unreachable Destination IP Address field. 5.4. Route Reply Acknowledgment (RREP-ACK) Message Format 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 4 Reserved Sent as 0; ignored on reception. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 8] Internet Draft AODV 26 Jan 2004 6. AODV Operation This section describes the scenarios during which nodes generate Route Request (RREQ) and Route Reply (RREP) for unicast communication to a destination node and how the message fields are handled. In order to process the messages correctly, certain state information has to be maintained in the routing table for destinations of interest. All AODV messages are sent to port 654 using UDP. 6.1. Maintaining Sequence Numbers AODV requires each node in the network to own and maintain its destination sequence number in order to guarantee the loop-freedom of all routes towards that node. A node increments its own sequence number in two circumstances: - Immediately before a node initiates a route discovery, it MUST increment its own sequence number. This prevents conflicts with previously established reverse routes towards the originator of a RREQ. - Immediately before a node issues a RREP in response to a RREQ, it MUST update its own sequence number to the maximum of its current sequence number and the destination sequence number in the RREQ packet plus one (1). SeqNum=Max(SeqNum,RREQSeqNum+1) When a node increments a sequence number, it MUST do so by treating the sequence number value as if it were an unsigned number. Additionally the sequence number zero (0) is reserved and MUST never be used. To accomplish sequence number rollover, if the sequence number has already been assigned to be the largest possible number representable as a 32-bit unsigned integer (i.e., 4294967295), then it MUST then have a value of one (1) when it is incremented. This is in contrast to the manner in which the result of comparing two AODV sequence numbers is to be treated (see below). Every routing table at every node MUST include the latest information available about the sequence number for the IP address of each destination for which a routing table entry is maintained. This sequence number is called the "destination sequence number". It is updated whenever a node receives new (i.e., not stale) information about the sequence number from RREQ, RREP, or RERR messages that may be received related to that destination. In order to ascertain that information about a destination is not stale, the node compares its current numerical value for the sequence number in its routing table with that obtained from the incoming AODV Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 9] Internet Draft AODV 26 Jan 2004 message. In AODV, the sequence number zero (0) has special meaning and represents an unknown sequence number. Any known sequence number is considered higher than an unknown sequence number. Given a known sequence number in an AODV message, this comparison MUST be done using signed 32-bit arithmetic. This is necessary to accomplish sequence number rollover. If the result of subtracting the currently stored sequence number from the value of the incoming sequence number is less than zero, or a sequence number is known and the incoming sequence number is unknown, then the information related to that destination in the AODV message MUST be discarded, since that information is stale compared to the node's currently stored information. The only other circumstance in which a node may change the destination sequence number in one of its routing table entries is in response to a lost or expired link to the next hop towards that destination. The node determines which destinations use a particular next hop by consulting its routing table. For each destination that uses the next hop, the node increments the sequence number and marks the route as inactive. Whenever any fresh (i.e., containing a sequence number at least equal to the recorded sequence number) routing information for an affected destination is received, the node SHOULD update its route table information according to the information contained in the update. A node may change the sequence number in the routing table entry of a destination only if: - it is itself the destination node, and it offers a new route to itself, or - it receives an AODV message with new information about the sequence number for a destination node, or - the path towards the destination node expires or breaks. 6.2. Creating and Updating Route Table Entries When a node receives an AODV control packet from a neighbor or creates or updates a route for a particular destination, it checks its routing table for an entry to the destination using longest-prefix matching. In the event that there is no corresponding entry for that destination, an entry is created. The ``new'' sequence number is either determined from the information contained in the control packet or set to zero (0), representing an unknown sequence number. A route is only updated if one of the following conditions is met: Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 10] Internet Draft AODV 26 Jan 2004 (i) the new sequence number is higher than the destination sequence number in the route table, or (ii) the new sequence number is the same as the destination sequence number in the route table and the route is marked as inactive, or (iii) the sequence number in the routing table is unknown. In addition, a route MAY be updated if the new sequence number is the same as the destination sequence number in the route table, and the new route is favorable for some reason, such as reduced hop count. If the route table entry to this destination is created or updated, then the following actions occur: - the route is marked as active, - the Next Hop IP Address in the routing table entry for the destination is assigned to be that of the node from which the control packet was received, which is indicated by the source IP address field in the IP header, or by examining the accumulated path list, - the Hop Count is set to the number of hops to this destination, - the Hostid Size is set to the value from the control packet or zero, - the Lifetime field is set to the current time plus the value of ACTIVE_ROUTE_TIMEOUT, - and the Destination Sequence Number is set to the sequence number for this destination from the control packet or zero (0) for an unknown sequence number. After updating a route, if it is active it may now be used to send any queued data packets and to fulfill any outstanding route requests. Each time a route is used to forward a data packet, the Lifetime field of the routing table entry for the IP destination is updated to be no less than the current time plus ACTIVE_ROUTE_TIMEOUT. Note that the Lifetime field in the routing table plays a dual role -- for an active route it is the expiry time, and for an inactive route it is the deletion time. If a data packet is received for an Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 11] Internet Draft AODV 26 Jan 2004 inactive route, the Lifetime field is updated to current time plus DELETE_PERIOD. 6.3. Generating Route Requests A node generates a RREQ when it determines that it needs a route to a destination and does not have one available. This can happen if the destination is previously unknown to the node or if a previously active route to the destination has expired or been marked as inactive. The Destination Sequence Number field in the RREQ message is the last known destination sequence number for this destination and is copied from the Destination Sequence Number field in the pertinent routing table entry. If no sequence number is known, the sequence number field MUST be set to zero (0). The Originator Sequence Number in the RREQ message is the node's own sequence number, which is incremented prior to insertion in a RREQ. The RREQ ID field is incremented by one from the last RREQ ID used by the current node. Each node maintains only one RREQ ID. The Hop Count field is set to zero. The RREQ TTL value is set to NET_DIAMETER. Before broadcasting the RREQ, the originating node buffers the RREQ ID and the Originator IP address (its own address) of the RREQ for PATH_DISCOVERY_TIME. By doing so, the node will not reprocess or re-forward the packet when it receives the packet again from its neighbors. The originating node then broadcasts the RREQ. A node SHOULD NOT originate more than RREQ_RATELIMIT RREQ messages per second. After broadcasting a RREQ, a node waits for a RREP or other control message with current information regarding the destination. If a route is not received within NET_TRAVERSAL_TIME milliseconds, the node MAY again try to discover a route by broadcasting another RREQ, up to a maximum of RREQ_TRIES times. Each new attempt MUST increment and update the RREQ ID. To reduce congestion in a network, repeated attempts by a source node at route discovery for a single destination MUST utilize a binary exponential backoff. The first time a source node broadcasts a RREQ, it waits NET_TRAVERSAL_TIME milliseconds for the reception of a RREP. If a RREP is not received within that time, the source node sends a new RREQ. When calculating the time to wait for the RREP after sending the second RREQ, the source node MUST use a binary exponential backoff. Hence, the waiting time for the RREP corresponding to the second RREQ is 2 * NET_TRAVERSAL_TIME milliseconds. If a RREP is not received within this time period, another RREQ may be sent, up to RREQ_TRIES additional attempts after the first RREQ. For each additional attempt, the waiting time for Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 12] Internet Draft AODV 26 Jan 2004 the RREP is multiplied by 2 so that the time conforms to a binary exponential backoff. Data packets waiting for a route (i.e., waiting for a RREP after a RREQ has been sent) SHOULD be buffered. The buffering SHOULD be "first-in, first-out" (FIFO). If a route discovery has been attempted RREQ_TRIES times at the maximum TTL without receiving any RREP, all data packets destined for the corresponding destination SHOULD be dropped from the buffer and a Destination Unreachable ICMP message SHOULD be delivered to the application. 6.4. Receiving Route Requests When a node receives a RREQ, the node increments the Hop Count field in the RREQ by one, to account for the previous hop. Then it MAY create or update route to any destination listed in the accumulated path list as specified in Section 6.2. The node can use any active route to forward data packets. Next it checks to determine whether it has received a RREQ with the same Originator IP Address and RREQ ID within PATH_DISCOVERY_TIME. If such a RREQ has been received, the node SHOULD silently discard the newly received RREQ. The rest of this subsection describes actions taken for RREQs that are not discarded. If this intermediate node does not generate a RREP (following the rules in Section 7.6) and if the incoming IP header has a TTL larger than 1, then the RREQ is updated. The TTL field in the outgoing IP header is decreased by one. The Destination Sequence number in the RREQ for the requested destination is set to the maximum of the original value received in the RREQ message and the destination sequence value currently maintained by the node for the requested destination. However, the forwarding node MUST NOT modify the maintained value in its routing table for the destination sequence number, even if the value received in the incoming RREQ is larger than the value currently maintained by the forwarding node. Finally, the current host appends its sequence number and IP address to the accumulated path list. After updating the RREQ, it broadcasts the RREQ to address 255.255.255.255 on each of its configured interfaces (see Section 6.7). 6.5. Generating Route Replies Upon reception of a RREQ, a node MUST generate a RREP if it is the destination. When generating a RREP message, a node copies the Destination IP Address, Originator IP Address and Originator Sequence Number from the RREQ message into the corresponding fields of the Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 13] Internet Draft AODV 26 Jan 2004 RREP message. In addition, the accumulated path list from the RREQ is appended to the RREP in the same order as listed in the RREQ. The APN Count field is set to the length of accumulated path node list. If the destination generates a response, it MUST increment its own sequence number to be at least one greater than the Destination Sequence Number in the RREQ. If this condition is already satisfied the destination does not change its sequence number before generating the RREP message. The destination node places its (perhaps newly changed) sequence number into the Destination Sequence Number field of the RREP, and enters the value zero into the Hop Count field of the RREP. Once created, the RREP is unicast to the next hop toward the originator of the RREQ, indicated by the last entry in the accumulated path list. Intermediate nodes MAY generate RREP under certain conditions. Intermediate node route replies are described in Section 7.6. 6.6. Receiving Route Replies When a node receives a RREP message, it increments the Hop Count field in the RREP by one to account for the new hop through the previous node. Next, a route MAY be created for the source and each destination listed in the accumulated path list. Then a route to the destination is updated or created by way of the procedure specified in Section 6.2. Subsequently, the node can use any of its active routes to forward data packets to the destination. If the current node is not the node indicated by the Originator IP Address in the RREP message, AND after an active route has been created or updated to the destination, the node SHOULD send the RREP to the IP address previous to its own IP address in the accumulated path list. If there are no nodes listed in the accumulated path list, denoted by zero (0) in APN Count, the RREP is sent to the Next Hop IP Address in the active routing table entry for the Originator IP Address. A node may send the RREP via an active route to the Originator IP address via a route different from the accumulated path list, but it MUST remove the accumulated path information and set the APN Count to zero (0). 6.7. Interfaces Because AODV should operate smoothly over heterogeneous networks (wired, as well as wireless) and it is likely that AODV will also be used with multiple wireless devices, the particular interface Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 14] Internet Draft AODV 26 Jan 2004 over which packets arrive must be known to AODV whenever a packet is received. This includes the reception of RREQ, RREP, and RERR messages. Whenever a packet is received from a new neighbor, the interface on which that packet was received is recorded into the routing table entry for that neighbor along with all the other appropriate routing information. Similarly, whenever a route to a new destination is discovered, the interface through which the destination can be reached is also recorded into the destination's route table entry. When multiple interfaces are available, a node transmitting a broadcast control message SHOULD broadcast the message on all interfaces that have been configured for operation in the ad hoc network. 7. Performance Improvements Nodes that implement only the basic AODV features do not economize the use of the physical network medium, and thus are more likely to contribute to the overall congestion in the network. This is not a problem, as long as the medium utilization is low. However, if network capacity limits applications, it is more important for the AODV nodes to implement more features in order to reduce network congestion. Another way that performance can be improved in an ad hoc network is to reduce the time duration of communications disruptions caused by node movement. This can be done in several ways, notably by the transmission of the RERR message to trigger route repair and update mechanisms. Without RERR, the robustness of the communication between the application endpoints becomes dependent upon recovery methods that are been built into the application. There are applications that have no such recover mechanisms, and those applications, hosted on nodes that do not attempt any routing repairs, would be adversely affected by node mobility. If any node in the network depends on RERR messages to detect route breaks, all nodes SHOULD support it. Each of the performance improvements in this section SHOULD be implemented by every AODV node, so that the network as a whole runs in a way more responsive to application needs, and creates less network congestion. 7.1. Operation over Unidirectional Links It is possible that a RREP transmission may fail, especially if the RREQ transmission triggering the RREP occurs over a unidirectional Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 15] Internet Draft AODV 26 Jan 2004 link. If no other RREP generated from the same route discovery attempt reaches the node which originated the RREQ message, the originator will reattempt route discovery after a timeout (see section 6.3). However, the same scenario might well be repeated without any improvement, and no route would be discovered even after repeated retries. Unless corrective action is taken, this can happen even when bidirectional routes between originator and destination do exist. Link layers using broadcast transmissions for the RREQ will not be able to detect the presence of such unidirectional links. In AODV, any node acts on only the first RREQ with the same RREQ ID and ignores any subsequent RREQs. Suppose, for example, that the first RREQ arrives along a path that has one or more unidirectional link(s). A subsequent RREQ may arrive via a bidirectional path (assuming such paths exist), but it will be ignored. To prevent this problem, when a node detects that its transmission of a RREP message has failed, it remembers the next-hop of the failed RREP in a ``blacklist'' set. Such failures can be detected via the absence of a link-layer or network-layer acknowledgment (e.g., RREP-ACK). A node ignores all RREQs received from any node in its blacklist set. Nodes are removed from the blacklist set after a BLACKLIST_TIMEOUT period. This period should be set to the upper bound of the time it takes to perform the allowed number of route request retry attempts as described in section 6.3. Note that the RREP-ACK packet does not contain any information about which RREP it is acknowledging. The time at which the RREP-ACK is received will likely come just after the time when the RREP was sent with the 'A' bit. This information is expected to be sufficient to provide assurance to the sender of the RREP that the link is currently bidirectional, without any real dependence on the particular RREP message being acknowledged. However, that assurance typically cannot be expected to remain in force permanently. If unidirectional links are likely to occur the 'A' bit in RREPs SHOULD be set. 7.2. Hello Messages A node MAY offer connectivity information by broadcasting local Hello messages. A node SHOULD only use hello messages if it is participating in routing of data packets. Every HELLO_INTERVAL milliseconds, the node checks whether it has sent a broadcast control message (e.g., a RREQ). If it has not, it SHOULD broadcast a RREP with TTL = 1, called a Hello message, where the RREP message fields are set as follows: Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 16] Internet Draft AODV 26 Jan 2004 Destination IP Address The node's IP address. Destination Sequence Number The node's sequence number. Hop Count 0 Whenever a node receives a Hello message from a neighbor, the node SHOULD process it as a normal RREP, as specified in Section 6.6. Additionally, a neighboring node MAY determine connectivity by listening for packets from its set of neighbors. If an active route to a neighbor exists but no packets from that neighbor (Hello messages or otherwise) have been received for more than (ALLOWED_HELLO_LOSS * HELLO_INTERVAL) milliseconds, the node SHOULD assume that the link to this neighbor is currently lost. When this happens, the node SHOULD invalidate the route to that neighbor and increase the sequence number stored in the routing table by one. Additionally, each active route in the routing table that lists this neighbor as the next hop should be invalidated and its corresponding sequence number incremented. 7.3. Maintaining Local Connectivity Each forwarding node SHOULD keep track of its continued connectivity to its active next hops as well as neighbors that have transmitted Hello messages during the last (ALLOWED_HELLO_LOSS * HELLO_INTERVAL). A node can maintain accurate information about its continued connectivity to these active next hops using one or more of the available link or network layer mechanisms, as described below. - Any suitable link layer notification can be used to determine connectivity each time a packet is transmitted to an active next hop. For example, failure to transmit a packet after the maximum number of retransmission attempts in IEEE 802.11 results in an indicator signifying a failed transmission. This indicator can be understood as loss of the link to the active next hop when the network utilization is low. - If layer-2 notification is not available, passive acknowledgment MAY be used, when the next hop is expected to forward the packet, by listening to the channel for a transmission attempt made by the next hop. - If transmission is not detected within NEXT_HOP_WAIT milliseconds or the next hop is the destination (and thus is not likely to forward the packet), the node may signal the next hop to cause it Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 17] Internet Draft AODV 26 Jan 2004 to transmit a packet in return. Many methods may be used. For example, sending an ICMP Echo Request message to the next hop should cause the next hop to send an Echo Reply. - Use of Hello messages. If a link to the next hop cannot be detected by any of these methods, the node SHOULD assume that the link is lost after (ALLOWED_HELLO_LOSS * HELLO_INTERVAL) milliseconds. It should invalidate the route to the next hop and increase the destination sequence number by one. Additionally, for all active routes that utilize the lost link as the next hop, these routes should be invalidated and their sequence numbers incremented by one. 7.4. Generating Route Error Messages When a data packet for an inactive route or unknown destination is received, a Route Error (RERR) message is generated. The Unreachable Destination field is the IP address of the inactive or unknown destination. If an inactive route exists in the routing table, the Unreachable Destination Sequence Number field of the RERR is filled with the value in the routing table; otherwise zero (0) is placed in the Unreachable Destination Sequence Number field of the RERR. All unreachable destinations, with the same next hop, and their corresponding sequence numbers SHOULD be placed in the same RERR message. Then the RERR message is broadcast to all neighbors. A node SHOULD NOT generate more than RERR_RATELIMIT RERR messages per second. The RERR is sent to the local broadcast address (Destination IP == 255.255.255.255, TTL == 1) with the unreachable destinations, and their corresponding sequence numbers included in the packet. The DestCount field of the RERR packet indicates the number of unreachable destinations included in the packet. 7.5. Receiving Route Error Messages When a node receives a RERR message, and a route to the next hop does not already exist, a route MAY be created for the previous hop without a valid sequence number and a hop count of one (1) (see Section 6.2). Then the node compares the first unreachable destination listed in the RERR to the routes in its routing table. If a route to the unreachable destination exists and the next hop listed in the routing table entry is the node that sent this RERR (indicated by the source IP address field in the IP header), and either: Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 18] Internet Draft AODV 26 Jan 2004 (i) the Unreachable Destination Sequence Number in the RERR is zero (0), or (ii) the Unreachable Destination Sequence Number in the RERR is higher than the destination sequence number listed in the routing table for the unreachable destination then the route is invalidated and the destination sequence number for the unreachable destination is updated to be the maximum of the sequence number listed in the routing table entry and the Unreachable Destination Sequence number from the RERR. If a route is invalidated then a RERR message is created to be broadcast with the unreachable destination. If additional unreachable destinations are listed in the RERR they MAY be used to invalidate other unreachable destinations as described above. Any additional destinations that became unreachable due to the processing of this RERR SHOULD be added to the new RERR message sent by this node. 7.6. Intermediate Node Route Replies An intermediate node MAY generate a RREP if it has an active route to the destination and the destination-only flag is not set. If an intermediate node generates the response, it places the known destination sequence number from the routing table entry for the destination into the Destination Sequence Number field of the RREP, and places the known hop count from the routing table entry into the Hop Count field in the RREP. When generating a RREP message, a node copies the Destination IP Address, Originator IP Address and Originator Sequence Number from the RREQ message into the corresponding fields of the RREP message. In addition, the accumulated path list from the RREQ is appended to the RREP in the same order as listed in the RREQ. The APN Count field is set to the length of the accumulated path node list. Once created, the RREP is unicast to the next hop toward the originator of the RREQ, indicated by the last entry in the accumulated path list. If the Gratuitous Route Reply flag is set, the intermediate node MUST generate a Gratuitous Route Reply. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 19] Internet Draft AODV 26 Jan 2004 7.6.1. Generating Gratuitous Route Replies After an intermediate node receives a RREQ and responds with a RREP, it discards the RREQ. If the RREQ has the 'G' flag set, and the intermediate node returns a RREP to the originating node, it MUST also send a gratuitous RREP to the destination node. The gratuitous RREP that is to be sent to the desired destination contains the following values in the RREP message fields: APN Count 0 Hop Count The Hop Count as indicated in the node's route table entry for the originator Destination IP Address The IP address of the node that originated the RREQ Destination Sequence Number The Originator Sequence Number from the RREQ Originator IP Address The IP address of the Destination node in the RREQ Originator Sequence Number The Sequence Number of the Destination node in the RREQ The gratuitous RREP is then sent to the next hop along the path to the destination node, just as if the destination node had already issued a RREQ for the originating node and this RREP was produced in response to that (fictitious) RREQ. The RREP that is sent to the originator of the RREQ is the same whether or not the 'G' bit is set. 7.7. Actions After Reboot Transient routing loops SHOULD be protected against in an ad hoc network, because whenever the transient condition occurs, there is a lot of unnecessary routing and energy expenditure by the nodes creating the loop. For this reason, AODV nodes SHOULD implement the simple protective measures specified in this section. A node participating in the ad hoc network must take certain actions after reboot if it loses its own sequence number. Otherwise, if neighboring nodes are using this node as an active next hop, there Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 20] Internet Draft AODV 26 Jan 2004 would be a potential for routing loops. To prevent this possibility, each node (if it has lost its sequence number) on reboot waits for DELETE_PERIOD before transmitting any route discovery messages. During this time, if the node receives a RREQ, RREP, or RERR control packet, it SHOULD create route entries as appropriate given the sequence number information in the control packets, but it MUST not forward any control packets. If the node receives a data packet for some unicast destination, it SHOULD broadcast a RERR as described in Section 7.4 and MUST reset the reboot waiting timer to expire after current time plus DELETE_PERIOD. It can be shown [6] that by the time the rebooted node comes out of the waiting phase and resumes routing again, its neighbors will no longer be using it as an active next hop. Its own sequence number is updated once it receives a RREQ from any other node, as the RREQ always carries the maximum destination sequence number seen en route. If no such RREQ arrives, the node may initialize its own sequence number to any allowable value other than zero (0) (for example, (1)). 8. AODV and Aggregated Networks AODV has been designed for use by mobile nodes with IP addresses that are not necessarily related to each other. However, in some cases a collection of mobile nodes MAY operate in a fixed relationship to each other and share a common subnet prefix, moving together within the ad hoc network. Call such a collection of nodes a ``subnet''. In this case, it is possible for a single node within the subnet to advertise reachability for all other nodes in the subnet, by responding with an appropriate RREP message to any RREQ message requesting a route to any node sharing the subnet routing prefix. Call this single node the ``subnet router''. In order for a subnet router to operate the AODV protocol for the whole subnet, it has to maintain a destination sequence number for the entire subnet. In any RREP message sent by the subnet router, the Hostid Size field of the RREP message MUST be set to the number of bits of the IP address that remain, after subtracting the bits that are used for the subnet prefix. Other nodes sharing the subnet prefix SHOULD NOT issue RREP messages, and SHOULD forward RREQ messages to the subnet router. The router supplies data to indicate the number of bits in the Hostid, instead of the number of bits in the subnet prefix, in order to maintain compatibility with hosts in the ad hoc network that ignore nonzero Hostid Size fields. When the Hostid Size field is zero (or ignored), the recipient of the RREP treats the information in that message as if there were no subnet routers. The processing of RREPs that give routes to subnets (i.e., have nonzero Hostid Size fields) is the same as processing for host-specific RREP messages. Every node that receives the RREP with Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 21] Internet Draft AODV 26 Jan 2004 Hostid Size information SHOULD create or update the route table entry for the subnet. Then, in the future nodes with this subnet route can use the information to avoid sending RREQs for other nodes in the same subnet. When a node uses a subnet route it may be that a packet is routed to an IP address on the subnet that is not assigned to any existing node in the ad hoc network. When that happens, the subnet router MUST return ICMP Host Unreachable message to the sending node. Upstream nodes receiving such an ICMP message SHOULD record the information that the particular IP address is unreachable, but MUST NOT invalidate the route entry for any matching subnet prefix. If several nodes in the subnet advertise reachability to the subnet defined by the subnet prefix, the node with the lowest IP address is elected to be the subnet router, and all other nodes MUST stop advertising reachability. The behavior of default routes (i.e., routes with routing prefix length 0) is not defined in this specification. Selection of routes sharing prefix bits should be according to longest match first. 9. IPv6 Operation For operation in IPv6 networks the IP addresses in AODV control messages are 128 bits (instead of 32 bits). When AODV recognizes that a control message was delivered using an IPv6 packet header, then all IP address fields are expected to contain 128 bit addresses. Besides the change in IP address length, all other protocol message fields and functionality remain unchanged. 10. Extensions In this section, the format of extensions to the RREQ and RREP messages is specified. All such extensions appear after the message data, and have the following format: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | type-specific data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ where: Type 1-255 Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 22] Internet Draft AODV 26 Jan 2004 Length The length of the type-specific data, not including the Type and Length fields of the extension in bytes. Extensions with types between 128 and 255 may NOT be skipped. The rules for extensions conform to the rules for handling IPv6 options. 10.1. Lifetime Extension Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Lifetime ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... Lifetime, continued | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 2 Length 4 Lifetime The number of milliseconds to be added to the lifetime field for this route entry. The Lifetime extension MAY be appended to a RREQ or RREP. If this field is used the Lifetime value from the extension SHOULD be used to update the lifetime field in the routing table for this active route entry instead of ACTIVE_ROUTE_TIMEOUT. 11. Configuration Parameters This section gives default values for some important parameters associated with AODV protocol operations. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 23] Internet Draft AODV 26 Jan 2004 Parameter Name Value ---------------------- ----- NODE_TRAVERSAL_TIME 10 milliseconds NET_DIAMETER 20 NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER PATH_DISCOVERY_TIME 2 * NET_TRAVERSAL_TIME ACTIVE_ROUTE_TIMEOUT 2 * NET_TRAVERSAL_TIME DELETE_PERIOD 5 * NET_TRAVERSAL_TIME RREQ_TRIES 3 RREQ_RATELIMIT 10 RERR_RATELIMIT 10 HELLO_INTERVAL 1,000 milliseconds ALLOWED_HELLO_LOSS 2 NEXT_HOP_WAIT 2 * NODE_TRAVERSAL_TIME BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME For correct operation ACTIVE_ROUTE_TIMEOUT MUST be greater than both (ALLOWED_HELLO_LOSS * HELLO_INTERVAL) and NET_TRAVERSAL_TIME. Likewise, DELETE_PERIOD MUST be greater than ACTIVE_ROUTE_TIMEOUT. 12. Security Considerations Currently, AODV does not specify any special security measures. Routing protocols, however, are prime targets for impersonation attacks. In networks where the node membership is not known, it is difficult to determine the occurrence of impersonation attacks, and security prevention techniques are difficult at best. However, when the network membership is known and there is a danger of such attacks, AODV control messages must be protected by the use of authentication techniques, such as those involving generation of unforgeable and cryptographically strong message digests or digital signatures. While AODV does not place restrictions on the authentication mechanism used for this purpose, IPsec Authentication Header (AH) is an appropriate choice for cases where the nodes share an appropriate security association that enables the use of AH. In particular, RREP messages SHOULD be authenticated to avoid creation of spurious routes to a destination. Otherwise, an attacker could masquerade as that destination, and maliciously deny service to the destination and/or maliciously inspect and consume traffic intended for delivery to the destination. RERR messages, while less dangerous, SHOULD be authenticated in order to prevent malicious nodes from disrupting active routes between communicating nodes. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 24] Internet Draft AODV 26 Jan 2004 AODV does not make any assumption about the method by which addresses are assigned to the mobile nodes except that they are presumed to have unique IP addresses. Therefore, no special consideration, other than what is natural because of the general protocol specifications, can be made about the applicability of IPsec authentication headers or key exchange mechanisms. However, if the mobile nodes in the ad hoc network have preestablished security associations, it is presumed that the purposes for which the security associations are created include that of authorizing the processing of AODV control messages. Given this understanding, the mobile nodes should be able to use the same authentication mechanisms based on their IP addresses as they would have used otherwise. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 25] Internet Draft AODV 26 Jan 2004 13. IANA Considerations AODV defines a "Type" field for messages sent to port 654. A new registry is to be created for the values for this Type field, and the following values assigned: Message Type Value --------------------------- ----- Route Request (RREQ) 1 Route Reply (RREP) 2 Route Error (RERR) 3 Route-Reply Ack (RREP-ACK) 4 AODV control messages can have extensions. Currently, only one extension is defined. A new registry is to be created for the Type field of the extensions: Extension Type Value --------------------------- ----- Lifetime 1 Future values of the Message Type or Extension Type can be allocated using standards action [2]. 14. Acknowledgments Special thanks to Samir Das, University of Cincinnati, for his extensive contributions to prior revisions. We acknowledge with gratitude the work done at University of Pennsylvania within Carl Gunter's group, as well as at Stanford and CMU, to determine some conditions (especially involving reboots and lost RERRs) under which previous versions of AODV could suffer from routing loops. Contributors to those efforts include Karthikeyan Bhargavan, Joshua Broch, Dave Maltz, Madanlal Musuvathi, and Davor Obradovic. The idea of a DELETE_PERIOD, for which expired routes (and, in particular, the sequence numbers) to a particular destination must be maintained, was also suggested by them. We also acknowledge the comments and improvements suggested by Sung-Ju Lee, Mahesh Marina, Erik Nordstrom, Yves Prelot, Marc Mosko, Manel Guerrero Zapata, Philippe Jacquet, Fred Baker, and Chris Shiflet. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 26] Internet Draft AODV 26 Jan 2004 We also acknowledge David Johnson, David Maltz and Yih-Chun Hu for presenting path accumulation, part of the DSR protocol [7]. AODVbis uses path accumulation to disseminate routing information during route discovery and reduce the number of route requests. References [1] S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, March 1997. [2] T. Narten and H. Alvestrand. Guidelines for Writing an IANA Considerations Section in RFCs. Request for Comments (Best Current Practice) 2434, Internet Engineering Task Force, October 1998. [3] C. Perkins, E. Belding-Royer, and S. Das. Ad hoc on demand distance vector (AODV) routing (work in progress). Request for Comments (Experimental Standard) 3561, Internet Engineering Task Force, July 2003. [4] J. Manner et al. Mobility Related Terminology (work in progress). Internet Draft, Internet Engineering Task Force, November 2003. [5] Ian D. Chakeres and Luke Klein-Berndt. AODVjr: AODV Simplified. In ACM SIGMOBILE Mobile Computing and Communications Review, pages 100--101, July 2002. [6] Karthikeyan Bhargavan, Carl A. Gunter, and Davor Obradovic. Fault Origin Adjudication. In Proceedings of the Workshop on Formal Methods in Software Practice, Portland, OR, August 2000. [7] D. Johnson and D. Maltz. Dynamic source routing in ad-hoc wireless networks. In Computer Communications Review -- Proceedings of SIGCOMM '96, August 1996. References [1], [2] and [3] are normative; all others are informative. Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 27] Internet Draft AODV 26 Jan 2004 A. Draft Modifications The following are major changes between this version (01) of the AODV draft and previous versions: - Removed valid/invalid route definition in favor of active/inactive route. - Allow and specified operation for nodes that forward RREP using active route information instead of accumulated path information. - Clarified Sequence Number handling upon RREP receipt. - Clarified Hostid Size field meaning. - Reduced the strict dependence on hop count during route update decision. - Added IPv6 Operation Section. Author's Addresses Questions about this memo can be directed to: Charles E. Perkins Communications Systems Laboratory Nokia Research Center 313 Fairchild Drive Mountain View, CA 94303 USA +1 650 625 2986 +1 650 691 2170 (fax) charles.perkins@nokia.com Elizabeth M. Belding-Royer Department of Computer Science University of California, Santa Barbara Santa Barbara, CA 93106 +1 805 893 3411 +1 805 893 8553 (fax) ebelding@cs.ucsb.edu Ian D. Chakeres Department of Electrical and Computer Engineering University of California, Santa Barbara Santa Barbara, CA 93106 Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 28] Internet Draft AODV 26 Jan 2004 +1 805 893 8981 +1 805 893 8553 (fax) idc@engineering.ucsb.edu Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 29]