idnits 2.17.1 draft-yi-manet-reactive-jitter-01.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 (October 20, 2013) is 3833 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 185 == Missing Reference: 'MAXJITTER' is mentioned on line 185, but not defined == Outdated reference: A later version (-15) exists of draft-clausen-lln-loadng-09 == Outdated reference: A later version (-04) exists of draft-rogge-baccelli-olsrv2-ett-metric-03 Summary: 1 error (**), 0 flaws (~~), 4 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 LIX, Ecole Polytechnique 4 Intended status: Informational J. Cordero 5 Expires: April 23, 2014 ICTEAM, Universite catholique de 6 Louvain 7 T. Clausen 8 LIX, Ecole Polytechnique 9 October 20, 2013 11 Jitter Consideration for Reactive Protocols in Mobile Ad Hoc Networks 12 (MANETs) 13 draft-yi-manet-reactive-jitter-01 15 Abstract 17 This document provides recommendations for jittering (randomly 18 timing) of routing control message transmission, especially route 19 request dissemination, in reactive protocol of Mobile Ad Hoc 20 Networks, to reduce the probability of collisions, decrease routing 21 overhead, and help finding the optimum routes 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 April 23, 2014. 40 Copyright Notice 42 Copyright (c) 2013 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 . . . . . . . . . . . . 6 63 5.2. Window Jitter for Generic Metric . . . . . . . . . . . . . 6 64 6. Implementation Status . . . . . . . . . . . . . . . . . . . . . 7 65 6.1. Implementation by Ecole Polytechnique . . . . . . . . . . . 7 66 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 67 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 68 8.1. Normative References . . . . . . . . . . . . . . . . . . . 7 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 protocol such as AODV [RFC3561], DSR [RFC4728] and LOADng 92 [I-D.clausen-lln-loadng], packet loss due to concurrent transmissions 93 by neighboring routers are also a concern, in particular for Route 94 Request message (RREQ) dissemination. This, because RREQ 95 transmissions in neighbor routers are triggered by a single event: 96 reciept of RREQ message to be flooded through the network as part of 97 the route disovery process. However, unlike TC message dissemination 98 in OLSRv2, forwarding of RREQ message has another objective: to 99 discover the best path from the source to the destination. It has 100 been observed, however, that the jitter mechanism as, defined in 101 [RFC5148] and if applied directly, in some cases may result in 102 inferier routes, or in unnecessary RREQ retransmissions. 104 This document analyzes the limitation of [RFC5148] when it is applied 105 to reactive protocols, and then introduces a "window" jitter 106 mechanism, which can help reducing RREQ message retransmission and 107 finding the optimum routes. 109 2. Terminology 111 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 112 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 113 "OPTIONAL" in this document are to be interpreted as described in 114 [RFC2119]. 116 This document uses the terminology and notation defined in [RFC5148]. 118 3. Applicability Statement 120 This document describes a jitter mechanism that is applicable to the 121 Route Discovery process in reactive MANET protocols, such as Route 122 Request (RREQ) flooding in AODV [RFC3561], DSR [RFC4728], or LOADng 123 [I-D.clausen-lln-loadng]. 125 The jitter mechanism, as described in [RFC5148], is intended for 126 application where the underlying medium access control and lower 127 layers do not provide effective mechanisms to avoid packet collisions 128 when faced with concurrent transmission by neighboring routers. This 129 document handles the situation of "Message Forwarding", described in 130 section 5.3 of [RFC5148]. In addition to collision avoidance by way 131 of a random delay in transmission of RREQ messages, the document also 132 considers: 134 Route Discovery of Optimal Routes When RREQ messages are flooded 135 through the network, the path cost (e.g., hop count or any other 136 link metrics) is also accumulated and recorded. The destination 137 of the RREQ will reply it with a Route Reply (RREP) message. 138 However, the RREQ copy that arrives first may not always be the 139 one which has traversed the optimal path, with respect to the 140 metric used. It has been observed that, in some cases, this is 141 exacerbated by the use of [RFC5148]. 143 Route Discovery Overhead In classic flooding, duplicate message are 144 dropped by intermediate routers, and not retransmitted. However, 145 for RREQ flooding, in which the cumulated path cost is carried in 146 the RREQ, intermediate routers may need to transmit the same RREQ 147 message multiple times, when the shortest (according to the metric 148 in use) path is desired. For example, when an RREQ arrives from 149 the same source to the same destination, and with same sequence 150 number as previously forwarded RREQ, but with a lower path cost. 151 Again, this is exacerbated by the used of [RFC5148]. 153 This document suggest a "window jitter" mechanism, which can help 154 discovering the optimal routes in reactive protocol, and, 155 simultaneously, can reduce the route discovery overhead. 157 4. Problem Statement 159 [RFC5148] recommends applying jitter to a forwarded message by 160 reducing the time of its emission by a small, random duration. This 161 delay is recommended to be generated uniformly in an interval between 162 zero and MAXJITTER. This has been show to work well in message 163 flooding, where the goal simply is that all routers get a copy of the 164 unmodified message, such as is the case for TC messages in OLSRv2 166 [I-D.ietf-manet-olsrv2]. 168 In reactive protocols, RREQ message from a source are flooded through 169 the network, carrying a "path cost" field, modified by intermediate 170 routers when the message is forwarded. This allows the destination 171 sought through the Route Discovery process to identify which copy of 172 the RREQ has traveled through the "least cost path" (according to the 173 metric in use in the network), and select that path for generating a 174 RREP and installing a routing path. It is, therefore, unfortunate if 175 the copy of the RREQ arriving via the "least cost path" is received 176 later than a RREQ over a path with a higher cost due to inappropriate 177 application of a jitter mechanism. 179 Consider the topology shown in Figure 1, and assume that router A 180 floods an RREQ to identify a path towards router D. If no jitter is 181 used, the RREQ would reach router D through path {A-E-D} faster than 182 the path {A-B-C-D}, assuming that processing time and transmission 183 time at each intermediate router (Ti) are similar. 185 If [RFC5148] is applied, a uniform random distribution [0, MAXJITTER] 186 is used at each hop to determine an additional delay before 187 retransmission, see [RFC5148] section 5.3, the RREQ copy sent through 188 the longer path (in number of hops), may reach the destination faster 189 than the RREQ over shorter path. For example, in Figure 1, the 190 MAXJITTER is 500ms (MAXJITTER is normally chosen to be much greater 191 than transmission time Ti, to avoid collision. Therefore, Ti is 192 neglectable if jitter is used). If Jitter at E (JitterE) is chosen 193 to be 300ms, JitterB is 100ms, and JitterC is 150ms, the RREQ though 194 the longer path (A-B-C-D) would reach D faster than the shorter path 195 (A-E-D). This phenomenon is called "delay inversion". 197 JitterE=300ms 198 /----- E------\ 199 / \ 200 A D 201 \ / 202 B--------C---/ 203 JitterB=100ms JitterC=150ms 205 Figure 1: An example of delay inversion. The RREQ through longer 206 routes may traverl faster, if jitter in RFC5148 is used. 208 In this case, router D would reply to the RREQ with an RREP that 209 advertises path (A-B-C-D), which is suboptimal. When the RREQ 210 traversing (A-E-D) reaches router D, router D would reply again to 211 the cope of that same RREQ again with the shorter path. 213 If router D is not the final destination of the RREQ, but only an 214 intermediate router that forwards the RREQ message, there are two 215 possibilities used in different protocols: 217 o For AODV [RFC3561] and DSR [RFC4728], the intermediate routers 218 only forward the first copy of the RREQ received - all the later 219 ones are discarded, even if the later one carries routes with 220 lower costs. This would lead to sub-optimal routes discovered. 222 o For LOADng [I-D.clausen-lln-loadng], the intermediate routers 223 would always retransmit the RREQ carrying better routes that comes 224 later. In the example of Figure 1, router D would retransmit the 225 RREQ received from JitterE also, which result in one more flooding 226 (not only at router D, but to the whole network). 228 The example above illustrates that a "naive" application of [RFC5148] 229 for reactive protocols may present some drawbacks, in terms of path 230 sub-optimality and/or control traffic inefficiency. 232 5. Reactive Jitter 234 In order to avoid the "delay inversion" phenomenon, described in 235 Section 4, the notion of window jitter introduced in this section. 236 The purpose of "window jitter" is to attempt at "penalizing long 237 paths" more than short paths, and it is RECOMMENDED that this be 238 employed for Route Discovery (RREQ flooding). In addition to the 239 MAXJITTER, a lower bound of jitter is applied, with this lower bound 240 depending on the metrics used. 242 5.1. Window Jitter for Hop-count Metric 244 For protocols like AODV [RFC3561], DSR [RFC4728] and LOADng 245 [I-D.clausen-lln-loadng], the hop-count metric is supported by 246 default, i.e., a path with a lower hop count is better than a path 247 with more hop counts. 249 When a router forwards an RREQ message, it SHOULD be jittered by 250 delaying it by a random duration. This delay SHOULD be generated 251 uniformly in an interval between MAXJITTER/2 and MAXJITTER. 253 5.2. Window Jitter for Generic Metric 255 While the hop count metric is straightforward and easy to implement, 256 operational experience has revealed that the used of hop-count as 257 routing metric often leads to unsatisfactory network performance. 258 Reactive protocols like LOADng [I-D.clausen-lln-loadng] thus support 259 using metrics other than hop count, such as ETX 261 [I-D.funkfeuer-manet-olsrv2-etx] and ETT 262 [I-D.rogge-baccelli-olsrv2-ett-metric]. 264 For those generic metrics, given a link quality indicator LQ between 265 (0,1) (1 indicates highest quality links), jitter values SHOULD be 266 assigned under a generalized window jitter distribution uniformly 267 within the interval between (1-LQ)MAXJITTER and MAXJITTER. 269 6. Implementation Status 271 This section records the status of known implementation of the 272 protocol defined by this specification, based on a proposal described 273 in [I-D.sheffer-running-code]. There are currently one publicly- 274 known implementation of window jitter specified in this document. 276 6.1. Implementation by Ecole Polytechnique 278 This implementation is developed by the Networking Group at Ecole 279 Polytechnique and applied to LOADng [I-D.clausen-lln-loadng] for RREQ 280 message flooding. It can run over real network interfaces, and can 281 also be integrated with the network simulator NS2. It is a Java 282 implementation, and can be used on any platform that includes a Java 283 virtual machine. 285 The implementation is based on the -00 revision of this document, and 286 makes up only a handful of lines of code - in addition to the core 287 LOADng protocol implementation. Both analytical and simulation 288 results have been published in [IEEE_WiOpt2013] and [NBis2013]. The 289 results show that if the shortest paths are desired, the window 290 jitter can reduce the RREQ flooding overhead by 50%, as compared to a 291 naive application of [RFC5148]. 293 7. IANA Considerations 295 This document contains no actions for IANA. 297 8. References 299 8.1. Normative References 301 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 302 Requirement Levels", BCP 14, RFC 2119, March 1997. 304 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 305 Considerations in Mobile Ad Hoc Networks (MANETs)", 306 RFC 5148, February 2008. 308 8.2. Informative References 310 [I-D.clausen-lln-loadng] 311 Clausen, T., Verdiere, A., Yi, J., Niktash, A., Igarashi, 312 Y., Satoh, H., Herberg, U., Lavenu, C., Lys, T., and J. 313 Dean, "The Lightweight On-demand Ad hoc Distance-vector 314 Routing Protocol - Next Generation (LOADng)", 315 draft-clausen-lln-loadng-09 (work in progress), July 2013. 317 [I-D.funkfeuer-manet-olsrv2-etx] 318 Rogge, H., Baccelli, E., and A. Kaplan, "Packet Sequence 319 Number based ETX Metric for Mobile Ad Hoc Networks", 320 draft-funkfeuer-manet-olsrv2-etx-01 (work in progress), 321 March 2010. 323 [I-D.ietf-manet-olsrv2] 324 Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 325 "The Optimized Link State Routing Protocol version 2", 326 draft-ietf-manet-olsrv2-19 (work in progress), March 2013. 328 [I-D.rogge-baccelli-olsrv2-ett-metric] 329 Rogge, H. and E. Baccelli, "Packet Sequence Number based 330 directional airtime metric for OLSRv2", 331 draft-rogge-baccelli-olsrv2-ett-metric-03 (work in 332 progress), September 2013. 334 [I-D.sheffer-running-code] 335 Sheffer, Y. and A. Farrel, "Improving Awareness of Running 336 Code: the Implementation Status Section", 337 draft-sheffer-running-code-06 (work in progress), 338 June 2013. 340 [IEEE_WiOpt2013] 341 Yi, J., Cordero, J., and T. Clausen, "Optimization of 342 Jitter Configuration for Reactive Route Discovery in 343 Wireless Mesh Networks", Proceedings of IEEE WiOpt 2013, 344 IEEE International Symposium on Modeling and Optimization 345 in Mobile, Ad Hoc and Wireless Networks, 2013. 347 [NBis2013] 348 Cordero, J., Yi, J., and T. Clausen, "Jitter 349 Considerations in On-demand Route Discovery for Mobile Ad 350 Hoc Networks", Proceedings of the 16th International 351 Conference on Netwokr-Based Information Systems, 2013. 353 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 354 Demand Distance Vector (AODV) Routing", RFC 3561, 355 July 2003. 357 [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source 358 Routing Protocol (DSR) for Mobile Ad Hoc Networks for 359 IPv4", RFC 4728, February 2007. 361 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 362 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 363 RFC 6130, April 2011. 365 Authors' Addresses 367 Jiazi Yi 368 LIX, Ecole Polytechnique 370 Phone: +33 1 6933 4031 371 Email: jiazi@jiaziyi.com 372 URI: http://www.jiaziyi.com/ 374 Juan Antonio Cordero Fuertes 375 ICTEAM, Universite catholique de Louvain 377 Email: j.a.cordero@gmail.com 379 Thomas Clausen 380 LIX, Ecole Polytechnique 381 91128 Palaiseau Cedex, 382 France 384 Phone: +33-6-6058-9349 385 Email: T.Clausen@computer.org 386 URI: http://www.thomasclausen.org