idnits 2.17.1 draft-ietf-manet-aodvv2-12.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 11 instances of too long lines in the document, the longest one being 4 characters in excess of 72. == There are 7 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 13, 2015) is 3116 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'Address' is mentioned on line 402, but not defined == Missing Reference: 'MetricType' is mentioned on line 2908, but not defined == Missing Reference: 'OrigAddr' is mentioned on line 4078, but not defined == Missing Reference: 'TargAddr' is mentioned on line 2073, but not defined == Missing Reference: 'TBD' is mentioned on line 2980, but not defined == Missing Reference: 'HopCount' is mentioned on line 3414, but not defined -- Looks like a reference, but probably isn't: '0' on line 4302 == Unused Reference: 'RFC4291' is defined on line 3208, but no explicit reference was found in the text == Unused Reference: 'RFC5082' is defined on line 3212, but no explicit reference was found in the text == Unused Reference: 'Perkins99' is defined on line 3256, but no explicit reference was found in the text == Unused Reference: 'RFC4861' is defined on line 3277, but no explicit reference was found in the text == Unused Reference: 'Sholander02' is defined on line 3296, but no explicit reference was found in the text ** Downref: Normative reference to an Experimental RFC: RFC 3561 Summary: 2 errors (**), 0 flaws (~~), 13 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networks Working Group C. Perkins 3 Internet-Draft Futurewei 4 Intended status: Standards Track S. Ratliff 5 Expires: April 15, 2016 Idirect 6 J. Dowdell 7 Airbus Defence and Space 8 L. Steenbrink 9 HAW Hamburg, Dept. Informatik 10 V. Mercieca 11 Airbus Defence and Space 12 October 13, 2015 14 Ad Hoc On-demand Distance Vector Routing Version 2 (AODVv2) 15 draft-ietf-manet-aodvv2-12 17 Abstract 19 The Ad Hoc On-demand Distance Vector Version 2 (AODVv2) routing 20 protocol is intended for use by mobile routers in wireless, multihop 21 networks. AODVv2 determines unicast routes among AODVv2 routers 22 within the network in an on-demand fashion, offering rapid 23 convergence in dynamic topologies. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on April 15, 2016. 42 Copyright Notice 44 Copyright (c) 2015 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 4 60 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 61 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 62 4. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 10 63 4.1. Interface List . . . . . . . . . . . . . . . . . . . . . 10 64 4.2. Router Client Table . . . . . . . . . . . . . . . . . . . 10 65 4.3. Neighbor Table . . . . . . . . . . . . . . . . . . . . . 11 66 4.4. Sequence Numbers . . . . . . . . . . . . . . . . . . . . 12 67 4.5. Multicast Route Message Table . . . . . . . . . . . . . . 13 68 4.6. Route Table . . . . . . . . . . . . . . . . . . . . . . . 14 69 5. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 70 6. AODVv2 Protocol Operations . . . . . . . . . . . . . . . . . 17 71 6.1. Initialization . . . . . . . . . . . . . . . . . . . . . 17 72 6.2. Adjacency Monitoring . . . . . . . . . . . . . . . . . . 18 73 6.3. Neighbor Table Update . . . . . . . . . . . . . . . . . . 19 74 6.4. Interaction with Forwarding Plane . . . . . . . . . . . . 20 75 6.5. Message Transmission . . . . . . . . . . . . . . . . . . 21 76 6.6. Route Discovery, Retries and Buffering . . . . . . . . . 23 77 6.7. Processing Received Route Information . . . . . . . . . . 24 78 6.7.1. Evaluating Route Information . . . . . . . . . . . . 25 79 6.7.2. Applying Route Updates . . . . . . . . . . . . . . . 27 80 6.8. Suppressing Redundant Messages Using the Multicast Route 81 Message Table . . . . . . . . . . . . . . . . . . . . . . 28 82 6.9. Route Maintenance . . . . . . . . . . . . . . . . . . . . 31 83 6.9.1. Route State . . . . . . . . . . . . . . . . . . . . . 31 84 6.9.2. Reporting Invalid Routes . . . . . . . . . . . . . . 33 85 7. AODVv2 Protocol Messages . . . . . . . . . . . . . . . . . . 34 86 7.1. Route Request (RREQ) Message . . . . . . . . . . . . . . 34 87 7.1.1. RREQ Generation . . . . . . . . . . . . . . . . . . . 35 88 7.1.2. RREQ Reception . . . . . . . . . . . . . . . . . . . 36 89 7.1.3. RREQ Regeneration . . . . . . . . . . . . . . . . . . 38 90 7.2. Route Reply (RREP) Message . . . . . . . . . . . . . . . 39 91 7.2.1. RREP Generation . . . . . . . . . . . . . . . . . . . 40 92 7.2.2. RREP Reception . . . . . . . . . . . . . . . . . . . 42 93 7.2.3. RREP Regeneration . . . . . . . . . . . . . . . . . . 43 94 7.3. Route Reply Acknowledgement (RREP_Ack) Message . . . . . 44 95 7.3.1. RREP_Ack Generation . . . . . . . . . . . . . . . . . 45 96 7.3.2. RREP_Ack Reception . . . . . . . . . . . . . . . . . 45 98 7.4. Route Error (RERR) Message . . . . . . . . . . . . . . . 45 99 7.4.1. RERR Generation . . . . . . . . . . . . . . . . . . . 46 100 7.4.2. RERR Reception . . . . . . . . . . . . . . . . . . . 48 101 7.4.3. RERR Regeneration . . . . . . . . . . . . . . . . . . 49 102 8. RFC 5444 Representation . . . . . . . . . . . . . . . . . . . 50 103 8.1. Route Request Message Representation . . . . . . . . . . 52 104 8.1.1. Message Header . . . . . . . . . . . . . . . . . . . 52 105 8.1.2. Message TLV Block . . . . . . . . . . . . . . . . . . 52 106 8.1.3. Address Block . . . . . . . . . . . . . . . . . . . . 52 107 8.1.4. Address Block TLV Block . . . . . . . . . . . . . . . 52 108 8.2. Route Reply Message Representation . . . . . . . . . . . 53 109 8.2.1. Message Header . . . . . . . . . . . . . . . . . . . 53 110 8.2.2. Message TLV Block . . . . . . . . . . . . . . . . . . 54 111 8.2.3. Address Block . . . . . . . . . . . . . . . . . . . . 54 112 8.2.4. Address Block TLV Block . . . . . . . . . . . . . . . 54 113 8.3. Route Reply Acknowledgement Message Representation . . . 55 114 8.3.1. Message Header . . . . . . . . . . . . . . . . . . . 55 115 8.3.2. Message TLV Block . . . . . . . . . . . . . . . . . . 55 116 8.3.3. Address Block . . . . . . . . . . . . . . . . . . . . 55 117 8.3.4. Address Block TLV Block . . . . . . . . . . . . . . . 55 118 8.4. Route Error Message Representation . . . . . . . . . . . 56 119 8.4.1. Message Header . . . . . . . . . . . . . . . . . . . 56 120 8.4.2. Message TLV Block . . . . . . . . . . . . . . . . . . 56 121 8.4.3. Address Block . . . . . . . . . . . . . . . . . . . . 56 122 8.4.4. Address Block TLV Block . . . . . . . . . . . . . . . 56 123 9. Simple External Network Attachment . . . . . . . . . . . . . 57 124 10. Optional Features . . . . . . . . . . . . . . . . . . . . . . 58 125 10.1. Expanding Rings Multicast . . . . . . . . . . . . . . . 59 126 10.2. Precursor Lists . . . . . . . . . . . . . . . . . . . . 59 127 10.3. Intermediate RREP . . . . . . . . . . . . . . . . . . . 60 128 10.4. Message Aggregation Delay . . . . . . . . . . . . . . . 60 129 11. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 60 130 11.1. Timers . . . . . . . . . . . . . . . . . . . . . . . . . 61 131 11.2. Protocol Constants . . . . . . . . . . . . . . . . . . . 62 132 11.3. Local Settings . . . . . . . . . . . . . . . . . . . . . 63 133 11.4. Network-Wide Settings . . . . . . . . . . . . . . . . . 63 134 11.5. Optional Feature Settings . . . . . . . . . . . . . . . 63 135 11.6. MetricType Allocation . . . . . . . . . . . . . . . . . 64 136 11.7. AddressType Allocation . . . . . . . . . . . . . . . . . 64 137 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 65 138 12.1. RFC 5444 Message Types . . . . . . . . . . . . . . . . . 65 139 12.2. RFC 5444 Address Block TLV Types . . . . . . . . . . . . 65 140 13. Security Considerations . . . . . . . . . . . . . . . . . . . 65 141 14. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 68 142 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 69 143 15.1. Normative References . . . . . . . . . . . . . . . . . . 69 144 15.2. Informative References . . . . . . . . . . . . . . . . . 70 145 Appendix A. Multi-homing Considerations . . . . . . . . . . . . 71 146 Appendix B. Router Client Relocation . . . . . . . . . . . . . . 71 147 Appendix C. Example Algorithms for AODVv2 Operations . . . . . . 72 148 C.1. HopCount MetricType . . . . . . . . . . . . . . . . . . . 73 149 C.2. General Operations . . . . . . . . . . . . . . . . . . . 74 150 C.2.1. Route Operations . . . . . . . . . . . . . . . . . . 74 151 C.2.2. LoopFree . . . . . . . . . . . . . . . . . . . . . . 77 152 C.2.3. Multicast Route Message Table Operations . . . . . . 78 153 C.3. Message Algorithms . . . . . . . . . . . . . . . . . . . 79 154 C.3.1. Build_RFC_5444_Message_Header . . . . . . . . . . . . 80 155 C.3.2. RREQ Operations . . . . . . . . . . . . . . . . . . . 80 156 C.3.3. RREP Operations . . . . . . . . . . . . . . . . . . . 84 157 C.3.4. RREP_Ack Operations . . . . . . . . . . . . . . . . . 88 158 C.3.5. RERR Operations . . . . . . . . . . . . . . . . . . . 88 159 Appendix D. AODVv2 Draft Updates . . . . . . . . . . . . . . . . 93 160 D.1. Changes between revisions 11 and 12 . . . . . . . . . . . 93 161 D.2. Changes between revisions 10 and 11 . . . . . . . . . . . 94 162 D.3. Changes between revisions 9 and 10 . . . . . . . . . . . 95 163 D.4. Changes between revisions 8 and 9 . . . . . . . . . . . . 95 164 D.5. Changes between revisions 7 and 8 . . . . . . . . . . . . 98 165 D.6. Changes between revisions 6 and 7 . . . . . . . . . . . . 99 166 D.7. Changes between revisions 5 and 6 . . . . . . . . . . . . 100 167 D.8. Changes between revisions 4 and 5 . . . . . . . . . . . . 101 168 D.9. Changes between revisions 3 and 4 . . . . . . . . . . . . 102 169 D.10. Changes between revisions 2 and 3 . . . . . . . . . . . . 103 170 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 104 172 1. Overview 174 The Ad Hoc On-demand Distance Vector Version 2 (AODVv2) routing 175 protocol (formerly named DYMO) enables on-demand, multihop unicast 176 routing among AODVv2 routers in mobile ad hoc networks (MANETs) 177 [RFC2501]. 179 Compared to AODV [RFC3561], AODVv2 makes some features optional, 180 notably intermediate route replies, expanding ring search, and 181 precursor lists. Hello messages and local repair have been removed. 182 Message formats have been updated and made compliant with [RFC5444]. 183 AODVv2 also provides a mechanism for the use of multiple metric 184 types. 186 The basic operations of the AODVv2 protocol are route discovery and 187 route maintenance. 189 Route discovery is performed when an AODVv2 router needs to forward 190 an IP packet for one of its clients, but does not have a valid route 191 to the packet's destination. AODVv2 routers use Route Request (RREQ) 192 and Route Reply (RREP) messages to carry route information between 193 the originator of the route discovery and the target, establishing a 194 route to both endpoints on all intermediate routers. A metric value 195 is included to represent the cost of the route contained within the 196 message. 198 AODVv2 uses sequence numbers to identify stale routing information, 199 and compares route metric values to determine if advertised routes 200 could form loops. 202 Route maintenance involves monitoring the router's links and routes 203 for changes. This includes confirming bidirectionality of links to 204 other AODVv2 routers, issuing Route Error messages if link failures 205 invalidate routes, extending and enforcing route timeouts, and 206 reacting to received Route Error messages. 208 AODVv2 control plane messages use the Generalized MANET Packet/ 209 Message Format defined in [RFC5444] and the parameters in [RFC5498]. 210 AODVv2 defines a set of Data Elements which map to [RFC5444] Address 211 Blocks, Address Block TLVs, and Message TLVs. 213 Security for authentication of AODVv2 routers and encryption of 214 control messages is accomplished using the TIMESTAMP and ICV TLVs 215 defined in [RFC7182]. 217 2. Terminology 219 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 220 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 221 "OPTIONAL" in this document are to be interpreted as described in 222 [RFC2119]. In addition, this document uses terminology from 223 [RFC5444], and defines the following terms: 225 AddressList 226 An AODVv2 Data Element containing a list of IP addresses. 228 Adjacency 229 A bi-directional link between neighboring AODVv2 routers for the 230 purpose of routing information. 232 AckReq 233 An AODVv2 Data Element used in a Route Reply message to request 234 that the Route Reply message is acknowledged by returning a Route 235 Reply Ack message. This Data Element contains the address of the 236 AODVv2 router that should acknowledge the Route Reply message. 238 AdvRte 239 A route advertised in an incoming route message. 241 AODVv2 Router 242 An IP addressable device in the ad hoc network that performs the 243 AODVv2 protocol operations specified in this document. 245 CurrentTime 246 The current time as maintained by the AODVv2 router. 248 Data Element 249 A named field used within AODVv2 protocol messages. 251 ENAR (External Network Access Router) 252 An AODVv2 router with an interface to an external, non-AODVv2 253 network. 255 Invalid route 256 A route that cannot be used for forwarding. 258 MANET 259 A Mobile Ad Hoc Network as defined in [RFC2501]. 261 MetricType 262 An AODVv2 Data Element indicating the metric type for a metric 263 value included in a message. 265 MetricTypeList 266 An AODVv2 Data Element used in a Route Error message, containing a 267 list of metric types associated with the addresses in the 268 AddressList of the message. 270 Neighbor 271 An AODVv2 router from which an AODVv2 message has been received. 272 Neighbors exchange routing information and attempt to verify 273 bidirectionality of the link to a neighbor before installing a 274 route via that neighbor. 276 Node 277 An IP addressable device in the ad hoc network. All nodes in this 278 document are either AODVv2 Routers or Router Clients. 280 OrigAddr (Originator Address) 281 An AODVv2 Data Element containing the source IP address of the IP 282 packet triggering route discovery. 284 OrigMetric 285 An AODVv2 Data Element containing the metric value associated with 286 the route to the OrigAddr in a message. 288 OrigPrefixLen 289 The prefix length, in bits, associated with OrigAddr. 291 OrigSeqNum 292 An AODVv2 Data Element used in a Route Request message, containing 293 the sequence number of the AODVv2 router which originated the 294 Route Request. 296 PktSource 297 An AODVv2 Data Element used in a Route Error message, containing 298 the source address of the IP packet which triggered the Route 299 Error message. 301 PrefixLengthList 302 An AODVv2 Data Element containing a list of routing prefix lengths 303 associated with the addresses in the AddressList of the message. 305 Reactive 306 A protocol operation is called "reactive" if it is performed only 307 in reaction to specific events. In this document, "reactive" is 308 synonymous with "on-demand". 310 RERR (Route Error) 311 The AODVv2 message type used to indicate that an AODVv2 router 312 does not have a route toward one or more particular destinations. 314 RERR_Gen (RERR Generating Router) 315 The AODVv2 router generating a Route Error message. 317 Routable Unicast IP Address 318 A routable unicast IP address is a unicast IP address that is 319 scoped sufficiently to be forwarded by a router. Globally-scoped 320 unicast IP addresses and Unique Local Addresses (ULAs) [RFC4193] 321 are examples of routable unicast IP addresses. 323 Router Client 324 An address or address range configured on an AODVv2 router, 325 corresponding to one or more nodes which require that router to 326 initiate and respond to route discoveries on their behalf, so that 327 they can send and receive IP traffic to and from remote 328 destinations. The AODVv2 router's interface addresses are also 329 configured as Router Clients. 331 RREP (Route Reply) 332 The AODVv2 message type used to reply to a Route Request message. 334 RREP_Gen (RREP Generating Router) 335 The AODVv2 router configured with TargAddr as a Router Client, 336 i.e., the router that creates the Route Reply message. 338 RREQ (Route Request) 339 The AODVv2 message type used to discover a route to the Target 340 Address and distribute information about the route to the 341 Originator Address. 343 RREQ_Gen (RREQ Generating Router) 344 The AODVv2 router that creates the Route Request message on behalf 345 of a Router Client. 347 RteMsg (Route Message) 348 A Route Request (RREQ) or Route Reply (RREP) message. 350 Sequence Number (SeqNum) 351 An AODVv2 Data Element containing the sequence number maintained 352 by an AODVv2 router to indicate freshness of route information. 354 SeqNumList 355 An AODVv2 Data Element containing a list of sequence numbers 356 associated with the addresses in the AddressList of a message. 358 TargAddr (Target Address) 359 An AODVv2 Data Element containing the destination address of the 360 IP packet triggering route discovery. 362 TargMetric 363 An AODVv2 Data Element containing the metric value associated with 364 the route to the TargAddr in a message. 366 TargPrefixLen 367 The prefix length, in bits, associated with TargAddr. 369 TargSeqNum 370 An AODVv2 Data Element used in a Route Reply message, containing 371 the sequence number of the AODVv2 router which originated the 372 Route Reply. 374 Valid route 375 A route that can be used for forwarding. 377 Unreachable Address 378 An address reported in an RERR message, either the destination 379 address of an IP packet that could not be forwarded because a 380 valid route to the destination is not known, or the address on a 381 route which became Invalid. 383 Upstream 384 In the direction from destination to source (from TargAddr to 385 OrigAddr). 387 ValidityTime 388 An AODVv2 Data Element containing the length of time the route 389 described by the message is offered. 391 The AODVv2 Data Elements are used to create AODVv2 messages. Their 392 contents are transferred into [RFC5444] formatted messages (see 393 Section 8) before sending. 395 This document uses the notational conventions in Table 1 to simplify 396 the text. 398 +-----------------------+------------------------------------+ 399 | Notation | Meaning | 400 +-----------------------+------------------------------------+ 401 | Route[Address] | A route toward Address | 402 | Route[Address].Field | A field in a route toward Address | 403 | RteMsg.Field | A field in either RREQ or RREP | 404 +-----------------------+------------------------------------+ 406 Table 1: Notational Conventions 408 3. Applicability Statement 410 The AODVv2 routing protocol is a reactive routing protocol. Certain 411 interactions with the forwarding plane are required, and these are 412 discussed in Section 6.4. 414 AODVv2 is designed for stub or disconnected mobile ad hoc networks, 415 i.e., non-transit networks or those not connected to the internet. 416 AODVv2 can, however, be configured to perform gateway functions when 417 attached to external networks, as discussed in Section 9. 419 AODVv2 handles a wide variety of mobility and traffic patterns by 420 determining routes on-demand. In networks with a large number of 421 routers, AODVv2 is best suited for relatively sparse traffic 422 scenarios where each router forwards IP packets to a small percentage 423 of other AODVv2 routers in the network. In this case fewer routes 424 are needed, and therefore less control traffic is produced. 426 Providing security for a reactive routing protocol can be difficult. 427 AODVv2 provides for message integrity and security against replay 428 attacks by using integrity check values, timestamps and sequence 429 numbers, as described in Section 13. If security associations can be 430 established, encryption can be used for AODVv2 messages to ensure 431 that only trusted routers participate in routing operations. 433 Since the route discovery process typically results in a route being 434 established in both directions along the same path, uni-directional 435 links are not suitable. AODVv2 will detect and exclude those links 436 from route discovery. The route discovered is optimised for the 437 requesting router, and the return path may not be the optimal route. 439 AODVv2 is applicable to memory constrained devices, since only a 440 little routing state is maintained in each AODVv2 router. In 441 contrast to proactive routing protocols, which maintain routing 442 information for all destinations within the MANET, AODVv2 routes that 443 are not needed for forwarding data do not need to be maintained. On 444 routers unable to store persistent AODVv2 state, recovery can impose 445 a performance penalty (e.g., in case of AODVv2 router reboot), since 446 if a router loses its sequence number, there is a delay before the 447 router can resume full operations. This is described in Section 6.1. 449 AODVv2 supports routers with multiple interfaces, as long as each 450 interface configured for AODVv2 has a unicast IP address. A router 451 may use the same IP address on multiple interfaces. Address 452 assignment procedures are out of scope for AODVv2. 454 AODVv2 supports hosts with multiple interfaces, as long as each 455 interface is configured with its own unicast IP address. Multi- 456 homing of an IP address is not supported by AODVv2, and therefore a 457 Router Client, i.e. an IP Address, SHOULD NOT be served by more than 458 one AODVv2 router at any one time. Appendix A contains some notes on 459 this topic. 461 Although AODVv2 is closely related to AODV [RFC3561], and shares some 462 features of DSR [RFC4728], AODVv2 is not interoperable with either of 463 those protocols. 465 The routing algorithm in AODVv2 MAY be operated at layers other than 466 the network layer, using layer-appropriate addresses. 468 4. Data Structures 470 4.1. Interface List 472 If multiple interfaces of the AODVv2 router are configured for use by 473 AODVv2, a list of the interfaces SHOULD be configured in the 474 AODVv2_INTERFACES list. 476 4.2. Router Client Table 478 An AODVv2 router MUST provide route discovery services for its own 479 local applications and for other non-routing nodes that are reachable 480 without traversing another AODVv2 router. These nodes, and the 481 AODVv2 router itself, are referred to as Router Clients. An AODVv2 482 router will only originate Route Request and Route Reply messages on 483 behalf of configured Router Clients. 485 Router Client Table entries MUST contain: 487 RouterClient.IPAddress 488 An IP address or the start of an address range that requires route 489 discovery services from the AODVv2 router. 491 RouterClient.PrefixLength 492 The length, in bits, of the routing prefix associated with the 493 RouterClient.IPAddress. If a prefix length is included, the 494 AODVv2 router MUST provide connectivity for all addresses within 495 that prefix. 497 RouterClient.Cost 498 The cost associated with reaching this Router Client. This cost 499 will also appear as the metric in a route table entry for the 500 Router Client address. 502 The Router Client Table for an AODVv2 router is never empty, since an 503 AODVv2 router is always its own client. The IP Addresses of the 504 router's interfaces will appear in the Router Client Table. 506 In the initial state, an AODVv2 router is not required to have 507 information about the Router Clients of any other AODVv2 router. 509 A Router Client address MUST NOT be served by more than one AODVv2 510 router at any one time, i.e. a Router Client of one AODVv2 router 511 MUST NOT be configured as a Router Client on another AODVv2 router 512 using the same Router Client IP address. Shifting responsibility for 513 a Router Client to a different AODVv2 router is discussed in 514 Appendix B. 516 4.3. Neighbor Table 518 A neighbor table MUST be maintained with information about 519 neighboring AODVv2 routers which are used in discovered routes. 521 Neighbor Table entries MUST contain: 523 Neighbor.IPAddress 524 An IP address of the neighboring router, learned from the source 525 IP address of a received route message. 527 Neighbor.State 528 The state of the adjacency with the neighbor (Confirmed, Unknown, 529 or Blacklisted). The Unknown state is the initial state. The 530 Confirmed state indicates that the link to the neighbor has been 531 confirmed as bidirectional. The Blacklisted state indicates that 532 the link to the neighbor is uni-directional. Section 6.2 533 discusses how to monitor adjacency. 535 Neighbor.ResetTime 536 When the State is Blacklisted, this time indicates the point at 537 which the State reverts to Unknown. By default this value is 538 calculated at the time the router is blacklisted and is equal to 539 CurrentTime + MAX_BLACKLIST_TIME. When the neighbor State is not 540 Blacklisted, this time is set to INFINITY_TIME. 542 4.4. Sequence Numbers 544 Sequence numbers enable AODVv2 routers to determine the temporal 545 order of route discovery messages, identifying stale routing 546 information so that it can be discarded. The sequence number 547 fulfills the same roles as the "Destination Sequence Number" of DSDV 548 [Perkins94], and the AODV Sequence Number in [RFC3561]. 550 Each AODVv2 router in the network MUST maintain its own sequence 551 number as a 16-bit unsigned integer. 553 All RREQ and RREP messages created by an AODVv2 router include the 554 router's sequence number. Each AODVv2 router MUST ensure that its 555 sequence number is strictly increasing. It is incremented by one (1) 556 whenever an RREQ or RREP is created, except when the sequence number 557 is 65,535 (the maximum value of a 16-bit unsigned integer), in which 558 case it MUST be reset to one (1). The value zero (0) is reserved to 559 indicate that the sequence number for an address is unknown. 561 An AODVv2 router can only attach its own sequence number to 562 information about a route to one of its configured router clients. 563 All route messages regenerated by other routers retain the 564 originator's sequence number. Therefore, when two pieces of 565 information about a route are received, they both contain a sequence 566 number from the originating router. Comparing the sequence number 567 will identify which information is stale. The currently stored 568 sequence number is subtracted from the incoming sequence number. The 569 result of the subtraction is to be interpreted as a signed 16-bit 570 integer, and if less than zero, then the information in the AODVv2 571 message is stale and MUST be discarded. 573 As a consequence, loop freedom is assured. 575 An AODVv2 router SHOULD maintain its sequence number in persistent 576 storage. If the sequence number is lost, the router MUST follow the 577 procedure in Section 6.1 to safely resume routing operations with a 578 new sequence number. 580 4.5. Multicast Route Message Table 582 A route message (RteMsg) is either a Route Request or Route Reply 583 message. The Multicast Route Message Table is a conceptual table 584 which contains information about previously received multicast route 585 messages, so that when a route message is received, an AODVv2 router 586 can determine if the incoming information is redundant, and avoid 587 unnecessary regeneration of the route message. 589 A Multicast Route Message Table entry MUST contain the following 590 information: 592 RteMsg.MessageType 593 Either RREQ or RREP. 595 RteMsg.OrigAddr 596 An IP address of the node which requires the route, i.e., the 597 source address of the IP packet triggering the route request. 599 RteMsg.OrigPrefixLen 600 The prefix length associated with OrigAddr. 602 RteMsg.TargAddr 603 An IP address of the target, i.e., the destination address of the 604 IP packet triggering the route request. 606 RteMsg.TargPrefixLen 607 The prefix length associated with TargAddr. 609 RteMsg.OrigSeqNum 610 The sequence number associated with the originator, if present in 611 RteMsg. 613 RteMsg.TargSeqNum 614 The sequence number associated with the target, if present in 615 RteMsg. 617 RteMsg.MetricType 618 The metric type of the route requested. 620 RteMsg.Metric 621 The metric value received in the RteMsg. 623 RteMsg.Timestamp 624 The last time this entry was updated. 626 RteMsg.RemoveTime 627 The time at which this entry MUST be removed, MAX_SEQNUM_LIFETIME 628 after the last update of RteMsg.OrigSeqNum for an RREQ, or 629 RteMsg.TargSeqNum for an RREP. 631 The Multicast Route Message Table is maintained so that no two 632 entries have the same MessageType, OrigAddr, TargAddr, and 633 MetricType. See Section 6.8 for details on updating this table. 635 4.6. Route Table 637 All AODVv2 routers MUST maintain a route table. The route table 638 entry is a conceptual data structure. Implementations MAY use any 639 internal representation but MUST contain the following information: 641 Route.Address 642 An address, which, when combined with Route.PrefixLength, 643 describes the set of destination addresses this route includes. 645 Route.PrefixLength 646 The prefix length, in bits, associated with Route.Address. 648 Route.SeqNum 649 The sequence number associated with Route.Address, obtained from 650 the last route message that successfully updated this route. 652 Route.NextHop 653 The source IP address of the message advertising the route to 654 Route.Address, i.e. an IP address of the AODVv2 router used for 655 the next hop on the path toward Route.Address. 657 Route.NextHopInterface 658 The interface used to send IP packets toward Route.Address. 660 Route.LastUsed 661 The time this route was last used to forward an IP packet. 663 Route.LastSeqNumUpdate 664 The time the sequence number for this route was last updated. 666 Route.ExpirationTime 667 The time at which this route must be marked as Invalid. 669 Route.MetricType 670 The type of metric associated with this route. 672 Route.Metric 673 The cost of the route toward Route.Address expressed in units 674 consistent with Route.MetricType. 676 Route.State 677 The last known state (Active, Idle, Invalid, or Unconfirmed) of 678 the route. 680 Route.Precursors (optional feature) 681 A list of upstream neighbors using the route (see Section 10.2). 683 There are four possible states for an AODVv2 route: 685 Active 686 An Active route is in current use for forwarding IP packets. 688 Idle 689 An Idle route has not been used in the last ACTIVE_INTERVAL, but 690 can still be used for forwarding IP packets. 692 Invalid 693 An Invalid route cannot be used for forwarding IP packets. 694 Invalid routes have sequence number information, which allows 695 incoming information to be assessed for freshness. 697 Unconfirmed 698 An Unconfirmed route cannot be used for forwarding IP packets. It 699 is a route learned from a Route Request which has not yet been 700 confirmed as bidirectional. 702 Route state changes are detailed in Section 6.9.1. 704 An AODVv2 route MAY be offered for a limited time. In this case, the 705 route is referred to as a timed route. The length of time for which 706 the route is valid is referred to as validity time, and is included 707 in messages which advertise the route. The shortened validity time 708 is reflected in Route.ExpirationTime. If a route is not timed, the 709 ExpirationTime is INFINITY_TIME. 711 5. Metrics 713 Metrics measure a cost or quality associated with a route or a link, 714 e.g., latency, delay, financial cost, energy, etc. Metric values are 715 reported in route messages, where the goal is to determine a route 716 between OrigAddr and TargAddr. In Route Request messages, the metric 717 describes the cost of the route from OrigAddr (the router client) to 718 the router sending the Route Request. The receiving router 719 calculates the cost from OrigAddr to itself, combining the metric 720 value from the message with knowledge of the link cost from the 721 sender to the receiver, i.e., the incoming link cost. This updated 722 route cost is included when regenerating the Route Request message. 723 In Route Reply messages, the metric reflects the cost of the route 724 from TargAddr (the router client) to the router sending the Route 725 Reply. Routes to OrigAddr and TargAddr are installed at intermediate 726 routers for the purposes of forwarding a Route Reply message and 727 subsequent data traffic between OrigAddr and TargAddr. Assuming link 728 metrics are symmetric, the cost of the routes to OrigAddr and 729 TargAddr installed at each router will be correct. 731 AODVv2 enables the use of multiple metric types. Each route 732 discovery attempt indicates the metric type which is requested for 733 the route. Only one metric type may be used in each route discovery 734 attempt. However, routes to a single destination might be requested 735 for different metric types. The decision of which of these routes to 736 use for forwarding is outside the scope of AODVv2. 738 For each MetricType, AODVv2 requires: 740 o A MetricType number, to indicate the metric type of a route. 741 MetricType numbers allocated are detailed in Section 11.6. 743 o A maximum value, denoted MAX_METRIC[MetricType]. If the cost of a 744 route exceeds MAX_METRIC[MetricType], the route is ignored. 745 AODVv2 cannot store routes that cost more than 746 MAX_METRIC[MetricType]. 748 o A function for incoming link cost, denoted Cost(L). Using 749 incoming link costs means that the route learned has a path 750 optimized for the direction from OrigAddr to TargAddr. 752 o A function for route cost, denoted Cost(R). 754 o A function to analyze routes for potential loops, denoted 755 LoopFree(R1, R2). LoopFree verifies that a route R2 is not a sub- 756 section of another route R1. An AODVv2 router invokes LoopFree() 757 as part of the process in Section 6.7.1, when an advertised route 758 (R1) and an existing route (R2) have the same destination address, 759 metric type, and sequence number. LoopFree returns FALSE to 760 indicate that an advertised route is not to be used to update a 761 stored route, if it may cause a routing loop. In the case where 762 the existing route is Invalid, it is possible that the advertised 763 route includes the existing route and came from a router which did 764 not yet receive notification of the route becoming Invalid, so the 765 advertised route should not be used in case it forms a loop to a 766 broken route. 768 AODVv2 currently supports cost metrics where Cost(R) is strictly 769 increasing, by defining: 771 o Cost(R) := Sum of Cost(L) of each link in the route 773 o LoopFree(R1, R2) := ( Cost(R1) <= Cost(R2) ) 775 Implementers MAY consider other metric types, but the definitions of 776 Cost and LoopFree functions for such types are undefined, and 777 interoperability issues need to be considered. 779 6. AODVv2 Protocol Operations 781 The AODVv2 protocol's operations include managing sequence numbers, 782 monitoring adjacent AODVv2 routers, performing route discovery and 783 dealing with requests from other routers, processing incoming route 784 information and updating the route table, suppressing redundant 785 messages, maintaining the route table and reporting broken routes. 786 These processes are discussed in detail in the following sections. 788 6.1. Initialization 790 During initialization where an AODVv2 router does not have 791 information about its previous sequence number, or if its sequence 792 number is lost at any point, the router resets its sequence number to 793 one (1). However, other AODVv2 routers may still hold sequence 794 number information that this router previously issued. Since 795 sequence number information is removed if there has been no update to 796 the sequence number in MAX_SEQNUM_LIFETIME, the initializing router 797 must wait for MAX_SEQNUM_LIFETIME before it creates any messages 798 containing its new sequence number. It can then be sure that the 799 information it sends will not be considered stale. 801 Until MAX_SEQNUM_LIFETIME after its sequence number is reset, the 802 router SHOULD NOT create RREQ or RREP messages. 804 During this wait period, the router can do the following: 806 o Process information in a received RREQ or RREP message to learn a 807 route to the originator or target of that route discovery 809 o Regenerate a received RREQ or RREP 811 o Send an RREP_Ack 813 o Maintain valid routes in order that the forwarding process can 814 forward IP packets to Router Clients and to other routers 816 o Create, process and regenerate RERR messages 818 6.2. Adjacency Monitoring 820 AODVv2 routers MUST NOT establish routes over uni-directional links. 821 Consider the following. An RREQ is forwarded toward TargAddr, and 822 intermediate routers install a route to OrigAddr. If, at one of 823 those routers, the link to the next hop toward OrigAddr was uni- 824 directional, and this route was used to forward data traffic, the 825 data packets would be lost. Further, an RREP sent toward OrigAddr 826 using this link will not reach the next hop, and will therefore not 827 be regenerated, and will never reach RREQ_Gen, so end-to-end route 828 establishment will fail. AODVv2 routers MUST verify that the link to 829 the next hop is bidirectional when establishing a route, and before 830 allowing data traffic to be forwarded on that route. If 831 bidirectionality cannot be verified, this link MUST be excluded from 832 the route discovery procedure. 834 AODVv2 refers to a bidirectional link with a neighboring router as an 835 adjacency. AODVv2 routers do not need to monitor adjacency to all 836 neighboring AODVv2 routers at all times, but MUST determine if there 837 is an adjacency to the chosen next-hop AODVv2 router during route 838 discovery. 840 o For the next hop toward OrigAddr, the approach for testing 841 bidirectional connectivity is to request acknowledgement of Route 842 Reply messages. Receipt of an acknowledgement proves that 843 bidirectional connectivity exists. All AODVv2 routers MUST 844 support this process, which is explained in Section 7.2 and 845 Section 7.3. If a link to a neighbor is determined to be 846 unidirectional because a requested acknowledgement is not received 847 within RREP_Ack_SENT_TIMEOUT, the neighbor MUST be marked as 848 blacklisted (see below). 850 o For the next hop toward TargAddr, receipt of the Route Reply 851 message containing the route to TargAddr is confirmation of 852 bidirectionality, since a Route Reply message is a reply to a 853 Route Request message which previously crossed the link in the 854 opposite direction. 856 To assist with adjacency monitoring, a Neighbor Table (Section 4.3) 857 is maintained. Each entry contains a neighbor IP address and an 858 indication of the state of the adjacency with that neighbor (Unknown, 859 Blacklisted, or Confirmed). When an RREQ or RREP is received from an 860 IP address which does not already have an entry in the Neighbor 861 Table, a new entry is created as described in Section 6.3. While 862 neighbor state is Unknown, acknowledgement of RREP messages MUST be 863 requested. While neighbor state is Confirmed, the request for an 864 acknowledgement is unnecessary. 866 When routers perform other operations such as those from the list 867 below, these MAY be used as additional indications of connectivity: 869 o NHDP HELLO Messages [RFC6130] 871 o Route timeout 873 o Lower layer triggers, e.g. message reception or link status 874 notifications 876 o TCP timeouts 878 o Promiscuous listening 880 o Other monitoring mechanisms or heuristics 882 If such an external process signals that the link is bidirectional, 883 the neighbor state MAY be set to Confirmed. If an external process 884 signals that a link is not bidirectional, the AODVv2 router MAY 885 update the matching Neighbor Table entry by changing the neighbor 886 state to Blacklisted. If an external process signals that the link 887 might not be bidirectional, and the neighbor state is currently 888 Confirmed, the state MAY be set to Unknown. 890 For example, receipt of a Neighborhood Discovery Protocol HELLO 891 message with the receiving router listed as a neighbor is a signal of 892 bidirectional connectivity. The AODVv2 router MAY update the 893 matching Neighbor Table entry by changing the neighbor state to 894 Confirmed. 896 Similarly, if AODVv2 receives notification of a timeout, for example, 897 from TCP or some other protocol, this may be due to a disconnection. 898 The AODVv2 router MAY update the matching Neighbor Table entry by 899 resetting the neighbor state to Unknown. 901 6.3. Neighbor Table Update 903 On receipt of an RREQ or RREP message, the neighbor table MUST be 904 checked for an entry with Neighbor.IPAddress which matches the source 905 IP address of the message. If no matching entry is found, a new 906 entry is created. 908 A new Neighbor Table entry is created as follows: 910 o Neighbor.IPAddress := Source IP address of the message 911 o Neighbor.State := Unknown 913 o Neighbor.ResetTime := INFINITY_TIME 915 When the link to the neighbor is determined to be bidirectional, the 916 Neighbor Table entry is updated as follows: 918 o Neighbor.State := Confirmed 920 When the link to the neighbor is determined to be uni-directional, 921 the Neighbor Table entry is updated as follows: 923 o Neighbor.State := Blacklisted 925 o Neighbor.ResetTime := CurrentTime + MAX_BLACKLIST_TIME 927 When the Neighbor.ResetTime is reached, the Neighbor Table entry is 928 updated as follows: 930 o Neighbor.State := Unknown 932 When a link to a neighbor is determined to be broken, the Neighbor 933 Table entry SHOULD be removed. 935 Route requests from neighbors with Neighbor.State set to Blacklisted 936 are ignored to avoid persistent IP packet loss or protocol failures. 937 However, the reset time allows the neighbor to again be allowed to 938 participate in route discoveries after MAX_BLACKLIST_TIME, in case 939 the link between the routers has become bidirectional. 941 6.4. Interaction with Forwarding Plane 943 A reactive protocol reacts when a route is needed. A route is 944 requested when an application tries to send a packet. The 945 fundamental concept of reactive routing is to avoid creating routes 946 that are not needed. 948 AODVv2 requires signals from the forwarding plane: 950 o A packet cannot be forwarded because a route is unavailable: 951 AODVv2 needs to know the source and destination IP addresses of 952 the packet, to determine whether it should initiate route 953 discovery, and include this information in a Route Request 954 message, or create a Route Error message. 956 o A packet is to be forwarded: AODVv2 needs to check the state of 957 the route to deal with timeouts. If the implementation uses 958 timers to enforce route timeouts, this signal is unnecessary. 960 o Packet forwarding failure occurs: AODVv2 needs to initiate route 961 error reports. 963 o Packet forwarding succeeds: AODVv2 needs to update the record of 964 when a route was last used to forward a packet. 966 AODVv2 needs to send signals to the forwarding plane: 968 o A route discovery is in progress: packets awaiting a route may be 969 buffered while route discovery is attempted. 971 o A route discovery was not attempted: any buffered packets 972 requiring that route should be discarded. 974 o A route discovery failed: any buffered packets requiring that 975 route should be discarded, and the source of the packet should be 976 notified that the destination is unreachable (using an ICMP 977 Destination Unreachable message). 979 o A route discovery succeeded: install a route which AODVv2 has 980 determined to be valid and begin transmitting any buffered 981 packets. 983 o A route has been lost: remove an installed route which AODVv2 has 984 determined to be invalid. 986 o A route has been updated: update an installed route when AODVv2 987 receives new information about the route. 989 These are conceptual signals, and can be implemented in various ways. 990 Conformant implementations of AODVv2 are not mandated to implement 991 the forwarding plane separately from the control plane or data plane; 992 these signals and interactions are identified simply as assistance 993 for implementers who may find them useful. 995 6.5. Message Transmission 997 AODVv2 sends [RFC5444] formatted messages using the parameters for 998 port number and IP protocol specified in [RFC5498]. Mapping of 999 AODVv2 Data Elements to [RFC5444] is detailed in Section 8. 1001 Messages may travel a maximum of MAX_HOPCOUNT hops. 1003 Unless otherwise specified, AODVv2 multicast messages are sent to the 1004 link-local multicast address LL-MANET-Routers [RFC5498]. All AODVv2 1005 routers MUST subscribe to LL-MANET-Routers [RFC5498] to receive 1006 AODVv2 messages. 1008 Note that multicast messages MAY be sent via unicast. For example, 1009 this may occur for certain link-types (non-broadcast media), for 1010 manually configured router adjacencies, or in order to improve 1011 robustness. 1013 Implementations MAY choose to employ techniques to reduce the number 1014 of multicast messages sent. Use of [RFC6621] in deployments is 1015 recommended. Employing [RFC6621] in a subset of the operational 1016 AODVv2 routers in a network, or configuring different algorithms on 1017 different routers, will not cause interoperability issues, but will 1018 reduce the effectiveness of the multicast reduction scheme. 1020 When multiple interfaces are available, an AODVv2 router transmitting 1021 a multicast message to LL-MANET-Routers MUST send the message on all 1022 interfaces that have been configured for AODVv2 operation, as given 1023 in the AODVv2_INTERFACES list (Section 4.1). Similarly, AODVv2 1024 routers MUST subscribe to LL-MANET-Routers on all their AODVv2 1025 interfaces. 1027 To avoid congestion, each AODVv2 router's rate of message generation 1028 SHOULD be limited (CONTROL_TRAFFIC_LIMIT) and administratively 1029 configurable. To prioritize transmission of AODVv2 control messages 1030 in order to respect the CONTROL_TRAFFIC_LIMIT: 1032 o Highest priority SHOULD be given to RREP_Ack messages. This 1033 allows learned routes to be confirmed as bidirectional and avoids 1034 undesirable blacklisting of next hop routers. 1036 o Second priority SHOULD be given to RERR messages for undeliverable 1037 IP packets, so that broken routes that are still being used are 1038 reported, and to avoid IP data packets being repeatedly forwarded 1039 to AODVv2 routers which cannot forward to their destination. 1041 o Third priority SHOULD be given to RREP messages in order that 1042 RREQs do not time out. 1044 o RREQ messages SHOULD be given priority over RERR messages for 1045 newly invalidated routes, since the invalidated routes may not 1046 still be in use, and if there is an attempt to use the route, a 1047 new RERR message will be generated. 1049 o Lowest priority SHOULD be given to RERR messages generated in 1050 response to RREP messages which cannot be regenerated. In this 1051 case the route request will be retried at a later point. 1053 6.6. Route Discovery, Retries and Buffering 1055 AODVv2's RREQ and RREP messages are used for route discovery. The 1056 main difference between the two messages is that, usually, RREQ 1057 messages are multicast to solicit an RREP, whereas RREP is unicast as 1058 a response to the RREQ. The constants used in this section are 1059 defined in Section 11. 1061 When an AODVv2 router needs to forward an IP packet (with source 1062 address OrigAddr and destination address TargAddr) from one of its 1063 Router Clients, it needs a route to the packet's destination. If no 1064 route exists, the AODVv2 router generates and multicasts a Route 1065 Request message (RREQ) using OrigAddr and TargAddr. The procedure 1066 for this is described in Section 7.1.1. Each new RREQ results in an 1067 increment to the sequence number. The AODVv2 router is referred to 1068 as RREQ_Gen. 1070 IP packets awaiting a route MAY be buffered by RREQ_Gen. Buffering 1071 of IP packets can have both positive and negative effects. Real-time 1072 traffic, voice, and scheduled delivery may suffer if packets are 1073 buffered and subjected to delays, but TCP connection establishment 1074 will benefit if packets are queued while route discovery is 1075 performed. 1077 Determining which packets to discard first when the buffer is full is 1078 a matter of policy at each AODVv2 router. Routers without sufficient 1079 memory available for buffering SHOULD have buffering disabled. This 1080 will affect the latency for launching TCP applications to new 1081 destinations. 1083 RREQ_Gen awaits reception of a Route Reply message (RREP) containing 1084 a route toward TargAddr. An RREQ from TargAddr would also fulfil the 1085 request, if adjacency to the next hop is already confirmed. If a 1086 route to TargAddr is not learned within RREQ_WAIT_TIME, RREQ_Gen MAY 1087 retry the route discovery. To reduce congestion in a network, 1088 repeated attempts at route discovery for a particular target address 1089 SHOULD utilize a binary exponential backoff: for each additional 1090 attempt, the waiting time for receipt of the RREP is multiplied by 2. 1091 If the requested route is not learned within the wait period, another 1092 RREQ MAY be sent, up to a total of DISCOVERY_ATTEMPTS_MAX. This is 1093 the same technique used in AODV [RFC3561]. 1095 The RREQ is received by neighboring AODVv2 routers, and processed and 1096 regenerated as described in Section 7.1. Intermediate routers learn 1097 a potential route to OrigAddr from the RREQ. The router responsible 1098 for TargAddr responds by generating a Route Reply message (RREP) and 1099 unicasts it back toward RREQ_Gen using the potential route to 1100 OrigAddr learned from the RREQ. Each intermediate router regenerates 1101 the RREP and unicasts toward OrigAddr. 1103 Links which are not bidirectional cause problems. If a link is 1104 unavailable in the direction toward OrigAddr, an RREP is not received 1105 at the next hop, so cannot be regenerated, and it will never reach 1106 RREQ_Gen. However, since routers monitor adjacencies (Section 6.2), 1107 the loss of the RREP will cause the last router which regenerated the 1108 RREP to blacklist the router which did not receive it. Later, a 1109 timeout occurs at RREQ_Gen, and a new RREQ MAY be regenerated. If 1110 the new RREQ arrives via the blacklisted router, it will be ignored, 1111 enabling the RREQ to discover a different path toward TargAddr. 1113 Route discovery SHOULD be considered to have failed after 1114 DISCOVERY_ATTEMPTS_MAX and the corresponding wait time for an RREP 1115 response to the final RREQ, in order to avoid repeatedly generating 1116 control traffic that is unlikely to discover a route. After the 1117 attempted route discovery has failed, RREQ_Gen MUST wait at least 1118 RREQ_HOLDDOWN_TIME before attempting another route discovery to the 1119 same destination, to avoid generating more multicast messages which 1120 are unlikely to discover a route. Any IP packets buffered for 1121 TargAddr MUST also be dropped and a Destination Unreachable ICMP 1122 message (Type 3) with a code of 1 (Host Unreachable Error) SHOULD be 1123 delivered to the source of the packet, so that the application knows 1124 about the failure. The source can be an application on RREQ_Gen 1125 itself, or on a Router Client with address OrigAddr. 1127 If RREQ_Gen does receive a route message containing a route to 1128 TargAddr within the timeout, it MUST process the message according to 1129 Section 7. When a valid route is installed, the router can begin 1130 sending the buffered IP packets. Any retry timers for the 1131 corresponding RREQ MUST be cancelled. 1133 During route discovery, all routers on the path learn a route to both 1134 OrigAddr and TargAddr, so that routes are constructed in both 1135 directions. The route is optimized for the forward route, and the 1136 return route uses the same path in reverse. 1138 6.7. Processing Received Route Information 1140 All AODVv2 route messages contain a route. A Route Request (RREQ) 1141 includes a route to OrigAddr, and a Route Reply (RREP) contains a 1142 route to TargAddr. 1144 All AODVv2 routers that receive a route message can store the route 1145 contained within it. Incoming information is first checked to verify 1146 that it is both safe to use and offers an improvement to existing 1147 information. This process is explained in Section 6.7.1. The route 1148 table MAY then be updated according to Section 6.7.2. 1150 In the processes below, RteMsg is used to denote the route message, 1151 AdvRte is used to denote the route contained within it, and Route 1152 denotes an existing route which matches AdvRte on address, prefix 1153 length, and metric type. 1155 AdvRte has the following properties: 1157 o AdvRte.Address := RteMsg.OrigAddr (in RREQ) or RteMsg.TargAddr (in 1158 RREP) 1160 o AdvRte.PrefixLength := RteMsg.OrigPrefixLen (in RREQ) or 1161 RteMsg.TargPrefixLen (in RREP) if included, or if no prefix length 1162 was included in RteMsg, the address length, in bits, of 1163 AdvRte.Address 1165 o AdvRte.SeqNum := RteMsg.OrigSeqNum (in RREQ) or RteMsg.TargSeqNum 1166 (in RREP) 1168 o AdvRte.NextHop := RteMsg.IPSourceAddress (an address of the router 1169 from which the AdvRte was received) 1171 o AdvRte.MetricType := RteMsg.MetricType 1173 o AdvRte.Metric := RteMsg.Metric 1175 o AdvRte.Cost := Cost(R) using the cost function associated with the 1176 route's metric type, i.e. Cost(R) = AdvRte.Metric + Cost(L), as 1177 described in Section 5, where L is the link from the advertising 1178 router. 1180 o AdvRte.ValidityTime := RteMsg.ValidityTime, if included 1182 6.7.1. Evaluating Route Information 1184 An incoming route advertisement (AdvRte) is compared to existing 1185 routes to determine whether the advertised route is to be used to 1186 update the routing table. The incoming route information MUST be 1187 processed as follows: 1189 1. Search for a route (Route) matching AdvRte's address, prefix 1190 length and metric type 1192 * If no matching route exists, AdvRte MUST be used to update the 1193 routing table. Multiple routes to the same destination may 1194 exist with different metric types. 1196 * If all matching routing table entries have State set to 1197 Unconfirmed, AdvRte SHOULD be added to the routing table. 1198 This may result in multiple Unconfirmed routes to the same 1199 address. In this case, the best route from the set of 1200 Unconfirmed routes SHOULD be used to forward future RREPs. If 1201 the link to the next hop is found to be bidirectional, and the 1202 Unconfirmed route becomes valid, any remaining Unconfirmed 1203 routes which would not offer improvement MUST be expunged. 1205 * If a matching route exists with State set to Active, Idle, or 1206 Invalid, continue to Step 2. 1208 2. Compare sequence numbers using the technique described in 1209 Section 4.4 1211 * If AdvRte is more recent, AdvRte MUST be used to update the 1212 routing table. 1214 * If AdvRte is stale, AdvRte MUST NOT be used to update the 1215 routing table. 1217 * If the sequence numbers are equal, continue to Step 3. 1219 3. Check that AdvRte is safe against routing loops (see Section 5) 1221 * If LoopFree(AdvRte, Route) returns FALSE, AdvRte MUST NOT be 1222 used to update the routing table because using the incoming 1223 information might cause a routing loop. 1225 * If LoopFree(AdvRte, Route) returns TRUE, continue to Step 4. 1227 4. Compare route costs 1229 * If AdvRte is better, it SHOULD be used to update the routing 1230 table because it offers improvement. If it is not used to 1231 update the existing route, the existing non-optimal route will 1232 continue to be used, causing data flows to use a route with a 1233 worse cost where this could have been avoided. 1235 * If AdvRte is equal in cost and Route is Valid, AdvRte MAY be 1236 used to update the routing table but will offer no 1237 improvement. 1239 * If AdvRte is worse and Route is valid, AdvRte MUST NOT be used 1240 to update the routing table because it does not offer any 1241 improvement. 1243 * If AdvRte is not better (i.e., it is worse or equal) but Route 1244 is Invalid, AdvRte SHOULD be used to update the routing table 1245 because it can safely repair the existing Invalid route. 1247 If the advertised route SHOULD be used to update the routing table, 1248 the procedure in Section 6.7.2 MUST be followed. If the route is not 1249 used, non-optimal routes will remain in the routing table. 1251 6.7.2. Applying Route Updates 1253 If AdvRte is from an RREQ message, the next hop neighbor may not be 1254 confirmed as adjacent (see Section 4.3). If Neighbor.State is 1255 Unknown, the route to AdvRte.Address might not be viable, but it MUST 1256 be stored to allow a corresponding RREP to be sent. However, the 1257 route's State will be set to Unconfirmed to indicate that this route 1258 SHOULD NOT yet be used to forward data, since the link may be uni- 1259 directional and packet losses may occur. If a valid route already 1260 exists for this destination, this Unconfirmed route SHOULD be stored 1261 as an additional entry. If the link to the next hop is later 1262 confirmed to be bidirectional, the route will offer improvement over 1263 the existing valid route. 1265 The route update is applied as follows: 1267 1. If no existing route matches AdvRte on address, prefix length and 1268 metric type, continue to Step 3 and create a new route. 1270 2. If a matching route exists: 1272 * If AdvRte has a different next hop to the existing route 1273 (Route), and both AdvRte.NextHop's Neighbor.State is Unknown 1274 and Route.State is Active or Idle, the current route is valid 1275 but the advertised route may offer improvement, if the next 1276 hop can be confirmed as bidirectional. Continue processing 1277 from Step 3 to create a new route. 1279 * If AdvRte.NextHop's Neighbor.State is Unknown and Route.State 1280 is Invalid, continue processing from Step 4 to update the 1281 existing route (Route). 1283 * If AdvRte.NextHop's Neighbor.State is Confirmed, continue 1284 processing from Step 4 to update the existing route. 1286 3. Create a route and initialize as follows: 1288 * Route.Address := AdvRte.Address 1290 * Route.PrefixLength := AdvRte.PrefixLength 1291 * Route.MetricType := AdvRte.MetricType 1293 4. Update the route as follows: 1295 * Route.SeqNum := AdvRte.SeqNum 1297 * Route.NextHop := AdvRte.NextHop 1299 * Route.NextHopInterface := interface on which RteMsg was 1300 received 1302 * Route.Metric := AdvRte.Cost 1304 * Route.LastUsed := CurrentTime 1306 * Route.LastSeqNumUpdate := CurrentTime 1308 * Route.ExpirationTime := CurrentTime + AdvRte.ValidityTime if a 1309 validity time exists, otherwise INFINITY_TIME 1311 5. If a new route was created, or if the existing Route.State is 1312 Invalid or Unconfirmed, update the route as follows: 1314 * Route.State := Unconfirmed (if the next hop's Neighbor.State 1315 is Unknown) or Idle (if the next hop's Neighbor.State is 1316 Confirmed) 1318 6. If an existing route changed from Invalid or Unconfirmed to 1319 become Idle, any matching route table entries with worse metric 1320 values SHOULD be expunged. 1322 7. If this update results in a route with Route.State set to Active 1323 or Idle, which matches an outstanding route request, the 1324 associated route request retry timers can be cancelled and any 1325 associated buffered IP packets MUST be forwarded. 1327 6.8. Suppressing Redundant Messages Using the Multicast Route Message 1328 Table 1330 When route messages are flooded in a MANET, an AODVv2 router may 1331 receive multiple similar messages. Regenerating every one of these 1332 gives little additional benefit, and generates unnecessary signaling 1333 traffic and interference. 1335 Each AODVv2 router stores information about recently received route 1336 messages in the AODVv2 Multicast Route Message Table (Section 4.5). 1338 To create a Multicast Route Message Table Entry: 1340 o RteMsg.MessageType := RREQ or RREP 1342 o RteMsg.OrigAddr := OrigAddr from the message 1344 o RteMsg.OrigPrefixLen := the prefix length associated with OrigAddr 1346 o RteMsg.TargAddr := TargAddr from the message 1348 o RteMsg.TargPrefixLen := the prefix length associated with TargAddr 1350 o RteMsg.OrigSeqNum := the sequence number associated with OrigAddr, 1351 if present in the message 1353 o RteMsg.TargSeqNum := the sequence number associated with TargAddr, 1354 if present in the message 1356 o RteMsg.MetricType := the metric type of the route requested 1358 o RteMsg.Metric := the metric value associated with OrigAddr in an 1359 RREQ or TargAddr in an RREP 1361 o RteMsg.Timestamp := CurrentTime 1363 o RteMsg.RemoveTime := CurrentTime + MAX_SEQNUM_LIFETIME 1365 Entries in the Multicast Route Message Table SHOULD be maintained for 1366 at least RteMsg_ENTRY_TIME after the last Timestamp update in order 1367 to account for long-lived RREQs traversing the network. An entry 1368 MUST be deleted when the sequence number is no longer valid, i.e., 1369 after MAX_SEQNUM_LIFETIME. Memory-constrained devices MAY remove the 1370 entry before this time. 1372 To update a Multicast Route Message Table Entry, set: 1374 o RteMsg.OrigSeqNum := the sequence number associated with OrigAddr, 1375 if present in the message 1377 o RteMsg.TargSeqNum := the sequence number associated with TargAddr, 1378 if present in the message 1380 o RteMsg.Metric := the metric value associated with OrigAddr in an 1381 RREQ or TargAddr in an RREP 1383 o RteMsg.Timestamp := CurrentTime 1385 o RteMsg.RemoveTime := CurrentTime + MAX_SEQNUM_LIFETIME 1386 Received route messages are tested against previously received route 1387 messages, and if determined to be redundant, regeneration or response 1388 can be avoided. 1390 To determine if a received message is redundant: 1392 1. Search for an entry in the Multicast Route Message Table with the 1393 same MessageType, OrigAddr, TargAddr, and MetricType 1395 * If there is none, the message is not redundant. 1397 * If there is an entry, continue to Step 2. 1399 2. Compare sequence numbers using the technique described in 1400 Section 4.4 1402 * For RREQ messages, use OrigSeqNum of the entry for comparison. 1403 For RREP messages, use TargSeqNum of the entry for comparison. 1405 * If the entry has an older sequence number than the received 1406 message, the message is not redundant. 1408 * If the entry has a newer sequence number than the received 1409 message, the message is redundant. 1411 * If the entry has the same sequence number, continue to Step 3. 1413 3. Compare the metric values 1415 * If the entry has a Metric value that is worse than or equal to 1416 the metric in the received message, the message is redundant. 1418 * If the entry has a Metric value that is better than the metric 1419 in the received message, the message is not redundant. 1421 If the message is redundant, update the timestamp on the entry, since 1422 matching route messages are still traversing the network and this 1423 entry should be maintained. This message SHOULD NOT be regenerated 1424 or responded to. 1426 If the message is not redundant, create an entry or update the 1427 existing entry. Where the message is determined not redundant before 1428 Step 3, it MUST be regenerated or responded to. Where the message is 1429 determined not redundant in Step 3, it MAY be suppressed to avoid 1430 extra control traffic. However, since the processing of the message 1431 will result in an update to the route table, the message SHOULD be 1432 regenerated or responded to, to ensure other routers have up-to-date 1433 information and the best metrics. If not regenerated, the best route 1434 may not be found. Where necessary, regeneration or response is 1435 performed using the processes in Section 7. 1437 6.9. Route Maintenance 1439 Route maintenance involves monitoring and updating route state, 1440 handling route timeouts and reporting routes that become Invalid. 1442 Before using a route to forward an IP packet, an AODVv2 router MUST 1443 check firstly if there is a route, and secondly the status of the 1444 route (Section 6.9.1). If the route exists and is valid, it MUST be 1445 marked as Active and its LastUsed timestamp MUST be updated, before 1446 forwarding the IP packet to the route's next hop. If there is no 1447 valid route, and if the source address of the IP packet is a Router 1448 Client, the RREQ generation procedure MUST be followed. Otherwise, 1449 the absence of a route MUST be reported to the packet's source (see 1450 Section 6.9.2). 1452 6.9.1. Route State 1454 During normal operation, AODVv2 does not require any explicit 1455 timeouts to manage the lifetime of a route. At any time, any route 1456 MAY be examined and updated according to the rules below. If timers 1457 are not used to prompt route state updates, route state MUST be 1458 checked before IP packet forwarding and before any operation based on 1459 route state. 1461 The four possible states for an AODVv2 route are Active, Idle, 1462 Invalid, and Unconfirmed: 1464 Active 1465 If Route.State is Active and the route is not timed (i.e., if 1466 Route.ExpirationTime is INFINITY_TIME), Route.State MUST become 1467 Idle if Route is not used to forward IP packets within 1468 ACTIVE_INTERVAL. Route.State for a timed route (i.e., 1469 Route.ExpirationTime is not equal to INFINITY_TIME) remains Active 1470 until its expiration time, after which it MUST become Invalid. 1472 Idle 1473 If Route.State is Idle, and the route is used to forward an IP 1474 packet, Route.State MUST become Active. If the route is not used 1475 to forward an IP packet within MAX_IDLETIME, Route.State MUST 1476 become Invalid. 1478 Invalid 1479 If Route.State is Invalid, the route SHOULD be maintained until 1480 MAX_SEQNUM_LIFETIME after Route.LastSeqNumUpdate, after which it 1481 MUST be expunged. Route.SeqNum is used to classify future 1482 information about Route.Address as stale or fresh. 1484 Unconfirmed 1485 If Route.State is Unconfirmed, the route MUST become Idle when an 1486 adjacency with Route.NextHop is confirmed, or MUST be expunged if 1487 the neighbor is blacklisted, or at MAX_SEQNUM_LIFETIME after 1488 Route.LastSeqNumUpdate. 1490 In all cases, if the time since Route.LastSeqNumUpdate exceeds 1491 MAX_SEQNUM_LIFETIME, Route.SeqNum must be set to zero. This is 1492 required to ensure that any AODVv2 routers following the 1493 initialization procedure can safely begin routing functions using a 1494 new sequence number, and that their messages will not be classified 1495 as stale and ignored. A route with Route.State set to Active or Idle 1496 can continue to be used to forward IP packets, but if Route.State 1497 later becomes Invalid, the route MUST be expunged. 1499 Appendix C.2.1.1 contains an algorithmic representation of this 1500 timeout behavior. 1502 Routes can become Invalid before a timeout occurs: 1504 o If a link breaks, all routes using that link for Route.NextHop 1505 MUST immediately have Route.State set to Invalid. 1507 o If a Route Error (RERR) message containing the route is received, 1508 either from Route.NextHop, or with PktSource set to a Router 1509 Client address, Route.State MUST immediately be set to Invalid. 1511 When Route.State changes from Unconfirmed to Idle as a result of the 1512 adjacency with Route.NextHop being Confirmed (see Section 4.3), any 1513 matching routes with metric values worse than Route.Metric MUST be 1514 expunged. 1516 Memory constrained devices MAY choose to expunge routes from the 1517 AODVv2 route table before Route.ExpirationTime, but MUST adhere to 1518 the following rules: 1520 o An Active route MUST NOT be expunged, as this will result in 1521 generation of a Route Error message followed by a necessary Route 1522 Request to re-establish the route. 1524 o An Idle route SHOULD NOT be expunged, as the route is still valid 1525 for forwarding IP traffic, and if deleted, this could result in 1526 dropped IP packets and a Route Request could be generated to re- 1527 establish the route. 1529 o Any Invalid route MAY be expunged; least recently used Invalid 1530 routes SHOULD be expunged first, since these are less likely to be 1531 reused. 1533 o An Unconfirmed route MUST NOT be expunged if it was installed 1534 within the last RREQ_WAIT_TIME, because it may correspond to a 1535 route discovery in progress. A Route Reply message might be 1536 received which needs to use the Route.NextHop information. 1537 Otherwise, it MAY be expunged. 1539 Route table entries are updated when Neighbor State is updated: 1541 o While Neighbor.State is set to Unknown, any routes learned through 1542 that neighbor are marked as Unconfirmed. 1544 o When Neighbor.State is set to Confirmed, the Unconfirmed routes 1545 using the neighbor as a next hop SHOULD be marked as valid (see 1546 Section 6.9.1). 1548 o When Neighbor.State is set to Blacklisted, any valid routes 1549 installed which use that neighbor for their next hop are marked as 1550 Invalid. 1552 o When a Neighbor Table entry is removed, all routes using the 1553 neighbor as next hop MUST be marked as Invalid. 1555 6.9.2. Reporting Invalid Routes 1557 When Route.State changes from Active to Invalid as a result of a 1558 broken link or a received Route Error (RERR) message, other routers 1559 SHOULD be informed by sending an RERR message containing details of 1560 the invalidated route. 1562 An RERR message SHOULD also be sent when an AODVv2 router receives an 1563 IP packet to forward on behalf of another router but does not have a 1564 valid route for the destination of the packet. 1566 An RERR message SHOULD also be sent when an AODVv2 router receives an 1567 RREP message to regenerate, but the route to the OrigAddr in the RREP 1568 has been lost and is marked as Invalid. 1570 The packet or message triggering the RERR MUST be discarded. 1572 Generation of an RERR message is described in Section 7.4.1. 1574 7. AODVv2 Protocol Messages 1576 AODVv2 defines four message types: Route Request (RREQ), Route Reply 1577 (RREP), Route Reply Acknowledgement (RREP_Ack), and Route Error 1578 (RERR). 1580 Each AODVv2 message is defined as a set of Data Elements. Rules for 1581 the generation, reception and regeneration of each message type are 1582 described in the following sections. Section 8 discusses how the 1583 Data Elements map to [RFC5444] Message TLVs, Address Blocks, and 1584 Address TLVs. 1586 7.1. Route Request (RREQ) Message 1588 Route Request messages are used in route discovery operations to 1589 request a route to a specified target address. RREQ messages have 1590 the following contents: 1592 +-----------------------------------------------------------------+ 1593 | msg_hop_limit, (optional) msg_hop_count | 1594 +-----------------------------------------------------------------+ 1595 | AddressList | 1596 +-----------------------------------------------------------------+ 1597 | PrefixLengthList (optional) | 1598 +-----------------------------------------------------------------+ 1599 | OrigSeqNum, (optional) TargSeqNum | 1600 +-----------------------------------------------------------------+ 1601 | MetricType | 1602 +-----------------------------------------------------------------+ 1603 | OrigMetric | 1604 +-----------------------------------------------------------------+ 1605 | ValidityTime (optional) | 1606 +-----------------------------------------------------------------+ 1608 Figure 1: RREQ message contents 1610 RREQ Data Elements 1612 msg_hop_limit 1613 The remaining number of hops allowed for dissemination of the RREQ 1614 message. 1616 msg_hop_count 1617 The number of hops already traversed during dissemination of the 1618 RREQ message. 1620 AddressList 1621 Contains OrigAddr and TargAddr, the source and destination 1622 addresses of the IP packet for which a route is requested. 1623 OrigAddr and TargAddr MUST be routable unicast addresses. 1625 PrefixLengthList 1626 Contains OrigPrefixLen, i.e., the length, in bits, of the prefix 1627 associated with OrigAddr. If omitted, the prefix length is equal 1628 to OrigAddr's address length in bits. 1630 OrigSeqNum 1631 The sequence number associated with OrigAddr. 1633 TargSeqNum 1634 A sequence number associated with TargAddr. This MAY be included 1635 if an Invalid route exists to the target. This is useful for the 1636 optional Intermediate RREP feature (see Section 10.3). 1638 MetricType 1639 The metric type associated with OrigMetric. 1641 OrigMetric 1642 The metric value associated with the route to OrigAddr, as 1643 measured by the sender of the message. 1645 ValidityTime 1646 The length of time that the message sender is willing to offer a 1647 route toward OrigAddr. Omitted if no time limit is imposed. 1649 7.1.1. RREQ Generation 1651 An RREQ is generated when an IP packet needs to be forwarded for a 1652 Router Client, and no valid route currently exists for the packet's 1653 destination. 1655 Before creating an RREQ, the router SHOULD check if an RREQ has 1656 recently been sent for the requested destination. If so, and the 1657 wait time for a reply has not yet been reached, the router SHOULD 1658 continue to await a response without generating a new RREQ. If the 1659 timeout has been reached, a new RREQ MAY be generated. If buffering 1660 is configured, the incoming IP packet SHOULD be buffered until the 1661 route discovery is completed. 1663 If the limit for the rate of AODVv2 control message generation has 1664 been reached, no message SHOULD be generated. If approaching the 1665 limit, the message should be sent if the priorities in Section 6.5 1666 allow it. 1668 To generate the RREQ, the router (referred to as RREQ_Gen) follows 1669 this procedure: 1671 1. Set msg_hop_limit := MAX_HOPCOUNT 1673 2. Set msg_hop_count := 0, if including it 1675 3. Set AddressList := {OrigAddr, TargAddr} 1677 4. For the PrefixLengthList: 1679 * If OrigAddr is part of an address range configured as a Router 1680 Client, set PrefixLengthList := {OrigPrefixLen, null}. 1682 * Otherwise, omit PrefixLengthList. 1684 5. For OrigSeqNum: 1686 * Increment the router SeqNum as specified in Section 4.4. 1688 * Set OrigSeqNum := SeqNum. 1690 6. For TargSeqNum: 1692 * If an Invalid route exists matching TargAddr using longest 1693 prefix matching and has a valid sequence number, set 1694 TargSeqNum := route's sequence number. 1696 * If no Invalid route exists matching TargAddr, or the route 1697 doesn't have a sequence number, omit TargSeqNum. 1699 7. Include the MetricType Data Element and set the type accordingly 1701 8. Set OrigMetric := Route[OrigAddr].Metric, i.e., RouterClient.Cost 1703 9. Include the ValidityTime Data Element if advertising that the 1704 route to OrigAddr via this router is offered for a limited time, 1705 and set ValidityTime accordingly 1707 This AODVv2 message is used to create a corresponding [RFC5444] 1708 message (see Section 8) which is multicast, by default, to LL-MANET- 1709 Routers on all interfaces configured for AODVv2 operation. 1711 7.1.2. RREQ Reception 1713 Upon receiving an RREQ, an AODVv2 router performs the following 1714 steps: 1716 1. If the sender is blacklisted (Section 4.3), check the entry's 1717 reset time 1719 * If CurrentTime < Remove Time, ignore this RREQ for further 1720 processing. 1722 * If CurrentTime >= Remove Time, reset the neighbor state to 1723 Unknown and continue to Step 2. 1725 2. Verify that the message hop count, if included, hasn't exceeded 1726 MAX_HOPCOUNT 1728 * If so, ignore this RREQ for further processing. 1730 3. Verify that the message contains the required Data Elements: 1731 msg_hop_limit, OrigAddr, TargAddr, OrigSeqNum, and OrigMetric, 1732 and that OrigAddr and TargAddr are valid addresses (routable and 1733 unicast) 1735 * If not, ignore this RREQ for further processing. 1737 4. Check that the MetricType is supported and configured for use 1739 * If not, ignore this RREQ for further processing. 1741 5. Verify that the cost of the advertised route will not exceed the 1742 maximum allowed metric value for the metric type (Metric <= 1743 MAX_METRIC[MetricType] - Cost(L)) 1745 * If it will, ignore this RREQ for further processing. 1747 6. Process the route to OrigAddr as specified in Section 6.7.1 1749 7. Check if the message is redundant by comparing to entries in the 1750 Multicast Route Message table, following the procedure in 1751 (Section 6.8) 1753 * If redundant, ignore this RREQ for further processing. 1755 * If not redundant, continue processing. 1757 8. Check if the TargAddr belongs to one of the Router Clients 1759 * If so, generate an RREP as specified in Section 7.2.1. 1761 * If not, continue to RREQ regeneration. 1763 7.1.3. RREQ Regeneration 1765 By regenerating an RREQ, a router advertises that it will forward IP 1766 packets to the OrigAddr contained in the RREQ according to the 1767 information enclosed. The router MAY choose not to regenerate the 1768 RREQ, though this could decrease connectivity in the network or 1769 result in non-optimal paths. The full set of circumstances under 1770 which a router might avoid regenerating an RREQ are not declared in 1771 this document, though examples include the router being heavily 1772 loaded or low on energy and therefore unwilling to advertise routing 1773 capability for more traffic. 1775 The RREQ SHOULD NOT be regenerated if the limit for the rate of 1776 AODVv2 control message generation has been reached. If approaching 1777 the limit, the message should be sent if the priorities in 1778 Section 6.5 allow it. 1780 The procedure for RREQ regeneration is as follows: 1782 1. Set msg_hop_limit := received msg_hop_limit - 1 1784 2. If msg_hop_limit is now zero, do not continue the regeneration 1785 process 1787 3. Set msg_hop_count := received msg_hop_count + 1, if included, 1788 otherwise omit msg_hop_count 1790 4. Set AddressList, PrefixLengthList, sequence numbers and 1791 MetricType to the values in the received RREQ 1793 5. Set OrigMetric := Route[OrigAddr].Metric 1795 6. If the received RREQ contains a ValidityTime, or if the 1796 regenerating router wishes to limit the time that it offers a 1797 route to OrigAddr, the regenerated RREQ MUST include a 1798 ValidityTime Data Element 1800 * The ValidityTime is either the time limit the previous AODVv2 1801 router specified, or the time limit this router wishes to 1802 impose, whichever is lower. 1804 This AODVv2 message is used to create a corresponding [RFC5444] 1805 message (see Section 8) which is multicast, by default, to LL-MANET- 1806 Routers on all interfaces configured for AODVv2 operation. However, 1807 the regenerated RREQ can be unicast to the next hop address of the 1808 route toward TargAddr, if known. 1810 7.2. Route Reply (RREP) Message 1812 When a Route Request message is received, requesting a route to a 1813 Target Address which is configured as a Router Client, a Route Reply 1814 message is sent in response. The RREP offers a route to the Target 1815 Address. 1817 The RREP is sent by unicast to the next hop router on the route to 1818 OrigAddr, if there is a Confirmed entry in the Neighbor Table for the 1819 next hop. Otherwise, the RREP is sent multicast to LL-MANET-Routers, 1820 including the AckReq Data Element in the message to indicate the 1821 intended next hop address and to request acknowledgement to confirm 1822 the neighbor adjacency. 1824 RREP messages have the following contents: 1826 +-----------------------------------------------------------------+ 1827 | msg_hop_limit, (optional) msg_hop_count | 1828 +-----------------------------------------------------------------+ 1829 | AckReq (optional) | 1830 +-----------------------------------------------------------------+ 1831 | AddressList | 1832 +-----------------------------------------------------------------+ 1833 | PrefixLengthList (optional) | 1834 +-----------------------------------------------------------------+ 1835 | TargSeqNum | 1836 +-----------------------------------------------------------------+ 1837 | MetricType | 1838 +-----------------------------------------------------------------+ 1839 | TargMetric | 1840 +-----------------------------------------------------------------+ 1841 | ValidityTime (optional) | 1842 +-----------------------------------------------------------------+ 1844 Figure 2: RREP message contents 1846 RREP Data Elements 1848 msg_hop_limit 1849 The remaining number of hops allowed for dissemination of the RREP 1850 message. 1852 msg_hop_count 1853 The number of hops already traversed during dissemination of the 1854 RREP message. 1856 AckReq 1857 The address of the intended next hop of the RREP. This Data 1858 Element is used when the RREP is to be multicast because the next 1859 hop toward OrigAddr is a neighbor with Unknown state. It 1860 indicates that an acknowledgement of the RREP is requested by the 1861 sender from the intended next hop (see Section 6.2). 1863 AddressList 1864 Contains OrigAddr and TargAddr, the source and destination 1865 addresses of the IP packet for which a route is requested. 1866 OrigAddr and TargAddr MUST be routable unicast addresses. 1868 PrefixLengthList 1869 Contains TargPrefixLen, i.e., the length, in bits, of the prefix 1870 associated with TargAddr. If omitted, the prefix length is equal 1871 to TargAddr's address length, in bits. 1873 TargSeqNum 1874 The sequence number associated with TargAddr. 1876 MetricType 1877 The metric type associated with TargMetric. 1879 TargMetric 1880 The metric value associated with the route to TargAddr, as seen 1881 from the sender of the message. 1883 ValidityTime 1884 The length of time that the message sender is willing to offer a 1885 route toward TargAddr. Omitted if no time limit is imposed. 1887 7.2.1. RREP Generation 1889 An RREP is generated when an RREQ arrives requesting a route to one 1890 of the AODVv2 router's Router Clients. 1892 Before creating an RREP, the router SHOULD check if the corresponding 1893 RREQ is redundant, i.e., a response has already been generated, or if 1894 the limit for the rate of AODVv2 control message generation has been 1895 reached. If so, the RREP SHOULD NOT be created. If approaching the 1896 limit, the message should be sent if the priorities in Section 6.5 1897 allow it. 1899 If the next hop neighbor on the route to OrigAddr is not yet 1900 confirmed as adjacent (as described in Section 6.2), the RREP MUST 1901 include an AckReq Data Element including the intended next hop 1902 address, in order to perform adjacency monitoring. If the next hop 1903 neighbor is already confirmed as adjacent, the AckReq Data Element 1904 can be omitted. The AckReq Data Element indicates that an 1905 acknowledgement to the RREP is requested from the intended next hop 1906 router in the form of a Route Reply Acknowledgement (RREP_Ack). 1908 Implementations MAY allow a number of retries of the RREP if an 1909 acknowledgement is not received within RREP_Ack_SENT_TIMEOUT, 1910 doubling the timeout with each retry, up to a maximum of 1911 RREP_RETRIES, using the same exponential backoff described in 1912 Section 6.6 for RREQ retries. Adjacency confirmation MUST be 1913 considered to have failed after the wait time for an RREP_Ack 1914 response to the final RREP. The next hop router MUST be marked as 1915 blacklisted (Section 4.3), and any installed routes with next hop set 1916 to the newly blacklisted router SHOULD become Invalid. 1918 To generate the RREP, the router (also referred to as RREP_Gen) 1919 follows this procedure: 1921 1. Set msg_hop_limit := msg_hop_count from the received RREQ 1922 message, if it was included, or MAX_HOPCOUNT if it was not 1923 included 1925 2. Set msg_hop_count := 0, if including it 1927 3. If adjacency with the next hop toward OrigAddr is not already 1928 confirmed, include the AckReq Data Element with the address of 1929 the intended next hop router 1931 4. Set Address List := {OrigAddr, TargAddr} 1933 5. For the PrefixLengthList: 1935 * If TargAddr is part of an address range configured as a Router 1936 Client, set PrefixLengthList := {null, TargPrefixLen}. 1938 * Otherwise, omit PrefixLengthList. 1940 6. For the TargSeqNum: 1942 * Increment the router SeqNum as specified in Section 4.4. 1944 * Set TargSeqNum := SeqNum. 1946 7. Include the MetricType Data Element and set the type to match the 1947 MetricType in the received RREQ message 1949 8. Set TargMetric := Route[TargAddr].Metric, i.e., RouterClient.Cost 1950 9. Include the ValidityTime Data Element if advertising that the 1951 route to TargAddr via this router is offered for a limited time, 1952 and set ValidityTime accordingly 1954 This AODVv2 message is used to create a corresponding [RFC5444] 1955 message (see Section 8). If there is a Confirmed entry in the 1956 Neighbor Table for the next hop router on the route to OrigAddr, the 1957 RREP is sent by unicast to the next hop. Otherwise, the RREP is sent 1958 multicast to LL-MANET-Routers. 1960 7.2.2. RREP Reception 1962 Upon receiving an RREP, an AODVv2 router performs the following 1963 steps: 1965 1. If the sender is blacklisted (Section 4.3), but the RREP answers 1966 a recently sent RREQ, the Neighbor Table entry for this sender 1967 SHOULD have State set to Confirmed since an RREP is an 1968 indication of adjacency 1970 2. Verify that the message hop count, if included, hasn't exceeded 1971 MAX_HOPCOUNT 1973 * If so, ignore this RREQ for further processing. 1975 3. Verify that the message contains the required Data Elements: 1976 msg_hop_limit, OrigAddr, TargAddr, TargSeqNum, and TargMetric, 1977 and that OrigAddr and TargAddr are valid addresses (routable and 1978 unicast) 1980 * If not, ignore this RREP for further processing. 1982 4. Check that the MetricType is supported and configured for use 1984 * If not, ignore this RREP for further processing. 1986 5. Verify that the cost of the advertised route does not exceed the 1987 maximum allowed metric value for the metric type (Metric <= 1988 MAX_METRIC[MetricType] - Cost(L)) 1990 * If it does, ignore this RREP for further processing. 1992 6. If the AckReq Data Element is present, check the intended 1993 recipient of the received RREP 1995 * If the receiving router is the intended recipient, send an 1996 acknowledgement as specified in Section 7.3 and continue 1997 processing. 1999 * If the receiving router is not the intended recipient, ignore 2000 this RREP for further processing. 2002 7. Process the route to TargAddr as specified in Section 6.7.1 2004 * If the route to TargAddr fulfills a previously sent RREQ, any 2005 associated timeouts will be cancelled and buffered IP packets 2006 will be forwarded to TargAddr, but processing continues to 2007 Step 8. 2009 8. Check if the message is redundant by comparing to entries in the 2010 Multicast Route Message table (Section 6.8) 2012 * If redundant, ignore this RREP for further processing. 2014 * If not redundant, save the information in the Multicast Route 2015 Message table to identify future redundant RREP messages and 2016 continue processing. 2018 9. Check if the OrigAddr belongs to one of the Router Clients 2020 * If so, no further processing is necessary. 2022 10. Check if a valid (Active or Idle) or Unconfirmed route exists to 2023 OrigAddr 2025 * If so, continue to RREP regeneration. 2027 * If not, a Route Error message SHOULD be transmitted to 2028 TargAddr according to Section 7.4.1 and the RREP SHOULD be 2029 discarded and not regenerated. 2031 7.2.3. RREP Regeneration 2033 A received Route Reply message is regenerated toward OrigAddr. 2034 Unless the router is prepared to advertise the route contained within 2035 the received RREP, it halts processing. By regenerating a RREP, a 2036 router advertises that it will forward IP packets to TargAddr 2037 according to the information enclosed. The router MAY choose not to 2038 regenerate the RREP, in the same way it MAY choose not to regenerate 2039 an RREQ (see Section 7.1.3), though this could decrease connectivity 2040 in the network or result in non-optimal paths. 2042 The RREP SHOULD NOT be regenerated if the limit for the rate of 2043 AODVv2 control message generation has been reached. If approaching 2044 the limit, the message should be sent if the priorities in 2045 Section 6.5 allow it. 2047 If the next hop neighbor on the route to OrigAddr is not yet 2048 confirmed as adjacent (as described in Section 6.2), the RREP MUST 2049 include an AckReq Data Element including the intended next hop 2050 address, in order to perform adjacency monitoring. If the adjacency 2051 is already confirmed, the AckReq Data Element can be omitted. The 2052 AckReq Data Element indicates that an acknowledgement to the RREP is 2053 requested in the form of a Route Reply Acknowledgement (RREP_Ack) 2054 from the intended next hop router. 2056 The procedure for RREP regeneration is as follows: 2058 1. Set msg_hop_limit := received msg_hop_limit - 1 2060 2. If msg_hop_limit is now zero, do not continue the regeneration 2061 process 2063 3. Set msg_hop_count := received msg_hop_count + 1, if it was 2064 included, otherwise omit msg_hop_count 2066 4. If an adjacency with the next hop toward OrigAddr is not already 2067 confirmed, include the AckReq Data Element with the address of 2068 the intended next hop router 2070 5. Set AddressList, PrefixLengthList, TargSeqNum and MetricType to 2071 the values in the received RREP 2073 6. Set TargMetric := Route[TargAddr].Metric 2075 7. If the received RREP contains a ValidityTime, or if the 2076 regenerating router wishes to limit the time that it will offer a 2077 route to TargAddr, the regenerated RREP MUST include a 2078 ValidityTime Data Element 2080 * The ValidityTime is either the time limit the previous AODVv2 2081 router specified, or the time limit this router wishes to 2082 impose, whichever is lower. 2084 This AODVv2 message is used to create a corresponding [RFC5444] 2085 message (see Section 8). If there is a Confirmed entry in the 2086 Neighbor Table for the next hop router on the route to OrigAddr, the 2087 RREP is sent by unicast to the next hop. Otherwise, the RREP is sent 2088 multicast to LL-MANET-Routers. 2090 7.3. Route Reply Acknowledgement (RREP_Ack) Message 2092 The Route Reply Acknowledgement MUST be sent in response to a 2093 received Route Reply which includes an AckReq Data Element with an 2094 address matching one of the receiving router's IP addresses. When 2095 the RREP_Ack message is received, it confirms the adjacency between 2096 the two routers. The RREP_Ack has no Data Elements. 2098 7.3.1. RREP_Ack Generation 2100 An RREP_Ack MUST be generated when a received RREP includes the 2101 AckReq Data Element with the address of the receiving router. The 2102 RREP_Ack SHOULD NOT be generated if the limit for the rate of AODVv2 2103 control message generation has been reached. 2105 There are no Data Elements in an RREP_Ack. The [RFC5444] 2106 representation is discussed in Section 8. The RREP_Ack is unicast, 2107 by default, to the source IP address of the RREP message that 2108 requested it. 2110 7.3.2. RREP_Ack Reception 2112 Upon receiving an RREP_Ack, an AODVv2 router performs the following 2113 steps: 2115 1. If an RREP_Ack message was expected from the IP source address of 2116 the RREP_Ack, the router cancels any associated timeouts 2118 2. If the RREP_Ack was expected, ensure the router sending the 2119 RREP_Ack is marked with state Confirmed in the Neighbor 2120 Table (Section 4.3) 2122 7.4. Route Error (RERR) Message 2124 A Route Error message is generated by an AODVv2 router to notify 2125 other AODVv2 routers of routes that are no longer available. An RERR 2126 message has the following contents: 2128 +-----------------------------------------------------------------+ 2129 | msg_hop_limit | 2130 +-----------------------------------------------------------------+ 2131 | PktSource (optional) | 2132 +-----------------------------------------------------------------+ 2133 | AddressList | 2134 +-----------------------------------------------------------------+ 2135 | PrefixLengthList (optional) | 2136 +-----------------------------------------------------------------+ 2137 | SeqNumList (optional) | 2138 +-----------------------------------------------------------------+ 2139 | MetricTypeList | 2140 +-----------------------------------------------------------------+ 2142 Figure 3: RERR message contents 2144 RERR Data Elements 2146 msg_hop_limit 2147 The remaining number of hops allowed for dissemination of the RERR 2148 message. 2150 PktSource 2151 The source address of the IP packet triggering the RERR. If the 2152 RERR is triggered by a broken link, the PktSource Data Element is 2153 not required. 2155 AddressList 2156 The addresses of the routes no longer available through RERR_Gen. 2158 PrefixLengthList 2159 The prefix lengths, in bits, associated with the routes no longer 2160 available through RERR_Gen. These values indicate whether routes 2161 represent a single device or an address range. 2163 SeqNumList 2164 The sequence numbers of the routes no longer available through 2165 RERR_Gen (where known). 2167 MetricTypeList 2168 The metric types associated with the routes no longer available 2169 through RERR_Gen. 2171 7.4.1. RERR Generation 2173 An RERR is generated when an AODVv2 router (also referred to as 2174 RERR_Gen) needs to report that a destination is no longer reachable. 2175 There are two events that cause this response: 2177 o If an IP packet arrives that cannot be forwarded because no valid 2178 route exists for its destination, or if an RREP arrives which 2179 cannot be regenerated because no route exists to OrigAddr, the 2180 RERR generated MUST contain the PktSource Data Element and will 2181 contain only one unreachable address. The contents of PktSource 2182 and AddressList are set as follows: 2184 * For an IP packet that cannot be forwarded, PktSource is set to 2185 the source address of the IP packet, and the AddressList 2186 contains the destination address of the IP packet. 2188 * For an RREP message when the route to OrigAddr has been lost, 2189 PktSource is set to the TargAddr of the RREP, and the 2190 AddressList contains the OrigAddr from the RREP. 2192 The prefix length and sequence number MAY be included if known 2193 from an Invalid route entry to PktSource. The MetricTypeList MUST 2194 also be included if a MetricType can be determined from the IP 2195 packet or an existing Invalid route to PktSource. 2197 RERR_Gen MUST discard the IP packet or RREP message that triggered 2198 generation of the RERR. 2200 In order to avoid flooding the network with RERR messages when a 2201 stream of IP packets to an unreachable address arrives, an AODVv2 2202 router SHOULD determine whether an RERR has recently been sent 2203 with the same unreachable address and PktSource, and SHOULD avoid 2204 creating duplicate RERR messages. 2206 o When a link breaks, multiple routes may become Invalid, and the 2207 RERR generated MAY contain multiple unreachable addresses. If the 2208 message contents would cause the MTU to be exceeded, multiple RERR 2209 messages must be sent. The RERR MUST include the MetricTypeList 2210 Data Element. The PktSource Data Element is omitted. 2212 All previously Active routes that used the broken link MUST be 2213 reported. The AddressList, PrefixLengthList, SeqNumList, and 2214 MetricTypeList will contain entries for each route which has 2215 become Invalid. 2217 An RERR message is only sent if an Active route becomes Invalid, 2218 though an AODVv2 router can also include Idle routes that become 2219 Invalid if the configuration parameter ENABLE_IDLE_IN_RERR is set 2220 (see Section 11.3). 2222 Incidentally, if an AODVv2 router receives an ICMP error packet to or 2223 from the address of one of its Router Clients, it simply forwards the 2224 ICMP packet in the same way as any other IP packet, and will not 2225 generate any RERR message based on the contents of the ICMP packet. 2227 The RERR SHOULD NOT be generated if the limit for the rate of AODVv2 2228 control message generation has been reached. If approaching the 2229 limit, the message should be sent if the priorities in Section 6.5 2230 allow it. 2232 To generate the RERR, the router follows this procedure: 2234 1. Set msg_hop_limit := MAX_HOPCOUNT 2236 2. If necessary, include the PktSource Data Element and set the 2237 value to the source address of the IP packet triggering the RERR, 2238 or the TargAddr of an RREP that cannot be regenerated toward 2239 OrigAddr 2241 3. For each route that needs to be reported, while respecting the 2242 interface MTU: 2244 * Insert the route address into the AddressList. 2246 * Insert the prefix length into PrefixLengthList, if known and 2247 not equal to the address length. 2249 * Insert the sequence number into SeqNumList, if known. 2251 * Insert the metric type into MetricTypeList. 2253 4. If interface MTU would be exceeded, create additional RERR 2254 messages 2256 The AODVv2 message is used to create a corresponding [RFC5444] 2257 message (see Section 8). 2259 If the RERR is sent in response to an undeliverable IP packet or RREP 2260 message, it SHOULD be sent unicast to the next hop on the route to 2261 PktSource, or alternatively it MUST be multicast to LL-MANET-Routers. 2263 If the RERR is sent in response to a broken link, the RERR is, by 2264 default, multicast to LL-MANET-Routers. 2266 If the optional precursor lists feature (see Section 10.2) is 2267 enabled, the RERR is unicast to the precursors of the routes being 2268 reported. 2270 7.4.2. RERR Reception 2272 Upon receiving an RERR, an AODVv2 router performs the following 2273 steps: 2275 1. Verify that the message contains the required Data Elements: 2276 msg_hop_limit and at least one unreachable address 2278 * If not, ignore this RREP for further processing. 2280 2. For each address in the AddressList, check that: 2282 * The address is valid (routable and unicast) 2284 * The MetricType is supported and configured for use 2286 * There is a valid route with the same MetricType matching the 2287 address using longest prefix matching 2289 * Either the route's next hop is the sender of the RERR and 2290 route's next hop interface is the interface on which the RERR 2291 was received, or PktSource is present in the RERR and is a 2292 Router Client address 2294 * The unreachable address' sequence number is either unknown, or 2295 is greater than the route's sequence number 2297 If any of the above are false, the route does not need to be made 2298 Invalid and the unreachable address does not need to be 2299 advertised in a regenerated RERR. 2301 If all of the above are true: 2303 * If the route's prefix length is the same as the unreachable 2304 address' prefix length, set the route state to Invalid, and 2305 note that the route SHOULD be advertised in a regenerated 2306 RERR. 2308 * If the prefix length is shorter than the original route, the 2309 route MUST be expunged from the routing table, since it is a 2310 sub-route of the larger route which is reported to be Invalid. 2312 * If the prefix length is different, create a new route with the 2313 unreachable address, and its prefix and sequence number, set 2314 the state to Invalid, and note that the route SHOULD be 2315 advertised in a regenerated RERR. 2317 * Update the sequence number on the existing route, if the 2318 reported sequence number is determined to be newer using the 2319 comparison technique described in Section 4.4. 2321 3. If PktSource is included and is a Router Client, do not 2322 regenerate the RERR. 2324 4. Check if there are unreachable addresses which need to be 2325 advertised in a regenerated RERR 2327 * If so, regenerate the RERR as detailed in Section 7.4.3. 2329 * If not, take no further action. 2331 7.4.3. RERR Regeneration 2333 The RERR SHOULD NOT be generated if the limit for the rate of AODVv2 2334 control message generation has been reached. If approaching the 2335 limit, the message should be sent if the priorities in Section 6.5 2336 allow it. 2338 The procedure for RERR regeneration is as follows: 2340 1. Set msg_hop_limit := received msg_hop_limit - 1 2342 2. If msg_hop_limit is now zero, do not continue the regeneration 2343 process 2345 3. If the PktSource Data Element was included in the original RERR, 2346 copy it into the regenerated RERR 2348 4. For each route that needs to be reported, while respecting the 2349 interface MTU: 2351 * Insert the unreachable address into the AddressList. 2353 * Insert the prefix length into PrefixLengthList, if known and 2354 not equal to the address length. 2356 * Insert the sequence number into SeqNumList, if known. 2358 * Insert the MetricType into MetricTypeList. 2360 5. If interface MTU would be exceeded, create additional RERR 2361 messages 2363 The AODVv2 message is used to create a corresponding [RFC5444] 2364 message (see Section 8). If the RERR contains the PktSource Data 2365 Element, the regenerated RERR SHOULD be sent unicast to the next hop 2366 on the route to PktSource, or alternatively it MUST be multicast to 2367 LL-MANET-Routers. If the RERR is sent in response to a broken link, 2368 the RERR is, by default, multicast to LL-MANET-Routers. 2370 8. RFC 5444 Representation 2372 AODVv2 specifies that all control plane messages between routers 2373 SHOULD use the Generalized Mobile Ad Hoc Network Packet/Message 2374 Format [RFC5444], and therefore AODVv2's route messages comprise Data 2375 Elements that map to message elements in [RFC5444]. 2377 [RFC5444] provides a multiplexed transport for multiple protocols. 2378 An [RFC5444] multiplexer MAY choose to optimize the content of 2379 certain message elements to reduce control plane overhead. 2381 A brief summary of the [RFC5444] format: 2383 1. A packet contains zero or more messages 2384 2. A message contains a Message Header, one Message TLV Block, zero 2385 or more Address Blocks, and one Address Block TLV Block per 2386 Address Block 2388 3. The Message TLV Block MAY contain zero or more Message TLVs 2390 4. An Address Block TLV Block MAY include zero or more Address Block 2391 TLVs 2393 5. Each TLV value in an Address Block TLV Block can be associated 2394 with all of the addresses, or with a contiguous set of addresses, 2395 or with a single address in the Address Block 2397 AODVv2 does not require access to the [RFC5444] packet header. 2399 In the message header, AODVv2 uses , , 2400 and . The field 2401 indicates the length of any addresses in the message (using := (address length in octets - 1), i.e. 3 for IPv4 and 2403 15 for IPv6). 2405 Each address included in the Address Block is identified as OrigAddr, 2406 TargAddr, PktSource, or Unreachable Address by including an 2407 ADDRESS_TYPE TLV in the Address Block TLV Block. 2409 The addresses in an Address Block MAY appear in any order, and values 2410 in a TLV in the Address Block TLV Block must be associated with the 2411 correct address in the Address Block by the [RFC5444] implementation. 2412 To indicate which value is associated with each address, the AODVv2 2413 message representation uses lists where the order of the addresses in 2414 the AODVv2 AddressList Data Element matches the order of values in 2415 other list-based Data Elements, e.g., the order of SeqNums in the 2416 SeqNumList in an RERR. [RFC5444] maps this information to Address 2417 Block TLVs associated with the relevant addresses in the Address 2418 Block. 2420 The following sections show how AODVv2 Data Elements are represented 2421 in [RFC5444] messages. AODVv2 makes use of the VALIDITY_TIME TLV 2422 from [RFC5497], and defines (in Section 12) a number of new TLVs. 2424 Where the extension type of a TLV is set to zero, this is the default 2425 [RFC5444] value and the extension type will not be included in the 2426 message. 2428 8.1. Route Request Message Representation 2430 8.1.1. Message Header 2432 +---------------+-----------------+---------------------------------+ 2433 | Data Element | Header Field | Value | 2434 +---------------+-----------------+---------------------------------+ 2435 | None | | RREQ | 2436 | msg_hop_limit | | MAX_HOPCOUNT, reduced by number | 2437 | | | of hops traversed so far by the | 2438 | | | message. | 2439 | msg_hop_count | | Number of hops traversed so far | 2440 | | | by the message. | 2441 +---------------+-----------------+---------------------------------+ 2443 8.1.2. Message TLV Block 2445 An RREQ contains no Message TLVs. 2447 8.1.3. Address Block 2449 An RREQ contains two Addresses, OrigAddr and TargAddr, and each 2450 address has an associated prefix length. If the prefix length has 2451 not been included in the AODVv2 message, it is equal to the address 2452 length in bits. 2454 +-------------------------+------------------------------+ 2455 | Data Elements | Address Block | 2456 +-------------------------+------------------------------+ 2457 | OrigAddr/OrigPrefixLen |
+ | 2458 | TargAddr/TargPrefixLen |
+ | 2459 +-------------------------+------------------------------+ 2461 8.1.4. Address Block TLV Block 2463 Address Block TLVs are always associated with one or more addresses 2464 in the Address Block. The following sections show the TLVs that 2465 apply to each address. 2467 8.1.4.1. Address Block TLVs for OrigAddr 2468 +--------------+---------------+------------+-----------------------+ 2469 | Data Element | TLV Type | Extension | Value | 2470 | | | Type | | 2471 +--------------+---------------+------------+-----------------------+ 2472 | None | ADDRESS_TYPE | 0 | ADDRTYPE_ORIGADDR | 2473 | OrigSeqNum | SEQ_NUM | 0 | Sequence Number of | 2474 | | | | RREQ_Gen, the router | 2475 | | | | which initiated route | 2476 | | | | discovery. | 2477 | OrigMetric | PATH_METRIC | MetricType | Metric value for the | 2478 | /MetricType | | | route to OrigAddr, | 2479 | | | | using MetricType. | 2480 | ValidityTime | VALIDITY_TIME | 0 | ValidityTime for | 2481 | | | | route to OrigAddr. | 2482 +--------------+---------------+------------+-----------------------+ 2484 8.1.4.2. Address Block TLVs for TargAddr 2486 +------------+--------------+-------------+-------------------------+ 2487 | Data | TLV Type | Extension | Value | 2488 | Element | | Type | | 2489 +------------+--------------+-------------+-------------------------+ 2490 | None | ADDRESS_TYPE | 0 | ADDRTYPE_TARGADDR | 2491 | TargSeqNum | SEQ_NUM | 0 | The last known | 2492 | | | | TargSeqNum for | 2493 | | | | TargAddr. | 2494 +------------+--------------+-------------+-------------------------+ 2496 8.2. Route Reply Message Representation 2498 8.2.1. Message Header 2500 +---------------+-----------------+---------------------------------+ 2501 | Data Element | Header Field | Value | 2502 +---------------+-----------------+---------------------------------+ 2503 | None | | RREP | 2504 | msg_hop_limit | | from | 2505 | | | corresponding RREQ, reduced by | 2506 | | | number of hops traversed so far | 2507 | | | by the message. | 2508 | msg_hop_count | | Number of hops traversed so far | 2509 | | | by the message. | 2510 +---------------+-----------------+---------------------------------+ 2512 8.2.2. Message TLV Block 2514 An RREP contains no Message TLVs. 2516 8.2.3. Address Block 2518 An RREP contains a minimum of two Addresses, OrigAddr and TargAddr, 2519 and each address has an associated prefix length. If the prefix 2520 length has not been included in the AODVv2 message, it is equal to 2521 the address length in bits. 2523 It MAY also contain the address of the intended next hop, in order to 2524 request acknowledgement to confirm adjacency, as described in 2525 Section 6.2. The prefix length associated with this address is equal 2526 to the address length in bits. 2528 +-------------------------+------------------------------+ 2529 | Data Elements | Address Block | 2530 +-------------------------+------------------------------+ 2531 | OrigAddr/OrigPrefixLen |
+ | 2532 | TargAddr/TargPrefixLen |
+ | 2533 | AckReq |
+ | 2534 +-------------------------+------------------------------+ 2536 8.2.4. Address Block TLV Block 2538 Address Block TLVs are always associated with one or more addresses 2539 in the Address Block. The following sections show the TLVs that 2540 apply to each address. 2542 8.2.4.1. Address Block TLVs for OrigAddr 2544 +-------------+---------------+----------------+--------------------+ 2545 | Data | TLV Type | Extension Type | Value | 2546 | Element | | | | 2547 +-------------+---------------+----------------+--------------------+ 2548 | None | ADDRESS_TYPE | 0 | ADDRTYPE_ORIGADDR | 2549 +-------------+---------------+----------------+--------------------+ 2551 8.2.4.2. Address Block TLVs for TargAddr 2552 +--------------+---------------+------------+-----------------------+ 2553 | Data Element | TLV Type | Extension | Value | 2554 | | | Type | | 2555 +--------------+---------------+------------+-----------------------+ 2556 | None | ADDRESS_TYPE | 0 | ADDRTYPE_TARGADDR | 2557 | TargSeqNum | SEQ_NUM | 0 | Sequence number of | 2558 | | | | RREP_Gen, the router | 2559 | | | | which created the | 2560 | | | | RREP. | 2561 | TargMetric | PATH_METRIC | MetricType | Metric value for the | 2562 | /MetricType | | | route to TargAddr, | 2563 | | | | using MetricType. | 2564 | ValidityTime | VALIDITY_TIME | 0 | ValidityTime for | 2565 | | | | route to TargAddr. | 2566 +--------------+---------------+------------+-----------------------+ 2568 8.2.4.3. Address Block TLVs for AckReq Intended Recipient Address 2570 +--------------+---------------+-----------------+------------------+ 2571 | Data Element | TLV Type | Extension Type | Value | 2572 +--------------+---------------+-----------------+------------------+ 2573 | None | ADDRESS_TYPE | 0 | ADDRTYPE_INTEND | 2574 +--------------+---------------+-----------------+------------------+ 2576 8.3. Route Reply Acknowledgement Message Representation 2578 8.3.1. Message Header 2580 +---------------+---------------+-----------+ 2581 | Data Element | Header Field | Value | 2582 +---------------+---------------+-----------+ 2583 | None | | RREP_Ack | 2584 +---------------+---------------+-----------+ 2586 8.3.2. Message TLV Block 2588 An RREP_Ack contains no Message TLVs. 2590 8.3.3. Address Block 2592 An RREP_Ack contains no Address Block. 2594 8.3.4. Address Block TLV Block 2596 An RREP_Ack contains no Address Block TLV Block. 2598 8.4. Route Error Message Representation 2600 8.4.1. Message Header 2602 +---------------+-----------------+---------------------------------+ 2603 | Data Element | Header Field | Value | 2604 +---------------+-----------------+---------------------------------+ 2605 | None | | RERR | 2606 | msg_hop_limit | | MAX_HOPCOUNT, reduced by number | 2607 | | | of hops traversed so far by the | 2608 | | | message. | 2609 +---------------+-----------------+---------------------------------+ 2611 8.4.2. Message TLV Block 2613 An RERR contains no Message TLVs. 2615 8.4.3. Address Block 2617 The Address Block in an RERR MAY contain PktSource, the source 2618 address of the IP packet triggering RERR generation, as detailed in 2619 Section 7.4. Prefix Length associated with PktSource is equal to the 2620 address length in bits. 2622 Address Block always contains one Address per route that is no longer 2623 valid, and each address has an associated prefix length. If a prefix 2624 length has not been included for this address, it is equal to the 2625 address length in bits. 2627 +------------------------------+------------------------------------+ 2628 | Data Element | Address Block | 2629 +------------------------------+------------------------------------+ 2630 | PktSource |
+ for | 2631 | | PktSource | 2632 | AddressList/PrefixLengthList |
+ for | 2633 | | each unreachable address in | 2634 | | AddressList | 2635 +------------------------------+------------------------------------+ 2637 8.4.4. Address Block TLV Block 2639 Address Block TLVs are always associated with one or more addresses 2640 in the Address Block. The following sections show the TLVs that 2641 apply to each type of address in the RERR. 2643 8.4.4.1. Address Block TLVs for PktSource 2645 +--------------+---------------+---------------+--------------------+ 2646 | Data Element | TLV Type | Extension | Value | 2647 | | | Type | | 2648 +--------------+---------------+---------------+--------------------+ 2649 | PktSource | ADDRESS_TYPE | 0 | ADDRTYPE_PKTSOURCE | 2650 +--------------+---------------+---------------+--------------------+ 2652 8.4.4.2. Address Block TLVs for Unreachable Addresses 2654 +----------------+--------------+------------+----------------------+ 2655 | Data Element | TLV Type | Extension | Value | 2656 | | | Type | | 2657 +----------------+--------------+------------+----------------------+ 2658 | None | ADDRESS_TYPE | 0 | ADDRTYPE_UNREACHABLE | 2659 | SeqNumList | SEQ_NUM | 0 | Sequence Number | 2660 | | | | associated with | 2661 | | | | invalid route to the | 2662 | | | | unreachable address. | 2663 | MetricTypeList | PATH_METRIC | MetricType | None. Extension Type | 2664 | | | | set to MetricType of | 2665 | | | | the route to the | 2666 | | | | unreachable address. | 2667 +----------------+--------------+------------+----------------------+ 2669 9. Simple External Network Attachment 2671 Figure 4 shows a stub (i.e., non-transit) network of AODVv2 routers 2672 which is attached to an external network via a single External 2673 Network Access Router (ENAR). The interface to the external network 2674 MUST NOT be configured in the AODVv2_INTERFACES list. 2676 As in any externally-attached network, AODVv2 routers and Router 2677 Clients that wish to be reachable from hosts on the external network 2678 MUST have IP addresses within the ENAR's routable and topologically 2679 correct prefix (i.e., 191.0.2.0/24 in Figure 4). This AODVv2 network 2680 and subnets within it will be advertised to the external network 2681 using procedures which are out of scope for this specification. 2683 /-------------------------\ 2684 / +----------------+ \ 2685 / | AODVv2 Router | \ 2686 | | 191.0.2.2/32 | | 2687 | +----------------+ | Routable 2688 | +-----+--------+ Prefix 2689 | | ENAR | /191.0.2.0/24 2690 | | AODVv2 Router| / 2691 | | 191.0.2.1 |/ /---------------\ 2692 | | serving net +------+ External \ 2693 | | 191.0.2.0/24 | \ Network / 2694 | +-----+--------+ \---------------/ 2695 | +----------------+ | 2696 | | AODVv2 Router | | 2697 | | 191.0.2.3/32 | | 2698 \ +----------------+ / 2699 \ / 2700 \-------------------------/ 2702 Figure 4: Simple External Network Attachment Example 2704 When an AODVv2 router within the AODVv2 MANET wants to discover a 2705 route toward an address on the external network, it uses the normal 2706 AODVv2 route discovery for that IP Destination Address. The ENAR 2707 MUST respond to RREQ on behalf of all external network destinations, 2708 i.e., destinations not on the configured 191.0.2.0/24 subnet. RREQs 2709 for addresses inside the AODVv2 network, i.e. destinations on the 2710 configured 191.0.2.0/24 subnet, are handled using the standard 2711 processes described in Section 7. 2713 When an IP packet from an address on the external network destined 2714 for an address in the AODVv2 MANET reaches the ENAR, if the ENAR does 2715 not have a route toward that exact destination it will perform normal 2716 AODVv2 route discovery for that destination. 2718 Configuring the ENAR as a default router is outside the scope of this 2719 specification. 2721 10. Optional Features 2723 A number of optional features for AODVv2, associated initially with 2724 AODV, MAY be useful in networks with greater mobility or larger node 2725 populations, or networks requiring reduced latency for application 2726 launches. These features are not required by minimal 2727 implementations. 2729 10.1. Expanding Rings Multicast 2731 For multicast RREQ, msg_hop_limit MAY be set in accordance with an 2732 expanding ring search as described in [RFC3561] to limit the RREQ 2733 propagation to a subset of the local network and possibly reduce 2734 route discovery overhead. 2736 10.2. Precursor Lists 2738 This section specifies an interoperable enhancement to AODVv2 2739 enabling more economical RERR notifications. 2741 There can be several sources of traffic for a certain destination. 2742 Each source of traffic and each upstream router between the 2743 forwarding AODVv2 router and the traffic source is known as a 2744 "precursor" for the destination. For each destination, an AODVv2 2745 router MAY choose to keep track of precursors that have provided 2746 traffic for that destination. Route Error messages about that 2747 destination can be sent unicast to these precursors instead of 2748 multicast to all AODVv2 routers. 2750 Since an RERR will be regenerated if it comes from a next hop on a 2751 valid route, the RERR SHOULD ideally be sent backwards along the 2752 route that the source of the traffic uses, to ensure it is 2753 regenerated at each hop and reaches the traffic source. If the 2754 reverse path is unknown, the RERR SHOULD be sent toward the source 2755 along some other route. Therefore, the options for saving precursor 2756 information are as follows: 2758 o Save the next hop on an existing route to the IP packet's source 2759 address as the precursor. In this case, it is not guaranteed that 2760 an RERR that is sent will follow the reverse of the source's 2761 route. In rare situations, this may prevent the route from being 2762 invalidated at the source of the data traffic. 2764 o Save the IP packet's source address as the precursor. In this 2765 case, the RERR can be sent along any existing route to the source 2766 of the data traffic, and SHOULD include the PktSource Data Element 2767 to ensure that the route will be invalidated at the source of the 2768 traffic, in case the RERR does not follow the reverse of the 2769 source's route. 2771 o By inspecting the MAC address of each forwarded IP packet, 2772 determine which router forwarded the packet, and save the router 2773 address as a precursor. This ensures that when an RERR is sent to 2774 the precursor router, the route will be invalidated at that 2775 router, and the RERR will be regenerated toward the source of the 2776 IP packet. 2778 During normal operation, each AODVv2 router maintaining precursor 2779 lists for a route must update the precursor list whenever it uses 2780 this route to forward traffic to the destination. Precursors are 2781 classified as Active if traffic has recently been forwarded by the 2782 precursor. The precursor is marked with a timestamp to indicate the 2783 time it last forwarded traffic on this route. 2785 When an AODVv2 router detects that one or more routes are broken, it 2786 MAY notify each Active precursor using a unicast Route Error message 2787 instead of creating multicast traffic. Unicast is applicable when 2788 there are few Active precursors compared to the number of neighboring 2789 AODVv2 routers. However, the default multicast behavior is still 2790 preferable when there are many precursors, since fewer message 2791 transmissions are required. 2793 When an AODVv2 router supporting precursor lists receives an RERR 2794 message, it MAY identify the list of its own affected Active 2795 precursors for the routes in the RERR, and choose to send a unicast 2796 RERR to those, rather than send a multicast RERR. 2798 When a route is expunged, any precursor list associated with it must 2799 also be expunged. 2801 10.3. Intermediate RREP 2803 Without iRREP, only the AODVv2 router responsible for the target 2804 address can respond to an RREQ. Using iRREP, route discoveries can 2805 be faster and create less control traffic. This specification has 2806 been published as a separate Internet Draft [I-D.perkins-irrep]. 2808 10.4. Message Aggregation Delay 2810 The aggregation of multiple messages into a packet is specified in 2811 [RFC5444]. 2813 Implementations MAY choose to briefly delay transmission of messages 2814 for the purpose of aggregation (into a single packet) or to improve 2815 performance by using jitter [RFC5148]. 2817 11. Configuration 2819 AODVv2 uses various parameters which can be grouped into the 2820 following categories: 2822 o Timers 2824 o Protocol constants 2825 o Administrative parameters and controls 2827 This section show the parameters along with their definitions and 2828 default values (if any). 2830 Note that several fields have limited size (bits or bytes). These 2831 sizes and their encoding may place specific limitations on the values 2832 that can be set. 2834 11.1. Timers 2836 AODVv2 requires certain timing information to be associated with 2837 route table entries and message replies. The default values are as 2838 follows: 2840 +------------------------+----------------+ 2841 | Name | Default Value | 2842 +------------------------+----------------+ 2843 | ACTIVE_INTERVAL | 5 second | 2844 | MAX_IDLETIME | 200 seconds | 2845 | MAX_BLACKLIST_TIME | 200 seconds | 2846 | MAX_SEQNUM_LIFETIME | 300 seconds | 2847 | RteMsg_ENTRY_TIME | 12 seconds | 2848 | RREQ_WAIT_TIME | 2 seconds | 2849 | RREP_Ack_SENT_TIMEOUT | 1 second | 2850 | RREQ_HOLDDOWN_TIME | 10 seconds | 2851 +------------------------+----------------+ 2853 Table 2: Timing Parameter Values 2855 The above timing parameter values have worked well for small and 2856 medium well-connected networks with moderate topology changes. The 2857 timing parameters SHOULD be administratively configurable. Ideally, 2858 for networks with frequent topology changes the AODVv2 parameters 2859 SHOULD be adjusted using experimentally determined values or dynamic 2860 adaptation. For example, in networks with infrequent topology 2861 changes MAX_IDLETIME MAY be set to a much larger value. 2863 If MAX_SEQNUM_LIFETIME was configured differently across the network, 2864 and any of the routers lost their sequence number or rebooted, this 2865 could result in their next route messages being classified as stale 2866 at any AODVv2 router using a greater value for MAX_SEQNUM_LIFETIME. 2867 This would delay route discovery from and to the re-initializing 2868 router. 2870 11.2. Protocol Constants 2872 AODVv2 protocol constants typically do not require changes. The 2873 following table lists these constants, along with their values and a 2874 reference to the section describing their use. 2876 +------------------------+---------+--------------------------------+ 2877 | Name | Default | Description | 2878 +------------------------+---------+--------------------------------+ 2879 | DISCOVERY_ATTEMPTS_MAX | 3 | Section 6.6 | 2880 | RREP_RETRIES | 2 | Section 7.2.1 | 2881 | MAX_METRIC[MetricType] | [TBD] | Section 5 | 2882 | MAX_METRIC[HopCount] | 20 hops | Section 5 and Section 7 | 2883 | MAX_HOPCOUNT | 20 | Same as MAX_METRIC[HopCount] | 2884 | INFINITY_TIME | [TBD] | Maximum expressible clock time | 2885 | | | (Section 6.7.2) | 2886 +------------------------+---------+--------------------------------+ 2888 Table 3: AODVv2 Constants 2890 Note that is an 8-bit field in the [RFC5444] message 2891 header and therefore MAX_HOPCOUNT cannot be larger than 255. 2893 MAX_METRIC[MetricType] MUST always be the maximum expressible metric 2894 value of type MetricType. Field lengths associated with metric 2895 values are found in Section 11.6. 2897 These protocol constants MUST have the same values for all AODVv2 2898 routers in the ad hoc network. If the values were configured 2899 differently, the following consequences may be observed: 2901 o DISCOVERY_ATTEMPTS_MAX: Routers with higher values are likely to 2902 be more successful at finding routes, at the cost of additional 2903 control traffic. 2905 o RREP_RETRIES: Routers with lower values are more likely to 2906 blacklist neighbors when there is a 2908 o MAX_METRIC[MetricType]: No interoperability problems due to 2909 variations on different routers, but routers with lower values may 2910 exhibit overly restrictive behavior during route comparisons. 2911 temporary fluctuation in link quality. 2913 o MAX_HOPCOUNT: Routers with a value too small would not be able to 2914 discover routes to distant addresses. 2916 o INFINITY_TIME: No interoperability problems due to variations on 2917 different routers, but if a lower value is used, route state 2918 management may exhibit overly restrictive behavior. 2920 11.3. Local Settings 2922 The following table lists AODVv2 parameters which SHOULD be 2923 administratively configured for each router: 2925 +------------------------+------------------------+--------------+ 2926 | Name | Default Value | Description | 2927 +------------------------+------------------------+--------------+ 2928 | AODVv2_INTERFACES | | Section 3 | 2929 | BUFFER_SIZE_PACKETS | 2 | Section 6.6 | 2930 | BUFFER_SIZE_BYTES | MAX_PACKET_SIZE [TBD] | Section 6.6 | 2931 | CONTROL_TRAFFIC_LIMIT | [TBD - 50 pkts/sec?] | Section 7 | 2932 +------------------------+------------------------+--------------+ 2934 Table 4: Configuration for Local Settings 2936 11.4. Network-Wide Settings 2938 The following administrative controls MAY be used to change the 2939 operation of the network. The same settings SHOULD be used across 2940 the network. Inconsistent settings at different routers in the 2941 network will not result in protocol errors, but poor performance may 2942 result. 2944 +----------------------+-----------+----------------+ 2945 | Name | Default | Description | 2946 +----------------------+-----------+----------------+ 2947 | ENABLE_IDLE_IN_RERR | Disabled | Section 7.4.1 | 2948 +----------------------+-----------+----------------+ 2950 Table 5: Configuration for Network-Wide Settings 2952 11.5. Optional Feature Settings 2954 These options are not required for correct routing behavior, although 2955 they may reduce AODVv2 protocol overhead in certain situations. The 2956 default behavior is to leave these options disabled. 2958 +---------------------------+-----------+---------------------------+ 2959 | Name | Default | Description | 2960 +---------------------------+-----------+---------------------------+ 2961 | PRECURSOR_LISTS | Disabled | Local (Section 10.2) | 2962 | MSG_AGGREGATION | Disabled | Local (Section 10.4) | 2963 | ENABLE_IRREP | Disabled | Network-wide (Section | 2964 | | | 10.3) | 2965 | EXPANDING_RINGS_MULTICAST | Disabled | Network-wide (Section | 2966 | | | 10.1) | 2967 +---------------------------+-----------+---------------------------+ 2969 Table 6: Configuration for Optional Features 2971 11.6. MetricType Allocation 2973 The metric types used by AODVv2 are identified according to the 2974 assignments in [RFC6551]. All implementations MUST use these values. 2976 +---------------------+----------+--------------------+ 2977 | Name of MetricType | Type | Metric Value Size | 2978 +---------------------+----------+--------------------+ 2979 | Unassigned | 0 | Undefined | 2980 | Hop Count | 3 [TBD] | 1 octet | 2981 | Unallocated | 9 - 254 | TBD | 2982 | Reserved | 255 | Undefined | 2983 +---------------------+----------+--------------------+ 2985 Table 7: AODVv2 Metric Types 2987 11.7. AddressType Allocation 2989 These values are used in the [RFC5444] Address Type TLV discussed in 2990 Section 8. All implementations MUST use these values. 2992 +-----------------------+--------+ 2993 | Address Type | Value | 2994 +-----------------------+--------+ 2995 | ADDRTYPE_ORIGADDR | 0 | 2996 | ADDRTYPE_TARGADDR | 1 | 2997 | ADDRTYPE_UNREACHABLE | 2 | 2998 | ADDRTYPE_PKTSOURCE | 3 | 2999 | ADDRTYPE_INTEND | 4 | 3000 | ADDRTYPE_UNSPECIFIED | 255 | 3001 +-----------------------+--------+ 3003 Table 8: AODVv2 Address Types 3005 12. IANA Considerations 3007 This section specifies several [RFC5444] message types and address 3008 tlv-types required for AODVv2. A registry of metric types is 3009 specified, in addition to a registry of address types. 3011 12.1. RFC 5444 Message Types 3013 This specification defines four Message Types, to be allocated from 3014 the 0-223 range of the "Message Types" namespace defined in 3015 [RFC5444], as specified in Table 9. 3017 +-----------------------------------------+-----------+ 3018 | Name of Message | Type | 3019 +-----------------------------------------+-----------+ 3020 | Route Request (RREQ) | 10 (TBD) | 3021 | Route Reply (RREP) | 11 (TBD) | 3022 | Route Error (RERR) | 12 (TBD) | 3023 | Route Reply Acknowledgement (RREP_Ack) | 13 (TBD) | 3024 +-----------------------------------------+-----------+ 3026 Table 9: AODVv2 Message Types 3028 12.2. RFC 5444 Address Block TLV Types 3030 This specification defines three Address Block TLV Types, to be 3031 allocated from the "Address Block TLV Types" namespace defined in 3032 [RFC5444], as specified in Table 10. 3034 +------------------------+----------+---------------+---------------+ 3035 | Name of TLV | Type | Length | Reference | 3036 | | | (octets) | | 3037 +------------------------+----------+---------------+---------------+ 3038 | PATH_METRIC | 10 (TBD) | depends on | Section 7 | 3039 | | | MetricType | | 3040 | SEQ_NUM | 11 (TBD) | 2 | Section 7 | 3041 | ADDRESS_TYPE | 15 (TBD) | 1 | Section 8 | 3042 +------------------------+----------+---------------+---------------+ 3044 Table 10: AODVv2 Address Block TLV Types 3046 13. Security Considerations 3048 This section describes various security considerations and potential 3049 avenues to secure AODVv2 routing. The objective of the AODVv2 3050 protocol is for each router to communicate reachability information 3051 about addresses for which it is responsible, and for routes it has 3052 learned from other AODVv2 routers. Positive routing information 3053 (i.e. a route exists) is distributed via RREQ and RREP messages. 3054 AODVv2 routers store the information contained in these messages in 3055 order to properly forward IP packets, and they generally provide this 3056 information to other AODVv2 routers. Negative routing information 3057 (i.e. a route does not exist) is distributed via RERR messages. 3058 AODVv2 routers process these messages and remove routes, and forward 3059 this information to other AODVv2 routers. 3061 Networks using AODVv2 to maintain connectivity and establish routes 3062 on demand may be vulnerable to certain well-known types of threats. 3063 Flooding attacks using RREQ amount to a denial of service for route 3064 discovery. Valid route table entries can be replaced by maliciously 3065 constructed RREQ and RREP messages. Links could be erroneously 3066 treated as bidirectional if malicious unsolicited RREP or RREP_Ack 3067 messages were to be accepted. Replay attacks using RERR messages 3068 could, in some circumstances, be used to disrupt active routes. 3069 Passive inspection of AODVv2 control messages could enable 3070 unauthorized devices to gain information about the network topology, 3071 since exchanging such information is the main purpose of AODVv2. 3073 The on-demand nature of AODVv2 route discovery reduces the 3074 vulnerability to route disruption. Since control traffic for 3075 updating route tables is diminished, there is less opportunity for 3076 failure. Processing requirements for AODVv2 are typically quite 3077 small, and would typically be dominated by calculations to verify 3078 integrity. This has the effect of reducing (but by no means 3079 eliminating) AODVv2's vulnerability to denial of service attacks. 3081 Encryption MAY be used for AODVv2 messages. If the routers share a 3082 packet-level security association, the message data can be encrypted 3083 prior to message transmission. The establishment of such security 3084 associations is outside the scope of this specification. Encryption 3085 will not only protect against unauthorized devices obtaining 3086 information about network topology but will ensure that only trusted 3087 routers participate in routing operations. 3089 Message integrity checking is enabled by the Integrity Check Value 3090 mechanisms defined in [RFC7182]. The data contained in AODVv2 3091 routing protocol messages SHOULD be verified using ICV values, to 3092 avoid the use of message data if the message has been tampered with 3093 or replayed. Otherwise, it would be possible to disrupt 3094 communications by injecting nonexistent or malicious routes into the 3095 route tables of routers within the ad hoc network. This can result 3096 in loss of data or message processing by unauthorized devices. 3098 The remainder of this section provides specific recommendations for 3099 the use of the integrity checking and timestamp functions defined in 3100 [RFC7182] to ensure the integrity of each AODVv2 message. The 3101 calculation used for the Integrity Check Value will depend on the 3102 message type. Sequence numbers can be used as timestamps to protect 3103 against replay, since they are known to be strictly increasing. 3105 RREQ messages advertise a route to OrigAddr, and impose very little 3106 processing requirement for receivers. The main threat presented by 3107 sending an RREQ message with false information is that traffic to 3108 OrigAddr could be disrupted. Since RREQ is multicast and likely to 3109 be received by all routers in the ad hoc network, this threat could 3110 have serious impact on applications communicating by way of OrigAddr. 3111 The actual threat to disrupt routes to OrigAddr is reduced by the 3112 AODVv2 mechanism of marking RREQ-derived routes as "Unconfirmed" 3113 until adjacency with the next hop is confirmed. If AODVv2 routers 3114 always verify the integrity of the RREQ message data, then the threat 3115 of disruption is minimized. The ICV mechanisms offered in [RFC7182] 3116 are sufficient for this purpose. Since OrigAddr is included as a 3117 Data Element of the RREQ, the ICV can be calculated and verified 3118 using message contents. The ICV SHOULD be verified at every step 3119 along the dispersal path of the RREQ to mitigate the threat. Since 3120 RREQ_Gen's sequence number is incremented for each new RREQ, replay 3121 protection is already afforded and no extra timestamp mechanism is 3122 required. 3124 RREP messages advertise a route to TargAddr, and impose very little 3125 processing requirement for receivers. The main threat presented by 3126 sending an RREP message with false information is that traffic to 3127 TargAddr could be disrupted. Since RREP is unicast, this threat is 3128 restricted to receivers along the path from OrigAddr to TargAddr. If 3129 AODVv2 routers always verify the integrity of the RREP message data, 3130 then this threat is minimized. This facility is offered by the ICV 3131 mechanisms in [RFC7182]. Since TargAddr is included as a Data 3132 Element of the RREP, the ICV can be calculated and verified using 3133 message contents. The ICV SHOULD be verified at every step along the 3134 unicast path of the RREP. Since RREP_Gen's sequence number is 3135 incremented for each new RREP, replay protection is afforded and no 3136 extra timestamp mechanism is required. 3138 RREP_Ack messages are intended to verify bidirectional neighbor 3139 connectivity, and impose very little processing requirement for 3140 receivers. The main threat presented by sending an RREP_Ack message 3141 with false information is that the route advertised to a target 3142 address in an RREP might be erroneously accepted even though the 3143 route would contain a unidirectional link and thus not be suitable 3144 for most traffic. Since RREP_Ack is unicast, this threat is strictly 3145 local to the RREP transmitter expecting the acknowledgement. A 3146 malicious router could also attempt to send an unsolicited RREP_Ack 3147 to convince another router that a bidirectional link exists and 3148 subsequently use further messages to divert traffic along a route 3149 which is not valid. If AODVv2 routers always verify the integrity of 3150 the RREP_Ack message data, then this threat is minimized. This 3151 facility is offered by the ICV mechanisms in [RFC7182]. The RREP_Gen 3152 SHOULD use the source IP address of the RREP_Ack to identify the 3153 sender, and so the ICV SHOULD be calculated using the message 3154 contents and the IP source address. The message must also include 3155 the Timestamp defined in [RFC7182] to protect against replay attacks, 3156 using TargSeqNum from the RREP as the value in the TIMESTAMP TLV. 3158 RERR messages remove routes, and impose very little processing 3159 requirement for receivers. The main threat presented by sending an 3160 RERR message with false information is that traffic to the advertised 3161 destinations could be disrupted. Since RERR is multicast and can be 3162 received by many routers in the ad hoc network, this threat could 3163 have serious impact on applications communicating by way of the 3164 sender of the RERR message. However, since the sender of the RERR 3165 message with erroneous information MAY be presumed to be either 3166 malicious or broken, it is better that such routes not be used 3167 anyway. Another threat is that a malicious RERR message MAY be sent 3168 with a PktSource Data Element included, to disrupt PktSource's 3169 ability to send to the addresses contained in the RERR. If AODVv2 3170 routers always verify the integrity of the RERR message data, then 3171 this threat is reduced. This facility is offered by the ICV 3172 mechanisms in [RFC7182]. The receiver of the RERR SHOULD use the 3173 source IP address of the RERR to identify the sender. The message 3174 must also include the Timestamp defined in [RFC7182] to protect 3175 against replay attacks, using SeqNum from RERR_Gen as the value in 3176 the TIMESTAMP TLV. 3178 14. Acknowledgments 3180 AODVv2 is a descendant of the design of previous MANET on-demand 3181 protocols, especially AODV [RFC3561] and DSR [RFC4728]. Changes to 3182 previous MANET on-demand protocols stem from research and 3183 implementation experiences. Thanks to Elizabeth Belding and Ian 3184 Chakeres for their long time authorship of AODV. Additional thanks 3185 to Derek Atkins, Emmanuel Baccelli, Abdussalam Baryun, Ramon Caceres, 3186 Thomas Clausen, Justin Dean, Christopher Dearlove, Ulrich Herberg, 3187 Henner Jakob, Luke Klein-Berndt, Lars Kristensen, Tronje Krop, 3188 Koojana Kuladinithi, Kedar Namjoshi, Keyur Patel, Alexandru Petrescu, 3189 Henning Rogge, Fransisco Ros, Pedro Ruiz, Christoph Sommer, Romain 3190 Thouvenin, Richard Trefler, Jiazi Yi, Seung Yi, and Cong Yuan, for 3191 their reviews of AODVv2 and DYMO, as well as numerous specification 3192 suggestions. 3194 15. References 3196 15.1. Normative References 3198 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3199 Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ 3200 RFC2119, March 1997, 3201 . 3203 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 3204 Demand Distance Vector (AODV) Routing", RFC 3561, DOI 3205 10.17487/RFC3561, July 2003, 3206 . 3208 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 3209 Architecture", RFC 4291, DOI 10.17487/RFC4291, February 3210 2006, . 3212 [RFC5082] Gill, V., Heasley, J., Meyer, D., Savola, P., Ed., and C. 3213 Pignataro, "The Generalized TTL Security Mechanism 3214 (GTSM)", RFC 5082, DOI 10.17487/RFC5082, October 2007, 3215 . 3217 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 3218 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 3219 Format", RFC 5444, DOI 10.17487/RFC5444, February 2009, 3220 . 3222 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 3223 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, DOI 3224 10.17487/RFC5497, March 2009, 3225 . 3227 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc Network 3228 (MANET) Protocols", RFC 5498, DOI 10.17487/RFC5498, March 3229 2009, . 3231 [RFC6551] Vasseur, JP., Ed., Kim, M., Ed., Pister, K., Dejean, N., 3232 and D. Barthel, "Routing Metrics Used for Path Calculation 3233 in Low-Power and Lossy Networks", RFC 6551, DOI 10.17487/ 3234 RFC6551, March 2012, 3235 . 3237 [RFC7182] Herberg, U., Clausen, T., and C. Dearlove, "Integrity 3238 Check Value and Timestamp TLV Definitions for Mobile Ad 3239 Hoc Networks (MANETs)", RFC 7182, DOI 10.17487/RFC7182, 3240 April 2014, . 3242 15.2. Informative References 3244 [I-D.perkins-irrep] 3245 Perkins, C., "Intermediate RREP for dynamic MANET On- 3246 demand (AODVv2) Routing", draft-perkins-irrep-03 (work in 3247 progress), May 2015. 3249 [Perkins94] 3250 Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 3251 Sequenced Distance-Vector Routing (DSDV) for Mobile 3252 Computers", Proceedings of the ACM SIGCOMM '94 Conference 3253 on Communications Architectures, Protocols and 3254 Applications, London, UK, pp. 234-244, August 1994. 3256 [Perkins99] 3257 Perkins, C. and E. Royer, "Ad hoc On-Demand Distance 3258 Vector (AODV) Routing", Proceedings of the 2nd IEEE 3259 Workshop on Mobile Computing Systems and Applications, New 3260 Orleans, LA, pp. 90-100, February 1999. 3262 [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking 3263 (MANET): Routing Protocol Performance Issues and 3264 Evaluation Considerations", RFC 2501, DOI 10.17487/ 3265 RFC2501, January 1999, 3266 . 3268 [RFC4193] Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast 3269 Addresses", RFC 4193, DOI 10.17487/RFC4193, October 2005, 3270 . 3272 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 3273 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 3274 IPv4", RFC 4728, DOI 10.17487/RFC4728, February 2007, 3275 . 3277 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 3278 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 3279 DOI 10.17487/RFC4861, September 2007, 3280 . 3282 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 3283 Considerations in Mobile Ad Hoc Networks (MANETs)", RFC 3284 5148, DOI 10.17487/RFC5148, February 2008, 3285 . 3287 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 3288 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 3289 RFC 6130, DOI 10.17487/RFC6130, April 2011, 3290 . 3292 [RFC6621] Macker, J., Ed., "Simplified Multicast Forwarding", RFC 3293 6621, DOI 10.17487/RFC6621, May 2012, 3294 . 3296 [Sholander02] 3297 Sholander, P., Coccoli, P., Oakes, T., and S. Swank, "A 3298 Portable Software Implementation of a Hybrid MANET Routing 3299 Protocol", 2002. 3301 Appendix A. Multi-homing Considerations 3303 Multi-homing is not supported by the AODVv2 specification. A Router 3304 Client, i.e., an IP Address, can only be served by one AODVv2 router 3305 at any time. The coordination between multiple AODVv2 routers to 3306 distribute routing information correctly for a shared address is not 3307 defined. See Appendix B for information about how to move a router 3308 client to a different AODVv2 router. 3310 Previous work indicates that it can be supported by expanding the 3311 sequence number to include the AODVv2 router's IP address as a 3312 parsable field of the SeqNum. Without this, comparing sequence 3313 numbers would not work to evaluate freshness. Even when the IP 3314 address is included, there is no good way to compare sequence numbers 3315 from different IP addresses, but a handling node can determine 3316 whether the two given sequence numbers are comparable. If the route 3317 table can store multiple routes for the same destination, then multi- 3318 homing can work with sequence numbers augmented by IP addresses. 3320 This non-normative information is provided simply to document the 3321 results of previous efforts to enable multi-homing. The intention is 3322 to simplify the task of future specification if multihoming becomes 3323 necessary for reactive protocol operation. 3325 Appendix B. Router Client Relocation 3327 Only one AODVv2 router within a MANET SHOULD be responsible for a 3328 particular address at any time. If two AODVv2 routers dynamically 3329 shift the advertisement of a network prefix, correct AODVv2 routing 3330 behavior must be observed. The AODVv2 router adding the new network 3331 prefix must wait for any existing routing information about this 3332 network prefix to be purged from the network, i.e., it must wait at 3333 least MAX_SEQNUM_LIFETIME after the previous AODVv2 router's last 3334 SeqNum update for this network prefix. 3336 Appendix C. Example Algorithms for AODVv2 Operations 3338 The following subsections show example algorithms for protocol 3339 operations required by AODVv2. AODVv2 requires general algorithms 3340 for manipulating and comparing table entries, and algorithms specific 3341 to each message type, and sometimes values and algorithms specific to 3342 each metric type. 3344 The following table indicates the field names used in subsequent 3345 sections and their meaning. 3347 +-------------------------+-----------------------------------------+ 3348 | Parameter | Description | 3349 +-------------------------+-----------------------------------------+ 3350 | RteMsg | A route message | 3351 | | (inRREQ/outRREQ/inRREP/outRREP) | 3352 | RteMsg.HopLimit | Hop limit for the message | 3353 | RteMsg.HopCount | Hop count for the message | 3354 | RteMsg.AckReq | True/False, optional in RREP | 3355 | RteMsg.MetricType | The type of metric included, optional | 3356 | RteMsg.OrigAddr | Address of source of queued data | 3357 | RteMsg.TargAddr | Address route is requested for | 3358 | RteMsg.OrigPrefixLen | Prefix length of OrigAddr, optional | 3359 | RteMsg.TargPrefixLen | Prefix length of TargAddr, optional | 3360 | RteMsg.OrigSeqNum | SeqNum of OrigAddr, in RREQ only | 3361 | RteMsg.TargSeqNum | SeqNum of TargAddr, in RREP, optional | 3362 | | in RREQ | 3363 | RteMsg.OrigMetric | Metric to OrigAddr, in RREQ only | 3364 | RteMsg.TargMetric | Metric to TargAddr, in RREP only | 3365 | RteMsg.ValidityTime | Time limit for route advertised | 3366 | RteMsg.NbrIP | Sender of the RteMsg | 3367 | RteMsg.Netif | Interface on which the RteMsg arrived | 3368 | AdvRte | Derived from a RteMsg (see Section 6.7) | 3369 | AdvRte.Address | Route destination address | 3370 | AdvRte.PrefixLength | Route destination prefix length | 3371 | AdvRte.SeqNum | SeqNum associated with route | 3372 | AdvRte.MetricType | MetricType associated with route | 3373 | AdvRte.Metric | Advertised metric of route | 3374 | AdvRte.Cost | Cost from receiving router | 3375 | AdvRte.ValidityTime | Time limit for route advertised | 3376 | AdvRte.NextHopIP | Sender of the RteMsg | 3377 | AdvRte.NextHopIntf | Interface on which the RteMsg arrived | 3378 | AdvRte.HopCount | Number of hops traversed | 3379 | AdvRte.HopLimit | Allowed number of hops remaining | 3380 | Route | A route table entry (see Section 4.6) | 3381 | Route.Address | Route destination address | 3382 | Route.PrefixLength | Route destination prefix length | 3383 | Route.SeqNum | SeqNum associated with route | 3384 | Route.NextHop | Address of router which advertised the | 3385 | | route | 3386 | Route.NextHopInterface | Interface on which next hop is | 3387 | | reachable | 3388 | Route.LastUsed | Time this route was last used for | 3389 | | packet forwarding | 3390 | Route.LastSeqNumUpdate | Time the SeqNum of the route was last | 3391 | | updated | 3392 | Route.ExpirationTime | Time at which the route will expire | 3393 | Route.MetricType | MetricType associated with route | 3394 | Route.Metric | Cost from receiving router | 3395 | Route.State | Active/Idle/Invalid | 3396 | Route.Precursors | Optional (see Section 10.2) | 3397 | RERR | Route Error message (inRERR/outRERR) | 3398 | RERR.HopLimit | Hop limit for the message | 3399 | RERR.PktSource | Source address of packet which | 3400 | | triggered RERR | 3401 | RERR.AddressList[] | List of unreachable route addresses | 3402 | RERR.PrefixLengthList[] | List of PrefixLengths for AddressList | 3403 | RERR.SeqNumList[] | List of SeqNums for AddressList | 3404 | RERR.MetricTypeList[] | MetricType for the invalid routes | 3405 | RERR.Netif | Interface on which the RERR arrived | 3406 +-------------------------+-----------------------------------------+ 3408 Table 11: Notation used in Appendix 3410 C.1. HopCount MetricType 3412 The HopCount MetricType defines: 3414 o MAX_METRIC[HopCount] := MAX_HOPCOUNT. A constant defined in 3415 Section 11.2. MAX_HOPCOUNT is also used to limit the number of 3416 hops an AODVv2 message can travel, regardless of the MetricType in 3417 use. It MUST be larger than the AODVv2 network diameter, in order 3418 that AODVv2 protocol messages may reach their intended 3419 destinations. 3421 o Cost(L) := 1 3423 o Cost(R) := Sum of Cost(L) of each link in the route, i.e., the hop 3424 count between the router calculating the cost, and the destination 3425 of the route (OrigAddr if RREQ, TargAddr if RREP) 3427 o LoopFree(R1, R2) := ( Cost(R1) <= Cost(R2) ). This is derived 3428 from the fact that route cost increases with number of hops. 3429 Therefore, an advertised route with higher cost than the 3430 corresponding existing route could include the existing route as a 3431 sub-section. Replacing the existing route with the advertised 3432 route could form a routing loop. 3434 C.2. General Operations 3436 General AODVv2 operations involve the comparisons of incoming and 3437 current data, and updates to local data sets. 3439 C.2.1. Route Operations 3441 C.2.1.1. Check_Route_State 3443 /* Update the state of the route entry based on timeouts. Return 3444 whether the route can be used for forwarding a packet. */ 3446 Check_Route_State(route) 3447 { 3448 if (CurrentTime > route.ExpirationTime) 3449 route.State := Invalid; 3450 if ((CurrentTime - route.LastUsed > ACTIVE_INTERVAL + MAX_IDLETIME) 3451 AND (route.State != Unconfirmed) 3452 AND (route.ExpirationTime == INFINITY_TIME)) //not a timed route 3453 route.State := Invalid; 3454 if ((CurrentTime - route.LastUsed > ACTIVE_INTERVAL) 3455 AND (route.State != Unconfirmed) 3456 AND (route.ExpirationTime == INFINITY_TIME)) //not a timed route 3457 route.State := Idle; 3458 if ((CurrentTime - route.LastSeqNumUpdate > MAX_SEQNUM_LIFETIME) 3459 AND (route.State == Invalid OR route.State == Unconfirmed)) 3460 /* remove route from route table */ 3461 if ((CurrentTime - route.LastSeqNumUpdate > MAX_SEQNUM_LIFETIME) 3462 AND (route.State != Invalid) 3463 route.SeqNum := 0; 3465 if (route still exists AND route.State != Invalid 3466 AND Route.State != Unconfirmed) 3467 return TRUE; 3468 else 3469 return FALSE; 3470 } 3472 C.2.1.2. Process_Routing_Info 3474 (See Section 6.7.1) 3476 /* Compare incoming route information to stored route, and if better, 3477 use to update stored route. */ 3479 Process_Routing_Info (advRte) 3480 { 3481 rte := Fetch_Route_Table_Entry (advRte); 3482 if (!rte exists) 3483 { 3484 rte := Create_Route_Table_Entry(advRte); 3485 return rte; 3486 } 3488 if (AdvRte.SeqNum > Route.SeqNum /* stored route is stale */ 3489 OR 3490 (AdvRte.SeqNum == Route.SeqNum /* same SeqNum */ 3491 AND 3492 ((Route.State == Invalid AND LoopFree(advRte, rte)) 3493 /* advRte can repair stored */ 3494 OR AdvRte.Cost < Route.Metric))) /* advRte is better */ 3495 { 3496 if (advRte is from a RREQ) 3497 rte := Create_Route_Table_Entry(advRte); 3498 else 3499 Update_Route_Table_Entry (rte, advRte); 3500 } 3501 return rte; 3502 } 3504 C.2.1.3. Fetch_Route_Table_Entry 3505 /* Lookup a route table entry matching an advertised route */ 3507 Fetch_Route_Table_Entry (advRte) 3508 { 3509 foreach (rteTableEntry in rteTable) 3510 { 3511 if (rteTableEntry.Address == advRte.Address 3512 AND rteTableEntry.MetricType == advRte.MetricType) 3513 return rteTableEntry; 3514 } 3515 return null; 3516 } 3518 /* Lookup a route table entry matching address and metric type */ 3520 Fetch_Route_Table_Entry (destination, metricType) 3521 { 3522 foreach (rteTableEntry in rteTable) 3523 { 3524 if (rteTableEntry.Address == destination 3525 AND rteTableEntry.MetricType == metricType) 3526 return rteTableEntry; 3527 } 3528 return null; 3529 } 3531 C.2.1.4. Update_Route_Table_Entry 3533 /* Update a route table entry using AdvRte in received RteMsg */ 3535 Update_Route_Table_Entry (rte, advRte); 3536 { 3537 rte.SeqNum := advRte.SeqNum; 3538 rte.NextHop := advRte.NextHopIp; 3539 rte.NextHopInterface := advRte.NextHopIntf; 3540 rte.LastUsed := CurrentTime; 3541 rte.LastSeqNumUpdate := CurrentTime; 3542 if (validityTime) 3543 rte.ExpirationTime := CurrentTime + advRte.ValidityTime; 3544 else 3545 rte.ExpirationTime := INFINITY_TIME; 3547 rte.Metric := advRte.Cost; 3548 if (rte.State == Invalid) 3549 rte.State := Idle (if advRte is from RREP); 3550 or Unconfirmed (if advRte is from RREQ); 3551 } 3553 C.2.1.5. Create_Route_Table_Entry 3555 /* Create a route table entry from address and prefix length */ 3557 Create_Route_Table_Entry (address, prefixLength, seqNum, metricType) 3558 { 3559 rte := allocate_memory(); 3560 rte.Address := address; 3561 rte.PrefixLength := prefixLength; 3562 rte.SeqNum := seqNum; 3563 rte.MetricType := metricType; 3564 } 3566 /* Create a route table entry from the advertised route */ 3568 Create_Route_Table_Entry(advRte) 3569 { 3570 rte := allocate_memory(); 3572 rte.Address := advRte.Address; 3573 if (advRte.PrefixLength) 3574 rte.PrefixLength := advRte.PrefixLength; 3575 else 3576 rte.PrefixLength := maxPrefixLenForAddressFamily; 3578 rte.SeqNum := advRte.SeqNum; 3579 rte.NextHop := advRte.NextHopIp; 3580 rte.NextHopInterface := advRte.NextHopIntf; 3581 rte.LastUsed := CurrentTime; 3582 rte.LastSeqNumUpdate := CurrentTime; 3583 if (validityTime) 3584 rte.ExpirationTime := CurrentTime + advRte.ValidityTime; 3585 else 3586 rte.ExpirationTime := INFINITY_TIME; 3587 rte.MetricType := advRte.MetricType; 3588 rte.Metric := advRte.Metric; 3589 rte.State := Idle (if advRte is from RREP); 3590 or Unconfirmed (if advRte is from RREQ); 3591 } 3593 C.2.2. LoopFree 3594 /* Return TRUE if the route advRte is LoopFree compared to rte */ 3596 LoopFree(advRte, rte) 3597 { 3598 if (advRte.Cost <= rte.Cost) 3599 return TRUE; 3600 else 3601 return FALSE; 3602 } 3604 C.2.3. Multicast Route Message Table Operations 3606 C.2.3.1. Fetch_Rte_Msg_Table_Entry 3608 /* Find an entry in the RteMsg table matching the given 3609 message's msg-type, OrigAddr, TargAddr, MetricType */ 3611 Fetch_Rte_Msg_Table_Entry (rteMsg) 3612 { 3613 foreach (entry in RteMsgTable) 3614 { 3615 if (entry.msg-type == rteMsg.msg-type 3616 AND entry.OrigAddr == rteMsg.OrigAddr 3617 AND entry.TargAddr == rteMsg.TargAddr 3618 AND entry.MetricType == rteMsg.MetricType) 3619 return entry; 3620 } 3621 return NULL; 3622 } 3624 C.2.3.2. Update_Rte_Msg_Table 3626 (See Section 4.5) 3628 /* Update the multicast route message suppression table based on the 3629 received RteMsg, return true if it was created or the SeqNum was 3630 updated (i.e. it needs to be regenerated) */ 3632 Update_Rte_Msg_Table(rteMsg) 3633 { 3634 /* search for a comparable entry */ 3635 entry := Fetch_Rte_Msg_Table_Entry(rteMsg); 3637 /* if there is none, create one */ 3638 if (entry does not exist) 3639 { 3640 entry.MessageType := rteMsg.msg_type; 3641 entry.OrigAddr := rteMsg.OrigAddr; 3642 entry.TargAddr := rteMsg.TargAddr; 3643 entry.OrigSeqNum := rteMsg.origSeqNum; // (if present) 3644 entry.TargSeqNum := rteMsg.targSeqNum; // (if present) 3645 entry.MetricType := rteMsg.MetricType; 3646 entry.Metric := rteMsg.OrigMetric; // (for RREQ) 3647 or rteMsg.TargMetric; // (for RREP) 3648 entry.Timestamp := CurrentTime; 3649 return TRUE; 3650 } 3652 /* if current entry is stale */ 3653 if ( 3654 (rteMsg.msg-type == RREQ AND entry.OrigSeqNum < rteMsg.OrigSeqNum) 3655 OR 3656 (rteMsg.msg-type == RREP AND entry.TargSeqNum < rteMsg.TargSeqNum)) 3657 { 3658 entry.OrigSeqNum := rteMsg.OrigSeqNum; // (if present) 3659 entry.TargSeqNum := rteMsg.TargSeqNum; // (if present) 3660 entry.Timestamp := CurrentTime; 3661 return TRUE; 3662 } 3664 /* if received rteMsg is stale */ 3665 if ( 3666 (rteMsg.msg-type == RREQ AND entry.OrigSeqNum > rteMsg.OrigSeqNum) 3667 OR 3668 (rteMsg.msg-type == RREP AND entry.TargSeqNum > rteMsg.TargSeqNum)) 3669 { 3670 entry.Timestamp := CurrentTime; 3671 return FALSE; 3672 } 3674 /* if same SeqNum but rteMsg has lower metric */ 3675 if (entry.Metric > rteMsg.Metric) 3676 entry.Metric := rteMsg.Metric; 3678 entry.Timestamp := CurrentTime; 3679 return FALSE; 3680 } 3682 C.3. Message Algorithms 3684 Processing for messages follows the following general outline: 3686 1. Receive incoming message. 3688 2. Update route table as appropriate. 3690 3. Respond as needed, often regenerating the incoming message with 3691 updated information. 3693 After processing a message, the most recent information is stored in 3694 the route table. For this reason, it is equally appropriate to set 3695 outgoing message field values using route table information or using 3696 fields from the incoming message. 3698 C.3.1. Build_RFC_5444_Message_Header 3700 /* This pseudocode shows possible RFC 5444 actions, and would not 3701 be performed by the AODVv2 implementation. It is shown only to 3702 provide more understanding about the AODVv2 message that will be 3703 constructed by RFC 5444. 3704 MAL := Message Address Length 3705 MF := Message Flags 3706 Size := number of octets in MsgHdr, AddrBlk, AddrTLVs */ 3708 Build_RFC_5444_Message_Header (msgType, Flags, AddrFamily, Size, 3709 hopLimit, hopCount, tlvLength) 3710 { 3711 /* Build RFC 5444 message header fields */ 3712 msg-type := msgType; 3713 MF := Flags; 3714 MAL := 3 or 15; // for IPv4 or IPv6 3715 msg-size := Size; 3716 msg-hop-limit := hopLimit; 3717 if (hopCount != 0) /* if hopCount is 0, do not include */ 3718 msg-hop-count := hopCount; 3719 msg.tlvs-length := tlvLength; 3720 } 3722 C.3.2. RREQ Operations 3724 C.3.2.1. Generate_RREQ 3726 /* Generate a route request message to find a route from OrigAddr 3727 to TargAddr using the given MetricType 3728 origAddr := IP address of Router Client which generated the 3729 packet to be forwarded 3730 origPrefix := prefix length associated with the Router Client 3731 targAddr := destination IP address in the packet to be forwarded 3732 targSeqNum := sequence number in existing route to targAddr 3733 mType := metric type for the requested route */ 3735 Generate_RREQ(origAddr, origPrefix, targAddr, targSeqNum, mType) 3736 { 3737 /* Increment sequence number in nonvolatile storage */ 3738 mySeqNum := (1 + mySeqNum); 3740 /* Marshall parameters */ 3741 outRREQ.HopLimit := MAX_HOPCOUNT; 3742 outRREQ.HopCount := 0; // if included 3743 outRREQ.MetricType := mType; //include if not DEFAULT_METRIC_TYPE 3744 outRREQ.OrigAddr := origAddr; 3745 outRREQ.TargAddr := targAddr; 3746 outRREQ.OrigPrefixLen := origPrefix; //include if not address length 3747 outRREQ.OrigSeqNum := mySeqNum; 3748 outRREQ.TargSeqNum := targSeqNum; //included if available 3749 outRREQ.OrigMetric := Route[OrigAddr].Metric; //zero by default 3750 outRREQ.ValidityTime := limit for route to OrigAddr; //if required 3752 /* Build Address Blk using prefix length information from 3753 outRREQ.OrigPrefixLen if necessary */ 3754 AddrBlk := {outRREQ.OrigAddr, outRREQ.TargAddr}; 3756 /* Include sequence numbers in appropriate Address Block TLVs */ 3757 /* OrigSeqNum Address Block TLV */ 3758 origSeqNumAddrBlkTlv.value := outRREQ.OrigSeqNum; 3759 /* TargSeqNum Address Block TLV */ 3760 if (outRREQ.TargSeqNum is known) 3761 targSeqNumAddrBlkTlv.value := outRREQ.TargSeqNum; 3763 /* Build Metric Address Block TLV, include Metric AddrBlkTlv 3764 Extension type if a non-default metric */ 3765 metricAddrBlkTlv.value := outRREQ.OrigMetric; 3766 if (outRREQ.MetricType != DEFAULT_METRIC_TYPE) 3767 metricAddrBlkTlv.typeExtension := outRREQ.MetricType; 3769 if (outRREQ.ValidityTime is required) 3770 { 3771 /* Build VALIDITY_TIME Address Block TLV */ 3772 VALIDITY_TIMEAddrBlkTlv.value := outRREQ.ValidityTime; 3773 } 3775 Build_RFC_5444_Message_Header (RREQ, 4, IPv4 or IPv6, NN, 3776 outRREQ.HopLimit, outRREQ.HopCount, tlvLength); 3778 /* multicast RFC 5444 message to LL-MANET-Routers */ 3779 } 3781 C.3.2.2. Receive_RREQ 3783 /* Process a RREQ received on link L */ 3785 Receive_RREQ (inRREQ, L) 3786 { 3787 if (inRREQ.NbrIP present in blacklist) 3788 { 3789 if (blacklist_expiration_time < CurrentTime) 3790 return; // don't process or regenerate RREQ 3791 else 3792 remove nbrIP from blacklist; 3793 } 3794 if (inRREQ does not contain msg_hop_limit, OrigAddr, 3795 TargAddr, OrigSeqNum, OrigMetric) 3796 return; 3797 if (msg_hop_count > MAX_HOPCOUNT) 3798 return; 3799 if (msg_hop_limit < 0) 3800 return; 3801 if (inRREQ.OrigAddr and inRREQ.TargAddr are not valid routable 3802 and unicast addresses) 3803 return; 3804 if (inRREQ.MetricType is present but an unknown value) 3805 return; 3806 if (inRREQ.OrigMetric > MAX_METRIC[inRREQ.MetricType] - Cost(L)) 3807 return; 3809 /* Extract inRREQ values */ 3810 advRte.Address := inRREQ.OrigAddr; 3811 advRte.PrefixLength := inRREQ.OrigPrefixLen; (if present) 3812 or the address length of advRte.Address; 3813 advRte.SeqNum := inRREQ.OrigSeqNum; 3814 advRte.MetricType := inRREQ.MetricType; 3815 advRte.Metric := inRREQ.OrigMetric; 3816 advRte.Cost := inRREQ.OrigMetric + Cost(L); 3817 //according to the indicated MetricType 3818 advRte.ValidityTime := inRREQ.ValidityTime; //if present 3819 advRte.NextHopIP := inRREQ.NbrIP; 3820 advRte.NextHopIntf := inRREQ.Netif; 3821 advRte.HopCount := inRREQ.HopCount; 3822 advRte.HopLimit := inRREQ.HopLimit; 3824 rte := Process_Routing_Info (advRte); 3826 /* Update the RteMsgTable and determine if the RREQ needs 3827 to be regenerated */ 3828 regenerate := Update_Rte_Msg_Table(inRREQ); 3830 if (inRREQ.TargAddr is in Router Client list) 3831 Generate_RREP(inRREQ, rte); 3832 else if (regenerate) 3833 Regenerate_RREQ(inRREQ, rte); 3835 } 3837 C.3.2.3. Regenerate_RREQ 3839 /* Called from receive_RREQ() 3840 rte := the route to OrigAddr */ 3842 Regenerate_RREQ (inRREQ, rte) 3843 { 3844 outRREQ.HopLimit := inRREQ.HopLimit - 1; 3845 if (outRREQ.HopLimit == 0) 3846 return; // don't regenerate 3848 if (inRREQ.HopCount exists) 3849 { 3850 if (inRREQ.HopCount >= MAX_HOPCOUNT) 3851 return; // don't regenerate 3852 outRREQ.HopCount := inRREQ.HopCount + 1; 3853 } 3855 /* Marshall parameters */ 3856 outRREQ.MetricType := rte.MetricType; 3857 outRREQ.OrigAddr := rte.Address; 3858 outRREQ.TargAddr := inRREQ.TargAddr; 3859 /* include prefix length if not equal to address length */ 3860 outRREQ.OrigPrefixLen := rte.PrefixLength; 3861 outRREQ.OrigSeqNum := rte.SeqNum; 3862 outRREQ.TargSeqNum := inRREQ.TargSeqNum; // if present 3863 outRREQ.OrigMetric := rte.Metric; 3864 outRREQ.ValidityTime := rte.ValidityTime; 3865 or the time limit this router wishes to put on 3866 route to OrigAddr 3868 /* Build Address Block using prefix length information from 3869 outRREQ.OrigPrefixLen if necessary */ 3870 AddrBlk := {outRREQ.OrigAddr, outRREQ.TargAddr}; 3872 /* Include sequence numbers in appropriate Address Block TLVs */ 3873 /* OrigSeqNum Address Block TLV */ 3874 origSeqNumAddrBlkTlv.value := outRREQ.OrigSeqNum; 3875 /* TargSeqNum Address Block TLV */ 3876 if (outRREQ.TargSeqNum is known) 3877 targSeqNumAddrBlkTlv.value := outRREQ.TargSeqNum; 3879 /* Build Metric Address Block TLV, include Metric AddrBlkTlv 3880 Extension type if a non-default metric */ 3881 metricAddrBlkTlv.value := outRREQ.OrigMetric; 3882 if (outRREQ.MetricType != DEFAULT_METRIC_TYPE) 3883 metricAddrBlkTlv.typeExtension := outRREQ.MetricType; 3885 if (outRREQ.ValidityTime is required) 3886 { 3887 /* Build VALIDITY_TIME Address Block TLV */ 3888 VALIDITY_TIMEAddrBlkTlv.value := outRREQ.ValidityTime; 3889 } 3890 Build_RFC_5444_Message_Header (RREQ, 4, IPv4 or IPv6, NN, 3891 outRREQ.HopLimit, outRREQ.HopCount, tlvLength); 3893 /* Multicast RFC 5444 message to LL-MANET-Routers, or if 3894 inRREQ was unicast, the message can be unicast to the next 3895 hop on the route to TargAddr, if known */ 3896 } 3898 C.3.3. RREP Operations 3900 C.3.3.1. Generate_RREP 3902 Generate_RREP(inRREQ, rte) 3903 { 3904 /* Increment sequence number in nonvolatile storage */ 3905 mySeqNum := (1 + mySeqNum); 3907 /* Marshall parameters */ 3908 outRREP.HopLimit := inRREQ.HopCount; 3909 outRREP.HopCount := 0; 3910 /* Include the AckReq when: 3911 - previous RREP does not seem to enable any data flow, OR 3912 - when RREQ is received from same OrigAddr after RREP was 3913 unicast to rte.NextHop */ 3914 outRREP.AckReq := TRUE or FALSE; //TRUE if acknowledgement required 3915 /* if included, set timeout RREP_Ack_SENT_TIMEOUT */ 3917 if (rte.MetricType != DEFAULT_METRIC_TYPE) 3918 outRREP.MetricType := rte.MetricType; 3919 outRREP.OrigAddr := inRREQ.Address; 3920 outRREP.TargAddr := rte.TargAddr; 3921 outRREP.TargPrefixLen := rte.PrefixLength; //if not address length 3922 outRREP.TargSeqNum := mySeqNum; 3923 outRREP.TargMetric := rte.Metric; 3924 outRREP.ValidityTime := limit for route to TargAddr; //if required 3926 if (outRREP.AckReq == TRUE) 3927 /* include AckReq Message TLV */ 3929 /* Build Address Block using prefix length information from 3930 outRREP.TargPrefixLen if necessary */ 3932 AddrBlk := {outRREP.OrigAddr, outRREP.TargAddr}; 3934 /* TargSeqNum Address Block TLV */ 3935 targSeqNumAddrBlkTlv.value := outRREP.TargSeqNum; 3937 /* Build Metric Address Block TLV include Metric AddrBlkTlv 3938 Extension type if a non-default metric */ 3939 metricAddrBlkTlv.value := outRREP.TargMetric; 3940 if (outRREP.MetricType != DEFAULT_METRIC_TYPE) 3941 metricAddrBlkTlv.typeExtension := outRREP.MetricType; 3943 if (outRREP.ValidityTime is required) 3944 { 3945 /* Build VALIDITY_TIME Address Block TLV */ 3946 VALIDITY_TIMEAddrBlkTlv.value := outRREP.ValidityTime; 3947 } 3949 Build_RFC_5444_Message_Header (RREP, 4, IPv4 or IPv6, NN, 3950 outRREP.HopLimit, outRREQ.HopCount, tlvLength); 3952 /* unicast RFC 5444 message to rte[OrigAddr].NextHop */ 3953 } 3955 C.3.3.2. Receive_RREP 3957 /* Process a RREP received on link L */ 3959 Receive_RREP (inRREP, L) 3960 { 3961 if (inRREP.NbrIP present in blacklist) 3962 { 3963 if (blacklist_expiration_time < CurrentTime) 3964 return; // don't process or regenerate RREP 3965 else 3966 remove NbrIP from blacklist; 3967 } 3969 if (inRREP does not contain msg_hop_limit, OrigAddr, 3970 TargAddr, TargSeqNum, TargMetric) 3971 return; 3972 if (msg_hop_count > MAX_HOPCOUNT) 3973 return; 3974 if (msg_hop_limit < 0) 3975 return; 3976 if (inRREP.OrigAddr and inRREQ.TargAddr are not 3977 valid routable and unicast addresses) 3978 return; 3979 if (inRREP.MetricType is present but an unknown value) 3980 return; 3981 if (inRREP.TargMetric > MAX_METRIC[inRREP.MetricType]) 3982 return; 3984 /* Extract inRREP values */ 3985 advRte.Address := inRREP.TargAddr; 3986 advRte.PrefixLength := inRREP.TargPrefixLen; //if present 3987 or the address length of advRte.Address; 3988 advRte.SeqNum := inRREP.TargSeqNum; 3989 advRte.MetricType := inRREP.MetricType; 3990 advRte.Metric := inRREP.TargMetric; 3991 advRte.Cost := inRREP.TargMetric + Cost(L); 3992 //according to the indicated MetricType 3993 advRte.ValidityTime := inRREP.ValidityTime; //if present 3994 advRte.NextHopIP := inRREP.NbrIP; 3995 advRte.NextHopIntf := inRREP.Netif; 3996 advRte.HopCount := inRREP.HopCount; 3997 advRte.HopLimit := inRREP.HopLimit; //if included 3999 rte := Process_Routing_Info (advRte); 4001 ` if (inRREP includes AckReq data element) 4002 Generate_RREP_Ack(inRREP); 4004 /* Update the RteMsgTable and determine if the RREP needs 4005 to be regenerated */ 4006 regenerate := Update_Rte_Msg_Table(inRREP); 4008 if (inRREP.TargAddr is in the Router Client list) 4009 send_buffered_packets(rte); /* start to use the route */ 4010 else if (regenerate) 4011 Regenerate_RREP(inRREP, rte); 4012 } 4014 C.3.3.3. Regenerate_RREP 4016 Regenerate_RREP(inRREP, rte) 4017 { 4018 if (rte does not exist) 4019 { 4020 Generate_RERR(inRREP); 4021 return; 4022 } 4024 outRREP.HopLimit := inRREP.HopLimit - 1; 4025 if (outRREP.HopLimit == 0) /* don't regenerate */ 4026 return; 4028 if (inRREP.HopCount exists) 4029 { 4030 if (inRREP.HopCount >= MAX_HOPCOUNT) 4031 return; // don't regenerate the RREP 4032 outRREP.HopCount := inRREP.HopCount + 1; 4033 } 4035 /* Marshall parameters */ 4036 /* Include the AckReq when: 4037 - previous unicast RREP seems not to enable data flow, OR 4038 - when RREQ is received from same OrigAddr after RREP 4039 was unicast to rte.NextHop */ 4040 outRREP.AckReq := TRUE or FALSE; //TRUE if acknowledgement required 4041 /* if included, set timeout RREP_Ack_SENT_TIMEOUT */ 4043 if (rte.MetricType != DEFAULT_METRIC_TYPE) 4044 outRREP.MetricType := rte.MetricType; 4045 outRREP.OrigAddr := inRREP.OrigAddr; 4046 outRREP.TargAddr := rte.Address; 4047 outRREP.TargPrefixLen := rte.PrefixLength; //if not address length 4048 outRREP.TargSeqNum := rte.SeqNum; 4049 outRREP.TargMetric := rte.Metric; 4050 outRREP.ValidityTime := limit for route to TargAddr; //if required 4051 outRREP.NextHop := rte.NextHop 4053 if (outRREP.AckReq == TRUE) 4054 /* include AckReq Message TLV */ 4056 /* Build Address Block using prefix length information from 4057 outRREP.TargPrefixLen if necessary */ 4058 AddrBlk := {outRREP.OrigAddr, outRREP.TargAddr}; 4060 /* TargSeqNum Address Block TLV */ 4061 targSeqNumAddrBlkTlv.value := outRREP.TargSeqNum; 4063 /* Build Metric Address Block TLV include Metric AddrBlkTlv 4064 Extension type if a non-default metric */ 4065 metricAddrBlkTlv.value := outRREP.TargMetric; 4066 if (outRREP.MetricType != DEFAULT_METRIC_TYPE) 4067 metricAddrBlkTlv.typeExtension := outRREP.MetricType; 4069 if (outRREP.ValidityTime is required) 4070 { 4071 /* Build VALIDITY_TIME Address Block TLV */ 4072 VALIDITY_TIMEAddrBlkTlv.value := outRREP.ValidityTime; 4073 } 4075 Build_RFC_5444_Message_Header (RREP, 4, IPv4 or IPv6, NN, 4076 outRREP.HopLimit, 0, tlvLength); 4078 /* unicast RFC 5444 message to rte[OrigAddr].NextHop */ 4079 } 4081 C.3.4. RREP_Ack Operations 4083 C.3.4.1. Generate_RREP_Ack 4085 /* To be sent when a received RREP includes the AckReq data element */ 4087 Generate_RREP_Ack(inRREP) 4088 { 4089 Build_RFC_5444_Message_Header (RREP_Ack, 4, IPv4 or IPv6, NN, 4090 1, 0, 0); 4091 /* unicast RFC 5444 message to inRREP.NbrIP */ 4092 } 4094 C.3.4.2. Receive_RREP_Ack 4096 Receive_RREP_Ack(inRREP_Ack) 4097 { 4098 /* cancel timeout event for the node sending RREP_Ack */ 4099 } 4101 C.3.4.3. Timeout_RREP_Ack 4103 Timeout_RREP_Ack(outRREP) 4104 { 4105 if (numRetries < RREP_RETRIES) 4106 /* resend RREP and double the previous timeout */ 4107 else 4108 /* insert unresponsive node into blacklist */ 4109 } 4111 C.3.5. RERR Operations 4113 C.3.5.1. Generate_RERR 4115 There are two parts to this function, based on whether it was 4116 triggered by an undeliverable packet or a broken link to neighboring 4117 AODVv2 router. 4119 /* Generate a Route Error message. 4120 errorType := undeliverablePacket or brokenLink */ 4122 Generate_RERR(errorType, triggerPkt, brokenLinkNbrIp) 4123 { 4124 switch (errorType) 4125 { 4126 case (brokenLink): 4127 doGenerate := FALSE; 4128 num-broken-addr := 0; 4129 precursors[] := new empty precursor list; 4130 outRERR.HopLimit := MAX_HOPCOUNT; 4131 /* find routes which are now Invalid */ 4132 foreach (rte in route table) 4133 { 4134 if (brokenLinkNbrIp == rte.NextHop 4135 AND (rte.State == Active 4136 OR 4137 (rte.State == Idle AND ENABLE_IDLE_IN_RERR))) 4138 { 4139 if (rte.State == Active) 4140 doGenerate := TRUE; 4141 rte.State := Invalid; 4142 precursors += rte.Precursors (if any); 4143 outRERR.AddressList[num-broken-addr] := rte.Address; 4144 outRERR.PrefixLengthList[num-broken-addr] := 4145 rte.PrefixLength; 4146 outRERR.SeqNumList[num-broken-addr] := rte.SeqNum; 4147 outRERR.MetricTypeList[num-broken-addr] := rte.MetricType 4148 num-broken-addr := num-broken-addr + 1; 4149 } 4150 } 4151 } 4152 case (undeliverablePacket): 4153 doGenerate := TRUE; 4154 num-broken-addr := 1; 4155 outRERR.HopLimit := MAX_HOPCOUNT; 4156 outRERR.PktSource := triggerPkt.SrcIP; 4157 or triggerPkt.TargAddr; //if pkt was a RREP 4158 outRERR.AddressList[0] := triggerPkt.DestIP; 4159 or triggerPkt.OrigAddr; //if pkt was RREP 4160 /* optional to include outRERR.PrefixLengthList, outRERR.SeqNumList 4161 and outRERR.MetricTypeList */ 4162 } 4164 if (doGenerate == FALSE) 4165 return; 4167 if (triggerPkt exists) 4168 { 4169 /* Build PktSource Message TLV */ 4170 pktSourceMessageTlv.value := outRERR.PktSource; 4171 } 4172 /* The remaining steps add address, prefix length, sequence 4173 number and metric type information for each unreachable address, 4174 while conforming to the allowed MTU. If the MTU is reached, a new 4175 message MUST be created. */ 4177 /* Build Address Block using prefix length information from 4178 outRERR.PrefixLengthList[] if necessary */ 4179 AddrBlk := outRERR.AddressList[]; 4181 /* Optionally, add SeqNum Address Block TLV, including index values */ 4182 seqNumAddrBlkTLV := outRERR.SeqNumList[]; 4184 if (outRERR.MetricTypeList contains non-default MetricTypes) 4185 /* include Metric Address Block TLVs with Type Extension set to 4186 MetricType, including index values if necessary */ 4187 metricAddrBlkTlv.typeExtension := outRERR.MetricTypeList[]; 4189 Build_RFC_5444_Message_Header (RERR, 4, IPv4 or IPv6, NN, 4190 outRERR.HopLimit, 0, tlvLength); 4192 if (undeliverablePacket) 4193 /* unicast outRERR to rte[outRERR.PktSource].NextHop */ 4194 else if (brokenLink) 4195 /* unicast to precursors, or multicast to LL-MANET-Routers */ 4196 } 4198 C.3.5.2. Receive_RERR 4200 Receive_RERR (inRERR) 4201 { 4202 if (inRERR does not contain msg_hop_limit and at least 4203 one unreachable address) 4204 return; 4206 /* Extract inRERR values, copy relevant unreachable addresses, 4207 their prefix lengths, and sequence numbers to outRERR */ 4208 num-broken-addr := 0; 4209 precursors[] := new empty precursor list; 4210 foreach (unreachableAddress in inRERR.AddressList) 4211 { 4212 if (unreachableAddress is not valid routable and unicast) 4213 continue; 4214 if (unreachableAddress MetricType is present but an unknown value) 4215 return; 4217 /* Find a matching route table entry, assume 4218 DEFAULT_METRIC_TYPE if no MetricType included */ 4219 rte := Fetch_Route_Table_Entry (unreachableAddress, 4220 unreachableAddress MetricType) 4221 if (rte does not exist) 4222 continue; 4223 if (rte.State == Invalid)/* ignore already invalid routes */ 4224 continue; 4225 if ((rte.NextHop != inRERR.NbrIP 4226 OR 4227 rte.NextHopInterface != inRERR.Netif) 4228 AND (PktSource is not present OR is not a Router Client)) 4229 continue; 4230 if (unreachableAddress SeqNum (if known) < rte.SeqNum) 4231 continue; 4233 /* keep a note of all precursors of newly Invalid routes */ 4234 precursors += rte.Precursors; //if any 4236 /* assume prefix length is address length if not included */ 4237 if (rte.PrefixLength != unreachableAddress prefixLength) 4238 { 4239 /* create new route with unreachableAddress information */ 4240 invalidRte := Create_Route_Table_Entry(unreachableAddress, 4241 unreachableAddress PrefixLength, 4242 unreachableAddress SeqNum, 4243 unreachableAddress MetricType); 4244 invalidRte.State := Invalid; 4246 if (rte.PrefixLength > unreachableAddress prefixLength) 4247 expunge_route(rte); 4248 rte := invalidRte; 4249 } 4250 else if (rte.PrefixLength == unreachableAddress prefixLength) 4251 rte.State := Invalid; 4253 outRERR.AddressList[num-broken-addr] := rte.Address; 4254 outRERR.PrefixLengthList[num-broken-addr] := rte.PrefixLength; 4255 outRERR.SeqNumList[num-broken-addr] := rte.SeqNum; 4256 outRERR.MetricTypeList[num-broken-addr] := rte.MetricType; 4257 num-broken-addr := num-broken-addr + 1; 4258 } 4260 if (num-broken-addr AND (PktSource is not present OR PktSource is not 4261 a Router Client)) 4262 Regenerate_RERR(outRERR, inRERR, precursors); 4263 } 4264 C.3.5.3. Regenerate_RERR 4266 Regenerate_RERR (outRERR, inRERR, precursors) 4267 { 4268 /* Marshal parameters */ 4269 outRERR.HopLimit := inRERR.HopLimit - 1; 4270 if (outRERR.HopLimit == 0) // don't regenerate 4271 return; 4273 outRERR.PktSource := inRERR.PktSource; //if included 4274 /* AddressList[], SeqNumList[], and PrefixLengthList[] are 4275 already up-to-date */ 4277 if (outRERR.PktSource exists) 4278 { 4279 /* Build PktSource Message TLV */ 4280 pktSourceMessageTlv.value := outRERR.PktSource; 4281 } 4283 /* Build Address Block using prefix length information from 4284 outRERR.PrefixLengthList[] if necessary */ 4285 AddrBlk := outRERR.AddressList[]; 4287 /* Optionally, add SeqNum Address Block TLV, including index values */ 4288 seqNumAddrBlkTLV := outRERR.SeqNumList[]; 4290 if (outRERR.MetricTypeList contains non-default MetricTypes) 4291 /* include Metric Address Block TLVs with Type Extension set to 4292 MetricType, including index values if necessary */ 4293 metricAddrBlkTlv.typeExtension := outRERR.MetricTypeList[]; 4295 Build_RFC_5444_Message_Header (RERR, 4, IPv4 or IPv6, NN, 4296 outRERR.HopLimit, 0, tlvLength); 4298 if (outRERR.PktSource exists) 4299 /* unicast RFC 5444 message to next hop towards 4300 outRERR.PktSource */ 4301 else if (number of precursors == 1) 4302 /* unicast RFC 5444 message to precursors[0] */ 4303 else if (number of precursors > 1) 4304 /* unicast RFC 5444 message to all precursors, or multicast 4305 RFC 5444 message to RERR_PRECURSORS if preferable */ 4306 else 4307 /* multicast RFC 5444 message to LL-MANET-Routers */ 4308 } 4309 Appendix D. AODVv2 Draft Updates 4311 D.1. Changes between revisions 11 and 12 4313 This section lists the changes between AODVv2 revisions ...-11.txt 4314 and ...-12.txt. 4316 o Avoided use of "node" and "subnet" where possible. 4318 o Improved separation of data structure information from protocol 4319 operation. 4321 o Updated uses of the terms "IP address" and "packet" to be clearer. 4323 o More consistent and accurate use of MUST, SHOULD, SHOULD NOT, and 4324 MAY, and added explanations of consequences of not implementing 4325 SHOULDs. 4327 o Used consistent references to [RFC5444]. 4329 o Updated title to include "Version 2". 4331 o Updated Overview to state differences from AODV, text about loop 4332 freedom and RFC 7182 in Overview. 4334 o Updated Terminology and removed the Data Element table. Gave 4335 clearer definition of Router Client and Unreachable Address. 4337 o Updated Applicability Statement to draw attention to requirements 4338 of the forwarding plane, handling of uni-directional links, usage 4339 of IP addresses on multiple interfaces, and description of gateway 4340 functionality. Added note about penalty for not storing 4341 persistent state. 4343 o Updated Router Client section and added cost to Router Client 4344 entry. 4346 o Clarified that Neighbor Table needs only information on 4347 neighboring routers on discovered routes. 4349 o Updated Sequence Number section. Use only one sequence number per 4350 router. Added description of sequence number comparison. 4352 o Updated descriptions of route states. 4354 o Improved clarity of Metrics section, generic metric instead of 4355 hopcount, removed default metric type, added explanation of 4356 LoopFree. 4358 o Improved Initialization section. 4360 o Major update to Adjacency Monitoring section. Made it clear that 4361 if bidirectional connectivity is already confirmed, requesting 4362 acknowledgement is unnecessary. Separated Neighbor Table Updates 4363 into separate section. 4365 o Updated description of message prioritization near the control 4366 message generation limit. 4368 o Updated wording regarding [RFC6621]. 4370 o Added description of backoff used for message retries. 4372 o Improved description of how unidirectional links are handled. 4374 o Improved text regarding creation of Unconfirmed route entries. 4376 o Improved section on determining redundancy of received multicast 4377 messages. 4379 o Added section on interactions with the forwarding plane. 4381 o Improved Route State section. Clarified action when Active route 4382 expires. Separated information on expunging routes on memory 4383 constrained routers. 4385 o Updated RERR description to be clearer about triggers. 4387 o Updated IANA section to include only newly defined Messages and 4388 TLVs, and define an Unspecified value for AddressType. 4390 o Updated references. 4392 o Updated section on Gateway behaviour. 4394 o Updated Appendix D to include more checks on msg_hop_limit and 4395 msg_hop_count. 4397 o Renamed MAX_TIME to INFINITY_TIME to make meaning clearer. 4399 D.2. Changes between revisions 10 and 11 4401 This section lists the changes between AODVv2 revisions ...-10.txt 4402 and ...-11.txt. 4404 o Updated Simple Internet Attachment section to clarify behaviour of 4405 IAR for incoming RREQ messages. 4407 D.3. Changes between revisions 9 and 10 4409 This section lists the changes between AODVv2 revisions ...-09.txt 4410 and ...-10.txt. 4412 o Updated [RFC5444] Representation section to add "Address Type" 4413 TLV, which explicitly declares the meaning of addresses in the 4414 [RFC5444] Address Block. 4416 o Relocated route state definitions. Minor improvements to clarity 4417 throughout. 4419 o Updated definition of timed routes. 4421 o More consistent use of OrigPrefixLen, TargPrefixLen, and Invalid. 4423 o Mandated use of neighbor adjacency checking and support of AckReq 4424 and RREP_Ack and clarified related text. 4426 o Changed order of LoopFree checking and route cost comparisons in 4427 Evaluating Route Information. 4429 o Updated structure of section on Applying Route Updates. 4431 o Updated AckReq to include intended next hop address, and RREP to 4432 be multicast if intended next hop is not a confirmed neighbor. 4434 o Clarified that gateway router is not default router. 4436 D.4. Changes between revisions 8 and 9 4438 This section lists the changes between AODVv2 revisions ...-08.txt 4439 and ...-09.txt. 4441 o Numerous editorial improvements were made, including 4442 relocation/removal/renaming/adding of some sections and text, 4443 collection and tidying of scattered text on same topic, formatting 4444 made more consistent to improve readability. 4446 o Removed mentions of precursors from main text, except one mention 4447 in Route Table Entry. 4449 o Removed use of MIN_METRIC which was not defined. 4451 o Changed Current_Time to CurrentTime for consistency. 4453 o Changed OrigAddrMetric and TargAddrMetric to OrigMetric and 4454 TargMetric respectively. 4456 o Updated Overview to simplify and provide a broader summary. 4458 o Updated Terminology definitions, Data Elements tables and combined 4459 sections. 4461 o Updated Applicability Statement to move some of the non- 4462 applicability text and to simplify what remains. 4464 o Updated TLV names to conform to existing naming style. 4466 o Updated Blacklist to be a NeighborList to include neighbors that 4467 have confirmed bidirectional connectivity. 4469 o Updated messages processed if router on blacklist and which are 4470 indicators of bidirectional links. 4472 o Added RemoveTime to RteMsg Table section. 4474 o Added short description of timed route to Route Table Entry 4475 section but removed Route.Timed flag. Route is timed if its 4476 expiration time is not MAX_TIME. 4478 o Added Unconfirmed route state for route to OrigAddr learned from 4479 RREQ. 4481 o Updated AODVv2 Protocol Operations section and subsections, 4482 including Initialization, Adjacency Monitoring, making algorithms 4483 easier to read and making notation consistent, general 4484 improvements to the text. 4486 o Updated Route Discovery, Retries and Buffering to include a more 4487 complete description of the route discovery process. 4489 o Updated wording relating to different metric types. 4491 o Added text regarding control message limit in Message Transmission 4492 section. 4494 o Added short explanation of positive/negative effects of buffering. 4496 o Simplified the packet diagrams, since some of their contents was 4497 already explained in the text below and then again as part of 4498 generation, reception and regeneration processes. 4500 o Clarified some elements of the message content descriptions. 4502 o Moved MetricType above MetricList in message sections, for 4503 consistency. 4505 o Mirrored structure throughout AODVv2 Protocol Messages. 4507 o Changed RREQ and RREP's use of Lists when only one entry is 4508 necessary. 4510 o Added some pre-message-generation checks. 4512 o Ensured consistency in regeneration (if msg-hop-limit is reduced 4513 to zero, do not regenerate). 4515 o Removed statements about neighbors but added blacklist checks 4516 where necessary. 4518 o Noted that RREQ retries SHOULD increase the SeqNum. 4520 o Added statement that implementations SHOULD retry sending RREP. 4522 o Added text explaining what happens if RREP is lost, regarding 4523 blacklisting and RREQ retries. 4525 o Removed hop limit from RREP_Ack. Changed order of blacklist 4526 check. 4528 o Updated RERR so that multiple metric types can be reported in the 4529 same message. 4531 o Updated RERR reception processing to ensure PktSource deletes the 4532 contained route. 4534 o Added text to show that if a router is the destination of a RERR, 4535 the RERR is not regenerated. 4537 o Added text that RERRs SHOULD NOT be created if the same RERR has 4538 recently been sent. 4540 o Updated [RFC5444] overview and simplified/rearranged text in this 4541 section. 4543 o Major update to [RFC5444] representation section 4545 o Updated RERR's [RFC5444] representation so that PktSource is 4546 placed in Address Block, and updated IANA section to make 4547 PktSource an Address Block TLV to indicate which address is 4548 PktSource. 4550 o Described use of extension type in Metric TLV to represent 4551 MetricType, and the interpretation when using the default metric 4552 type. 4554 o Removed Multicast RREP as an optional feature. 4556 o Updated Precursor Lists section to include options for precursor 4557 information to store. 4559 o Updated Security Considerations. 4561 D.5. Changes between revisions 7 and 8 4563 This section lists the changes between AODVv2 revisions ...-07.txt 4564 and ...-08.txt. 4566 o MetricType is now an Address Block TLV. Minor changes to the 4567 text. By using an extension type in the Metric TLV we can 4568 represent MetricType more elegantly in the [RFC5444] message. 4570 o Updated Overview to be slightly more concise. 4572 o Moved MetricType next to Metric when mentioned for better flow. 4574 o Added text to Applicability to address comments on mailing list 4575 regarding gateway behavior and NHDP HELLO messages. 4577 o Removed paragraph in AODVv2 Message Transmission section regarding 4578 TTL. 4580 o Added reference where precursors are mentioned in route table 4581 entry. 4583 o Added text to bidirectionality explanation regarding NHDP HELLO 4584 messages and lower layer triggers. 4586 o Clarified blacklist removal with SHOULD rather than MAY. 4588 o Removed pseudo-code from section on evaluating incoming routing 4589 information. 4591 o Clarified rules for expunging route entries on memory-constrained 4592 devices. 4594 o Clarified the use of exponential backoff for route discovery 4595 attempts. 4597 o Small updates to message sections. Removed steps about checking 4598 if neighbors. 4600 o Renamed [RFC5444] parser to multiplexer in Section 10. 4602 o Removed "optional feature" to include multiple addresses in RERR. 4604 o Removed MetricType from the Message TLV Type Specification. 4606 o Updated Security Considerations. 4608 o Added reference to RFC 7182. 4610 o Small updates to message algorithms, including moving MetricType 4611 from Message TLV to the Metric TLV in the Address Block TLV Block, 4612 and only generating RERR if an Active route was made Invalid. 4614 D.6. Changes between revisions 6 and 7 4616 This section lists the changes since AODVv2 revision ...-06.txt 4618 o Added Victoria Mercieca as co-author. 4620 o Reorganized protocol message descriptions into major subsections 4621 for each protocol message. For protocol messages, organized 4622 processing into Generation, Reception, and Regeneration 4623 subsections. 4625 o Separated RREQ and RREP message processing description into 4626 separate major subsection which had previously been combined into 4627 RteMsg description. 4629 o Enlarged RREQ Table function to include similar processing for 4630 optional flooded RREP messages. The table name has been 4631 correspondingly been changed to be the Table for Multicast 4632 RteMsgs. 4634 o Moved sections for Multiple Interfaces and AODVv2 Control Message 4635 Generation Limits to be major subsections of the AODVv2 Protocol 4636 Operations section. 4638 o Reorganized the protocol message processing steps into the 4639 subsections as previously described, adopting a more step-by-step 4640 presentation. 4642 o Coalesced the router states Broken and Expired into a new combined 4643 state named the Invalid state. No changes in processing are 4644 required for this. 4646 o Merged the sections describing Next-hop Router Adjacency 4647 Monitoring and Blacklists. 4649 o Specified that routes created during Route Discovery are marked as 4650 Idle routes. If they are used for carrying data they become 4651 Active routes. 4653 o Added Route.LastSeqNumUpdate information to route table, so that 4654 route activity and sequence number validity can be tracked 4655 separately. An active route can still forward traffic even if the 4656 sequence number has not been refreshed within MAX_SEQNUM_LIFETIME. 4658 o Mandated implementation of RREP_Ack as response to AckReq Message 4659 TLV in RREP messages. 4660 Added field to RREP_Ack to ensure correspondence to the correct 4661 AckReq message. 4663 o Added explanations for what happens if protocol constants are 4664 given different values on different AODVv2 routers. 4666 o Specified that AODVv2 implementations are free to choose their own 4667 heuristics for reducing multicast overhead, including RFC 6621. 4669 o Added appendix to identify AODVv2 requirements from OS 4670 implementation of IP and ICMP. 4672 o Deleted appendix showing example [RFC5444] packet formats. 4674 o Clarification on the use of RFC 5497 VALIDITY_TIME. 4676 o In Terminology, deleted superfluous definitions, added missing 4677 definitions. 4679 o Numerous editorial improvements and clarifications. 4681 D.7. Changes between revisions 5 and 6 4683 This section lists the changes between AODVv2 revisions ...-05.txt 4684 and ...-06.txt. 4686 o Added Lotte Steenbrink as co-author. 4688 o Reorganized section on Metrics to improve readability by putting 4689 specific topics into subsections. 4691 o Introduced concept of data element, which is used to clarify the 4692 method of enabling [RFC5444] representation for AODVv2 data 4693 elements. A list of Data Elements was introduced in section 3, 4694 which provides a better understanding of their role than was 4695 previously supplied by the table of notational devices. 4697 o Replaced instances of OrigNode by OrigAddr whenever the more 4698 specific meaning is appropriate. Similarly for instances of other 4699 node versus address terminology. 4701 o Introduced concepts of PrefixLengthList and MetricList in order to 4702 avoid use of index-based terminology such as OrigNdx and TargNdx. 4704 o Added section 5, "AODVv2 Message Transmission", describing the 4705 intended interface to [RFC5444]. 4707 o Included within the main body of the specification the mandatory 4708 setting of the TLV flag thassingleindex for TLVs OrigSeqNum and 4709 TargSeqNum. 4711 o Removed the Route.Timed state. Created a new flag for route table 4712 entries known as Route.Timed. This flag can be set when the route 4713 is in the active state. Previous description would require that 4714 the route table entry be in two states at the same time, which 4715 seems to be misleading. The new flag is used to clarify other 4716 specification details for Timed routes. 4718 o Created table 3 to show the correspondence between AODVv2 data 4719 elements and [RFC5444] message components. 4721 o Replaced "invalid" terminology by the more specific terms "broken" 4722 or "expired" where appropriate. 4724 o Eliminated the instance of duplicate specification for inclusion 4725 of OrigNode (now, OrigAddr) in the message. 4727 o Corrected the terminology to be Mid instead of Tail for the 4728 trailing address bits of OrigAddr and TargAddr for the example 4729 message formats in the appendices. 4731 o Repaired remaining instances of phraseology that could be 4732 construed as indicating that AODV only supports a single network 4733 interface. 4735 o Numerous editorial improvements and clarifications. 4737 D.8. Changes between revisions 4 and 5 4739 This section lists the changes between AODVv2 revisions ...-04.txt 4740 and ...-05.txt. 4742 o Normative text moved out of definitions into the relevant section 4743 of the body of the specification. 4745 o Editorial improvements and improvements to consistent terminology 4746 were made. Replaced "retransmit" by the slightly more accurate 4747 term "regenerate". 4749 o Issues were resolved as discussed on the mailing list. 4751 o Changed definition of LoopFree as suggested by Kedar Namjoshi and 4752 Richard Trefler to avoid the failure condition that they have 4753 described. In order to make understanding easier, replaced 4754 abstract parameters R1 by RteMsg and R2 by Route to reduce the 4755 level of abstraction when the function LoopFree is discussed. 4757 o Added text to clarify that different metrics may have different 4758 data types and different ranges of acceptable values. 4760 o Added text to section "RteMsg Structure" to emphasize the proper 4761 use of [RFC5444]. 4763 o Included within the main body of the specification the mandatory 4764 setting of the TLV flag thassingleindex for TLVs OrigSeqNum and 4765 TargSeqNum. 4767 o Made more extensive use of the AdvRte terminology, in order to 4768 better distinguish between the incoming RREQ or RREP message 4769 (i.e., RteMsg) versus the route advertised by the RteMsg (i.e., 4770 AdvRte). 4772 D.9. Changes between revisions 3 and 4 4774 This section lists the changes between AODVv2 revisions ...-03.txt 4775 and ...-04.txt. 4777 o An appendix was added to exhibit algorithmic code for 4778 implementation of AODVv2 functions. 4780 o Numerous editorial improvements and improvements to consistent 4781 terminology were made. Terminology related to prefix lengths was 4782 made consistent. Some items listed in "Notational Conventions" 4783 were no longer used, and so deleted. 4785 o Issues were resolved as discussed on the mailing list. 4787 o Appropriate instances of "may" were changed to "MAY". 4789 o Definition inserted for "upstream". 4791 o Route.Precursors included as an *optional* route table field 4792 o Reworded text to avoid use of "relevant". 4794 o Deleted references to "DestOnly" flag. 4796 o Refined statements about MetricType TLV to allow for omission when 4797 MetricType == HopCount. 4799 o Bulletized list in section 8.1 4801 o ENABLE_IDLE_UNREACHABLE renamed to be ENABLE_IDLE_IN_RERR 4803 o Transmission and subscription to LL-MANET-Routers converted to 4804 MUST from SHOULD. 4806 D.10. Changes between revisions 2 and 3 4808 This section lists the changes between AODVv2 revisions ...-02.txt 4809 and ...-03.txt. 4811 o The "Added Node" feature was removed. This feature was intended 4812 to enable additional routing information to be carried within a 4813 RREQ or a RREP message, thus increasing the amount of topological 4814 information available to nodes along a routing path. However, 4815 enlarging the packet size to include information which might never 4816 be used can increase congestion of the wireless medium. The 4817 feature can be included as an optional feature at a later date 4818 when better algorithms are understood for determining when the 4819 inclusion of additional routing information might be worthwhile. 4821 o Numerous editorial improvements and improvements to consistent 4822 terminology were made. Instances of OrigNodeNdx and TargNodeNdx 4823 were replaced by OrigNdx and TargNdx, to be consistent with the 4824 terminology shown in Table 1. 4826 o Example RREQ and RREP message formats shown in the Appendices were 4827 changed to use OrigSeqNum and TargSeqNum message TLVs instead of 4828 using the SeqNum message TLV. 4830 o Inclusion of the OrigNode's SeqNum in the RREP message is not 4831 specified. The processing rules for the OrigNode's SeqNum were 4832 incompletely specified in previous versions of the draft, and very 4833 little benefit is foreseen for including that information, since 4834 reverse path forwarding is used for the RREP. 4836 o Additional acknowledgements were included, and contributors names 4837 were alphabetized. 4839 o Definitions in the Terminology section capitalize the term to be 4840 defined. 4842 o Uncited bibliographic entries deleted. 4844 o Ancient "Changes" sections were deleted. 4846 Authors' Addresses 4848 Charles E. Perkins 4849 Futurewei Inc. 4850 2330 Central Expressway 4851 Santa Clara, CA 95050 4852 USA 4854 Phone: +1-408-330-4586 4855 Email: charliep@computer.org 4857 Stan Ratliff 4858 Idirect 4859 13861 Sunrise Valley Drive, Suite 300 4860 Herndon, VA 20171 4861 USA 4863 Email: ratliffstan@gmail.com 4865 John Dowdell 4866 Airbus Defence and Space 4867 Celtic Springs 4868 Newport, Wales NP10 8FZ 4869 United Kingdom 4871 Email: john.dowdell@airbus.com 4873 Lotte Steenbrink 4874 HAW Hamburg, Dept. Informatik 4875 Berliner Tor 7 4876 D-20099 Hamburg 4877 Germany 4879 Email: lotte.steenbrink@haw-hamburg.de 4880 Victoria Mercieca 4881 Airbus Defence and Space 4882 Celtic Springs 4883 Newport, Wales NP10 8FZ 4884 United Kingdom 4886 Email: victoria.mercieca@airbus.com