Network Working Group J. Yi Internet-Draft LIX, Ecole Polytechnique Intended status: Informational J. Cordero Expires: April 23, 2014 ICTEAM, Universite catholique de Louvain T. Clausen LIX, Ecole Polytechnique October 20, 2013 Jitter Consideration for Reactive Protocols in Mobile Ad Hoc Networks (MANETs) draft-yi-manet-reactive-jitter-01 Abstract This document provides recommendations for jittering (randomly timing) of routing control message transmission, especially route request dissemination, in reactive protocol of Mobile Ad Hoc Networks, to reduce the probability of collisions, decrease routing overhead, and help finding the optimum routes in the network. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on April 23, 2014. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents Yi, et al. Expires April 23, 2014 [Page 1] Internet-Draft MANET Reactive Jitter October 2013 carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Applicability Statement . . . . . . . . . . . . . . . . . . . . 4 4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 4 5. Reactive Jitter . . . . . . . . . . . . . . . . . . . . . . . . 6 5.1. Window Jitter for Hop-count Metric . . . . . . . . . . . . 6 5.2. Window Jitter for Generic Metric . . . . . . . . . . . . . 6 6. Implementation Status . . . . . . . . . . . . . . . . . . . . . 7 6.1. Implementation by Ecole Polytechnique . . . . . . . . . . . 7 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8.1. Normative References . . . . . . . . . . . . . . . . . . . 7 8.2. Informative References . . . . . . . . . . . . . . . . . . 8 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 Yi, et al. Expires April 23, 2014 [Page 2] Internet-Draft MANET Reactive Jitter October 2013 1. Introduction Jitter - randomly modifying timing of packet transmissions - is RECOMMENDED to be used in MANETs [RFC5148], to avoid simultaneous packet transmission by neighboring routers - something which might result packet losses due to link-layer collisions. In [RFC5148], it is RECOMMENDED that in a protocol with regularly scheduled messages, event-triggered message, schedule reset, forwarding, etc, a deliberated random variation in time (jitter) SHOULD be employed. If a message transmission is scheduled, or triggered at time t, a random value between zero and maximum timing variation (denoted MAXJITTER) is chosen to reduce or increase the time of that transmission. Jitter has been used in NHDP [RFC6130], for periodic HELLO message transmission, and OLSRv2 [I-D.ietf-manet-olsrv2], for triggered and periodic Topology Control (TC) message transmissions. In reactive protocol such as AODV [RFC3561], DSR [RFC4728] and LOADng [I-D.clausen-lln-loadng], packet loss due to concurrent transmissions by neighboring routers are also a concern, in particular for Route Request message (RREQ) dissemination. This, because RREQ transmissions in neighbor routers are triggered by a single event: reciept of RREQ message to be flooded through the network as part of the route disovery process. However, unlike TC message dissemination in OLSRv2, forwarding of RREQ message has another objective: to discover the best path from the source to the destination. It has been observed, however, that the jitter mechanism as, defined in [RFC5148] and if applied directly, in some cases may result in inferier routes, or in unnecessary RREQ retransmissions. This document analyzes the limitation of [RFC5148] when it is applied to reactive protocols, and then introduces a "window" jitter mechanism, which can help reducing RREQ message retransmission and finding the optimum routes. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. This document uses the terminology and notation defined in [RFC5148]. Yi, et al. Expires April 23, 2014 [Page 3] Internet-Draft MANET Reactive Jitter October 2013 3. Applicability Statement This document describes a jitter mechanism that is applicable to the Route Discovery process in reactive MANET protocols, such as Route Request (RREQ) flooding in AODV [RFC3561], DSR [RFC4728], or LOADng [I-D.clausen-lln-loadng]. The jitter mechanism, as described in [RFC5148], is intended for application where the underlying medium access control and lower layers do not provide effective mechanisms to avoid packet collisions when faced with concurrent transmission by neighboring routers. This document handles the situation of "Message Forwarding", described in section 5.3 of [RFC5148]. In addition to collision avoidance by way of a random delay in transmission of RREQ messages, the document also considers: Route Discovery of Optimal Routes When RREQ messages are flooded through the network, the path cost (e.g., hop count or any other link metrics) is also accumulated and recorded. The destination of the RREQ will reply it with a Route Reply (RREP) message. However, the RREQ copy that arrives first may not always be the one which has traversed the optimal path, with respect to the metric used. It has been observed that, in some cases, this is exacerbated by the use of [RFC5148]. Route Discovery Overhead In classic flooding, duplicate message are dropped by intermediate routers, and not retransmitted. However, for RREQ flooding, in which the cumulated path cost is carried in the RREQ, intermediate routers may need to transmit the same RREQ message multiple times, when the shortest (according to the metric in use) path is desired. For example, when an RREQ arrives from the same source to the same destination, and with same sequence number as previously forwarded RREQ, but with a lower path cost. Again, this is exacerbated by the used of [RFC5148]. This document suggest a "window jitter" mechanism, which can help discovering the optimal routes in reactive protocol, and, simultaneously, can reduce the route discovery overhead. 4. Problem Statement [RFC5148] recommends applying jitter to a forwarded message by reducing the time of its emission by a small, random duration. This delay is recommended to be generated uniformly in an interval between zero and MAXJITTER. This has been show to work well in message flooding, where the goal simply is that all routers get a copy of the unmodified message, such as is the case for TC messages in OLSRv2 Yi, et al. Expires April 23, 2014 [Page 4] Internet-Draft MANET Reactive Jitter October 2013 [I-D.ietf-manet-olsrv2]. In reactive protocols, RREQ message from a source are flooded through the network, carrying a "path cost" field, modified by intermediate routers when the message is forwarded. This allows the destination sought through the Route Discovery process to identify which copy of the RREQ has traveled through the "least cost path" (according to the metric in use in the network), and select that path for generating a RREP and installing a routing path. It is, therefore, unfortunate if the copy of the RREQ arriving via the "least cost path" is received later than a RREQ over a path with a higher cost due to inappropriate application of a jitter mechanism. Consider the topology shown in Figure 1, and assume that router A floods an RREQ to identify a path towards router D. If no jitter is used, the RREQ would reach router D through path {A-E-D} faster than the path {A-B-C-D}, assuming that processing time and transmission time at each intermediate router (Ti) are similar. If [RFC5148] is applied, a uniform random distribution [0, MAXJITTER] is used at each hop to determine an additional delay before retransmission, see [RFC5148] section 5.3, the RREQ copy sent through the longer path (in number of hops), may reach the destination faster than the RREQ over shorter path. For example, in Figure 1, the MAXJITTER is 500ms (MAXJITTER is normally chosen to be much greater than transmission time Ti, to avoid collision. Therefore, Ti is neglectable if jitter is used). If Jitter at E (JitterE) is chosen to be 300ms, JitterB is 100ms, and JitterC is 150ms, the RREQ though the longer path (A-B-C-D) would reach D faster than the shorter path (A-E-D). This phenomenon is called "delay inversion". JitterE=300ms /----- E------\ / \ A D \ / B--------C---/ JitterB=100ms JitterC=150ms Figure 1: An example of delay inversion. The RREQ through longer routes may traverl faster, if jitter in RFC5148 is used. In this case, router D would reply to the RREQ with an RREP that advertises path (A-B-C-D), which is suboptimal. When the RREQ traversing (A-E-D) reaches router D, router D would reply again to the cope of that same RREQ again with the shorter path. Yi, et al. Expires April 23, 2014 [Page 5] Internet-Draft MANET Reactive Jitter October 2013 If router D is not the final destination of the RREQ, but only an intermediate router that forwards the RREQ message, there are two possibilities used in different protocols: o For AODV [RFC3561] and DSR [RFC4728], the intermediate routers only forward the first copy of the RREQ received - all the later ones are discarded, even if the later one carries routes with lower costs. This would lead to sub-optimal routes discovered. o For LOADng [I-D.clausen-lln-loadng], the intermediate routers would always retransmit the RREQ carrying better routes that comes later. In the example of Figure 1, router D would retransmit the RREQ received from JitterE also, which result in one more flooding (not only at router D, but to the whole network). The example above illustrates that a "naive" application of [RFC5148] for reactive protocols may present some drawbacks, in terms of path sub-optimality and/or control traffic inefficiency. 5. Reactive Jitter In order to avoid the "delay inversion" phenomenon, described in Section 4, the notion of window jitter introduced in this section. The purpose of "window jitter" is to attempt at "penalizing long paths" more than short paths, and it is RECOMMENDED that this be employed for Route Discovery (RREQ flooding). In addition to the MAXJITTER, a lower bound of jitter is applied, with this lower bound depending on the metrics used. 5.1. Window Jitter for Hop-count Metric For protocols like AODV [RFC3561], DSR [RFC4728] and LOADng [I-D.clausen-lln-loadng], the hop-count metric is supported by default, i.e., a path with a lower hop count is better than a path with more hop counts. When a router forwards an RREQ message, it SHOULD be jittered by delaying it by a random duration. This delay SHOULD be generated uniformly in an interval between MAXJITTER/2 and MAXJITTER. 5.2. Window Jitter for Generic Metric While the hop count metric is straightforward and easy to implement, operational experience has revealed that the used of hop-count as routing metric often leads to unsatisfactory network performance. Reactive protocols like LOADng [I-D.clausen-lln-loadng] thus support using metrics other than hop count, such as ETX Yi, et al. Expires April 23, 2014 [Page 6] Internet-Draft MANET Reactive Jitter October 2013 [I-D.funkfeuer-manet-olsrv2-etx] and ETT [I-D.rogge-baccelli-olsrv2-ett-metric]. For those generic metrics, given a link quality indicator LQ between (0,1) (1 indicates highest quality links), jitter values SHOULD be assigned under a generalized window jitter distribution uniformly within the interval between (1-LQ)MAXJITTER and MAXJITTER. 6. Implementation Status This section records the status of known implementation of the protocol defined by this specification, based on a proposal described in [I-D.sheffer-running-code]. There are currently one publicly- known implementation of window jitter specified in this document. 6.1. Implementation by Ecole Polytechnique This implementation is developed by the Networking Group at Ecole Polytechnique and applied to LOADng [I-D.clausen-lln-loadng] for RREQ message flooding. It can run over real network interfaces, and can also be integrated with the network simulator NS2. It is a Java implementation, and can be used on any platform that includes a Java virtual machine. The implementation is based on the -00 revision of this document, and makes up only a handful of lines of code - in addition to the core LOADng protocol implementation. Both analytical and simulation results have been published in [IEEE_WiOpt2013] and [NBis2013]. The results show that if the shortest paths are desired, the window jitter can reduce the RREQ flooding overhead by 50%, as compared to a naive application of [RFC5148]. 7. IANA Considerations This document contains no actions for IANA. 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter Considerations in Mobile Ad Hoc Networks (MANETs)", Yi, et al. Expires April 23, 2014 [Page 7] Internet-Draft MANET Reactive Jitter October 2013 RFC 5148, February 2008. 8.2. Informative References [I-D.clausen-lln-loadng] Clausen, T., Verdiere, A., Yi, J., Niktash, A., Igarashi, Y., Satoh, H., Herberg, U., Lavenu, C., Lys, T., and J. Dean, "The Lightweight On-demand Ad hoc Distance-vector Routing Protocol - Next Generation (LOADng)", draft-clausen-lln-loadng-09 (work in progress), July 2013. [I-D.funkfeuer-manet-olsrv2-etx] Rogge, H., Baccelli, E., and A. Kaplan, "Packet Sequence Number based ETX Metric for Mobile Ad Hoc Networks", draft-funkfeuer-manet-olsrv2-etx-01 (work in progress), March 2010. [I-D.ietf-manet-olsrv2] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, "The Optimized Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-19 (work in progress), March 2013. [I-D.rogge-baccelli-olsrv2-ett-metric] Rogge, H. and E. Baccelli, "Packet Sequence Number based directional airtime metric for OLSRv2", draft-rogge-baccelli-olsrv2-ett-metric-03 (work in progress), September 2013. [I-D.sheffer-running-code] Sheffer, Y. and A. Farrel, "Improving Awareness of Running Code: the Implementation Status Section", draft-sheffer-running-code-06 (work in progress), June 2013. [IEEE_WiOpt2013] Yi, J., Cordero, J., and T. Clausen, "Optimization of Jitter Configuration for Reactive Route Discovery in Wireless Mesh Networks", Proceedings of IEEE WiOpt 2013, IEEE International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2013. [NBis2013] Cordero, J., Yi, J., and T. Clausen, "Jitter Considerations in On-demand Route Discovery for Mobile Ad Hoc Networks", Proceedings of the 16th International Conference on Netwokr-Based Information Systems, 2013. [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- Yi, et al. Expires April 23, 2014 [Page 8] Internet-Draft MANET Reactive Jitter October 2013 Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [RFC4728] Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4", RFC 4728, February 2007. [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", RFC 6130, April 2011. Authors' Addresses Jiazi Yi LIX, Ecole Polytechnique Phone: +33 1 6933 4031 Email: jiazi@jiaziyi.com URI: http://www.jiaziyi.com/ Juan Antonio Cordero Fuertes ICTEAM, Universite catholique de Louvain Email: j.a.cordero@gmail.com Thomas Clausen LIX, Ecole Polytechnique 91128 Palaiseau Cedex, France Phone: +33-6-6058-9349 Email: T.Clausen@computer.org URI: http://www.thomasclausen.org Yi, et al. Expires April 23, 2014 [Page 9]