idnits 2.17.1 draft-clausen-lln-loadng-00.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 408 has weird spacing: '...Routers is a ...' == Line 911 has weird spacing: '...ous-hop is th...' == Line 1267 has weird spacing: '...ous-hop is th...' == The document seems to contain a disclaimer for pre-RFC5378 work, but was first submitted on or after 10 November 2008. The disclaimer is usually necessary only for documents that revise or obsolete older RFCs, and that take significant amounts of text from those RFCs. If you can contact all authors of the source material and they are willing to grant the BCP78 rights to the IETF Trust, you can and should remove the disclaimer. Otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 24, 2011) is 4567 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-14) exists of draft-ietf-manet-smf-12 Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group T. Clausen 3 Internet-Draft A. Colin de Verdiere 4 Intended status: Standards Track J. Yi 5 Expires: April 26, 2012 LIX, Ecole Polytechnique 6 C. Lavenu 7 EDF R&D 8 T. Lys 9 ERDF 10 A. Niktash 11 Maxim Integrated Products 12 Y. Igarashi 13 SATOH. H. 14 Hitachi, Ltd., Yokohama Research 15 Laboratory 16 October 24, 2011 18 The LLN On-demand Ad hoc Distance-vector Routing Protocol - Next 19 Generation (LOADng) 20 draft-clausen-lln-loadng-00 22 Abstract 24 This document describes the LLN Ad hoc On-Demand (LOAD) distance 25 vector routing protocol, a reactive routing protocol intended for use 26 in Low power Lossy Networks (LLN). The protocol is derived from AODV 27 and extended for use in LLNs. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on April 26, 2012. 46 Copyright Notice 48 Copyright (c) 2011 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 This document may contain material from IETF Documents or IETF 62 Contributions published or made publicly available before November 63 10, 2008. The person(s) controlling the copyright in some of this 64 material may not have granted the IETF Trust the right to allow 65 modifications of such material outside the IETF Standards Process. 66 Without obtaining an adequate license from the person(s) controlling 67 the copyright in such materials, this document may not be modified 68 outside the IETF Standards Process, and derivative works of it may 69 not be created outside the IETF Standards Process, except to format 70 it for publication as an RFC or to translate it into languages other 71 than English. 73 Table of Contents 75 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 76 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 77 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 78 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 79 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 6 80 4.2. Routers and Interfaces . . . . . . . . . . . . . . . . . . 7 81 4.3. Information Base Overview . . . . . . . . . . . . . . . . 7 82 4.4. Signaling Overview . . . . . . . . . . . . . . . . . . . . 8 83 5. Protocol Parameters and Constants . . . . . . . . . . . . . . 9 84 6. Information Base . . . . . . . . . . . . . . . . . . . . . . . 10 85 6.1. Routing Set . . . . . . . . . . . . . . . . . . . . . . . 10 86 6.2. Blacklisted Neighbor Set . . . . . . . . . . . . . . . . . 11 87 6.3. Destination Address Set . . . . . . . . . . . . . . . . . 11 88 6.4. Pending Acknowledgment Set . . . . . . . . . . . . . . . . 12 89 7. LOADng Router Sequence Numbers . . . . . . . . . . . . . . . . 12 90 8. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . 13 91 8.1. TLV Block . . . . . . . . . . . . . . . . . . . . . . . . 13 92 8.2. Message Format . . . . . . . . . . . . . . . . . . . . . . 14 93 8.2.1. RREQ and RREP Message Format . . . . . . . . . . . . . 14 94 8.2.2. RREP-ACK Message Format . . . . . . . . . . . . . . . 16 95 8.2.3. RERR Message Format . . . . . . . . . . . . . . . . . 16 96 9. Route Maintenance . . . . . . . . . . . . . . . . . . . . . . 17 97 10. Unidirectional links handling . . . . . . . . . . . . . . . . 18 98 10.1. Blacklist usage . . . . . . . . . . . . . . . . . . . . . 19 99 11. Common rules for RREQ and RREP Messages . . . . . . . . . . . 19 100 11.1. Identifying Invalid RREQ or RREP Messages . . . . . . . . 20 101 11.2. RREQ and RREP Message Processing . . . . . . . . . . . . . 21 102 11.3. Updating Routing Tuples In Response to RREQ and RREP . . . 22 103 12. Route Requests (RREQs) . . . . . . . . . . . . . . . . . . . . 22 104 12.1. RREQ Generation . . . . . . . . . . . . . . . . . . . . . 23 105 12.2. RREQ Processing . . . . . . . . . . . . . . . . . . . . . 23 106 12.3. RREQ Forwarding . . . . . . . . . . . . . . . . . . . . . 24 107 12.4. RREQ Transmission . . . . . . . . . . . . . . . . . . . . 24 108 13. Route Replies (RREPs) . . . . . . . . . . . . . . . . . . . . 24 109 13.1. RREP Generation . . . . . . . . . . . . . . . . . . . . . 25 110 13.2. RREP Processing . . . . . . . . . . . . . . . . . . . . . 26 111 13.3. RREP Forwarding . . . . . . . . . . . . . . . . . . . . . 26 112 13.4. RREP Transmission . . . . . . . . . . . . . . . . . . . . 26 113 14. Route Errors (RERRs) . . . . . . . . . . . . . . . . . . . . . 27 114 14.1. RERR Generation . . . . . . . . . . . . . . . . . . . . . 27 115 14.2. RERR Processing . . . . . . . . . . . . . . . . . . . . . 27 116 14.3. RERR Forwarding . . . . . . . . . . . . . . . . . . . . . 28 117 14.4. RERR Transmission . . . . . . . . . . . . . . . . . . . . 28 118 15. Route Reply Acknowledgements (RREP-ACKs) . . . . . . . . . . . 29 119 15.1. RREP-ACK Generation . . . . . . . . . . . . . . . . . . . 29 120 15.2. RREP-ACK Processing . . . . . . . . . . . . . . . . . . . 29 121 15.3. RREP-ACK Forwarding . . . . . . . . . . . . . . . . . . . 30 122 15.4. RREP-ACK Transmission . . . . . . . . . . . . . . . . . . 30 123 16. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 124 16.1. The Default <= Comparison Operator . . . . . . . . . . . . 30 125 16.2. Specifying New Metrics . . . . . . . . . . . . . . . . . . 31 126 16.3. Example Metric: Hop Count . . . . . . . . . . . . . . . . 31 127 16.3.1. Simple Hop Count . . . . . . . . . . . . . . . . . . . 32 128 17. Security Considerations . . . . . . . . . . . . . . . . . . . 32 129 18. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32 130 18.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 32 131 18.2. Packet Types . . . . . . . . . . . . . . . . . . . . . . . 32 132 18.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 33 133 18.4. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 33 134 18.5. Error Codes . . . . . . . . . . . . . . . . . . . . . . . 34 135 19. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 34 136 20. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 35 137 21. References . . . . . . . . . . . . . . . . . . . . . . . . . . 35 138 21.1. Normative References . . . . . . . . . . . . . . . . . . . 35 139 21.2. Informative References . . . . . . . . . . . . . . . . . . 35 140 Appendix A. LOADng Control Packet Illustrations . . . . . . . . . 36 141 A.1. RREQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 142 A.2. RREP . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 143 A.3. RREP-ACK . . . . . . . . . . . . . . . . . . . . . . . . . 36 144 A.4. RERR . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 146 1. Introduction 148 The LLN On-demand Ad hoc Distance-vector Routing Protocol - Next 149 Generation (LOADng) is a routing protocol, derived from AODV 150 [RFC3561] and extended for use in Low power Lossy Networks (LLNs). 151 As a reactive protocol, the basic operations of LOADng include 152 generation of Route Requests (RREQs) by a router (originator) for 153 when discovering a route to a destination, forwarding of such RREQs 154 until they reach the destination router, generation of Route Replies 155 (RREPs) upon receipt of a RREQ by the indicated destination, and 156 unicast hop-by-hop forwarding of these RREPs towards the originator. 157 If a route is detected broken, i.e., if forwarding of a data packet 158 to the recorded next hop on the route to the destination is detected 159 to fail, local route repair can be attempted, or a Route Error (RERR) 160 message can be returned to the originator of that data packet. 162 Compared to [RFC3561], LOADng is simplified as follows: 164 o Only the destination is permitted to respond to a RREQ; 165 intermediate routers are explicitly prohibited from responding to 166 RREQs, even if they may have active routes to the sought 167 destination, and all messages (RREQ or RREPs) generated by a given 168 router share a single unique, monotonically increasing sequence 169 number. This also eliminates Gratuitous RREPs while ensuring loop 170 freedom. The rationale for this simplification is reduced 171 complexity of protocol operation and reduced message sizes. 173 o A LOADng router does not maintain a precursor list, thus when 174 forwarding of a data packet to the recorded next hop on the route 175 to the destination fails, a RERR is sent only to the originator of 176 that data packet. The rationale for this simplification is an 177 assumption that few overlapping routes are in use concurrently in 178 a given network. 180 Compared to [RFC3561], LOADng is extended as follows: 182 o Optimized Flooding is supported, reducing the overhead incurred by 183 RREQ generation and flooding. 185 o Different address lengths are supported - from full 16 octet IPv6 186 addresses over 6 octet Ethernet MAC addresses and 4 octet IPv4 187 addresses to shorter 1 and 2 octet addresses. The only 188 requirement is, that within a given routing doamin, all addresses 189 are of the same address length. 191 o Control messages can include TLV (Type-Length-Value) elements, 192 permitting protocol extensions to be developed. 194 2. Terminology 196 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 197 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 198 "OPTIONAL" in this document are to be interpreted as described in 199 [RFC2119]. 201 Additionally, this document uses the following terminology: 203 LOADng Router - A router which implements this routing protocol. 205 Link Cost - The cost (weight) between a pair of LOADng Routers, 206 determined by a LOADng router upon receipt of a packet. 208 Route Cost - The sum of the Link Costs for the links that a RREQ or 209 RREP has crossed. 211 Weak Link - A link which is marginally usable, i.e., which MAY be 212 used if no other links are available, but which SHOULD be avoided 213 if at all possible - even if it entails ultimately longer routes. 214 As an example, a Weak Link might be defined as a link with a 215 nominatively high bit-rate (thus, a priori attractive) while 216 suffering a significant loss-rate. 218 This document uses the following notational conventions: 220 a := b An assignment operator, whereby the left side (a) is assigned 221 the value of the right side (b). 223 c = d A comparison operator, returning true if the value of the left 224 side (c) is equal to the value of the right side (d). 226 3. Applicability Statement 228 This protocol: 230 o Is a reactive routing protocol for Low power and Lossy Networks 231 (LLNs). 233 o Supports the use of optimized flooding for RREQs. 235 o Enables any router in the LLN to discover bi-directional routes to 236 any other router in the LLN. 238 o Supports addresses of any length, from 16 octets to a single 239 octet. 241 o Is layer-agnostic, i.e., may be used at layer 3 as a "route over" 242 routing protocol, or at layer 2 as a "mesh under" routing 243 protocol. 245 o Supports per-route maintenance; if a destination becomes 246 unreachable, rediscovery of that single (bi-directional) route is 247 performed, without need for global topology recalculation. 249 4. Protocol Overview and Functioning 251 The objective of this protocol is for each LOADng router to, 252 independently: 254 o Discover a bi-directional route to any destination in the network. 256 o Establish routes only when there is data traffic to be sent along 257 that route. 259 o Maintain a route only for as long as it is an active route, i.e., 260 there is traffic using the route. 262 o Generate control traffic based on network events only: when a new 263 route is required, or when an active route is detected broken. 264 Specifically, this protocol does not require periodic signaling. 266 4.1. Overview 268 These objectives are achieved, for each LOADng router, by: 270 o When having a data packet to deliver to a destination, for which 271 no entry in the routing table exists, generating a Route Request 272 (RREQ) encoding the destination address, and transmitting this to 273 all of its neighbors. 275 o Upon receiving an RREQ, install or refresh an entry in the routing 276 table towards the originator address from the RREQ, as well as to 277 the neighbor LOADng router from which the RREQ was received. This 278 will install the Reverse Route (towards the originator address 279 from the RREQ). 281 o Upon receiving a RREQ, inspect the indicated destination address: 283 * If that address is an address in the Destination Address Set of 284 the LOADng router, generate a Route Reply (RREP), which is 285 unicast in a hop-by-hop fashion along the installed Reverse 286 Route. 288 * If that address is not an address in the Destination Address 289 Set of the LOADng router, consider the RREQ as a candidate for 290 forwarding. 292 o When a RREQ is considered a candidate for forwarding, retransmit 293 it according to the flooding operation specified for the network. 295 o Upon receiving a RREP, install a route towards the originator 296 address from the RREP, as well as to the neighbor LOADng router, 297 from which that RREP was received. This will install the Forward 298 Route (towards the originator address from the RREP). 300 o Upon receiving a RREP, forward it, as unicast, to the recorded 301 next hop along the corresponding Reverse Route until the RREP gets 302 to the LOADng router which has the destination address from the 303 RREP in its Destination Address Set. 305 4.2. Routers and Interfaces 307 In order for a LOADng router to participate in a LLN, it MUST have at 308 least one, and possibly more, LOADng interfaces. Each LOADng 309 interface: 311 o Is configured with one or more interface addresses. 313 In addition to a set of LOADng interfaces as described above, each 314 LOADng router: 316 o Has a number of router parameters. 318 o Has an Information Base. 320 o Generates and processes RREQ, RREP, RREP-ACK and RERR messages. 322 4.3. Information Base Overview 324 Necessary protocol state is recorded by way of four information sets: 325 the "Routing Set", the "Blacklisted Neighbor Set", the "Destination 326 Address Set", and the "Pending Acknowledgement Set". 328 The Routing Set contains tuples, representing next-hop, distance 329 towards a destination address and the sequence number, all extracted 330 from the message (RREQ or RREP) that generated the tuple so as to 331 enable routing. The routing table is to be updated using this 332 Routing Set. (A router MAY choose to use any or all destination 333 addresses in the Routing Set to update the routing table, this 334 selection is outside the scope of this specification.) 335 The Blacklisted Neighbor Set contains tuples representing neighbor 336 LOADng routers with which unidirectional connectivity has been 337 detected. 339 The Destination Address Set containts tuples, representing the 340 addresses for which the LOADng is able to generate RREPs, i.e., the 341 Destination Address Set records addresses of this LOADng router and 342 of hosts and networks directly attached to this LOADng router and for 343 which this LOADng router provides connectivity in the LLN. 345 The Pending Acknowledgement Set contains tuples, representing 346 transmitted RREPs for which an RREP-ACK is expected, but where this 347 RREP-ACK has not yet been received. 349 The Routing Set and the Blacklisted Neigbor Set is updated by this 350 protocol. The Destination Address Set is used, but not updated, by 351 this protocol. 353 4.4. Signaling Overview 355 This protocol generates and processes the following routing messages: 357 Route Request (RREQ) - Generated by a LOADng router when it has a 358 data packet to deliver to a given destination, but when it does 359 not have an entry in its Routing Set indicating a route to that 360 destination. A RREQ contains: 362 * The address (destination) to which a Forward Route is to be 363 discovered by way of soliciting the LOADng router with that 364 destination address in its Destination Address Set to generate 365 a RREP. 367 * The address for which a Reverse Route is to be installed 368 (originator) by RREQ forwarding and processing. 370 * The sequence number of the LOADng router, generating the RREQ. 372 A RREQ is flooded through the network, possibly employing an 373 optimized flooding mechanism. 375 Route Reply (RREP) - Generated as a response to a RREQ by the LOADng 376 router which has the address (destination) from the RREQ in its 377 Destination Address Set. A RREP is sent in unicast towards the 378 originator of that RREQ. A RREP contains: 380 * The address (originator) to which a Forward Route is to be 381 installed when forwarding the RREP. 383 * The address (destination) towards which the RREP is to be sent. 384 More precisely, the destination address indicates the unicast 385 route which the RREP follows. 387 * The sequence number of the LOADng router, generating the RREP. 389 Route Reply Acknowledgement (RREP-ACK) - Generated by a LOADng 390 router as a response to a RREP, in order to signal to the neighbor 391 which transmitted the RREP that the RREP was succesfully received. 392 Receipt of an RREP-ACK indicates that the link between these two 393 neighboring LOADng routers is bidirectional. A RREP-ACK is 394 unicast to the neighbor from which the RREP has arrived, and is 395 not forwarded. RREP-ACKs are generated only in response to an 396 RREP which, by way of a flag, has explicitly indicated that an 397 RREP-ACK is desired. 399 Route Error (RERR) - Generated by a LOADng router when a link on an 400 active route to a destination is detected as broken by way of 401 inability to forward a data packet towards that destination. A 402 RERR is unicast to the source of the undeliverable data packet. 404 5. Protocol Parameters and Constants 406 The parameters and constants used in this specification are: 408 LL-LLN-Routers is a link-local-scoped multicast address of a group, 409 which all LOADng routers MUST join. 411 NET_TRAVERSAL_TIME is the maximum expected time that a packet takes 412 to transverse from one end of the network to the other. 414 RREQ_RETRIES is the maximum number of subsequent RREQs that a 415 particular router may generate in order to discover a route to a 416 destination, before declaring that destination unreachable. 418 RREQ_RATELIMIT is the maximum number of RREQ that a particular 419 router is allowed to send per second. 421 R_HOLD_TIME is the minimum time a Routing Entry SHOULD be kept in 422 the Routing Set after it was last refreshed. This MAY be a 423 network-wide constant, but MAY also be a variable whose value is 424 defined by an auxiliary mechanism, e.g., in an extension to this 425 protocol. 427 MAX_DIST is the value (tuple) representing the maximum possible 428 distance (R_dist field). 430 RREP_ACK_TIMEOUT is the minimum time after transmission of a 431 RREP_ACK, that a LOADng router SHOULD wait for a RREP_ACK from a 432 neighbor LOADng router, before considering that the link to this 433 neighbor as unidirectional. 435 BLACKLIST_TIME is the time during which the link between the 436 neighbor LOADng router and this LOADng router MUST be considered 437 as non-bidirectional, and that therefore RREQs received from that 438 neighbor LOADng router MUST be ignored) after being added. 439 BLACKLIST_TIME should be greater than 2 x NET_TRANSVERSAL_TIME, to 440 ensure that subsequent RREQs will reach the destination via a 441 route excluding this link. 443 6. Information Base 445 Each LOADng router maintains an Information Base, containing the 446 information sets necessary for protocol operation, as described in 447 the following sections. The organization of information into these 448 information sets is non-normative, given so as to facilitate 449 description of message generation, forwarding and processing rules in 450 this specification. An implementation may choose any representation 451 or structure for when maintaining this information. 453 6.1. Routing Set 455 The Routing Set records the next hop on the route to each known 456 destination, when such a route is known. It consists of Routing 457 Tuples: 459 (R_dest_addr, R_next_addr, R_dist, R_metric, R_seq_num, R_valid_time) 461 where: 463 R_dest_addr - is the address of the destination, either the address 464 of an interface of a destination LOADng router, or the address of 465 an interface reachable via the destination LOADng router, but 466 which is outside the LLN; 468 R_next_addr - is the address of the "next hop" on the selected route 469 to the destination; 471 R_dist - is the distance associated with the selected route to the 472 destination with address R_dest_addr. R_dist is a tuple 473 containing Route Cost, Weak Links and (depending on the metric 474 used) additional fields; see Section 16. 476 R_metric - specifies how R_dist is defined and calculated, as well 477 as the comparison operator '<=' for determining which of two route 478 costs is lower. This is specified in Section 16; 480 R_seq_num - is the value of the field of the RREQ or RREP 481 which installed or last updated this tuple. For the routing 482 tuples installed by previous hop information of RREQ or RREP, 483 R_seq_num MUST be set to -1. 485 R_valid_time - specifies the time until which the information 486 recorded in this tuple is considered valid. 488 6.2. Blacklisted Neighbor Set 490 The Blacklisted Neighbor Set records the neighbors of a LOADng 491 router, with which connectivity has been detected to be 492 unidirectional. Specifically, the Blacklisted Neighbor Set records 493 neighbors from which a RREQ has been received (i.e., through which a 494 Forward Route would possible) but to which it has been determined 495 that it is not possible to communicate (i.e., forwarding Route 496 Replies via this neighbor fails, rendering installing the Forward 497 Route impossible). It consists of blacklist tuples: 499 (B_neighbor_address, B_valid_time) 501 where: 503 B_neighbor_address - is the address of the blacklisted neighbor; 505 B_valid_time - specifies the time until which the information 506 recorded in this tuple is considered valid. 508 6.3. Destination Address Set 510 The Destination Address Set records addresses, for which a LOADng 511 router will generate RREPs in response to received RREQs. The 512 Destination Address Set thus represents those destinations (hosts or 513 external networks, or addresses of the LOADng router), for which this 514 LOADng router is providing connectivity. It consists of destination 515 address tuples: 517 (D_address) 519 where: 521 D_address - is the address of a destination (a host or a network), 522 attached to this LOADng router and for which this LOADng router 523 provides connectivity through the LLN. 525 The Destination Address Set is used for generating signaling, but is 526 not itself updated by signaling specified in this document. Updates 527 to the Destination Address Set are due to changes of the environment 528 of a LOADng router - hosts or external networks being connected to or 529 disconnected from a LOADng router. The Destination Address Set may 530 be administrationally provisioned, or provisioned by external 531 protocols. 533 6.4. Pending Acknowledgment Set 535 The Pending Acknowledgements Set contains RREPs which have been 536 transmitted with the ACK_REQUIRED flag set, and for which a RREP-ACK 537 has not yet been received. It consists of Pending Acknowledgment 538 Tuples: 540 (P_next_hop, P_originator, P_seq_num, P_ack_timeout) 542 where: 544 P_next_hop - is the address of the neighbor to which the RREP was 545 sent; 547 P_originator - is the address of the originator of the RREP; 549 P_seq_num - corresponds to the field of the sent RREP; 551 P_ack_timeout - is the time after which the neighbor is considered 552 not to have a bidirectional link to this router and SHOULD be 553 added to the blacklist; the tuple SHOULD then be discarded. 555 7. LOADng Router Sequence Numbers 557 Each LOADng router maintains a single sequence number, which must be 558 included in each RREQ or RREP message it generates. Each router MUST 559 make sure that no two messages (both RREQ and RREP) are generated 560 with the same sequence number, and MUST generate sequence number such 561 that these are monotonically increasing. This sequence number is 562 used as freshness information for when comparing routes to the router 563 having generated the message. 565 However, with a limited number of bits for representing sequence 566 numbers, wrap-around (that the sequence number is incremented from 567 the maximum possible value to zero) will occur. To prevent this from 568 interfering with the operation of the protocol, the following MUST be 569 observed. The term MAXVALUE designates in the following the largest 570 possible value for a sequence number. The sequence number S1 is said 571 to be "greater than" (denoted '>') the sequence number S2 if: 573 S2 < S1 AND S1 - S2 <= MAXVALUE/2 OR 575 S1 < S2 AND S2 - S1 > MAXVALUE/2 577 8. Packet Format 579 The packet format, used by this protocol, is described in this 580 section using the notational conventions from [RFC5444]. Example 581 packets are illustrated in Appendix A. 583 This format uses network byte order (most significant octet first) 584 for all fields. The most significant bit in an octet is numbered bit 585 0, and the least significant bit of an octet is numbered bit 7 586 [Stevens]. 588 The general format for all packets, generated, forwarded and 589 processed by this specification, is as follows: 591 := 592 593 595 where: 597 is a 4 bit unsigned integer field and specifies the type of 598 the field, specified in Section 8.2. 600 is specified in Section 8.1. 602 is specified in Section 8.2. 604 8.1. TLV Block 606 The TLV Block contains zero or more Type-Length-Value elements 607 (TLVs). A TLV allows the association of an arbitrary attribute with 608 a packet. The attribute (value) is made up from an integer number of 609 consecutive octets. Different attributes have different types; 610 attributes which are unknown when parsing can be skipped, as 611 specified by flags associated with a given TLV. 613 := 614 ()* 616 where: 618 is a 4 bit unsigned integer field, specifying the number 619 of TLVs included. 621 is a 4 bit unsigned integer field, specifying the type of 622 the TLV. 624 is a 4 bit field specifying processing and forwarding 625 rules related to the TLV processing: 627 bit 0-3 (RESERVED): SHOULD be set to zero on transmission and 628 SHOULD be ignored upon reciept. 630 is an 8 bit unsigned integer field, specifying the 631 length of the following field. 633 is a field of length octets. 635 8.2. Message Format 637 This section specifies the format of the field for message 638 types RREQ, RREP,RREP-ACK and RERR. 640 8.2.1. RREQ and RREP Message Format 642 The format of Route Request (RREQ) and Route Reply (RREP) messages is 643 identical, RREQ and RREP messages being distinguished by the 644 field in the packet. They are as follows: 646 := 647 648 649 650 651 652 653 655 where: 657 is a 4 bit unsigned integer field and specifies the 658 interpretation of the remainder of the message. 660 For RREQ messages: 662 bit 0-3 (RESERVED): SHOULD be set to zero on transmission and 663 SHOULD be ignored upon reciept. 665 For RREP messages: 667 bit 0 (ackrequired): When set ('1'), a RREP-ACK MUST be 668 generated by the recipient of an RREP if the RREP is 669 successfully processed. When cleared ('0'), a RREP-ACK MUST 670 NOT be generated in response to processing of the RREP. 672 bit 1-3 (RESERVED): SHOULD be set to zero on transmission and 673 SHOULD be ignored upon reciept. 675 is a 4 bit unsigned integer field, encoding the length 676 of the destination and originator addresses ( and 677 ) as follows: 679 := the length of an address in octets - 1 681 is thus 1 for 16-bit short addresses [RFC4944], 3 682 for IPv4 addresses, 7 for 64-bit extended addresses [RFC4944] or 683 15 for IPv6 addresses. 685 is a 16 bit unsigned integer field, containing the 686 sequence number (see Section 7) of the LOADng router, generating 687 the RREQ or RREP messages. 689 is a 4 bit unsigned integer field and specifies how the 690 value of the field is calculated, as well as the 691 comparison operator '<=' used for when determining which from 692 among two route costs is lower. 694 is a 4 bit unsigned integer field and specifies the 695 total number of weak links on the route from the originator to the 696 destination. 698 is an 8 bit unsigned integer field and specifies the 699 cost of the route from the to the . 701 is an identifier of + 1 octets, 702 specifying the address to which the RREQ or RREP should be sent. 703 For a RREQ, this address would be the address for which a route is 704 sought. For a RREP, this address is an unicast address of the 705 router, which originated the RREQ triggering the RREP. 707 is an identifier of + 1 octets, 708 specifying the address of the router which generated this message, 709 and to which a route is supplied by this message. For a RREQ, the 710 route supplied corresponds to the "reverse route", whereas for a 711 RREP the route supplied corresponds to the "forward route". 713 8.2.2. RREP-ACK Message Format 715 The format of a Route Reply Acknowledgement (RREP-ACK) message is as 716 follows: 718 := 719 720 721 723 where: 725 is a 4 bit unsigned integer field and specifies the 726 interpretation of the remainder of the message: 728 bit 0-3 (RESERVED): SHOULD be set to zero on transmission and 729 SHOULD be ignored upon reciept. 731 is a 4 bit unsigned integer field, encoding the length 732 of the destination and originator addresses ( and 733 ) as follows: 735 := the length of an address in octets - 1 737 is thus 1 for 16-bit short addresses [RFC4944], 3 738 for IPv4 addresses, 7 for 64-bit extended addresses [RFC4944] or 739 15 for IPv6 addresses. 741 is an 16 bit unsigned integer field and contains the value 742 of the field from the RREP for which this RREP-ACK is 743 sent. 745 is an identifier of + 1 octets, 746 specifying the address of the originator which has originated the 747 RREP identified by . 749 8.2.3. RERR Message Format 751 The format of a Route Error (RERR) message is as follows: 753 := 754 755 756 758 where: 760 is a 4 bit unsigned integer field and specifies the 761 reason for the error message being generated, according to 762 Table 4. 764 is a 4 bit unsigned integer field, encoding the length 765 of the destination and source addresses ( and 766 ) as follows: 768 := the length of an address in octets - 1 770 is thus 1 for 16-bit short addresses [RFC4944], 3 771 for IPv4 addresses, 7 for 64-bit extended addresses [RFC4944] or 772 15 for IPv6 addresses. 774 is an identifier of + 1 octets, specifying 775 the source address of a data packet, for which delivery to 776 failed. The LOADng router with this address is the 777 ultimate target for the RERR message. 779 is an identifier of + 1 octets, 780 specifying the address of the destination, which has become 781 unreachable, and for which an error is reported. 783 9. Route Maintenance 785 Entries in the Routing Set are maintained by way of four different 786 mechanisms: 788 o RREQ/RREP exchange, as described in Section 12 and Section 13. 790 o Data traffic delivery success. 792 o Data traffic delivery failure. 794 o External signals indicating that an entry in the Routing Set 795 necessitates updating. 797 o Information expiration. 799 Routing Tuples in the Routing Set contain a validity time, which 800 specifies the time until which the information recorded in this tuple 801 is considered valid. After this time, the information in such tuples 802 is to be considered as invalid, for the processing specified in this 803 document. 805 Routing Tuples for actively used routes (i.e., a route via which 806 traffic is currently transiting) SHOULD NOT be removed, unless there 807 is evidence that they no longer provide connectivity - i.e., unless a 808 link on that route has broken. 810 To this end, one or more of the following mechanisms (non-exhaustive 811 list) MAY be used: 813 o If a lower layer mechanism provides signals, such as when delivery 814 to a presumed neighbor LOADng router fails, this signal MAY be 815 used to indicate that a link has broken, trigger early expiration 816 of a Routing Tuple from the Routing Set, and to initiate Route 817 Repair (see Section 13) or Route Error Signaling (see Section 14). 818 Conversely, absence of such a signal when attempting delivery MAY 819 be interpreted as validation that the corresponding Routing 820 Tuple(s) are valid, and their R_valid_time refreshed 821 correspondingly. 823 o Conversely, for each successful delivery of a packet to a presumed 824 neighbor or a destination, if signaled by a lower layer or a 825 transport mechanism, or each positive confirmation of the presence 826 of a neighbor by way of an external neighbor discovery protocol, 827 MAY be interpreted as validation that the corresponding Routing 828 Tuple(s) are valid, and their R_valid_time refreshed 829 correspondingly. 831 Furthermore, a LOADng router may experience that a route currently 832 used for forwarding data packets is no longer operational, and must 833 act to either rectify this situation locally (Section 13) or signal 834 this situation to the source of the data packets for which delivery 835 was unsuccessful (Section 14). 837 10. Unidirectional links handling 839 Each LOADng router MUST monitor the bidirectionality of the links to 840 its neighbors when processing Route Replies (RREP). To this end, one 841 or more of the following mechanisms MAY be used (non exhaustive 842 list): 844 o If a lower layer mechanism provides signals, such as when delivery 845 to a presumed neighbor LOADng router fails, this signal MAY be 846 used to detect that a link to this neighbor is broken or 847 unidirectional; the LOADng router SHOULD then blacklist the 848 neighbor, see Section 10.1 850 o If a mechanism such as NDP [RFC4861] is available, the LOADng 851 router MAY use it; 853 o RREP-ACK message exchange, as described in Section 15 855 o Upper-layer mechanisms, such as transport-layer acknowledgements, 856 MAY be used to detect unidirectional or broken links. 858 When a LOADng router detects, via one of these mechanisms, that a 859 link to a LOADng neighbor router is unidirectional or broken, the 860 router SHOULD blacklist this neighbor, see Section 10.1. Conversely, 861 if a LOADng router detects via one of these mechanisms that a 862 previously blacklisted LOADng router has a bidirectional link to this 863 router, it MAY remove it from the blacklist before the 864 of the corresponding tuple. 866 10.1. Blacklist usage 868 The Blacklist is maintained according to Section 6.2. When a LOADng 869 router is detected to have a unidirectional link to the LOADng router 870 by means of a chosen mechanism, it is blacklisted, i.e. a tuple 871 (B_neighbor_address, B_valid_time) is added to the list, such as: 873 o B_neighbor_address is the address of the blacklisted neighbor; 875 o B_valid_time := current_time + BLACKLIST_TIME 877 When a LOADng neighbor router is blacklisted, i.e. when there is a 878 corresponding (neighbor_address, B_valid_time) tuple in the 879 Blacklist, it is temporarily not considered as a neighbor, and thus: 881 o Every RREQ received from this neighbor SHOULD be discarded; 883 o If the LOADng router needs to establish a route to this neighbor, 884 it SHOULD initiate a new route discovery by generating a RREQ 885 towards the blacklisted neighbor. 887 11. Common rules for RREQ and RREP Messages 889 RREQ and RREP messages, both, supply routes between their recipients 890 and the originator of the RREQ or RREP message. The two message 891 types therefore share common processing rules, and differ only in the 892 following: 894 o RREQ messages are multicast or broadcast, intended to be received 895 by all LOADng routers in the network, whereas RREP messages are 896 all unicast, intended to be received only by routers on a specific 897 route towards a specific destination. 899 o Receipt of a RREQ message MAY trigger generation of a RREP 900 message. 902 o Receipt of a RREP message MAY trigger generation of a RREP-ACK 903 message. 905 For the purpose of the processing description in this section, the 906 following additional notation is used: 908 <= is the comparison operator specified by the indicated in 909 the RREQ or RREP message and described in Section 16. 911 previous-hop is the address of the LOADng router, from which the 912 RREQ or RREP message was received. 914 > is the comparison operator for specified in Section 8. 916 11.1. Identifying Invalid RREQ or RREP Messages 918 A received RREQ or RREP message is invalid, and MUST be discarded 919 without further processing, if any of the following conditions are 920 true: 922 o The address contained in the field is an address of 923 this router; 925 o There is a tuple in the Routing Set where: 927 * R_dest_addr = 929 * R_seq_num > 931 o The metrics type contained in the field of the RREQ or 932 RREP message is different from the metrics type used by the 933 interface of this router on which the RREQ or RREP message was 934 received, or some TLVs required by the metric type are absent from 935 the received RREQ or RREP message; 937 o Furthermore, for RREQ messages only, a RREQ SHOULD be considered 938 invalid if the previous-hop is blacklisted (i.e. its address is in 939 a tuple in the Blacklist, see Section 10.1) 941 A LOADng router MAY recognize additional reasons for identifying that 942 a RREQ or RREP message is invalid for processing, e.g., to allow a 943 security protocol to perform verification of signatures and prevent 944 processing of unverifiable RREQ or RREP message by this protocol. 946 11.2. RREQ and RREP Message Processing 948 A received and not invalid RREQ or RREP message is processed as 949 follows: 951 1. The TLV fields included in the TLV block are added/removed/ 952 updated according to their specification. 954 2. If the RREQ or RREP message was received over a "weak link", 955 increment the field in the received RREQ or RREP by 956 one. 958 3. Find the Routing Tuple (henceforth, matching Routing Tuple) 959 where: 961 * R_dest_addr = 963 4. If no matching Routing Tuple is found, then create a new matching 964 Routing Tuple (the "reverse route" for RREQ messages or "forward 965 route" for RREP messages) with: 967 * R_dest_addr := 969 * R_next_addr := previous-hop 971 * R_dist := MAX_DIST 973 * R_seq_num := -1 975 * R_valid_time := current time + R_HOLD_TIME 977 5. The matching Routing Tuple, existing or new, is compared to the 978 received RREQ or RREP message: 980 1. If 982 + (, , ()*) <= R_dist; AND 984 + R_seq_num = 986 OR 988 + > R_seq_num 990 Then: 992 + The message is used for updating the Routing Set according 993 to Section 11.3. 995 + If there is no matching Routing Tuple in the Routing Set 996 with R_dest_addr = previous-hop, create a new matching 997 Routing Tuple with: 999 - R_dest_addr := previous-hop 1001 - R_next_addr := previous-hop 1003 - R_dist := MAX_DIST 1005 - R_seq_num := -1 1007 - R_valid_time = current time + R_HOLD_TIME 1009 2. Otherwise, the RREQ or RREP message is not processed further, 1010 and is not considered for forwarding. 1012 11.3. Updating Routing Tuples In Response to RREQ and RREP 1014 A Routing Tuple in the routing set is updated when a received RREQ or 1015 RREP message provides a better route to the than the 1016 route current recorded in that Routing Tuple. The Routing set is 1017 updated thus: 1019 o R_next_addr := previous-hop 1021 o R_dist := (, , ()*); the TLVs used 1022 are defined by the included in the RREQ or RREP message. 1024 o R_seq_num := 1026 o R_valid_time := current time + R_HOLD_TIME 1028 12. Route Requests (RREQs) 1030 Route Requests (RREQs) are generated by a LOADng router, when it has 1031 data packets to deliver to a destination for which it has no matching 1032 entry in the Routing Set. The RREQ is transmitted to all directly 1033 reachable neighbor LOADng routers. 1035 After originating a RREQ, a LOADng router waits for a corresponding 1036 RREP. If no such RREP is received within 2*NET_TRAVERSAL_TIME 1037 milliseconds, the LOADng router MAY issue a new RREQ for the sought 1038 destination (with an incremented seq_num) up to a maximum of 1039 RREQ_RETRIES times. A LOADng router SHOULD NOT originate more than 1040 RREQ_RATELIMIT RREQs per second. A LOADng router MAY use mechanisms 1041 such as exponential backoff to determine the rate at which it 1042 originates RREQs. 1044 12.1. RREQ Generation 1046 A RREQ packet is generated according to Section 8.2 with the 1047 following content: 1049 o := RREQ; 1051 o the TLV block, containing the TLVs needed; 1053 o set to the length of the address, as specified in 1054 Section 8; 1056 o set to indicate how route costs are to be calculated and 1057 compared, according to Table 3; 1059 o := 0; 1061 o set to the next unused sequence number, maintained by 1062 this router; 1064 o := the cost associated with the interface over which 1065 the RREQ is transmitted, and according to the specification of the 1066 included in the RREQ, see Section 16; 1068 o := the address to which a route is sought; 1070 o := the address of the LOADng router, generating the 1071 RREQ. 1073 12.2. RREQ Processing 1075 On receiving a RREQ message, a LOADng router must process the message 1076 according to this section: 1078 1. If the message is invalid for processing, as defined in 1079 Section 11.1, the message MUST be discarded without further 1080 processing. The message is not considered for forwarding. 1082 2. Otherwise, the message is processed according to Section 11.2. 1084 3. If in the RREQ message does not correspond to an 1085 address of of this LOADng router, then the message is considered 1086 for forwarding according to Section 12.3. 1088 4. If in the RREQ message corresponds to an address of 1089 this LOADng router, then an RREP can be generated, see 1090 Section 13.1. The RREQ is not considered for forwarding. 1092 12.3. RREQ Forwarding 1094 A Route Request (RREQ), considered for forwarding, MUST be updated as 1095 follows, prior to it being transmitted: 1097 1. The field must be updated according to the cost 1098 associated with the interface over which the RREQ is transmitted, 1099 and according to the specification of the included in 1100 the RREQ, see Section 16. 1102 RREQ forwarding MAY be undertaken using classic flooding, may employ 1103 a reduced relay set mechanism such as [SMF] or any other information 1104 diffusion mechanism such as [RFC6206]. Care must be taken that 1105 NET_TRAVERSAL_TIME is chosen so as to accommodate for the maximum 1106 time that may take for a RREQ to transverse the network, accounting 1107 for in-router delays incurring due to or imposed by such algorithms. 1109 12.4. RREQ Transmission 1111 RREQs, initially generated or forwarded, are sent to all neighbor 1112 LOADng routers. If LOADng is operating as an IP routing protocol, 1113 the destination address for this RREQ MUST be the link local 1114 multicast address LL-LLN-Routers, and the source address MUST be the 1115 address of the interface over which the RREQ is sent. 1117 When a RREQ is transmitted, all receiving LOADng routers will process 1118 the RREQ message and MAY consider the RREQ message for forwarding at 1119 the same, or at almost the same, time. If using data link and 1120 physical layers that are subject to packet loss due to collisions, 1121 such RREQ messages SHOULD be jittered as described in [RFC5148]. 1123 13. Route Replies (RREPs) 1125 Route Replies (RREPs) are generated by a LOADng router in response to 1126 a RREQ where the corresponds to one of that LOADng 1127 router's addresses. RREPs are sent, hop by hop, in unicast towards 1128 the originator of the corresponding RREQ, along the Reverse Route 1129 installed by that RREQ. A router, upon forwarding a RREP, installs 1130 the Forward Route towards the . 1132 Thus, with forwarding of RREQs installing the Reverse Route and 1133 forwarding of RREPs installing the Forward Route, bi-directional 1134 routes are provided between the and 1135 indicated in the RREQ. 1137 13.1. RREP Generation 1139 At least one RREP MUST be generated in response to a (set of) 1140 received RREQ messages with identical (,). A 1141 RREP can be generated immediately as a response to each RREQ 1142 processed, or can be generated after a certain delay after the 1143 arrival of the first RREQ, in order to use the "best" received RREQ 1144 (received over lowest-cost path, over path with least Weak Links 1145 etc). A LOADng router MAY generate further RREPs for subsequent 1146 RREQs received with the same (,) pairs, if these 1147 indicate a better route. The content of RREP is as follows: 1149 o := RREP; 1151 o the TLV block; 1153 o bit-0 set to ('1') if RREP-ACK need to be generated. 1154 Otherwise, bit-0 is set to ('0'); 1156 o set to the length of the address, as specified in 1157 Section 8; 1159 o set to the next unused sequence number, maintained by 1160 this LOADng router; 1162 o set to indicate how route costs are to be calculated and 1163 compared, according to Table 3; 1165 o := 0; 1167 o := the cost associated with the interface over which 1168 the RREP is transmitted, and according to the specification of the 1169 included in the RREP message, see Section 16; 1171 o := the address to which this RREP message is to be 1172 sent; this corresponds to the address from the RREQ 1173 message, in response to which this RRREP message is generated; 1175 o := the address of the LOADng router, generating the 1176 RREP. 1178 The specification of the TLVs included in the of the RREQ 1179 responsible to generate the RREP MUST stipulate if, and under which 1180 conditions, these are to be included in the of the RREP. 1182 13.2. RREP Processing 1184 On receiving a RREP message, a LOADng router must process the message 1185 according to this section: 1187 1. If the message is invalid for processing, as defined in 1188 Section 11.1, the message MUST be discarded without further 1189 processing. The message is not considered for forwarding. 1191 2. Otherwise, the message is processed according to Section 11.2. 1193 3. If the RREP message has the ACK-REQUIRED flag set, an RREP_ACK 1194 message MUST be sent to the previous-hop, according to 1195 Section 15.1. 1197 4. If the in the RREP message does not correspond to 1198 an address of this LOADng router, the RREP message is considered 1199 for forwarding according to Section 13.3. 1201 13.3. RREP Forwarding 1203 A Route Reply (RREP) message, considered for forwarding, MUST be 1204 updated as follows, prior to it being transmitted: 1206 1. The and must be updated according to the cost 1207 associated with the interface over which the RREP is transmitted, 1208 and according to the specification of the included in 1209 the RREP, see Section 16. 1211 2. If this interface of the LOADng router uses RREP-ACKs to check 1212 the bidirectionality of the links, the ACK_REQUIRED flag MUST be 1213 set to 1, see Section 15. 1215 The RREP message is then unicast to the next hop towards the 1216 indicated in the RREP. 1218 13.4. RREP Transmission 1220 A Route Reply (RREP) is, ultimately, destined for the LOADng router 1221 listed in the field, and is forwarded in unicast 1222 towards this LOADng router. The RREP MUST, however, be transmitted 1223 so as to allow it to be processed in each intermediate LOADng router 1224 to: 1226 o install proper forward routes 1228 o permit that and be updated to reflect 1229 the route, and 1231 o permit that TLVs included may be processed/added/removed according 1232 to their specification. 1234 14. Route Errors (RERRs) 1236 If Route Repair is not successful, or if Route Repair is not 1237 attempted, a LOADng router MUST generate a Route Error (RERR), and 1238 send this RERR along the Reverse Route to the source of the data 1239 packet for which delivery was unsuccessful. 1241 14.1. RERR Generation 1243 A RERR packet is generated by the LOADng router, detecting the link 1244 breakage, with the following content: 1246 o := RERR; 1248 o the TLV block, containing the TLVs needed; 1250 o := the most appropriate error code from among those 1251 recorded in Table 4; 1253 o := the length of the address, as specified in 1254 Section 8; 1256 o := the source address from the unsuccessfully delivered 1257 data packet. 1259 o := the destination address from the unsuccessfully 1260 delivered data packet. 1262 14.2. RERR Processing 1264 For the purpose of the processing description below, the following 1265 additional notation is used: 1267 previous-hop is the address of the LOADng router, from which the 1268 RERR was received. 1270 Upon receiving an RERR, a LOADng router MUST update its Routing Set 1271 as follows: 1273 1. The TLV fields are added/removed/updated according to their 1274 specification. 1276 2. Find the Routing Tuple (henceforth "matching Routing Tuple") in 1277 the Routing Set where: 1279 * R_dest_addr = 1281 * R_next_addr = previous-hop 1283 3. If no matching Routing Tuple is found, the RERR is not processed 1284 further, and is not considered for forwarding. 1286 4. Otherwise, if one matching Routing Tuple is found, this matching 1287 Routing Tuple is updated as follows: 1289 * R_valid_time := expired 1291 The RERR message is, then, considered for forwarding. 1293 14.3. RERR Forwarding 1295 A RERR is, ultimately, destined for the LOADng router which has the 1296 address from the field, in its Destination Address Set. 1298 A RERR, considered for forwarding is therefore processed as follows: 1300 1. Find the Destination Address Tuple (henceforth, matching 1301 Destination Address Tuple) in the Destination Address Set where: 1303 * D_address = the address from the field of the RERR 1305 2. If one or more matching Destination Address Tuples is found, the 1306 RERR message is discarded and not retransmitted. 1308 3. Otherwise, if no matching Destination Address Tuples is found, 1309 the RERR message is transmitted according to Section 14.4. 1311 14.4. RERR Transmission 1313 An RERR is transmitted, as unicast, to LOADng router, recorded the 1314 next-hop for the indicated in the RERR message. The 1315 RERR MUST be transmitted hop-by-hop such that it can be processed in 1316 each intermediate LOADng router. This serves to: 1318 o Allow intermediate routers to update their Routing Sets, i.e., 1319 remove entries for this destination. 1321 o Permit that TLVs included may be processed/added/removed according 1322 to their specification. 1324 15. Route Reply Acknowledgements (RREP-ACKs) 1326 A LOADng router SHOULD use RREP-ACK exchange to monitor 1327 bidirectionality of links with neighbor routers, except if another 1328 mechanism, as described in Section 10, provides for such 1329 bidirectionality information. 1331 A LOADng router MUST signal in a transmitted RREP that it is 1332 expecting a RREP-ACK, by setting the ackrequired flag in the RREP. 1333 When doing so, the LOADng router MUST also add a tuple (P_next_hop, 1334 P_originator, P_seq_num, P_ack_timeout) to the Pending 1335 Acknowledgement Set, and set P_ack_timeout to RREP_ACK_TIMEOUT. 1337 15.1. RREP-ACK Generation 1339 Upon reception of a RREP message with the flag set, a 1340 LOADng router MUST generate a RREP-ACK and send this RREP-ACK in 1341 unicast to the neighbor which originated the RREP. 1343 A RREP-ACK packet is generated by a LOADng router with the following 1344 content: 1346 o := RREP-ACK; 1348 o the TLV block, containing the TLVs needed; 1350 o := the length of the address, as specified in 1351 Section 8; 1353 o := the field of the received RREP; 1355 o := the field of the received RREP. 1357 15.2. RREP-ACK Processing 1359 On receiving a RREP-ACK from a LOADng neighbor router, a LOADng 1360 router SHOULD do the following: 1362 1. The TLV fields are added/removed/updated according to their 1363 specification. 1365 2. Check whether a corresponding RREP is pending, i.e. if the 1366 Pending List contains a tuple (next_hop, originator, seq_num, 1367 ack_timeout) such as: 1369 * next_hop is the address of the LOADng neighbor router from 1370 which the RREP-ACK was received; 1372 * originator corresponds to the field of the RREP- 1373 ACK; 1375 * seq_num corresponds to the field of the RREP-ACK. 1377 3. If such a tuple exists, then the RREP has been correctly 1378 acknowledged and the tuple MUST be discarded. 1380 4. Otherwise, i.e. if no such tuple exists, then no further 1381 processing is required. 1383 15.3. RREP-ACK Forwarding 1385 A RREP-ACK is intended only for a specific direct neighbor, and MUST 1386 NOT be forwarded. 1388 15.4. RREP-ACK Transmission 1390 A RREP-ACK is transmitted, in unicast, to the neighbor LOADng router 1391 from which the RREP was received. 1393 16. Metrics 1395 This specification permits the use of different metrics for when 1396 calculating route costs, and specifies one particularly simplified 1397 such metric in Section 16.3 purely intended as an example - while 1398 encouraging that more appropriate metrics be developed for different 1399 deployment environments. 1401 16.1. The Default <= Comparison Operator 1403 The objective of the <= comparison operator is to be able to 1404 determine which of two routes is "best", i.e., which route has the 1405 lowest cost. A link between a pair of interfaces may have a nominal 1406 and administratively assigned cost associated (such as, for example, 1407 representing a nominal bandwidth), however may also have a dynamic 1408 component making an link with an otherwise low cost a less attractive 1409 choice - a "Weak Link" - for when establishing a new route (such as, 1410 for example, if a high loss-rate is experienced across that link). 1411 This may make a longer (in term of cost) route preferable over a 1412 shorter route involving such "Weak Links". 1414 To accommodate this situation, this specification includes in RREQs 1415 and RREPs, both a element, representing the cost of the 1416 route traveled, and a element, counting the number of 1417 weak links encountered. When a destination receives multiple copies 1418 of the same RREQ, via different routes, the default <= comparison 1419 operator is defined so as to prefer routes with fewer weak links, 1420 even if such a route has an absolute higher route cost. 1422 Let (WL, RC) be the pair (weak-links, route-cost) received in one 1423 RREQ, and let (WL', RC') be the pair (weak-links, route-cost) 1424 received in another RREQ. The comparison operator <= is then defined 1425 as: 1427 (WL,RC) <= (WL',RC') if and only if: 1429 WL < WL'; OR 1430 WL == WL' AND RC <= RC' 1432 16.2. Specifying New Metrics 1434 When defining a metric, the following considerations SHOULD be taken 1435 into consideration, and MUST be taken into consideration when 1436 requesting a code-point from IANA for the 1-64 range of the Cost 1437 Types registry defined in Table 3: 1439 o The definition of the R_dist field, as well as the value of 1440 MAX_DIST. 1442 o The mechanism for determining when a link qualifies as a "Weak 1443 Link". Examples include when an SNR or SIR is above/below a given 1444 threshold, etc. This MAY be by way of lower-layer information, 1445 message statistics or any other means. 1447 o The mechanism for determining how to update the field 1448 when a RREP or RREQ is transmitted over an interface. 1450 o The required TLV fields for R_dist, as well as the mechanism for 1451 determining how to update those fields. 1453 o The <= comparison operator. This MAY be by way of indicating that 1454 the definition in Section 16.1 is used, or an operator MAY be 1455 specified using also, e.g., information contained in TLVs; in 1456 either case, the comparison operator to use MUST be specified. 1457 Furthermore, the comparison operator MUST specify a strict 1458 ordering of the R_dist space, i.e. R_dist1 can always be compared 1459 to R_dist2 and (R_dist1 <= R_dist2 && R_dist1 > R_dist2) if and 1460 only if R_dist1 = R_dist2. 1462 16.3. Example Metric: Hop Count 1464 This section is intended to exemplify of how to specify Metrics. It 1465 represents a simple "hop count" based cost. It is RECOMMENDED to 1466 define a more appropriate metric for the environment in which the 1467 protocol is to operate. 1469 16.3.1. Simple Hop Count 1471 R_dist: R_dist := (RC, WL) where RC is the Route Cost and WL the 1472 number of weak links. MAX_DIST := (255, 15). 1474 Weak Link: No link is ever considered as a Weak Link. Consequently, 1475 when generating a RREQ or RREP, the element is set to 1476 zero, the is never incremented when forwarding. 1478 Route Cost: When generating a RREQ or a RREP, the is 1479 initialized to one, the is incremented by one when 1480 forwarding. 1482 TLVs: No additional TLVs are used. 1484 <= : (WL,RC) <= (WL',RC') if and only if: RC < RC' OR (RC = RC' AND 1485 RC <= RC') 1487 17. Security Considerations 1489 Currently, this document does not specify any specific security 1490 measures. By way of enabling inclusion of TLVs, development of 1491 security measures, appropriate for a given deployment, is however 1492 supported. 1494 18. IANA Considerations 1496 18.1. Multicast Addresses 1498 IANA is requested to allocate LL-LLN-ROUTERS well-known, link-scoped 1499 multicast addresses for both IPv4 and IPv6. 1501 18.2. Packet Types 1503 IANA is requested to create a new registry for packet types, with 1504 initial assignments and allocation policies as specified in Table 1. 1506 +--------+--------------------------------------+-------------------+ 1507 | Type | Description | Allocation Policy | 1508 +--------+--------------------------------------+-------------------+ 1509 | 0 | Route Request (RREQ) | | 1510 | 1 | Route Reply (RREP) | | 1511 | 2 | Route Error (RERR) | | 1512 | 3 | Route Reply Acknowledgement | | 1513 | | (RREP-ACK) | | 1514 | 4-64 | Unassigned | Expert Review | 1515 | 65-127 | Unassigned | Experimental Use | 1516 +--------+--------------------------------------+-------------------+ 1517 Table 1: Packet Types 1519 18.3. TLV Types 1521 IANA is requested to create a new registry for TLV types, with 1522 initial assignments and allocation policies as specified in Table 2. 1524 +--------+-------------+-------------------+ 1525 | Type | Description | Allocation Policy | 1526 +--------+-------------+-------------------+ 1527 | 0-64 | Unassigned | Expert Review | 1528 | 65-127 | Unassigned | Experimental Use | 1529 +--------+-------------+-------------------+ 1531 Table 2: TLV Types 1533 18.4. Metrics 1535 IANA is requested to create a new registry for Metrics, with initial 1536 assignments and allocation policies as specified in Table 3. 1538 +--------+-----------------------------------------+----------------+ 1539 | Code | Description | Allocation | 1540 | | | Policy | 1541 +--------+-----------------------------------------+----------------+ 1542 | 0 | Hop Count While Avoiding Weak Links | | 1543 | | (Section 16) | | 1544 | 1-64 | Unassigned | Expert Review | 1545 | 65-127 | Unassigned | Experimental | 1546 | | | Use | 1547 +--------+-----------------------------------------+----------------+ 1549 Table 3: Metrics 1551 When assigning a new Metric, the specification requesting that 1552 assignment MUST specify the way in which each LOADng router 1553 calculates the field in RREQs and RREPs, as well as the 1554 criteria for incrementing the field in RREQs and RREPs. 1555 The specification MUST also specify the comparison operations '<=' 1556 for determining from among two RREQs (or RREPs) for the same 1557 destination represents the shortest route; note that this comparison 1558 operation SHOULD involve the field and MAY use other 1559 information such as or content of specific TLV types 1560 included in the RREQ or RREP. 1562 18.5. Error Codes 1564 IANA is requested to create a new registry for Error Codes, with 1565 initial assignments and allocation policies as specified in Table 4. 1567 +--------+--------------------+-------------------+ 1568 | Code | Description | Allocation Policy | 1569 +--------+--------------------+-------------------+ 1570 | 0 | No available route | | 1571 | 1-64 | Unassigned | Expert Review | 1572 | 65-127 | Unassigned | Experimental Use | 1573 +--------+--------------------+-------------------+ 1575 Table 4: Error Codes 1577 19. Contributors 1579 This specification is the result of the joint efforts of the 1580 following contributors -- listed alphabetically. 1582 o Alberto Camacho, LIX, France, 1584 o Thomas Heide Clausen, LIX, France, 1586 o Axel Colin de Verdiere, LIX, France, 1588 o Kenneth Garey, Maxim Integrated Products, USA, 1589 1591 o Ulrich Herberg, Fujitsu Laboratories of America, USA 1592 1594 o Yuichi Igarashi, Hitachi Ltd, Yokohama Research Laboratory, Japan, 1595 1597 o Cedric Lavenu, EDF R&D, France, 1599 o Thierry Lys, ERDF, France, 1601 o Afshin Niktash, Maxim Integrated Products, USA, 1602 1604 o Hiroki Satoh, Hitachi Ltd, Yokohama Research Laboratory, Japan, 1605 1607 o Jiazi Yi, LIX, France, 1609 20. Acknowledgments 1611 The authors would like to acknowledge the team behind AODV, specified 1612 in RFC3561 for their contributions. The authors would also like to 1613 acknowledge the efforts of K. Kim (picosNet Corp/Ajou University), S. 1614 Daniel Park (Samsung Electronics), G. Montenegro (Microsoft 1615 Corporation), S. Yoo (Ajou University) and N. Kushalnagar (Intel 1616 Corp.) for their work on an initial version of a specification, from 1617 which this protocol is derived. 1619 21. References 1621 21.1. Normative References 1623 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1624 Requirement Levels", RFC 2119, BCP 14, March 1997. 1626 [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, 1627 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 1628 Format", RFC 5444, February 2009. 1630 21.2. Informative References 1632 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 1633 Demand Distance Vector (AODV) Routing", RFC 3561, 1634 July 2003. 1636 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 1637 "Transmission of IPv6 Packets over IEEE 802.15.4 1638 Networks", RFC 4944, September 2007. 1640 [RFC6206] Levis, P., Clausen, T., Gnawali, O., and J. Ko, "The 1641 Trickle Algorithm", RFC 6206, March 2011. 1643 [SMF] Macker, J., "Simplified Multicast Forwarding", 1644 draft-ietf-manet-smf-12 (work in progress), July 2011. 1646 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 1647 Considerations in Mobile Ad Hoc Networks (MANETs)", 1648 RFC 5148, February 2008. 1650 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 1651 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 1652 September 2007. 1654 [Stevens] Stevens, W., "TCP/IP Illustrated Volume 1 - The 1655 Protocols", 1994. 1657 Appendix A. LOADng Control Packet Illustrations 1659 This section presents example packets following these specifications. 1661 A.1. RREQ 1663 This figure describes the format of a sample RREQ packet using 32 1664 bits IPv4 addresses. The packet is as follows: 1666 0 1 2 3 1667 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 1668 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1669 | RREQ | 0 | 0 | 3 | Sequence number | 1670 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1671 | Metric| WL | Route Cost | Destination ...| 1672 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1673 |... address (IPv4) | Originator ...| 1674 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1675 |... address (IPv4) | 1676 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1678 A.2. RREP 1680 This figure describes the format of a sample RREP packet using 32 1681 bits IPv4 addresses. The packet is as follows: 1683 0 1 2 3 1684 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 1685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1686 | RREQ | 0 | 0 | 3 | Sequence number | 1687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1688 | Metric| WL | Route Cost | Destination ...| 1689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1690 |... address (IPv4) | Originator ...| 1691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1692 |... address (IPv4) | 1693 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1695 A.3. RREP-ACK 1697 This figure describes the format of a sample RREP-ACK packet using 32 1698 bits IPv4 addresses, as follows: 1700 0 1 2 3 1701 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 1702 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1703 | R-ACK | 0 | 0 | 3 | Source ...| 1704 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1705 |... address (IPv4) | Sequence number | 1706 +-+-+--+-+-+-+-+-+-+-+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1708 A.4. RERR 1710 This figure describes the format of a sample RERR packet using 32 1711 bits IPv4 addresses, as follows: 1713 0 1 2 3 1714 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 1715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1716 | RREP | 0 | 0 | 3 | Source ...| 1717 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1718 |... address (IPv4) | Destination ...| 1719 +-+-+--+-+-+-+-+-+-+-+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1720 |... address (IPv4) | 1721 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1723 Authors' Addresses 1725 Thomas Heide Clausen 1726 LIX, Ecole Polytechnique 1728 Phone: +33 6 6058 9349 1729 EMail: T.Clausen@computer.org 1730 URI: http://www.ThomasClausen.org/ 1732 Axel Colin de Verdiere 1733 LIX, Ecole Polytechnique 1735 Phone: +33 6 1264 7119 1736 EMail: axel@axelcdv.com 1737 URI: http://www.axelcdv.com/ 1738 Jiazi Yi 1739 LIX, Ecole Polytechnique 1741 Phone: +33 1 6933 4031 1742 EMail: jiazi@jiaziyi.com 1743 URI: http://www.jiaziyi.com/ 1745 Cedric Lavenu 1746 EDF R&D 1748 Phone: +33 1 4765 2729 1749 EMail: cedric-2.lavenu@edf.fr 1750 URI: http://www.edf.fr/ 1752 Thierry Lys 1753 ERDF 1755 Phone: +33 1 8197 6777 1756 EMail: thierry.lys@erdfdistribution.fr 1757 URI: http://www.erdfdistribution.fr/ 1759 Afshin Niktash 1760 Maxim Integrated Products 1762 Phone: +1 94 9450 1692 1763 EMail: afshin.niktash@maxim-ic.com 1764 URI: http://www.Maxim-ic.com/ 1766 Yuichi Igarashi 1767 Hitachi, Ltd., Yokohama Research Laboratory 1769 Phone: +81 45 860 3083 1770 EMail: yuichi.igarashi.hb@hitachi.com 1771 URI: http://www.hitachi.com/ 1773 Hiroki Satoh 1774 Hitachi, Ltd., Yokohama Research Laboratory 1776 Phone: +81 44 959 0205 1777 EMail: hiroki.satoh.yj@hitachi.com 1778 URI: http://www.hitachi.com/