idnits 2.17.1 draft-ietf-manet-aodv-13.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 181: '...ss as a destination IP address MUST be...' RFC 2119 keyword, line 213: '...ed words such as MUST, SHOULD, etc., t...' RFC 2119 keyword, line 424: '...tion (and precursor data) MUST be kept...' RFC 2119 keyword, line 461: '... message; MUST be at least 1....' RFC 2119 keyword, line 480: '...ent (RREP-ACK) message MUST be sent in...' (73 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: A node participating in the ad hoc network must take certain actions after reboot as it might lose all sequence number records for all destinations, including its own sequence number. However, there may be neighboring nodes that are using this node as an active next hop. This can potentially create routing loops. To prevent this possibility, each node on reboot waits for DELETE_PERIOD before transmitting any route discovery messages. 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 MUST not forward any control packets. If the node receives a data packet for some other destination, it SHOULD broadcast a RERR as described in subsection 6.11 and MUST reset the waiting timer to expire after current time plus DELETE_PERIOD. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2434 (ref. '2') (Obsoleted by RFC 5226) == Outdated reference: A later version (-04) exists of draft-manner-seamoby-terms-02 -- Possible downref: Normative reference to a draft: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' Summary: 6 errors (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Mobile Ad Hoc Networking Working Group Charles E. Perkins 2 INTERNET DRAFT Nokia Research Center 3 17 February 2003 Elizabeth M. Belding-Royer 4 University of California, Santa Barbara 5 Samir R. Das 6 University of Cincinnati 8 Ad hoc On-Demand Distance Vector (AODV) Routing 9 draft-ietf-manet-aodv-13.txt 11 Status of This Memo 13 This document is a submission by the Mobile Ad Hoc Networking Working 14 Group of the Internet Engineering Task Force (IETF). Comments should 15 be submitted to the manet@ietf.org mailing list. 17 Distribution of this memo is unlimited. 19 This document is an Internet-Draft and is in full conformance with 20 all provisions of Section 10 of RFC2026. Internet-Drafts are working 21 documents of the Internet Engineering Task Force (IETF), its areas, 22 and its working groups. Note that other groups may also distribute 23 working documents as Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at 27 any time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at: 31 http://www.ietf.org/ietf/1id-abstracts.txt 32 The list of Internet-Draft Shadow Directories can be accessed at: 33 http://www.ietf.org/shadow.html. 35 Abstract 37 The Ad hoc On-Demand Distance Vector (AODV) routing protocol 38 is intended for use by mobile nodes in an ad hoc network. It 39 offers quick adaptation to dynamic link conditions, low processing 40 and memory overhead, low network utilization, and determines 41 unicast routes to destinations within the ad hoc network. It uses 42 destination sequence numbers to ensure loop freedom at all times 43 (even in the face of anomalous delivery of routing control messages), 44 avoiding problems (such as ``counting to infinity'') associated with 45 classical distance vector protocols. 47 Contents 49 Status of This Memo i 51 Abstract i 53 1. Introduction 1 55 2. Overview 1 57 3. AODV Terminology 3 59 4. Applicability Statement 5 61 5. Message Formats 5 62 5.1. Route Request (RREQ) Message Format . . . . . . . . . . . 5 63 5.2. Route Reply (RREP) Message Format . . . . . . . . . . . . 7 64 5.3. Route Error (RERR) Message Format . . . . . . . . . . . . 8 65 5.4. Route Reply Acknowledgment (RREP-ACK) Message Format . . 9 67 6. AODV Operation 9 68 6.1. Maintaining Sequence Numbers . . . . . . . . . . . . . . 10 69 6.2. Route Table Entries and Precursor Lists . . . . . . . . . 11 70 6.3. Generating Route Requests . . . . . . . . . . . . . . . . 12 71 6.4. Controlling Dissemination of Route Request Messages . . . 13 72 6.5. Processing and Forwarding Route Requests . . . . . . . . 14 73 6.6. Generating Route Replies . . . . . . . . . . . . . . . . 16 74 6.6.1. Route Reply Generation by the Destination . . . . 16 75 6.6.2. Route Reply Generation by an Intermediate Node . 17 76 6.6.3. Generating Gratuitous RREPs . . . . . . . . . . . 17 77 6.7. Receiving and Forwarding Route Replies . . . . . . . . . 18 78 6.8. Operation over Unidirectional Links . . . . . . . . . . . 19 79 6.9. Hello Messages . . . . . . . . . . . . . . . . . . . . . 20 80 6.10. Maintaining Local Connectivity . . . . . . . . . . . . . 21 81 6.11. Route Error (RERR) Messages, Route Expiry and Route 82 Deletion . . . . . . . . . . . . . . . . . . . . . . . 22 83 6.12. Local Repair . . . . . . . . . . . . . . . . . . . . . . 23 84 6.13. Actions After Reboot . . . . . . . . . . . . . . . . . . 25 85 6.14. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 26 87 7. AODV and Aggregated Networks 26 89 8. Using AODV with Other Networks 27 91 9. Extensions 28 92 9.1. Hello Interval Extension Format . . . . . . . . . . . . . 28 94 10. Configuration Parameters 29 96 11. Security Considerations 31 98 12. IANA Considerations 32 100 13. IPv6 Considerations 32 102 14. Acknowledgments 32 104 A. Draft Modifications 34 106 1. Introduction 108 The Ad hoc On-Demand Distance Vector (AODV) algorithm enables 109 dynamic, self-starting, multihop routing between participating mobile 110 nodes wishing to establish and maintain an ad hoc network. AODV 111 allows mobile nodes to obtain routes quickly for new destinations, 112 and does not require nodes to maintain routes to destinations that 113 are not in active communication. AODV allows mobile nodes to respond 114 to link breakages and changes in network topology in a timely manner. 115 The operation of AODV is loop-free, and by avoiding the Bellman-Ford 116 ``counting to infinity'' problem offers quick convergence when the 117 ad hoc network topology changes (typically, when a node moves in the 118 network). When links break, AODV causes the affected set of nodes to 119 be notified so that they are able to invalidate the routes using the 120 lost link. 122 One distinguishing feature of AODV is its use of a destination 123 sequence number for each route entry. The destination sequence 124 number is created by the destination to be included along with any 125 route information it sends to requesting nodes. Using destination 126 sequence numbers ensures loop freedom and is simple to program. 127 Given the choice between two routes to a destination, a requesting 128 node is required to select the one with the greatest sequence number. 130 2. Overview 132 Route Requests (RREQs), Route Replies (RREPs), and Route Errors 133 (RERRs) are the message types defined by AODV. These message types 134 are received via UDP, and normal IP header processing applies. 135 So, for instance, the requesting node is expected to use its IP 136 address as the Originator IP address for the messages. For broadcast 137 messages, the IP limited broadcast address (255.255.255.255) is used. 138 This means that such messages are not blindly forwarded. However, 139 AODV operation does require certain messages (e.g., RREQ) to be 140 disseminated widely, perhaps throughout the ad hoc network. The 141 range of dissemination of such RREQs is indicated by the TTL in the 142 IP header. Fragmentation is typically not required. 144 As long as the endpoints of a communication connection have valid 145 routes to each other, AODV does not play any role. When a route to a 146 new destination is needed, the node broadcasts a RREQ to find a route 147 to the destination. A route can be determined when the RREQ reaches 148 either the destination itself, or an intermediate node with a 'fresh 149 enough' route to the destination. A 'fresh enough' route is a valid 150 route entry for the destination whose associated sequence number is 151 at least as great as that contained in the RREQ. The route is made 152 available by unicasting a RREP back to the origination of the RREQ. 153 Each node receiving the request caches a route back to the originator 154 of the request, so that the RREP can be unicast from the destination 155 along a path to that originator, or likewise from any intermediate 156 node that is able to satisfy the request. 158 Nodes monitor the link status of next hops in active routes. When a 159 link break in an active route is detected, a RERR message is used to 160 notify other nodes that the loss of that link has occurred. The RERR 161 message indicates those destinations (possibly subnets) which are no 162 longer reachable by way of the broken link. In order to enable this 163 reporting mechanism, each node keeps a ``precursor list'', containing 164 the IP address for each its neighbors that are likely to use it as a 165 next hop towards each destination. The information in the precursor 166 lists is most easily acquired during the processing for generation 167 of a RREP message, which by definition has to be sent to a node in a 168 precursor list (see section 6.6). If the RREP has a nonzero prefix 169 length, then the originator of the RREQ which solicited the RREP 170 information is included among the precursors for the subnet route 171 (not specifically for the particular destination). 173 A RREQ may also be received for a multicast IP address. In this 174 document, full processing for such messages is not specified. For 175 example, the originator of such a RREQ for a multicast IP address 176 may have to follow special rules. However, it is important to 177 enable correct multicast operation by intermediate nodes that are 178 not enabled as originating or destination nodes for IP multicast 179 addresses, and likewise are not equipped for any special multicast 180 protocol processing. For such multicast-unaware nodes, processing 181 for a multicast IP address as a destination IP address MUST be 182 carried out in the same way as for any other destination IP address. 184 AODV is a routing protocol, and it deals with route table 185 management. Route table information must be kept even 186 for short-lived routes, such as are created to temporarily 187 store reverse paths towards nodes originating RREQs. AODV 188 uses the following fields with each route table entry: 190 - Destination IP Address 191 - Destination Sequence Number 192 - Valid Destination Sequence Number flag 193 - 194 - Other state and routing flags (e.g., valid, invalid, repairable, 195 being repaired) 196 - Network Interface 197 - Hop Count (number of hops needed to reach destination) 198 - Next Hop 199 - List of Precursors (described in Section 6.2) 200 - Lifetime (expiration or deletion time of the route) 202 Managing the sequence number is crucial to avoiding routing loops, 203 even when links break and a node is no longer reachable to supply 204 its own information about its sequence number. A destination 205 becomes unreachable when a link breaks or is deactivated. When these 206 conditions occur, the route is invalidated by operations involving 207 the sequence number and marking the route table entry state as 208 invalid. See section 6.1 for details. 210 3. AODV Terminology 212 This protocol specification uses conventional meanings [1] for 213 capitalized words such as MUST, SHOULD, etc., to indicate requirement 214 levels for various protocol features. This section defines other 215 terminology used with AODV that is not already defined in [3]. 217 active route 219 A route towards a destination that has a routing table entry 220 that is marked as valid. Only active routes can be used to 221 forward data packets. 223 broadcast 225 Broadcasting means transmitting to the IP Limited Broadcast 226 address, 255.255.255.255. A broadcast packet may not be 227 blindly forwarded, but broadcasting is useful to enable 228 dissemination of AODV messages throughout the ad hoc network. 230 destination 232 An IP address to which data packets are to be transmitted. 233 Same as "destination node". A node knows it is the destination 234 node for a typical data packet when its address appears in the 235 appropriate field of the IP header. Routes for destination 236 nodes are supplied by action of the AODV protocol, which 237 carries the IP address of the desired destination node in route 238 discovery messages. 240 forwarding node 242 A node that agrees to forward packets destined for another 243 node, by retransmitting them to a next hop that is closer to 244 the unicast destination along a path that has been set up using 245 routing control messages. 247 forward route 249 A route set up to send data packets from a node originating a 250 Route Discovery operation towards its desired destination. 252 invalid route 254 A route that has expired, denoted by a state of invalid in 255 the routing table entry. An invalid route is used to store 256 previously valid route information for an extended period of 257 time. An invalid route cannot be used to forward data packets, 258 but it can provide information useful for route repairs, and 259 also for future RREQ messages. 261 originating node 263 A node that initiates an AODV route discovery message to be 264 processed and possibly retransmitted by other nodes in the 265 ad hoc network. For instance, the node initiating a Route 266 Discovery process and broadcasting the RREQ message is called 267 the originating node of the RREQ message. 269 reverse route 271 A route set up to forward a reply (RREP) packet back to the 272 originator from the destination or from an intermediate node 273 having a route to the destination. 275 sequence number 277 A monotonically increasing number maintained by each 278 originating node. In AODV routing protocol messages, it 279 is used by other nodes to determine the freshness of the 280 information contained from the originating node. 282 valid route 284 See active route. 286 4. Applicability Statement 288 The AODV routing protocol is designed for mobile ad hoc networks 289 with populations of tens to thousands of mobile nodes. AODV can 290 handle low, moderate, and relatively high mobility rates, as well 291 as a variety of data traffic levels. AODV is designed for use in 292 networks where the nodes can all trust each other, either by use 293 of preconfigured keys, or because it is known that there are no 294 malicious intruder nodes. AODV has been designed to reduce the 295 dissemination of control traffic and eliminate overhead on data 296 traffic, in order to improve scalability and performance. 298 5. Message Formats 300 5.1. Route Request (RREQ) Message Format 302 0 1 2 3 303 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 304 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 305 | Type |J|R|G|D|U| Reserved | Hop Count | 306 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 307 | RREQ ID | 308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 309 | Destination IP Address | 310 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 311 | Destination Sequence Number | 312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 313 | Originator IP Address | 314 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 315 | Originator Sequence Number | 316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 318 The format of the Route Request message is illustrated above, and 319 contains the following fields: 321 Type 1 323 J Join flag; reserved for multicast. 325 R Repair flag; reserved for multicast. 327 G Gratuitous RREP flag; indicates whether a 328 gratuitous RREP should be unicast to the node 329 specified in the Destination IP Address field (see 330 sections 6.3, 6.6.3) 332 D Destination only flag; indicates only the 333 destination may respond to this RREQ (see 334 section 6.5). 336 U Unknown sequence number; indicates the destination 337 sequence number is unknown (see section 6.3). 339 Reserved Sent as 0; ignored on reception. 341 Hop Count The number of hops from the Originator IP Address 342 to the node handling the request. 344 RREQ ID A sequence number uniquely identifying the 345 particular RREQ when taken in conjunction with the 346 originating node's IP address. 348 Destination IP Address 349 The IP address of the destination for which a route 350 is desired. 352 Destination Sequence Number 353 The latest sequence number received in the past 354 by the originator for any route towards the 355 destination. 357 Originator IP Address 358 The IP address of the node which originated the 359 Route Request. 361 Originator Sequence Number 362 The current sequence number to be used in the route 363 entry pointing towards the originator of the route 364 request. 366 5.2. Route Reply (RREP) Message Format 368 0 1 2 3 369 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 370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 371 | Type |R|A| Reserved |Prefix Sz| Hop Count | 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 373 | Destination IP address | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 375 | Destination Sequence Number | 376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 377 | Originator IP address | 378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 379 | Lifetime | 380 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 382 The format of the Route Reply message is illustrated above, and 383 contains the following fields: 385 Type 2 387 R Repair flag; used for multicast. 389 A Acknowledgment required; see sections 5.4 and 6.7. 391 Reserved Sent as 0; ignored on reception. 393 Prefix Size If nonzero, the 5-bit Prefix Size specifies that the 394 indicated next hop may be used for any nodes with 395 the same routing prefix (as defined by the Prefix 396 Size) as the requested destination. 398 Hop Count The number of hops from the Originator IP Address 399 to the Destination IP Address. For multicast route 400 requests this indicates the number of hops to the 401 multicast tree member sending the RREP. 403 Destination IP Address 404 The IP address of the destination for which a route 405 is supplied. 407 Destination Sequence Number 408 The destination sequence number associated to the 409 route. 411 Originator IP Address 412 The IP address of the node which originated the RREQ 413 for which the route is supplied. 415 Lifetime The time in milliseconds for which nodes receiving 416 the RREP consider the route to be valid. 418 Note that the Prefix Size allows a subnet router to supply a route 419 for every host in the subnet defined by the routing prefix, which 420 is determined by the IP address of the subnet router and the Prefix 421 Size. In order to make use of this feature, the subnet router has 422 to guarantee reachability to all the hosts sharing the indicated 423 subnet prefix. See section 7 for details. When the prefix size is 424 nonzero, any routing information (and precursor data) MUST be kept 425 with respect to the subnet route, not the individual destination IP 426 address on that subnet. 428 The 'A' bit is used when the link over which the RREP message is sent 429 may be unreliable or unidirectional. When the RREP message contains 430 the 'A' bit set, the receiver of the RREP is expected to return a 431 RREP-ACK message. See section 6.8. 433 5.3. Route Error (RERR) Message Format 435 0 1 2 3 436 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 437 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 438 | Type |N| Reserved | DestCount | 439 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 440 | Unreachable Destination IP Address (1) | 441 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 442 | Unreachable Destination Sequence Number (1) | 443 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| 444 | Additional Unreachable Destination IP Addresses (if needed) | 445 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 446 |Additional Unreachable Destination Sequence Numbers (if needed)| 447 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 The format of the Route Error message is illustrated above, and 450 contains the following fields: 452 Type 3 454 N No delete flag; set when a node has performed a local 455 repair of a link, and upstream nodes should not delete 456 the route. 458 Reserved Sent as 0; ignored on reception. 460 DestCount The number of unreachable destinations included in the 461 message; MUST be at least 1. 463 Unreachable Destination IP Address 464 The IP address of the destination that has become 465 unreachable due to a link break. 467 Unreachable Destination Sequence Number 468 The sequence number in the route table entry for 469 the destination listed in the previous Unreachable 470 Destination IP Address field. 472 The RERR message is sent whenever a link break causes one or more 473 destinations to become unreachable from some of the node's neighbors. 474 See section 6.2 for information about how to maintain the appropriate 475 records for this determination, and section 6.11 for specification 476 about how to create the list of destinations. 478 5.4. Route Reply Acknowledgment (RREP-ACK) Message Format 480 The Route Reply Acknowledgment (RREP-ACK) message MUST be sent in 481 response to a RREP message with the 'A' bit set (see section 5.2). 482 This is typically done when there is danger of unidirectional 483 links preventing the completion of a Route Discovery cycle (see 484 section 6.8). 486 0 1 487 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 489 | Type | Reserved | 490 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 492 Type 4 494 Reserved Sent as 0; ignored on reception. 496 6. AODV Operation 498 This section describes the scenarios under which nodes generate Route 499 Request (RREQ), Route Reply (RREP) and Route Error (RERR) messages 500 for unicast communication towards a destination, and how the message 501 data are handled. In order to process the messages correctly, 502 certain state information has to be maintained in the route table 503 entries for the destinations of interest. 505 All AODV messages are sent to port 654 using UDP. 507 6.1. Maintaining Sequence Numbers 509 Every route table entry at every node MUST include the latest 510 information available about the sequence number for the IP address of 511 the destination node for which the route table entry is maintained. 512 This sequence number is called the "destination sequence number". It 513 is updated whenever a node receives new (i.e., not stale) information 514 about the sequence number from RREQ, RREP, or RERR messages that 515 may be received related to that destination. AODV depends on each 516 node in the network to own and maintain its destination sequence 517 number to guarantee the loop-freedom of all routes towards that 518 node. A destination node increments its own sequence number in two 519 circumstances: 521 - Immediately before a node originates a route discovery, it MUST 522 increment its own sequence number. This prevents conflicts with 523 previously established reverse routes towards the originator of a 524 RREQ. 525 - Immediately before a destination node originates a RREP in 526 response to a RREQ, it MUST update its own sequence number to 527 the maximum of its current sequence number and the destination 528 sequence number in the RREQ packet. 530 When the destination increments its sequence number, it MUST do so 531 by treating the sequence number value as if it were an unsigned 532 number. To accomplish sequence number rollover, if the sequence 533 number has already been assigned to be the largest possible number 534 representable as a 32-bit unsigned integer (i.e., 4294967295), then 535 when it is incremented it will then have a value of zero (0). On 536 the other hand, if the sequence number currently has the value 537 2147483647, which is the largest possible positive integer if 2's 538 complement arithmetic is in use with 32-bit integers, the next value 539 will be 2147483648, which is the most negative possible integer in 540 the same numbering system. The representation of negative numbers 541 is not relevant to the increment of AODV sequence numbers. This is 542 in contrast to the manner in which the result of comparing two AODV 543 sequence numbers is to be treated (see below). 545 In order to ascertain that information about a destination is not 546 stale, the node compares its current numerical value for the sequence 547 number with that obtained from the incoming AODV message. This 548 comparison MUST be done using signed 32-bit arithmetic, this is 549 necessary to accomplish sequence number rollover. If the result of 550 subtracting the currently stored sequence number from the value of 551 the incoming sequence number is less than zero, then the information 552 related to that destination in the AODV message MUST be discarded, 553 since that information is stale compared to the node's currently 554 stored information. 556 The only other circumstance in which a node may change the 557 destination sequence number in one of its route table entries is 558 in response to a lost or expired link to the next hop towards that 559 destination. The node determines which destinations use a particular 560 next hop by consulting its routing table. In this case, for each 561 destination that uses the next hop, the node increments the sequence 562 number and marks the route as invalid (see also sections 6.11, 6.12). 563 Whenever any fresh enough (i.e., containing a sequence number at 564 least equal to the recorded sequence number) routing information for 565 an affected destination is received by a node that has marked that 566 route table entry as invalid, the node SHOULD update its route table 567 information according to the information contained in the update. 569 A node may change the sequence number in the routing table entry of a 570 destination only if: 572 - it is itself the destination node, and offers a new route to 573 itself, or 575 - it receives an AODV message with new information about the 576 sequence number for a destination node, or 578 - the path towards the destination node expires or breaks. 580 6.2. Route Table Entries and Precursor Lists 582 When a node receives an AODV control packet from a neighbor, or 583 creates or updates a route for a particular destination or subnet, 584 it checks its route table for an entry for the destination. In the 585 event that there is no corresponding entry for that destination, an 586 entry is created. The sequence number is either determined from 587 the information contained in the control packet, or else the valid 588 sequence number field is set to false. The route is only updated if 589 the new sequence number is either 591 (i) higher than the destination sequence number in the route 592 table, or 594 (ii) the sequence numbers are equal, but the hop count (of 595 the new information) plus one, is smaller than the 596 existing hop count in the routing table, or 598 (iii) the sequence number is unknown. 600 The Lifetime field of the routing table entry is either 601 determined from the control packet, or it is initialized to 602 ACTIVE_ROUTE_TIMEOUT. This route may now be used to send any queued 603 data packets and fulfills any outstanding route requests. 605 Each time a route is used to forward a data packet, its Active 606 Route Lifetime field of the source, destination and the next hop 607 on the path to the destination is updated to be no less than the 608 current time plus ACTIVE_ROUTE_TIMEOUT. Since the route between 609 each originator and destination pair is expected to be symmetric, 610 the Active Route Lifetime for the previous hop, along the reverse 611 path back to the IP source, is also updated to be no less than the 612 current time plus ACTIVE_ROUTE_TIMEOUT. The lifetime for an Active 613 Route is updated each time the route is used regardless of whether 614 the destination is a single node or a subnet. 616 For each valid route maintained by a node as a routing table entry, 617 the node also maintains a list of precursors that may be forwarding 618 packets on this route. These precursors will receive notifications 619 from the node in the event of detection of the loss of the next hop 620 link. The list of precursors in a routing table entry contains those 621 neighboring nodes to which a route reply was generated or forwarded. 623 6.3. Generating Route Requests 625 A node disseminates a RREQ when it determines that it needs a route 626 to a destination and does not have one available. This can happen if 627 the destination is previously unknown to the node, or if a previously 628 valid route to the destination expires or is marked as invalid. The 629 Destination Sequence Number field in the RREQ message is the last 630 known destination sequence number for this destination and is copied 631 from the Destination Sequence Number field in the routing table. If 632 no sequence number is known, the unknown sequence number flag MUST 633 be set. The Originator Sequence Number in the RREQ message is the 634 node's own sequence number, which is incremented prior to insertion 635 in a RREQ. The RREQ ID field is incremented by one from the last RREQ 636 ID used by the current node. Each node maintains only one RREQ ID. 637 The Hop Count field is set to zero. 639 Before broadcasting the RREQ, the originating node buffers the RREQ 640 ID and the Originator IP address (its own address) of the RREQ for 641 PATH_DISCOVERY_TIME. In this way, when the node receives the packet 642 again from its neighbors, it will not reprocess and re-forward the 643 packet. 645 An originating node often expects to have bidirectional 646 communications with a destination node. In such cases, it is 647 not sufficient for the originating node to have a route to the 648 destination node; the destination must also have a route back to 649 the originating node. In order for this to happen as efficiently 650 as possible, any generation of a RREP by an intermediate node (as 651 in section 6.6) for delivery to the originating node SHOULD be 652 accompanied by some action that notifies the destination about a 653 route back to the originating node. The originating node selects 654 this mode of operation in the intermediate nodes by setting the `G' 655 flag. See section 6.6.3 for details about actions taken by the 656 intermediate node in response to a RREQ with the `G' flag set. 658 A node SHOULD NOT originate more than RREQ_RATELIMIT RREQ messages 659 per second. After broadcasting a RREQ, a node waits for a RREP (or 660 other control message with current information regarding a route to 661 the appropriate destination). If a route is not received within 662 NET_TRAVERSAL_TIME milliseconds, the node MAY try again to discover a 663 route by broadcasting another RREQ, up to a maximum of RREQ_RETRIES 664 times at the maximum TTL value. Each new attempt MUST increment and 665 update the RREQ ID. For each attempt, the TTL field of the IP header 666 is set according to the mechanism specified in section 6.4, in order 667 to enable control over how far the RREQ is disseminated for the each 668 retry. 670 Data packets waiting for a route (i.e., waiting for a RREP after a 671 RREQ has been sent) SHOULD be buffered. The buffering SHOULD be 672 "first-in, first-out" (FIFO). If a route discovery has been attempted 673 RREQ_RETRIES times at the maximum TTL without receiving any RREP, all 674 data packets destined for the corresponding destination SHOULD be 675 dropped from the buffer and a Destination Unreachable message SHOULD 676 be delivered to the application. 678 To reduce congestion in a network, repeated attempts by a source 679 node at route discovery for a single destination MUST utilize a 680 binary exponential backoff. The first time a source node broadcasts 681 a RREQ, it waits NET_TRAVERSAL_TIME milliseconds for the reception 682 of a RREP. If a RREP is not received within that time, the source 683 node sends a new RREQ. When calculating the time to wait for 684 the RREP after sending the second RREQ, the source node MUST use 685 a binary exponential backoff. Hence, the waiting time for the 686 RREP corresponding to the second RREQ is 2 * NET_TRAVERSAL_TIME 687 milliseconds. If a RREP is not receivied within this time period, 688 another RREQ may be sent, up to RREQ_RETRIES additional attempts 689 after the first RREQ. For each additional attempt, the waiting time 690 for the RREP is multiplied by 2, so that the time conforms to a 691 binary exponential backoff. 693 6.4. Controlling Dissemination of Route Request Messages 695 To prevent unnecessary network-wide dissemination of RREQs, the 696 originating node SHOULD use an expanding ring search technique. 697 In an expanding ring search, the originating node initially 698 uses a TTL = TTL_START in the RREQ packet IP header and sets the 699 timeout for receiving a RREP to RING_TRAVERSAL_TIME milliseconds. 700 RING_TRAVERSAL_TIME is calculcated as described in section 10. The 701 TTL_VALUE used in calculating RING_TRAVERSAL_TIME is set equal to 702 the value of the TTL field in the IP header. If the RREQ times out 703 without a corresponding RREP, the originator broadcasts the RREQ 704 again with the TTL incremented by TTL_INCREMENT. This continues until 705 the TTL set in the RREQ reaches TTL_THRESHOLD, beyond which a TTL = 706 NET_DIAMETER is used for each attempt. Each time, the timeout for 707 receiving a RREP is RING_TRAVERSAL_TIME. When it is desired to have 708 all retries traverse the entire ad hoc network, this can be achieved 709 by configuring TTL_START and TTL_INCREMENT both to be the same value 710 as NET_DIAMETER. 712 The Hop Count stored in an invalid routing table entry indicates 713 the last known hop count to that destination in the routing table. 714 When a new route to the same destination is required at a later time 715 (e.g., upon route loss), the TTL in the RREQ IP header is initially 716 set to the Hop Count plus TTL_INCREMENT. Thereafter, following 717 each timeout the TTL is incremented by TTL_INCREMENT until TTL = 718 TTL_THRESHOLD is reached. Beyond this TTL = NET_DIAMETER is used. 719 Once TTL = NET_DIAMETER, the timeout for waiting for the RREP is set 720 to NET_TRAVERSAL_TIME, as specified in section 6.3. 722 An expired routing table entry SHOULD NOT be expunged before 723 (current_time + DELETE_PERIOD) (see section 6.11). Otherwise, the 724 soft state corresponding to the route (e.g., last known hop count) 725 will be lost. Furthermore, a longer routing table entry expunge time 726 MAY be configured. Any routing table entry waiting for a RREP SHOULD 727 NOT be expunged before (current_time + 2 * NET_TRAVERSAL_TIME). 729 6.5. Processing and Forwarding Route Requests 731 When a node receives a RREQ, it first creates or updates a route to 732 the previous hop without a valid sequence number (see section 6.2) 733 then checks to determine whether it has received a RREQ with 734 the same Originator IP Address and RREQ ID within at least the 735 last PATH_DISCOVERY_TIME. If such a RREQ has been received, the 736 node silently discards the newly received RREQ. The rest of this 737 subsection describes actions taken for RREQs that are not discarded. 739 First, it first increments the hop count value in the RREQ by one, 740 to account for the new hop through the intermediate node. Then the 741 node searches for a reverse route to the Originator IP Address (see 742 section 6.2), using longest-prefix matching. If need be, the route 743 is created, or updated using the Originator Sequence Number from the 744 RREQ in its routing table. This reverse route will be needed if 745 the node receives a RREP back to the node that originated the RREQ 746 (identified by the Originator IP Address). When the reverse route 747 is created or updated, the following actions on the route are also 748 carried out: 750 1. the Originator Sequence Number from the RREQ is compared to the 751 corresponding destination sequence number in the route table 752 entry and copied if greater than the existing value there 754 2. the valid sequence number field is set to true; 756 3. the next hop in the routing table becomes the node from which the 757 RREQ was received (it is obtained from the source IP address in 758 the IP header and is often not equal to the Originator IP Address 759 field in the RREQ message); 761 4. the hop count is copied from the Hop Count in the RREQ message; 763 Whenever a RREQ message is received, the Lifetime of the reverse 764 route entry for the Originator IP address is set to be the maximum of 765 (ExistingLifetime, MinimalLifetime), where 767 MinimalLifetime = (current time + 2*NET_TRAVERSAL_TIME - 768 2*HopCount*NODE_TRAVERSAL_TIME). 770 The current node can use the reverse route to forward data packets in 771 the same way as for any other route in the routing table. 773 If a node does not generate a RREP (following the processing rules in 774 section 6.6), and if the incoming IP header has TTL larger than 1, 775 the node updates and broadcasts the RREQ to address 255.255.255.255 776 on each of its configured interfaces (see section 6.14). To update 777 the RREQ, the TTL or hop limit field in the outgoing IP header 778 is decreased by one, and the Hop Count field in the RREQ message 779 is incremented by one, to account for the new hop through the 780 intermediate node. Lastly, the Destination Sequence number for the 781 requested destination is set to the maximum of the corresponding 782 value received in the RREQ message, and the destination sequence 783 value currently maintained by the node for the requested destination. 784 However, the forwarding node MUST NOT modify its maintained value for 785 the destination sequence number, even if the value received in the 786 incoming RREQ is larger than the value currently maintained by the 787 forwarding node. 789 Otherwise, if a node does generate a RREP, then the node discards the 790 RREQ. Notice that, if intermediate nodes reply to every transmission 791 of RREQs for a particular destination, it might turn out that the 792 destination does not receive any of the discovery messages. In 793 this situation, the destination does not learn of a route to the 794 originating node from the RREQ messages. This could cause the 795 destination to initiate a route discovery (for example, if the 796 originator is attempting to establish a TCP session). In order 797 that the destination learn of routes to the originating node, the 798 originating node SHOULD set the ``gratuitous RREP'' ('G') flag in the 799 RREQ if for any reason the destination is likely to need a route to 800 the originating node. If, in response to a RREQ with the 'G' flag 801 set, an intermediate node returns a RREP, it MUST also unicast a 802 gratuitous RREP to the destination node (see section 6.6.3). 804 6.6. Generating Route Replies 806 A node generates a RREP if either: 808 (i) it is itself the destination, or 810 (ii) it has an active route to the destination, the 811 destination sequence number in the node's existing route 812 table entry for the destination is valid and greater 813 than or equal to the Destination Sequence Number of the 814 RREQ (comparison using signed 32-bit arithmetic), and 815 the ``destination only'' ('D') flag is NOT set. 817 When generating a RREP message, a node copies the Destination IP 818 Address and the Originator Sequence Number from the RREQ message 819 into the corresponding fields in the RREP message. Processing is 820 slightly different, depending on whether the node is itself the 821 requested destination (see section 6.6.1), or instead if it is an 822 intermediate node with an fresh enough route to the destination (see 823 section 6.6.2). 825 Once created, the RREP is unicast to the next hop toward the 826 originator of the RREQ, as indicated by the route table entry for 827 that originator. As the RREP is forwarded back towards the node 828 which originated the RREQ message, the Hop Count field is incremented 829 by one at each hop. Thus, when the RREP reaches the originator, the 830 Hop Count represents the distance, in hops, of the destination from 831 the originator. 833 6.6.1. Route Reply Generation by the Destination 835 If the generating node is the destination itself, it MUST increment 836 its own sequence number by one if the sequence number in the 837 RREQ packet is equal to that incremented value. Otherwise, the 838 destination does not change its sequence number before generating 839 the RREP message. The destination node places its (perhaps newly 840 incremented) sequence number into the Destination Sequence Number 841 field of the RREP, and enters the value zero in the Hop Count field 842 of the RREP. 844 The destination node copies the value MY_ROUTE_TIMEOUT (see 845 section 10) into the Lifetime field of the RREP. Each node MAY 846 reconfigure its value for MY_ROUTE_TIMEOUT, within mild constraints 847 (see section 10). 849 6.6.2. Route Reply Generation by an Intermediate Node 851 If the node generating the RREP is not the destination node, but 852 instead is an intermediate hop along the path from the originator 853 to the destination, it copies its known sequence number for the 854 destination into the Destination Sequence Number field in the RREP 855 message. 857 The intermediate node updates the forward route entry by placing the 858 last hop node (from which it received the RREQ, as indicated by the 859 source IP address field in the IP header) into the precursor list for 860 the forward route entry -- i.e., the entry for the Destination IP 861 Address. The intermediate node also updates its route table entry 862 for the node originating the RREQ by placing the next hop towards 863 the destination in the precursor list for the reverse route entry 864 -- i.e., the entry for the Originator IP Address field of the RREQ 865 message data. 867 The intermediate node places its distance in hops from the 868 destination (indicated by the hop count in the routing table) Count 869 field in the RREP. The Lifetime field of the RREP is calculated by 870 subtracting the current time from the expiration time in its route 871 table entry. 873 6.6.3. Generating Gratuitous RREPs 875 After a node receives a RREQ and responds with a RREP, it discards 876 the RREQ. If the RREQ has the 'G' flag set, and the intermediate 877 node returns a RREP to the originating node, it MUST also unicast a 878 gratuitous RREP to the destination node. The gratuitous RREP that is 879 to be sent to the desired destination contains the following values 880 in the RREP message fields: 882 Hop Count The Hop Count as indicated in the node's route table 883 entry for the originator 885 Destination IP Address 886 The IP address of the node that originated the RREQ 888 Destination Sequence Number 889 The Originator Sequence Number from the RREQ 891 Originator IP Address 892 The IP address of the Destination node in the RREQ 894 Lifetime The remaining lifetime of the route towards the 895 originator of the RREQ, as known by the intermediate 896 node. 898 The gratuitous RREP is then sent to the next hop along the path to 899 the destination node, just as if the destination node had already 900 issued a RREQ for the originating node and this RREP was produced 901 in response to that (fictitious) RREQ. The RREP that is sent to the 902 originator of the RREQ is the same whether or not the 'G' bit is set. 904 6.7. Receiving and Forwarding Route Replies 906 When a node receives a RREP message, it searches (using 907 longest-prefix matching) for a route to the previous hop. If needed, 908 a route is created for the previous hop, but without a valid sequence 909 number (see section 6.2). Next, the node then increments the hop 910 count value in the RREP by one, to account for the new hop through 911 the intermediate node. Call this incremented value the "New Hop 912 Count". Then the forward route for this destination is created if it 913 does not already exist. Otherwise, the node compares the Destination 914 Sequence Number in the message with its own stored destination 915 sequence number for the Destination IP Address in the RREP message. 916 Upon comparison, the existing entry is updated only in the following 917 circumstances: 919 (i) the sequence number in the routing table is marked as 920 invalid in route table entry. 922 (ii) the Destination Sequence Number in the RREP is greater 923 than the node's copy of the destination sequence number 924 and the known value is valid, or 926 (iii) the sequence numbers are the same, but the route is is 927 marked as inactive, or 929 (iv) the sequence numbers are the same, and the New Hop Count 930 is smaller than the hop count in route table entry. 932 If the route table entry to the destination is created or updated, 933 then the following actions occur: 935 - the route is marked as active, 937 - the destination sequence number is marked as valid, 939 - the next hop in the route entry is assigned to be the node 940 from which the RREP is received, which is indicated by the 941 source IP address field in the IP header, 943 - the hop count is set to the value of the New Hop Count, 945 - the expiry time is set to the current time plus the value of 946 the Lifetime in the RREP message, 948 - and the destination sequence number is the Destination 949 Sequence Number in the RREP message. 951 The current node can subsequently use this route to forward data 952 packets to the destination. 954 If the current node is not the node indicated by the Originator IP 955 Address in the RREP message AND a forward route has been created or 956 updated as described above, the node consults its route table entry 957 for the originating node to determine the next hop for the RREP 958 packet, and then forwards the RREP towards the originator using the 959 information in that route table entry. If a node forwards a RREP 960 over a link that is likely to have errors or be unidirectional, the 961 node SHOULD set the `A' flag to require that the recipient of the 962 RREP acknowledge receipt of the RREP by sending a RREP-ACK message 963 back (see section 6.8). 965 When any node transmits a RREP, the precursor list for the 966 corresponding destination node is updated by adding to it the 967 next hop node to which the RREP is forwarded. Also, at each 968 node the (reverse) route used to forward a RREP has its lifetime 969 changed to be the maximum of (existing-lifetime, (current time + 970 ACTIVE_ROUTE_TIMEOUT)). Finally, the precursor list for the next hop 971 towards the destination is updated to contain the next hop towards 972 the source. 974 6.8. Operation over Unidirectional Links 976 It is possible that a RREP transmission may fail, especially if the 977 RREQ transmission triggering the RREP occurs over a unidirectional 978 link. If no other RREP generated from the same route discovery 979 attempt reaches the node which originated the RREQ message, the 980 originator will reattempt route discovery after a timeout (see 981 section 6.3). However, the same scenario might well be repeated 982 without any improvement, and no route would be discovered even after 983 repeated retries. Unless corrective action is taken, this can happen 984 even when bidirectional routes between originator and destination 985 do exist. Link layers using broadcast transmissions for the RREQ 986 will not be able to detect the presence of such unidirectional links. 987 In AODV, any node acts on only the first RREQ with the same RREQ ID 988 and ignores any subsequent RREQs. Suppose, for example, that the 989 first RREQ arrives along a path that has one or more unidirectional 990 link(s). A subsequent RREQ may arrive via a bidirectional path 991 (assuming such paths exist), but it will be ignored. 993 To prevent this problem, when a node detects that its transmission of 994 a RREP message has failed, it remembers the next-hop of the failed 995 RREP in a ``blacklist'' set. Such failures can be detected via 996 the absence of a link-layer or network-layer acknowledgment (e.g., 997 RREP-ACK). A node ignores all RREQs received from any node in its 998 blacklist set. Nodes are removed from the blacklist set after a 999 BLACKLIST_TIMEOUT period (see section 10). This period should be set 1000 to the upper bound of the time it takes to perform the allowed number 1001 of route request retry attempts as described in section 6.3. 1003 Note that the RREP-ACK packet does not contain any information about 1004 which RREP it is acknowledging. The time at which the RREP-ACK 1005 is received will likely come just after the time when the RREP 1006 was sent with the 'A' bit. This information is expected to be 1007 sufficient to provide assurance to the sender of the RREP that the 1008 link is currently bidirectional, without any real dependence on the 1009 particular RREP message being acknowledged. However, that assurance 1010 typically cannot be expected to remain in force permanently. 1012 6.9. Hello Messages 1014 A node MAY offer connectivity information by broadcasting local Hello 1015 messages. A node SHOULD only use hello messages if it is part of an 1016 active route. Every HELLO_INTERVAL milliseconds, the node checks 1017 whether it has sent a broadcast (e.g., a RREQ or an appropriate layer 1018 2 message) within the last HELLO_INTERVAL. If it has not, it MAY 1019 broadcast a RREP with TTL = 1, called a Hello message, with the RREP 1020 message fields set as follows: 1022 Destination IP Address 1023 The node's IP address. 1025 Destination Sequence Number 1026 The node's latest sequence number. 1028 Hop Count 0 1030 Lifetime ALLOWED_HELLO_LOSS * HELLO_INTERVAL 1032 A node MAY determine connectivity by listening for packets from its 1033 set of neighbors. If, within the past DELETE_PERIOD, it has received 1034 a Hello message from a neighbor, and then for that neighbor does 1035 not receive any packets (Hello messages or otherwise) for more than 1036 ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node SHOULD 1037 assume that the link to this neighbor is currently lost. When this 1038 happens, the node SHOULD proceed as in Section 6.11. 1040 Whenever a node receives a Hello message from a neighbor, the 1041 node SHOULD make sure that it has an active route to the neighbor, 1042 and create one if necessary. If a route already exists, then the 1043 Lifetime for the route should be increased, if necessary, to be at 1044 least ALLOWED_HELLO_LOSS * HELLO_INTERVAL. The route to the neighbor, 1045 if it exists, MUST subsequently contain the latest Destination 1046 Sequence Number from the Hello message. The current node can now 1047 begin using this route to forward data packets. Routes that are 1048 created by hello messages and not used by any other active routes 1049 will have empty precursor lists and would not trigger a RERR message 1050 if the neighbor moves away and a neighbor timeout occurs. 1052 6.10. Maintaining Local Connectivity 1054 Each forwarding node SHOULD keep track of its continued connectivity 1055 to its active next hops (i.e., which next hops or precursors have 1056 forwarded packets to or from the forwarding node during the last 1057 ACTIVE_ROUTE_TIMEOUT), as well as neighbors that have transmitted 1058 Hello messages during the last (ALLOWED_HELLO_LOSS * HELLO_INTERVAL). 1059 A node can maintain accurate information about its continued 1060 connectivity to these active next hops, using one or more of the 1061 available link or network layer mechanisms, as described below. 1063 - Any suitable link layer notification, such as those provided by 1064 IEEE 802.11, can be used to determine connectivity, each time 1065 a packet is transmitted to an active next hop. For example, 1066 absence of a link layer ACK or failure to get a CTS after sending 1067 RTS, even after the maximum number of retransmission attempts, 1068 indicates loss of the link to this active next hop. 1070 - If layer-2 notification is not available, passive acknowledgment 1071 SHOULD be used when the next hop is expected to forward the 1072 packet, by listening to the channel for a transmission attempt 1073 made by the next hop. If transmission is not detected within 1074 NEXT_HOP_WAIT milliseconds or the next hop is the destination 1075 (and thus is not supposed to forward the packet) one of the 1076 following methods SHOULD be used to determine connectivity: 1078 * Receiving any packet (including a Hello message) from the 1079 next hop. 1081 * A RREQ unicast to the next hop, asking for a route to the 1082 next hop. 1084 * An ICMP Echo Request message unicast to the next hop. 1086 If a link to the next hop cannot be detected by any of these methods, 1087 the forwarding node SHOULD assume that the link is lost, and take 1088 corrective action by following the methods specified in Section 6.11. 1090 6.11. Route Error (RERR) Messages, Route Expiry and Route Deletion 1092 Generally, route error and link breakage processing requires the 1093 following steps: 1095 - Invalidating existing routes 1097 - Listing affected destinations 1099 - Determining which, if any, neighbors may be affected 1101 - Delivering an appropriate RERR to such neighbors 1103 A Route Error (RERR) message MAY be either broadcast (if there 1104 are many precursors), unicast (if there is only 1 precursor), 1105 or iteratively unicast to all precursors (if broadcast is 1106 inappropriate). Even when the RERR message is iteratively unicast 1107 to several precursors, it is considered to be a single control 1108 message for the purposes of the description in the text that follows. 1109 With that understanding, a node SHOULD NOT generate more than 1110 RERR_RATELIMIT RERR messages per second. 1112 A node initiates processing for a RERR message in three situations: 1114 (i) if it detects a link break for the next hop of an active 1115 route in its routing table while transmitting data (and 1116 route repair, if attempted, was unsuccessful), or 1118 (ii) if it gets a data packet destined to a node for which it 1119 does not have an active route and is not repairing (if 1120 using local repair), or 1122 (iii) if it receives a RERR from a neighbor for one or more 1123 active routes. 1125 For case (i), the node first makes a list of unreachable destinations 1126 consisting of the unreachable neighbor and any additional 1127 destinations (or subnets, see section 7) in the local routing 1128 table that use the unreachable neighbor as the next hop. In this 1129 case, if a subnet route is found to be newly unreachable, an IP 1130 destination address for the subnet is constructed by appending 1131 zeroes to the subnet prefix as shown in the route table entry. This 1132 is unambiguous, since the precursor is known to have route table 1133 information with a compatible prefix length for that subnet. 1135 For case (ii), there is only one unreachable destination, which is 1136 the destination of the data packet that cannot be delivered. For 1137 case (iii), the list should consist of those destinations in the RERR 1138 for which there exists a corresponding entry in the local routing 1139 table that has the transmitter of the received RERR as the next hop. 1141 Some of the unreachable destinations in the list could be used by 1142 neighboring nodes, and it may therefore be necessary to send a (new) 1143 RERR. The RERR should contain those destinations that are part of 1144 the created list of unreachable destinations and have a non-empty 1145 precursor list. 1147 The neighboring node(s) that should receive the RERR are all those 1148 that belong to a precursor list of at least one of the unreachable 1149 destination(s) in the newly created RERR. In case there is only one 1150 unique neighbor that needs to receive the RERR, the RERR SHOULD be 1151 unicast toward that neighbor. Otherwise the RERR is typically sent 1152 to the local broadcast address (Destination IP == 255.255.255.255, 1153 TTL == 1) with the unreachable destinations, and their corresponding 1154 destination sequence numbers, included in the packet. The DestCount 1155 field of the RERR packet indicates the number of unreachable 1156 destinations included in the packet. 1158 Just before transmitting the RERR, certain updates are made on the 1159 routing table that may affect the destination sequence numbers for 1160 the unreachable destinations. For each one of these destinations, 1161 the corresponding routing table entry is updated as follows: 1163 1. The destination sequence number of this routing entry, if it 1164 exists and is valid, is incremented for cases (i) and (ii) above, 1165 and copied from the incoming RERR in case (iii) above. 1167 2. The entry is invalidated by marking the route entry as invalid 1169 3. The Lifetime field is updated to current time plus DELETE_PERIOD. 1170 Before this time, the entry SHOULD NOT be deleted. 1172 Note that the Lifetime field in the routing table plays dual role 1173 -- for an active route it is the expiry time, and for an invalid 1174 route it is the deletion time. If a data packet is received for an 1175 invalid route, the Lifetime field is updated to current time plus 1176 DELETE_PERIOD. The determination of DELETE_PERIOD is discussed in 1177 Section 10. 1179 6.12. Local Repair 1181 When a link break in an active route occurs, the node upstream of 1182 that break MAY choose to repair the link locally if the destination 1183 was no farther than MAX_REPAIR_TTL hops away. To repair the link 1184 break, the node increments the sequence number for the destination 1185 and then broadcasts a RREQ for that destination. The TTL of the RREQ 1186 should initially be set to the following value: 1188 max(MIN_REPAIR_TTL, 0.5 * #hops) + LOCAL_ADD_TTL, 1190 where #hops is the number of hops to the sender (originator) of the 1191 currently undeliverable packet. Thus, local repair attempts will 1192 often be invisible to the originating node, and will always have TTL 1193 >= MIN_REPAIR_TTL + LOCAL_ADD_TTL. The node initiating the repair 1194 then waits the discovery period to receive RREPs in response to the 1195 RREQ. During local repair data packets SHOULD be buffered. If, at 1196 the end of the discovery period, the reparing node has not received 1197 a RREP (or other control message creating or updating the route) 1198 for that destination, it proceeds as described in Section 6.11 by 1199 transmitting a RERR message for that destination. 1201 On the other hand, if the node receives one or more RREPs (or 1202 other control message creating or updating the route to the desired 1203 destination) during the discovery period, it first compares the hop 1204 count of the new route with the value in the hop count field of the 1205 invalid route table entry for that destination. If the hop count of 1206 the newly determined route to the destination is greater than the 1207 hop count of the previously known route the node SHOULD issue a RERR 1208 message for the destination, with the 'N' bit set. Then it proceeds 1209 as described in Section 6.7, updating its route table entry for that 1210 destination. 1212 A node that receives a RERR message with the 'N' flag set MUST NOT 1213 delete the route to that destination. The only action taken should 1214 be the retransmission of the message, if the RERR arrived from the 1215 next hop along that route, and if there are one or more precursor 1216 nodes for that route to the destination. When the originating node 1217 receives a RERR message with the 'N' flag set, if this message 1218 came from its next hop along its route to the destination then 1219 the originating node MAY choose to reinitiate route discovery, as 1220 described in Section 6.3. 1222 Local repair of link breaks in routes sometimes results in increased 1223 path lengths to those destinations. Repairing the link locally is 1224 likely to increase the number of data packets that are able to be 1225 delivered to the destinations, since data packets will not be dropped 1226 as the RERR travels to the originating node. Sending a RERR to the 1227 originating node after locally repairing the link break may allow the 1228 originator to find a fresh route to the destination that is better, 1229 based on current node positions. However, it does not require the 1230 originating node to rebuild the route, as the originator may be done, 1231 or nearly done, with the data session. 1233 When a link breaks along an active route, there are often multiple 1234 destinations that become unreachable. The node that is upstream 1235 of the lost link tries an immediate local repair for only the one 1236 destination towards which the data packet was traveling. Other 1237 routes using the same link MUST be marked as invalid, but the node 1238 handling the local repair MAY flag each such newly lost route as 1239 locally repairable; this local repair flag in the route table MUST be 1240 reset when the route times out (e.g., after the route has been not 1241 been active for ACTIVE_ROUTE_TIMEOUT). Before the timeout occurs, 1242 these other routes will be repaired as needed when packets arrive for 1243 the other destinations. Hence, these routes are repaired as needed; 1244 if a data packet does not arrive for the route, then that route will 1245 not be repaired. Alternatively, depending upon local congestion, 1246 the node MAY begin the process of establishing local repairs for 1247 the other routes, without waiting for new packets to arrive. By 1248 proactively repairing the routes that have broken due to the loss 1249 of the link, incoming data packets for those routes will not be 1250 subject to the delay of repairing the route and can be immediately 1251 forwarded. However, repairing the route before a data packet is 1252 received for it runs the risk of repairing routes that are no longer 1253 in use. Therefore, depending upon the local traffic in the network 1254 and whether congestion is being experienced, the node MAY elect to 1255 proactively repair the routes before a data packet is received; 1256 otherwise, it can wait until a data is received, and then commence 1257 the repair of the route. 1259 6.13. Actions After Reboot 1261 A node participating in the ad hoc network must take certain actions 1262 after reboot as it might lose all sequence number records for all 1263 destinations, including its own sequence number. However, there 1264 may be neighboring nodes that are using this node as an active 1265 next hop. This can potentially create routing loops. To prevent 1266 this possibility, each node on reboot waits for DELETE_PERIOD 1267 before transmitting any route discovery messages. If the node 1268 receives a RREQ, RREP, or RERR control packet, it SHOULD create route 1269 entries as appropriate given the sequence number information in the 1270 control packets, but MUST not forward any control packets. If the 1271 node receives a data packet for some other destination, it SHOULD 1272 broadcast a RERR as described in subsection 6.11 and MUST reset the 1273 waiting timer to expire after current time plus DELETE_PERIOD. 1275 It can be shown [4] that by the time the rebooted node comes out 1276 of the waiting phase and becomes an active router again, none of 1277 its neighbors will be using it as an active next hop any more. Its 1278 own sequence number gets updated once it receives a RREQ from any 1279 other node, as the RREQ always carries the maximum destination 1280 sequence number seen en route. If no such RREQ arrives, the node 1281 MUST initialize its own sequence number to zero. 1283 6.14. Interfaces 1285 Because AODV should operate smoothly over wired, as well as wireless, 1286 networks, and because it is likely that AODV will also be used with 1287 multiple wireless devices, the particular interface over which 1288 packets arrive must be known to AODV whenever a packet is received. 1289 This includes the reception of RREQ, RREP, and RERR messages. 1290 Whenever a packet is received from a new neighbor, the interface 1291 on which that packet was received is recorded into the route table 1292 entry for that neighbor, along with all the other appropriate routing 1293 information. Similarly, whenever a route to a new destination is 1294 learned, the interface through which the destination can be reached 1295 is also recorded into the destination's route table entry. 1297 When multiple interfaces are available, a node retransmitting a RREQ 1298 message rebroadcasts that message on all interfaces that have been 1299 configured for operation in the ad-hoc network, except those on which 1300 it is known that all of the nodes neighbors have already received 1301 the RREQ For instance, for some broadcast media (e.g., Ethernet) it 1302 may be presumed that all nodes on the same link receive a broadcast 1303 message at the same time. When a node needs to transmit a RERR, it 1304 SHOULD only transmit it on those interfaces that have neighboring 1305 precursor nodes for that route. 1307 7. AODV and Aggregated Networks 1309 AODV has been designed for use by mobile nodes with IP addresses 1310 that are not necessarily related to each other, to create an ad hoc 1311 network. However, in some cases a collection of mobile nodes MAY 1312 operate in a fixed relationship to each other and share a common 1313 subnet prefix, moving together within an area where an ad hoc network 1314 has formed. Call such a collection of nodes a ``subnet''. In this 1315 case, it is possible for a single node within the subnet to advertise 1316 reachability for all other nodes on the subnet, by responding with 1317 a RREP message to any RREQ message requesting a route to any node 1318 with the subnet routing prefix. Call the single node the ``subnet 1319 router''. In order for a subnet router to operate the AODV protocol 1320 for the whole subnet, it has to maintain a destination sequence 1321 number for the entire subnet. In any such RREP message sent by the 1322 subnet router, the Prefix Size field of the RREP message MUST be 1323 set to the length of the subnet prefix. Other nodes sharing the 1324 subnet prefix SHOULD NOT issue RREP messages, and SHOULD forward RREQ 1325 messages to the subnet router. 1327 The processing for RREPs that give routes to subnets (i.e., have 1328 nonzero prefix length) is the same as processing for host-specific 1329 RREP messages. Every node that receives the RREP with prefix size 1330 information SHOULD create or update the route table entry for the 1331 subnet, including the sequence number supplied by the subnet router, 1332 and including the appropriate precursor information. Then, in the 1333 future the node can use the information to avoid sending future RREQs 1334 for other nodes on the same subnet. 1336 When a node uses a subnet route it may be that a packet is routed to 1337 an IP address on the subnet that is not assigned to any existing node 1338 in the ad hoc network. When that happens, the subnet router MUST 1339 return ICMP Host Unreachable message to the sending node. Upstream 1340 nodes receiving such an ICMP message SHOULD record the information 1341 that the partcular IP address is unreachable, but MUST NOT invalidate 1342 the route entry for any matching subnet prefix. 1344 If several nodes in the subnet advertise reachability to the subnet 1345 defined by the subnet prefix, the node with the lowest IP address 1346 is elected to be the subnet router, and all other nodes MUST stop 1347 advertising reachability. 1349 The behavior of default routes (i.e., routes with routing prefix 1350 length 0) is not defined in this specification. Selection of routes 1351 sharing prefix bits should be according to longest match first. 1353 8. Using AODV with Other Networks 1355 In some configurations, an ad hoc network may be able to provide 1356 connectivity between external routing domains that do not use AODV. 1357 If the points of contact to the other networks can act as subnet 1358 routers (see Section 7) for any relevant networks within the external 1359 routing domains, then the ad hoc network can maintain connectivity to 1360 the external routing domains. Indeed, the external routing networks 1361 can use the ad hoc network defined by AODV as a transit network. 1363 In order to provide this feature, a point of contact to an external 1364 network (call it an Infrastructure Router) has to act as the subnet 1365 router for every subnet of interest within the external network for 1366 which the Infrastructure Router can provide reachability. This 1367 includes the need for maintaining a destination sequence number for 1368 that external subnet. 1370 If multiple Infrastructure Routers offer reachability to the same 1371 external subnet, those Infrastructure Routers have to cooperate (by 1372 means outside the scope of this specification) to provide consistent 1373 AODV semantics for ad hoc access to those subnets. 1375 9. Extensions 1377 In this section, the format of extensions to the RREQ and RREP 1378 messages is specified. All such extensions appear after the message 1379 data, and have the following format: 1381 0 1 2 3 1382 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 1383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1384 | Type | Length | type-specific data ... 1385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1387 where: 1389 Type 1-255 1391 Length The length of the type-specific data, not including the 1392 Type and Length fields of the extension in bytes. 1394 Extensions with types between 128 and 255 may NOT be skipped. The 1395 rules for extensions will be spelled out more fully, and conform to 1396 the rules for handling IPv6 options. 1398 9.1. Hello Interval Extension Format 1400 0 1 2 3 1401 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 1402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1403 | Type | Length | Hello Interval ... | 1404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1405 | ... Hello Interval, continued | 1406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1408 Type 1 1410 Length 4 1412 Hello Interval 1413 The number of milliseconds between successive 1414 transmissions of a Hello message. 1416 The Hello Interval extension MAY be appended to a RREP message with 1417 TTL == 1, to be used by a neighboring receiver in determine how long 1418 to wait for subsequent such RREP messages (i.e., Hello messages; see 1419 section 6.9). 1421 10. Configuration Parameters 1423 This section gives default values for some important parameters 1424 associated with AODV protocol operations. A particular mobile node 1425 may wish to change certain of the parameters, in particular the 1426 NET_DIAMETER, MY_ROUTE_TIMEOUT, ALLOWED_HELLO_LOSS, RREQ_RETRIES, 1427 and possibly the HELLO_INTERVAL. In the latter case, the node 1428 should advertise the HELLO_INTERVAL in its Hello messages, by 1429 appending a Hello Interval Extension to the RREP message. Choice 1430 of these parameters may affect the performance of the protocol. 1431 Changing NODE_TRAVERSAL_TIME also changes the node's estimate 1432 of the NET_TRAVERSAL_TIME, and so can only be done with suitable 1433 knowledge about the behavior of other nodes in the ad hoc network. 1434 The configured value for MY_ROUTE_TIMEOUT MUST be at least 2 * 1435 PATH_DISCOVERY_TIME. 1437 Parameter Name Value 1438 ---------------------- ----- 1439 ACTIVE_ROUTE_TIMEOUT 3,000 Milliseconds 1440 ALLOWED_HELLO_LOSS 2 1441 BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME 1442 DELETE_PERIOD see note below 1443 HELLO_INTERVAL 1,000 Milliseconds 1444 LOCAL_ADD_TTL 2 1445 MAX_REPAIR_TTL 0.3 * NET_DIAMETER 1446 MIN_REPAIR_TTL see note below 1447 MY_ROUTE_TIMEOUT 2 * ACTIVE_ROUTE_TIMEOUT 1448 NET_DIAMETER 35 1449 NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER 1450 NEXT_HOP_WAIT NODE_TRAVERSAL_TIME + 10 1451 NODE_TRAVERSAL_TIME 40 milliseconds 1452 PATH_DISCOVERY_TIME 2 * NET_TRAVERSAL_TIME 1453 RERR_RATELIMIT 10 1454 RING_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * 1455 (TTL_VALUE + TIMEOUT_BUFFER) 1456 RREQ_RETRIES 2 1457 RREQ_RATELIMIT 10 1458 TIMEOUT_BUFFER 2 1459 TTL_START 1 1460 TTL_INCREMENT 2 1461 TTL_THRESHOLD 7 1462 TTL_VALUE see note below 1464 The MIN_REPAIR_TTL should be the last known hop count to 1465 the destination. If Hello messages are used, then the 1466 ACTIVE_ROUTE_TIMEOUT parameter value MUST be more than the 1467 value (ALLOWED_HELLO_LOSS * HELLO_INTERVAL). For a given 1468 ACTIVE_ROUTE_TIMEOUT value, this may require some adjustment to 1469 the value of the HELLO_INTERVAL, and consequently use of the Hello 1470 Interval Extension in the Hello messages. 1472 TTL_VALUE is the value of the TTL field in the IP header while the 1473 expanding ring search is being performed. This is described further 1474 in section 6.4. The TIMEOUT_BUFFER is configurable. Its purpose is 1475 to provide a buffer for the timeout so that if the RREP is delayed 1476 due to congestion, a timeout is less likely to occur while the RREP 1477 is still en route back to the source. To omit this buffer, set 1478 TIMEOUT_BUFFER = 0. 1480 DELETE_PERIOD is intended to provide an upper bound on the time 1481 for which an upstream node A can have a neighbor B as an active 1482 next hop for destination D, while B has invalidated the route to 1483 D. Beyond this time B can delete the (already invalidated) route 1484 to D. The determination of the upper bound depends somewhat on the 1485 characteristics of the underlying link layer. If Hello messages 1486 are used to determine the continued availability of links to next 1487 hop nodes, DELETE_PERIOD must be at least ALLOWED_HELLO_LOSS * 1488 HELLO_INTERVAL. If the link layer feedback is used to detect loss 1489 of link, DELETE_PERIOD must be at least ACTIVE_ROUTE_TIMEOUT. If 1490 hello messages are received from a neighbor but data packets to that 1491 neighbor are lost, (due to temporary link asymmetry, e.g.) we have 1492 to make more concrete assumptions about the underlying link layer. 1493 We assume that such asymmetry cannot persist beyond a certain time, 1494 say, a multiple K of HELLO_INTERVAL. In other words, a node will 1495 invariably receive at least one out of K subsequent Hello messages 1496 from a neighbor if the link is working and the neighbor is sending no 1497 other traffic. Covering all possibilities, 1499 DELETE_PERIOD = K * max (ACTIVE_ROUTE_TIMEOUT, HELLO_INTERVAL) 1500 (K = 5 is recommended). 1502 NET_DIAMETER measures the maximum possible number of hops between 1503 two nodes in the network. NODE_TRAVERSAL_TIME is a conservative 1504 estimate of the average one hop traversal time for packets and should 1505 include queuing delays, interrupt processing times and transfer 1506 times. ACTIVE_ROUTE_TIMEOUT SHOULD be set to a longer value (at 1507 least 10,000 milliseconds) if link-layer indications are used to 1508 detect link breakages such as in IEEE 802.11 [5] standard. TTL_START 1509 should be set to at least 2 if Hello messages are used for local 1510 connectivity information. Performance of the AODV protocol is 1511 sensitive to the chosen values of these constants, which often depend 1512 on the characteristics of the underlying link layer protocol, radio 1513 technologies etc. BLACKLIST_TIMEOUT should be suitably increased 1514 if an expanding ring search is used. In such cases, it should be 1515 {[(TTL_THRESHOLD - TTL_START)/TTL_INCREMENT] + 1 + RREQ_RETRIES} * 1516 NET_TRAVERSAL_TIME. This is to account for possible additional route 1517 discovery attempts. 1519 11. Security Considerations 1521 Currently, AODV does not specify any special security measures. 1522 Route protocols, however, are prime targets for impersonation 1523 attacks. In networks where the node membership is not known, it 1524 is difficult to determine the occurrence of impersonation attacks, 1525 and security prevention techniques are difficult at best. However, 1526 when the network membership is known and there is a danger of 1527 such attacks, AODV control messages must be protected by use of 1528 authentication techniques, such as those involving generation 1529 of unforgeable and cryptographically strong message digests or 1530 digital signatures. While AODV does not place restrictions on the 1531 authentication mechanism used for this purpose, IPsec AH is an 1532 appropriate choice for cases where the nodes share an appropriate 1533 security association that enables the use of AH. 1535 In particular, RREP messages SHOULD be authenticated to avoid 1536 creation of spurious routes to a desired destination. Otherwise, an 1537 attacker could masquerade as the desired destination, and maliciously 1538 deny service to the destination and/or maliciously inspect and 1539 consume traffic intended for delivery to the destination. RERR 1540 messages, while less dangerous, SHOULD be authenticated in order to 1541 prevent malicious nodes from disrupting valid routes between nodes 1542 that are communication partners. 1544 AODV does not make any assumption about the method by which addresses 1545 are assigned to the mobile nodes, except that they are presumed to 1546 have unique IP addresses. Therefore, no special consideration, other 1547 than what is natural because of the general protocol specifications, 1548 can be made about the applicability of IPsec authentication headers 1549 or key exchange mechanisms. However, if the mobile nodes in the 1550 ad hoc network have pre-established security associations, it is 1551 presumed that the purposes for which the security associations are 1552 created include that of authorizing the processing of AODV control 1553 messages. Given this understanding, the mobile nodes should be able 1554 to use the same authentication mechanisms based on their IP addresses 1555 as they would have used otherwise. 1557 12. IANA Considerations 1559 AODV defines a "Type" field for messages sent to port 654. A new 1560 registry is to be created for the values for this Type field, and the 1561 following values assigned: 1563 Message Type Value 1564 --------------------------- ----- 1565 Route Request (RREQ) 1 1566 Route Reply (RREP) 2 1567 Route Error (RERR) 3 1568 Route-Reply Ack (RREP-ACK) 4 1570 AODV control messages can have extensions. Currently, only one 1571 extension is defined. A new registry is to be created for the Type 1572 field of the extensions: 1574 Extension Type Value 1575 --------------------------- ----- 1576 Hello Interval 1 1578 Future values of the Message Type or Extension Type can be allocated 1579 using standards action [2]. 1581 13. IPv6 Considerations 1583 See [6] for detailed operation for IPv6. The only changes to the 1584 protocol are that the address fields are enlarged. 1586 14. Acknowledgments 1588 Special thanks to Ian Chakeres, UCSB, for his extensive suggestions 1589 and contributions to recent revisions. 1591 We acknowledge with gratitude the work done at University of 1592 Pennsylvania within Carl Gunter's group, as well as at Stanford and 1593 CMU, to determine some conditions (especially involving reboots and 1594 lost RERRs) under which previous versions of AODV could suffer from 1595 routing loops. Contributors to those efforts include Karthikeyan 1596 Bhargavan, Joshua Broch, Dave Maltz, Madanlal Musuvathi, and 1597 Davor Obradovic. The idea of a DELETE_PERIOD, for which expired 1598 routes (and, in particular, the sequence numbers) to a particular 1599 destination must be maintained, was also suggested by them. 1601 We also acknowledge the comments and improvements suggested by 1602 Sung-Ju Lee (especially regarding local repair), Mahesh Marina, Erik 1603 Nordstrom (who provided text for section 6.11), Yves Prelot, Marc 1604 Mosko, Manel Guerrero Zapata, Philippe Jacquet, and Fred Baker. 1606 References 1608 [1] S. Bradner. Key words for use in RFCs to Indicate Requirement 1609 Levels. Request for Comments (Best Current Practice) 2119, 1610 Internet Engineering Task Force, March 1997. 1612 [2] T. Narten and H. Alvestrand. Guidelines for Writing an IANA 1613 Considerations Section in RFCs. Request for Comments (Best 1614 Current Practice) 2434, Internet Engineering Task Force, October 1615 1998. 1617 [3] J. Manner et al. Mobility Related Terminology (work in 1618 progress). draft-manner-seamoby-terms-02.txt, July 2001. 1620 [4] Karthikeyan Bhargavan, Carl A. Gunter, and Davor Obradovic. 1621 Fault Origin Adjudication. In Proceedings of the Workshop on 1622 Formal Methods in Software Practice, Portland, OR, August 2000. 1624 [5] IEEE 802.11 Committee, AlphaGraphics #35, 10201 N.35th Avenue, 1625 Phoenix AZ 85051. Wireless LAN Medium Access Control MAC and 1626 Physical Layer PHY Specifications, June 1997. IEEE Standard 1627 802.11-97. 1629 [6] C. Perkins, E. Royer, and S. Das. Ad hoc on demand distance 1630 vector (AODV) routing for ip version 6 (work in progress). 1631 Internet Draft, Internet Engineering Task Force, November 2001. 1633 References [1] and [2] are normative; all others are informative. 1635 A. Draft Modifications 1637 The following are major changes between this version (13) of the AODV 1638 draft and previous versions: 1640 - RERR clarifications for handling subnet routes. A processing 1641 step was added to eliminate host routes that are redundant with 1642 subnet routes. 1644 - Added explicit specification to clarify that subnet routes are 1645 handled the same way as host routes for managing timeouts and 1646 route table entries. 1648 - Applicability Statement and IANA Considerations sections added. 1650 - Normative References placed at beginning of bibliography. 1652 - Updated Security Considerations section. AH is suggested but not 1653 mandated as a good choice for authenticating control messages. 1655 - Updated the AODV and Aggregated Networks section to include the 1656 transmission of an ICMP Host Unreachable message for data packets 1657 sent to non-existent destinations. 1659 Author's Addresses 1661 Questions about this memo can be directed to: 1663 Charles E. Perkins 1664 Communications Systems Laboratory 1665 Nokia Research Center 1666 313 Fairchild Drive 1667 Mountain View, CA 94303 1668 USA 1669 +1 650 625 2986 1670 +1 650 691 2170 (fax) 1671 charliep@iprg.nokia.com 1673 Elizabeth M. Belding-Royer 1674 Department of Computer Science 1675 University of California, Santa Barbara 1676 Santa Barbara, CA 93106 1677 +1 805 893 3411 1678 +1 805 893 8553 (fax) 1679 ebelding@cs.ucsb.edu 1680 Samir R. Das 1681 Department of Electrical and Computer Engineering 1682 & Computer Science 1683 University of Cincinnati 1684 Cincinnati, OH 45221-0030 1685 +1 513 556 2594 1686 +1 513 556 7326 (fax) 1687 sdas@ececs.uc.edu