idnits 2.17.1 draft-ietf-manet-aodvv2-05.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 4 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The exact meaning of the all-uppercase expression 'MAY NOT' is not defined in RFC 2119. If it is intended as a requirements expression, it should be rewritten using one of the combinations defined in RFC 2119; otherwise it should not be all-uppercase. == The expression 'MAY NOT', while looking like RFC 2119 requirements text, is not defined in RFC 2119, and should not be used. Consider using 'MUST NOT' instead (if that is what you mean). Found 'MAY NOT' in this paragraph: Active An Active route is in current use for forwarding packets. The route's state determines the operations that can be performed on the route table entry. During use, an Active route is maintained continuously by AODVv2 and is considered to remain active as long as it is used at least once during every ACTIVE_INTERVAL. When a route is no longer Active, it becomes an Idle route. Idle An Idle route can be used for forwarding packets, even though it is not in current use. If an Idle route is used to forward a packet, it becomes an Active route once again. After an Idle route remains idle for MAX_IDLETIME, it becomes an Expired route. Expired After a route has been idle for too long, it expires, and may no longer be used for forwarding packets. An Expired route is not used for forwarding, but the sequence number information can be maintained until the destination sequence number has had no updates for MAX_SEQNUM_LIFETIME; after that time, old sequence number information is considered no longer valuable and the Expired route MUST BE expunged. Broken A route marked as Broken cannot be used for forwarding packets but still has valid destination sequence number information. When the link to a route's next hop is broken, the route is marked as being Broken, and afterwards the route MAY NOT be used. Timed The expiration of a Timed route is controlled by the Route.ExpirationTime time of the route table entry (instead of MAX_IDLETIME). Until that time, a Timed route can be used for forwarding packets. Afterwards, the route must be Expired (or expunged). -- The document date (October 27, 2014) is 3441 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 154, but not defined == Missing Reference: 'Address' is mentioned on line 303, but not defined -- Looks like a reference, but probably isn't: '1' on line 313 == Missing Reference: 'N' is mentioned on line 314, but not defined -- Looks like a reference, but probably isn't: '3' on line 701 == Missing Reference: 'OrigNode' is mentioned on line 1219, but not defined == Missing Reference: 'OrigNdx' is mentioned on line 1235, but not defined == Missing Reference: 'TargNdx' is mentioned on line 1233, but not defined == Missing Reference: 'TargNode' is mentioned on line 1127, but not defined == Missing Reference: 'UnreachableNodes' is mentioned on line 1335, but not defined == Missing Reference: 'TBD' is mentioned on line 1789, but not defined -- Looks like a reference, but probably isn't: '0' on line 2519 == Outdated reference: A later version (-03) exists of draft-perkins-irrep-02 Summary: 0 errors (**), 0 flaws (~~), 13 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad hoc Networks Working Group C. Perkins 3 Internet-Draft Futurewei 4 Intended status: Standards Track S. Ratliff 5 Expires: April 30, 2015 Cisco 6 J. Dowdell 7 Airbus Defence and Space 8 October 27, 2014 10 Dynamic MANET On-demand (AODVv2) Routing 11 draft-ietf-manet-aodvv2-05 13 Abstract 15 The revised Ad Hoc On-demand Distance Vector (AODVv2) routing 16 protocol is intended for use by mobile routers in wireless, multihop 17 networks. AODVv2 determines unicast routes among AODVv2 routers 18 within the network in an on-demand fashion, offering rapid 19 convergence in dynamic topologies. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on April 30, 2015. 38 Copyright Notice 40 Copyright (c) 2014 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 4 56 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 57 3. Notational Conventions . . . . . . . . . . . . . . . . . . . 7 58 4. Applicability Statement . . . . . . . . . . . . . . . . . . . 8 59 5. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 10 60 5.1. Route Table Entry . . . . . . . . . . . . . . . . . . . . 10 61 5.2. Bidirectional Connectivity and Blacklists . . . . . . . . 12 62 5.3. Router Clients and Client Networks . . . . . . . . . . . 12 63 5.4. AODVv2 Message Header Fields and Information Elements . . 13 64 5.5. Sequence Numbers . . . . . . . . . . . . . . . . . . . . 14 65 5.6. Enabling Alternate Metrics . . . . . . . . . . . . . . . 14 66 5.7. RREQ Table: Received RREQ Messages . . . . . . . . . . . 16 67 6. AODVv2 Operations on Route Table Entries . . . . . . . . . . 17 68 6.1. Evaluating Incoming Routing Information . . . . . . . . . 18 69 6.2. Applying Route Updates To Route Table Entries . . . . . . 19 70 6.3. Route Table Entry Timeouts . . . . . . . . . . . . . . . 20 71 7. Routing Messages RREQ and RREP (RteMsgs) . . . . . . . . . . 20 72 7.1. Route Discovery Retries and Buffering . . . . . . . . . . 21 73 7.2. RteMsg Structure . . . . . . . . . . . . . . . . . . . . 22 74 7.3. RREQ Generation . . . . . . . . . . . . . . . . . . . . . 23 75 7.4. RREP Generation . . . . . . . . . . . . . . . . . . . . . 24 76 7.5. Handling a Received RteMsg . . . . . . . . . . . . . . . 25 77 7.5.1. Additional Handling for Incoming RREQ . . . . . . . . 26 78 7.5.2. Additional Handling for Incoming RREP . . . . . . . . 27 79 7.6. Suppressing Redundant RREQ messages . . . . . . . . . . . 27 80 8. Route Maintenance and RERR Messages . . . . . . . . . . . . . 28 81 8.1. Maintaining Route Lifetimes During Packet Forwarding . . 28 82 8.2. Active Next-hop Router Adjacency Monitoring . . . . . . . 29 83 8.3. RERR Generation . . . . . . . . . . . . . . . . . . . . . 29 84 8.3.1. Case 1: Undeliverable Packet . . . . . . . . . . . . 30 85 8.3.2. Case 2: Broken Link . . . . . . . . . . . . . . . . . 31 86 8.4. Receiving and Handling RERR Messages . . . . . . . . . . 31 87 9. Unknown Message and TLV Types . . . . . . . . . . . . . . . . 33 88 10. Simple Internet Attachment . . . . . . . . . . . . . . . . . 33 89 11. Multiple Interfaces . . . . . . . . . . . . . . . . . . . . . 34 90 12. AODVv2 Control Message Generation Limits . . . . . . . . . . 34 91 13. Optional Features . . . . . . . . . . . . . . . . . . . . . . 34 92 13.1. Expanding Rings Multicast . . . . . . . . . . . . . . . 34 93 13.2. Intermediate RREP . . . . . . . . . . . . . . . . . . . 35 94 13.3. Precursor Lists and Notifications . . . . . . . . . . . 35 95 13.3.1. Overview . . . . . . . . . . . . . . . . . . . . . . 35 96 13.3.2. Precursor Notification Details . . . . . . . . . . . 35 98 13.4. Multicast RREP Response to RREQ . . . . . . . . . . . . 36 99 13.5. RREP_ACK . . . . . . . . . . . . . . . . . . . . . . . . 36 100 13.6. Message Aggregation . . . . . . . . . . . . . . . . . . 37 101 14. Administratively Configurable Parameters and Timer Values . . 37 102 14.1. Timers . . . . . . . . . . . . . . . . . . . . . . . . . 37 103 14.2. Protocol constants . . . . . . . . . . . . . . . . . . . 38 104 14.3. Administrative (functional) controls . . . . . . . . . . 38 105 14.4. Other administrative parameters and lists . . . . . . . 39 106 15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 107 15.1. AODVv2 Message Types Specification . . . . . . . . . . . 39 108 15.2. Message TLV Type Specification . . . . . . . . . . . . . 40 109 15.3. Address Block TLV Specification . . . . . . . . . . . . 40 110 15.4. Metric Type Number Allocation . . . . . . . . . . . . . 40 111 16. Security Considerations . . . . . . . . . . . . . . . . . . . 41 112 17. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 43 113 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 43 114 18.1. Normative References . . . . . . . . . . . . . . . . . . 43 115 18.2. Informative References . . . . . . . . . . . . . . . . . 44 116 Appendix A. Example Algorithms for AODVv2 Protocol Operations . 45 117 A.1. Subroutines for AODVv2 Protocol Operations . . . . . . . 47 118 A.2. Example Algorithms for AODVv2 RREQ Operations . . . . . . 47 119 A.2.1. Generate_RREQ . . . . . . . . . . . . . . . . . . . . 47 120 A.2.2. Receive_RREQ . . . . . . . . . . . . . . . . . . . . 48 121 A.2.3. Regenerate_RREQ . . . . . . . . . . . . . . . . . . . 49 122 A.3. Example Algorithms for AODVv2 RREP Operations . . . . . . 50 123 A.3.1. Generate_RREP . . . . . . . . . . . . . . . . . . . . 51 124 A.3.2. Receive_RREP . . . . . . . . . . . . . . . . . . . . 52 125 A.3.3. Regenerate_RREP . . . . . . . . . . . . . . . . . . . 53 126 A.3.4. Consume_RREP . . . . . . . . . . . . . . . . . . . . 54 127 A.4. Example Algorithms for AODVv2 RERR Operations . . . . . . 54 128 A.4.1. Generate_RERR . . . . . . . . . . . . . . . . . . . . 54 129 A.4.2. Receive_RERR . . . . . . . . . . . . . . . . . . . . 55 130 A.4.3. Regenerate_RERR . . . . . . . . . . . . . . . . . . . 56 131 A.5. Example Algorithms for AODVv2 RREP-Ack Operations . . . . 58 132 A.5.1. Generate_RREP_Ack . . . . . . . . . . . . . . . . . . 58 133 A.5.2. Consume_RREP_Ack . . . . . . . . . . . . . . . . . . 58 134 A.5.3. Timeout_RREP_Ack . . . . . . . . . . . . . . . . . . 58 135 Appendix B. Example RFC 5444-compliant packet formats . . . . . 58 136 B.1. RREQ Message Format . . . . . . . . . . . . . . . . . . . 59 137 B.2. RREP Message Format . . . . . . . . . . . . . . . . . . . 61 138 B.3. RERR Message Format . . . . . . . . . . . . . . . . . . . 63 139 B.4. RREP_ACK Message Format . . . . . . . . . . . . . . . . . 64 140 Appendix C. Changes since revision ...-04.txt . . . . . . . . . 64 141 Appendix D. Changes since revision ...-03.txt . . . . . . . . . 65 142 Appendix E. Changes since revision ...-02.txt . . . . . . . . . 65 143 Appendix F. Multi-homing Considerations . . . . . . . . . . . . 66 144 Appendix G. Shifting Network Prefix Advertisement Between AODVv2 145 Routers . . . . . . . . . . . . . . . . . . . . . . 66 147 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 66 149 1. Overview 151 The revised Ad Hoc On-demand Distance Vector (AODVv2) routing 152 protocol [formerly named DYMO] enables on-demand, multihop unicast 153 routing among AODVv2 routers in mobile ad hod networks 154 [MANETs][RFC2501]. The basic operations of the AODVv2 protocol are 155 route discovery and route maintenance. Route discovery is performed 156 when an AODVv2 router must transmit a packet towards a destination 157 for which it does not have a route. Route maintenance is performed 158 to avoid prematurely expunging routes from the route table, and to 159 avoid dropping packets when an active route breaks. 161 During route discovery, the originating AODVv2 router (RREQ_Gen) 162 multicasts a Route Request message (RREQ) to find a route toward some 163 target destination. Using a hop-by-hop regeneration algorithm, each 164 AODVv2 router receiving the RREQ message records a route toward the 165 originator. When the target's AODVv2 router (RREP_Gen) receives the 166 RREQ, it records a route toward RREQ_Gen and generates a Route Reply 167 (RREP) unicast toward RREQ_Gen. Each AODVv2 router that receives the 168 RREP stores a route toward the target, and again unicasts the RREP 169 toward the originator. When RREQ_Gen receives the RREP, routes have 170 then been established between RREQ_Gen (the originating AODVv2 171 router) and RREP_Gen (the target's AODVv2 router) in both directions. 173 Route maintenance consists of two operations. In order to maintain 174 active routes, AODVv2 routers extend route lifetimes upon 175 successfully forwarding a packet. When a data packet is received to 176 be forwarded but there is no valid route for the destination, then 177 the AODVv2 router of the source of the packet is notified via a Route 178 Error (RERR) message. Each upstream router that receives the RERR 179 marks the route as broken. Before such an upstream AODVv2 router 180 could forward a packet to the same destination, it would have to 181 perform route discovery again for that destination. RERR messages 182 are also used to notify upstream routers when routes break (say, due 183 to loss of a link to a neighbor). 185 AODVv2 uses sequence numbers to assure loop freedom [Perkins99], 186 similarly to AODV. Sequence numbers enable AODVv2 routers to 187 determine the temporal order of AODVv2 route discovery messages, 188 thereby avoiding use of stale routing information. Unlike AODV, 189 AODVv2 uses RFC 5444 message and TLV formats. 191 2. Terminology 193 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 194 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 195 "OPTIONAL" in this document are to be interpreted as described in 196 [RFC2119]. 198 This document uses terminology from [RFC5444]. 200 This document defines the following terms: 202 Adjacency 203 A bi-directional relationship between neighboring AODVv2 routers 204 for the purpose of exchanging routing information. Not every pair 205 of neighboring routers will necessarily form an adjacency. 206 Monitoring of adjacencies where packets are being forwarded is 207 required (see Section 8.2). 208 AODVv2 Router 209 An IP addressable device in the ad-hoc network that performs the 210 AODVv2 protocol operations specified in this document. 211 AODVv2 Sequence Number (SeqNum) 212 Same as Sequence Number. 213 Client Interface 214 An interface that directly connects Router Clients to the Router. 215 Current_Time 216 The current time as maintained by the AODVv2 router. 217 Disregard 218 Ignore for further processing (see Section 5.4). 219 Handling Router (HandlingRtr) 220 HandlingRtr denotes the AODVv2 router receiving and handling an 221 AODVv2 message. 222 Incoming Link 223 A link over which an AODVv2 Router has received a message from an 224 adjacent router. 225 MANET 226 A Mobile Ad Hoc Network as defined in [RFC2501]. 227 Node 228 An IP addressable device in the ad-hoc network. A node may be an 229 AODVv2 router, or it may be a device in the network that does not 230 perform any AODVv2 protocol operations. All nodes in this 231 document are either AODVv2 Routers or else Router Clients. 232 Originating Node (OrigNode) 233 The Originating Node is the node that launched the application 234 requiring communication with the Target Node. If OrigNode is a 235 Router Client, its AODVv2 router (RREQ_Gen) has the responsibility 236 to generate a AODVv2 RREQ message on behalf of OrigNode as 237 necessary to discover a route. 238 Reactive 239 A protocol operation is said to be "reactive" if it is performed 240 only in reaction to specific events. As used in this document, 241 "reactive" is synonymous with "on-demand". 242 Routable Unicast IP Address 243 A routable unicast IP address is a unicast IP address that is 244 scoped sufficiently to be forwarded by a router. Globally-scoped 245 unicast IP addresses and Unique Local Addresses (ULAs) [RFC4193] 246 are examples of routable unicast IP addresses. 247 Route Error (RERR) 248 A RERR message is used to indicate that an AODVv2 router does not 249 have a route toward one or more particular destinations. 250 Route Reply (RREP) 251 A RREP message is used to establish a route between the Target 252 Node and the Originating Node, at all the AODVv2 routers between 253 them. 254 Route Request (RREQ) 255 An AODVv2 router uses a RREQ message to discover a valid route to 256 a particular destination address, called the Target Node. An 257 AODVv2 router processing a RREQ receives routing information for 258 the Originating Node. 259 Router Client 260 A node that requires the services of an AODVv2 router for route 261 discovery and maintenance. An AODVv2 router is always its own 262 client, so that its list of client IP addresses is never empty. 263 Router Interface 264 An interface supporting the transmission or reception of Router 265 Messages. 266 RREP Generating Router (RREP_Gen) 267 The RREP Generating Router is the AODVv2 router that serves 268 TargNode. RREP_Gen generates the RREP message to advertise a 269 route towards TargNode from OrigNode. 270 RREQ Generating Router (RREQ_Gen) 271 The RREQ Generating Router is the AODVv2 router that serves 272 OrigNode. RREQ_Gen generates the RREQ message to discover a route 273 for TargNode. 274 Sequence Number (SeqNum) 275 Each AODVv2 router MUST maintain an unsigned integer known as the 276 router's "Sequence Number". The Sequence Number guarantees the 277 temporal order of routing information to maintain loop-free 278 routes, and fulfills the same role as the "Destination Sequence 279 Number" of DSDV [Perkins94], and as the AODV Sequence Number in 280 RFC 3561[RFC3561]. The value zero (0) is reserved to indicate 281 that the Sequence Number for an address is unknown. 282 Target Node (TargNode) 283 The Target Node denotes the node towards which a route is needed. 284 Type-Length-Value structure (TLV) 285 A generic way to represent information as specified in [RFC5444]. 286 Unreachable Node (UnreachableNode) 287 An UnreachableNode is a node for which a valid route is not known. 288 upstream 289 In the direction from TargNode to OrigNode. 290 Valid route 291 A route that can be used for forwarding; in other words a route 292 that is not Broken or Expired. 294 3. Notational Conventions 296 This document uses the conventions found in Table 1 to describe 297 information in the fields from [RFC5444]. 299 +------------------------+------------------------------------------+ 300 | Notation | Information Location and/or Meaning | 301 +------------------------+------------------------------------------+ 302 | Route[Address] | A route table entry towards Address | 303 | Route[Address].{field} | A field in a route table entry | 304 | -- | -- | 305 | | RFC 5444 Message Header | 306 | | RFC 5444 Message Header | 307 | AddrBlk | an RFC 5444 Address TLV Block | 308 | AddrBlk[1] | The first address slot in AddrBlk | 309 | AddrBlk[N] | The Nth address slot in AddrBlk | 310 | OrigNdx | The index of OrigNode within the AddrBlk | 311 | TargNdx | The index of TargNode within the AddrBlk | 312 | AddrTLV | an RFC 5444 Address Block TLV | 313 | AddrTLV[1] | the first item in AddrTLV | 314 | AddrTLV[N] | the Nth item in AddrTLV | 315 | Metric_TLV | Metric AddrTLV for AddrBlk | 316 | SeqNum_TLV | Sequence Number AddrTLV for AddrBlk | 317 | OrigSeqNum_TLV | Originating Node Sequence Number AddrTLV | 318 | TargSeqNum_TLV | Target Node Sequence Number AddrTLV | 319 | -- | -- | 320 | OrigNode | Originating Node | 321 | RREQ_Gen | AODVv2 router originating an RREQ | 322 | RREP_Gen | AODVv2 router responding to an RREQ | 323 | RteMsg | Either RREQ or RREP | 324 | RteMsg.{field} | Field in RREQ or RREP | 325 | AdvRte | a route advertised in an incoming RteMsg | 326 | HandlingRtr | Handling Router | 327 | TargNode | Target Node | 328 | UnreachableNode | Unreachable Node | 329 +------------------------+------------------------------------------+ 331 Table 1 333 4. Applicability Statement 335 The AODVv2 routing protocol is a reactive routing protocol designed 336 for stub (i.e., non-transit) or disconnected (i.e., from the 337 Internet) mobile ad hoc networks (MANETs). AODVv2 handles a wide 338 variety of mobility patterns by determining routes on-demand. AODVv2 339 also handles a wide variety of traffic patterns. In networks with a 340 large number of routers, AODVv2 is best suited for relatively sparse 341 traffic scenarios where any particular router forwards packets to 342 only a small percentage of the AODVv2 routers in the network, due to 343 the on-demand nature of route discovery and route maintenance. 344 AODVv2 supports routers with multiple interfaces, as long as each 345 interface has its own (unicast routeable) IP address; the set of all 346 network interfaces supporting AODVv2 is administratively configured 347 in a list (namely, AODVv2_INTERFACES). 349 Although AODVv2 is closely related to AODV [RFC3561], and shares some 350 features of DSR [RFC4728], AODVv2 is not interoperable with either of 351 those other two protocols. 353 AODVv2 is applicable to memory constrained devices, since only a 354 little routing state is maintained in each AODVv2 router. Routes 355 that are not needed for forwarding data do not have to be maintained, 356 in contrast to proactive routing protocols that require routing 357 information to all routers within the MANET be maintained. 359 In addition to routing for its own local applications, each AODVv2 360 router can also route on behalf of other non-routing nodes (in this 361 document, "Router Clients"), reachable via Client Interfaces. Each 362 AODVv2 router, if serving router clients other than itself, SHOULD be 363 configured with information about the IP addresses of its clients, 364 using any suitable method. In the initial state, no AODVv2 router is 365 required to have information about the relationship between any other 366 AODVv2 router and its Router Clients (see Section 5.3). 368 The coordination among multiple AODVv2 routers to distribute routing 369 information correctly for a shared address (i.e. an address that is 370 advertised and can be reached via multiple AODVv2 routers) is not 371 described in this document. The AODVv2 router operation of shifting 372 responsibility for a routing client from one AODVv2 router to another 373 is described in Appendix G. Address assignment procedures are 374 entirely out of scope for AODVv2. A Router Client SHOULD NOT be 375 served by more than one AODVv2 router at any one time. 377 AODVv2 routers perform route discovery to find a route toward a 378 particular destination. AODVv2 routers MUST must be configured to 379 respond to RREQs for themselves and their clients. When AODVv2 is 380 the only protocol interacting with the forwarding table, AODVv2 MAY 381 be configured to perform route discovery for all unknown unicast 382 destinations. 384 AODVv2 only supports bidirectional links. In the case of possible 385 unidirectional links, blacklists (see Section 5.2) SHOULD be used, or 386 other means (e.g. adjacency establishment with only neighboring 387 routers that have bidirectional communication as indicated by NHDP 388 [RFC6130]) of assuring and monitoring bi-directionality are 389 recommended. Otherwise, persistent packet loss or persistent 390 protocol failures could occur. The cost of bidirectional link L 391 (denoted Cost(L)) may depend upon the direction across the link for 392 which the cost is measured. If received over a link that is 393 unidirectional, metric information from incoming AODVv2 messages MUST 394 NOT be used for route table updates. 396 The routing algorithm in AODVv2 may be operated at layers other than 397 the network layer, using layer-appropriate addresses. The routing 398 algorithm makes use of some persistent state; if there is no 399 persistent storage available for this state, recovery can impose a 400 performance penalty (e.g., in case of AODVv2 router reboots). 402 5. Data Structures 404 5.1. Route Table Entry 406 The route table entry is a conceptual data structure. 407 Implementations MAY use any internal representation so long as it 408 provides access to the information specified below. 410 A route table entry has the following fields: 412 Route.Address 413 The address or address prefix of one or more TargNode(s) 414 Route.PrefixLength 415 The length of the address or prefix. If the value of 416 Route.PrefixLength is less than the length of addresses in the 417 address family used by the AODVv2 routers, the associated address 418 is an address prefix, rather than an address. A PrefixLength is 419 stored for every route in the route table. 420 Route.SeqNum 421 The Sequence Number associated with Route.Address, as obtained 422 from the last packet that successfully updated this route table 423 entry. 424 Route.NextHopAddress 425 The IP address of the adjacent AODVv2 router used for the path 426 toward the Route.Address 427 Route.NextHopInterface 428 The interface used to send packets toward Route.Address 429 Route.LastUsed 430 The time that this route was last used 431 Route.ExpirationTime 432 The time at which this route must expire 433 Route.MetricType 434 The type of the metric for the route towards Route.Address 435 Route.Metric 436 The cost of the route towards Route.Address expressed in units 437 consistent with Route.MetricType 438 Route.State 439 The last *known* state of the route. Route.State is one of the 440 following: Active, Idle, Expired, Broken or Timed. 442 Route.Precursors (optional) 443 A list of upstream nodes using the route. 445 A route table entry (i.e., a route) is in one of the following 446 states: 448 Active 449 An Active route is in current use for forwarding packets. The 450 route's state determines the operations that can be performed on 451 the route table entry. During use, an Active route is maintained 452 continuously by AODVv2 and is considered to remain active as long 453 as it is used at least once during every ACTIVE_INTERVAL. When a 454 route is no longer Active, it becomes an Idle route. 455 Idle 456 An Idle route can be used for forwarding packets, even though it 457 is not in current use. If an Idle route is used to forward a 458 packet, it becomes an Active route once again. After an Idle 459 route remains idle for MAX_IDLETIME, it becomes an Expired route. 460 Expired 461 After a route has been idle for too long, it expires, and may no 462 longer be used for forwarding packets. An Expired route is not 463 used for forwarding, but the sequence number information can be 464 maintained until the destination sequence number has had no 465 updates for MAX_SEQNUM_LIFETIME; after that time, old sequence 466 number information is considered no longer valuable and the 467 Expired route MUST BE expunged. 468 Broken 469 A route marked as Broken cannot be used for forwarding packets but 470 still has valid destination sequence number information. When the 471 link to a route's next hop is broken, the route is marked as being 472 Broken, and afterwards the route MAY NOT be used. 473 Timed 474 The expiration of a Timed route is controlled by the 475 Route.ExpirationTime time of the route table entry (instead of 476 MAX_IDLETIME). Until that time, a Timed route can be used for 477 forwarding packets. Afterwards, the route must be Expired (or 478 expunged). 480 MAX_SEQNUM_LIFETIME is the time after a reboot during which an AODVv2 481 router MUST NOT transmit any routing messages. Thus, if all other 482 AODVv2 routers expunge routes to the rebooted router after that time 483 interval, the rebooted AODVv2 router's sequence number will not be 484 considered stale by any other AODVv2 router in the MANET. 486 5.2. Bidirectional Connectivity and Blacklists 488 To avoid repeated failure of Route Discovery, an AODVv2 router 489 (HandlingRtr) handling a RREP message MUST attempt to verify 490 connectivity towards RREQ_Gen. This MAY be done by including the 491 Acknowledgement Request (AckReq) message TLV (see Section 15.2) in 492 the RREP. In reply to an AckReq, an RREP_ACK message message MUST be 493 sent. If the verification is not received within 494 UNICAST_MESSAGE_SENT_TIMEOUT, HandlingRtr MUST put the upstream 495 neighbor in the blacklist. RREQs received from a blacklisted router, 496 or any router over a link that is known to be incoming-only, MUST NOT 497 be regenerated by HandlingRtr. However, the upstream neighbor SHOULD 498 NOT be permanently blacklisted; after a certain time 499 (MAX_BLACKLIST_TIME), it SHOULD once again be considered as a viable 500 upstream neighbor for route discovery operations. 502 For this purpose, a list of blacklisted routers along with their time 503 of removal SHOULD be maintained: 505 Blacklist.Router 506 The IP address of the router that did not verify bidirectional 507 connectivity. 508 Blacklist.RemoveTime 509 The time at which Blacklist.Router MAY be removed from the 510 blacklist. 512 5.3. Router Clients and Client Networks 514 An AODVv2 router may offer routing services to other nodes that are 515 not AODVv2 routers; such nodes are defined as Router Clients in this 516 document. 518 For this purpose, CLIENT_ADDRESSES must be configured on each AODVv2 519 router with the following information: 521 Client IP address 522 The IP address of the node that requires routing service from the 523 AODVv2 router. 524 Client Prefix Length 525 The length of the routing prefix associated with the client IP 526 address. 528 If the Client Prefix Length is not the full length of the Client IP 529 address, then the prefix defines a Client Network. If an AODVv2 530 router is configured to serve a Client Network, then the AODVv2 531 router MUST serve every node that has an address within the range 532 defined by the routing prefix of the Client Network. The list of 533 Routing Clients for an AODVv2 router is never empty, since an AODVv2 534 router is always its own client as well. 536 5.4. AODVv2 Message Header Fields and Information Elements 538 In its default mode of operation, AODVv2 sends messages using the 539 parameters for port number and IP protocol specified in [RFC5498] to 540 carry protocol packets. By default, AODVv2 messages are sent with 541 the IP destination address set to the link-local multicast address 542 LL-MANET-Routers [RFC5498] unless otherwise specified. Therefore, 543 all AODVv2 routers MUST subscribe to LL-MANET-Routers [RFC5498] to 544 receive AODVv2 messages. In order to reduce multicast overhead, 545 regenerated multicast packets in MANETs SHOULD be done according to 546 methods specified in [RFC6621]. AODVv2 does not specify which method 547 should be used to restrict the set of AODVv2 routers that have the 548 responsibility to regenerate multicast packets. Note that multicast 549 packets MAY be sent via unicast. For example, this may occur for 550 certain link-types (non-broadcast media), for manually configured 551 router adjacencies, or in order to improve robustness. 553 The IPv4 TTL (IPv6 Hop Limit) field for all packets containing AODVv2 554 messages is set to 255. If a packet is received with a value other 555 than 255, any AODVv2 message contained in the packet MUST be 556 disregarded by AODVv2. This mechanism, known as "The Generalized TTL 557 Security Mechanism" (GTSM) [RFC5082] helps to assure that packets 558 have not traversed any intermediate routers. 560 IP packets containing AODVv2 protocol messages SHOULD be given 561 priority queuing and channel access. 563 AODVv2 messages are transmitted in messages that conform to the 564 packet and message format specified in [RFC5444]. Here is a brief 565 summary of the format. 567 A packet formatted according to RFC 5444 contains zero or more 568 messages. 569 A message contains a message header, message TLV block, and zero 570 or more address blocks. 571 Each address block MAY also have an associated TLV block; this TLV 572 block MAY encode multiple TLVs. Each such TLV may include an 573 array of values. The list of TLV values may be associated with 574 various subsets of the addresses in the address block. 576 If a packet contains only a single AODVv2 message and no packet TLVs, 577 it need only include a minimal Packet-Header [RFC5444]. The length 578 of an address (32 bits for IPv4 and 128 bits for IPv6) inside an 579 AODVv2 message is indicated by the msg-addr-length (MAL) in the msg- 580 header, as specified in [RFC5444]. 582 5.5. Sequence Numbers 584 Sequence Numbers allow AODVv2 routers to evaluate the freshness of 585 routing information. Each AODVv2 router in the network MUST maintain 586 its own sequence number. Each RREQ and RREP generated by an AODVv2 587 router includes that sequence number. Each AODVv2 router MUST make 588 sure that its sequence number is unique and monotonically increasing. 589 This can be achieved by incrementing it with every RREQ or RREP it 590 generates. 592 Every router receiving a RREQ or RREP can thus use the Sequence 593 Number of a RREQ or RREP as information concerning the freshness of 594 the packet's route update: if the new packet's Sequence Number is 595 lower than the one already stored in the route table, its information 596 is considered stale. 598 As a consequence, loop freedom is assured. 600 An AODVv2 router increments its SeqNum as follows. Most of the time, 601 SeqNum is incremented by simply adding one (1). But when the SeqNum 602 has the value of the largest possible number representable as a 603 16-bit unsigned integer (i.e., 65,535), it MUST be incremented by 604 setting to one (1). In other words, the sequence number after 65,535 605 is 1. 607 An AODVv2 router SHOULD maintain its SeqNum in persistent storage. 608 If an AODVv2 router's SeqNum is lost, it MUST take the following 609 actions to avoid the danger of routing loops. First, the AODVv2 610 router MUST invalidate all route table entries, by setting 611 Route.State = Broken for each entry. Furthermore the AODVv2 router 612 MUST wait for at least MAX_SEQNUM_LIFETIME before transmitting or 613 regenerating any AODVv2 RREQ or RREP messages. If an AODVv2 protocol 614 message is received during this waiting period, the AODVv2 router 615 SHOULD perform normal route table entry updates, but not forward the 616 message to other nodes. If a data packet is received for forwarding 617 to another destination during this waiting period, the AODVv2 router 618 MUST transmit a RERR message indicating that no route is available. 619 At the end of the waiting period the AODVv2 router sets its SeqNum to 620 one (1) and begins performing AODVv2 protocol operations again. 622 5.6. Enabling Alternate Metrics 624 AODVv2 route selection in MANETs depends upon associating metric 625 information with each route table entry. When presented with 626 candidate route update information, deciding whether to use the 627 update involves evaluating the metric. Some applications may require 628 metric information other than Hop Count, which has traditionally been 629 the default metric associated with routes in MANET. Unfortunately, 630 it is well known that reliance on Hop Count can cause selection of 631 the worst possible route in many situations. 633 It is beyond the scope of this document to describe how applications 634 specify route selection at the time they launch processing. One 635 possibility would be to provide a route metric preference as part of 636 the library routines for opening sockets. In view of the above 637 considerations, it is important to enable route selection based on 638 metric information other than Hop Count -- in other words, based on 639 "alternate metrics". Each such alternate metric measures a "cost" of 640 using the associated route, and there are many different kinds of 641 cost (latency, delay, monetary, energy, etc.). The range and data 642 type of each such alternate metric may be different. For instance, 643 the data type might be integers, or floating point numbers, or 644 restricted subsets thereof. 646 The most significant change when enabling use of alternate metrics is 647 to require the possibility of multiple routes to the same 648 destination, where the "cost" of each of the multiple routes is 649 measured by a different metric. Moreover, the method by which route 650 updates are tested for usefulness has to be slightly generalized to 651 depend upon a more abstract method of evaluation which, in this 652 document, is named "Cost(R)", where 'R' is the route for which the 653 Cost is to be evaluated. From the above, the route table information 654 for 'R' must always include the type of metric by which Cost(R) is 655 evaluated, so the metric type does not have to be shown as a distinct 656 parameter for Cost(R). Since determining loop freedom is known to 657 depend on comparing the Cost(R) of route update information to the 658 Cost(R) of an existing stored route using the same metric, AODVv2 659 must also be able to invoke an abstract routine which in this 660 document is called "LoopFree(R1, R2)". LoopFree(R1, R2) returns TRUE 661 when, (under the assumption of nondecreasing SeqNum during Route 662 Discovery) given that R2 is loop-free and Cost(R2) is the cost of 663 route R2, Cost(R1) is known to guarantee loop freedom of the route 664 R1. In this document, an AODVv2 router will only invoke LoopFree 665 (AdvRte, Route), for routes AdvRte and Route which use the same 666 metric to the same destination. AdvRte is the route advertised in an 667 incoming RREQ or RREP, and is used as parameter R1 for LoopFree. 668 Route is a route already existing in the AODVv2 router's route table, 669 and is used as parameter R2 for LoopFree. 671 Generally, HopCount may still be considered the default metric for 672 use in MANETs, notwithstanding the above objections. Each metric has 673 to have a Metric Type, and the Metric Type is allocated by IANA as 674 specified in [RFC6551]. Each Route has to include the Metric Type as 675 part of the route table entry for that route. Hop Count has Metric 676 Type assignment 3. The Cost of a route using Metric Type 3 is simply 677 the hop count between the router and the destination. Using Metric 678 Type 3, LoopFree (AdvRte, Route) is TRUE when Cost(AdvRte) <= 679 Cost(Route). The specification of Cost(R) and LoopFree(AdvRte, 680 Route) for metric types other than 3 is beyond the scope of this 681 document. 683 Whenever an AODV router receives metric information in an incoming 684 message, the value of the metric is as measured by the transmitting 685 router, and does not reflect the cost of traversing the incoming 686 link. In order to simplify the description of storing accrued route 687 costs in the route table, the Cost() function is also defined to 688 return the value of traversing a link 'L'. In other words, the 689 domain of the Cost() function is enlarged to include links as well as 690 routes. For Metric Type 3, (i.e., the HopCount metric) Cost(L) = 1 691 for all links L. The specification of Cost(L) for metric types other 692 than 3 is beyond the scope of this document. Whether the argument of 693 the Cost() function is a link or a route will, in this document, 694 always be clear. As a natural result of the way routes are looked up 695 according to conformant metric type, all intermediate routers 696 handling a RteMsg will assign the same metric type to all metric 697 information in the RteMsg. 699 For some metrics, a maximum value is defined, namely MAX_METRIC[i] 700 where 'i' is the Metric Type. AODVv2 does not store routes that cost 701 more than MAX_METRIC[i]. MAX_METRIC[3] is defined to be 702 MAX_HOPCOUNT, where as before 3 is the Metric Type of the HopCount 703 metric. MAX_HOPCOUNT MUST be larger than the AODVv2 network 704 diameter. Otherwise, AODVv2 protocol messages may not reach their 705 intended destinations. 707 5.7. RREQ Table: Received RREQ Messages 709 Two incoming RREQ messages are considered to be "comparable" if they 710 were generated by the same AODVv2 router in order to discover a route 711 for the same destination with the same metric type. According to 712 that notion of comparability, when RREQ messages are flooded in a 713 MANET, an AODVv2 router may well receive comparable RREQ messages 714 from more than one of its neighbors. A router, after receiving an 715 RREQ message, MUST check against previous RREQs to assure that its 716 response message would contain information that is not redundant (see 717 Section 7.6 regarding suppression of redundant RREQ messages). 718 Otherwise, multicast RREQs are likely to be regenerated again and 719 again with almost no additional benefit, but generating a great deal 720 of unnecessary signaling traffic and interference. 722 To avoid transmission of redundant RREQ messages, while still 723 enabling the proper handling of earlier RREQ messages that may have 724 somehow been delayed in the network, it is needed for each AODVv2 725 router to keep a list of the certain information about RREQ messages 726 which it has recently received. 728 This list is called the AODVv2 Received RREQ Table -- or, more 729 briefly, the RREQ Table. Two AODVv2 RREQ messages are comparable if: 731 o they have the same metric type 732 o they have the same OrigNode and TargNode addresses 734 Each entry in the RREQ Table has the following fields: 736 o OrigNode address 737 o TargNode address 738 o OrigNode Sequence Number 739 o TargNode Sequence Number (if present in RREQ) 740 o Metric Type 741 o Metric 742 o Timestamp 744 The RREQ Table is maintained so that no two entries in the RREQ 745 Table are comparable -- that is, all RREQs represented in the RREQ 746 Table either have different OrigNode addresses, different TargNode 747 addresses, or different metric types. If two RREQs have the same 748 metric type and OrigNode and Targnode addresses, the information from 749 the one with the older Sequence Number is not needed in the table; in 750 case they have the same Sequence Number, the one with the greater 751 Metric value is not needed; in case they have the same Metric as 752 well, it does not matter which table entry is maintained. Whenever a 753 RREQ Table entry is updated, its Timestamp field should also be 754 updated to reflect the Current_Time. 756 When optional multicast RREP (see Section 13.4) is used to enable 757 selection from among multiple possible return routes, an AODVv2 758 router can eliminate redundant RREP messages using the analogous 759 mechanism along with a RREP Table. The description in this section 760 only refers to RREQ multicast messages. 762 Protocol handling of RERR messages eliminates the need for tracking 763 RERR messages, since the rules for RERR regeneration prevent the 764 phenomenon of redundant retansmission that affects RREQ and RREP 765 multicast. 767 6. AODVv2 Operations on Route Table Entries 769 In this section, operations are specified for updating the route 770 table due to timeouts and route updates within AODVv2 messages. 771 Route update information in AODVv2 messages includes IP addresses, 772 along with the SeqNum and prefix length associated with each IP 773 address, and including the Metric measured from the node transmitting 774 the AODVv2 message to the IP address in the route update. IP 775 addresses and prefix length are encoded within an RFC 5444 AddrBlk, 776 and the SeqNum and Metric associated with each address in the AddrBlk 777 are encoded in RFC 5444 AddrTLVs. A RREQ message advertises a route 778 to OrigNode, and a RREP message analogously advertises a route to 779 TargNode. In this section, RteMsg is either RREQ or RREP, and AdvRte 780 is the route advertised by the RteMsg. All SeqNum comparisons use 781 signed 16-bit arithmetic. 783 6.1. Evaluating Incoming Routing Information 785 If the incoming RteMsg does not have a Metric Type Message TLV, then 786 the metric information contained by AdvRte is considered to be of 787 type DEFAULT_METRIC_TYPE -- in other words, 3 (for HopCount) unless 788 changed by administrative action. The AODVv2 router (HandlingRtr) 789 checks the advertised route (AdvRte) to see whether the AdvRte should 790 be used to update an existing route table entry. HandlingRtr 791 searches its route table to see if there is a route table entry with 792 the same Metric Type as the AdvRte, matching AdvRte.Address. If not, 793 HandlingRtr creates a route table entry for AdvRte.Address as 794 described in Section 6.2. Otherwise, HandlingRtr compares the 795 incoming routing information for AdvRte against the already stored 796 routing information in the route table entry (Route) for 797 AdvRte.Address, as described next. 799 Route[AdvRte.Address] uses the same metric type as the incoming 800 routing information, and the route entry contains Route.SeqNum, 801 Route.Metric, and Route.State. Define AdvRte.SeqNum and 802 AdvRte.Metric to be the corresponding routing information for 803 Route.Address in the incoming RteMsg. Define AdvRte.Cost to be 804 (AdvRte.Metric + Cost(L)), where L is the link from which the 805 incoming message was received. The incoming routing information is 806 classified as follows: 808 1. Stale:: AdvRte.SeqNum < Route.SeqNum : 809 If AdvRte.SeqNum < Route.SeqNum the incoming information is stale. 810 Using stale routing information is not allowed, since that might 811 result in routing loops. In this case, HandlingRtr MUST NOT 812 update the route table entry using the routing information for 813 AdvRte.Address. 814 2. Unsafe against loops:: (TRUE != LoopFree (AdvRte, Route)) : 815 If AdvRte is not Stale (as in (1) above), AdvRte.Cost is next 816 considered to insure loop freedom. If (TRUE != LoopFree (AdvRte, 817 Route)) (see Section 5.6), then the incoming AdvRte information is 818 not guaranteed to prevent routing loops, and it MUST NOT be used 819 to update any route table entry. 820 3. More costly:: 822 (AdvRte.Cost >= Route.Metric) && (Route.State != Broken) 823 When AdvRte.SeqNum is the same as in a valid route table entry, 824 and LoopFree (AdvRte, Route) assures loop freedom, incoming 825 information still does not offer any improvement over the existing 826 route table information if AdvRte.Cost >= Route.Metric. Using 827 such incoming routing information to update a route table entry is 828 not recommended. 829 4. Offers improvement:: 830 Advertised routing information that does not match any of the 831 above criteria is better than existing route table information and 832 SHOULD be used to improve the route table. The following pseudo- 833 code illustrates whether advertised routing information should be 834 used to update an existing route table entry as described in 835 Section 6.2. 837 (AdvRte.SeqNum > Route.SeqNum) OR 838 ((AdvRte.SeqNum == Route.SeqNum) AND 839 [(AdvRte.Cost < Route.Metric) OR 840 ((Route.State == Broken) && LoopFree (AdvRte, Route))]) 842 The above logic corresponds to placing the following conditions 843 (compared to the existing route table entry) on the advertised 844 route update before it can be used: 846 * it is more recent, or 847 * it is not stale and is less costly, or 848 * it can safely repair a broken route. 850 6.2. Applying Route Updates To Route Table Entries 852 To apply the route update, a route table entry for AdvRte.Address is 853 either found to already exist in the route table, or else a new route 854 table entry for AdvRte.Address is created and inserted into the route 855 table. If the route table entry already exists, and the state is 856 Expired or Broken, then the state is reset to be Idle. If the route 857 table entry had to be created, the state is set to be Active. The 858 route table entry is populated with the following information: 860 o If AdvRte.PrefixLength exists, then Route.PrefixLength := 861 AdvRte.PrefixLength. Otherwise, Route.PrefixLength := maximum 862 length for address family (either 32 or 128). 863 o Route.SeqNum := AdvRte.SeqNum 864 o Route.NextHopAddress := IP.SourceAddress (i.e., an address of the 865 node from which the RteMsg was received) 866 o Route.NextHopInterface is set to the interface on which RteMsg was 867 received 868 o Route.MetricType := AdvRte.MetricType. 869 o Route.Metric := AdvRte.Cost 870 o Route.LastUsed := Current_Time 871 o If RteMsg.VALIDITY_TIME is included, then 872 Route.ExpirationTime := Current_Time + RteMsg.VALIDITY_TIME, 873 otherwise, Route.ExpirationTime := Current_Time + (ACTIVE_INTERVAL 874 + MAX_IDLETIME). 876 With these assignments to the route table entry, a route has been 877 made available, and the route can be used to send any buffered data 878 packets and subsequently to forward any incoming data packets for 879 Route.Address. An updated route entry also fulfills any outstanding 880 route discovery (RREQ) attempts for Route.Address. 882 6.3. Route Table Entry Timeouts 884 During normal operation, AODVv2 does not require any explicit 885 timeouts to manage the lifetime of a route. However, the route table 886 entry MUST be examined before using it to forward a packet, as 887 discussed in Section 8.1. Any required expiry or deletion can occur 888 at that time. Nevertheless, it is permissible to implement timers 889 and timeouts to achieve the same effect. 891 At any time, the route table can be examined and route table entries 892 can be expunged according to their current state at the time of 893 examination, as follows. 895 o An Active route MUST NOT be expunged. 896 o An Idle route SHOULD NOT be expunged. 897 o An Expired route MAY be expunged (least recently used first). 898 o A route MUST be expunged if (Current_Time - Route.LastUsed) >= 899 MAX_SEQNUM_LIFETIME. 900 o A route MUST be expunged if Current_Time >= Route.ExpirationTime 902 If precursor lists are maintained for the route (as described in 903 Section 13.3) then the precursor lists must also be expunged at the 904 same time that the route itself is expunged. 906 7. Routing Messages RREQ and RREP (RteMsgs) 908 AODVv2 message types RREQ and RREP are together known as Routing 909 Messages (RteMsgs) and are used to discover a route between an 910 Originating and Target Node, denoted here by OrigNode and TargNode. 911 The constructed route is bidirectional, enabling packets to flow 912 between OrigNode and TargNode. RREQ and RREP have similar 913 information and function, but have some differences in their rules 914 for handling. When a node receives a RREQ or a RREP, the node then 915 creates or updates a route to the OrigNode or the TargNode 916 respectively. The main difference between the two messages is that 917 RREQ messages are typically multicast to solicit a RREP, whereas RREP 918 is typically unicast as a response to RREQ. 920 When an AODVv2 router needs to forward a data packet from a node 921 (OrigNode) in its set of router clients, and it does not have a 922 forwarding route toward the packet's IP destination address 923 (TargNode), the AODVv2 router (RREQ_Gen) generates a RREQ (as 924 described in Section 7.3) to discover a route toward TargNode. 925 Subsequently RREQ_Gen awaits reception of an RREP message (see 926 Section 7.4) or other route table update (see Section 6.2) to 927 establish a route toward TargNode. The RREQ message contains routing 928 information to enable RREQ recipients to route packets back to 929 OrigNode, and the RREP message contains routing information enabling 930 RREP recipients to route packets to TargNode. 932 7.1. Route Discovery Retries and Buffering 934 After issuing a RREQ, as described above RREQ_Gen awaits a RREP 935 providing a bidirectional route toward Target Node. If the RREP is 936 not received within RREQ_WAIT_TIME, RREQ_Gen MAY retry the Route 937 Discovery by generating another RREQ. Route Discovery SHOULD be 938 considered to have failed after DISCOVERY_ATTEMPTS_MAX and the 939 corresponding wait time for a RREP response to the final RREQ. After 940 the attempted Route Discovery has failed, RREQ_Gen MUST wait at least 941 RREQ_HOLDDOWN_TIME before attempting another Route Discovery to the 942 same destination. 944 To reduce congestion in a network, repeated attempts at route 945 discovery for a particular Target Node SHOULD utilize a binary 946 exponential backoff. 948 Data packets awaiting a route SHOULD be buffered by RREQ_Gen. This 949 buffer SHOULD have a fixed limited size (BUFFER_SIZE_PACKETS or 950 BUFFER_SIZE_BYTES). Determining which packets to discard first is a 951 matter of policy at each AODVv2 router; in the absence of policy 952 constraints, by default older data packets SHOULD be discarded first. 953 Buffering of data packets can have both positive and negative effects 954 (albeit usually positive). Nodes without sufficient memory available 955 for buffering SHOULD be configured to disable buffering by 956 configuring BUFFER_SIZE_PACKETS == 0 and BUFFER_SIZE_BYTES == 0. 957 Doing so will affect the latency required for launching TCP 958 applications to new destinations. 960 If a route discovery attempt has failed (i.e., DISCOVERY_ATTEMPTS_MAX 961 attempts have been made without receiving a RREP) to find a route 962 toward the Target Node, any data packets buffered for the 963 corresponding Target Node MUST BE dropped and a Destination 964 Unreachable ICMP message (Type 3) SHOULD be delivered to the source 965 of the data packet. The code for the ICMP message is 1 (Host 966 unreachable error). If RREQ_Gen is not the source (OrigNode), then 967 the ICMP is sent over the interface from which OrigNode sent the 968 packet to the AODVv2 router. 970 7.2. RteMsg Structure 972 AODVv2 specifies that all control plane messages between Routers 973 SHOULD use the Generalised Mobile Ad-hoc Network Packet and Message 974 Format [RFC5444], which provides a multiplexed transport for multiple 975 protocols. AODVv2 therefore specifies Route Messages that have 976 components that map to message elements in RFC5444 but, in line with 977 the concept of use, does not specify which order the messages should 978 be arranged in an RFC5444 packet. An implementation of an RFC5444 979 parser may choose to optimise the content of certain message elements 980 to reduce control plane overhead. 982 AODVv2 uses the following RFC5444 message elements: 984 o Address of the originating node, OrigNode, which should be mapped 985 to the element in . 986 o Message Hop Count, , which should be mapped to the 987 element in . 988 o Message Hop Limit, , which should be mapped to the 989 element in . 991 RteMsgs have the following general format: 993 +---------------------------------------------------------------+ 994 | RFC 5444 Message Header | 995 +---------------------------------------------------------------+ 996 | MsgTLVs (optional) | 997 +---------------------------------------------------------------+ 998 | AddrBlk := {OrigNode,TargNode} | 999 +---------------------------------------------------------------+ 1000 | AddrBlk.PrefixLength[OrigNode OR TargNode] (Optional) | 1001 +---------------------------------------------------------------+ 1002 | OrigSeqNum_TLV AND/OR TargSeqNum_TLV | 1003 +---------------------------------------------------------------+ 1004 | Metric TLV {OrigNode, TargNode} | 1005 +---------------------------------------------------------------+ 1007 Figure 1: RREQ and RREP (RteMsg) message structure 1009 Required RFC 5444 Message Header Fields 1011 * 1012 * Metric Type Message TLV, if Metric Type != 3 1013 Optional RFC 5444 Message Header Fields 1015 * 1016 * Metric Type TLV (Metric Type for Metric AddrTLV) 1017 * AckReq TLV (Acknowledgement Requested) 1018 AddrBlk 1019 The Address Block contains the IP addresses for RREQ Originating 1020 and Target Node (OrigNode and TargNode). For both RREP and RREQ, 1021 OrigNode and TargNode are as identified in the context of the RREQ 1022 message originator. 1023 OrigSeqNum AND/OR TargSeqNum AddrTLV 1024 At least one of OrigSeqNum or TargSeqNum Address Block TLV is 1025 REQUIRED and carries the destination sequence numbers associated 1026 with OrigNode or TargNode respectively. 1027 Metric AddrTLV 1028 The Metric AddrTLV is REQUIRED and carries the route metric 1029 information associated with either OrigNode or TargNode. 1031 RteMsgs carry information about OrigNode and TargNode. Since their 1032 addresses may appear in arbitrary order within the RFC 5444 AddrBlk, 1033 the OrigSeqNum and/or TargSeqNum TLVs must be used to distinguish the 1034 nature of the node addresses present in the AddrBlk. In each RteMsg, 1035 either the OrigSeqNum TLV or TargSeqNum TLV MUST appear. Both TLVs 1036 MAY appear in the same RteMsg when SeqNum information is available 1037 for both OrigNode and TargNode, but each one MUST NOT appear more 1038 than once, because there is only one OrigNode and only one TargNode 1039 address in the AddrBlk. The TLV flag thassingleindex MUST be set for 1040 these TLVs. 1042 If the OrigSeqNum TLV appears, then the address range for the 1043 OrigSeqNum TLV MUST be limited to a single position in the AddrBlk. 1044 That position is used as the OrigNdx, identifying the OrigNode 1045 address. The other address in the AddrBlk is, by elimination, the 1046 TargNode address, and TargNdx is set appropriately. 1048 Otherwise, if the TargSeqNum TLV appears, then the address range for 1049 the TargSeqNum TLV MUST be limited to a single position in the 1050 AddrBlk. That position is used as the TargNdx, identifying the 1051 TargNode address. The other address in the AddrBlk is, by 1052 elimination, the OrigNode address, and OrigNdx is set appropriately. 1054 7.3. RREQ Generation 1056 The AODVv2 router generating the RREQ (RREQ_Gen) on behalf of its 1057 client OrigNode follows the steps in this section. OrigNode MUST be 1058 a unicast address. The order of protocol elements is illustrated 1059 schematically in Figure 1. 1061 1. RREQ_Gen MUST increment its SeqNum by one (1) according to the 1062 rules specified in Section 5.5. This assures that each node 1063 receiving the RREQ will update its route table using the 1064 information in the RREQ. 1065 2. SHOULD be set to MAX_HOPCOUNT. 1066 3. , if included, MUST be set to 0. 1068 * This RFC 5444 constraint causes certain RREQ payloads to incur 1069 additional enlargement (otherwise, could often 1070 be used as the metric). 1071 4. RREQ.AddrBlk := {OrigNode.Addr, TargNode.Addr} 1073 Let OrigNdx and TargNdx denote the indexes of OrigNode and 1074 TargNode respectively in the RREQ.AddrBlk list. 1075 5. If Route[OrigNode].PrefixLength/8 is equal to the number of bytes 1076 in the addresses of the RREQ (4 for IPv4, 16 for IPv6), then no 1077 is included with the RREQ.AddrBlk. Otherwise, 1078 RREQ.PrefixLength[OrigNdx] := Route[OrigNode].PrefixLength 1079 according to the rules of RFC 5444 AddrBlk encoding. 1080 6. RREQ.OrigSeqNum_TLV[OrigNdx] := RREQ_Gen's SeqNum 1081 7. RREQ.TargSeqNum_TLV[TargNdx] := TargNode's SeqNum (only if known) 1083 RREQ_Gen SHOULD include TargNode's SeqNum, if a previous value of 1084 the TargNode's SeqNum is known (e.g., from an invalid route table 1085 entry using longest-prefix matching). If TargNode's SeqNum is 1086 not included, AODVv2 routers handling the RREQ assume that 1087 RREQ_Gen does not have that information. 1088 8. RREQ.Metric_TLV[OrigNdx] := Route[OrigNode].Metric 1090 An example RREQ message format is illustrated in Appendix B.1. 1092 7.4. RREP Generation 1094 This section specifies the generation of an RREP by an AODVv2 router 1095 (RREP_Gen) that provides connectivity for the Target Node (TargNode) 1096 of a RREQ, thus enabling the establishment of a route between 1097 OrigNode and TargNode. If TargNode is not a unicast IP address the 1098 RREP MUST NOT be generated, and processing for the RREQ is complete. 1099 Before transmitting a RREP, the routing information of the RREQ is 1100 processed as specified in Section 6.2; after such processing, 1101 RREP_Gen has an updated route to OrigNode as well as TargNode. The 1102 basic format of an RREP conforms to the structure for RteMsgs as 1103 shown in Figure 1. 1105 RREP_Gen generates the RREP as follows: 1107 1. RREP_Gen checks the RREQ against recently received RREQ 1108 information as specified in Section 7.6. If a previously 1109 received RREQ has made the information in the incoming RREQ to 1110 be redundant, no RREP is generated and processing is complete. 1111 2. RREP_Gen MUST increment its SeqNum by one (1) according to the 1112 rules specified in Section 5.5. 1113 3. RREP.AddrBlk := {OrigNode.Addr, TargNode.Addr} 1115 Let OrigNdx and TargNdx denote the indexes of OrigNode and 1116 TargNode respectively in the RREQ.AddrBlk list. 1117 4. RREP.TargSeqNum_TLV[TargNdx] := RREP_Gen's SeqNum 1118 5. If Route[TargNode].PrefixLength/8 is equal to the number of 1119 bytes in the addresses of the RREQ (4 for IPv4, 16 for IPv6), 1120 then no is included with the RREP.AddrBlk. 1121 Otherwise, RREP.PrefixLength[TargNdx] := 1122 Route[TargNode].PrefixLength according to the rules of RFC 5444 1123 AddrBlk encoding. 1124 6. If (DEFAULT != Route[TargNode].MetricType) then include the 1125 Metric Type message TLV and assign RREP.MetricType[TargNdx] := 1126 Route[TargNode].MetricType 1127 7. RREP.Metric_TLV[TargNdx] := Route[TargNode].Metric 1128 8. , if included, MUST be set to 0. 1129 9. SHOULD be set to RREQ.. 1130 10. IP.DestinationAddress := Route[OrigNode].NextHop 1132 An example message format for RREP is illustrated in Appendix B.2. 1134 7.5. Handling a Received RteMsg 1136 Before an AODVv2 router can make use of a received RteMsg (i.e., RREQ 1137 or RREP), the router first must verify that the RteMsg is permissible 1138 according to the following steps. OrigNdx and TargNdx are set 1139 according to the rules in Section 7.2. For RREQ, RteMsg.Metric is 1140 Metric_TLV[OrigNdx]. For RREP, RteMsg.Metric is Metric_TLV[TargNdx]. 1141 In this section (unless qualified by additional description such as 1142 "upstream" or "neighboring") all occurrences of the term "router" 1143 refer to the AODVv2 router handling the received RteMsg. 1145 1. A router MUST handle RteMsgs only from neighbors as specified in 1146 Section 5.4. RteMsgs from other sources MUST be disregarded. 1147 2. The router examines the RteMsg to ascertain that it contains the 1148 required information: , TargNode.Addr, 1149 OrigNode.Addr, RteMsg.Metric, and either RteMsg.OrigSeqNum or 1150 RteMsg.TargSeqNum. If the required information does not exist, 1151 the message is disregarded. 1152 3. The router checks that OrigNode.Addr and TargNode.Addr are valid 1153 routable unicast addresses. If not, the message is disregarded. 1154 4. The router checks the Metric Type MsgTLV (if present) to assure 1155 that the Metric Type associated with the Metric AddrTLV 1156 information in the RREQ or RREP is known. If not, the message is 1157 disregarded. 1159 * DISCUSSION: or, can change the AddrBlk metric to use HopCount, 1160 e.g., measured from . 1161 5. If (MAX_METRIC[RteMsg.MetricType] - Cost(L)) <= RteMsg.Metric, 1162 the RteMsg is disregarded, where Cost(L) denotes the cost of 1163 traversing the incoming link (i.e., as measured by the network 1164 interface receiving the incoming RteMsg). 1166 An AODVv2 router handles a permissible RteMsg according to the 1167 following steps. 1169 1. The router MUST process the routing information for OrigNode and 1170 TargNode contained in the RteMsg as specified in Section 6.1. 1171 2. If RteMsg. is zero (0), no further action is 1172 taken, and the RteMsg is not regenerated. Otherwise, the router 1173 MUST decrement RteMsg.. 1174 3. If the RteMsg. is present, and MAX_HOPCOUNT <= 1175 , then no further action is taken. Otherwise, the 1176 router MUST increment RteMsg. 1178 Further actions to transmit an updated RteMsg depend upon whether the 1179 incoming RteMsg is an RREP or an RREQ. 1181 7.5.1. Additional Handling for Incoming RREQ 1183 o By sending a RREQ, a router advertises that it will route for 1184 addresses contained in the RteMsg based on the information 1185 enclosed. The router MAY choose not to send the RREQ, though not 1186 resending the RREQ could decrease connectivity in the network or 1187 result in nonoptimal paths. The circumstances under which a 1188 router might choose not to re-transmit a RREQ are not specified in 1189 this document. Some examples might include the following: 1191 * The router is already heavily loaded and does not want to 1192 advertise routing for more traffic 1193 * The router recently transmitted identical routing information 1194 (e.g. in a RREQ advertising the same metric) Section 7.6 1195 * The router is low on energy and has to reduce energy expended 1196 for sending protocol messages or packet forwarding 1198 Unless the router is prepared to send a RREQ, it halts processing. 1199 o If the upstream router sending a RREQ is in the Blacklist, and 1200 Current_Time < Blacklist.RemoveTime, then the router receiving 1201 that RREQ MUST NOT transmit any outgoing RteMsg, and processing is 1202 complete. 1204 o Otherwise, if the upstream router is in the Blacklist, and 1205 Current_Time >= Blacklist.RemoveTime, then the upstream router 1206 SHOULD be removed from the Blacklist, and message processing 1207 continued. 1208 o The incoming RREQ MUST be checked against previously received 1209 information from the RREQ Table (Section 7.6). If the information 1210 in the incoming RteMsg is redundant, then then no further action 1211 is taken. 1212 o If TargNode is a client of the router receiving the RREQ, then the 1213 router generates a RREP message as specified in Section 7.4, and 1214 subsequently processing for the RREQ is complete. Otherwise, 1215 processing continues as follows. 1216 o If (DEFAULT != Route[OrigNode].MetricType) then include the Metric 1217 Type message TLV and assign RREQ.MetricType := 1218 Route[OrigNode].MetricType 1219 o RREQ.Metric_TLV[OrigNdx] := Route[OrigNode].Metric 1220 o The RREQ (with updated fields as specified above>) SHOULD be sent 1221 to the IP multicast address LL-MANET-Routers [RFC5498]. If the 1222 RREQ is unicast, the IP.DestinationAddress is set to 1223 Route[RREQ.TargNode].NextHopAddress. 1225 7.5.2. Additional Handling for Incoming RREP 1227 As always, OrigNode and TargNode are named in the context of RREQ_Gen 1228 (i.e., the router originating the RREQ for which the RREP was 1229 generated) (see Table 1). OrigNdx and TargNdx are set according to 1230 the rules in Section 7.2. 1232 o If no forwarding route exists to OrigNode, then a RERR SHOULD be 1233 transmitted to RREP.AddrBlk[TargNdx]. Otherwise, if HandlingRtr 1234 is not RREQ_Gen then the outgoing RREP is sent to the 1235 Route.NextHopAddress for the RREP.AddrBlk[OrigNdx]. 1236 o If HandlingRtr is RREQ_Gen then the RREP satisfies RREQ_Gen's 1237 earlier RREQ, and RREP processing is completed. Any packets 1238 buffered for OrigNode should be transmitted. 1240 7.6. Suppressing Redundant RREQ messages 1242 Since RREQ messages are multicast, there are common circumstances in 1243 which an AODVv2 router might transmit a redundant response (RREQ or 1244 RREP), duplicating the information transmitted in response to some 1245 other recent RREQ (see Section 5.7). Before responding, an AODVv2 1246 router MUST suppress such RREQ messages. This is done by checking 1247 the list of recently received RREQs to determine whether the incoming 1248 RREQ is redundant, as follows: 1250 o The AODVv2 router searches the RREQ Table for recent entries with 1251 the same OrigNode, TargNode, and Metric Type. If there is no such 1252 entry, the incoming RREQ message is not suppressed. A new entry 1253 for the incoming RREQ is created in the RREQ Table. 1254 o If there is such an entry, and the incoming RREQ has a newer 1255 sequence number, the incoming RREQ is not suppressed, and the 1256 existing table entry MUST be updated to reflect the new Sequence 1257 Number and Metric. 1258 o Similarly, if the Sequence Numbers are the same, and the incoming 1259 RREQ offers a better Metric, the incoming RREQ is not suppressed, 1260 and the RREQ Table entry MUST be updated to reflect the new 1261 Metric. 1262 o Otherwise, the incoming RREQ is suppressed. 1264 8. Route Maintenance and RERR Messages 1266 AODVv2 routers attempt to maintain active routes. When a routing 1267 problem is encountered, an AODVv2 router (denoted RERR_Gen) attempts 1268 to quickly notify upstream routers. Two kinds of routing problems 1269 may trigger generation of a RERR message. The first case happens 1270 when the router receives a packet but does not have a route for the 1271 destination of the packet. The second case happens immediately upon 1272 detection of a broken link (see Section 8.2) of an Active route, to 1273 quickly notify upstream AODVv2 routers that that route is no longer 1274 available. 1276 8.1. Maintaining Route Lifetimes During Packet Forwarding 1278 Before using a route to forward a packet, an AODVv2 router MUST check 1279 the status of the route as follows. 1281 o If the route is marked has been marked as Broken, it cannot be 1282 used for forwarding. 1283 o If Current_Time > Route.ExpirationTime, the route table entry has 1284 expired, and cannot be used for forwarding. 1285 o Similarly, if (Route.ExpirationTime == MAXTIME), and if 1286 (Current_Time - Route.LastUsed) > (ACTIVE_INTERVAL + 1287 MAX_IDLETIME), the route has expired, and cannot be used for 1288 forwarding. 1289 o Furthermore, if Current_Time - Route.LastUsed > 1290 (MAX_SEQNUM_LIFETIME), the route table entry MUST be expunged. 1292 If any of the above route error conditions hold true, the route 1293 cannot be used to forward the packet, and an RERR message MUST be 1294 generated (see Section 8.3). 1296 Otherwise, Route.LastUsed := Current_Time, and the packet is 1297 forwarded to the route's next hop. 1299 Optionally, if a precursor list is maintained for the route, see 1300 Section 13.3 for precursor lifetime operations. 1302 8.2. Active Next-hop Router Adjacency Monitoring 1304 Neighboring routers MAY form an adjacency based on various 1305 information or other protocols; for example, exchange of AODVv2 1306 routing messages, other protocols (e.g. NDP [RFC4861] or NHDP 1307 [RFC6130]), or manual configuration. Loss of a routing adjacency may 1308 also be indicated by similar information. AODVv2 routers SHOULD 1309 monitor connectivity to adjacent routers along active routes. This 1310 monitoring can be accomplished by one or several mechanisms, 1311 including: 1313 o Neighborhood discovery [RFC6130] 1314 o Route timeout 1315 o Lower layer trigger that a link is broken 1316 o TCP timeouts 1317 o Promiscuous listening 1318 o Other monitoring mechanisms or heuristics 1320 If a next-hop AODVv2 router has become unreachable, RERR_Gen follows 1321 the procedures specified in Section 8.3.2. 1323 8.3. RERR Generation 1325 An RERR message is generated by a AODVv2 router (i.e., RERR_Gen) in 1326 order to notify upstream routers that packets cannot be delivered to 1327 certain destinations. An RERR message has the following general 1328 structure: 1330 +---------------------------------------------------------------+ 1331 | RFC 5444 Message Header | 1332 +---------------------------------------------------------------+ 1333 | UnreachableNode AddrBlk (Unreachable Node addresses) | 1334 +---------------------------------------------------------------+ 1335 | AddrBlk.PrefixLength[UnreachableNodes] (Optional) | 1336 +---------------------------------------------------------------+ 1337 | UnreachableNode SeqNum AddrBlk TLV | 1338 +---------------------------------------------------------------+ 1339 | UnreachableNode PfxLen AddrBlk TLV | 1340 +---------------------------------------------------------------+ 1342 Figure 2: RERR message structure 1344 Required Message Header Fields 1345 The RERR MUST contain the following: 1347 * 1348 * PktSource Message TLV (see Section 15), if the RERR is unicast 1349 * Metric Type Message TLV (see Section 15), if Metric Type != 3 1350 Optional Message Header Fields 1351 The RERR SHOULD contain the following: 1353 * 1354 UnreachableNode AddrBlk 1355 This Address Block contains the IP addresses unreachable by AODVv2 1356 router transmitting the RERR. 1357 UnreachableNode.PrefixLength 1358 If needed, the Address Block can also carry the prefix length 1359 associated with each UnreachableNode. 1360 Sequence Number AddrBlk TLV 1361 This Address Block TLV carries the destination sequence number 1362 associated with each UnreachableNode when that information is 1363 available. 1365 There are two kinds of events indicating that packets cannot be 1366 delivered to certain destinations. The two cases differ in the way 1367 that the neighboring IP destination address for the RERR is chosen, 1368 and in the way that the set of UnreachableNodes is identified. 1370 In both cases, the MUST be included and SHOULD be set 1371 to MAX_HOPCOUNT. SHOULD be included and set to 0, to 1372 facilitate use of various route repair strategies including expanding 1373 rings multicast and Intermediate RREP [I-D.perkins-irrep]. 1375 8.3.1. Case 1: Undeliverable Packet 1377 The first case happens when the router receives a packet from another 1378 AODVv2 router but does not have a valid route for the destination of 1379 the packet. In this case, there is exactly one UnreachableNode to be 1380 included in the RERR's AddrBlk (either IP.DestinationAddress from a 1381 data packet or the OrigNode address found in the AddrBlk of an RREP 1382 message). The RERR SHOULD be sent to the multicast address LL-MANET- 1383 Routers, but RERR_Gen MAY instead send the RERR to the next hop 1384 towards the source IP address of the packet which was undeliverable. 1385 For unicast RERR, the PktSource Message TLV MUST be included, 1386 containing the the source IP address of the undeliverable packet, or 1387 the IP address of TargRtr in case the undeliverable packet was an 1388 RREP message generated by TargRtr. If a Sequence Number for 1389 UnreachableNode is known, that Sequence Number SHOULD be included in 1390 a Seqnum AddrTLV the RERR. Otherwise all nodes handling the RERR 1391 will assume their route through RERR_Gen towards the UnreachableNode 1392 is no longer valid and mark those routes as broken, regardless of the 1393 Sequence Number information for those routes. RERR_Gen MUST discard 1394 the packet or message that triggered generation of the RERR. 1396 If an AODVv2 router receives an ICMP packet from the address of one 1397 of its client nodes, it simply relays the packet to the ICMP packet's 1398 destination address, and does not generate any RERR message. 1400 8.3.2. Case 2: Broken Link 1402 The second case happens when the link breaks to an active adjacent 1403 AODVv2 router (i.e., the next hop of an active route). In this case, 1404 the RERR MUST be sent to the multicast address LL-MANET-Routers, 1405 except when the optional feature of maintaining precursor lists is 1406 used as specified in Section 13.3. All routes (Active, Idle and 1407 Expired) that use the broken link MUST be marked as Broken. The set 1408 of UnreachableNodes is initialized by identifying those Active routes 1409 which use the broken link. For each such Active Route, Route.Dest is 1410 added to the set of Unreachable Nodes. After the Active Routes using 1411 the broken link have all been included as UnreachableNodes, Idle 1412 routes MAY also be included, if allowed by the setting of 1413 ENABLE_IDLE_IN_RERR, as long as the packet size of the RERR does not 1414 exceed the MTU (interface "Maximum Transfer Unit") of the physical 1415 medium. 1417 If the set of UnreachableNodes is empty, no RERR is generated. 1418 Otherwise, RERR_Gen generates a new RERR, and the address of each 1419 UnreachableNode is inserted into an AddrBlock. If any 1420 UnreachableNode.Addr entry is associated with a routing prefix (i.e., 1421 a prefix length shorter than the maximum length for the address 1422 family), then the AddrBlk MUST include prefix lengths; otherwise, if 1423 no such entry, the prefix lengths NOT be included. The value for 1424 each UnreachableNode's SeqNum (UnreachableNode.SeqNum) MUST be placed 1425 in the SeqNum AddrTLV. 1427 Every broken route reported in the RERR MUST have the same Metric 1428 Type. If the Metric Type is not 3, then the RERR message MUST 1429 contain a Metric Type MsgTLV indicating the Metric Type of the broken 1430 route(s). 1432 8.4. Receiving and Handling RERR Messages 1434 When an AODVv2 router (HandlingRtr) receives a RERR message, it uses 1435 the information provided to invalidate affected routes. If 1436 HandlingRtr has neighbors that are using the affected routes, then 1437 HandlingRtr subsequently sends an RERR message to those neighbors. 1438 This has the effect of regenerating the RERR information and is 1439 counted as another "hop" for purposes of properly modifying and in the RERR message header. 1442 HandlingRtr examines the incoming RERR to assure that it contains 1443 and at least one UnreachableNode.Address. If the 1444 required information does not exist, the incoming RERR message is 1445 disregarded and further processing stopped. Otherwise, for each 1446 UnreachableNode.Address, HandlingRtr searches its route table for a 1447 route using longest prefix matching. If no such Route is found, 1448 processing is complete for that UnreachableNode.Address. Otherwise, 1449 HandlingRtr verifies the following: 1451 1. The UnreachableNode.Address is a routable unicast address. 1452 2. Route.NextHopAddress is the same as RERR IP.SourceAddress. 1453 3. Route.NextHopInterface is the same as the interface on which the 1454 RERR was received. 1455 4. The UnreachableNode.SeqNum is unknown, OR Route.SeqNum <= 1456 UnreachableNode.SeqNum (using signed 16-bit arithmetic). 1458 If the Route satisfies all of the above conditions, HandlingRtr 1459 checks whether Route.PrefixLength is the same as the prefix length 1460 for UnreachableNode.Address. If so, HandlingRtr simply sets the 1461 state for that Route to be Broken. Otherwise, HandlingRtr creates a 1462 new route (call it BrokenRoute) with the same PrefixLength as the 1463 prefix length for UnreachableNode.Address, and sets Route.State == 1464 Broken for BrokenRoute. If the prefix length for the new route is 1465 shorter than Route.PrefixLength, then Route MUST be expunged from the 1466 route table (since it is a subroute of the larger route which is 1467 reported to be broken). Furthermore, if is greater 1468 than 0, then HandlingRtr adds the UnreachableNode address and TLV 1469 information to an AddrBlk for delivery in the outgoing RERR message. 1471 If there are no UnreachableNode addresses to be transmitted in an 1472 RERR to upstream routers, HandlingRtr MUST discard the RERR, and no 1473 further action is taken. 1475 Otherwise, is decremented by one (1) and processing 1476 continues as follows: 1478 o (Optional) If precursor lists are maintained, the outgoing RERR 1479 SHOULD be sent to the active precursors of the broken route as 1480 specified in Section 13.3. 1481 o Otherwise, if the incoming RERR message was received at the LL- 1482 MANET-Routers [RFC5498] multicast address, the outgoing RERR 1483 SHOULD also be sent to LL-MANET-Routers. 1484 o Otherwise, if the PktSource Message TLV is present, and 1485 HandlingRtr has a Route to PktSource.Addr, then HandlingRtr MUST 1486 send the outgoing RERR to Route[PktSource.Addr].NextHop. 1487 o Otherwise, the outgoing RERR MUST be sent to LL-MANET-Routers. 1489 9. Unknown Message and TLV Types 1491 For handling of messages that contain unknown TLV types, ignore the 1492 information for processing, but preserve it unmodified for 1493 forwarding. 1495 10. Simple Internet Attachment 1497 Simple Internet attachment means attachment of a stub (i.e., non- 1498 transit) network of AODVv2 routers to the Internet via a single 1499 Internet AODVv2 router (called IAR). 1501 As in any Internet-attached network, AODVv2 routers, and their 1502 clients, wishing to be reachable from hosts on the Internet MUST have 1503 IP addresses within the IAR's routable and topologically correct 1504 prefix (e.g. 191.0.2.0/24). 1506 /-------------------------\ 1507 / +----------------+ \ 1508 / | AODVv2 Router | \ 1509 | | 191.0.2.2/32 | | 1510 | +----------------+ | Routable 1511 | +-----+--------+ Prefix 1512 | | Internet | /191.0.2/24 1513 | | AODVv2 Router| / 1514 | | 191.0.2.1 |/ /---------------\ 1515 | | serving net +------+ Internet \ 1516 | | 191.0.2/24 | \ / 1517 | +-----+--------+ \---------------/ 1518 | +----------------+ | 1519 | | AODVv2 Router | | 1520 | | 191.0.2.3/32 | | 1521 \ +----------------+ / 1522 \ / 1523 \-------------------------/ 1525 Figure 3: Simple Internet Attachment Example 1527 When an AODVv2 router within the AODVv2 MANET wants to discover a 1528 route toward a node on the Internet, it uses the normal AODVv2 route 1529 discovery for that IP Destination Address. The IAR MUST respond to 1530 RREQ on behalf of all Internet destinations. 1532 When a packet from a node on the Internet destined for a node in the 1533 AODVv2 MANET reaches the IAR, if the IAR does not have a route toward 1534 that destination it will perform normal AODVv2 route discovery for 1535 that destination. 1537 11. Multiple Interfaces 1539 AODVv2 MAY be used with multiple interfaces; therefore, the 1540 particular interface over which packets arrive MUST be known whenever 1541 a packet is received. Whenever a new route is created, the interface 1542 through which the route's destination can be reached is also recorded 1543 in the route table entry. 1545 When multiple interfaces are available, a node transmitting a 1546 multicast packet to LL-MANET-Routers MUST send the packet on all 1547 interfaces that have been configured for AODVv2 operation. 1549 Similarly, AODVv2 routers MUST subscribe to LL-MANET-Routers on all 1550 their AODVv2 interfaces. 1552 12. AODVv2 Control Message Generation Limits 1554 To avoid congestion, each AODVv2 router's rate of packet/message 1555 generation SHOULD be limited. The rate and algorithm for limiting 1556 messages (CONTROL_TRAFFIC_LIMITS) is left to the implementor and 1557 should be administratively configurable. AODVv2 messages SHOULD be 1558 discarded in the following order of preference: RREQ, RREP, and 1559 finally RERR. 1561 13. Optional Features 1563 Some optional features of AODVv2, associated with AODV, are not 1564 required by minimal implementations. These features are expected to 1565 apply in networks with greater mobility, or larger node populations, 1566 or requiring reduced latency for application launches. The optional 1567 features are as follows: 1569 o Expanding Rings Multicast 1570 o Intermediate RREPs (iRREPs): Without iRREP, only the destination 1571 can respond to a RREQ. 1572 o Precursor lists. 1573 o Reporting Multiple Unreachable Nodes. An RERR message can carry 1574 more than one Unreachable Destination node for cases when a single 1575 link breakage causes multiple destinations to become unreachable 1576 from an intermediate router. 1577 o RREP_ACK. 1578 o Message Aggregation. 1580 13.1. Expanding Rings Multicast 1582 For multicast RREQ, MAY be set in accordance with an 1583 expanding ring search as described in [RFC3561] to limit the RREQ 1584 propagation to a subset of the local network and possibly reduce 1585 route discovery overhead. 1587 13.2. Intermediate RREP 1589 This specification has been published as a separate Internet Draft 1590 [I-D.perkins-irrep]. 1592 13.3. Precursor Lists and Notifications 1594 This section specifies an interoperable enhancement to AODVv2 (and 1595 possibly other reactive routing protocols) enabling more economical 1596 notifications to traffic sources upon determination that a route 1597 needed to forward such traffic to its destination has become Broken. 1599 13.3.1. Overview 1601 In many circumstances, there can be several sources of traffic for a 1602 certain destination. Each such source of traffic is known as a 1603 "precursor" for the destination, as well as all upstream routers 1604 between the forwarding AODVv2 router and the traffic source. For 1605 each active destination, an AODVv2 router MAY choose to keep track of 1606 the upstream neighbors that have provided traffic for that 1607 destination; there is no need to keep track of upstream routers any 1608 farther away than the next hop. 1610 Moreover, any particular link to an adjacent AODVv2 router may be a 1611 path component of multiple routes towards various destinations. The 1612 precursors for all destinations using the next hop across any link 1613 are collectively known as the precursors for that next hop. 1615 When an AODVv2 router determines that an active link to one of its 1616 neighbors has broken, the AODVv2 router detecting the broken link 1617 must mark multiple routes as Broken, for each of the newly 1618 unreachable destinations, as described in Section 8.3. Each route 1619 that relies on the newly broken link is no longer valid. 1620 Furthermore, the precursors of the broken link should be notified 1621 (using RERR) about the change in status of their route to a 1622 destination relying upon the broken next hop. 1624 13.3.2. Precursor Notification Details 1626 During normal operation, each AODVv2 router wishing to maintain 1627 precursor lists as described above, maintains a precursor table and 1628 updates the table whenever the node forwards traffic to one of the 1629 destinations in its route table. For each precursor in the precursor 1630 list, a record must be maintained to indicate whether the precursor 1631 has been used for recent traffic (in other words, whether the 1632 precursor is an Active precursor). So, when traffic arrives from a 1633 precursor, the Current_Time is used to mark the time of last use for 1634 the precursor list element associated with that precursor. 1636 When an AODVv2 router detects that a link is broken, then for each 1637 precursor using that next hop, the node MAY notify the precursor 1638 using either unicast or multicast RERR: 1640 unicast RERR to each Active precursor 1641 This option is applicable when there are few Active precursors 1642 compared to the number of neighboring AODVv2 routers. 1643 multicast RERR to RERR_PRECURSORS 1644 RERR_PRECURSORS is, by default, LL-MANET-Routers [RFC5498]. This 1645 option is typically preferable when there are many precursors, 1646 since fewer packet transmissions are required. 1648 Each active upstream neighbor (i.e., precursor) MAY then execute the 1649 same procedure until all active upstream routers have received the 1650 RERR notification. 1652 13.4. Multicast RREP Response to RREQ 1654 The RREQ Target Router (RREP_Gen) MAY, as an alternative to 1655 unicasting a RREP, be configured to distribute routing information 1656 about the route toward the RREQ TargNode (RREP_Gen's client) more 1657 widely. That is, RREP_Gen MAY be configured respond to a route 1658 discovery by generating a RREP, using the procedure in Section 7.4, 1659 but multicasting the RREP to LL-MANET-Routers [RFC5498] (subject to 1660 similar suppression algorithm for redundant RREP multicasts as 1661 described in Section 7.6). The redundant message suppression must 1662 occur at every router handling the multicast RREP. Afterwards, 1663 RREP_Gen processing for the incoming RREQ is complete. 1665 Broadcast RREP response to incoming RREQ was originally specified to 1666 handle unidirectional links, but it is expensive. Due to the 1667 significant overhead, AODVv2 routers MUST NOT use multicast RREP 1668 unless configured to do so by setting the administrative parameter 1669 USE_MULTICAST_RREP. 1671 13.5. RREP_ACK 1673 Instead of relying on existing mechanisms for requesting verification 1674 of link bidirectionality during Route Discovery, RREP_Ack is provided 1675 as an optional feature and modeled on the RREP_Ack message type from 1676 AODV [RFC3561]. 1678 Since the RREP_ACK is simply echoed back to the node from which the 1679 RREP was received, there is no need for any additional RFC 5444 1680 address information (or TLVs). Considerations of packet TTL are as 1681 specified in Section 5.4. An example message format is illustrated 1682 in section Appendix B.4. 1684 13.6. Message Aggregation 1686 The aggregation of multiple messages into a packet is specified in 1687 RFC 5444 [RFC5444]. 1689 Implementations MAY choose to briefly delay transmission of messages 1690 for the purpose of aggregation (into a single packet) or to improve 1691 performance by using jitter [RFC5148]. 1693 14. Administratively Configurable Parameters and Timer Values 1695 AODVv2 uses various configurable parameters of various types: 1697 o Timers 1698 o Protocol constants 1699 o Administrative (functional) controls 1700 o Other administrative parameters and lists 1702 The tables in the following sections show the parameters along their 1703 definitions and default values (if any). 1705 Note: several fields have limited size (bits or bytes). These sizes 1706 and their encoding may place specific limitations on the values that 1707 can be set. For example, is a 8-bit field and 1708 therefore MAX_HOPCOUNT cannot be larger than 255. 1710 14.1. Timers 1712 AODVv2 requires certain timing information to be associated with 1713 route table entries. The default values are as follows, subject to 1714 future experience: 1716 +------------------------------+---------------+ 1717 | Name | Default Value | 1718 +------------------------------+---------------+ 1719 | ACTIVE_INTERVAL | 5 second | 1720 | MAX_IDLETIME | 200 seconds | 1721 | MAX_BLACKLIST_TIME | 200 seconds | 1722 | MAX_SEQNUM_LIFETIME | 300 seconds | 1723 | RREQ_WAIT_TIME | 2 seconds | 1724 | UNICAST_MESSAGE_SENT_TIMEOUT | 1 second | 1725 | RREQ_HOLDDOWN_TIME | 10 seconds | 1726 +------------------------------+---------------+ 1728 Table 2: Timing Parameter Values 1730 The above timing parameter values have worked well for small and 1731 medium well-connected networks with moderate topology changes. 1733 The timing parameters SHOULD be administratively configurable for the 1734 network where AODVv2 is used. Ideally, for networks with frequent 1735 topology changes the AODVv2 parameters should be adjusted using 1736 either experimentally determined values or dynamic adaptation. For 1737 example, in networks with infrequent topology changes MAX_IDLETIME 1738 may be set to a much larger value. 1740 14.2. Protocol constants 1742 AODVv2 protocol constants typically do not require changes. The 1743 following table lists these constants, along with their values and a 1744 reference to the specification describing their use. 1746 +------------------------+--------------------+---------------------+ 1747 | Name | Default Value | Description | 1748 +------------------------+--------------------+---------------------+ 1749 | DISCOVERY_ATTEMPTS_MAX | 3 | Section 7.1 | 1750 | MAX_HOPCOUNT | 20 hops | Section 5.6 | 1751 | MAX_METRIC[i] | Specified only for | Section 5.6 | 1752 | | HopCount | | 1753 | MAXTIME | [TBD] | Maximum expressible | 1754 | | | clock time | 1755 +------------------------+--------------------+---------------------+ 1757 Table 3: Parameter Values 1759 14.3. Administrative (functional) controls 1761 The following administrative controls may be used to change the 1762 operation of the network, by enabling optional behaviors. These 1763 options are not required for correct routing behavior, although they 1764 may potentially reduce AODVv2 protocol messaging in certain 1765 situations. The default behavior is to NOT enable most such options, 1766 options. Packet buffering is enabled by default. 1768 +------------------------+------------------------------------+ 1769 | Name | Description | 1770 +------------------------+------------------------------------+ 1771 | DEFAULT_METRIC_TYPE | 3 (i.e, Hop Count (see [RFC6551])) | 1772 | ENABLE_IDLE_IN_RERR | Section 8.3.2 | 1773 | ENABLE_IRREP | Section 7.3 | 1774 | USE_MULTICAST_RREP | Section 13.4 | 1775 +------------------------+------------------------------------+ 1777 Table 4: Administratively Configured Controls 1779 14.4. Other administrative parameters and lists 1781 The following table lists contains AODVv2 parameters which should be 1782 administratively configured for each specific network. 1784 +-----------------------+-----------------------+-----------------+ 1785 | Name | Default Value | Cross Reference | 1786 +-----------------------+-----------------------+-----------------+ 1787 | AODVv2_INTERFACES | | Section 4 | 1788 | BUFFER_SIZE_PACKETS | 2 | Section 7.1 | 1789 | BUFFER_SIZE_BYTES | MAX_PACKET_SIZE [TBD] | Section 7.1 | 1790 | CLIENT_ADDRESSES | AODVv2_INTERFACES | Section 5.3 | 1791 | CONTROL_TRAFFIC_LIMIT | TBD [50 packets/sec?] | Section 12 | 1792 +-----------------------+-----------------------+-----------------+ 1794 Table 5: Other Administrative Parameters 1796 15. IANA Considerations 1798 This section specifies several message types, message tlv-types, and 1799 address tlv-types. Also, a new registry of 16-bit alternate metric 1800 types is specified. 1802 15.1. AODVv2 Message Types Specification 1803 +----------------------------------------+------------+ 1804 | Name | Type (TBD) | 1805 +----------------------------------------+------------+ 1806 | Route Request (RREQ) | 10 | 1807 | Route Reply (RREP) | 11 | 1808 | Route Error (RERR) | 12 | 1809 | Route Reply Acknowledgement (RREP_ACK) | 13 | 1810 +----------------------------------------+------------+ 1812 Table 6: AODVv2 Message Types 1814 15.2. Message TLV Type Specification 1816 +-----------------------------------+-------+---------+-------------+ 1817 | Name | Type | Length | Cross | 1818 | | (TBD) | in | Reference | 1819 | | | octets | | 1820 +-----------------------------------+-------+---------+-------------+ 1821 | Acknowledgment Request (AckReq) | 10 | 0 | Section 5.2 | 1822 | Packet Source (PktSource) | 11 | 4 or 16 | Section 8.3 | 1823 | Metric Type | 12 | 1 | Section 7.2 | 1824 +-----------------------------------+-------+---------+-------------+ 1826 Table 7: Message TLV Types 1828 15.3. Address Block TLV Specification 1830 +-----------------------------+--------+--------------+-------------+ 1831 | Name | Type | Length | Value | 1832 | | (TBD) | | | 1833 +-----------------------------+--------+--------------+-------------+ 1834 | Metric | 10 | depends on | Section 7.2 | 1835 | | | Metric Type | | 1836 | Sequence Number (SeqNum) | 11 | 2 octets | Section 7.2 | 1837 | Originating Node Sequence | 12 | 2 octets | Section 7.2 | 1838 | Number (OrigSeqNum) | | | | 1839 | Target Node Sequence Number | 13 | 2 octets | Section 7.2 | 1840 | (TargSeqNum) | | | | 1841 | VALIDITY_TIME | 1 | 1 octet | [RFC5497] | 1842 +-----------------------------+--------+--------------+-------------+ 1844 Table 8: Address Block TLV (AddrTLV) Types 1846 15.4. Metric Type Number Allocation 1848 Metric types are identified according to the assignments as specified 1849 in [RFC6551]. The metric type of the Hop Count metric is assigned to 1850 be 3, in order to maintain compatibility with that existing table of 1851 values from RFC 6551. Non-addititve metrics are not supported in 1852 this draft. 1854 +-----------------------+----------+-------------+ 1855 | Name | Type | Metric Size | 1856 +-----------------------+----------+-------------+ 1857 | Unallocated | 0 -- 2 | TBD | 1858 | Hop Count | 3 - TBD | 1 octet | 1859 | Unallocated | 4 -- 254 | TBD | 1860 | Reserved | 255 | Undefined | 1861 +-----------------------+----------+-------------+ 1863 Table 9: Metric Types 1865 16. Security Considerations 1867 The objective of the AODVv2 protocol is for each router to 1868 communicate reachability information about addresses for which it is 1869 responsible. Positive routing information (i.e. a route exists) is 1870 distributed via RREQ and RREP messages. Negative routing information 1871 (i.e. a route does not exist) is distributed via RERRs. AODVv2 1872 routers store the information contained in these messages in order to 1873 properly forward data packets, and they generally provide this 1874 information to other AODVv2 routers. 1876 This section does not mandate any specific security measures. 1877 Instead, this section describes various security considerations and 1878 potential avenues to secure AODVv2 routing. 1880 The most important security mechanisms for AODVv2 routing are 1881 integrity/authentication and confidentiality. 1883 In situations where routing information or router identity are 1884 suspect, integrity and authentication techniques SHOULD be applied to 1885 AODVv2 messages. In these situations, routing information that is 1886 distributed over multiple hops SHOULD also verify the integrity and 1887 identity of information based on originator of the routing 1888 information. 1890 A digital signature could be used to identify the source of AODVv2 1891 messages and information, along with its authenticity. A nonce or 1892 timestamp SHOULD also be used to protect against replay attacks. S/ 1893 MIME and OpenPGP are two authentication/integrity protocols that 1894 could be adapted for this purpose. 1896 In situations where confidentiality of AODVv2 messages is important, 1897 cryptographic techniques can be applied. 1899 In certain situations, for example sending a RREP or RERR, an AODVv2 1900 router could include proof that it has previously received valid 1901 routing information to reach the destination, at one point of time in 1902 the past. In situations where routers are suspected of transmitting 1903 maliciously erroneous information, the original routing information 1904 along with its security credentials SHOULD be included. 1906 Note that if multicast is used, any confidentiality and integrity 1907 algorithms used MUST permit multiple receivers to handle the message. 1909 Routing protocols, however, are prime targets for impersonation 1910 attacks. In networks where the node membership is not known, it is 1911 difficult to determine the occurrence of impersonation attacks, and 1912 security prevention techniques are difficult at best. However, when 1913 the network membership is known and there is a danger of such 1914 attacks, AODVv2 messages must be protected by the use of 1915 authentication techniques, such as those involving generation of 1916 unforgeable and cryptographically strong message digests or digital 1917 signatures. While AODVv2 does not place restrictions on the 1918 authentication mechanism used for this purpose, IPsec Authentication 1919 Message (AH) is an appropriate choice for cases where the nodes share 1920 an appropriate security association that enables the use of AH. 1922 In particular, routing messages SHOULD be authenticated to avoid 1923 creation of spurious routes to a destination. Otherwise, an attacker 1924 could masquerade as that destination and maliciously deny service to 1925 the destination and/or maliciously inspect and consume traffic 1926 intended for delivery to the destination. RERR messages SHOULD be 1927 authenticated in order to prevent malicious nodes from disrupting 1928 active routes between communicating nodes. 1930 If the mobile nodes in the ad hoc network have pre-established 1931 security associations, the purposes for which the security 1932 associations are created should include that of authorizing the 1933 processing of AODVv2 control packets. Given this understanding, the 1934 mobile nodes should be able to use the same authentication mechanisms 1935 based on their IP addresses as they would have used otherwise. 1937 If the mobile nodes in the ad hoc network have pre-established 1938 security associations, the purposes for which the security 1939 associations Most AODVv2 messages are transmitted to the multicast 1940 address LL-MANET-Routers [RFC5498]. It is therefore required for 1941 security that AODVv2 neighbors exchange security information that can 1942 be used to insert an ICV [RFC6621] into the AODVv2 message block 1943 [RFC5444]. This enables hop-by-hop security. For destination-only 1944 RREP discovery procedures, AODVv2 routers that share a security 1945 association SHOULD use the appropriate mechanisms as specified in RFC 1946 6621. The establishment of these security associations is out of 1947 scope for this document. 1949 17. Acknowledgments 1951 AODVv2 is a descendant of the design of previous MANET on-demand 1952 protocols, especially AODV [RFC3561] and DSR [RFC4728]. Changes to 1953 previous MANET on-demand protocols stem from research and 1954 implementation experiences. Thanks to Elizabeth Belding-Royer for 1955 her long time authorship of AODV. Additional thanks to Derek Atkins, 1956 Emmanuel Baccelli, Abdussalam Baryun, Ramon Caceres, Thomas Clausen, 1957 Christopher Dearlove, Ulrich Herberg, Henner Jakob, Luke Klein- 1958 Berndt, Lars Kristensen, Tronje Krop, Koojana Kuladinithi, Kedar 1959 Namjoshi, Alexandru Petrescu, Henning Rogge, Fransisco Ros, Pedro 1960 Ruiz, Christoph Sommer, Lotte Steenbrink, Romain Thouvenin, Richard 1961 Trefler, Jiazi Yi, Seung Yi, and Cong Yuan, for their reviews AODVv2 1962 and DYMO, as well as numerous specification suggestions. 1964 18. References 1966 18.1. Normative References 1968 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1969 Requirement Levels", BCP 14, RFC 2119, March 1997. 1971 [RFC5082] Gill, V., Heasley, J., Meyer, D., Savola, P., and C. 1972 Pignataro, "The Generalized TTL Security Mechanism 1973 (GTSM)", RFC 5082, October 2007. 1975 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 1976 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 1977 Format", RFC 5444, February 2009. 1979 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 1980 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 1981 2009. 1983 [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc Network 1984 (MANET) Protocols", RFC 5498, March 2009. 1986 [RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D. 1987 Barthel, "Routing Metrics Used for Path Calculation in 1988 Low-Power and Lossy Networks", RFC 6551, March 2012. 1990 18.2. Informative References 1992 [I-D.perkins-irrep] 1993 Perkins, C. and I. Chakeres, "Intermediate RREP for 1994 dynamic MANET On-demand (AODVv2) Routing", draft-perkins- 1995 irrep-02 (work in progress), November 2012. 1997 [Perkins94] 1998 Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 1999 Sequenced Distance-Vector Routing (DSDV) for Mobile 2000 Computers", Proceedings of the ACM SIGCOMM '94 Conference 2001 on Communications Architectures, Protocols and 2002 Applications, London, UK, pp. 234-244, August 1994. 2004 [Perkins99] 2005 Perkins, C. and E. Royer, "Ad hoc On-Demand Distance 2006 Vector (AODV) Routing", Proceedings of the 2nd IEEE 2007 Workshop on Mobile Computing Systems and Applications, New 2008 Orleans, LA, pp. 90-100, February 1999. 2010 [RFC2501] Corson, M. and J. Macker, "Mobile Ad hoc Networking 2011 (MANET): Routing Protocol Performance Issues and 2012 Evaluation Considerations", RFC 2501, January 1999. 2014 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 2015 Demand Distance Vector (AODV) Routing", RFC 3561, July 2016 2003. 2018 [RFC4193] Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast 2019 Addresses", RFC 4193, October 2005. 2021 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 2022 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 2023 IPv4", RFC 4728, February 2007. 2025 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 2026 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 2027 September 2007. 2029 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 2030 Considerations in Mobile Ad Hoc Networks (MANETs)", RFC 2031 5148, February 2008. 2033 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 2034 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 2035 RFC 6130, April 2011. 2037 [RFC6621] Macker, J., "Simplified Multicast Forwarding", RFC 6621, 2038 May 2012. 2040 Appendix A. Example Algorithms for AODVv2 Protocol Operations 2042 The following subsections show example algorithms for protocol 2043 operations required by AODVv2, including RREQ, RREP, RERR, and RREP- 2044 ACK. 2046 Processing for RREQ, RREP, and RERR messages follows the following 2047 general outline: 2049 1. Receive incoming message. 2050 2. Update route table as appropriate. 2051 3. Respond as needed, often regenerating the incoming message with 2052 updated information. 2054 Once the route table has been updated, the information contained 2055 there is known to be the most recent available information for any 2056 fields in the outgoing message. For this reason, the algorithms are 2057 written as if outgoing message field values are assigned from the 2058 route table information, even though it is often equally appropriate 2059 to use fields from the incoming message. 2061 AODVv2_algorithms: 2063 o Process_Routing_Info 2064 o Generate_RREQ 2065 o Receive_RREQ 2066 o Regenerate_RREQ 2067 o Generate_RREP 2068 o Receive_RREP 2069 o Regenerate_RREP 2070 o Generate_RERR 2071 o Receive_RERR 2072 o Regenerate_RERR 2073 o Generate_RREP_Ack 2074 o Consume_RREP_Ack() 2075 o Timeout RREP_Ack() 2077 The following lists indicate the meaning of the field names used in 2078 subsequent sections to describe message processing for the above 2079 algorithms. 2081 Incoming RREQ message parameters: 2083 inRREQ.origIP := originator IP address 2084 inRREQ.origSeq := originator IP sequence # 2085 inRREQ.metType := metric type 2086 inRREQ.origMet := metric to originator 2087 inRREQ.targIP := target IP address 2088 inRREQ.targSeq := target sequence # (if known) 2089 inRREQ.hopLim := msg-hop-limit /* from RFC 5444 header */ 2090 inRREQ.nbrIP := IP address of the neighbor that sent the RREQ 2092 Outgoing RREQ message parameters: 2094 outRREQ.origIP := originator IP address 2095 outRREQ.origSeq := originator IP sequence # 2096 outRREQ.metType := metric type 2097 outRREQ.origMet := metric to origNode {initially 2098 MIN_METRIC[MetType]} 2099 outRREQ.targIP := target IP address 2100 outRREQ.targSeq := target sequence # (if known) 2101 outRREQ.hopLim /* initially MAX_HOPCOUNT at originator */ 2103 Incoming RREP message parameters: 2105 inRREP.hoplim /* msg-hop-limit from RFC 5444 header */ 2106 inRREP.origIP := originator's IP address 2107 inRREP.metType := metric type 2108 inRREP.targIP := target IP address 2109 inRREP.targSeq := target sequence # 2110 inRREP.targMet := target's metric {initially MIN_METRIC[MetType]} 2111 inRREP.PfxLen 2113 Outgoing RREP message parameters: 2115 outRREP.origIP := originator's IP address 2116 outRREP.metType := metric type 2117 outRREP.targIP := target IP address 2118 outRREP.targSeq := target sequence # 2119 outRREP.targMet := target's metric {starting with zero} 2120 outRREP.PfxLen 2121 outRREP.hopLim /* initially MAX_HOPCOUNT at originator */ 2123 Incoming RERR message parameters: 2125 inRERR.PktSrc := source IP of unforwardable packet (if present) 2126 inRERR.metType := metric type for routes to unreachable 2127 destinations 2128 inRERR.PfxLen[] := prefix lengths for unreachable destinations 2129 inRERR.LostDest[] := unreachable destinations 2130 inRERR.LostSeq[] := sequence #s for unreachable destinations 2132 Outgoing RERR message parameters: 2134 outRERR.PktSrc := source IP of unforwardable packet (if present) 2135 outRERR.metType := metric type for routes to unreachable 2136 destinations 2137 outRERR.PfxLen[] := prefix lengths for unreachable destinations 2138 outRERR.LostDest[] := unreachable destinations 2139 outRERR.LostSeq[] := sequence #s for unreachable destinations 2141 A.1. Subroutines for AODVv2 Protocol Operations 2143 /* Compare incoming route information to current route, maybe use */ 2144 Process_Routing_Info (dest, seq#, metric_type, metric, 2145 last_hop_metric) 2146 /* last_hop_metric: either Cost(inRREQ.netif) or (inRREP.netif) */ 2147 { 2148 new_metric := metric + last_hop_metric; 2149 rte := Fetch_Route_Table_Entry (dest, seq#, metric_type); 2150 if (NULL == rte) { 2151 rte := Create_Route_Table_Entry 2152 (dest, seq#, metric_type, new_metric); 2153 } else if (seq# > rte.seq#) { /* stale rte route entry */ 2154 Update_Route_Table_Entry (rte, seq#, metric_type, new_metric); 2155 } else if (seq# < rte.seq#) { /* stale incoming route infor */ 2156 return(NULL); 2157 } else if (rte.state == broken) { /* when (seq# == rte.seq#) */ 2158 Update_Route_Table_Entry (rte, seq#, metric_type, new_metric); 2159 } else if (rte.metric > (new_metric) { /* and (seq# == rte.seq#) */ 2160 Update_Route_Table_Entry (rte, seq#, metric_type, new_metric); 2161 } else { /* incoming route information is not useful */ 2162 return(NULL); 2163 } 2164 return (rte); 2165 } 2167 A.2. Example Algorithms for AODVv2 RREQ Operations 2169 A.2.1. Generate_RREQ 2170 Generate_RREQ { 2171 /* Marshall parameters */ 2172 outRREQ.origIP := IP address used by application 2173 outRREQ.origSeq := originating router's sequence # 2174 outRREQ.metType := (if included) metric type needed by application 2175 outRREQ.origMet := 0 (default) or MIN_METRIC(Metric_type) 2176 outRREQ.targIP := target IP address 2177 outRREQ.targSeq := target sequence # /* if known from route table */ 2178 outRREQ.hopLim := msg-hop-limit /* RFC 5444 */ 2180 /* build RFC 5444 message header fields */ 2181 { 2182 msg-type=RREQ (message is of type RREQ) 2183 MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2184 MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6]) 2185 msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs) 2186 msg-hop-limit := MAX_HOPCOUNT 2187 if (Metric_type == DEFAULT) { 2188 msg.tlvs-length=0 2189 } else { /* Metric_type != HopCount */ 2190 /* Build Metric_type Message TLV */ 2191 } 2192 } 2194 /* build AddrBlk */ 2195 num-addr := 2 2196 AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses} 2198 /* Include each available Sequence Number in appropriate AddrTLV */ 2199 /* put outRREQ.origSeq in OrigSeqNum AddrTLV */ 2200 if (NULL != targSeq) { 2201 /* put outRREQ.targSeq in TargSeqNum AddrTLV */ 2202 } 2204 /* Build Metric AddrTLV containing OrigNode metric */ 2205 /* use MIN_METRIC(metric type) [==0 for default metric type */ 2206 } 2208 A.2.2. Receive_RREQ 2209 Receive_RREQ (inRREQ) { 2210 /* Extract inRREQ values */ 2211 origRTE = Process_Routing_Info (inRREQ.origIP, inRREQ.origSeq, ...) 2212 if (inRREQ.targIP belongs to me or my client subnet) { 2213 Generate_RREP() 2214 } else if (inRREQ present in RREQ_table) { 2215 return; /* don't regenerate RREQ... */ 2216 } else if (inRREQ.nbrIP not present in blacklist) { 2217 Regenerate_RREQ(origRTE, inRREQ) 2218 } else if (blacklist_expiration_time > current_time) { 2219 return; /* don't regenerate RREQ... */ 2220 } else { 2221 Remove nbrIP from blacklist; 2222 Regenerate_RREQ(origRTE, inRREQ) 2223 } 2224 } 2226 A.2.3. Regenerate_RREQ 2227 Regenerate_RREQ (origRTE, inRREQ) { /* called from receive_RREQ() */ 2228 outRREQ.hopLim := inRREQ.hopLim - 1 2229 if (outRREQ.hopLim == 0) { /* don't regenerate */ 2230 return() 2231 } 2232 /* Marshall parameters */ 2233 outRREQ.origIP := origRTE.origIP 2234 outRREQ.origSeq := origRTE.origSeq 2235 outRREQ.origMet := origRTE.origMet 2236 outRREQ.metType := origRTE.metType 2237 outRREQ.targIP := inRREQ.targIP 2238 outRREQ.targSeq := inRREQ.targSeq /* if present */ 2240 /* build RFC 5444 message header fields */ 2241 { 2242 msg-type=RREQ (message is of type RREQ) 2243 MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2244 MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6]) 2245 msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs) 2246 msg-hop-limit := MAX_METRIC(Metric Type) (default, MAX_HOPCOUNT) 2247 if (Metric_type == DEFAULT) { 2248 msg.tlvs-length=0 2249 } else { /* Metric_type != HopCount */ 2250 /* Build Metric_type Message TLV */ 2251 } 2252 } 2254 /* build AddrBlk */ 2255 num-addr := 2 2256 AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses} 2258 /* Include each available Sequence Number in its proper AddrTLV */ 2259 /* put outRREQ.origSeq in OrigSeqNum AddrTLV */ 2260 if (NULL != targSeq) { 2261 /* put outRREQ.targSeq in TargSeqNum AddrTLV */ 2262 } 2264 /* Build Metric AddrTLV to contain outRREQ.origMet */ 2266 } 2268 A.3. Example Algorithms for AODVv2 RREP Operations 2269 A.3.1. Generate_RREP 2271 Generate_RREP { 2272 /* Marshall parameters */ 2273 outRREP.origIP := origRTE.origIP 2274 metric_type := origRTE.metType /* if not default */ 2275 if (DEFAULT != metric_type) 2276 outRREP.metType := metric_type 2277 outRREP.targIP := inRREQ.targIP 2278 outRREP.targMet := MIN_METRIC(outRREP.metType) (0 by default) 2279 my_sequence_# := (1 + my_sequence_#) /* from nonvolatile storage */ 2280 outRREP.targSeq := my_sequence_# 2282 /* build RFC 5444 message header fields */ 2283 { 2284 msg-type=RREP 2285 MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2286 MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6]) 2287 msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs) 2288 msg-hop-limit := MAX_HOPCOUNT 2289 /* Include the AckReq TLV when: 2290 - previous RREP does not seem to enable any data flow, OR 2291 - when RREQ is received from same OrigNode after RREP was 2292 unicast to targRTE.nextHop 2293 */ 2294 if (DEFAULT != metric_type) { 2295 msg.tlvs-length=0 2296 } else { /* Metric_type != HopCount */ 2297 /* Build Metric_type Message TLV */ 2298 } 2299 } 2301 /* build AddrBlk */ 2302 num-addr := 2 2303 AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses} 2305 /* put outRREP.TargSeq in TargSeqNum AddrTLV */ 2307 /* Build Metric AddrTLV containing TargNode metric */ 2308 /* use MIN_METRIC(origRTE.metType) */ 2309 } 2311 A.3.2. Receive_RREP 2313 Receive_RREP (inRREP) 2314 { 2315 If (RREP includes AckReq TLV) { 2316 Generate_RREP_Ack() 2317 } 2318 /* Extract inRREP values */ 2319 targRTE := Process_Routing_Info (inRREP.targIP, inRREP.targSeq, ...) 2320 if (inRREP.targIP belongs to me, a client, or a client subnet) { 2321 Consume_RREP(inRREP) 2322 } else { 2323 Regenerate_RREP(targRTE, inRREP) 2324 } 2325 } 2327 A.3.3. Regenerate_RREP 2329 Regenerate_RREP(targRTE, inRREP) { 2330 outRREP.hopLim := inRREP.hopLim - 1 2331 if (outRREP.hopLim == 0) { /* don't regenerate */ 2332 return() 2333 } 2334 /* Marshall parameters */ 2335 outRREP.targIP := targRTE.targIP 2336 outRREP.targSeq := targRTE.targSeq 2337 outRREP.targMet := targRTE.targMet 2338 metric_type := origRTE.metType /* if not default */ 2339 if (DEFAULT != metric_type) 2340 outRREP.metType := metric_type 2341 outRREP.origIP := inRREP.origIP 2342 outRREP.nextHop := targRTE.nextHop 2344 /* build RFC 5444 message header fields */ 2345 { 2346 msg-type=RREP (message is of type RREP) 2347 MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2348 MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6]) 2349 msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs) 2350 /* Include the AckReq TLV when: 2351 - previous RREP does not seem to enable any data flow, OR 2352 - when RREQ is received from same OrigNode after RREP was 2353 unicast to targRTE.nextHop 2354 */ 2355 msg-hop-limit := outRREP.hopLim; 2356 if (metric_type == DEFAULT) { 2357 msg.tlvs-length=0 2358 } else { /* Metric_type != HopCount */ 2359 /* Build Metric_type Message TLV */ 2360 } 2361 } 2363 /* build AddrBlk */ 2364 num-addr := 2 2365 AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses} 2367 /* put outRREP.targSeq in TargSeqNum AddrTLV */ 2369 /* Build Metric AddrTLV containing TargNode metric */ 2370 } 2372 A.3.4. Consume_RREP 2374 /* executed by RREQ_Gen */ 2375 /* TargNode route table entry was updated by Receive_RREP() */ 2376 Consume_RREP() { 2377 /* Transmit buffered packet(s) (if any) to TargNode */ 2378 } 2380 A.4. Example Algorithms for AODVv2 RERR Operations 2382 A.4.1. Generate_RERR 2384 Generate_RERR() 2385 { 2386 metric_type := DEFAULT; 2387 switch (error_type) in { 2388 case (broken_link): 2389 num-broken-addr=0 2390 /* find unreachable destinations, seqNums, prefixes */ 2391 for (every rte (route table entry) in route table) { 2392 if (broken_link == rte.next_hop) { 2393 rte.state := broken; 2394 outRERR.LostDest[num-broken-addr] := rte.dest 2395 outRERR.LostSeq[num-broken-addr] := rte.seq# 2396 outRERR.PfxLen[num-broken-addr] := rte.pfx 2397 metric_type := rte.metType 2398 num-broken-addr := (num-broken-addr+1) 2399 } 2400 } 2401 /* No offending-src for this case */ 2402 case (undeliverable packet): 2403 offending-src := undeliverable_packet.srcIP 2404 outRERR.LostDest[] := undeliverable_packet.destIP 2405 outRERR.LostPfxSiz[] := MAX_PFX_SIZE /* 31 or 127 */ 2406 num-broken-addr=1 2407 } 2409 /* build RFC 5444 message header fields */ 2410 { 2411 msg-type=RERR (message is of type RERR) 2412 MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2413 MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6]) 2414 msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs) 2415 msg-hop-limit := outRERR.hopLim; 2416 if (NULL != offending-src) { 2417 /* Build PktSource Message TLV */ 2418 } 2419 if (metric_type != DEFAULT) { /* Metric_type != HopCount */ 2420 /* Build Metric_type Message TLV */ 2421 } 2422 } 2424 /* build AddrBlk */ 2425 num-addr := num-broken-addr; 2426 AddrBlk := outRERR.LostDest[]; 2428 /* Add AddrBlk Seq# TLV */ 2429 Seq#TLV := outRERR.LostSeq[] 2431 /* only add AddrBlk PfxSiz TLV if prefixes are nondefault */ 2432 for (pfx in outRERR.LostPfx[]) { 2433 if (pfx != Max_Prefix_Size) { /* 31 for IPv4, 127 for IPv6 */ 2434 PfxSizTLV := outRERR.LostPfx[] 2435 return; 2436 } 2437 } 2438 } 2440 A.4.2. Receive_RERR 2441 Receive_RERR (inERR) 2442 { 2443 /* Extract inERR values */ 2444 next_hop := inRERR.nbrIP 2445 offending-src := inRERR.offending-src; /* NULL if not present */ 2447 precursors[] := NULL; 2448 num-broken-addr := 0; 2449 in-broken-addr := 0; 2450 for (IPaddr := inRERR.LostDest[in-broken-addr]) { 2451 rte := Fetch_Route_Table_Entry (dest, metric_type); 2452 if (NULL == rte) { 2453 continue; 2454 } else if (rte.nextHop != inRERR.fromIP) { 2455 continue; 2456 } else if (NULL != rte.precursors) { 2457 /* add rte.precursors to precursors */ 2458 } else if (rte.PfxSiz < inRERR.PfxSiz) { 2459 /*********************************************************** 2460 If the reported prefix from the incoming RERR is *longer* 2461 than the prefix from Route Table, then create a new route 2462 with the longer prefix. 2463 The newly created route will be marked as broken, and used 2464 to regenerate RERR, NOT using shorter the routing prefix. 2465 This avoids unnecessarily invalidating the larger subnet. 2466 **********************************************************/ 2467 rte := Create_Route_Table_Entry (IPaddr, seq#, 2468 metric_type, new_metric, inRERR.PfxSiz); 2469 } 2470 LostDest[num-broken-addr] := rte.Dest; 2471 Seq#[num-broken-addr] := rte.Seq#; 2472 PfxSiz[num-broken-addr] := rte.PfxSiz; 2473 rte.state = broken; 2474 num-broken-addr := (num-broken-addr + 1); 2475 in-broken-addr := (in-broken-addr + 1); 2476 } 2477 if (num-broken-addr > 0) { 2478 Regenerate_RERR (offending-src, precursors, 2479 LostDest[], Seq#[], PfxSiz[]) 2480 } 2481 } 2483 A.4.3. Regenerate_RERR 2484 Regenerate_RERR (offending-src, precursors, 2485 LostDest[], LostSeq#[], PfxSiz[]) 2486 { 2487 /* build RFC 5444 message header fields */ 2488 { 2489 msg-type=RERR (message is of type RERR) 2490 MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2491 MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6]) 2492 msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs) 2493 outRERR.hopLim := inRERR.hopLim - 1 2494 msg-hop-limit := outRERR.hopLim; 2496 if (NULL != offending-src) { 2497 /* Build PktSource Message TLV */ 2498 } 2499 if (metric_type != DEFAULT) { /* Metric_type != HopCount */ 2500 /* Build Metric_type Message TLV */ 2501 } 2502 } 2504 /* build AddrBlk */ 2505 num-addr := num-broken-addr; 2506 AddrBlk := LostDest[]; 2508 /* Add AddrBlk Seq# TLV */ 2509 Seq#TLV := LostSeq[] 2511 /* only add AddrBlk PfxSiz TLV if prefixes are nondefault */ 2512 for (pfx in PfxSiz[]) { 2513 if (pfx != Max_Prefix_Size) { /* 31 for IPv4, 127 for IPv6 */ 2514 PfxSizTLV := PfxSiz[] 2515 } 2516 } /* If all are default, don't include PfxSize AddrTLV */ 2518 if (#precursors == 1) { 2519 unicast RERR to precursor[0]; 2520 } else if (#precursors > 1) { 2521 multicast RERR to RERR_PRECURSORS; 2522 } else if (offending-src != NULL) { 2523 unicast RERR to offending-src; 2524 } else { 2525 multicast RERR to RERR_PRECURSORS; 2526 } 2527 } 2529 A.5. Example Algorithms for AODVv2 RREP-Ack Operations 2531 A.5.1. Generate_RREP_Ack 2533 /* To be sent when RREP includes the AckReq TLV */ 2534 Generate_RREP_Ack() 2535 { 2536 /* assign RFC 5444 fields */ 2537 msgtype := RREPAck 2538 MF := 0 2539 MAL := 3 2540 msg-size := 4 2541 } 2543 A.5.2. Consume_RREP_Ack 2545 Consume_RREP_Ack() 2546 { 2547 /* turn off timeout event for the node sending RREP_Ack */ 2548 } 2550 A.5.3. Timeout_RREP_Ack 2552 Timeout_RREP_Ack() 2553 { 2554 /* insert unresponsive node into blacklist */ 2555 } 2557 Appendix B. Example RFC 5444-compliant packet formats 2559 The following subsections show example RFC 5444-compliant packets for 2560 AODVv2 message types RREQ, RREP, RERR, and RREP-Ack. These proposed 2561 message formats are designed based on expected savings from IPv6 2562 addressable MANET nodes, and a layout for the Address TLVs that may 2563 be viewed as natural, even if perhaps not the absolute most compact 2564 possible encoding. 2566 For RteMsgs, the msg-hdr fields are followed by at least one and 2567 optionally two Address Blocks. The first AddrBlk contains OrigNode 2568 and TargNode. For each AddrBlk, there must be AddrTLVs of type 2569 Metric and one of the SeqNum types (i.e, OrigSeqNum, TargSeqNum, or 2570 Seqnum). 2572 There is no Metric Type Message TLV present, so the Metric AddrTLV 2573 measures HopCount. The Metric AddrTLV also provides a way for the 2574 AODV router generating the RREQ or RREP to supply an initial nonzero 2575 cost for the route to its client node (OrigNode or TargNode, for RREQ 2576 or RREP respectively). 2578 In all cases, the length of an address (32 bits for IPv4 and 128 bits 2579 for IPv6) inside an AODVv2 message is indicated by the msg-addr- 2580 length (MAL) in the msg-header, as specified in [RFC5444]. 2582 The RFC 5444 header preceding AODVv2 messages in this document has 2583 the format illustrated in Figure 4. 2585 0 1 2 3 2586 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2587 +-+-+-+-+-+-+-+-+ 2588 | PV=0 | PF=0 | 2589 +-+-+-+-+-+-+-+-+ 2591 Figure 4: RFC 5444 Packet Header 2593 The fields in Figure 4 are to be interpreted as follows: 2595 o PV=0 (Packet Header Version = 0) 2596 o PF=0 (Packet Flags = 0) 2598 B.1. RREQ Message Format 2600 Figure 5 illustrates an example RREQ message format. 2602 0 1 2 3 2603 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2605 | msg-type=RREQ | MF=4 | MAL=3 | msg-size=28 | 2606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2607 | msg-hop-limit | msg.tlvs-length=0 | num-addr=2 | 2608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2609 |1|0|0|0|0| Rsv | head-length=3 | Head (bytes for Orig & Target): 2610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2611 :Head(Orig&Targ)| Orig.Tail | Target.Tail |addr.TLV.len=11: 2612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2613 :addr.TLV.len=11|type=OrigSeqNum|0|1|0|1|0|0|Rsv| Index-start=0 | 2614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2615 | tlv-length=2 | Orig.Node Sequence # | type=Metric | 2616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2617 |0|1|0|1|0|0|Rsv| Index-start=0 | tlv-length=1 | OrigNodeHopCt | 2618 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2620 Figure 5: Example IPv4 RREQ, with OrigSeqNum and Metric AddrTLVs 2622 The fields in Figure 5 are to be interpreted as follows: 2624 o msg-type=RREQ (first [and only] message is of type RREQ) 2625 o MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2626 o MAL=3 (Message Address Length indicator [3 for IPv4, 15 for IPv6]) 2627 o msg-size=28 (octets -- counting MsgHdr, MsgTLVs, and AddrBlks) 2628 o msg-hop-limit (initially MAX_HOPCOUNT by default) 2629 o msg.tlvs-length=0 (no Message TLVs) 2630 o num-addr=2 (OrigNode and TargNode addresses in RteMsg AddrBlock) 2631 o AddrBlk flags: 2633 * bit 0 (ahashead): 1 2634 * bit 1 (ahasfulltail): 0 2635 * bit 2 (ahaszerotail): 0 2636 * bit 3 (ahassingleprelen): 0 2637 * bit 4 (ahasmultiprelen): 0 2638 * bits 5-7: RESERVED 2639 o head-length=3 (length of head part of each address is 3 octets) 2640 o Head (3 initial bytes for both Originating & Target addresses) 2641 o Orig.Tail (4th byte of Originating Node IP address) 2642 o Target.Tail (4th byte of Target Node IP address) 2643 o addr.TLV.len = 11 (length in bytes for OrigSeqNum and Metric TLVs 2644 o type=OrigSeqNum (type of first AddrBlk TLV, value 2 octets) 2645 o AddrTLV flags for the OrigSeqNum TLV: 2647 * bit 0 (thastypeext): 0 2648 * bit 1 (thassingleindex): 1 2649 * bit 2 (thasmultiindex): 0 2650 * bit 3 (thasvalue): 1 2651 * bit 4 (thasextlen): 0 2652 * bit 5 (tismultivalue): 0 2653 * bits 6-7: RESERVED 2654 o Index-start=0 (OrigSeqNum TLV value applies at index 0) 2655 o tlv-length=2 (so there is only one TLV value, [1 = 2/2]) 2656 o Orig.Node Sequence # (TLV value for the OrigSeqNum TLV 2657 o type=Metric (AddrTLV type of second AddrBlk TLV, values 1 octet) 2658 o AddrTLV flags for Metric_TLV: 2660 * bit 0 (thastypeext): 0 2661 * bit 1 (thassingleindex): 1 2662 * bit 2 (thasmultiindex): 0 2663 * bit 3 (thasvalue): 1 2664 * bit 4 (thasextlen): 0 2665 * bit 5 (tismultivalue): 0 2666 * bits 6-7: RESERVED 2667 o Index-start=0 (Metric TLV values start at index 0) 2668 o tlv-length=1 (so there is only one TLV value, [1 = 1/1]) 2669 o OrigNodeHopCt (first [and only] TLV value for the Metric TLV) 2671 B.2. RREP Message Format 2673 Figure 6 illustrates a packet format for an example RREP message. 2675 0 1 2 3 2676 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2678 | msg-type=RREP | MF=4 | MAL=3 | msg-size=28 | 2679 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2680 | msg-hop-limit | msg.tlvs-length=0 | num-addr=2 | 2681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2682 |1|0|0|0|0| Rsv | head-length=3 | Head (bytes for Orig & Target): 2683 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2684 :Head(Orig&Targ)| Orig.Tail | Target.Tail |addr.TLV.len=11: 2685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2686 :addr.TLV.len=11|type=TargSeqNum|0|1|0|1|0|0|Rsv| Index-start=1 | 2687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2688 | tlv-length=2 | Targ.Node Sequence # | type=Metric | 2689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2690 |0|1|0|1|0|0|Rsv| Index-start=1 | tlv-length=1 | TargNodeHopCt | 2691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2693 Figure 6: Example IPv4 RREP, with TargSeqNum TLV and 1 Metric 2695 The fields in Figure 6 are to be interpreted as follows: 2697 o msg-type=RREP (first [and only] message is of type RREP) 2698 o MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2699 o MAL=3 (Message Address Length indicator [3 for IPv4, 15 for IPv6]) 2700 o msg-size=28 (octets -- counting MsgHdr, MsgTLVs, and AddrBlks) 2701 o msg-hop-limit (initially MAX_HOPCOUNT by default) 2702 o msg.tlvs-length=0 (no Message TLVs) 2703 o num-addr=2 (OrigNode and TargNode addresses in RteMsg AddrBlock) 2704 o AddrBlk flags: 2706 * bit 0 (ahashead): 1 2707 * bit 1 (ahasfulltail): 0 2708 * bit 2 (ahaszerotail): 0 2709 * bit 3 (ahassingleprelen): 0 2710 * bit 4 (ahasmultiprelen): 0 2711 * bits 5-7: RESERVED 2712 o head-length=3 (length of head part of each address is 3 octets) 2713 o Head (3 initial bytes for both Originating & Target addresses) 2714 o Orig.Tail (4th byte of Originating Node IP address) 2715 o Target.Tail (4th byte of Target Node IP address) 2716 o addr.TLV.len = 11 (length in bytes for TargSeqNum TLV and Metric 2717 TLV 2718 o type=TargSeqNum (type of first AddrBlk TLV, value 2 octets) 2719 o AddrTLV flags for the TargSeqNum TLV: 2721 * bit 0 (thastypeext): 0 2722 * bit 1 (thassingleindex): 1 2723 * bit 2 (thasmultiindex): 0 2724 * bit 3 (thasvalue): 1 2725 * bit 4 (thasextlen): 0 2726 * bit 5 (tismultivalue): 0 2727 * bits 6-7: RESERVED 2728 o Index-start=1 (TargSeqNum TLV value applies to address at index 1) 2729 o tlv-length=2 (there is one TLV value, 2 bytes in length) 2730 o Targ.Node Sequence # (value for the TargSeqNum TLV) 2731 o type=Metric (AddrTLV type of second AddrBlk TLV, value 1 octet) 2732 o AddrTLV flags for the Metric TLV [01010000, same as for TargSeqNum 2733 TLV] 2734 o Index-start=1 (Metric TLV values start at index 1) 2735 o tlv-length=1 (there is one TLV value, 1 byte in length) 2736 o TargNodeHopCt (first [and only] TLV value for Metric TLV) 2738 B.3. RERR Message Format 2740 Figure 7 illustrates an example RERR message format. 2742 0 1 2 3 2743 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2744 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2745 | msg-type=RERR | MF=4 | MAL=3 | msg-size=24 | 2746 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2747 | msg-hop-limit | msg.tlvs-length=0 | num-addr=2 | 2748 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2749 |1|0|0|0|0| Rsv | head-length=3 | Head (for both destinations) : 2750 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2751 :Head (3rd byte)| Tail(Dest_1) | Tail(Dest_2) | addr.TLV.len=7: 2752 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2753 :addr.TLV.len=7 | type=SeqNum |0|0|1|1|0|1|Rsv| tlv-length=4 | 2754 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2755 | Dest_1 Sequence # | Dest_2 Sequence # | 2756 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2758 Figure 7: Example IPv4 RERR with Two Unreachable Nodes 2760 The fields in Figure 7 are to be interpreted as follows: 2762 o msg-type=RERR (first [and only] message is of type RERR) 2763 o MF=4 (Message Flags = 4 [only msg-hop-limit field is present]) 2764 o MAL=3 (Message Address Length indicator [3 for IPv4, 15 for IPv6]) 2765 o msg-size=24 (octets -- counting MsgHdr, MsgTLVs, and AddrBlks) 2766 o msg-hop-limit (initially MAX_HOPCOUNT by default) 2767 o msg.tlvs-length=0 (no Message TLVs) 2768 o num-addr=2 (OrigNode and TargNode addresses in RteMsg AddrBlock) 2769 o AddrBlk flags == 10000000 [same as RREQ and RREP AddrBlk examples] 2770 o head-length=3 (length of head part of each address is 3 octets) 2771 o Head (3 initial bytes for both Unreachable Nodes, Dest_1 and 2772 Dest_2) 2773 o Dest_1.Tail (4th byte of Dest_1 IP address) 2774 o Dest_2.Tail (4th byte of Dest_2 IP address) 2775 o addr.TLV.len = 7 (length in bytes for SeqNum TLV 2776 o type=SeqNum (AddrTLV type of AddrBlk TLV, values 2 octets each) 2777 o AddrTLV flags for SeqNum TLV: 2779 * bit 0 (thastypeext): 0 2780 * bit 1 (thassingleindex): 0 2781 * bit 2 (thasmultiindex): 1 2782 * bit 3 (thasvalue): 1 2783 * bit 4 (thasextlen): 0 2784 * bit 5 (tismultivalue): 1 2785 * bits 6-7: RESERVED 2787 o tlv-length=4 (so there are two TLV values, [2 = 4/2]) 2788 o Dest_1 Sequence # (first of two TLV values for the SeqNum TLV) 2789 o Dest_2 Sequence # (second of two TLV values for the SeqNum TLV) 2791 B.4. RREP_ACK Message Format 2793 The figure below illustrates a packet format for an example RREP_ACK 2794 message. 2796 0 1 2 3 2797 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2798 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2799 |msgtype=RREPAck| MF=0 | MAL=3 | msg-size=4 | 2800 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2802 Figure 8: Example IPv4 RREP_ACK 2804 Appendix C. Changes since revision ...-04.txt 2806 This section lists the changes since AODVv2 revision ...-04.txt 2808 o Normative text moved out of definitions into the relevant section 2809 of the body of the specification. 2810 o Editorial improvements and improvements to consistent terminology 2811 were made. Replaced "retransmit" by the slightly more accurate 2812 term "regenerate". 2813 o Issues were resolved as discussed on the mailing list. 2814 o Changed definition of LoopFree as suggested by Kedar Namjoshi and 2815 Richard Trefler to avoid the failure condition that they have 2816 described. In order to make understanding easier, replaced 2817 abstract parameters R1 by RteMsg and R2 by Route to reduce the 2818 level of abstraction when the function LoopFree is discussed. 2819 o Added text to clarify that different metrics may have different 2820 data types and different ranges of acceptable values. 2821 o Added text to section "RteMsg Structure" to emphasize the proper 2822 use of RFC 5444. 2823 o Included within the main body of the specification the mandatory 2824 setting of the TLV flag thassingleindex for TLVs OrigSeqNum and 2825 TargSeqNum. 2826 o Made more extensive use of the AdvRte terminology, in order to 2827 better distinguish between the incoming RREQ or RREP message 2828 (i.e., RteMsg) versus the route advertised by the RteMsg (i.e., 2829 AdvRte). 2831 Appendix D. Changes since revision ...-03.txt 2833 This section lists the changes since AODVv2 revision ...-03.txt 2835 o An appendix was added to exhibit algorithmic code for 2836 implementation of AODVv2 functions. 2837 o Numerous editorial improvements and improvements to consistent 2838 terminology were made. Terminology related to prefix lengths was 2839 made consistent. Some items listed in "Notational Conventions" 2840 were no longer used, and so deleted. 2841 o Issues were resolved as discussed on the mailing list. 2842 o Appropriate instances of "may" were changed to "MAY". 2843 o Definition inserted for "upstream". 2844 o Route.Precursors included as an *optional* route table field 2845 o Reworded text to avoid use of "relevant". 2846 o Deleted references to "DestOnly" flag. 2847 o Refined statements about Metric Type TLV to allow for omission 2848 when Metric Type == HopCount. 2849 o Bulletized list in section 8.1 2850 o ENABLE_IDLE_UNREACHABLE renamed to be ENABLE_IDLE_IN_RERR 2851 o Transmission and subscription to LL-MANET-Routers converted to 2852 MUST from SHOULD. 2854 Appendix E. Changes since revision ...-02.txt 2856 This section lists the changes since AODVv2 revision ...-02.txt 2858 o The "Added Node" feature was removed. This feature was intended 2859 to enable additional routing information to be carried within a 2860 RREQ or a RREP message, thus increasing the amount of topological 2861 information available to nodes along a routing path. However, 2862 enlarging the packet size to include information which might never 2863 be used can increase congestion of the wireless medium. The 2864 feature can be included as an optional feature at a later date 2865 when better algorithms are understood for determining when the 2866 inclusion of additional routing information might be worthwhile. 2867 o Numerous editorial improvements and improvements to consistent 2868 terminology were made. Instances of OrigNodeNdx and TargNodeNdx 2869 were replaced by OrigNdx and TargNdx, to be consistent with the 2870 terminology shown in Table 1. 2871 o Example RREQ and RREP message formats shown in the Appendices were 2872 changed to use OrigSeqNum and TargSeqNum message TLVs instead of 2873 using the SeqNum message TLV. 2874 o Inclusion of the OrigNode's SeqNum in the RREP message is not 2875 specified. The processing rules for the OrigNode's SeqNum were 2876 incompletely specified in previous versions of the draft, and very 2877 little benefit is foreseen for including that information, since 2878 reverse path forwarding is used for the RREP. 2879 o Additional acknowledgements were included, and contributors names 2880 were alphabetized. 2881 o Definitions in the Terminology section capitalize the term to be 2882 defined. 2883 o Uncited bibliographic entries deleted. 2884 o Ancient "Changes" sections were deleted. 2886 Appendix F. Multi-homing Considerations 2888 Multi-homing is not supported by the AODVv2 specification. There has 2889 been previous work indicating that it can be supported by expanding 2890 the sequence number to include the AODVv2 router's IP address as a 2891 parsable field of the SeqNum. Otherwise, comparing sequence numbers 2892 would not work to evaluate freshness. Even when the IP address is 2893 included, there isn't a good way to compare sequence numbers from 2894 different IP addresses, but at least a handling node can determine 2895 whether the two given sequence numbers are comparable. If the route 2896 table can store multiple routes for the same destination, then multi- 2897 homing can work with sequence numbers augmented by IP addresses. 2899 This non-normative information is provided simply to document the 2900 results of previous efforts to enable multi-homing. The intention is 2901 to simplify the task of future specification if multihoming becomes 2902 needed for reactive protocol operation. 2904 Appendix G. Shifting Network Prefix Advertisement Between AODVv2 2905 Routers 2907 Only one AODVv2 router within a MANET SHOULD be responsible for a 2908 particular address at any time. If two AODVv2 routers dynamically 2909 shift the advertisement of a network prefix, correct AODVv2 routing 2910 behavior must be observed. The AODVv2 router adding the new network 2911 prefix must wait for any existing routing information about this 2912 network prefix to be purged from the network. Therefore, it must 2913 wait at least ROUTER_SEQNUM_AGE_MAX_TIMEOUT after the previous AODVv2 2914 router for this address stopped advertising routing information on 2915 its behalf. 2917 Authors' Addresses 2918 Charles E. Perkins 2919 Futurewei Inc. 2920 2330 Central Expressway 2921 Santa Clara, CA 95050 2922 USA 2924 Phone: +1-408-330-5305 2925 Email: charliep@computer.org 2927 Stan Ratliff 2928 Cisco 2929 170 West Tasman Drive 2930 San Jose, CA 95134 2931 USA 2933 Email: sratliff@cisco.com 2935 John Dowdell 2936 Airbus Defence and Space 2937 Celtic Springs 2938 Newport, Wales NP10 8FZ 2939 United Kingdom 2941 Email: john.dowdell@cassidian.com