Network Working Group J. Yi Internet-Draft LIX, Ecole Polytechnique Intended status: Experimental J. Fuertes Expires: January 14, 2014 ICTEAM, Universite catholique de Louvain T. Clausen LIX, Ecole Polytechnique July 13, 2013 Jitter Consideration for Reactive Protocol in Mobile Ad Hoc Networks (MANETs) draft-yi-manet-reactive-jitter-00 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 January 14, 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 January 14, 2014 [Page 1] Internet-Draft MANET Reactive Jitter July 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 . . . . . . . . . . . . . . . . . . . . 3 4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 4 5. Protocol Functioning . . . . . . . . . . . . . . . . . . . . . 6 5.1. Window Jitter for Hop-count Metric . . . . . . . . . . . . 6 5.2. Window Jitter for Generic Metric . . . . . . . . . . . . . 6 6. Implementation Status . . . . . . . . . . . . . . . . . . . . . 6 6.1. Implementation of Ecole Polytechnique . . . . . . . . . . . 7 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 9.1. Normative References . . . . . . . . . . . . . . . . . . . 7 9.2. Informative References . . . . . . . . . . . . . . . . . . 8 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 Yi, et al. Expires January 14, 2014 [Page 2] Internet-Draft MANET Reactive Jitter July 2013 1. Introduction Jitter - the randomly varying timing - is RECOMMENDED to be used in MANETs [RFC5148], to avoid simultaneous packet transmission by near by nodes, which might result collision between these packets. 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 delay of transmission. Jitter has been used in NHDP [RFC6130], for periodic HELLO message transmission, and OLSRv2 [I-D.ietf-manet-olsrv2], for triggered Topology Control (TC) message transmission. In reactive protocol such as AODV [RFC3561], DSR [RFC4728] and LOADng [I-D.clausen-lln-loadng], jitter can be also used in the Route Request message (RREQ) dissemination, because RREQ transmissions in neighbor routers are triggered by a single event - the receiving of the RREQ message. However, unlike TC message dissemination in OLSRv2, the forwarding of RREQ message has another objective: discover the best route from the source to the destination. However, the jitter mechanism defined in [RFC5148] may result in inferier routes, or unnecessary RREQ retransmissions, if it is applied to reactive route discovery directly. This document first analyzes the limitation of [RFC5148] when it is applied to reactive protocols, and then introduced 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]. 3. Applicability Statement This document describes a jitter mechanism that is applicable to Yi, et al. Expires January 14, 2014 [Page 3] Internet-Draft MANET Reactive Jitter July 2013 Route Request flooding in reactive MANET protocols, such as AODV [RFC3561], DSR [RFC4728] or LOADng [I-D.clausen-lln-loadng]. The jitter described in [RFC5148] is intended for application where the underlying medium access control and lower layers do not provide effective mechanisms to avoid such collisions. In addition to collision avoidance by way of a random delay in transmission of RREQ messages, the document also considers: o Route discovery of optimal routes. When RREQ messages are flooded through the network, the route 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 the one which has traversed the optimal path with respect to the metric used - and this is exacerbated by the use of [RFC5148]. o Route discovery overhead. In a simple flooding algorithm, duplicate message are dropped by intermediate nodes, and not retransmitted. However, for RREQ flooding, in which the cumulated route cost is carried in the RREQ, intermediate nodes may need to transmit the same RREQ message multiple times, if the shortest route 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 route cost. Again, this is exacerbated by the used of [RFC5148]. This document introduces a "window jitter" mechanism, which can help discovering the optimal routes in reactive protocol, and reducing the route discovery overhead in the same time. 4. Problem Statement [RFC5148] recommends jitter a message by delaying it by a random duration when the message is being forwarded. This delay SHOULD be generated uniformly in an interval between zero and MAXJITTER. This works well in message flooding without modification of the message by the intermediate nodes, such as TC message in OLSRv2 [I-D.ietf-manet-olsrv2]. In reactive protocols, RREQ message from a source are flooded through the network, carrying a route cost field modified by every intermediate nodes, in order to identify a route towards the intended destination. Consider the topology shown in Figure 1, and assume that node A floods an RREQ to identify a route towards node D. If no jitter is Yi, et al. Expires January 14, 2014 [Page 4] Internet-Draft MANET Reactive Jitter July 2013 used, the RREQ would reach node D through path {A-E-D} faster than the path {A-B-C-D}, assuming that processing time and transmission time at each intermediate node (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, 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, node 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 node D, node D would reply again to the cope of that same RREQ again with the shorter path. If node D is not the final destination of the RREQ, but only an intermediate node that forwards the RREQ message, there are two possibilities here, depending on the protocols: o For AODV [RFC3561] and DSR [RFC4728], the intermediate nodes 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 nodes would always retransmit the RREQ carrying better routes that comes later. In the example of Figure 1, node D would retransmit the RREQ received from JitterE also, which result in one more flooding (not only at node D, but to the whole network). Yi, et al. Expires January 14, 2014 [Page 5] Internet-Draft MANET Reactive Jitter July 2013 The example about illustrate that the application of [RFC5148] to reactive protocols has some drawbacks, in terms of path sub- optimality and/or control traffic inefficiency. 5. Protocol Functioning In order to avoid "delay inversion" phenomenon described in Section 4, the window jitter introduced in this section SHOULD be employed in RREQ message retransmission. In addition to the MAXJITTER, a lower bound of jitter is applied, 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., the paths with less hop counts is better than the ones with more hop counts. When a node forward 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 hop count metric is straightforward and easy to implement, operational experience revealed that the used of hop-count as routing metric lead to unsatisfactory network performance. Reactive protocols like LOADng [I-D.clausen-lln-loadng] thus support using different metrics other than hop count, such as ETX [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. Yi, et al. Expires January 14, 2014 [Page 6] Internet-Draft MANET Reactive Jitter July 2013 6.1. Implementation of 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 -00 revision of this document, and includes only a handful of lines of code in addition to the LOADng 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 50% of RREQ flooding overhead, compared to classical jitter in [RFC5148]. 7. Security Considerations This document provides a window jitter mechanism to be used in MANET reactive protocols. Full security considerations are to be provides by specific protocol, rather than in this document. However, it may be noted that an attacker can always "turn off" the jitter mechanisms in itself, and thus make sure that the message manipulated by it can propagated faster than legitimate messages (which are delayed because of jitter). 8. IANA Considerations This document contains no actions for IANA. 9. References 9.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)", RFC 5148, February 2008. Yi, et al. Expires January 14, 2014 [Page 7] Internet-Draft MANET Reactive Jitter July 2013 9.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., Perkins, C., and J. Dean, "The Lightweight On-demand Ad hoc Distance-vector Routing Protocol - Next Generation (LOADng)", draft-clausen-lln-loadng-08 (work in progress), January 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 ETT Metric for OLSRv2", draft-rogge-baccelli-olsrv2-ett-metric-02 (work in progress), July 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., Fuertes, 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] Fuertes, 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- Demand Distance Vector (AODV) Routing", RFC 3561, Yi, et al. Expires January 14, 2014 [Page 8] Internet-Draft MANET Reactive Jitter July 2013 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 January 14, 2014 [Page 9]