idnits 2.17.1 draft-ietf-manet-aodvv2-10.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 9 instances of too long lines in the document, the longest one being 3 characters in excess of 72. == There are 6 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 == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'SHOULD not' in this paragraph: Until MAX_SEQNUM_LIFETIME after its sequence number is reset, the router SHOULD not create RREQ or RREP messages. -- The document date (July 6, 2015) is 3217 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: 'MANETs' is mentioned on line 191, but not defined == Missing Reference: 'Address' is mentioned on line 421, but not defined == Missing Reference: 'MetricType' is mentioned on line 2797, but not defined == Missing Reference: 'HopCount' is mentioned on line 2769, but not defined == Missing Reference: 'OrigAddr' is mentioned on line 3914, but not defined == Missing Reference: 'TargAddr' is mentioned on line 3765, but not defined == Missing Reference: 'TBD' is mentioned on line 2903, but not defined -- Looks like a reference, but probably isn't: '0' on line 4139 == Unused Reference: 'RFC4291' is defined on line 3093, but no explicit reference was found in the text == Unused Reference: 'RFC5082' is defined on line 3096, but no explicit reference was found in the text == Unused Reference: 'Perkins99' is defined on line 3129, but no explicit reference was found in the text == Unused Reference: 'RFC4861' is defined on line 3150, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 14 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: January 7, 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 July 6, 2015 14 Ad Hoc On-demand Distance Vector (AODVv2) Routing 15 draft-ietf-manet-aodvv2-10 17 Abstract 19 The revised Ad Hoc On-demand Distance Vector (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 January 7, 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 . . . . . . . . . . . . . . . . . . . 10 62 4. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 11 63 4.1. Interface List . . . . . . . . . . . . . . . . . . . . . 11 64 4.2. Router Client List . . . . . . . . . . . . . . . . . . . 11 65 4.3. Neighbor Table . . . . . . . . . . . . . . . . . . . . . 12 66 4.4. Sequence Numbers . . . . . . . . . . . . . . . . . . . . 13 67 4.5. Multicast Route Message Table . . . . . . . . . . . . . . 14 68 4.6. Route Table Entry . . . . . . . . . . . . . . . . . . . . 15 69 5. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 70 5.1. Cost Function . . . . . . . . . . . . . . . . . . . . . . 17 71 5.2. LoopFree Function . . . . . . . . . . . . . . . . . . . . 18 72 5.3. Default Metric Type . . . . . . . . . . . . . . . . . . . 18 73 5.4. Alternate Metric Types . . . . . . . . . . . . . . . . . 19 74 6. AODVv2 Protocol Operations . . . . . . . . . . . . . . . . . 19 75 6.1. Initialization . . . . . . . . . . . . . . . . . . . . . 19 76 6.2. Adjacency Monitoring . . . . . . . . . . . . . . . . . . 20 77 6.3. Message Transmission . . . . . . . . . . . . . . . . . . 22 78 6.4. Route Discovery, Retries and Buffering . . . . . . . . . 22 79 6.5. Processing Received Route Information . . . . . . . . . . 24 80 6.5.1. Evaluating Route Information . . . . . . . . . . . . 25 81 6.5.2. Applying Route Updates . . . . . . . . . . . . . . . 26 82 6.6. Suppressing Redundant Messages . . . . . . . . . . . . . 28 83 6.7. Route Maintenance . . . . . . . . . . . . . . . . . . . . 29 84 6.7.1. Route State . . . . . . . . . . . . . . . . . . . . . 29 85 6.7.2. Reporting Invalid Routes . . . . . . . . . . . . . . 31 86 7. AODVv2 Protocol Messages . . . . . . . . . . . . . . . . . . 31 87 7.1. Route Request (RREQ) Message . . . . . . . . . . . . . . 31 88 7.1.1. RREQ Generation . . . . . . . . . . . . . . . . . . . 33 89 7.1.2. RREQ Reception . . . . . . . . . . . . . . . . . . . 34 90 7.1.3. RREQ Regeneration . . . . . . . . . . . . . . . . . . 35 91 7.2. Route Reply (RREP) Message . . . . . . . . . . . . . . . 36 92 7.2.1. RREP Generation . . . . . . . . . . . . . . . . . . . 38 93 7.2.2. RREP Reception . . . . . . . . . . . . . . . . . . . 39 94 7.2.3. RREP Regeneration . . . . . . . . . . . . . . . . . . 41 95 7.3. Route Reply Acknowledgement (RREP_Ack) Message . . . . . 42 96 7.3.1. RREP_Ack Generation . . . . . . . . . . . . . . . . . 42 97 7.3.2. RREP_Ack Reception . . . . . . . . . . . . . . . . . 42 98 7.4. Route Error (RERR) Message . . . . . . . . . . . . . . . 43 99 7.4.1. RERR Generation . . . . . . . . . . . . . . . . . . . 44 100 7.4.2. RERR Reception . . . . . . . . . . . . . . . . . . . 46 101 7.4.3. RERR Regeneration . . . . . . . . . . . . . . . . . . 47 102 8. RFC 5444 Representation . . . . . . . . . . . . . . . . . . . 48 103 8.1. RREQ . . . . . . . . . . . . . . . . . . . . . . . . . . 49 104 8.1.1. Message Header . . . . . . . . . . . . . . . . . . . 49 105 8.1.2. Message TLV Block . . . . . . . . . . . . . . . . . . 49 106 8.1.3. Address Block . . . . . . . . . . . . . . . . . . . . 49 107 8.1.4. Address Block TLV Block . . . . . . . . . . . . . . . 50 108 8.2. RREP . . . . . . . . . . . . . . . . . . . . . . . . . . 51 109 8.2.1. Message Header . . . . . . . . . . . . . . . . . . . 51 110 8.2.2. Message TLV Block . . . . . . . . . . . . . . . . . . 51 111 8.2.3. Address Block . . . . . . . . . . . . . . . . . . . . 51 112 8.2.4. Address Block TLV Block . . . . . . . . . . . . . . . 51 113 8.3. RREP_Ack . . . . . . . . . . . . . . . . . . . . . . . . 52 114 8.3.1. Message Header . . . . . . . . . . . . . . . . . . . 52 115 8.3.2. Message TLV Block . . . . . . . . . . . . . . . . . . 53 116 8.3.3. Address Block . . . . . . . . . . . . . . . . . . . . 53 117 8.3.4. Address Block TLV Block . . . . . . . . . . . . . . . 53 118 8.4. RERR . . . . . . . . . . . . . . . . . . . . . . . . . . 53 119 8.4.1. Message Header . . . . . . . . . . . . . . . . . . . 53 120 8.4.2. Message TLV Block . . . . . . . . . . . . . . . . . . 53 121 8.4.3. Address Block . . . . . . . . . . . . . . . . . . . . 53 122 8.4.4. Address Block TLV Block . . . . . . . . . . . . . . . 54 123 9. Simple Internet Attachment . . . . . . . . . . . . . . . . . 55 124 10. Optional Features . . . . . . . . . . . . . . . . . . . . . . 56 125 10.1. Expanding Rings Multicast . . . . . . . . . . . . . . . 56 126 10.2. Precursor Lists . . . . . . . . . . . . . . . . . . . . 56 127 10.3. Intermediate RREP . . . . . . . . . . . . . . . . . . . 57 128 10.4. Message Aggregation Delay . . . . . . . . . . . . . . . 58 129 11. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 58 130 11.1. Timers . . . . . . . . . . . . . . . . . . . . . . . . . 58 131 11.2. Protocol Constants . . . . . . . . . . . . . . . . . . . 59 132 11.3. Local Settings . . . . . . . . . . . . . . . . . . . . . 60 133 11.4. Network-Wide Settings . . . . . . . . . . . . . . . . . 60 134 11.5. Optional Feature Settings . . . . . . . . . . . . . . . 60 135 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 61 136 12.1. RFC 5444 Message Types . . . . . . . . . . . . . . . . . 61 137 12.2. RFC 5444 Address Block TLV Types . . . . . . . . . . . . 61 138 12.3. MetricType Allocation . . . . . . . . . . . . . . . . . 62 139 12.4. AddressType Allocation . . . . . . . . . . . . . . . . . 62 140 13. Security Considerations . . . . . . . . . . . . . . . . . . . 63 141 14. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 65 142 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 66 143 15.1. Normative References . . . . . . . . . . . . . . . . . . 66 144 15.2. Informative References . . . . . . . . . . . . . . . . . 66 146 Appendix A. Features Required of IP . . . . . . . . . . . . . . 67 147 Appendix B. Multi-homing Considerations . . . . . . . . . . . . 68 148 Appendix C. Router Client Relocation . . . . . . . . . . . . . . 68 149 Appendix D. Example Algorithms for AODVv2 Operations . . . . . . 68 150 D.1. General Operations . . . . . . . . . . . . . . . . . . . 70 151 D.1.1. Check_Route_State . . . . . . . . . . . . . . . . . . 70 152 D.1.2. Process_Routing_Info . . . . . . . . . . . . . . . . 71 153 D.1.3. Fetch_Route_Table_Entry . . . . . . . . . . . . . . . 72 154 D.1.4. Update_Route_Table_Entry . . . . . . . . . . . . . . 73 155 D.1.5. Create_Route_Table_Entry . . . . . . . . . . . . . . 74 156 D.1.6. LoopFree . . . . . . . . . . . . . . . . . . . . . . 74 157 D.1.7. Fetch_Rte_Msg_Table_Entry . . . . . . . . . . . . . . 75 158 D.1.8. Update_Rte_Msg_Table . . . . . . . . . . . . . . . . 75 159 D.1.9. Build_RFC_5444_Message_Header . . . . . . . . . . . . 76 160 D.2. RREQ Operations . . . . . . . . . . . . . . . . . . . . . 77 161 D.2.1. Generate_RREQ . . . . . . . . . . . . . . . . . . . . 77 162 D.2.2. Receive_RREQ . . . . . . . . . . . . . . . . . . . . 78 163 D.2.3. Regenerate_RREQ . . . . . . . . . . . . . . . . . . . 80 164 D.3. RREP Operations . . . . . . . . . . . . . . . . . . . . . 81 165 D.3.1. Generate_RREP . . . . . . . . . . . . . . . . . . . . 81 166 D.3.2. Receive_RREP . . . . . . . . . . . . . . . . . . . . 82 167 D.3.3. Regenerate_RREP . . . . . . . . . . . . . . . . . . . 83 168 D.4. RREP_Ack Operations . . . . . . . . . . . . . . . . . . . 85 169 D.4.1. Generate_RREP_Ack . . . . . . . . . . . . . . . . . . 85 170 D.4.2. Receive_RREP_Ack . . . . . . . . . . . . . . . . . . 85 171 D.4.3. Timeout_RREP_Ack . . . . . . . . . . . . . . . . . . 85 172 D.5. RERR Operations . . . . . . . . . . . . . . . . . . . . . 85 173 D.5.1. Generate_RERR . . . . . . . . . . . . . . . . . . . . 85 174 D.5.2. Receive_RERR . . . . . . . . . . . . . . . . . . . . 87 175 D.5.3. Regenerate_RERR . . . . . . . . . . . . . . . . . . . 88 176 Appendix E. AODVv2 Draft Updates . . . . . . . . . . . . . . . . 90 177 E.1. Changes between revisions 9 and 10 . . . . . . . . . . . 90 178 E.2. Changes between revisions 8 and 9 . . . . . . . . . . . . 90 179 E.3. Changes between revisions 7 and 8 . . . . . . . . . . . . 93 180 E.4. Changes between revisions 6 and 7 . . . . . . . . . . . . 94 181 E.5. Changes between revisions 5 and 6 . . . . . . . . . . . . 95 182 E.6. Changes between revisions 4 and 5 . . . . . . . . . . . . 96 183 E.7. Changes between revisions 3 and 4 . . . . . . . . . . . . 97 184 E.8. Changes between revisions 2 and 3 . . . . . . . . . . . . 98 185 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 99 187 1. Overview 189 The revised Ad hoc On-demand Distance Vector (AODVv2) routing 190 protocol [formerly named DYMO] enables on-demand, multihop unicast 191 routing among AODVv2 routers in mobile ad hoc networks [MANETs] 192 [RFC2501]. The basic operations of the AODVv2 protocol are route 193 discovery and route maintenance. 195 Route discovery is performed when an AODVv2 router needs to forward a 196 packet for one of its clients, but does not have a valid route to the 197 packet's destination. AODVv2 routers use Route Request (RREQ) and 198 Route Reply (RREP) messages to carry route information between the 199 originator of the route discovery and the target node, establishing a 200 route to both endpoints on all intermediate routers. 202 A metric is included in RREQ and RREP messages to represent the cost 203 of the route to the originator or target of the route discovery. 204 AODVv2 compares route metrics in a way that ensures loop avoidance. 205 AODVv2 also uses sequence numbers to assure loop freedom, enabling 206 identification of stale routing information so that it can be 207 discarded. 209 Route maintenance involves monitoring the router's links and routes 210 for changes. This includes confirming adjacencies with other AODVv2 211 routers, issuing Route Error messages if link failures invalidate 212 routes, extending and enforcing route timeouts, and reacting to 213 received Route Error messages. 215 AODVv2 control plane messages use the Generalized MANET Packet/ 216 Message Format defined in [RFC5444] and the parameters in [RFC5498]. 217 AODVv2 defines a set of data elements which map to RFC 5444 Address 218 Blocks, Address Block TLVs, and Message TLVs. 220 Security for authentication of AODVv2 routers and encryption of 221 control messages is dealt with by using the recommendations in 222 [RFC7182]. 224 2. Terminology 226 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 227 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 228 "OPTIONAL" in this document are to be interpreted as described in 229 [RFC2119]. In addition, this document uses terminology from 230 [RFC5444], and defines the following terms: 232 AddressList 233 An AODVv2 Data Element (see Table 1). 235 Adjacency 236 A bi-directional relationship between neighboring AODVv2 routers 237 for the purpose of exchanging routing information. 239 AckReq 240 An AODVv2 Data Element (see Table 1). 242 AODVv2 Router 243 An IP addressable device in the ad hoc network that performs the 244 AODVv2 protocol operations specified in this document. 246 CurrentTime 247 The current time as maintained by the AODVv2 router. 249 Data Element 250 A named object used within AODVv2 protocol messages (see Table 1). 252 Disregard 253 Ignore for further processing. 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 (see Table 1). 264 MetricTypeList 265 An AODVv2 Data Element (see Table 1). 267 Node 268 An IP addressable device in the ad hoc network. All nodes in this 269 document are either AODVv2 Routers or Router Clients. 271 OrigAddr (Originator Address) 272 An AODVv2 Data Element (see Table 1). 274 OrigMetric 275 An AODVv2 Data Element (see Table 1). 277 OrigNode (Originating Node) 278 The node that launched the application requiring communication 279 with the Target Address. 281 OrigPrefixLen 282 The prefix length, in bits, associated with OrigAddr. 284 OrigSeqNum 285 An AODVv2 Data Element (see Table 1). 287 PktSource 288 An AODVv2 Data Element (see Table 1). 290 PrefixLengthList 291 An AODVv2 Data Element (see Table 1). 293 Reactive 294 A protocol operation is called "reactive" if it is performed only 295 in reaction to specific events. In this document, "reactive" is 296 synonymous with "on-demand". 298 RERR (Route Error) 299 The AODVv2 message type used to indicate that an AODVv2 router 300 does not have a route toward one or more particular destinations. 302 RERR_Gen (RERR Generating Router) 303 The AODVv2 router generating a Route Error message. 305 Routable Unicast IP Address 306 A routable unicast IP address is a unicast IP address that is 307 scoped sufficiently to be forwarded by a router. Globally-scoped 308 unicast IP addresses and Unique Local Addresses (ULAs) ([RFC4193]) 309 are examples of routable unicast IP addresses. 311 Router Client 312 A node that requires the services of an AODVv2 router. An AODVv2 313 router is also its own client. 315 RREP (Route Reply) 316 The AODVv2 message type used to reply to a Route Request message. 318 RREP_Gen (RREP Generating Router) 319 The AODVv2 router responsible for the Target Node of a Route 320 Request message, i.e., the router that creates the Route Reply 321 message. 323 RREQ (Route Request) 324 The AODVv2 message type used to discover a route to the Target 325 Address and distribute information about the route to the 326 Originator Address. 328 RREQ_Gen (RREQ Generating Router) 329 The AODVv2 router that creates the Route Request message on behalf 330 of the Originating Node to discover a route for Target Address. 332 RteMsg (Route Message) 333 A Route Request (RREQ) or Route Reply (RREP) message. 335 Sequence Number (SeqNum) 336 One of the sequence numbers maintained by an AODVv2 router to 337 indicate freshness of route information. Used as an AODVv2 Data 338 Element (see Table 1). 340 SeqNumList 341 An AODVv2 Data Element (see Table 1). 343 TargAddr (Target Address) 344 An AODVv2 Data Element (see Table 1). 346 Target Node 347 The node hosting the IP address toward which a route is needed. 349 TargMetric 350 An AODVv2 Data Element (see Table 1). 352 TargPrefixLen 353 The prefix length, in bits, associated with TargAddr. 355 TargSeqNum 356 An AODVv2 Data Element (see Table 1). 358 Unreachable Address 359 An address for which a valid route is not known. 361 Upstream 362 In the direction from destination to source (from TargAddr to 363 OrigAddr). 365 Valid route 366 A route that can be used for forwarding. 368 ValidityTime 369 An AODVv2 Data Element (see Table 1). 371 This document defines a set of Data Elements in Table 1 which are 372 used in AODVv2 messages. These data elements contain the message 373 data which is transferred into RFC 5444 formatted messages 374 (Section 8) before sending. 376 +------------------+------------------------------------------------+ 377 | Data Element | Meaning | 378 +------------------+------------------------------------------------+ 379 | AckReq | Presence in RREP means acknowledgement is | 380 | | requested from the router with the address | 381 | | indicated | 382 | AddressList | A list of IP addresses | 383 | MetricType | The metric type for a metric value | 384 | MetricTypeList | Metric types associated with routes to | 385 | | addresses in AddressList, used in RERR | 386 | msg_hop_limit | Number of hops the message is allowed to | 387 | | traverse | 388 | msg_hop_count | Number of hops traversed so far by the message | 389 | OrigMetric | Metric value associated with the route to | 390 | | OrigAddr | 391 | OrigSeqNum | Sequence number associated with OrigAddr, used | 392 | | in RREQ | 393 | OrigAddr | IP address of the Originating Node, the source | 394 | | address of the packet triggering route | 395 | | discovery | 396 | PktSource | Source address of a packet triggering a RERR | 397 | | message | 398 | PrefixLengthList | A list of routing prefixes associated with | 399 | | addresses in AddressList | 400 | SeqNum | Sequence number, when used in RERR | 401 | SeqNumList | A list of generic sequence numbers associated | 402 | | with addresses in an AddressList, used in RERR | 403 | TargAddr | IP address of the Target Node, the destination | 404 | | address for which a route is requested | 405 | TargMetric | Metric value associated with the route to | 406 | | TargAddr | 407 | TargSeqNum | Sequence number associated with TargAddr, used | 408 | | in RREQ (optional) and RREP | 409 | ValidityTime | Length of time a route is offered | 410 +------------------+------------------------------------------------+ 412 Table 1: Data Elements 414 This document uses the notational conventions in Table 2 to simplify 415 the text. 417 +----------------------+--------------------------------------------+ 418 | Notation | Meaning | 419 +----------------------+--------------------------------------------+ 420 | Route[Address] | A route table entry toward Address | 421 | Route[Address].Field | A field in a route table entry toward | 422 | | Address | 423 | RteMsg | Either RREQ or RREP | 424 | RteMsg.Field | A field in either RREQ or RREP | 425 | AdvRte | A route advertised in an incoming RteMsg | 426 +----------------------+--------------------------------------------+ 428 Table 2: Notational Conventions 430 3. Applicability Statement 432 The AODVv2 routing protocol is a reactive routing protocol designed 433 for stub or disconnected mobile ad hoc networks, i.e., non-transit 434 networks or those not connected to the internet. 436 AODVv2 handles a wide variety of mobility and traffic patterns by 437 determining routes on-demand. In networks with a large number of 438 routers, AODVv2 is best suited for relatively sparse traffic 439 scenarios where each router forwards packets to a small percentage of 440 other AODVv2 routers in the network. In this case fewer routes are 441 needed, and therefore less control traffic is produced. 443 AODVv2 is well suited to reactive scenarios such as emergency and 444 disaster relief, where the ability to communicate is more important 445 than being assured of secure operations. For other ad hoc networking 446 applications, in which insecure operation could negate the value of 447 establishing communication paths, it is important for neighboring 448 AODVv2 nodes to establish security associations with one another. 450 AODVv2 will not make use of uni-directional links. Route requests 451 from routers which cannot confirm bidirectional connectivity should 452 be ignored to avoid persistent packet loss or protocol failures. 454 AODVv2 is applicable to memory constrained devices, since only a 455 little routing state is maintained in each AODVv2 router. In 456 contrast to proactive routing protocols, which maintain routing 457 information for all destinations within the MANET, AODVv2 routes that 458 are not needed for forwarding data do not need to be maintained. On 459 routers unable to store persistent AODVv2 state, recovery can impose 460 a performance penalty (e.g., in case of AODVv2 router reboot). 462 AODVv2 supports routers with multiple interfaces, as long as each 463 interface configured for AODVv2 has its own unicast routable IP 464 address. Address assignment procedures are out of scope for AODVv2. 466 Multi-homing is not supported by AODVv2, and therefore a Router 467 Client SHOULD NOT be served by more than one AODVv2 router at any one 468 time. Appendix B contains some notes on this topic. 470 Although AODVv2 is closely related to AODV [RFC3561], and shares some 471 features of DSR [RFC4728], AODVv2 is not interoperable with either of 472 those protocols. 474 The routing algorithm in AODVv2 may be operated at layers other than 475 the network layer, using layer-appropriate addresses. 477 AODVv2 can be configured to perform gateway functions when attached 478 to the internet. Such a gateway router is referred to as an Internet 479 AODVv2 Router (IAR) as discussed in Section 9. The IAR will reply to 480 each route request generated inside the AODVv2 network for an 481 internet destination as if they were responsible for the target 482 address, and may advertise the AODVv2 network to the internet using 483 procedures out of scope for this specification. 485 4. Data Structures 487 4.1. Interface List 489 A list of the interfaces supporting AODVv2 should be configured in 490 the AODVv2_INTERFACES list. 492 4.2. Router Client List 494 An AODVv2 router may provide routing services for its own local 495 applications and for other non-routing nodes that are directly 496 reachable via its network interfaces. These nodes, including the 497 AODVv2 router itself, are referred to as Router Clients. 499 Each AODVv2 router MUST be configured with information about the IP 500 addresses of its clients. If a subnet is configured as a Router 501 Client, the AODVv2 router MUST serve every node in that subnet. 503 A CLIENT_ADDRESSES list should exist to store information about 504 Router Clients, with the following information: 506 RouterClient.IPAddress 507 The IP address of the client node or subnet that requires routing 508 services from the AODVv2 router. 510 RouterClient.PrefixLength 511 The length, in bits, of the routing prefix associated with the 512 client IP address or subnet. 514 The list of Router Clients for an AODVv2 router is never empty, since 515 an AODVv2 router is always its own client. The IP Addresses of the 516 router's interfaces will appear in the Router Client list. 518 The router MUST respond to Route Requests for all Router Clients. In 519 the initial state, an AODVv2 router is not required to have 520 information about the Router Clients of any other AODVv2 router. 522 A Router Client SHOULD NOT be served by more than one AODVv2 router 523 at any one time. Shifting responsibility for a Router Client to a 524 different AODVv2 router is discussed in Appendix C. 526 4.3. Neighbor Table 528 A neighbor table MUST be maintained with information about 529 neighboring AODVv2 routers, including an indication of the state of 530 the adjacency to the router. Section 6.2 discusses how to monitor 531 adjacency. 533 Neighboring routers which cannot confirm adjacency should be marked 534 as blacklisted. Certain AODVv2 messages received from a blacklisted 535 router should be ignored. Routers should be blacklisted for a 536 maximum of MAX_BLACKLIST_TIME, but can be removed from the blacklist 537 before this time if an indication of adjacency is received. 539 Neighbor entries should contain: 541 Neighbor.IPAddress 542 An IP address of the neighboring router. 544 Neighbor.State 545 The state of the adjacency (Confirmed, Unknown, or Blacklisted) 547 Neighbor.ResetTime 548 The time at which this router SHOULD no longer be considered 549 blacklisted. By default this value is calculated at the time the 550 router is blacklisted and is equal to CurrentTime + 551 MAX_BLACKLIST_TIME. After this time, the state should be reset to 552 Unknown. While the neighbor is not marked as blacklisted, this 553 value SHOULD be set to MAX_TIME. 555 Before a neighbor is confirmed, any routes learned through that 556 neighbor are marked as Unconfirmed. When neighbor state is set to 557 Confirmed, the Unconfirmed routes using the neighbor as a next hop 558 can transition to Idle state (see Section 6.7.1). 560 If a neighbor is blacklisted, any valid routes installed which use 561 that neighbor for their next hop should become Invalid. 563 When the link to a neighbor breaks, the neighbor entry should be 564 removed and all routes using the neighbor as next hop should become 565 Invalid. 567 4.4. Sequence Numbers 569 Sequence numbers enable AODVv2 routers to determine the temporal 570 order of route discovery messages, identifying stale routing 571 information so that it can be discarded. The sequence number 572 fulfills the same roles as the "Destination Sequence Number" of DSDV 573 [Perkins94], and the AODV Sequence Number in [RFC3561]. 575 Each AODVv2 router in the network MUST maintain its own sequence 576 number as a 16-bit unsigned integer. All route messages (Route 577 Request and Route Reply messages) created by an AODVv2 router include 578 the router's sequence number. 580 If the router has multiple AODVv2 interfaces, it can maintain 581 different sequence numbers for each interface IP address, but the 582 router MUST NOT use multiple sequence numbers for any one interface 583 IP address. All route messages created on behalf of Router Clients 584 on a particular interface MUST include the sequence number of that 585 interface's IP address. 587 Each AODVv2 router MUST ensure that its sequence number is strictly 588 increasing. It can ensure this by incrementing the sequence number 589 by one (1) whenever a route message is created, except when the 590 sequence number is 65,535 (the maximum value of a 16-bit unsigned 591 integer), in which case it MUST be reset to one (1). The value zero 592 (0) is reserved to indicate that the sequence number for an address 593 is unknown. 595 A router receiving a route message uses the sequence number to 596 determine the freshness of the route information in the message in 597 comparison with any existing information about the same route. If 598 the sequence number stored in the route table is higher than the 599 sequence number in the message, the received information is 600 considered stale and MUST NOT be used to update the route table. 602 As a consequence, loop freedom is assured. 604 An AODVv2 router SHOULD maintain its sequence number(s) in persistent 605 storage. If a sequence number is lost, the router must follow the 606 procedure in Section 6.1 to safely resume routing operations with a 607 new sequence number. 609 4.5. Multicast Route Message Table 611 A route message (RteMsg) is either a Route Request and Route Reply 612 message. The Multicast Route Message Table (RteMsg Table) contains 613 information about previously received multicast route messages, so 614 that when a route message is received, an AODVv2 router can determine 615 if the incoming information is redundant, and avoid unnecessary 616 regeneration of the route message. RREQ messages are usually 617 multicast. Future extensions to AODVv2 MAY enable RREP messages to 618 be multicast. 620 Each entry in the RteMsg Table stores the following information, 621 copied from the route message: 623 RteMsg.MessageType 624 Either RREQ or RREP. 626 RteMsg.OrigAddr 627 The IP address of the originating node wishing to send a packet. 629 RteMsg.OrigPrefixLen 630 The prefix length associated with OrigAddr. 632 RteMsg.TargAddr 633 The IP address of the target node, the destination of the packet. 635 RteMsg.TargPrefixLen 636 The prefix length associated with TargAddr. 638 RteMsg.OrigSeqNum 639 The sequence number associated with the originator, if present in 640 RteMsg. 642 RteMsg.TargSeqNum 643 The sequence number associated with the target, if present in 644 RteMsg. 646 RteMsg.MetricType 647 The metric type of the route requested. 649 RteMsg.Metric 650 The metric value received in the RteMsg. 652 RteMsg.Timestamp 653 The last time this entry was updated. 655 RteMsg.RemoveTime 656 The time at which this entry MUST be removed. 658 Multicast RteMsgs are considered to be comparable if they have the 659 same MessageType, OrigAddr, TargAddr, and MetricType. The RteMsg 660 Table is maintained so that no two entries are comparable, i.e., all 661 entries either have different MessageType, different OrigAddr, 662 different TargAddr, or different MetricType. See Section 6.6 for 663 details on updating this table. 665 Entries in the RteMsg Table MUST be deleted when the sequence number 666 is no longer valid, i.e., after MAX_SEQNUM_LIFETIME. RemoveTime 667 should be set when the sequence number of the entry is updated, i.e., 668 when OrigSeqNum is updated for a RREQ, and when TargSeqNum is updated 669 for a RREP. RemoveTime should be set to CurrentTime + 670 MAX_SEQNUM_LIFETIME. Memory-constrained devices MAY remove the entry 671 before this time, but the entry should be maintained for at least 672 RteMsg_ENTRY_TIME after the last Timestamp update in order to account 673 for long-lived RREQs traversing the network. 675 4.6. Route Table Entry 677 The route table entry is a conceptual data structure. 678 Implementations MAY use any internal representation that provides 679 access to the following information: 681 Route.Address 682 An address or address prefix of a node. 684 Route.PrefixLength 685 The prefix length, in bits, associated with the address. If it is 686 less than the length of Route.Address, this is a route to the 687 subnet on which Route.Address resides. 689 Route.SeqNum 690 The sequence number associated with Route.Address, obtained from 691 the last route message that successfully updated this route table 692 entry. 694 Route.NextHop 695 An IP address of the AODVv2 router used for the next hop on the 696 path toward Route.Address. 698 Route.NextHopInterface 699 The interface used to send packets toward Route.Address. 701 Route.LastUsed 702 The time this route was last used to forward a packet. 704 Route.LastSeqNumUpdate 705 The time the sequence number for this route was last updated. 707 Route.ExpirationTime 708 The time at which this route must be marked as Invalid. 710 Route.MetricType 711 The type of metric associated with this route. 713 Route.Metric 714 The cost of the route toward Route.Address expressed in units 715 consistent with Route.MetricType. 717 Route.State 718 The last known state (Active, Idle, Invalid, or Unconfirmed) of 719 the route. 721 Route.Precursors (optional feature) 722 A list of upstream neighbors using the route (see Section 10.2). 724 There are four possible states for an AODVv2 route: 726 Active 727 An Active route is in current use for forwarding packets. 729 Idle 730 An Idle route has not been used in the last ACTIVE_INTERVAL, but 731 can still be used for forwarding packets. 733 Invalid 734 An Invalid route cannot be used for forwarding packets, but its 735 sequence number information allows incoming information to be 736 assessed for freshness. 738 Unconfirmed 739 An Unconfirmed route cannot be used for forwarding packets. It is 740 a route learned 742 from a Route Request which has not yet been confirmed as 743 bidirectional. 745 Route state changes are detailed in Section 6.7.1. 747 An AODVv2 route may be offered for a limited time. In this case, the 748 route is referred to as a timed route. The length of time for which 749 the route is valid is referred to as validity time, and is included 750 in messages which advertise the route. The shortened validity time 751 is reflected in Route.ExpirationTime. If a route is not timed, the 752 ExpirationTime is MAX_TIME, and the route will become Idle and then 753 Invalid if it is not used. Invalid routes should be maintained for 754 their sequence number information. 756 5. Metrics 758 Metrics measure a cost or quality associated with a route or a link, 759 e.g., latency, delay, financial cost, energy, etc. 761 AODVv2 enables the use of multiple metric types. Each metric that 762 can be used in AODVv2 has a MetricType number. Numbers are allocated 763 by IANA as specified in [RFC6551] or detailed in Section 12.3. The 764 default metric type is discussed in Section 5.3. Alternate metrics 765 are discussed in Section 5.4. 767 An AODVv2 implementation MAY be configured to use a limited set of 768 the supported metric types. In the processing described in 769 Section 7, a "known" MetricType can be interpreted as a configured 770 MetricType. If a message is received using an unknown or non- 771 configured MetricType it MUST be ignored. Since the message will not 772 be regenerated, other routers which do support the MetricType will 773 not be able to route through a router which does not support the 774 MetricType. 776 For each MetricType, a maximum value is defined, denoted 777 MAX_METRIC[MetricType]. AODVv2 cannot store routes that cost more 778 than MAX_METRIC[MetricType]. 780 Metric information reported in incoming route messages describes the 781 metric as measured by message sender, and does not reflect the cost 782 of traversing the link to that sender. The receiving router 783 calculates the cost of the route from its perspective. This cost is 784 used to determine whether to use incoming information to update an 785 existing route. If the cost exceeds MAX_METRIC[MetricType], the 786 route is ignored. 788 5.1. Cost Function 790 This document uses the following notation to represent costs: 792 o Cost(L) for link cost 794 o Cost(R) for route cost 796 These functions return the cost of traversing a link or a route. 797 Cost(L) and Cost(R) for the default metric type are detailed in 798 Section 5.3. The Cost() functions for other metric types are beyond 799 the scope of this document. 801 5.2. LoopFree Function 803 When comparing an advertised route to an existing route for the same 804 destination and the same metric type, the metric value should be 805 examined to ensure that using the advertised route does not create 806 any routing loops. 808 The function LoopFree(R1, R2) is defined to verify that a route R2 is 809 not a part of another route R1. LoopFree returns TRUE if R2 cannot 810 be a sub-section of the route R1. 812 An AODVv2 router invokes LoopFree() as part of the process in 813 Section 6.5.1. The advertised route (AdvRte) is used as parameter 814 R1, and the stored route (Route) is used as parameter R2. 816 The LoopFree(R1,R2) function for the default metric type is detailed 817 in Section 5.3. The LoopFree(R1,R2) functions for other metric types 818 are beyond the scope of this document. 820 5.3. Default Metric Type 822 AODVv2's default metric type (DEFAULT_METRIC_TYPE) is HopCount, and 823 is the only metric described in detail in this document. Alternate 824 metrics are discussed in Section 5.4. 826 For the HopCount metric: 828 o Cost(L) := 1 830 o Cost(R) := Sum (Cost(L) of each link in the route), i.e., the hop 831 count between the router calculating the cost, and the destination 832 of the route 834 o LoopFree(R1, R2) returns TRUE when the cost of R1 is less than or 835 equal to the cost of R2, i.e., Cost(R1) <= Cost(R2) 837 o MAX_METRIC[HopCount] := MAX_HOPCOUNT 839 The LoopFree function for the HopCount metric is derived from the 840 fact that route cost increases with number of hops. When examining 841 two routes, the route with higher cost may include the route with 842 lower cost as a sub-section of its route. Therefore, an advertised 843 route with higher cost than the corresponding stored route could 844 include the stored route as a sub-section. Replacing the stored 845 route with the received route could form a routing loop. LoopFree 846 returns FALSE in this case to indicate that an advertised route with 847 higher cost is not to be used to update a stored route, even if the 848 stored route is Invalid. 850 MAX_HOPCOUNT is a constant defined in Section 11.2. It MUST be 851 larger than the AODVv2 network diameter, in order that AODVv2 852 protocol messages may reach their intended destinations. 854 5.4. Alternate Metric Types 856 Some applications may require metric information other than hop 857 count. For this reason, AODVv2 enables route selection based on 858 alternate metric types. 860 Using non-default metrics in an AODVv2 message requires the inclusion 861 of the MetricType data element. 863 Alternate metrics may have different types and ranges, for example 864 integers or floating point numbers, or restricted subsets thereof. 865 Therefore the size of the metric field in route messages may vary. 866 See Section 12.3 for further information on MetricType number 867 allocation and size. 869 Metrics might be classified as additive, concave, convex, or 870 multiplicative as discussed in [RFC6551]. Where Cost and LoopFree 871 functions can be developed for a metric type, it can be supported by 872 AODVv2. 874 AODVv2 can support additive metrics using the Cost(R) and 875 LoopFree(R1, R2) functions defined for the default metric. 876 Furthermore, any strictly increasing metric can be supported using 877 the LoopFree function defined. It is, however, out of the scope of 878 this document to specify for alternate metrics the correct Cost(L), 879 Cost(R), and LoopFree() functions. Where possible these should take 880 into account differences in the link cost in each direction. 882 6. AODVv2 Protocol Operations 884 The AODVv2 protocol's operations include managing sequence numbers, 885 monitoring adjacent AODVv2 routers, performing route discovery and 886 dealing with requests from other routers, processing incoming route 887 information and updating the route table, suppressing redundant 888 messages, maintaining the route table and reporting broken routes. 889 These processes are discussed in detail in the following sections. 891 6.1. Initialization 893 During initialization where the previous sequence number is unknown, 894 or if the sequence number is lost at any point, an AODVv2 router 895 resets its sequence number(s) to one (1). However, other AODVv2 896 routers may still hold sequence number information this router 897 previously issued. Since sequence number information will be removed 898 if there have been no sequence number updates in MAX_SEQNUM_LIFETIME, 899 the initializing router must wait for MAX_SEQNUM_LIFETIME before it 900 creates any messages containing its sequence number. It can then be 901 sure that the information it sends will not be considered stale. 903 Until MAX_SEQNUM_LIFETIME after its sequence number is reset, the 904 router SHOULD not create RREQ or RREP messages. 906 During this wait period, the router can do the following: 908 o Process information in a received RREQ or RREP message to learn a 909 route to the originator or target 911 o Send a RREP_Ack 913 o Regenerate a received RREQ or RREP 915 o Forward data packets to Router Clients, and to other routers, if a 916 route exists 918 o Create, process and regenerate RERR messages 920 6.2. Adjacency Monitoring 922 An adjacency is a bidirectional relationship between neighboring 923 AODVv2 routers for the purpose of exchanging routing information. 924 Not every pair of neighboring routers will necessarily form an 925 adjacency, but AODVv2 routers MUST monitor connectivity to 926 neighboring AODVv2 routers along potential routes and MUST NOT 927 establish routes over uni-directional links, since packet losses are 928 likely to occur and route establishment can fail. 930 The default approach for monitoring bidirectional connectivity to the 931 next hop toward OrigAddr is to request acknowledgement of Route Reply 932 messages. Receipt of an acknowledgement proves that bidirectional 933 connectivity exists. All AODVv2 routers MUST support this process, 934 which is explained in Section 7.2 and Section 7.3. 936 Bidirectionality to the next hop toward TargAddr is confirmed by 937 receipt of the Route Reply message, since a Route Reply message is a 938 reply to a Route Request message which previously crossed the link in 939 the opposite direction. 941 When routers perform other operations such as those from the list 942 below, these can be used as additional indications of connectivity: 944 o NHDP HELLO Messages [RFC6130] 945 o Route timeout 947 o Lower layer triggers, e.g. message reception or link status 948 notifications 950 o TCP timeouts 952 o Promiscuous listening 954 o Other monitoring mechanisms or heuristics 956 For example, receipt of a Neighborhood Discovery Protocol HELLO 957 message with the receiving router listed as a neighbor is a signal of 958 bidirectional connectivity. In this case, acknowledgement of a RREP 959 message sent to that neighbor is unnecessary. Similarly, if AODVv2 960 receives notification of a timeout, this may be due to a 961 disconnection. The AODVv2 router SHOULD attempt to verify 962 connectivity by requesting acknowledgement of the next RREP sent to 963 that neighbor. 965 The Neighbor Table (Section 4.3) gives the last known state of the 966 neighbor adjacency, either Confirmed, Unknown, or Blacklisted. Until 967 bidirectionality is confirmed, the state is Unknown, and 968 acknowledgement of RREP messages MUST be requested. If the state is 969 Confirmed, the acknowledgement request is unnecessary. If 970 bidirectionality cannot be confirmed, the state is Blacklisted. 971 RREQs received from a blacklisted router, or any router over a link 972 that is known to be incoming-only, MUST be disregarded. 974 Neighbor state is updated as follows: 976 o If a link to a neighbor is determined to be unidirectional, either 977 by failure to acknowledge a RREP, or by some other means, the 978 neighbor MUST be marked as blacklisted. 980 o If a notification indicates that there may be a problem with 981 bidirectionality, and the neighbor state is currently Confirmed, 982 the state SHOULD be set to Unknown to force acknowledgement of the 983 next RREP sent to the neighbor. 985 o If an indication of bidirectional connectivity is received, the 986 neighbor state SHOULD be set to Confirmed. 988 o If the neighbor state is Blacklisted and the reset time is 989 reached, the neighbor state SHOULD be reset to Unknown and the 990 neighbor SHOULD again be allowed to participate in route 991 discovery. 993 If a link to a neighbor is determined to be broken, the neighbor 994 entry should be removed. 996 6.3. Message Transmission 998 In its default mode of operation, AODVv2 sends [RFC5444] formatted 999 messages using the parameters for port number and IP protocol 1000 specified in [RFC5498]. Mapping of AODVv2 data elements to RFC 5444 1001 is detailed in Section 8. 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 Implementations are free to choose their own heuristics for reducing 1009 multicast overhead. Some methods for doing so are described in 1010 [RFC6621]. AODVv2 does not specify which method should be used to 1011 restrict the set of AODVv2 routers that have the responsibility to 1012 regenerate multicast messages. Note that multicast messages MAY be 1013 sent via unicast. For example, this may occur for certain link-types 1014 (non-broadcast media), for manually configured router adjacencies, or 1015 in order to improve robustness. 1017 When multiple interfaces are available, a node transmitting a 1018 multicast message to LL-MANET-Routers MUST send the message on all 1019 interfaces that have been configured for AODVv2 operation, as given 1020 in the AODVv2_INTERFACES list (Section 4.1). Similarly, AODVv2 1021 routers MUST subscribe to LL-MANET-Routers on all their AODVv2 1022 interfaces. 1024 To avoid congestion, each AODVv2 router's rate of message generation 1025 (CONTROL_TRAFFIC_LIMIT) SHOULD be limited and administratively 1026 configurable. The implementation is free to choose the algorithm for 1027 limiting messages, including prioritizing messages when approaching 1028 the limit. AODVv2 messages SHOULD be discarded in the following 1029 order: RERR for invalidated routes, RREQ, RREP, RERR for 1030 undeliverable packet, RREP_Ack. 1032 IP packets containing AODVv2 protocol messages SHOULD be given 1033 priority queuing and channel access. 1035 6.4. Route Discovery, Retries and Buffering 1037 AODVv2's RREQ and RREP messages are used for route discovery and are 1038 together known as route messages (RteMsgs). The main difference 1039 between the two messages is that, by default, RREQ messages are 1040 multicast to solicit a RREP, whereas RREP is unicast as a response to 1041 the RREQ. The constants used in this section are defined in 1042 Section 11. 1044 When an AODVv2 router needs to forward a data packet (with source 1045 address OrigAddr and destination address TargAddr) from one of its 1046 Router Clients, it needs a route to the packet's destination. If no 1047 route exists, the AODVv2 router generates and multicasts a Route 1048 Request message (RREQ) using OrigAddr and TargAddr. The procedure 1049 for this is described in Section 7.1.1. The AODVv2 router is 1050 referred to as RREQ_Gen. 1052 Data packets awaiting a route MAY be buffered by RREQ_Gen. Buffering 1053 of data packets can have both positive and negative effects (albeit 1054 usually positive). Real-time traffic, voice, and scheduled delivery 1055 may suffer if packets are buffered and subjected to delays, but TCP 1056 connection establishment will benefit if packets are queued while 1057 route discovery is performed. 1059 The packet buffer is configured with a fixed limited size of 1060 BUFFER_SIZE_PACKETS or BUFFER_SIZE_BYTES. Determining which packets 1061 to discard first when the buffer is full is a matter of policy at 1062 each AODVv2 router. Nodes without sufficient memory available for 1063 buffering SHOULD have buffering disabled by configuring 1064 BUFFER_SIZE_PACKETS := 0 and BUFFER_SIZE_BYTES := 0. This will 1065 affect the latency for launching TCP applications to new 1066 destinations. 1068 RREQ_Gen awaits reception of a Route Reply message (RREP) containing 1069 a route toward TargAddr. A RREQ from TargAddr would also fulfil the 1070 request, if adjacency to the next hop is already confirmed. If a 1071 route to TargAddr is not learned within RREQ_WAIT_TIME, RREQ_Gen MAY 1072 retry the route discovery by generating another RREQ with a new 1073 sequence number. To reduce congestion in a network, repeated 1074 attempts at route discovery for a particular target address SHOULD 1075 utilize a binary exponential backoff, as described in [RFC3561], 1076 where the wait time is doubled for each retry. 1078 The RREQ is received by neighboring AODVv2 routers, and processed and 1079 regenerated as described in Section 7.1. Intermediate routers learn 1080 a potential route to OrigAddr from the RREQ. The router responsible 1081 for TargAddr responds by generating a Route Reply message (RREP) and 1082 sends it back toward RREQ_Gen using the route to OrigAddr learned 1083 from the RREQ. Each intermediate router regenerates the RREP and 1084 unicasts toward OrigAddr. 1086 Links which are not bidirectional cause problems. If a RREP is not 1087 received at an intermediate router, the RREP cannot be regenerated 1088 and will never reach RREQ_Gen. However, since routers monitor 1089 adjacencies (Section 6.2), the loss of the RREP will cause the last 1090 router which regenerated the RREP to blacklist the router which did 1091 not receive it. When a timeout occurs at RREQ_Gen, a new RREQ may be 1092 regenerated. When the new RREQ arrives again via the blacklisted 1093 router, it will be ignored, and the RREQ should discover a different 1094 path. 1096 Route discovery SHOULD be considered to have failed after 1097 DISCOVERY_ATTEMPTS_MAX and the corresponding wait time for a RREP 1098 response to the final RREQ. After the attempted route discovery has 1099 failed, RREQ_Gen MUST wait at least RREQ_HOLDDOWN_TIME before 1100 attempting another route discovery to the same destination. Any data 1101 packets buffered for TargAddr MUST also be dropped and a Destination 1102 Unreachable ICMP message (Type 3) with a code of 1 (Host Unreachable 1103 Error) SHOULD be delivered to the source of the data packet. The 1104 source may be an application on RREQ_Gen itself, or on a Router 1105 Client with address OrigAddr. 1107 If RREQ_Gen does receive a route message containing a route to 1108 TargAddr within the timeout, it processes the message according to 1109 Section 7. When a valid route is installed, the router can begin 1110 sending the buffered packets. Any retry timers for the corresponding 1111 RREQ SHOULD be cancelled. 1113 During route discovery, all routers on the path learn a route to both 1114 OrigAddr and TargAddr, making the constructed route bidirectional. 1116 6.5. Processing Received Route Information 1118 All AODVv2 route messages contain a route. A Route Request (RREQ) 1119 includes a route to OrigAddr, and a Route Reply (RREP) contains a 1120 route to TargAddr. 1122 All AODVv2 routers that receive a route message can store the route 1123 contained within it. Incoming information is first checked to verify 1124 that it is both safe to use and offers an improvement to existing 1125 information. This process is explained in Section 6.5.1. The route 1126 table may then be updated according to Section 6.5.2. 1128 In the processes below, RteMsg is used to denote the route message, 1129 AdvRte is used to denote the route contained within it, and Route 1130 denotes a stored routing table entry which matches AdvRte. 1132 AdvRte has the following properties: 1134 o AdvRte.Address := RteMsg.OrigAddr (in RREQ) or RteMsg.TargAddr (in 1135 RREP) 1137 o AdvRte.PrefixLength := RteMsg.OrigPrefixLen (in RREQ) or 1138 RteMsg.TargPrefixLen (in RREP) if included, or if no prefix length 1139 was included in RteMsg, the address length, in bits, of 1140 AdvRte.Address 1142 o AdvRte.SeqNum := RteMsg.OrigSeqNum (in RREQ) or RteMsg.TargSeqNum 1143 (in RREP) 1145 o AdvRte.NextHop := IP.SourceAddress (the address of the router from 1146 which the AdvRte was received) 1148 o AdvRte.MetricType := RteMsg.MetricType if included, or 1149 DEFAULT_METRIC_TYPE if not 1151 o AdvRte.Metric := RteMsg.Metric 1153 o AdvRte.Cost := Cost(R) using the cost function associated with the 1154 route's metric type, where L is the link from the advertising 1155 router, i.e. Cost(R) = AdvRte.Metric + Cost(L) for the default 1156 metric type 1158 o AdvRte.ValidityTime := RteMsg.ValidityTime, if included 1160 If prefix length information is present, the route describes the 1161 subnet on which the address resides. 1163 6.5.1. Evaluating Route Information 1165 To determine whether the advertised route should be used to update 1166 the routing table, the incoming route information MUST be processed 1167 as follows: 1169 1. Search for a routing table entry (Route) matching AdvRte's 1170 address, prefix length and metric type 1172 * If no matching route exists, AdvRte SHOULD be used to update 1173 the routing table. Multiple routes to the same destination 1174 may exists with different metric types. 1176 * If all matching routes have State set to Unconfirmed, AdvRte 1177 SHOULD be used to update the routing table, so that it 1178 contains multiple Unconfirmed routes. If an Unconfirmed route 1179 becomes valid in future, any remaining Unconfirmed routes 1180 which would not offer improvement will be expunged. 1182 * If a matching route exists with State set to Active, Idle, or 1183 Invalid, continue to Step 2. 1185 2. Compare sequence numbers 1187 * If AdvRte is more recent (AdvRte.SeqNum > Route.SeqNum), 1188 AdvRte MUST be used to update the routing table. 1190 * If AdvRte is stale (AdvRte.SeqNum < Route.SeqNum), AdvRte MUST 1191 NOT be used to update the routing table. 1193 * If the sequence numbers are equal, continue to Step 3. 1195 3. Check that AdvRte is safe against routing loops (see Section 5.2) 1197 * If LoopFree(AdvRte, Route) returns FALSE, AdvRte MUST NOT be 1198 used to update the routing table because using the incoming 1199 information might cause a routing loop. 1201 * If LoopFree(AdvRte, Route) returns TRUE, continue to Step 3. 1203 4. Compare route costs 1205 * For some metric types, including the default metric specified 1206 in Section 5.3, the best route is the route with the lowest 1207 metric value. For other metric types, the best route may be 1208 the route with the highest metric. 1210 * If AdvRte is better, it SHOULD be used to update the routing 1211 table because it offers improvement. 1213 * If AdvRte is not better (i.e., it is worse or equal) and Route 1214 is valid, AdvRte MUST NOT be used to update the routing table 1215 because it does not offer any improvement. 1217 * If AdvRte is not better (i.e., it is worse or equal) but Route 1218 is Invalid, AdvRte SHOULD be used to update the routing table 1219 because it can safely repair the existing Invalid route. 1221 If the advertised route SHOULD be used to update the routing table, 1222 the procedure in Section 6.5.2 is followed. 1224 6.5.2. Applying Route Updates 1226 If AdvRte is from a RREQ message, the next hop neighbor may not be 1227 confirmed as adjacent (see Section 4.3). If Neighbor.State is 1228 Unknown, the route may not be viable, but it MUST be stored to allow 1229 a corresponding RREP to be sent. It SHOULD NOT yet be used to 1230 forward data. Route.State will be set to Unconfirmed to indicate 1231 this. If a valid route already exists for this destination, the 1232 Unconfirmed route should be stored as an additional entry. 1234 The route update is applied as follows: 1236 1. If no existing entry in the route table matches AdvRte on 1237 address, prefix length and metric type, continue to Step 3 and 1238 create a new route table entry. 1240 2. If a matching entry exists: 1242 * If AdvRte.NextHop is not equal to Route.NextHop, and 1243 AdvRte.NextHop's Neighbor.State is Unknown and Route.State is 1244 Active or Idle, the current route is valid but the advertised 1245 route may offer improvement, if it can be confirmed. Continue 1246 to Step 3 and create a new route table entry. It can replace 1247 the original route when Neighbor.State is set to Confirmed. 1249 * If AdvRte.NextHop's Neighbor.State is Unknown and Route.State 1250 is Invalid, continue to Step 4 and update the existing route 1251 table entry. 1253 * If AdvRte.NextHop's Neighbor.State is Confirmed, continue to 1254 Step 4 and update the existing route table entry. 1256 3. Create a route table entry and initialize as follows: 1258 * Route.Address := AdvRte.Address 1260 * Route.PrefixLength := AdvRte.PrefixLength (if included), or 1261 the length, in bits, of Route.Address (32 for IPv4 or 128 for 1262 IPv6) 1264 * Route.MetricType := AdvRte.MetricType 1266 4. Update the route table entry as follows: 1268 * Route.SeqNum := AdvRte.SeqNum 1270 * Route.NextHop := AdvRte.NextHop 1272 * Route.NextHopInterface := interface on which RteMsg was 1273 received 1275 * Route.Metric := AdvRte.Cost 1277 * Route.LastUsed := CurrentTime 1279 * Route.LastSeqNumUpdate := CurrentTime 1280 * Route.ExpirationTime := CurrentTime + AdvRte.ValidityTime if a 1281 validity time exists, otherwise MAX_TIME 1283 5. If a new route was created, or if the existing Route.State is 1284 Invalid or Unconfirmed, update as follows: 1286 * Route.State := Unconfirmed (if the next hop's Neighbor.State 1287 is Unknown) or Idle 1289 6. If an existing route changed from Invalid or Unconfirmed to 1290 become Idle, any matching inferior routes should be expunged. 1292 7. If this update results in a valid route which fulfills an 1293 outstanding route discovery, the associated timers can be 1294 cancelled and any buffered packets for this route can be 1295 forwarded. 1297 6.6. Suppressing Redundant Messages 1299 When route messages are flooded in a MANET, an AODVv2 router may 1300 receive multiple similar messages. Regenerating every one of these 1301 gives little additional benefit, and generates unnecessary signaling 1302 traffic and interference. 1304 Each AODVv2 router stores information about recently received route 1305 messages in the AODVv2 Multicast RteMsg Table (Section 4.5). 1306 Received RteMsgs are tested against previously received RteMsgs, and 1307 if determined to be redundant, regeneration can be avoided. Where 1308 necessary, regeneration is performed using the processes in 1309 Section 7. 1311 To determine if a received RREQ is redundant: 1313 1. Search for an entry in the RteMsg Table with the same 1314 MessageType, OrigAddr, TargAddr, and MetricType 1316 * If there is none, create an entry to store information about 1317 the received RREQ and regenerate the RREQ. 1319 * If there is an entry, update the timestamp field, since 1320 comparable RteMsgs are still traversing the network, and 1321 continue to Step 2. 1323 2. Compare the sequence numbers 1325 * If the entry has a lower OrigSeqNum than the received RREQ, 1326 update the entry using information from the new RREQ and 1327 regenerate the RREQ. 1329 * If the entry has a higher OrigSeqNum than the received RREQ, 1330 do not update the entry and do not regenerate the RREQ. 1332 * If the entry has the same OrigSeqNum, continue to Step 3. 1334 3. Compare the metric values 1336 * If the entry has a Metric that is worse than the received 1337 RREQ, update the entry using information from the new RREQ. 1339 * If the entry has a Metric that is better than the received 1340 RREQ, do not update the entry. 1342 * In both cases, the RREQ MAY be suppressed to avoid extra 1343 control traffic. However, if the processing of the RREQ 1344 results in an update to the route table, the RREQ MAY be 1345 regenerated to ensure other routers have up-to-date 1346 information. 1348 6.7. Route Maintenance 1350 Route maintenance involves monitoring and updating route state, 1351 handling route timeouts and reporting routes that become Invalid. 1353 Before using a route to forward a packet, an AODVv2 router MUST check 1354 the status of the route (Section 6.7.1). If the route is valid, it 1355 MUST be marked as Active and its LastUsed timestamp MUST be updated, 1356 before forwarding the packet to the route's next hop. If there is no 1357 valid route, this MUST be reported to the packet's source (see 1358 Section 6.7.2). 1360 6.7.1. Route State 1362 During normal operation, AODVv2 does not require any explicit 1363 timeouts to manage the lifetime of a route. At any time, any route 1364 table entry can be examined and updated according to the rules below. 1365 Route state should be checked before packet forwarding and before any 1366 operation based on route state. 1368 The four possible states for an AODVv2 route are Active, Idle, 1369 Invalid, and Unconfirmed, as defined in Section 4.6. 1371 Active 1372 If an Active route is not timed (i.e., its ExpirationTime is 1373 MAX_TIME), it becomes Idle if not used within ACTIVE_INTERVAL. A 1374 timed route (i.e., a route with ExpirationTime not equal to 1375 MAX_TIME) remains Active until its expiration time, after which it 1376 MAY either be expunged or marked as Invalid. 1378 Idle 1379 An Idle route becomes Active if it is used to forward a packet. 1380 If not used, an Idle route remains idle for MAX_IDLETIME before 1381 becoming an Invalid route. 1383 Invalid 1384 An Invalid route MAY be maintained until MAX_SEQNUM_LIFETIME after 1385 the last sequence number update. This allows incoming information 1386 to be assessed for freshness. After this time it should be 1387 expunged. 1389 Unconfirmed 1390 An Unconfirmed route becomes Idle when adjacency with the next hop 1391 router is confirmed, or will be expunged if the neighbor is 1392 blacklisted, or at MAX_SEQNUM_LIFETIME after the last sequence 1393 number update. 1395 In all cases, if the time since the route's last sequence number 1396 update exceeds MAX_SEQNUM_LIFETIME, the sequence number must be 1397 removed from the route. If the route is Invalid or Unconfirmed at 1398 this time, it MUST be expunged. Active and Idle routes can continue 1399 to be used to forward packets. The removal of the sequence number is 1400 required to ensure that any AODVv2 routers following the 1401 initialization procedure can safely begin routing functions using a 1402 new sequence number. 1404 Appendix D.1.1 contains an algorithmic representation of this timeout 1405 behavior. 1407 Routes can become Invalid before a timeout occurs: 1409 o If a link breaks, all routes using that link as the next hop MUST 1410 immediately be marked as Invalid. 1412 o If a Route Error (RERR) message containing the route is received 1413 from the route's next hop, the route MUST immediately be marked as 1414 Invalid. 1416 When an Unconfirmed route is set as Idle as a result of the adjacency 1417 with Route.NextHop being Confirmed (see Section 4.3), any inferior 1418 matching routes MUST be expunged. 1420 Memory constrained devices MAY choose to expunge routes from the 1421 AODVv2 route table before their expiration time, but MUST adhere to 1422 the following rules: 1424 o An Active route MUST NOT be expunged. 1426 o An Idle route SHOULD NOT be expunged. 1428 o Any Invalid route MAY be expunged; least recently used Invalid 1429 routes SHOULD be expunged first. 1431 o An Unconfirmed route MUST NOT be expunged if it was installed 1432 within the last RREQ_WAIT_TIME. Otherwise, it MAY be expunged. 1434 6.7.2. Reporting Invalid Routes 1436 When an Active route becomes Invalid as a result of a broken link or 1437 a received Route Error (RERR) message, other routers should be 1438 informed by sending a RERR message containing details of the 1439 invalidated route. 1441 A RERR message should also be sent when an AODVv2 router receives a 1442 packet to forward on behalf of another router but does not have a 1443 valid route for the destination of the packet. This packet may be a 1444 data packet or, in rare cases, a RREP message, if the route to the 1445 request originator has been lost. The packet or message triggering 1446 the RERR MUST be discarded. 1448 Generation of a RERR message is described in Section 7.4.1. 1450 7. AODVv2 Protocol Messages 1452 AODVv2 defines four message types: Route Request (RREQ), Route Reply 1453 (RREP), Route Reply Acknowledgement (RREP_Ack), and Route Error 1454 (RERR). 1456 Each AODVv2 message is defined as a set of data elements. Rules for 1457 the generation, reception and regeneration of each message type are 1458 described in the following sections. Section 8 discusses how the 1459 data elements map to RFC 5444 Message TLVs, Address Blocks, and 1460 Address TLVs. 1462 7.1. Route Request (RREQ) Message 1464 Route Request messages are used in route discovery operations to 1465 request a route to a specified target address. RREQ messages have 1466 the following general structure: 1468 +-----------------------------------------------------------------+ 1469 | msg_hop_limit, (optional) msg_hop_count | 1470 +-----------------------------------------------------------------+ 1471 | AddressList | 1472 +-----------------------------------------------------------------+ 1473 | PrefixLengthList (optional) | 1474 +-----------------------------------------------------------------+ 1475 | OrigSeqNum, (optional) TargSeqNum | 1476 +-----------------------------------------------------------------+ 1477 | MetricType (optional) | 1478 +-----------------------------------------------------------------+ 1479 | OrigMetric | 1480 +-----------------------------------------------------------------+ 1481 | ValidityTime (optional) | 1482 +-----------------------------------------------------------------+ 1484 Figure 1: RREQ message structure 1486 RREQ Data Elements 1488 msg_hop_limit 1489 The remaining number of hops allowed for dissemination of the 1490 RREQ message. 1492 msg_hop_count 1493 The number of hops already traversed during dissemination of 1494 the RREQ message. 1496 AddressList 1497 Contains OrigAddr and TargAddr, the source and destination 1498 addresses of the packet for which a route is requested. 1499 OrigAddr and TargAddr MUST be routable unicast addresses. 1501 PrefixLengthList 1502 Contains OrigPrefixLen, i.e., the length, in bits, of the 1503 prefix associated with OrigAddr. If omitted, the prefix length 1504 is equal to OrigAddr's address length in bits. If OrigAddr 1505 resides on a subnet configured as a Router Client, the prefix 1506 length represents the number of bits in the subnet mask. 1508 OrigSeqNum 1509 The sequence number associated with OrigAddr. 1511 TargSeqNum 1512 A sequence number associated with TargAddr. This may be 1513 included if an Invalid route exists to the target. This is 1514 useful for the optional Intermediate RREP feature (see 1515 Section 10.3). 1517 MetricType 1518 The type of metric associated with OrigMetric. This element 1519 can be omitted if the default metric type is used. 1521 OrigMetric 1522 The metric associated with the route to OrigAddr, as measured 1523 by the sender of the message. 1525 ValidityTime 1526 The length of time that the message sender is willing to offer 1527 a route toward OrigAddr. Omitted if no time limit is imposed. 1529 7.1.1. RREQ Generation 1531 A RREQ is generated when a packet needs to be forwarded for a Router 1532 Client, and no valid route currently exists for the packet's 1533 destination. 1535 Before creating a RREQ, the router should check if a RREQ has 1536 recently been sent for the requested destination. If so, and the 1537 wait time for a reply has not yet been reached, the router should 1538 continue to await a response without generating a new RREQ. If the 1539 timeout has been reached, a new RREQ may be generated. If buffering 1540 is configured, the incoming packet SHOULD be buffered until the route 1541 discovery is completed. 1543 If the limit for the rate of AODVv2 control message generation has 1544 been reached, no message should be generated. 1546 To generate the RREQ, the router (referred to as RREQ_Gen) follows 1547 this procedure: 1549 1. Set msg_hop_limit := MAX_HOPCOUNT 1551 2. Set msg_hop_count := 0, if including it 1553 3. Set AddressList := {OrigAddr, TargAddr} 1555 4. For the PrefixLengthList: 1557 * If OrigAddr resides on a Router Client subnet, set 1558 PrefixLengthList := {OrigPrefixLen, null}. 1560 * Otherwise, omit PrefixLengthList. 1562 5. For OrigSeqNum: 1564 * Increment the SeqNum associated with OrigAddr as specified in 1565 Section 4.4. 1567 * Set OrigSeqNum := SeqNum. 1569 6. For TargSeqNum: 1571 * If an Invalid route exists matching TargAddr using longest 1572 prefix matching and has a valid sequence number, set 1573 TargSeqNum := route's sequence number. 1575 * If no Invalid route exists matching TargAddr, or the route 1576 doesn't have a sequence number, omit TargSeqNum. 1578 7. Include the MetricType data element if requesting a route for a 1579 non-default metric type, and set the type accordingly 1581 8. Set OrigMetric := Route[OrigAddr].Metric 1583 9. Include the ValidityTime data element if advertising that the 1584 route to OrigAddr via this router is offered for a limited time, 1585 and set ValidityTime accordingly 1587 This AODVv2 message is used to create a corresponding RFC 5444 1588 message (see Section 8) which is multicast, by default, to LL-MANET- 1589 Routers on all interfaces configured for AODVv2 operation. 1591 7.1.2. RREQ Reception 1593 Upon receiving a RREQ, an AODVv2 router performs the following steps: 1595 1. If the sender is blacklisted (Section 4.3), check the entry's 1596 reset time 1598 * If CurrentTime < Remove Time, ignore this RREQ for further 1599 processing. 1601 * If CurrentTime >= Remove Time, reset the neighbor state to 1602 Unknown and continue to Step 2. 1604 2. Verify that the message hop count, if included, hasn't exceeded 1605 MAX_HOPCOUNT 1607 * If so, ignore this RREQ for further processing. 1609 3. Verify that the message contains the required data elements: 1610 msg_hop_limit, OrigAddr, TargAddr, OrigSeqNum, and OrigMetric, 1611 and that OrigAddr and TargAddr are valid addresses (routable and 1612 unicast) 1614 * If not, ignore this RREQ for further processing. 1616 4. If the MetricType data element is present, check that the metric 1617 type is known 1619 * If not, ignore this RREQ for further processing. 1621 5. Verify that the cost of the advertised route will not exceed the 1622 maximum allowed metric value for the metric type (Metric <= 1623 MAX_METRIC[MetricType] - Cost(L)) 1625 * If it will, ignore this RREQ for further processing. 1627 6. Process the route to OrigAddr as specified in Section 6.5.1 1629 7. Check if the message is redundant by comparing to entries in the 1630 RteMsg table (Section 6.6) 1632 * If redundant, ignore this RREQ for further processing. 1634 * If not redundant, save the information in the RteMsg table to 1635 identify future duplicates and continue processing. 1637 8. Check if the TargAddr belongs to one of the Router Clients 1639 * If so, generate a RREP as specified in Section 7.2.1. 1641 * If not, continue to RREQ regeneration. 1643 7.1.3. RREQ Regeneration 1645 By regenerating a RREQ, a router advertises that it will forward 1646 packets to the OrigAddr contained in the RREQ according to the 1647 information enclosed. The router MAY choose not to regenerate the 1648 RREQ, though this could decrease connectivity in the network or 1649 result in non-optimal paths. The full set of circumstances under 1650 which a router may avoid regenerating a RREQ are not declared in this 1651 document, though examples include the router being heavily loaded or 1652 low on energy and therefore unwilling to advertise routing capability 1653 for more traffic. 1655 The RREQ should not be regenerated if the limit for the rate of 1656 AODVv2 control message generation has been reached. 1658 The procedure for RREQ regeneration is as follows: 1660 1. Set msg_hop_limit := received msg_hop_limit - 1 1662 2. If msg_hop_limit is now zero, do not continue the regeneration 1663 process 1665 3. Set msg_hop_count := received msg_hop_count + 1, if included, 1666 otherwise omit msg_hop_count 1668 4. Set AddressList, PrefixLengthList, sequence numbers and 1669 MetricType to the values in the received RREQ 1671 5. Set OrigMetric := Route[OrigAddr].Metric 1673 6. If the received RREQ contains a ValidityTime, or if the 1674 regenerating router wishes to limit the time that it offers a 1675 route to OrigAddr, the regenerated RREQ MUST include a 1676 ValidityTime data element 1678 * The ValidityTime is either the ValidityTime the previous 1679 AODVv2 router specified, or the ValidityTime this router 1680 wishes to impose, whichever is lower. 1682 This AODVv2 message is used to create a corresponding RFC 5444 1683 message (see Section 8) which is multicast, by default, to LL-MANET- 1684 Routers on all interfaces configured for AODVv2 operation. However, 1685 the regenerated RREQ can be unicast to the next hop address of the 1686 route toward TargAddr, if known. 1688 7.2. Route Reply (RREP) Message 1690 A Route Reply message is sent in response to a Route Request message 1691 and offers a route to the Target Address in the RREQ. 1693 The RREP is sent by unicast to the next hop router on the route to 1694 OrigAddr, if there is a Confirmed entry in the Neighbor Table for the 1695 next hop. Otherwise, the RREP is sent multicast to LL-MANET-Routers, 1696 including the AckReq data element in the message to indicate the 1697 intended next hop address and request acknowledgement to confirm the 1698 neighbor adjacency. 1700 RREP messages have the following general structure: 1702 +-----------------------------------------------------------------+ 1703 | msg_hop_limit, (optional) msg_hop_count | 1704 +-----------------------------------------------------------------+ 1705 | AckReq (optional) | 1706 +-----------------------------------------------------------------+ 1707 | AddressList | 1708 +-----------------------------------------------------------------+ 1709 | PrefixLengthList (optional) | 1710 +-----------------------------------------------------------------+ 1711 | TargSeqNum | 1712 +-----------------------------------------------------------------+ 1713 | MetricType (optional) | 1714 +-----------------------------------------------------------------+ 1715 | TargMetric | 1716 +-----------------------------------------------------------------+ 1717 | ValidityTime (optional) | 1718 +-----------------------------------------------------------------+ 1720 Figure 2: RREP message structure 1722 RREP Data Elements 1724 msg_hop_limit 1725 The remaining number of hops allowed for dissemination of the 1726 RREP message. 1728 msg_hop_count 1729 The number of hops already traversed during dissemination of 1730 the RREP message. 1732 AckReq 1733 The address of the intended next hop of the RREP. This data 1734 element is used when the RREP is multicast because the next hop 1735 toward OrigAddr is a neighbor with Unknown state. It indicates 1736 that an acknowledgement to the RREP is requested by the sender 1737 from the intended next hop (see Section 6.2). 1739 AddressList 1740 Contains OrigAddr and TargAddr, the source and destination 1741 addresses of the packet for which a route is requested. 1742 OrigAddr and TargAddr MUST be routable unicast addresses. 1744 PrefixLengthList 1745 Contains TargPrefixLen, i.e., the length, in bits, of the 1746 prefix associated with TargAddr. If omitted, the prefix length 1747 is equal to TargAddr's address length, in bits. If TargAddr 1748 resides on a subnet configured as a Router Client, the prefix 1749 length represents the number of bits in the subnet mask. 1751 TargSeqNum 1752 The sequence number associated with TargAddr. 1754 MetricType 1755 The type of metric associated with TargMetric. This element 1756 can be omitted if the default metric type is used. 1758 TargMetric 1759 The metric associated with the route to TargAddr, as seen from 1760 the sender of the message. 1762 ValidityTime 1763 The length of time that the message sender is willing to offer 1764 a route toward TargAddr. Omitted if no time limit is imposed. 1766 7.2.1. RREP Generation 1768 A RREP is generated when a RREQ arrives for one of the AODVv2 1769 router's Router Clients. 1771 Before creating a RREP, the router should check if the corresponding 1772 RREQ is redundant, i.e., a response has already been generated, or if 1773 the limit for the rate of AODVv2 control message generation has been 1774 reached. If so, the RREP should not be created. 1776 If the next hop neighbor on the route to OrigAddr is not yet 1777 confirmed as adjacent (as described in Section 6.2), the RREP MUST 1778 include an AckReq data element including the intended next hop 1779 address, in order to perform adjacency monitoring. If the adjacency 1780 is already confirmed, it can be omitted. The AckReq data element 1781 indicates that an acknowledgement to the RREP is requested from the 1782 intended next hop router in the form of a Route Reply Acknowledgement 1783 (RREP_Ack). 1785 Implementations may allow a number of retries of the RREP if an 1786 acknowledgement is not received within RREP_Ack_SENT_TIMEOUT, 1787 doubling the timeout with each retry, up to a maximum of 1788 RREP_RETRIES, using the same exponential backoff described in 1789 Section 6.4 for RREQ retries. Adjacency confirmation MUST be 1790 considered to have failed after the wait time for a RREP_Ack response 1791 to the final RREP. The next hop router MUST be marked as blacklisted 1792 (Section 4.3), and any installed routes with next hop set to the 1793 newly blacklisted router should become Invalid. 1795 To generate the RREP, the router (also referred to as RREP_Gen) 1796 follows this procedure: 1798 1. Set msg_hop_limit := msg_hop_count from the received RREQ 1799 message, if it was included, or MAX_HOPCOUNT if it was not 1800 included 1802 2. Set msg_hop_count := 0, if including it 1804 3. If adjacency with the next hop toward OrigAddr is not already 1805 confirmed, include the AckReq data element with the address of 1806 the intended next hop router 1808 4. Set Address List := {OrigAddr, TargAddr} 1810 5. For the PrefixLengthList: 1812 * If TargAddr resides on a Router Client subnet, set 1813 PrefixLengthList := {null, TargPrefixLen}. 1815 * Otherwise, omit PrefixLengthList. 1817 6. For the TargSeqNum: 1819 * Increment the SeqNum associated with TargAddr as specified in 1820 Section 4.4. 1822 * Set TargSeqNum := SeqNum. 1824 7. Include the MetricType data element if the route requested is for 1825 a non-default metric type, and set the type accordingly 1827 8. Set TargMetric := Route[TargAddr].Metric 1829 9. Include the ValidityTime data element if advertising that the 1830 route to TargAddr via this router is offered for a limited time, 1831 and set ValidityTime accordingly 1833 This AODVv2 message is used to create a corresponding RFC 5444 1834 message (see Section 8). If there is a Confirmed entry in the 1835 Neighbor Table for the next hop router on the route to OrigAddr, the 1836 RREP is sent by unicast to the next hop. Otherwise, the RREP is sent 1837 multicast to LL-MANET-Routers. 1839 7.2.2. RREP Reception 1841 Upon receiving a RREP, an AODVv2 router performs the following steps: 1843 1. If the sender is blacklisted (Section 4.3), but the RREP answers 1844 a recently sent RREQ, the sender state should be set to 1845 Confirmed since a RREP is an indication of adjacency 1847 2. Verify that the message hop count, if included, hasn't exceeded 1848 MAX_HOPCOUNT 1850 * If so, ignore this RREQ for further processing. 1852 3. Verify that the message contains the required data elements: 1853 msg_hop_limit, OrigAddr, TargAddr, TargSeqNum, and TargMetric, 1854 and that OrigAddr and TargAddr are valid addresses (routable and 1855 unicast) 1857 * If not, ignore this RREP for further processing. 1859 4. If the MetricType data element is present, check that the metric 1860 type is known 1862 * If not, ignore this RREP for further processing. 1864 5. Verify that the cost of the advertised route will not exceed the 1865 maximum allowed metric value for the metric type (Metric <= 1866 MAX_METRIC[MetricType] - Cost(L)) 1868 * If it will, ignore this RREP for further processing. 1870 6. If the AckReq data element is present, check the intended 1871 recipient of the received RREP 1873 * If the receiving router is the intended recipient, send an 1874 acknowledgement as specified in Section 7.3 and continue 1875 processing. 1877 * If the receiving router is not the intended recipient, ignore 1878 this RREP for further processing. 1880 7. Process the route to TargAddr as specified in Section 6.5.1 1882 * If the route to TargAddr fulfills a previously sent RREQ, any 1883 associated timeouts will be cancelled and buffered packets 1884 will be forwarded to TargAddr, but processing continues to 1885 Step 8. 1887 8. Check if the message is redundant by comparing to entries in the 1888 RteMsg table (Section 6.6) 1890 * If redundant, ignore this RREP for further processing. 1892 * If not redundant, save the information in the RteMsg table to 1893 identify future redundant RREP messages and continue 1894 processing. 1896 9. Check if the OrigAddr belongs to one of the Router Clients 1898 * If so, no further processing is necessary. 1900 10. Check if a valid (Active or Idle) or Unconfirmed route exists to 1901 OrigAddr 1903 * If so, continue to RREP regeneration. 1905 * If not, a Route Error message SHOULD be transmitted to 1906 TargAddr according to Section 7.4.1 and the RREP should be 1907 discarded and not regenerated. 1909 7.2.3. RREP Regeneration 1911 A received Route Reply message is regenerated toward OrigAddr. 1912 Unless the router is prepared to advertise the route contained within 1913 the received RREP, it halts processing. By regenerating a RREP, a 1914 router advertises that it will forward packets to TargAddr according 1915 to the information enclosed. The router MAY choose not to regenerate 1916 the RREP, in the same way it may choose not to regenerate a RREQ (see 1917 Section 7.1.3), though this could decrease connectivity in the 1918 network or result in non-optimal paths. 1920 The RREP should not be regenerated if the limit for the rate of 1921 AODVv2 control message generation has been reached. 1923 If the next hop neighbor on the route to OrigAddr is not yet 1924 confirmed as adjacent (as described in Section 6.2), the RREP MUST 1925 include an AckReq data element including the intended next hop 1926 address, in order to perform adjacency monitoring. If the adjacency 1927 is already confirmed, the AckReq data element can be omitted. The 1928 AckReq data element indicates that an acknowledgement to the RREP is 1929 requested in the form of a Route Reply Acknowledgement (RREP_Ack) 1930 from the intended next hop router. 1932 The procedure for RREP regeneration is as follows: 1934 1. Set msg_hop_limit := received msg_hop_limit - 1 1936 2. If msg_hop_limit is now zero, do not continue the regeneration 1937 process 1939 3. Set msg_hop_count := received msg_hop_count + 1, if it was 1940 included, otherwise omit msg_hop_count 1942 4. If an adjacency with the next hop toward OrigAddr is not already 1943 confirmed, include the AckReq data element with the address of 1944 the intended next hop router 1946 5. Set AddressList, PrefixLengthList, TargSeqNum and MetricType to 1947 the values in the received RREP 1949 6. Set TargMetric := Route[TargAddr].Metric 1951 7. If the received RREP contains a ValidityTime, or if the 1952 regenerating router wishes to limit the time that it will offer a 1953 route to TargAddr, the regenerated RREP MUST include a 1954 ValidityTime data element 1956 * The ValidityTime is either the ValidityTime the previous 1957 AODVv2 router specified, or the ValidityTime this router 1958 wishes to impose, whichever is lower. 1960 This AODVv2 message is used to create a corresponding RFC 5444 1961 message (see Section 8). If there is a Confirmed entry in the 1962 Neighbor Table for the next hop router on the route to OrigAddr, the 1963 RREP is sent by unicast to the next hop. Otherwise, the RREP is sent 1964 multicast to LL-MANET-Routers. 1966 7.3. Route Reply Acknowledgement (RREP_Ack) Message 1968 The Route Reply Acknowledgement MUST be sent in response to a 1969 received Route Reply which includes an AckReq data element with an 1970 address matching one of the receiving router's IP addresses. When 1971 the RREP_Ack message is received, it confirms the adjacency between 1972 the two routers. The RREP_Ack has no data elements. 1974 7.3.1. RREP_Ack Generation 1976 A RREP_Ack MUST be generated when a received RREP includes the AckReq 1977 data element with the address of the receiving router. The RREP_Ack 1978 should not be generated if the limit for the rate of AODVv2 control 1979 message generation has been reached. 1981 There are no data elements in a RREP_Ack. The RFC 5444 1982 representation is discussed in Section 8. The RREP_Ack is unicast, 1983 by default, to the IP address of the router that requested it. 1985 7.3.2. RREP_Ack Reception 1987 Upon receiving a RREP_Ack, an AODVv2 router performs the following 1988 steps: 1990 1. If a RREP_Ack message was expected from the IP source address of 1991 the RREP_Ack, the router cancels any associated timeouts 1993 2. If the RREP_Ack was expected, ensure the router sending the 1994 RREP_Ack is marked with state Confirmed in the Neighbor 1995 Table (Section 4.3) 1997 7.4. Route Error (RERR) Message 1999 A Route Error message is generated by an AODVv2 router to notify 2000 other AODVv2 routers of routes that are no longer available. A RERR 2001 message has the following general structure: 2003 +-----------------------------------------------------------------+ 2004 | msg_hop_limit | 2005 +-----------------------------------------------------------------+ 2006 | PktSource (optional) | 2007 +-----------------------------------------------------------------+ 2008 | AddressList | 2009 +-----------------------------------------------------------------+ 2010 | PrefixLengthList (optional) | 2011 +-----------------------------------------------------------------+ 2012 | SeqNumList (optional) | 2013 +-----------------------------------------------------------------+ 2014 | MetricTypeList (optional) | 2015 +-----------------------------------------------------------------+ 2017 Figure 3: RERR message structure 2019 RERR Data Elements 2021 msg_hop_limit 2022 The remaining number of hops allowed for dissemination of the 2023 RERR message. 2025 PktSource 2026 The source IP address of the packet triggering the RERR. If 2027 the RERR is triggered by a broken link, the PktSource data 2028 element is not required. 2030 AddressList 2031 The addresses of the routes no longer available through 2032 RERR_Gen. 2034 PrefixLengthList 2035 The prefix lengths, in bits, associated with the routes no 2036 longer available through RERR_Gen, indicating whether a route 2037 represents a single device or a subnet. 2039 SeqNumList 2040 The sequence numbers of the routes no longer available through 2041 RERR_Gen (where known). 2043 MetricTypeList 2044 The types of metric associated with the routes no longer 2045 available through RERR_Gen. This element can be omitted if all 2046 routes use the default metric type. 2048 7.4.1. RERR Generation 2050 A RERR is generated when an AODVv2 router (also referred to as 2051 RERR_Gen) needs to report that a destination is no longer reachable. 2052 There are two events that cause this response: 2054 o If a packet arrives that cannot be forwarded because no valid 2055 route exists for its destination, the RERR generated MUST contain 2056 the PktSource data element and will contain only one unreachable 2057 address. The contents of PktSource and AddressList depend on the 2058 packet that triggered the RERR: 2060 * If the packet is a data packet forwarded by another AODVv2 2061 router, PktSource is set to the source IP address of the 2062 packet, and the AddressList contains the destination IP address 2063 of the packet. 2065 * If the packet contains a RREP message and the route to OrigAddr 2066 has been lost, PktSource is set to the TargAddr of the RREP, 2067 and the AddressList contains the OrigAddr from the RREP. 2069 The prefix length and sequence number MAY be included if known 2070 from an Invalid route entry to the destination of the packet. The 2071 MetricTypeList MAY also be included if a MetricType can be 2072 determined from the packet itself, or if an Invalid route exists 2073 for the packet's destination and the metric type is not 2074 DEFAULT_METRIC_TYPE. 2076 RERR_Gen MUST discard the packet or message that triggered 2077 generation of the RERR. 2079 In order to avoid flooding the network with RERR messages when a 2080 stream of packets to an unreachable address arrives, an AODVv2 2081 router SHOULD determine whether a RERR has recently been sent with 2082 the same unreachable address and PktSource, and SHOULD avoid 2083 creating duplicate RERR messages. 2085 o When a link breaks, multiple routes may become Invalid, and the 2086 RERR generated MAY contain multiple unreachable addresses. If the 2087 message contents would cause the MTU to be exceeded, multiple RERR 2088 messages must be sent. The RERR MUST include the MetricTypeList 2089 data element when it contains routes which do not use the 2090 DEFAULT_METRIC_TYPE. The PktSource data element is omitted. 2092 All previously Active routes that used the broken link MUST be 2093 reported. The AddressList, PrefixLengthList, SeqNumList, and 2094 MetricTypeList will contain entries for each route which has 2095 become Invalid. 2097 A RERR message is only sent if an Active route becomes Invalid, 2098 though an AODVv2 router can also include Idle routes that become 2099 Invalid if the configuration parameter ENABLE_IDLE_IN_RERR is set 2100 (see Section 11.3). 2102 Incidentally, if an AODVv2 router receives an ICMP error packet to or 2103 from the address of one of its Router Clients, it simply forwards the 2104 ICMP packet in the same way as any other data packet, and will not 2105 generate any RERR message based on the contents of the ICMP packet. 2107 The RERR should not be generated if the limit for the rate of AODVv2 2108 control message generation has been reached. 2110 To generate the RERR, the router follows this procedure: 2112 1. Set msg_hop_limit := MAX_HOPCOUNT 2114 2. If necessary, include the PktSource data element and set the 2115 value to the source address of the packet triggering the RERR 2117 3. For each route that needs to be reported, while respecting the 2118 interface MTU: 2120 * Insert the route address into the AddressList. 2122 * Insert the prefix length into PrefixLengthList, if known and 2123 not equal to the address length. 2125 * Insert the sequence number into SeqNumList, if known. 2127 * Insert the metric type into MetricTypeList, if known and not 2128 equal to DEFAULT_METRIC_TYPE. 2130 4. If interface MTU would be exceeded, create additional RERR 2131 messages 2133 The AODVv2 message is used to create a corresponding RFC 5444 message 2134 (see Section 8). 2136 If the RERR is sent in response to an undeliverable packet or 2137 message, it SHOULD be sent unicast to the next hop on the route to 2138 PktSource, or alternatively it MUST be multicast to LL-MANET-Routers. 2140 If the RERR is sent in response to a broken link, the RERR is, by 2141 default, multicast to LL-MANET-Routers. 2143 If the optional precursor lists feature (see Section 10.2) is 2144 enabled, the RERR is unicast to the precursors of the routes being 2145 reported. 2147 7.4.2. RERR Reception 2149 Upon receiving a RERR, an AODVv2 router performs the following steps: 2151 1. Verify that the message contains the required data elements: 2152 msg_hop_limit and at least one unreachable address 2154 * If not, ignore this RREP for further processing. 2156 2. For each address in the AddressList, check that: 2158 * The address is valid (routable and unicast) 2160 * The MetricType, if present, is known (assume 2161 DEFAULT_METRIC_TYPE if not present) 2163 * There is a valid route with the same MetricType matching the 2164 address using longest prefix matching 2166 * Either the route's next hop is the sender of the RERR and 2167 route's next hop interface is the interface on which the RERR 2168 was received, or PktSource is present in the RERR and is a 2169 Router Client address 2171 * The unreachable address' sequence number is either unknown, or 2172 is greater than the route's sequence number 2174 If any of the above are false, the route does not need to be made 2175 Invalid and the unreachable address does not need to be 2176 advertised in a regenerated RERR. 2178 If all of the above are true: 2180 * If the route's prefix length is the same as the unreachable 2181 address' prefix length, set the route state to Invalid, and 2182 note that the route should be advertised in a regenerated 2183 RERR. 2185 * If the prefix length is shorter than the original route, the 2186 route MUST be expunged from the routing table, since it is a 2187 sub-route of the larger route which is reported to be Invalid. 2189 * If the prefix length is different, create a new route with the 2190 unreachable address, and its prefix and sequence number, set 2191 the state to Invalid, and note that the route should be 2192 advertised in a regenerated RERR. 2194 * Update the sequence number on the stored route, if the 2195 reported sequence number is greater. 2197 3. If PktSource is included and is a Router Client, do not 2198 regenerate the RERR. 2200 4. Check if there are unreachable addresses which need to be 2201 advertised in a regenerated RERR 2203 * If so, regenerate the RERR as detailed in Section 7.4.3. 2205 * If not, take no further action. 2207 7.4.3. RERR Regeneration 2209 The RERR should not be generated if the limit for the rate of AODVv2 2210 control message generation has been reached. 2212 The procedure for RERR regeneration is as follows: 2214 1. Set msg_hop_limit := received msg_hop_limit - 1 2216 2. If msg_hop_limit is now zero, do not continue the regeneration 2217 process 2219 3. If the PktSource data element was included in the original RERR, 2220 copy it into the regenerated RERR 2222 4. For each route that needs to be reported, while respecting the 2223 interface MTU: 2225 * Insert the unreachable address into the AddressList. 2227 * Insert the prefix length into PrefixLengthList, if known and 2228 not equal to the address length. 2230 * Insert the sequence number into SeqNumList, if known. 2232 * Insert the MetricType into MetricTypeList if known, and not 2233 equal to DEFAULT_METRIC_TYPE. 2235 5. If interface MTU would be exceeded, create additional RERR 2236 messages 2238 The AODVv2 message is used to create a corresponding RFC 5444 message 2239 (see Section 8). If the RERR contains the PktSource data element, 2240 the regenerated RERR SHOULD be sent unicast to the next hop on the 2241 route to PktSource, or alternatively it MUST be multicast to LL- 2242 MANET-Routers. If the RERR is sent in response to a broken link, the 2243 RERR is, by default, multicast to LL-MANET-Routers. 2245 8. RFC 5444 Representation 2247 AODVv2 specifies that all control plane messages between routers 2248 SHOULD use the Generalized Mobile Ad Hoc Network Packet/Message 2249 Format [RFC5444], and therefore AODVv2 defines route messages 2250 comprising data elements that map to message elements in RFC 5444. 2252 RFC 5444 provides a multiplexed transport for multiple protocols. An 2253 RFC 5444 multiplexer may choose to optimize the content of certain 2254 message elements to reduce control plane overhead. 2256 A brief summary of the RFC 5444 format: 2258 1. A packet contains zero or more messages 2260 2. A message contains a Message Header, one Message TLV Block, zero 2261 or more Address Blocks, and one Address Block TLV Block per 2262 Address Block 2264 3. The Message TLV Block MAY contain zero or more Message TLVs 2266 4. An Address Block TLV Block MAY include zero or more Address Block 2267 TLVs 2269 5. Each TLV value in an Address Block TLV Block can be associated 2270 with all of the addresses, a contiguous set of addresses, or a 2271 single address in the Address Block 2273 AODVv2 does not require access to the RFC 5444 packet header. 2275 In the message header, AODVv2 uses , , 2276 and . indicates the 2277 length of any addresses in the message (using := 2278 address length in octets - 1, i.e. 3 for IPv4 and 15 for IPv6). 2280 Each address included in the Address Block is identified as OrigAddr, 2281 TargAddr, PktSource, or Unreachable Address by including an 2282 ADDRESS_TYPE TLV in the Address Block TLV Block. 2284 The addresses in an Address Block may appear in any order, and values 2285 in a TLV in the Address Block TLV Block must be associated with the 2286 correct address in the Address Block. To indicate which value is 2287 associated with each address, the AODVv2 message representation uses 2288 lists where the order of the addresses in the AODVv2 AddressList data 2289 element matches the order of values in other list-based data 2290 elements, e.g., the order of SeqNums in the SeqNumList in a RERR. 2292 The following sections show how AODVv2 data elements are represented 2293 in RFC 5444 messages. See Section 12 for more information about the 2294 Message TLVs and Address Block TLVs AODVv2 defines, and the type 2295 numbers allocated. 2297 Where the extension type of a TLV is set to zero, this is the default 2298 RFC 5444 value and the extension type will not be included in the 2299 message. 2301 8.1. RREQ 2303 8.1.1. Message Header 2305 +---------------+-----------------+---------------------------------+ 2306 | Data Element | Header Field | Value | 2307 +---------------+-----------------+---------------------------------+ 2308 | None | | RREQ | 2309 | msg_hop_limit | | MAX_HOPCOUNT | 2310 | msg_hop_count | | Number of hops traversed so far | 2311 | | | by the message. | 2312 +---------------+-----------------+---------------------------------+ 2314 8.1.2. Message TLV Block 2316 A RREQ contains no Message TLVs. 2318 8.1.3. Address Block 2320 A RREQ contains two Addresses, OrigAddr and TargAddr, and each 2321 address has an associated prefix length. If the prefix length has 2322 not been included in the AODVv2 message, it is equal to the address 2323 length in bits. 2325 +-------------------------+------------------------------+ 2326 | Data Elements | Address Block | 2327 +-------------------------+------------------------------+ 2328 | OrigAddr/OrigPrefixLen |
+ | 2329 | TargAddr/TargPrefixLen |
+ | 2330 +-------------------------+------------------------------+ 2332 8.1.4. Address Block TLV Block 2334 Address Block TLVs are always associated with addresses in the 2335 Address Block. The following sections show the TLVs that apply to 2336 each address. 2338 8.1.4.1. Address Block TLVs for OrigAddr 2340 +--------------+---------------+------------+-----------------------+ 2341 | Data Element | TLV Type | Extension | Value | 2342 | | | Type | | 2343 +--------------+---------------+------------+-----------------------+ 2344 | None | ADDRESS_TYPE | 0 | ADDRTYPE_ORIGADDR | 2345 | OrigSeqNum | SEQ_NUM | 0 | Sequence Number of | 2346 | | | | RREQ_Gen, the router | 2347 | | | | which initiated route | 2348 | | | | discovery. | 2349 | OrigMetric | PATH_METRIC | MetricType | Metric for the route | 2350 | /MetricType | | | to OrigAddr, using | 2351 | | | | MetricType. | 2352 | ValidityTime | VALIDITY_TIME | 0 | ValidityTime for | 2353 | | | | route to OrigAddr. | 2354 +--------------+---------------+------------+-----------------------+ 2356 In the AODVv2 representation, if the message relates to 2357 DEFAULT_METRIC_TYPE, MetricType is not included in the message. The 2358 RFC 5444 representation will set the extension type in the 2359 PATH_METRIC TLV to 0. AODVv2 interprets a MetricType of 0 as 2360 DEFAULT_METRIC_TYPE. 2362 8.1.4.2. Address Block TLVs for TargAddr 2364 +------------+--------------+-------------+-------------------------+ 2365 | Data | TLV Type | Extension | Value | 2366 | Element | | Type | | 2367 +------------+--------------+-------------+-------------------------+ 2368 | None | ADDRESS_TYPE | 0 | ADDRTYPE_TARGADDR | 2369 | TargSeqNum | SEQ_NUM | 0 | The last known | 2370 | | | | TargSeqNum for | 2371 | | | | TargAddr. | 2372 +------------+--------------+-------------+-------------------------+ 2374 8.2. RREP 2376 8.2.1. Message Header 2378 +---------------+-----------------+---------------------------------+ 2379 | Data Element | Header Field | Value | 2380 +---------------+-----------------+---------------------------------+ 2381 | None | | RREP | 2382 | msg_hop_limit | | from | 2383 | | | corresponding RREQ. | 2384 | msg_hop_count | | Number of hops traversed so far | 2385 | | | by the message. | 2386 +---------------+-----------------+---------------------------------+ 2388 8.2.2. Message TLV Block 2390 A RREP contains no Message TLVs. 2392 8.2.3. Address Block 2394 A RREP contains a minimum of two Addresses, OrigAddr and TargAddr, 2395 and each address has an associated prefix length. If the prefix 2396 length has not been included in the AODVv2 message, it is equal to 2397 the address length in bits. 2399 It may also contain the address of the intended next hop, in order to 2400 request acknowledgement to confirm adjacency, as described in 2401 Section 6.2. The prefix length associated with this address is equal 2402 to the address length in bits. 2404 +-------------------------+------------------------------+ 2405 | Data Elements | Address Block | 2406 +-------------------------+------------------------------+ 2407 | OrigAddr/OrigPrefixLen |
+ | 2408 | TargAddr/TargPrefixLen |
+ | 2409 | AckReq |
+ | 2410 +-------------------------+------------------------------+ 2412 8.2.4. Address Block TLV Block 2414 Address Block TLVs are always associated with addresses in the 2415 Address Block. The following sections show the TLVs that apply to 2416 each address. 2418 8.2.4.1. Address Block TLVs for OrigAddr 2420 +-------------+---------------+----------------+--------------------+ 2421 | Data | TLV Type | Extension Type | Value | 2422 | Element | | | | 2423 +-------------+---------------+----------------+--------------------+ 2424 | None | ADDRESS_TYPE | 0 | ADDRTYPE_ORIGADDR | 2425 +-------------+---------------+----------------+--------------------+ 2427 8.2.4.2. Address Block TLVs for TargAddr 2429 +--------------+---------------+------------+-----------------------+ 2430 | Data Element | TLV Type | Extension | Value | 2431 | | | Type | | 2432 +--------------+---------------+------------+-----------------------+ 2433 | None | ADDRESS_TYPE | 0 | ADDRTYPE_TARGADDR | 2434 | TargSeqNum | SEQ_NUM | 0 | Sequence number of | 2435 | | | | RREP_Gen, the router | 2436 | | | | which created the | 2437 | | | | RREP. | 2438 | TargMetric | PATH_METRIC | MetricType | Metric for the route | 2439 | /MetricType | | | to TargAddr, using | 2440 | | | | MetricType. | 2441 | ValidityTime | VALIDITY_TIME | 0 | ValidityTime for | 2442 | | | | route to TargAddr. | 2443 +--------------+---------------+------------+-----------------------+ 2445 In the AODVv2 representation, if the message relates to 2446 DEFAULT_METRIC_TYPE, MetricType is not included in the message. The 2447 RFC 5444 representation will set the extension type in the 2448 PATH_METRIC TLV to 0. AODVv2 interprets a MetricType of 0 as 2449 DEFAULT_METRIC_TYPE. 2451 8.2.4.3. Address Block TLVs for AckReq Intended Recipient Address 2453 +--------------+---------------+-----------------+------------------+ 2454 | Data Element | TLV Type | Extension Type | Value | 2455 +--------------+---------------+-----------------+------------------+ 2456 | None | ADDRESS_TYPE | 0 | ADDRTYPE_INTEND | 2457 +--------------+---------------+-----------------+------------------+ 2459 8.3. RREP_Ack 2461 8.3.1. Message Header 2462 +---------------+---------------+-----------+ 2463 | Data Element | Header Field | Value | 2464 +---------------+---------------+-----------+ 2465 | None | | RREP_Ack | 2466 +---------------+---------------+-----------+ 2468 8.3.2. Message TLV Block 2470 A RREP_Ack contains no Message TLVs. 2472 8.3.3. Address Block 2474 A RREP_Ack contains no Address Block. 2476 8.3.4. Address Block TLV Block 2478 A RREP_Ack contains no Address Block TLV Block. 2480 8.4. RERR 2482 8.4.1. Message Header 2484 +----------------+------------------+---------------+ 2485 | Data Element | Header Field | Value | 2486 +----------------+------------------+---------------+ 2487 | None | | RERR | 2488 | msg_hop_limit | | MAX_HOPCOUNT | 2489 +----------------+------------------+---------------+ 2491 8.4.2. Message TLV Block 2493 A RERR contains no Message TLVs. 2495 8.4.3. Address Block 2497 The Address Block in a RERR may contain PktSource, the source IP 2498 address of the packet triggering RERR generation, as detailed in 2499 Section 7.4. Prefix Length associated with PktSource is equal to the 2500 address length in bits. 2502 Address Block always contains one Address per route that is no longer 2503 valid, and each address has an associated prefix length. If a prefix 2504 length has not been included for this address, it is equal to the 2505 address length in bits. 2507 +------------------------------+------------------------------------+ 2508 | Data Element | Address Block | 2509 +------------------------------+------------------------------------+ 2510 | PktSource |
+ for | 2511 | | PktSource | 2512 | AddressList/PrefixLengthList |
+ for | 2513 | | each unreachable address in | 2514 | | AddressList | 2515 +------------------------------+------------------------------------+ 2517 8.4.4. Address Block TLV Block 2519 Address Block TLVs are always associated with addresses in the 2520 Address Block. The following sections show the TLVs that apply to 2521 each type of address in the RERR. 2523 8.4.4.1. Address Block TLVs for PktSource 2525 +--------------+---------------+---------------+--------------------+ 2526 | Data Element | TLV Type | Extension | Value | 2527 | | | Type | | 2528 +--------------+---------------+---------------+--------------------+ 2529 | PktSource | ADDRESS_TYPE | 0 | ADDRTYPE_PKTSOURCE | 2530 +--------------+---------------+---------------+--------------------+ 2532 8.4.4.2. Address Block TLVs for Unreachable Addresses 2534 +----------------+--------------+------------+----------------------+ 2535 | Data Element | TLV Type | Extension | Value | 2536 | | | Type | | 2537 +----------------+--------------+------------+----------------------+ 2538 | None | ADDRESS_TYPE | 0 | ADDRTYPE_UNREACHABLE | 2539 | SeqNumList | SEQ_NUM | 0 | Sequence Number | 2540 | | | | associated with | 2541 | | | | invalid route to the | 2542 | | | | unreachable address. | 2543 | MetricTypeList | PATH_METRIC | MetricType | None. Extension Type | 2544 | | | | set to MetricType of | 2545 | | | | the route to the | 2546 | | | | unreachable address. | 2547 +----------------+--------------+------------+----------------------+ 2549 Using the PATH_METRIC TLV without a value is a mechanism used in RERR 2550 messages to indicate the MetricType associated with the route being 2551 reported, without the need to include a Metric value. Multiple 2552 PATH_METRIC TLVs may be necessary if routes with multiple MetricTypes 2553 are included in the RERR. 2555 In the AODVv2 representation, if the RERR message includes only 2556 routes with DEFAULT_METRIC_TYPE, MetricType is not included in the 2557 message. In this case, the RFC 5444 representation does not need to 2558 include a PATH_METRIC TLV to indicate the DEFAULT_METRIC_TYPE. If 2559 the RERR message includes both routes with DEFAULT_METRIC_TYPE and 2560 other MetricTypes, only the routes with non-default MetricType need 2561 to be marked with a PATH_METRIC TLV using Extension Type to indicate 2562 MetricType. AODVv2 interprets the absence of MetricType information 2563 as an indication of DEFAULT_METRIC_TYPE. 2565 9. Simple Internet Attachment 2567 Figure 4 shows a stub (i.e., non-transit) network of AODVv2 routers 2568 which is attached to the Internet via a single Internet AODVv2 Router 2569 (abbreviated IAR). The interface to the Internet MUST NOT be 2570 configured in the AODVv2_INTERFACES list. 2572 As in any Internet-attached network, AODVv2 routers and clients that 2573 wish to be reachable from hosts on the Internet MUST have IP 2574 addresses within the IAR's routable and topologically correct prefix 2575 (i.e., 191.0.2.0/24). This AODVv2 network and subnets within it will 2576 be advertised to the internet using procedures which are out of scope 2577 for this specification. 2579 /-------------------------\ 2580 / +----------------+ \ 2581 / | AODVv2 Router | \ 2582 | | 191.0.2.2/32 | | 2583 | +----------------+ | Routable 2584 | +-----+--------+ Prefix 2585 | | Internet | /191.0.2.0/24 2586 | | AODVv2 Router| / 2587 | | 191.0.2.1 |/ /---------------\ 2588 | | serving net +------+ Internet \ 2589 | | 191.0.2.0/24 | \ / 2590 | +-----+--------+ \---------------/ 2591 | +----------------+ | 2592 | | AODVv2 Router | | 2593 | | 191.0.2.3/32 | | 2594 \ +----------------+ / 2595 \ / 2596 \-------------------------/ 2598 Figure 4: Simple Internet Attachment Example 2600 When an AODVv2 router within the AODVv2 MANET wants to discover a 2601 route toward a node on the Internet, it uses the normal AODVv2 route 2602 discovery for that IP Destination Address. The IAR MUST respond to 2603 RREQ on behalf of all Internet destinations, i.e., destinations not 2604 on the configured 191.0.2.0/24 subnet. 2606 When a packet from a node on the Internet destined for a node in the 2607 AODVv2 MANET reaches the IAR, if the IAR does not have a route toward 2608 that exact destination it will perform normal AODVv2 route discovery 2609 for that destination. 2611 Configuring the IAR as a default router is outside the scope of this 2612 specification. 2614 10. Optional Features 2616 A number of optional features for AODVv2, associated initially with 2617 AODV, MAY be useful in networks with greater mobility or larger node 2618 populations, or networks requiring reduced latency for application 2619 launches. These features are not required by minimal 2620 implementations. 2622 10.1. Expanding Rings Multicast 2624 For multicast RREQ, msg_hop_limit MAY be set in accordance with an 2625 expanding ring search as described in [RFC3561] to limit the RREQ 2626 propagation to a subset of the local network and possibly reduce 2627 route discovery overhead. 2629 10.2. Precursor Lists 2631 This section specifies an interoperable enhancement to AODVv2 2632 enabling more economical RERR notifications. 2634 There can be several sources of traffic for a certain destination. 2635 Each source of traffic and each upstream router between the 2636 forwarding AODVv2 router and the traffic source is known as a 2637 "precursor" for the destination. For each destination, an AODVv2 2638 router MAY choose to keep track of precursors that have provided 2639 traffic for that destination. Route Error messages about that 2640 destination can be sent unicast to these precursors instead of 2641 multicast to all AODVv2 routers. 2643 Since a RERR will be regenerated if it comes from a next hop on a 2644 valid route, the RERR should ideally be sent backwards along the 2645 route that the source of the traffic uses, to ensure it is 2646 regenerated at each hop and reaches the traffic source. If the 2647 reverse path is unknown, the RERR should be sent toward the source 2648 along some other route. Therefore, the options for saving precursor 2649 information are as follows: 2651 o Save the next hop on an existing route to the packet's source 2652 address as the precursor. In this case, it is not guaranteed that 2653 a RERR that is sent will follow the reverse of the source's route. 2654 In rare situations, this may prevent the route from being 2655 invalidated at the source of the data traffic. 2657 o Save the packet's source address as the precursor. In this case, 2658 the RERR can be sent along any existing route to the source of the 2659 data traffic, and should include the PktSource data element to 2660 ensure that the route will be invalidated at the source of the 2661 traffic, in case the RERR does not follow the reverse of the 2662 source's route. 2664 o By inspecting the MAC address of each forwarded packet, determine 2665 which router forwarded the packet, and save the router address as 2666 a precursor. This ensures that when a RERR is sent to the 2667 precursor router, the route will be invalidated at that router, 2668 and the RERR will be regenerated toward the source of the packet. 2670 During normal operation, each AODVv2 router maintaining precursor 2671 lists for a route must update the precursor list whenever it uses 2672 this route to forward traffic to the destination. Precursors are 2673 classified as Active if traffic has recently been forwarded by the 2674 precursor. The precursor is marked with a timestamp to indicate the 2675 time it last forwarded traffic on this route. 2677 When an AODVv2 router detects that one or more routes are broken, it 2678 MAY notify each Active precursor using a unicast Route Error message 2679 instead of creating multicast traffic. Unicast is applicable when 2680 there are few Active precursors compared to the number of neighboring 2681 AODVv2 routers. However, the default multicast behavior is still 2682 preferable when there are many precursors, since fewer message 2683 transmissions are required. 2685 When an AODVv2 router supporting precursor lists receives a RERR 2686 message, it MAY identify the list of its own affected Active 2687 precursors for the routes in the RERR, and choose to send a unicast 2688 RERR to those, rather than send a multicast RERR. 2690 When a route is expunged, any precursor list associated with it must 2691 also be expunged. 2693 10.3. Intermediate RREP 2695 Without iRREP, only the AODVv2 router responsible for the target 2696 address can respond to a RREQ. Using iRREP, route discoveries can be 2697 faster and create less control traffic. This specification has been 2698 published as a separate Internet Draft [I-D.perkins-irrep]. 2700 10.4. Message Aggregation Delay 2702 The aggregation of multiple messages into a packet is specified in 2703 RFC 5444 [RFC5444]. 2705 Implementations MAY choose to briefly delay transmission of messages 2706 for the purpose of aggregation (into a single packet) or to improve 2707 performance by using jitter [RFC5148]. 2709 11. Configuration 2711 AODVv2 uses various parameters which can be grouped into the 2712 following categories: 2714 o Timers 2716 o Protocol constants 2718 o Administrative parameters and controls 2720 This section show the parameters along with their definitions and 2721 default values (if any). 2723 Note that several fields have limited size (bits or bytes). These 2724 sizes and their encoding may place specific limitations on the values 2725 that can be set. 2727 11.1. Timers 2729 AODVv2 requires certain timing information to be associated with 2730 route table entries and message replies. The default values are as 2731 follows: 2733 +------------------------+----------------+ 2734 | Name | Default Value | 2735 +------------------------+----------------+ 2736 | ACTIVE_INTERVAL | 5 second | 2737 | MAX_IDLETIME | 200 seconds | 2738 | MAX_BLACKLIST_TIME | 200 seconds | 2739 | MAX_SEQNUM_LIFETIME | 300 seconds | 2740 | RteMsg_ENTRY_TIME | 12 seconds | 2741 | RREQ_WAIT_TIME | 2 seconds | 2742 | RREP_Ack_SENT_TIMEOUT | 1 second | 2743 | RREQ_HOLDDOWN_TIME | 10 seconds | 2744 +------------------------+----------------+ 2746 Table 3: Timing Parameter Values 2748 The above timing parameter values have worked well for small and 2749 medium well-connected networks with moderate topology changes. The 2750 timing parameters SHOULD be administratively configurable. Ideally, 2751 for networks with frequent topology changes the AODVv2 parameters 2752 should be adjusted using experimentally determined values or dynamic 2753 adaptation. For example, in networks with infrequent topology 2754 changes MAX_IDLETIME may be set to a much larger value. 2756 11.2. Protocol Constants 2758 AODVv2 protocol constants typically do not require changes. The 2759 following table lists these constants, along with their values and a 2760 reference to the section describing their use. 2762 +------------------------+---------+--------------------------------+ 2763 | Name | Default | Description | 2764 +------------------------+---------+--------------------------------+ 2765 | DISCOVERY_ATTEMPTS_MAX | 3 | Section 6.4 | 2766 | RREP_RETRIES | 2 | Section 7.2.1 | 2767 | MAX_METRIC[MetricType] | [TBD] | Section 5 | 2768 | MAX_METRIC[HopCount] | 20 hops | Section 5 and Section 7 | 2769 | MAX_HOPCOUNT | 20 | Same as MAX_METRIC[HopCount] | 2770 | MAX_TIME | [TBD] | Maximum expressible clock time | 2771 | | | (Section 6.5.2) | 2772 +------------------------+---------+--------------------------------+ 2774 Table 4: AODVv2 Constants 2776 Note that is an 8-bit field in the RFC 5444 message 2777 header and therefore MAX_HOPCOUNT cannot be larger than 255. Field 2778 lengths associated with metrics are to be found in Section 12.3. 2780 MAX_METRIC[MetricType] MUST always be the maximum expressible metric 2781 of type MetricType. 2783 These protocol constants MUST have the same values for all AODVv2 2784 routers in the ad hoc network. If the values were configured 2785 differently, the following consequences may be observed: 2787 o DISCOVERY_ATTEMPTS_MAX: Nodes with higher values are likely to be 2788 more successful at finding routes, at the cost of additional 2789 control traffic. 2791 o RREP_RETRIES: Nodes with lower values are more likely to blacklist 2792 neighbors when there is a temporary fluctuation in link quality. 2794 o MAX_HOPCOUNT: Nodes with a value too small would not be able to 2795 discover routes to distant addresses. 2797 o MAX_METRIC[MetricType]: No interoperability problems due to 2798 variations on different nodes, but nodes with lower values may 2799 exhibit overly restrictive behavior during route comparisons. 2801 o MAX_TIME: No interoperability problems due to variations on 2802 different nodes, but if a lower value is used, route state 2803 management may exhibit overly restrictive behavior. 2805 11.3. Local Settings 2807 The following table lists AODVv2 parameters which should be 2808 administratively configured for each node: 2810 +------------------------+------------------------+--------------+ 2811 | Name | Default Value | Description | 2812 +------------------------+------------------------+--------------+ 2813 | AODVv2_INTERFACES | | Section 3 | 2814 | BUFFER_SIZE_PACKETS | 2 | Section 6.4 | 2815 | BUFFER_SIZE_BYTES | MAX_PACKET_SIZE [TBD] | Section 6.4 | 2816 | CLIENT_ADDRESSES | AODVv2_INTERFACES | Section 4.2 | 2817 | CONTROL_TRAFFIC_LIMIT | [TBD - 50 pkts/sec?] | Section 7 | 2818 +------------------------+------------------------+--------------+ 2820 Table 5: Configuration for Local Settings 2822 11.4. Network-Wide Settings 2824 The following administrative controls may be used to change the 2825 operation of the network. The same settings should be used across 2826 the network. Inconsistent settings at different nodes in the network 2827 will not result in protocol errors, but poor performance may result, 2828 especially if metrics are misinterpreted because DEFAULT_METRIC_TYPE 2829 is configured differently at different nodes. 2831 +----------------------+----------------------+----------------+ 2832 | Name | Default | Description | 2833 +----------------------+----------------------+----------------+ 2834 | DEFAULT_METRIC_TYPE | 3 (i.e., Hop Count) | [RFC6551] | 2835 | ENABLE_IDLE_IN_RERR | Disabled | Section 7.4.1 | 2836 +----------------------+----------------------+----------------+ 2838 Table 6: Configuration for Network-Wide Settings 2840 11.5. Optional Feature Settings 2842 These options are not required for correct routing behavior, although 2843 they may reduce AODVv2 protocol overhead in certain situations. The 2844 default behavior is to leave these options disabled. 2846 +---------------------------+-----------+---------------------------+ 2847 | Name | Default | Description | 2848 +---------------------------+-----------+---------------------------+ 2849 | PRECURSOR_LISTS | Disabled | Local (Section 10.2) | 2850 | MSG_AGGREGATION | Disabled | Local (Section 10.4) | 2851 | ENABLE_IRREP | Disabled | Network-wide (Section | 2852 | | | 10.3) | 2853 | EXPANDING_RINGS_MULTICAST | Disabled | Network-wide (Section | 2854 | | | 10.1) | 2855 +---------------------------+-----------+---------------------------+ 2857 Table 7: Configuration for Optional Features 2859 12. IANA Considerations 2861 This section specifies several RFC 5444 message types, message tlv- 2862 types, and address tlv-types required for AODVv2. Also, a new 2863 registry of 16-bit metric types is specified. 2865 12.1. RFC 5444 Message Types 2867 +-----------------------------------------+-----------+ 2868 | Name of Message | Type | 2869 +-----------------------------------------+-----------+ 2870 | Route Request (RREQ) | 10 (TBD) | 2871 | Route Reply (RREP) | 11 (TBD) | 2872 | Route Error (RERR) | 12 (TBD) | 2873 | Route Reply Acknowledgement (RREP_Ack) | 13 (TBD) | 2874 +-----------------------------------------+-----------+ 2876 Table 8: AODVv2 Message Types 2878 12.2. RFC 5444 Address Block TLV Types 2880 +------------------------+----------+---------------+---------------+ 2881 | Name of TLV | Type | Length | Reference | 2882 | | | (octets) | | 2883 +------------------------+----------+---------------+---------------+ 2884 | PATH_METRIC | 10 (TBD) | depends on | Section 7 | 2885 | | | MetricType | | 2886 | SEQ_NUM | 11 (TBD) | 2 | Section 7 | 2887 | ADDRESS_TYPE | 15 (TBD) | 1 | Section 8 | 2888 | VALIDITY_TIME | 1 | 1 | [RFC5497] | 2889 +------------------------+----------+---------------+---------------+ 2891 Table 9: AODVv2 Address Block TLV Types 2893 12.3. MetricType Allocation 2895 Metric types are identified according to the assignments in 2896 [RFC6551]. 2898 +------------------------+----------+--------------+ 2899 | Name of MetricType | Type | Metric Size | 2900 +------------------------+----------+--------------+ 2901 | Unassigned | 0 | Undefined | 2902 | Currently Unsupported | 1 - 2 | TBD | 2903 | Hop Count | 3 [TBD] | 1 octet | 2904 | Currently Unsupported | 4 - 8 | TBD | 2905 | Unallocated | 9 - 254 | TBD | 2906 | Reserved | 255 | Undefined | 2907 +------------------------+----------+--------------+ 2909 Table 10: AODVv2 Metric Types 2911 When creating AODVv2 messages which relate to the 2912 DEFAULT_METRIC_TYPE, MetricType is not reported in the message. In 2913 the RFC 5444 message representation, the PATH_METRIC TLV, if 2914 included, will not include an extension type. While RFC 5444 would 2915 interpret the lack of an extension type value as indication that 2916 extension type is zero, AODVv2 will interpret an extension type of 2917 zero to mean the DEFAULT_METRIC_TYPE configured on the router. This 2918 is possible because zero is not assigned to any metric type 2919 ([RFC6551]). In RERR, the absence of the PATH_METRIC TLV also 2920 indicates use of the DEFAULT_METRIC_TYPE. 2922 12.4. AddressType Allocation 2924 The values used in the Address Type TLV used in Section 8 are given 2925 in the table below: 2927 +-----------------------+--------+ 2928 | Address Type | Value | 2929 +-----------------------+--------+ 2930 | ADDRTYPE_ORIGADDR | 0 | 2931 | ADDRTYPE_TARGADDR | 1 | 2932 | ADDRTYPE_UNREACHABLE | 2 | 2933 | ADDRTYPE_PKTSOURCE | 3 | 2934 | ADDRTYPE_INTEND | 4 | 2935 +-----------------------+--------+ 2937 Table 11: AODVv2 Address Types 2939 13. Security Considerations 2941 This section describes various security considerations and potential 2942 avenues to secure AODVv2 routing. The objective of the AODVv2 2943 protocol is for each router to communicate reachability information 2944 about addresses for which it is responsible, and for routes it has 2945 learned from other AODVv2 routers. Positive routing information 2946 (i.e. a route exists) is distributed via RREQ and RREP messages. 2947 Negative routing information (i.e. a route does not exist) is 2948 distributed via RERR messages. AODVv2 routers store the information 2949 contained in these messages in order to properly forward data 2950 packets, and they generally provide this information to other AODVv2 2951 routers. 2953 Networks using AODVv2 to maintain connectivity and establish routes 2954 on demand may be vulnerable to certain well-known types of threats. 2955 Flooding attacks using RREQ amount to a denial of service for route 2956 discovery. Valid route table entries can be replaced by maliciously 2957 constructed RREQ and RREP messages. Links could be erroneously 2958 treated as bidirectional if malicious unsolicited RREP or RREP_Ack 2959 messages were to be accepted. Replay attacks using RERR messages 2960 could, in some circumstances, be used to disrupt active routes. 2961 Passive inspection of AODVv2 control messages could enable 2962 unauthorized devices to gain information about the network topology, 2963 since exchanging such information is the main purpose of AODVv2. 2965 The on-demand nature of AODVv2 route discovery reduces the 2966 vulnerability to route disruption. Since control traffic for 2967 updating route tables is diminished, there is less opportunity for 2968 failure. Processing requirements for AODVv2 are typically quite 2969 small, and would typically be dominated by calculations to verify 2970 integrity. This has the effect of reducing (but by no means 2971 eliminating) AODVv2's vulnerability to denial of service attacks. 2973 Encryption MAY be used for AODVv2 messages. If the routers share a 2974 packet-level security association, the message data can be encrypted 2975 prior to message transmission. The establishment of such security 2976 associations is outside the scope of this specification. Encryption 2977 will not only protect against unauthorized devices obtaining 2978 information about network topology but will ensure that only trusted 2979 routers participate in routing operations. 2981 Message integrity checking is enabled by the Integrity Check Value 2982 mechanisms defined in [RFC7182]. The data contained in AODVv2 2983 routing protocol messages SHOULD be verified using ICV values, to 2984 avoid the use of message data if the message has been tampered with 2985 or replayed. Otherwise, it would be possible to disrupt 2986 communications by injecting nonexistent or malicious routes into the 2987 route tables of nodes within the ad hoc network. This can result in 2988 loss of data or message processing by unauthorized devices. 2990 The remainder of this section provides specific recommendations for 2991 the use of the integrity checking and timestamp functions defined in 2992 [RFC7182] to ensure the integrity of each AODVv2 message. The 2993 calculation used for the Integrity Check Value will depend on the 2994 message type. Sequence numbers can be used as timestamps to protect 2995 against replay, since they are known to be strictly increasing. 2997 RREQ messages advertise a route to OrigAddr, and impose very little 2998 processing requirement for receivers. The main threat presented by 2999 sending a RREQ message with false information is that traffic to 3000 OrigAddr could be disrupted. Since RREQ is multicast and likely to 3001 be received by all nodes in the ad hoc network, this threat could 3002 have serious impact on applications communicating by way of OrigAddr. 3003 The actual threat to disrupt routes to OrigAddr is reduced by the 3004 AODVv2 mechanism of marking RREQ-derived routes as "Unconfirmed" 3005 until adjacency with the next hop is confirmed. If AODVv2 routers 3006 always verify the integrity of the RREQ message data, then the threat 3007 of disruption is minimized. The ICV mechanisms offered in [RFC7182] 3008 are sufficient for this purpose. Since OrigAddr is included as a 3009 data element of the RREQ, the ICV can be calculated and verified 3010 using message contents. The ICV should be verified at every step 3011 along the dispersal path of the RREQ to mitigate the threat. Since 3012 RREQ_Gen's sequence number is incremented for each new RREQ, replay 3013 protection is already afforded and no extra timestamp mechanism is 3014 required. 3016 RREP messages advertise a route to TargAddr, and impose very little 3017 processing requirement for receivers. The main threat presented by 3018 sending a RREP message with false information is that traffic to 3019 TargAddr could be disrupted. Since RREP is unicast, this threat is 3020 restricted to receivers along the path from OrigAddr to TargAddr. If 3021 AODVv2 routers always verify the integrity of the RREP message data, 3022 then this threat is minimized. This facility is offered by the ICV 3023 mechanisms in [RFC7182]. Since TargAddr is included as a data 3024 element of the RREP, the ICV can be calculated and verified using 3025 message contents. The ICV should be verified at every step along the 3026 unicast path of the RREP. Since RREP_Gen's sequence number is 3027 incremented for each new RREP, replay protection is afforded and no 3028 extra timestamp mechanism is required. 3030 RREP_Ack messages are intended to verify bidirectional neighbor 3031 connectivity, and impose very little processing requirement for 3032 receivers. The main threat presented by sending a RREP_Ack message 3033 with false information is that the route advertised to a target node 3034 in a RREP might be erroneously accepted even though the route would 3035 contain a unidirectional link and thus not be suitable for most 3036 traffic. Since RREP_Ack is unicast, this threat is strictly local to 3037 the RREP transmitter expecting the acknowledgement. A malicious 3038 router could also attempt to send an unsolicited RREP_Ack to convince 3039 another router that a bidirectional link exists and subsequently use 3040 further messages to divert traffic along a route which is not valid. 3041 If AODVv2 routers always verify the integrity of the RREP_Ack message 3042 data, then this threat is minimized. This facility is offered by the 3043 ICV mechanisms in [RFC7182]. The RREP_Gen SHOULD use the source IP 3044 address of the RREP_Ack to identify the sender, and so the ICV should 3045 be calculated using the message contents and the IP source address. 3046 The message must also include the Timestamp defined in [RFC7182] to 3047 protect against replay attacks, using TargSeqNum from the RREP as the 3048 value in the TIMESTAMP TLV. 3050 RERR messages remove routes, and impose very little processing 3051 requirement for receivers. The main threat presented by sending a 3052 RERR message with false information is that traffic to the advertised 3053 destinations could be disrupted. Since RERR is multicast and can be 3054 received by many routers in the ad hoc network, this threat could 3055 have serious impact on applications communicating by way of the 3056 sender of the RERR message. However, since the sender of the RERR 3057 message with erroneous information may be presumed to be either 3058 malicious or broken, it is better that such routes not be used 3059 anyway. Another threat is that a malicious RERR message may be sent 3060 with a PktSource data element included, to disrupt PktSource's 3061 ability to send to the addresses contained in the RERR. If AODVv2 3062 routers always verify the integrity of the RERR message data, then 3063 this threat is reduced. This facility is offered by the ICV 3064 mechanisms in [RFC7182]. The receiver of the RERR SHOULD use the 3065 source IP address of the RERR to identify the sender. The message 3066 must also include the Timestamp defined in [RFC7182] to protect 3067 against replay attacks, using SeqNum from RERR_Gen as the value in 3068 the TIMESTAMP TLV. 3070 14. Acknowledgments 3072 AODVv2 is a descendant of the design of previous MANET on-demand 3073 protocols, especially AODV [RFC3561] and DSR [RFC4728]. Changes to 3074 previous MANET on-demand protocols stem from research and 3075 implementation experiences. Thanks to Elizabeth Belding and Ian 3076 Chakeres for their long time authorship of AODV. Additional thanks 3077 to Derek Atkins, Emmanuel Baccelli, Abdussalam Baryun, Ramon Caceres, 3078 Thomas Clausen, Justin Dean, Christopher Dearlove, Ulrich Herberg, 3079 Henner Jakob, Luke Klein-Berndt, Lars Kristensen, Tronje Krop, 3080 Koojana Kuladinithi, Kedar Namjoshi, Keyur Patel, Alexandru Petrescu, 3081 Henning Rogge, Fransisco Ros, Pedro Ruiz, Christoph Sommer, Romain 3082 Thouvenin, Richard Trefler, Jiazi Yi, Seung Yi, and Cong Yuan, for 3083 their reviews AODVv2 and DYMO, as well as numerous specification 3084 suggestions. 3086 15. References 3088 15.1. Normative References 3090 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3091 Requirement Levels", BCP 14, RFC 2119, March 1997. 3093 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 3094 Architecture", RFC 4291, February 2006. 3096 [RFC5082] Gill, V., Heasley, J., Meyer, D., Savola, P., and C. 3097 Pignataro, "The Generalized TTL Security Mechanism 3098 (GTSM)", RFC 5082, October 2007. 3100 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 3101 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 3102 Format", RFC 5444, February 2009. 3104 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 3105 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 3106 2009. 3108 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc Network 3109 (MANET) Protocols", RFC 5498, March 2009. 3111 [RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D. 3112 Barthel, "Routing Metrics Used for Path Calculation in 3113 Low-Power and Lossy Networks", RFC 6551, March 2012. 3115 15.2. Informative References 3117 [I-D.perkins-irrep] 3118 Perkins, C., "Intermediate RREP for dynamic MANET On- 3119 demand (AODVv2) Routing", draft-perkins-irrep-03 (work in 3120 progress), May 2015. 3122 [Perkins94] 3123 Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 3124 Sequenced Distance-Vector Routing (DSDV) for Mobile 3125 Computers", Proceedings of the ACM SIGCOMM '94 Conference 3126 on Communications Architectures, Protocols and 3127 Applications, London, UK, pp. 234-244, August 1994. 3129 [Perkins99] 3130 Perkins, C. and E. Royer, "Ad hoc On-Demand Distance 3131 Vector (AODV) Routing", Proceedings of the 2nd IEEE 3132 Workshop on Mobile Computing Systems and Applications, New 3133 Orleans, LA, pp. 90-100, February 1999. 3135 [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking 3136 (MANET): Routing Protocol Performance Issues and 3137 Evaluation Considerations", RFC 2501, January 1999. 3139 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 3140 Demand Distance Vector (AODV) Routing", RFC 3561, July 3141 2003. 3143 [RFC4193] Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast 3144 Addresses", RFC 4193, October 2005. 3146 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 3147 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 3148 IPv4", RFC 4728, February 2007. 3150 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 3151 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 3152 September 2007. 3154 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 3155 Considerations in Mobile Ad Hoc Networks (MANETs)", RFC 3156 5148, February 2008. 3158 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 3159 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 3160 RFC 6130, April 2011. 3162 [RFC6621] Macker, J., "Simplified Multicast Forwarding", RFC 6621, 3163 May 2012. 3165 [RFC7182] Herberg, U., Clausen, T., and C. Dearlove, "Integrity 3166 Check Value and Timestamp TLV Definitions for Mobile Ad 3167 Hoc Networks (MANETs)", RFC 7182, April 2014. 3169 Appendix A. Features Required of IP 3171 AODVv2 needs the following: 3173 o information that IP routes are requested 3175 o information that packets are flowing 3176 o the ability to queue packets 3178 A reactive protocol reacts when a route is needed. A route is 3179 requested when an application tries to send a packet. The 3180 fundamental concept of reactive routing is to avoid creating routes 3181 that are not needed. The trigger for route discovery is an 3182 application trying to send a packet. If a route is not available to 3183 forward the packet, the packet is queued while the route is 3184 requested. 3186 Appendix B. Multi-homing Considerations 3188 Multi-homing is not supported by the AODVv2 specification. The 3189 coordination between multiple AODVv2 routers to distribute routing 3190 information correctly for a shared address is not defined. 3192 Previous work indicates that it can be supported by expanding the 3193 sequence number to include the AODVv2 router's IP address as a 3194 parsable field of the SeqNum. Without this, comparing sequence 3195 numbers would not work to evaluate freshness. Even when the IP 3196 address is included, there is no good way to compare sequence numbers 3197 from different IP addresses, but a handling node can determine 3198 whether the two given sequence numbers are comparable. If the route 3199 table can store multiple routes for the same destination, then multi- 3200 homing can work with sequence numbers augmented by IP addresses. 3202 This non-normative information is provided simply to document the 3203 results of previous efforts to enable multi-homing. The intention is 3204 to simplify the task of future specification if multihoming becomes 3205 necessary for reactive protocol operation. 3207 Appendix C. Router Client Relocation 3209 Only one AODVv2 router within a MANET SHOULD be responsible for a 3210 particular address at any time. If two AODVv2 routers dynamically 3211 shift the advertisement of a network prefix, correct AODVv2 routing 3212 behavior must be observed. The AODVv2 router adding the new network 3213 prefix must wait for any existing routing information about this 3214 network prefix to be purged from the network, i.e., it must wait at 3215 least MAX_SEQNUM_LIFETIME after the previous AODVv2 router's last 3216 SeqNum update for this network prefix. 3218 Appendix D. Example Algorithms for AODVv2 Operations 3220 The following subsections show example algorithms for protocol 3221 operations required by AODVv2. AODVv2 requires general algorithms 3222 for manipulating and comparing table entries, and algorithms specific 3223 to each message type. 3225 Processing for messages follows the following general outline: 3227 1. Receive incoming message. 3229 2. Update route table as appropriate. 3231 3. Respond as needed, often regenerating the incoming message with 3232 updated information. 3234 Once the route table has been updated, the information contained 3235 there is known to be the most recent available information for any 3236 fields in the outgoing message. For this reason, the algorithms are 3237 written as if outgoing message field values are assigned from the 3238 route table information, even though it is often equally appropriate 3239 to use fields from the incoming message. 3241 The following table indicates the field names used in subsequent 3242 sections to describe the AODVv2 algorithms. 3244 +-------------------------+-----------------------------------------+ 3245 | Parameter | Description | 3246 +-------------------------+-----------------------------------------+ 3247 | RteMsg | A route message | 3248 | | (inRREQ/outRREQ/inRREP/outRREP) | 3249 | RteMsg.HopLimit | Hop limit for the message | 3250 | RteMsg.HopCount | Hop count for the message | 3251 | RteMsg.AckReq | True/False, optional in RREP | 3252 | RteMsg.MetricType | The type of metric included, optional | 3253 | RteMsg.OrigAddr | Address of source of queued data | 3254 | RteMsg.TargAddr | Address route is requested for | 3255 | RteMsg.OrigPrefixLen | Prefix length of OrigAddr, optional | 3256 | RteMsg.TargPrefixLen | Prefix length of TargAddr, optional | 3257 | RteMsg.OrigSeqNum | SeqNum of OrigAddr, in RREQ only | 3258 | RteMsg.TargSeqNum | SeqNum of TargAddr, in RREP, optional | 3259 | | in RREQ | 3260 | RteMsg.OrigMetric | Metric to OrigAddr, in RREQ only | 3261 | RteMsg.TargMetric | Metric to TargAddr, in RREP only | 3262 | RteMsg.ValidityTime | Time limit for route advertised | 3263 | RteMsg.NbrIP | Sender of the RteMsg | 3264 | RteMsg.Netif | Interface on which the RteMsg arrived | 3265 | AdvRte | Derived from a RteMsg (see Section 6.5) | 3266 | AdvRte.Address | Route destination address | 3267 | AdvRte.PrefixLength | Route destination prefix length | 3268 | AdvRte.SeqNum | SeqNum associated with route | 3269 | AdvRte.MetricType | MetricType associated with route | 3270 | AdvRte.Metric | Advertised metric of route | 3271 | AdvRte.Cost | Cost from receiving router | 3272 | AdvRte.ValidityTime | Time limit for route advertised | 3273 | AdvRte.NextHopIP | Sender of the RteMsg | 3274 | AdvRte.NextHopIntf | Interface on which the RteMsg arrived | 3275 | AdvRte.HopCount | Number of hops traversed | 3276 | AdvRte.HopLimit | Allowed number of hops remaining | 3277 | Route | A route table entry (see Section 4.6) | 3278 | Route.Address | Route destination address | 3279 | Route.PrefixLength | Route destination prefix length | 3280 | Route.SeqNum | SeqNum associated with route | 3281 | Route.NextHop | Address of router which advertised the | 3282 | | route | 3283 | Route.NextHopInterface | Interface on which next hop is | 3284 | | reachable | 3285 | Route.LastUsed | Time this route was last used for | 3286 | | packet forwarding | 3287 | Route.LastSeqNumUpdate | Time the SeqNum of the route was last | 3288 | | updated | 3289 | Route.ExpirationTime | Time at which the route will expire | 3290 | Route.MetricType | MetricType associated with route | 3291 | Route.Metric | Cost from receiving router | 3292 | Route.State | Active/Idle/Invalid | 3293 | Route.Precursors | Optional (see Section 10.2) | 3294 | RERR | Route Error message (inRERR/outRERR) | 3295 | RERR.HopLimit | Hop limit for the message | 3296 | RERR.PktSource | Source address of packet which | 3297 | | triggered RERR | 3298 | RERR.AddressList[] | List of unreachable route addresses | 3299 | RERR.PrefixLengthList[] | List of PrefixLengths for AddressList | 3300 | RERR.SeqNumList[] | List of SeqNums for AddressList | 3301 | RERR.MetricTypeList[] | MetricType for the invalid routes | 3302 | RERR.Netif | Interface on which the RERR arrived | 3303 +-------------------------+-----------------------------------------+ 3305 Table 12: Notation used in Appendix 3307 D.1. General Operations 3309 D.1.1. Check_Route_State 3310 /* Update the state of the route entry based on timeouts. Return 3311 whether the route can be used for forwarding a packet. */ 3313 Check_Route_State(route) 3314 { 3315 if (CurrentTime > route.ExpirationTime) 3316 route.State := Invalid; 3317 if ((CurrentTime - route.LastUsed > ACTIVE_INTERVAL + MAX_IDLETIME) 3318 AND (route.State != Unconfirmed) 3319 AND (route.ExpirationTime == MAX_TIME)) //not a timed route 3320 route.State := Invalid; 3321 if ((CurrentTime - route.LastUsed > ACTIVE_INTERVAL) 3322 AND (route.State != Unconfirmed) 3323 AND (route.ExpirationTime == MAX_TIME)) //not a timed route 3324 route.State := Idle; 3325 if ((CurrentTime - route.LastSeqNumUpdate > MAX_SEQNUM_LIFETIME) 3326 AND (route.State == Invalid OR route.State == Unconfirmed)) 3327 /* remove route from route table */ 3328 if ((CurrentTime - route.LastSeqNumUpdate > MAX_SEQNUM_LIFETIME) 3329 AND (route.State != Invalid) 3330 route.SeqNum := 0; 3332 if (route still exists AND route.State != Invalid 3333 AND Route.State != Unconfirmed) 3334 return TRUE; 3335 else 3336 return FALSE; 3337 } 3339 D.1.2. Process_Routing_Info 3341 (See Section 6.5.1) 3343 /* Compare incoming route information to stored route, and if better, 3344 use to update stored route. */ 3346 Process_Routing_Info (advRte) 3347 { 3348 rte := Fetch_Route_Table_Entry (advRte); 3349 if (!rte exists) 3350 { 3351 rte := Create_Route_Table_Entry(advRte); 3352 return rte; 3353 } 3355 if (AdvRte.SeqNum > Route.SeqNum /* stored route is stale */ 3356 OR 3357 (AdvRte.SeqNum == Route.SeqNum /* same SeqNum */ 3358 AND 3359 ((Route.State == Invalid AND LoopFree(advRte, rte)) 3360 /* advRte can repair stored */ 3361 OR AdvRte.Cost < Route.Metric))) /* advRte is better */ 3362 { 3363 if (advRte is from a RREQ) 3364 rte := Create_Route_Table_Entry(advRte); 3365 else 3366 Update_Route_Table_Entry (rte, advRte); 3367 } 3368 return rte; 3369 } 3371 D.1.3. Fetch_Route_Table_Entry 3372 /* Lookup a route table entry matching an advertised route */ 3374 Fetch_Route_Table_Entry (advRte) 3375 { 3376 foreach (rteTableEntry in rteTable) 3377 { 3378 if (rteTableEntry.Address == advRte.Address 3379 AND rteTableEntry.MetricType == advRte.MetricType) 3380 return rteTableEntry; 3381 } 3382 return null; 3383 } 3385 /* Lookup a route table entry matching address and metric type */ 3387 Fetch_Route_Table_Entry (destination, metricType) 3388 { 3389 foreach (rteTableEntry in rteTable) 3390 { 3391 if (rteTableEntry.Address == destination 3392 AND rteTableEntry.MetricType == metricType) 3393 return rteTableEntry; 3394 } 3395 return null; 3396 } 3398 D.1.4. Update_Route_Table_Entry 3400 /* Update a route table entry using AdvRte in received RteMsg */ 3402 Update_Route_Table_Entry (rte, advRte); 3403 { 3404 rte.SeqNum := advRte.SeqNum; 3405 rte.NextHop := advRte.NextHopIp; 3406 rte.NextHopInterface := advRte.NextHopIntf; 3407 rte.LastUsed := CurrentTime; 3408 rte.LastSeqNumUpdate := CurrentTime; 3409 if (validityTime) 3410 rte.ExpirationTime := CurrentTime + advRte.ValidityTime; 3411 else 3412 rte.ExpirationTime := MAX_TIME; 3414 rte.Metric := advRte.Cost; 3415 if (rte.State == Invalid) 3416 rte.State := Idle (if advRte is from RREP); 3417 or Unconfirmed (if advRte is from RREQ); 3418 } 3420 D.1.5. Create_Route_Table_Entry 3422 /* Create a route table entry from address and prefix length */ 3424 Create_Route_Table_Entry (address, prefixLength, seqNum, metricType) 3425 { 3426 rte := allocate_memory(); 3427 rte.Address := address; 3428 rte.PrefixLength := prefixLength; 3429 rte.SeqNum := seqNum; 3430 rte.MetricType := metricType; 3431 } 3433 /* Create a route table entry from the advertised route */ 3435 Create_Route_Table_Entry(advRte) 3436 { 3437 rte := allocate_memory(); 3439 rte.Address := advRte.Address; 3440 if (advRte.PrefixLength) 3441 rte.PrefixLength := advRte.PrefixLength; 3442 else 3443 rte.PrefixLength := maxPrefixLenForAddressFamily; 3445 rte.SeqNum := advRte.SeqNum; 3446 rte.NextHop := advRte.NextHopIp; 3447 rte.NextHopInterface := advRte.NextHopIntf; 3448 rte.LastUsed := CurrentTime; 3449 rte.LastSeqNumUpdate := CurrentTime; 3450 if (validityTime) 3451 rte.ExpirationTime := CurrentTime + advRte.ValidityTime; 3452 else 3453 rte.ExpirationTime := MAX_TIME; 3454 rte.MetricType := advRte.MetricType; 3455 rte.Metric := advRte.Metric; 3456 rte.State := Idle (if advRte is from RREP); 3457 or Unconfirmed (if advRte is from RREQ); 3458 } 3460 D.1.6. LoopFree 3461 /* Return TRUE if the route advRte is LoopFree compared to rte */ 3463 LoopFree(advRte, rte) 3464 { 3465 if (advRte.Cost <= rte.Cost) 3466 return TRUE; 3467 else 3468 return FALSE; 3469 } 3471 D.1.7. Fetch_Rte_Msg_Table_Entry 3473 /* Find an entry in the RteMsg table matching the given 3474 message's msg-type, OrigAddr, TargAddr, MetricType */ 3476 Fetch_Rte_Msg_Table_Entry (rteMsg) 3477 { 3478 foreach (entry in RteMsgTable) 3479 { 3480 if (entry.msg-type == rteMsg.msg-type 3481 AND entry.OrigAddr == rteMsg.OrigAddr 3482 AND entry.TargAddr == rteMsg.TargAddr 3483 AND entry.MetricType == rteMsg.MetricType) 3484 return entry; 3485 } 3486 return NULL; 3487 } 3489 D.1.8. Update_Rte_Msg_Table 3491 (See Section 4.5) 3493 /* Update the multicast route message suppression table based on the 3494 received RteMsg, return true if it was created or the SeqNum was 3495 updated (i.e. it needs to be regenerated) */ 3497 Update_Rte_Msg_Table(rteMsg) 3498 { 3499 /* search for a comparable entry */ 3500 entry := Fetch_Rte_Msg_Table_Entry(rteMsg); 3502 /* if there is none, create one */ 3503 if (entry does not exist) 3504 { 3505 entry.MessageType := rteMsg.msg_type; 3506 entry.OrigAddr := rteMsg.OrigAddr; 3507 entry.TargAddr := rteMsg.TargAddr; 3508 entry.OrigSeqNum := rteMsg.origSeqNum; // (if present) 3509 entry.TargSeqNum := rteMsg.targSeqNum; // (if present) 3510 entry.MetricType := rteMsg.MetricType; 3511 entry.Metric := rteMsg.OrigMetric; // (for RREQ) 3512 or rteMsg.TargMetric; // (for RREP) 3513 entry.Timestamp := CurrentTime; 3514 return TRUE; 3515 } 3517 /* if current entry is stale */ 3518 if ( 3519 (rteMsg.msg-type == RREQ AND entry.OrigSeqNum < rteMsg.OrigSeqNum) 3520 OR 3521 (rteMsg.msg-type == RREP AND entry.TargSeqNum < rteMsg.TargSeqNum)) 3522 { 3523 entry.OrigSeqNum := rteMsg.OrigSeqNum; // (if present) 3524 entry.TargSeqNum := rteMsg.TargSeqNum; // (if present) 3525 entry.Timestamp := CurrentTime; 3526 return TRUE; 3527 } 3529 /* if received rteMsg is stale */ 3530 if ( 3531 (rteMsg.msg-type == RREQ AND entry.OrigSeqNum > rteMsg.OrigSeqNum) 3532 OR 3533 (rteMsg.msg-type == RREP AND entry.TargSeqNum > rteMsg.TargSeqNum)) 3534 { 3535 entry.Timestamp := CurrentTime; 3536 return FALSE; 3537 } 3539 /* if same SeqNum but rteMsg has lower metric */ 3540 if (entry.Metric > rteMsg.Metric) 3541 entry.Metric := rteMsg.Metric; 3543 entry.Timestamp := CurrentTime; 3544 return FALSE; 3545 } 3547 D.1.9. Build_RFC_5444_Message_Header 3548 /* This pseudocode shows possible RFC 5444 actions, and would not 3549 be performed by the AODVv2 implementation. It is shown only to 3550 provide more understanding about the AODVv2 message that will be 3551 constructed by RFC 5444. 3552 MAL := Message Address Length 3553 MF := Message Flags 3554 Size := number of octets in MsgHdr, AddrBlk, AddrTLVs */ 3556 Build_RFC_5444_Message_Header (msgType, Flags, AddrFamily, Size, 3557 hopLimit, hopCount, tlvLength) 3558 { 3559 /* Build RFC 5444 message header fields */ 3560 msg-type := msgType; 3561 MF := Flags; 3562 MAL := 3 or 15; // for IPv4 or IPv6 3563 msg-size := Size; 3564 msg-hop-limit := hopLimit; 3565 if (hopCount != 0) /* if hopCount is 0, do not include */ 3566 msg-hop-count := hopCount; 3567 msg.tlvs-length := tlvLength; 3568 } 3570 D.2. RREQ Operations 3572 D.2.1. Generate_RREQ 3574 /* Generate a route request message to find a route from OrigAddr 3575 to TargAddr using the given MetricType 3576 origAddr := IP address of Router Client which generated the 3577 packet to be forwarded 3578 origPrefix := prefix length associated with the Router Client 3579 targAddr := destination IP address in the packet to be forwarded 3580 targSeqNum := sequence number in existing route to targAddr 3581 mType := metric type for the requested route */ 3583 Generate_RREQ(origAddr, origPrefix, targAddr, targSeqNum, mType) 3584 { 3585 /* Increment sequence number in nonvolatile storage */ 3586 mySeqNum := (1 + mySeqNum); 3588 /* Marshall parameters */ 3589 outRREQ.HopLimit := MAX_HOPCOUNT; 3590 outRREQ.HopCount := 0; // if included 3591 outRREQ.MetricType := mType; //include if not DEFAULT_METRIC_TYPE 3592 outRREQ.OrigAddr := origAddr; 3593 outRREQ.TargAddr := targAddr; 3594 outRREQ.OrigPrefixLen := origPrefix; //include if not address length 3595 outRREQ.OrigSeqNum := mySeqNum; 3596 outRREQ.TargSeqNum := targSeqNum; //included if available 3597 outRREQ.OrigMetric := Route[OrigAddr].Metric; //zero by default 3598 outRREQ.ValidityTime := limit for route to OrigAddr; //if required 3600 /* Build Address Blk using prefix length information from 3601 outRREQ.OrigPrefixLen if necessary */ 3602 AddrBlk := {outRREQ.OrigAddr, outRREQ.TargAddr}; 3604 /* Include sequence numbers in appropriate Address Block TLVs */ 3605 /* OrigSeqNum Address Block TLV */ 3606 origSeqNumAddrBlkTlv.value := outRREQ.OrigSeqNum; 3607 /* TargSeqNum Address Block TLV */ 3608 if (outRREQ.TargSeqNum is known) 3609 targSeqNumAddrBlkTlv.value := outRREQ.TargSeqNum; 3611 /* Build Metric Address Block TLV, include Metric AddrBlkTlv 3612 Extension type if a non-default metric */ 3613 metricAddrBlkTlv.value := outRREQ.OrigMetric; 3614 if (outRREQ.MetricType != DEFAULT_METRIC_TYPE) 3615 metricAddrBlkTlv.typeExtension := outRREQ.MetricType; 3617 if (outRREQ.ValidityTime is required) 3618 { 3619 /* Build VALIDITY_TIME Address Block TLV */ 3620 VALIDITY_TIMEAddrBlkTlv.value := outRREQ.ValidityTime; 3621 } 3623 Build_RFC_5444_Message_Header (RREQ, 4, IPv4 or IPv6, NN, 3624 outRREQ.HopLimit, outRREQ.HopCount, tlvLength); 3626 /* multicast RFC 5444 message to LL-MANET-Routers */ 3627 } 3629 D.2.2. Receive_RREQ 3630 /* Process a RREQ received on link L */ 3632 Receive_RREQ (inRREQ, L) 3633 { 3634 if (inRREQ.NbrIP present in blacklist) 3635 { 3636 if (blacklist_expiration_time < CurrentTime) 3637 return; // don't process or regenerate RREQ 3638 else 3639 remove nbrIP from blacklist; 3640 } 3641 if (inRREQ does not contain msg_hop_limit, OrigAddr, 3642 TargAddr, OrigSeqNum, OrigMetric) 3643 return; 3644 if (inRREQ.OrigAddr and inRREQ.TargAddr are not valid routable 3645 and unicast addresses) 3646 return; 3647 if (inRREQ.MetricType is present but an unknown value) 3648 return; 3649 if (inRREQ.OrigMetric > MAX_METRIC[inRREQ.MetricType] - Cost(L)) 3650 return; 3652 /* Extract inRREQ values */ 3653 advRte.Address := inRREQ.OrigAddr; 3654 advRte.PrefixLength := inRREQ.OrigPrefixLen; (if present) 3655 or the address length of advRte.Address; 3656 advRte.SeqNum := inRREQ.OrigSeqNum; 3657 advRte.MetricType := inRREQ.MetricType; 3658 advRte.Metric := inRREQ.OrigMetric; 3659 advRte.Cost := inRREQ.OrigMetric + Cost(L); 3660 //according to the indicated MetricType 3661 advRte.ValidityTime := inRREQ.ValidityTime; //if present 3662 advRte.NextHopIP := inRREQ.NbrIP; 3663 advRte.NextHopIntf := inRREQ.Netif; 3664 advRte.HopCount := inRREQ.HopCount; 3665 advRte.HopLimit := inRREQ.HopLimit; 3667 rte := Process_Routing_Info (advRte); 3669 /* Update the RteMsgTable and determine if the RREQ needs 3670 to be regenerated */ 3671 regenerate := Update_Rte_Msg_Table(inRREQ); 3673 if (inRREQ.TargAddr is in Router Client list) 3674 Generate_RREP(inRREQ, rte); 3675 else if (regenerate) 3676 Regenerate_RREQ(inRREQ, rte); 3677 } 3679 D.2.3. Regenerate_RREQ 3681 /* Called from receive_RREQ() 3682 rte := the route to OrigAddr */ 3684 Regenerate_RREQ (inRREQ, rte) 3685 { 3686 outRREQ.HopLimit := inRREQ.HopLimit - 1; 3687 if (outRREQ.HopLimit == 0) 3688 return; // don't regenerate 3690 if (inRREQ.HopCount exists) 3691 { 3692 if (inRREQ.HopCount >= MAX_HOPCOUNT) 3693 return; // don't regenerate 3694 outRREQ.HopCount := inRREQ.HopCount + 1; 3695 } 3697 /* Marshall parameters */ 3698 outRREQ.MetricType := rte.MetricType; 3699 outRREQ.OrigAddr := rte.Address; 3700 outRREQ.TargAddr := inRREQ.TargAddr; 3701 /* include prefix length if not equal to address length */ 3702 outRREQ.OrigPrefixLen := rte.PrefixLength; 3703 outRREQ.OrigSeqNum := rte.SeqNum; 3704 outRREQ.TargSeqNum := inRREQ.TargSeqNum; // if present 3705 outRREQ.OrigMetric := rte.Metric; 3706 outRREQ.ValidityTime := rte.ValidityTime; 3707 or the time limit this router wishes to put on 3708 route to OrigAddr 3710 /* Build Address Block using prefix length information from 3711 outRREQ.OrigPrefixLen if necessary */ 3712 AddrBlk := {outRREQ.OrigAddr, outRREQ.TargAddr}; 3714 /* Include sequence numbers in appropriate Address Block TLVs */ 3715 /* OrigSeqNum Address Block TLV */ 3716 origSeqNumAddrBlkTlv.value := outRREQ.OrigSeqNum; 3717 /* TargSeqNum Address Block TLV */ 3718 if (outRREQ.TargSeqNum is known) 3719 targSeqNumAddrBlkTlv.value := outRREQ.TargSeqNum; 3721 /* Build Metric Address Block TLV, include Metric AddrBlkTlv 3722 Extension type if a non-default metric */ 3723 metricAddrBlkTlv.value := outRREQ.OrigMetric; 3724 if (outRREQ.MetricType != DEFAULT_METRIC_TYPE) 3725 metricAddrBlkTlv.typeExtension := outRREQ.MetricType; 3727 if (outRREQ.ValidityTime is required) 3728 { 3729 /* Build VALIDITY_TIME Address Block TLV */ 3730 VALIDITY_TIMEAddrBlkTlv.value := outRREQ.ValidityTime; 3731 } 3732 Build_RFC_5444_Message_Header (RREQ, 4, IPv4 or IPv6, NN, 3733 outRREQ.HopLimit, outRREQ.HopCount, tlvLength); 3735 /* Multicast RFC 5444 message to LL-MANET-Routers, or if 3736 inRREQ was unicast, the message can be unicast to the next 3737 hop on the route to TargAddr, if known */ 3738 } 3740 D.3. RREP Operations 3742 D.3.1. Generate_RREP 3744 Generate_RREP(inRREQ, rte) 3745 { 3746 /* Increment sequence number in nonvolatile storage */ 3747 mySeqNum := (1 + mySeqNum); 3749 /* Marshall parameters */ 3750 outRREP.HopLimit := inRREQ.HopCount; 3751 outRREP.HopCount := 0; 3752 /* Include the AckReq when: 3753 - previous RREP does not seem to enable any data flow, OR 3754 - when RREQ is received from same OrigAddr after RREP was 3755 unicast to rte.NextHop */ 3756 outRREP.AckReq := TRUE or FALSE; //TRUE if acknowledgement required 3757 /* if included, set timeout RREP_Ack_SENT_TIMEOUT */ 3759 if (rte.MetricType != DEFAULT_METRIC_TYPE) 3760 outRREP.MetricType := rte.MetricType; 3761 outRREP.OrigAddr := rte.Address; 3762 outRREP.TargAddr := inRREQ.TargAddr; 3763 outRREP.TargPrefixLen := rte.PrefixLength; //if not address length 3764 outRREP.TargSeqNum := mySeqNum; 3765 outRREP.TargMetric := Route[TargAddr].Metric; 3766 //zero by default 3767 outRREP.ValidityTime := limit for route to TargAddr; //if required 3769 if (outRREP.AckReq == TRUE) 3770 /* include AckReq Message TLV */ 3772 /* Build Address Block using prefix length information from 3773 outRREP.TargPrefixLen if necessary */ 3774 AddrBlk := {outRREP.OrigAddr, outRREP.TargAddr}; 3775 /* TargSeqNum Address Block TLV */ 3776 targSeqNumAddrBlkTlv.value := outRREP.TargSeqNum; 3778 /* Build Metric Address Block TLV include Metric AddrBlkTlv 3779 Extension type if a non-default metric */ 3780 metricAddrBlkTlv.value := outRREP.TargMetric; 3781 if (outRREP.MetricType != DEFAULT_METRIC_TYPE) 3782 metricAddrBlkTlv.typeExtension := outRREP.MetricType; 3784 if (outRREP.ValidityTime is required) 3785 { 3786 /* Build VALIDITY_TIME Address Block TLV */ 3787 VALIDITY_TIMEAddrBlkTlv.value := outRREP.ValidityTime; 3788 } 3790 Build_RFC_5444_Message_Header (RREP, 4, IPv4 or IPv6, NN, 3791 outRREP.HopLimit, outRREQ.HopCount, tlvLength); 3793 /* unicast RFC 5444 message to rte[OrigAddr].NextHop */ 3794 } 3796 D.3.2. Receive_RREP 3798 /* Process a RREP received on link L */ 3800 Receive_RREP (inRREP, L) 3801 { 3802 if (inRREP.NbrIP present in blacklist) 3803 { 3804 if (blacklist_expiration_time < CurrentTime) 3805 return; // don't process or regenerate RREP 3806 else 3807 remove NbrIP from blacklist; 3808 } 3810 if (inRREP does not contain msg_hop_limit, OrigAddr, 3811 TargAddr, TargSeqNum, TargMetric) 3812 return; 3813 if (inRREP.OrigAddr and inRREQ.TargAddr are not 3814 valid routable and unicast addresses) 3815 return; 3816 if (inRREP.MetricType is present but an unknown value) 3817 return; 3818 if (inRREP.TargMetric > MAX_METRIC[inRREP.MetricType] - Cost(L)) 3819 return; 3821 /* Extract inRREP values */ 3822 advRte.Address := inRREP.TargAddr; 3823 advRte.PrefixLength := inRREP.TargPrefixLen; //if present 3824 or the address length of advRte.Address; 3825 advRte.SeqNum := inRREP.TargSeqNum; 3826 advRte.MetricType := inRREP.MetricType; 3827 advRte.Metric := inRREP.TargMetric; 3828 advRte.Cost := inRREP.TargMetric + Cost(L); 3829 //according to the indicated MetricType 3830 advRte.ValidityTime := inRREP.ValidityTime; //if present 3831 advRte.NextHopIP := inRREP.NbrIP; 3832 advRte.NextHopIntf := inRREP.Netif; 3833 advRte.HopCount := inRREP.HopCount; 3834 advRte.HopLimit := inRREP.HopLimit; //if included 3836 rte := Process_Routing_Info (advRte); 3838 ` if (inRREP includes AckReq data element) 3839 Generate_RREP_Ack(inRREP); 3841 /* Update the RteMsgTable and determine if the RREP needs 3842 to be regenerated */ 3843 regenerate := Update_Rte_Msg_Table(inRREP); 3845 if (inRREP.TargAddr is in the Router Client list) 3846 send_buffered_packets(rte); /* start to use the route */ 3847 else if (regenerate) 3848 Regenerate_RREP(inRREP, rte); 3849 } 3851 D.3.3. Regenerate_RREP 3853 Regenerate_RREP(inRREP, rte) 3854 { 3855 if (rte does not exist) 3856 { 3857 Generate_RERR(inRREP); 3858 return; 3859 } 3861 outRREP.HopLimit := inRREP.HopLimit - 1; 3862 if (outRREP.HopLimit == 0) /* don't regenerate */ 3863 return; 3865 if (inRREP.HopCount exists) 3866 { 3867 if (inRREP.HopCount >= MAX_HOPCOUNT) 3868 return; // don't regenerate the RREP 3869 outRREP.HopCount := inRREP.HopCount + 1; 3870 } 3871 /* Marshall parameters */ 3872 /* Include the AckReq when: 3873 - previous unicast RREP seems not to enable data flow, OR 3874 - when RREQ is received from same OrigAddr after RREP 3875 was unicast to rte.NextHop */ 3876 outRREP.AckReq := TRUE or FALSE; //TRUE if acknowledgement required 3877 /* if included, set timeout RREP_Ack_SENT_TIMEOUT */ 3879 if (rte.MetricType != DEFAULT_METRIC_TYPE) 3880 outRREP.MetricType := rte.MetricType; 3881 outRREP.OrigAddr := inRREP.OrigAddr; 3882 outRREP.TargAddr := rte.Address; 3883 outRREP.TargPrefixLen := rte.PrefixLength; //if not address length 3884 outRREP.TargSeqNum := rte.SeqNum; 3885 outRREP.TargMetric := rte.Metric; 3886 outRREP.ValidityTime := limit for route to TargAddr; //if required 3887 outRREP.NextHop := rte.NextHop 3889 if (outRREP.AckReq == TRUE) 3890 /* include AckReq Message TLV */ 3892 /* Build Address Block using prefix length information from 3893 outRREP.TargPrefixLen if necessary */ 3894 AddrBlk := {outRREP.OrigAddr, outRREP.TargAddr}; 3896 /* TargSeqNum Address Block TLV */ 3897 targSeqNumAddrBlkTlv.value := outRREP.TargSeqNum; 3899 /* Build Metric Address Block TLV include Metric AddrBlkTlv 3900 Extension type if a non-default metric */ 3901 metricAddrBlkTlv.value := outRREP.TargMetric; 3902 if (outRREP.MetricType != DEFAULT_METRIC_TYPE) 3903 metricAddrBlkTlv.typeExtension := outRREP.MetricType; 3905 if (outRREP.ValidityTime is required) 3906 { 3907 /* Build VALIDITY_TIME Address Block TLV */ 3908 VALIDITY_TIMEAddrBlkTlv.value := outRREP.ValidityTime; 3909 } 3911 Build_RFC_5444_Message_Header (RREP, 4, IPv4 or IPv6, NN, 3912 outRREP.HopLimit, 0, tlvLength); 3914 /* unicast RFC 5444 message to rte[OrigAddr].NextHop */ 3915 } 3916 D.4. RREP_Ack Operations 3918 D.4.1. Generate_RREP_Ack 3920 /* To be sent when a received RREP includes the AckReq data element */ 3922 Generate_RREP_Ack(inRREP) 3923 { 3924 Build_RFC_5444_Message_Header (RREP_Ack, 4, IPv4 or IPv6, NN, 3925 1, 0, 0); 3926 /* unicast RFC 5444 message to inRREP.NbrIP */ 3927 } 3929 D.4.2. Receive_RREP_Ack 3931 Receive_RREP_Ack(inRREP_Ack) 3932 { 3933 /* cancel timeout event for the node sending RREP_Ack */ 3934 } 3936 D.4.3. Timeout_RREP_Ack 3938 Timeout_RREP_Ack(outRREP) 3939 { 3940 if (numRetries < RREP_RETRIES) 3941 /* resend RREP and double the previous timeout */ 3942 else 3943 /* insert unresponsive node into blacklist */ 3944 } 3946 D.5. RERR Operations 3948 D.5.1. Generate_RERR 3950 There are two parts to this function, based on whether it was 3951 triggered by an undeliverable packet or a broken link to neighboring 3952 AODVv2 router. 3954 /* Generate a Route Error message. 3955 errorType := undeliverablePacket or brokenLink */ 3957 Generate_RERR(errorType, triggerPkt, brokenLinkNbrIp) 3958 { 3959 switch (errorType) 3960 { 3961 case (brokenLink): 3962 doGenerate := FALSE; 3963 num-broken-addr := 0; 3964 precursors[] := new empty precursor list; 3965 outRERR.HopLimit := MAX_HOPCOUNT; 3966 /* find routes which are now Invalid */ 3967 foreach (rte in route table) 3968 { 3969 if (brokenLinkNbrIp == rte.NextHop 3970 AND (rte.State == Active 3971 OR 3972 (rte.State == Idle AND ENABLE_IDLE_IN_RERR))) 3973 { 3974 if (rte.State == Active) 3975 doGenerate := TRUE; 3976 rte.State := Invalid; 3977 precursors += rte.Precursors (if any); 3978 outRERR.AddressList[num-broken-addr] := rte.Address; 3979 outRERR.PrefixLengthList[num-broken-addr] := 3980 rte.PrefixLength; 3981 outRERR.SeqNumList[num-broken-addr] := rte.SeqNum; 3982 outRERR.MetricTypeList[num-broken-addr] := rte.MetricType 3983 num-broken-addr := num-broken-addr + 1; 3984 } 3985 } 3986 } 3987 case (undeliverablePacket): 3988 doGenerate := TRUE; 3989 num-broken-addr := 1; 3990 outRERR.HopLimit := MAX_HOPCOUNT; 3991 outRERR.PktSource := triggerPkt.SrcIP; 3992 or triggerPkt.TargAddr; //if pkt was a RREP 3993 outRERR.AddressList[0] := triggerPkt.DestIP; 3994 or triggerPkt.OrigAddr; //if pkt was RREP 3995 /* optional to include outRERR.PrefixLengthList, outRERR.SeqNumList 3996 and outRERR.MetricTypeList */ 3997 } 3999 if (doGenerate == FALSE) 4000 return; 4002 if (triggerPkt exists) 4003 { 4004 /* Build PktSource Message TLV */ 4005 pktSourceMessageTlv.value := outRERR.PktSource; 4006 } 4008 /* The remaining steps add address, prefix length, sequence 4009 number and metric type information for each unreachable address, 4010 while conforming to the allowed MTU. If the MTU is reached, a new 4011 message MUST be created. */ 4013 /* Build Address Block using prefix length information from 4014 outRERR.PrefixLengthList[] if necessary */ 4015 AddrBlk := outRERR.AddressList[]; 4017 /* Optionally, add SeqNum Address Block TLV, including index values */ 4018 seqNumAddrBlkTLV := outRERR.SeqNumList[]; 4020 if (outRERR.MetricTypeList contains non-default MetricTypes) 4021 /* include Metric Address Block TLVs with Type Extension set to 4022 MetricType, including index values if necessary */ 4023 metricAddrBlkTlv.typeExtension := outRERR.MetricTypeList[]; 4025 Build_RFC_5444_Message_Header (RERR, 4, IPv4 or IPv6, NN, 4026 outRERR.HopLimit, 0, tlvLength); 4028 if (undeliverablePacket) 4029 /* unicast outRERR to rte[outRERR.PktSource].NextHop */ 4030 else if (brokenLink) 4031 /* unicast to precursors, or multicast to LL-MANET-Routers */ 4032 } 4034 D.5.2. Receive_RERR 4036 Receive_RERR (inRERR) 4037 { 4038 if (inRERR does not contain msg_hop_limit and at least 4039 one unreachable address) 4040 return; 4042 /* Extract inRERR values, copy relevant unreachable addresses, 4043 their prefix lengths, and sequence numbers to outRERR */ 4044 num-broken-addr := 0; 4045 precursors[] := new empty precursor list; 4046 foreach (unreachableAddress in inRERR.AddressList) 4047 { 4048 if (unreachableAddress is not valid routable and unicast) 4049 continue; 4050 if (unreachableAddress MetricType is present but an unknown value) 4051 return; 4053 /* Find a matching route table entry, assume 4054 DEFAULT_METRIC_TYPE if no MetricType included */ 4055 rte := Fetch_Route_Table_Entry (unreachableAddress, 4056 unreachableAddress MetricType) 4057 if (rte does not exist) 4058 continue; 4059 if (rte.State == Invalid)/* ignore already invalid routes */ 4060 continue; 4062 if ((rte.NextHop != inRERR.NbrIP 4063 OR 4064 rte.NextHopInterface != inRERR.Netif) 4065 AND (PktSource is not present OR is not a Router Client)) 4066 continue; 4067 if (unreachableAddress SeqNum (if known) < rte.SeqNum) 4068 continue; 4070 /* keep a note of all precursors of newly Invalid routes */ 4071 precursors += rte.Precursors; //if any 4073 /* assume prefix length is address length if not included */ 4074 if (rte.PrefixLength != unreachableAddress prefixLength) 4075 { 4076 /* create new route with unreachableAddress information */ 4077 invalidRte := Create_Route_Table_Entry(unreachableAddress, 4078 unreachableAddress PrefixLength, 4079 unreachableAddress SeqNum, 4080 unreachableAddress MetricType); 4081 invalidRte.State := Invalid; 4083 if (rte.PrefixLength > unreachableAddress prefixLength) 4084 expunge_route(rte); 4085 rte := invalidRte; 4086 } 4087 else if (rte.PrefixLength == unreachableAddress prefixLength) 4088 rte.State := Invalid; 4090 outRERR.AddressList[num-broken-addr] := rte.Address; 4091 outRERR.PrefixLengthList[num-broken-addr] := rte.PrefixLength; 4092 outRERR.SeqNumList[num-broken-addr] := rte.SeqNum; 4093 outRERR.MetricTypeList[num-broken-addr] := rte.MetricType; 4094 num-broken-addr := num-broken-addr + 1; 4095 } 4097 if (num-broken-addr AND (PktSource is not present OR PktSource is not 4098 a Router Client)) 4099 Regenerate_RERR(outRERR, inRERR, precursors); 4100 } 4102 D.5.3. Regenerate_RERR 4103 Regenerate_RERR (outRERR, inRERR, precursors) 4104 { 4105 /* Marshal parameters */ 4106 outRERR.HopLimit := inRERR.HopLimit - 1; 4107 if (outRERR.HopLimit == 0) // don't regenerate 4108 return; 4110 outRERR.PktSource := inRERR.PktSource; //if included 4111 /* AddressList[], SeqNumList[], and PrefixLengthList[] are 4112 already up-to-date */ 4114 if (outRERR.PktSource exists) 4115 { 4116 /* Build PktSource Message TLV */ 4117 pktSourceMessageTlv.value := outRERR.PktSource; 4118 } 4120 /* Build Address Block using prefix length information from 4121 outRERR.PrefixLengthList[] if necessary */ 4122 AddrBlk := outRERR.AddressList[]; 4124 /* Optionally, add SeqNum Address Block TLV, including index values */ 4125 seqNumAddrBlkTLV := outRERR.SeqNumList[]; 4127 if (outRERR.MetricTypeList contains non-default MetricTypes) 4128 /* include Metric Address Block TLVs with Type Extension set to 4129 MetricType, including index values if necessary */ 4130 metricAddrBlkTlv.typeExtension := outRERR.MetricTypeList[]; 4132 Build_RFC_5444_Message_Header (RERR, 4, IPv4 or IPv6, NN, 4133 outRERR.HopLimit, 0, tlvLength); 4135 if (outRERR.PktSource exists) 4136 /* unicast RFC 5444 message to next hop towards 4137 outRERR.PktSource */ 4138 else if (number of precursors == 1) 4139 /* unicast RFC 5444 message to precursors[0] */ 4140 else if (number of precursors > 1) 4141 /* unicast RFC 5444 message to all precursors, or multicast 4142 RFC 5444 message to RERR_PRECURSORS if preferable */ 4143 else 4144 /* multicast RFC 5444 message to LL-MANET-Routers */ 4145 } 4146 Appendix E. AODVv2 Draft Updates 4148 E.1. Changes between revisions 9 and 10 4150 This section lists the changes between AODVv2 revisions ...-09.txt 4151 and ...-10.txt. 4153 o Updated RFC 5444 Representation section to add "Address Type" TLV, 4154 which explicitly declares the meaning of addresses in the RFC 5444 4155 Address Block. 4157 o Relocated route state definitions. Minor improvements to clarity 4158 throughout. 4160 o Updated definition of timed routes. 4162 o More consistent use of OrigPrefixLen, TargPrefixLen, and Invalid. 4164 o Mandated use of neighbor adjacency checking and support of AckReq 4165 and RREP_Ack and clarified related text. 4167 o Changed order of LoopFree checking and route cost comparisons in 4168 Evaluating Route Information. 4170 o Updated structure of section on Applying Route Updates. 4172 o Updated AckReq to include intended next hop address, and RREP to 4173 be multicast if intended next hop is not a confirmed neighbor. 4175 o Clarified that gateway router is not default router. 4177 E.2. Changes between revisions 8 and 9 4179 This section lists the changes between AODVv2 revisions ...-08.txt 4180 and ...-09.txt. 4182 o Numerous editorial improvements were made, including 4183 relocation/removal/renaming/adding of some sections and text, 4184 collection and tidying of scattered text on same topic, formatting 4185 made more consistent to improve readability. 4187 o Removed mentions of precursors from main text, except one mention 4188 in Route Table Entry. 4190 o Removed use of MIN_METRIC which was not defined. 4192 o Changed Current_Time to CurrentTime for consistency. 4194 o Changed OrigAddrMetric and TargAddrMetric to OrigMetric and 4195 TargMetric respectively. 4197 o Updated Overview to simplify and provide a broader summary. 4199 o Updated Terminology definitions, Data Elements tables and combined 4200 sections. 4202 o Updated Applicability Statement to move some of the non- 4203 applicability text and to simplify what remains. 4205 o Updated TLV names to conform to existing naming style. 4207 o Updated Blacklist to be a NeighborList to include neighbors that 4208 have confirmed bidirectional connectivity. 4210 o Updated messages processed if router on blacklist and which are 4211 indicators of bidirectional links. 4213 o Added RemoveTime to RteMsg Table section. 4215 o Added short description of timed route to Route Table Entry 4216 section but removed Route.Timed flag. Route is timed if its 4217 expiration time is not MAX_TIME. 4219 o Added Unconfirmed route state for route to OrigAddr learned from 4220 RREQ. 4222 o Updated AODVv2 Protocol Operations section and subsections, 4223 including Initialization, Adjacency Monitoring, making algorithms 4224 easier to read and making notation consistent, general 4225 improvements to the text. 4227 o Updated Route Discovery, Retries and Buffering to include a more 4228 complete description of the route discovery process. 4230 o Updated wording relating to different metric types. 4232 o Added text regarding control message limit in Message Transmission 4233 section. 4235 o Added short explanation of positive/negative effects of buffering. 4237 o Simplified the packet diagrams, since some of their contents was 4238 already explained in the text below and then again as part of 4239 generation, reception and regeneration processes. 4241 o Clarified some elements of the message content descriptions. 4243 o Moved MetricType above MetricList in message sections, for 4244 consistency. 4246 o Mirrored structure throughout AODVv2 Protocol Messages. 4248 o Changed RREQ and RREP's use of Lists when only one entry is 4249 necessary. 4251 o Added some pre-message-generation checks. 4253 o Ensured consistency in regeneration (if msg-hop-limit is reduced 4254 to zero, do not regenerate). 4256 o Removed statements about neighbors but added blacklist checks 4257 where necessary. 4259 o Noted that RREQ retries should increase the SeqNum. 4261 o Added statement that implementations SHOULD retry sending RREP. 4263 o Added text explaining what happens if RREP is lost, regarding 4264 blacklisting and RREQ retries. 4266 o Removed hop limit from RREP_Ack. Changed order of blacklist 4267 check. 4269 o Updated RERR so that multiple metric types can be reported in the 4270 same message. 4272 o Updated RERR reception processing to ensure PktSource deletes the 4273 contained route. 4275 o Added text to show that if a router is the destination of a RERR, 4276 the RERR is not regenerated. 4278 o Added text that RERRs should not be created if the same RERR has 4279 recently been sent. 4281 o Updated RFC 5444 overview and simplified/rearranged text in this 4282 section. 4284 o Major update to RFC 5444 representation section 4286 o Updated RERR's RFC 5444 representation so that PktSource is placed 4287 in Address Block, and updated IANA section to make PktSource an 4288 Address Block TLV to indicate which address is PktSource. 4290 o Described use of extension type in Metric TLV to represent 4291 MetricType, and the interpretation when using the default metric 4292 type. 4294 o Removed Multicast RREP as an optional feature. 4296 o Updated Precursor Lists section to include options for precursor 4297 information to store. 4299 o Updated Security Considerations. 4301 E.3. Changes between revisions 7 and 8 4303 This section lists the changes between AODVv2 revisions ...-07.txt 4304 and ...-08.txt. 4306 o MetricType is now an Address Block TLV. Minor changes to the 4307 text. By using an extension type in the Metric TLV we can 4308 represent MetricType more elegantly in the RFC 5444 message. 4310 o Updated Overview to be slightly more concise. 4312 o Moved MetricType next to Metric when mentioned for better flow. 4314 o Added text to Applicability to address comments on mailing list 4315 regarding gateway behavior and NHDP HELLO messages. 4317 o Removed paragraph in AODVv2 Message Transmission section regarding 4318 TTL. 4320 o Added reference where precursors are mentioned in route table 4321 entry. 4323 o Added text to bidirectionality explanation regarding NHDP HELLO 4324 messages and lower layer triggers. 4326 o Clarified blacklist removal with SHOULD rather than MAY. 4328 o Removed pseudo-code from section on evaluating incoming routing 4329 information. 4331 o Clarified rules for expunging route entries on memory-constrained 4332 devices. 4334 o Clarified the use of exponential backoff for route discovery 4335 attempts. 4337 o Small updates to message sections. Removed steps about checking 4338 if neighbors. 4340 o Renamed RFC 5444 parser to multiplexer in Section 10. 4342 o Removed "optional feature" to include multiple addresses in RERR. 4344 o Removed MetricType from the Message TLV Type Specification. 4346 o Updated Security Considerations. 4348 o Added reference to RFC 7182. 4350 o Small updates to message algorithms, including moving MetricType 4351 from Message TLV to the Metric TLV in the Address Block TLV Block, 4352 and only generating RERR if an Active route was made Invalid. 4354 E.4. Changes between revisions 6 and 7 4356 This section lists the changes since AODVv2 revision ...-06.txt 4358 o Added Victoria Mercieca as co-author. 4360 o Reorganized protocol message descriptions into major subsections 4361 for each protocol message. For protocol messages, organized 4362 processing into Generation, Reception, and Regeneration 4363 subsections. 4365 o Separated RREQ and RREP message processing description into 4366 separate major subsection which had previously been combined into 4367 RteMsg description. 4369 o Enlarged RREQ Table function to include similar processing for 4370 optional flooded RREP messages. The table name has been 4371 correspondingly been changed to be the Table for Multicast 4372 RteMsgs. 4374 o Moved sections for Multiple Interfaces and AODVv2 Control Message 4375 Generation Limits to be major subsections of the AODVv2 Protocol 4376 Operations section. 4378 o Reorganized the protocol message processing steps into the 4379 subsections as previously described, adopting a more step-by-step 4380 presentation. 4382 o Coalesced the router states Broken and Expired into a new combined 4383 state named the Invalid state. No changes in processing are 4384 required for this. 4386 o Merged the sections describing Next-hop Router Adjacency 4387 Monitoring and Blacklists. 4389 o Specified that routes created during Route Discovery are marked as 4390 Idle routes. If they are used for carrying data they become 4391 Active routes. 4393 o Added Route.LastSeqNumUpdate information to route table, so that 4394 route activity and sequence number validity can be tracked 4395 separately. An active route can still forward traffic even if the 4396 sequence number has not been refreshed within MAX_SEQNUM_LIFETIME. 4398 o Mandated implementation of RREP_Ack as response to AckReq Message 4399 TLV in RREP messages. 4400 Added field to RREP_Ack to ensure correspondence to the correct 4401 AckReq message. 4403 o Added explanations for what happens if protocol constants are 4404 given different values on different AODVv2 routers. 4406 o Specified that AODVv2 implementations are free to choose their own 4407 heuristics for reducing multicast overhead, including RFC 6621. 4409 o Added appendix to identify AODVv2 requirements from OS 4410 implementation of IP and ICMP. 4412 o Deleted appendix showing example RFC 5444 packet formats. 4414 o Clarification on the use of RFC 5497 VALIDITY_TIME. 4416 o In Terminology, deleted superfluous definitions, added missing 4417 definitions. 4419 o Numerous editorial improvements and clarifications. 4421 E.5. Changes between revisions 5 and 6 4423 This section lists the changes between AODVv2 revisions ...-05.txt 4424 and ...-06.txt. 4426 o Added Lotte Steenbrink as co-author. 4428 o Reorganized section on Metrics to improve readability by putting 4429 specific topics into subsections. 4431 o Introduced concept of data element, which is used to clarify the 4432 method of enabling RFC 5444 representation for AODVv2 data 4433 elements. A list of Data Elements was introduced in section 3, 4434 which provides a better understanding of their role than was 4435 previously supplied by the table of notational devices. 4437 o Replaced instances of OrigNode by OrigAddr whenever the more 4438 specific meaning is appropriate. Similarly for instances of other 4439 node versus address terminology. 4441 o Introduced concepts of PrefixLengthList and MetricList in order to 4442 avoid use of index-based terminology such as OrigNdx and TargNdx. 4444 o Added section 5, "AODVv2 Message Transmission", describing the 4445 intended interface to RFC 5444. 4447 o Included within the main body of the specification the mandatory 4448 setting of the TLV flag thassingleindex for TLVs OrigSeqNum and 4449 TargSeqNum. 4451 o Removed the Route.Timed state. Created a new flag for route table 4452 entries known as Route.Timed. This flag can be set when the route 4453 is in the active state. Previous description would require that 4454 the route table entry be in two states at the same time, which 4455 seems to be misleading. The new flag is used to clarify other 4456 specification details for Timed routes. 4458 o Created table 3 to show the correspondence between AODVv2 data 4459 elements and RFC 5444 message components. 4461 o Replaced "invalid" terminology by the more specific terms "broken" 4462 or "expired" where appropriate. 4464 o Eliminated the instance of duplicate specification for inclusion 4465 of OrigNode (now, OrigAddr) in the message. 4467 o Corrected the terminology to be Mid instead of Tail for the 4468 trailing address bits of OrigAddr and TargAddr for the example 4469 message formats in the appendices. 4471 o Repaired remaining instances of phraseology that could be 4472 construed as indicating that AODV only supports a single network 4473 interface. 4475 o Numerous editorial improvements and clarifications. 4477 E.6. Changes between revisions 4 and 5 4479 This section lists the changes between AODVv2 revisions ...-04.txt 4480 and ...-05.txt. 4482 o Normative text moved out of definitions into the relevant section 4483 of the body of the specification. 4485 o Editorial improvements and improvements to consistent terminology 4486 were made. Replaced "retransmit" by the slightly more accurate 4487 term "regenerate". 4489 o Issues were resolved as discussed on the mailing list. 4491 o Changed definition of LoopFree as suggested by Kedar Namjoshi and 4492 Richard Trefler to avoid the failure condition that they have 4493 described. In order to make understanding easier, replaced 4494 abstract parameters R1 by RteMsg and R2 by Route to reduce the 4495 level of abstraction when the function LoopFree is discussed. 4497 o Added text to clarify that different metrics may have different 4498 data types and different ranges of acceptable values. 4500 o Added text to section "RteMsg Structure" to emphasize the proper 4501 use of RFC 5444. 4503 o Included within the main body of the specification the mandatory 4504 setting of the TLV flag thassingleindex for TLVs OrigSeqNum and 4505 TargSeqNum. 4507 o Made more extensive use of the AdvRte terminology, in order to 4508 better distinguish between the incoming RREQ or RREP message 4509 (i.e., RteMsg) versus the route advertised by the RteMsg (i.e., 4510 AdvRte). 4512 E.7. Changes between revisions 3 and 4 4514 This section lists the changes between AODVv2 revisions ...-03.txt 4515 and ...-04.txt. 4517 o An appendix was added to exhibit algorithmic code for 4518 implementation of AODVv2 functions. 4520 o Numerous editorial improvements and improvements to consistent 4521 terminology were made. Terminology related to prefix lengths was 4522 made consistent. Some items listed in "Notational Conventions" 4523 were no longer used, and so deleted. 4525 o Issues were resolved as discussed on the mailing list. 4527 o Appropriate instances of "may" were changed to "MAY". 4529 o Definition inserted for "upstream". 4531 o Route.Precursors included as an *optional* route table field 4533 o Reworded text to avoid use of "relevant". 4535 o Deleted references to "DestOnly" flag. 4537 o Refined statements about MetricType TLV to allow for omission when 4538 MetricType == HopCount. 4540 o Bulletized list in section 8.1 4542 o ENABLE_IDLE_UNREACHABLE renamed to be ENABLE_IDLE_IN_RERR 4544 o Transmission and subscription to LL-MANET-Routers converted to 4545 MUST from SHOULD. 4547 E.8. Changes between revisions 2 and 3 4549 This section lists the changes between AODVv2 revisions ...-02.txt 4550 and ...-03.txt. 4552 o The "Added Node" feature was removed. This feature was intended 4553 to enable additional routing information to be carried within a 4554 RREQ or a RREP message, thus increasing the amount of topological 4555 information available to nodes along a routing path. However, 4556 enlarging the packet size to include information which might never 4557 be used can increase congestion of the wireless medium. The 4558 feature can be included as an optional feature at a later date 4559 when better algorithms are understood for determining when the 4560 inclusion of additional routing information might be worthwhile. 4562 o Numerous editorial improvements and improvements to consistent 4563 terminology were made. Instances of OrigNodeNdx and TargNodeNdx 4564 were replaced by OrigNdx and TargNdx, to be consistent with the 4565 terminology shown in Table 2. 4567 o Example RREQ and RREP message formats shown in the Appendices were 4568 changed to use OrigSeqNum and TargSeqNum message TLVs instead of 4569 using the SeqNum message TLV. 4571 o Inclusion of the OrigNode's SeqNum in the RREP message is not 4572 specified. The processing rules for the OrigNode's SeqNum were 4573 incompletely specified in previous versions of the draft, and very 4574 little benefit is foreseen for including that information, since 4575 reverse path forwarding is used for the RREP. 4577 o Additional acknowledgements were included, and contributors names 4578 were alphabetized. 4580 o Definitions in the Terminology section capitalize the term to be 4581 defined. 4583 o Uncited bibliographic entries deleted. 4585 o Ancient "Changes" sections were deleted. 4587 Authors' Addresses 4589 Charles E. Perkins 4590 Futurewei Inc. 4591 2330 Central Expressway 4592 Santa Clara, CA 95050 4593 USA 4595 Phone: +1-408-330-4586 4596 Email: charliep@computer.org 4598 Stan Ratliff 4599 Idirect 4600 13861 Sunrise Valley Drive, Suite 300 4601 Herndon, VA 20171 4602 USA 4604 Email: ratliffstan@gmail.com 4606 John Dowdell 4607 Airbus Defence and Space 4608 Celtic Springs 4609 Newport, Wales NP10 8FZ 4610 United Kingdom 4612 Email: john.dowdell@airbus.com 4614 Lotte Steenbrink 4615 HAW Hamburg, Dept. Informatik 4616 Berliner Tor 7 4617 D-20099 Hamburg 4618 Germany 4620 Email: lotte.steenbrink@haw-hamburg.de 4621 Victoria Mercieca 4622 Airbus Defence and Space 4623 Celtic Springs 4624 Newport, Wales NP10 8FZ 4625 United Kingdom 4627 Email: victoria.mercieca@airbus.com