idnits 2.17.1 draft-yi-loadngsmartrreq-02.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 179 has weird spacing: '...rt-rreq is a ...' -- The document date (July 4, 2014) is 3577 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Outdated reference: A later version (-15) exists of draft-clausen-lln-loadng-10 -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Yi 3 Internet-Draft T. Clausen 4 Intended status: Experimental LIX, Ecole Polytechnique 5 Expires: January 5, 2015 July 4, 2014 7 Smart Route Request for Lightweight On-demand Ad hoc Distance-vector 8 Routing - Next Generation 9 draft-yi-loadngsmartrreq-02 11 Abstract 13 This document describes the Smart Route Request extension for 14 Lightweight Ad hoc On-Demand - Next Generation (LOADng) distance 15 vector routing protocol. It allows making use of existed routing 16 information to forward Route Request message, and helps reducing 17 routing overhead in LOADng. 19 Status of this Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on January 5, 2015. 36 Copyright Notice 38 Copyright (c) 2014 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 3 56 4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 4 57 5. Protocol Signaling and Information Bases . . . . . . . . . . . 5 58 6. Protocol Functioning . . . . . . . . . . . . . . . . . . . . . 5 59 7. Smart Route Request Message . . . . . . . . . . . . . . . . . 6 60 7.1. RREQ_SMART Generation . . . . . . . . . . . . . . . . . . 6 61 7.2. RREQ_SMART Processing . . . . . . . . . . . . . . . . . . 6 62 7.3. RREQ_SMART Forwarding . . . . . . . . . . . . . . . . . . 6 63 7.4. RREQ_SMART Transmission . . . . . . . . . . . . . . . . . 7 64 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 7 65 8.1. Implementation of Ecole Polytechnique . . . . . . . . . . 8 66 9. Security Considerations . . . . . . . . . . . . . . . . . . . 8 67 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 68 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 69 11.1. Normative References . . . . . . . . . . . . . . . . . . . 8 70 11.2. Informative References . . . . . . . . . . . . . . . . . . 9 71 Appendix A. LOADng Smart Route Request Control Messages using 72 RFC5444 . . . . . . . . . . . . . . . . . . . . . . . 9 73 A.1. RREQ_SMART Messages Encoding Considerations . . . . . . . 9 74 Appendix B. RFC5444-Specific IANA Considerations . . . . . . . . 10 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 77 1. Introduction 79 Smart Route Request is an extension of LOADng protocol 80 [I-D.clausen-lln-loadng] for use in forwarding Route Request message 81 (RREQ), based on the routing information already known by the LOADng 82 router. 84 In LOADng [I-D.clausen-lln-loadng], on receiving an RREQ message 85 destined to other routers, an intermediate router has to multicast 86 the RREQ message to all its neighbor routers. The Smart RREQ 87 specified in this document makes use of available routing information 88 in the local router, if possible, to reduce message multicasting. It 89 does not require extract message exchange, and does not introduce 90 computation overload. 92 Compared to RREQ dissemination by classical flooding, Smart RREQ can 93 reduce up to 90% of route discovery overhead, depending on the 94 scenarios applied. 96 2. Terminology 98 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 99 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 100 "OPTIONAL" in this document are to be interpreted as described in 101 [RFC2119]. 103 This document uses the terminology and notation defined in 104 [I-D.clausen-lln-loadng]. 106 3. Applicability Statement 108 This protocol: 110 o Is an extension of LOADng for RREQ message forwarding. 112 o Makes use of routes available in the local router, and forward the 113 RREQ message in unicast to the desired destination, if possible. 115 o Can reduce the overhead used for route discovery in LOADng, 116 especially in the scenarios where the data packets are sent to a 117 few concentrators in the network. 119 o Can work seamlessly with LOADng protocol, even with the LOADng 120 Routers without Smart RREQ extension. 122 4. Problem Statement 124 In route discovery of LOADng [I-D.clausen-lln-loadng], the protocol 125 explicitly prohibits intermediate routers from replying RREQ 126 messages. Only the destination is permitted to respond to an RREQ by 127 unicasting a Route Reply (RREP) message. For example, as shown in 128 Figure 1, in a LOADng network, Router A initiates a route discovery 129 to Router D. Even the intermediate Routers (Router B and Router C in 130 this case) have already available routes to Router D, they have to 131 broadcast the RREQ message until the messsage reaches the final 132 destination Router D. The Router D can then send an RREP to build the 133 router from Router A to Router D. 135 RREQ RREQ RREQ 137 \ / \ / \ / 138 A <--RREP-- B <--RREP-- C <--RREP-- D 139 / \ / \ / \ 141 Figure 1: LOADng route discovery from Router A to Router D 143 Eliminating intermediate RREP can reduce the control message size and 144 protocol complexity, but can also cause unnecessary multicast in the 145 network. For example, in Figure 2, Router A initiates a route 146 discovery to Router D. Router B, C and E have already routes to D. On 147 receiving the RREQ, Router B, C and E still need to multicast the 148 RREQ message to the whole network. The retransmission of the RREQ 149 would be N (N is the number of routers in the network). 151 _ D__ 152 / | \ 153 B ----A ---C 154 \ | / 155 - E - 157 Figure 2: LOADng route discovery from Router A to Router D. Router B, 158 C and E have already routes to Router D 160 In AODV [RFC3561], the intermediate routers can send reply to the 161 originator of the router discovery. In the example of Figure 2, 162 Router B, C and E will send an RREP to A directly, instead of 163 flooding the RREQ message to the whole network. In this way, the RRE 164 message can be kept "local" - but with the cost of complex sequence 165 number check to avoid loops, and extra Gratuitous RREP message 166 exchange. 168 The Smart Route Request described in this document reduces redundant 169 multicast RREQ in LOADng if possible, while keeps the lightweight 170 nature of LOADng. 172 5. Protocol Signaling and Information Bases 174 LOADng Smart Route Request is an extension of LOADng, and thus 175 inherits all the information bases and signaling defined in 176 [I-D.clausen-lln-loadng]. Only one additional flag for RREQ message 177 is introduced: 179 RREQ.smart-rreq is a boolean flag which, when set ('1'), indicates 180 the message is an RREQ_SMART message, and MUST be processed 181 according to this specification. 183 6. Protocol Functioning 185 This document concerns only RREQ dissemination of LOADng. When a 186 LOADng Router initiates a route discovery, it floods an RREQ message 187 with RREQ.smart-rreq flag set 1 (denoted RREQ_SMART message). 189 On receiving the RREQ_SMART message, the intermediate LOADng Router 190 MUST process the message according to Section 12.2 of 191 [I-D.clausen-lln-loadng]. Prior to the message being transmitted, 192 the LOADng Router will check if there is an available Routing Tuple 193 to the destination of RREQ_SMART. If such Routing Tuple is found, 194 the LOADng Router will unicast the RREQ_SMART message to the 195 R_next_addr of the Routing Tuple. Or else, the RREQ_SMART message is 196 transmitted according to the flooding operation specified for the 197 network. 199 Figure 3 illustrates an example of operation of Smart Route Request. 200 Router A requires a route discovery to Router D, and thus floods a 201 RREQ_SMART message. Router B and C has already available routes to 202 Router D. They will unicast the RREQ_SMART message to Router D. 204 RREQ_SMART 206 \ / --RREQ_SMART--> --RREQ_SMART--> 207 A <--RREP--- B <----RREP---- C <----RREP---- D 208 / \ 210 Figure 3: LOADng route discovery from Router A to Router D with Smart 211 Route Request. Router B and Router C have already availalbe routes to 212 Router D 214 In the example in Figure 2, Router B, C and E will unicast the 215 RREQ_SMART to Router D. Although those RREQ_SMART messages will not 216 be processed by Router D because the messages carries longer routes, 217 the RREQ_SMART message is kept local, instead of being flooded to the 218 whole network. This is not a rare case in real application, like all 219 the Routers send data to a concentrator in the network. 221 If the Smart RREQ defined in this specification is used, the 222 RREQ_RETRIES parameter (defined in [I-D.clausen-lln-loadng]) MUST be 223 great than 1. For a route discovery process, on the first RREQ 224 message can be a RREQ_SMART message. For the following retries, the 225 RREQ.smart-rreq flag MUST be cleared ('0'). 227 7. Smart Route Request Message 229 The Smart Route Request Message (RREQ_SMART) are generated by a 230 LOADng Router for the first try, when it has a data packet to deliver 231 to a destination, but the LOADng Router has no matching tuple in the 232 Routing Set. The basic operation follows Section 12 of 233 [I-D.clausen-lln-loadng], except the RREQ.smart-rreq flag is treated 234 differently, as specified in this section. 236 7.1. RREQ_SMART Generation 238 A LOADng Router with Smart Route Request extension generate an 239 RREQ_SMART message for the first try of a route discovery process, 240 with the following content: 242 o RREQ.smart-rreq := TRUE; 244 o All the other fields are set according to Section 12.1 of 245 [I-D.clausen-lln-loadng]. 247 If there was no RREP message received after 2*NET_TRAVERSAL_TIME, 248 anther RREQ message MUST be initiated. The following RREQ messages 249 MUST set RREQ.smart-rreq to FALSE, and be treated as normal RREQ 250 message as specified in Section 12 of [I-D.clausen-lln-loadng]. 252 7.2. RREQ_SMART Processing 254 RREQ_SMART messages are processed according to Section 12.2 of 255 [I-D.clausen-lln-loadng]. 257 7.3. RREQ_SMART Forwarding 259 The fields of an RREQ_SMART message considered for forwarding MUST be 260 updated following Section 12.3 of [I-D.clausen-lln-loadng], prior to 261 it being transmitted. 263 The RREQ_SMART message is then transmitted, according to Section 7.4. 265 7.4. RREQ_SMART Transmission 267 RREQ_SMART transmission is accomplished by the following procedure: 269 1. Find the Routing Tuple (henceforth, the "Matching Routing Tuple") 270 in the Route Set, where: 272 * R_dest_addr = RREQ.destination; and 274 * R_next_addr does not equal to the interface address from which 275 RREQ_SMART was received. 277 2. If a Matching Routing Tuple is found, find the Local Interface 278 Tuple (henceforth, matching Local Interface Tuple) in the Local 279 Interface Set where: 281 * I_local_iface_addr_list contains R_local_iface_addr from the 282 Matching Routing Tuple 284 The RREQ_SMART is transmitted over the LOADng Interface, 285 identified by the Matching Interface Tuple to the neighbor LOADng 286 Router, identified by R_next_addr from the Matching Routing 287 Tuple. 289 3. Otherwise, the RREQ_SMART is transmitted according to Section 290 12.4 of [I-D.clausen-lln-loadng]. 292 8. Implementation Status 294 This section records the status of known implementations of the 295 protocol defined by this specification at the time of posting of this 296 Internet-Draft, and based on a proposal described in [RFC6982]. The 297 description of implementations in this section is intended to assist 298 the IETF in its decision processes in progressing drafts to RFCs. 299 Please note that the listing of any individual implementation here 300 does not imply endorsement by the IETF. Furthermore, no effort has 301 been spent to verify the information presented here that was supplied 302 by IETF contributors. This is not intended as, and must not be 303 construed to be, a catalog of available implementations or their 304 features. Readers are advised to note that other implementations may 305 exist. 307 According to [RFC6982], "this will allow reviewers and working groups 308 to assign due consideration to documents that have the benefit of 309 running code, which may serve as evidence of valuable experimentation 310 and feedback that have made the implemented protocols more mature. 311 It is up to the individual working groups to use this information as 312 they see fit". 314 There are currently one publicly-known implementation of smart route 315 request extension of LOADng specified in this document. 317 8.1. Implementation of Ecole Polytechnique 319 This implementation is developed by the Networking Group at Ecole 320 Polytechnique and applied to LOADng [I-D.clausen-lln-loadng] for RREQ 321 message forwarding. It can run over real network interfaces, and can 322 also be integrated with the network simulator NS2. It is a Java 323 implementation, and can be used on any platform that includes a Java 324 virtual machine. 326 The implementation is based on -00 revision of this document, and 327 includes about 20 line of additional code to the LOADng 328 implementation. Simulation results based on NS2 have been published 329 in [IEEE_ICWITS2012]. The results show that in point-to-point 330 scenarios, Smart RREQ extension can save 30% RREQ flooding overhead 331 compared to LOADng; in multipoint-to-point scenarios, Smart RREQ 332 extension can save up to 90% RREQ flooding overhead compared to 333 LOADng. 335 9. Security Considerations 337 This Smart RREQ extension inherits the vulnerabilities of LOADng, as 338 discussed in section 18 of [I-D.clausen-lln-loadng]. No additional 339 vulnerability is introduced in this extension. 341 10. IANA Considerations 343 IANA is requested to .... 345 11. References 347 11.1. Normative References 349 [I-D.clausen-lln-loadng] 350 Clausen, T., Verdiere, A., Yi, J., Niktash, A., Igarashi, 351 Y., Satoh, H., Herberg, U., Lavenu, C., Lys, T., and J. 352 Dean, "The Lightweight On-demand Ad hoc Distance-vector 353 Routing Protocol - Next Generation (LOADng)", 354 draft-clausen-lln-loadng-10 (work in progress), 355 October 2013. 357 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 358 Requirement Levels", BCP 14, RFC 2119, March 1997. 360 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 361 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 362 Format", RFC 5444, February 2009. 364 11.2. Informative References 366 [IEEE_ICWITS2012] 367 Yi, J., Clausen, T., and A. Bas, "Smart Route Request for 368 on-demand route discovery in constrained environments", 369 Proceedings of IEEE ICWITS2012, IEEE International 370 Conference on Wireless Information Technology and Systems, 371 2012. 373 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 374 Demand Distance Vector (AODV) Routing", RFC 3561, 375 July 2003. 377 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 378 Code: The Implementation Status Section", RFC 6982, 379 July 2013. 381 Appendix A. LOADng Smart Route Request Control Messages using RFC5444 383 This section presents how the abstract LOADng Smart Route Request 384 messages, used throughout this specification, are mapped into 385 [RFC5444] messages. It only concerns the flag RREQ.smart-rreq. 387 A.1. RREQ_SMART Messages Encoding Considerations 389 This protocol makes use of RREQ message defined in 390 [I-D.clausen-lln-loadng]. Therefore, it reuses the RREQ Message Type 391 defined in [I-D.clausen-lln-loadng], and defines one additional 392 flags: RREQ.smart-rreq. Table 1 describes how the flag is mapped 393 into [RFC5444]. 395 +-----------------+-----------------+-------------------------------+ 396 | RREQ Element | RFC5444-Element | Considerations | 397 +-----------------+-----------------+-------------------------------+ 398 | RREQ.smart-rreq | FLAGS Message | Encoded by way of a | 399 | | TLV | Message-Type-specific Message | 400 | | | TLV of type FLAGS, defined in | 401 | | | Table 3 | 402 +-----------------+-----------------+-------------------------------+ 404 Table 1: RREQ Message Elements for Smart Route Request 406 Appendix B. RFC5444-Specific IANA Considerations 408 This document only specifies one addition flag of RREQ, which has 409 been allocated in "Message Types" namespace of [RFC5444], in 410 [I-D.clausen-lln-loadng]. 412 IANA is requested to add a RREQ Message-Type-specific Message TLV 413 Type, in accordance with Section 6.2.1 of [RFC5444], with allocation 414 policies as specified in Table 2. 416 +---------+-------------+-------------------+ 417 | Type | Description | Allocation Policy | 418 +---------+-------------+-------------------+ 419 | 129 | FLAGS | | 420 | 130-223 | Unassigned | Expert Review | 421 +---------+-------------+-------------------+ 423 Table 2: RREQ Message-Type-specific TLV Type for LOADng-CT 425 Allocation of the FLAGS TLV from the RREQ Message-Type-specific 426 Message TLV Types in Table 2 will create a new Type Extension 427 registry, with type extension 0, as illustrated in Table 3. 429 +-------+------+-----------+-----+----------------------------------+ 430 | Name | Type | Type | Bit | Description | 431 | | | Extension | | | 432 +-------+------+-----------+-----+----------------------------------+ 433 | FLAGS | 129 | 0 | 0 | RREQ.smart-rreq flag (i.e., the | 434 | | | | | RREQ message is a RREQ_SMART | 435 | | | | | when it is set to 1) | 436 | FLAGS | 129 | 1-255 | | Unassigned | 437 +-------+------+-----------+-----+----------------------------------+ 439 Table 3: Message TLV Type assignment: FLAGs 441 Authors' Addresses 443 Jiazi Yi 444 LIX, Ecole Polytechnique 446 Phone: +33 1 6933 4031 447 Email: jiazi@jiaziyi.com 448 URI: http://www.jiaziyi.com/ 450 Thomas Clausen 451 LIX, Ecole Polytechnique 452 91128 Palaiseau Cedex, 453 France 455 Phone: +33-6-6058-9349 456 Email: T.Clausen@computer.org 457 URI: http://www.thomasclausen.org