idnits 2.17.1 draft-yi-manet-reactive-jitter-03.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 : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 14, 2014) is 3718 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 188 == Missing Reference: 'MAXJITTER' is mentioned on line 188, but not defined == Outdated reference: A later version (-15) exists of draft-clausen-lln-loadng-10 == Outdated reference: A later version (-16) exists of draft-ietf-manet-aodvv2-03 == Outdated reference: A later version (-04) exists of draft-rogge-baccelli-olsrv2-ett-metric-03 -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Yi 3 Internet-Draft LIX, Ecole Polytechnique 4 Intended status: Informational JA. Cordero 5 Expires: August 18, 2014 ICTEAM, Universite catholique de 6 Louvain 7 T. Clausen 8 LIX, Ecole Polytechnique 9 February 14, 2014 11 Jitter Consideration for Reactive Protocols in Mobile Ad Hoc Networks 12 (MANETs) 13 draft-yi-manet-reactive-jitter-03 15 Abstract 17 This document provides recommendations for jittering (randomly 18 timing) of routing control message transmission, especially route 19 request dissemination, in reactive protocols of Mobile Ad Hoc 20 Networks, to reduce the probability of collisions, decrease routing 21 overhead, and help finding the optimum paths in the network. 23 Status of this Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on August 18, 2014. 40 Copyright Notice 42 Copyright (c) 2014 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 3. Applicability Statement . . . . . . . . . . . . . . . . . . . . 4 60 4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 4 61 5. Reactive Jitter . . . . . . . . . . . . . . . . . . . . . . . . 6 62 5.1. Window Jitter for Hop-count Metric . . . . . . . . . . . . 7 63 5.2. Window Jitter for Generic Metric . . . . . . . . . . . . . 7 64 6. Implementation Status . . . . . . . . . . . . . . . . . . . . . 7 65 6.1. Implementation by Ecole Polytechnique . . . . . . . . . . . 7 66 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8 67 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 68 8.1. Normative References . . . . . . . . . . . . . . . . . . . 8 69 8.2. Informative References . . . . . . . . . . . . . . . . . . 8 70 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 72 1. Introduction 74 Jitter - randomly modifying timing of packet transmissions - is 75 RECOMMENDED to be used in MANETs [RFC5148], to avoid simultaneous 76 packet transmission by neighboring routers - something which might 77 result packet losses due to link-layer collisions. 79 In [RFC5148], it is RECOMMENDED that in a protocol with regularly 80 scheduled messages, event-triggered message, schedule reset, 81 forwarding, etc, a deliberated random variation in time (jitter) 82 SHOULD be employed. If a message transmission is scheduled, or 83 triggered at time t, a random value between zero and maximum timing 84 variation (denoted MAXJITTER) is chosen to reduce or increase the 85 time of that transmission. 87 Jitter has been used in NHDP [RFC6130], for periodic HELLO message 88 transmission, and OLSRv2 [I-D.ietf-manet-olsrv2], for triggered and 89 periodic Topology Control (TC) message transmissions. 91 In reactive protocols such as AODV [RFC3561], DSR [RFC4728] and 92 LOADng [I-D.clausen-lln-loadng], packet loss due to concurrent 93 transmissions by neighboring routers are also a concern, in 94 particular for Route Request message (RREQ) dissemination. This, 95 because RREQ transmissions in neighbor routers are triggered by a 96 single event: reciept of RREQ message to be flooded through the 97 network as part of the route disovery process. However, unlike TC 98 message dissemination in OLSRv2, forwarding of RREQ message has 99 another objective: to discover the best path from the source to the 100 destination. It has been observed, however, that the jitter 101 mechanism as, defined in [RFC5148] and if applied directly, in some 102 cases may result in inferier paths, or unnecessary RREQ 103 retransmissions. 105 This document analyzes the limitation of [RFC5148] when it is applied 106 to reactive protocols, and then introduces a "window" jitter 107 mechanism, which can help reducing RREQ message retransmission and 108 finding the optimum paths. 110 2. Terminology 112 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 113 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 114 "OPTIONAL" in this document are to be interpreted as described in 115 [RFC2119]. 117 This document uses the terminology and notation defined in [RFC5148]. 119 3. Applicability Statement 121 This document describes a jitter mechanism that is applicable to the 122 Route Discovery process in reactive MANET protocols, such as Route 123 Request (RREQ) flooding in AODV [RFC3561], DSR [RFC4728], LOADng 124 [I-D.clausen-lln-loadng], or AODVv2 [I-D.ietf-manet-aodvv2]. 126 The jitter mechanism, as described in [RFC5148], is originally 127 intended for application where the underlying medium access control 128 and lower layers do not provide effective mechanisms to avoid packet 129 collisions when faced with concurrent transmission by neighboring 130 routers. This document handles the situation of "Message 131 Forwarding", described in section 5.3 of [RFC5148]. In addition to 132 collision avoidance by way of a random delay in transmission of RREQ 133 messages, the document also considers: 135 Route Discovery of Optimal Paths When RREQ messages are flooded 136 through the network, the path cost (e.g., hop count or any other 137 link metrics) is also accumulated and recorded. The destination 138 of the RREQ will reply it with a Route Reply (RREP) message. 139 However, the RREQ copy that arrives first may not always be the 140 one which has traversed the optimal path, with respect to the 141 metric used. It has been observed that, in some cases, this is 142 exacerbated by the use of [RFC5148]. 144 Route Discovery Overhead In classic flooding, duplicate message are 145 dropped by intermediate routers, and not retransmitted. However, 146 for RREQ flooding, in which the cumulated path cost is carried in 147 the RREQ, intermediate routers may need to transmit the same RREQ 148 message multiple times, when the shortest (according to the metric 149 in use) path is desired. For example, when an RREQ arrives from 150 the same source to the same destination, and with same sequence 151 number as previously forwarded RREQ, but with a lower path cost. 152 Again, this is exacerbated by the used of [RFC5148]. 154 This document suggest a "window jitter" mechanism, which can help 155 discovering the optimal paths in reactive protocols, and, 156 simultaneously, can reduce the route discovery overhead, with the 157 cost of slightly increasing the route discovery delay. 159 4. Problem Statement 161 [RFC5148] recommends applying jitter to a forwarded message by 162 reducing the time of its emission by a small, random duration in the 163 mediums where transmission collisions are possible. This delay is 164 recommended to be generated uniformly in an interval between zero and 165 MAXJITTER. This has been show to work well in message flooding, 166 where the goal simply is that all routers get a copy of the 167 unmodified message, such as is the case for TC messages in OLSRv2 168 [I-D.ietf-manet-olsrv2]. 170 In reactive protocols, RREQ message from a source are flooded through 171 the network, carrying a "path cost" field, modified by intermediate 172 routers when the message is forwarded. This allows the destination 173 sought through the Route Discovery process to identify which copy of 174 the RREQ has traveled through the "least cost path" (according to the 175 metric in use in the network), and select that path for generating a 176 RREP and installing a routing path. It is, therefore, unfortunate if 177 the copy of the RREQ arriving via the "least cost path" is received 178 later than a RREQ over a path with a higher cost due to inappropriate 179 application of a jitter mechanism. 181 Consider the topology shown in Figure 1, and assume that router A 182 floods an RREQ to identify a path towards router D. Hop count metric 183 is used in this example. If no jitter is used, the RREQ would reach 184 router D through path {A-E-D} faster than the path {A-B-C-D}, 185 assuming that processing time and transmission time at each 186 intermediate router (Ti) are similar. 188 If [RFC5148] is applied, a uniform random distribution [0, MAXJITTER] 189 is used at each hop to determine an additional delay before 190 retransmission, see [RFC5148] section 5.3, the RREQ copy sent through 191 the longer path (in number of hops), may reach the destination faster 192 than the RREQ over shorter path. For example, in Figure 1, the 193 MAXJITTER is 500ms (MAXJITTER is normally chosen to be much greater 194 than transmission time Ti, to avoid collision. Therefore, Ti is 195 neglectable if jitter is used). If Jitter at E (JitterE) is chosen 196 to be 300ms, JitterB is 100ms, and JitterC is 150ms, the RREQ though 197 the longer path (A-B-C-D) would reach D faster than the shorter path 198 (A-E-D). This phenomenon is called "delay inversion". 200 JitterE=300ms 201 /----- E------\ 202 / \ 203 A D 204 \ / 205 B--------C---/ 206 JitterB=100ms JitterC=150ms 208 Figure 1: An example of delay inversion. The RREQ through longer 209 paths may traverl faster, if jitter in RFC5148 is used. 211 In this case, router D would reply to the RREQ with an RREP that 212 advertises path (A-B-C-D), which is suboptimal. When the RREQ 213 traversing (A-E-D) reaches router D, router D would reply again to 214 the cope of that same RREQ again with the shorter path (assuming 215 shorter path is preferred). 217 If router D is not the final destination of the RREQ, but only an 218 intermediate router that forwards the RREQ message, there are two 219 possible approches used in different protocols: 221 o For AODV [RFC3561] and DSR [RFC4728], the intermediate routers 222 only forward the first copy of the RREQ received - all the later 223 ones are discarded, even if the later one carries paths with lower 224 costs. This would lead to sub-optimal paths discovered. 226 o For LOADng [I-D.clausen-lln-loadng], the intermediate routers 227 would always retransmit the RREQ carrying better paths that comes 228 later. In the example of Figure 1, router D would retransmit the 229 RREQ received from JitterE also, which result in one more flooding 230 (not only at router D, but to the whole network). 232 The example above illustrates that a "naive" application of [RFC5148] 233 for reactive protocols may present some drawbacks, in terms of path 234 sub-optimality and/or control traffic inefficiency. 236 The "delay inversion" phenomenon stems from the fact that the delay 237 imposed by intermediate routers can not really reflect the link 238 metrics of related routers. Even jitter is not used at all, it will 239 happen -- and the application of jitter amplified such phenomenon. 240 Using other link metrics, or reduced topology mechanisms (like 241 Connected Dominating Set) will not mitigate the problem. On the 242 other hand, the delay inversion has direct relationship with the 243 network size -- it is more often as the network grows [NBis2013]. 245 5. Reactive Jitter 247 In order to reduce the impact of the "delay inversion" phenomenon, 248 described in Section 4, the notion of window jitter introduced in 249 this section. The purpose of "window jitter" is to attempt at 250 "penalizing long paths" more than short paths (in the aspect of hop 251 count, or other metrics), and it is RECOMMENDED that this be employed 252 for Route Discovery (RREQ flooding). In addition to the MAXJITTER, a 253 lower bound of jitter is applied, with this lower bound depending on 254 the metrics used. 256 5.1. Window Jitter for Hop-count Metric 258 For protocols like AODV [RFC3561], DSR [RFC4728], LOADng 259 [I-D.clausen-lln-loadng] or AODVv2 [I-D.ietf-manet-aodvv2], the hop- 260 count metric is supported by default, i.e., a path with a lower hop 261 count is better than a path with more hop counts. 263 When a router forwards an RREQ message, it SHOULD be jittered by 264 delaying it by a random duration. This delay SHOULD be generated 265 uniformly in an interval between MAXJITTER/2 and MAXJITTER. 267 5.2. Window Jitter for Generic Metric 269 While the hop count metric is straightforward and easy to implement, 270 operational experience has revealed that the used of hop-count as 271 routing metric often leads to unsatisfactory network performance. 272 Reactive protocols like LOADng [I-D.clausen-lln-loadng] thus support 273 using metrics other than hop count, such as ETX 274 [I-D.funkfeuer-manet-olsrv2-etx] and ETT 275 [I-D.rogge-baccelli-olsrv2-ett-metric]. 277 For those generic metrics, given a link quality indicator LQ between 278 (0,1) (1 indicates highest quality links), jitter values SHOULD be 279 assigned under a generalized window jitter distribution uniformly 280 within the interval between (1-LQ)MAXJITTER and MAXJITTER. 282 6. Implementation Status 284 This section records the status of known implementation of the 285 protocol defined by this specification, based on a proposal described 286 in [RFC6982]. There are currently one publicly-known implementation 287 of window jitter specified in this document. 289 6.1. Implementation by Ecole Polytechnique 291 This implementation is developed by the Networking Group at Ecole 292 Polytechnique and applied to LOADng [I-D.clausen-lln-loadng] for RREQ 293 message flooding. It can run over real network interfaces, and can 294 also be integrated with the network simulator NS2. It is a Java 295 implementation, and can be used on any platform that includes a Java 296 virtual machine. 298 The implementation is based on the -00 revision of this document, and 299 makes up only a handful of lines of code - in addition to the core 300 LOADng protocol implementation. Both analytical and simulation 301 results have been published in [IEEE_WiOpt2013] and [NBis2013]. The 302 results show that if the shortest paths are desired, the window 303 jitter can reduce the RREQ flooding overhead by 50%, as compared to a 304 naive application of [RFC5148]. 306 7. IANA Considerations 308 This document contains no actions for IANA. 310 8. References 312 8.1. Normative References 314 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 315 Requirement Levels", BCP 14, RFC 2119, March 1997. 317 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 318 Considerations in Mobile Ad Hoc Networks (MANETs)", 319 RFC 5148, February 2008. 321 8.2. Informative References 323 [I-D.clausen-lln-loadng] 324 Clausen, T., Verdiere, A., Yi, J., Niktash, A., Igarashi, 325 Y., Satoh, H., Herberg, U., Lavenu, C., Lys, T., and J. 326 Dean, "The Lightweight On-demand Ad hoc Distance-vector 327 Routing Protocol - Next Generation (LOADng)", 328 draft-clausen-lln-loadng-10 (work in progress), 329 October 2013. 331 [I-D.funkfeuer-manet-olsrv2-etx] 332 Rogge, H., Baccelli, E., and A. Kaplan, "Packet Sequence 333 Number based ETX Metric for Mobile Ad Hoc Networks", 334 draft-funkfeuer-manet-olsrv2-etx-01 (work in progress), 335 March 2010. 337 [I-D.ietf-manet-aodvv2] 338 Perkins, C., Ratliff, S., and J. Dowdell, "Dynamic MANET 339 On-demand (AODVv2) Routing", draft-ietf-manet-aodvv2-03 340 (work in progress), February 2014. 342 [I-D.ietf-manet-olsrv2] 343 Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 344 "The Optimized Link State Routing Protocol version 2", 345 draft-ietf-manet-olsrv2-19 (work in progress), March 2013. 347 [I-D.rogge-baccelli-olsrv2-ett-metric] 348 Rogge, H. and E. Baccelli, "Packet Sequence Number based 349 directional airtime metric for OLSRv2", 350 draft-rogge-baccelli-olsrv2-ett-metric-03 (work in 351 progress), September 2013. 353 [IEEE_WiOpt2013] 354 Yi, J., Cordero, J., and T. Clausen, "Optimization of 355 Jitter Configuration for Reactive Route Discovery in 356 Wireless Mesh Networks", Proceedings of IEEE WiOpt 2013, 357 IEEE International Symposium on Modeling and Optimization 358 in Mobile, Ad Hoc and Wireless Networks, 2013. 360 [NBis2013] 361 Cordero, J., Yi, J., and T. Clausen, "Jitter 362 Considerations in On-demand Route Discovery for Mobile Ad 363 Hoc Networks", Proceedings of the 16th International 364 Conference on Netwokr-Based Information Systems, 2013. 366 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 367 Demand Distance Vector (AODV) Routing", RFC 3561, 368 July 2003. 370 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 371 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 372 IPv4", RFC 4728, February 2007. 374 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 375 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 376 RFC 6130, April 2011. 378 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 379 Code: The Implementation Status Section", RFC 6982, 380 July 2013. 382 Authors' Addresses 384 Jiazi Yi 385 LIX, Ecole Polytechnique 387 Phone: +33 1 6933 4031 388 Email: jiazi@jiaziyi.com 389 URI: http://www.jiaziyi.com/ 390 Juan Antonio Cordero Fuertes 391 ICTEAM, Universite catholique de Louvain 393 Email: j.a.cordero@gmail.com 395 Thomas Clausen 396 LIX, Ecole Polytechnique 397 91128 Palaiseau Cedex, 398 France 400 Phone: +33-6-6058-9349 401 Email: T.Clausen@computer.org 402 URI: http://www.thomasclausen.org