[Search] [txt|pdfized|bibtex] [Tracker] [Email] [Diff1] [Diff2] [Nits]
Versions: 00 01 02 03 04                                                
Network Working Group                                              J. Yi
Internet-Draft                                  LIX, Ecole Polytechnique
Intended status: Informational                               JA. Cordero
Expires: August 18, 2014                ICTEAM, Universite catholique de
                                                              T. Clausen
                                                LIX, Ecole Polytechnique
                                                       February 14, 2014

 Jitter Consideration for Reactive Protocols in Mobile Ad Hoc Networks


   This document provides recommendations for jittering (randomly
   timing) of routing control message transmission, especially route
   request dissemination, in reactive protocols of Mobile Ad Hoc
   Networks, to reduce the probability of collisions, decrease routing
   overhead, and help finding the optimum paths 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 August 18, 2014.

Copyright Notice

   Copyright (c) 2014 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 August 18, 2014                [Page 1]

Internet-Draft            MANET Reactive Jitter            February 2014

   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  . . . . . . . . . . . . 7
     5.2.  Window Jitter for Generic Metric  . . . . . . . . . . . . . 7
   6.  Implementation Status . . . . . . . . . . . . . . . . . . . . . 7
     6.1.  Implementation by Ecole Polytechnique . . . . . . . . . . . 7
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8
   8.  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 8
     8.1.  Normative References  . . . . . . . . . . . . . . . . . . . 8
     8.2.  Informative References  . . . . . . . . . . . . . . . . . . 8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 9

Yi, et al.               Expires August 18, 2014                [Page 2]

Internet-Draft            MANET Reactive Jitter            February 2014

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 protocols 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 paths, or unnecessary RREQ

   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 paths.

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "OPTIONAL" in this document are to be interpreted as described in

   This document uses the terminology and notation defined in [RFC5148].

Yi, et al.               Expires August 18, 2014                [Page 3]

Internet-Draft            MANET Reactive Jitter            February 2014

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], LOADng
   [I-D.clausen-lln-loadng], or AODVv2 [I-D.ietf-manet-aodvv2].

   The jitter mechanism, as described in [RFC5148], is originally
   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 Paths  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 paths in reactive protocols, and,
   simultaneously, can reduce the route discovery overhead, with the
   cost of slightly increasing the route discovery delay.

4.  Problem Statement

   [RFC5148] recommends applying jitter to a forwarded message by
   reducing the time of its emission by a small, random duration in the
   mediums where transmission collisions are possible.  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,

Yi, et al.               Expires August 18, 2014                [Page 4]

Internet-Draft            MANET Reactive Jitter            February 2014

   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

   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. Hop count metric
   is used in this example.  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".

                           /----- E------\
                          /               \
                        A                  D
                          \               /
                        JitterB=100ms  JitterC=150ms

     Figure 1: An example of delay inversion. The RREQ through longer
          paths may traverl faster, if jitter in RFC5148 is used.

   In this case, router D would reply to the RREQ with an RREP that

Yi, et al.               Expires August 18, 2014                [Page 5]

Internet-Draft            MANET Reactive Jitter            February 2014

   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 (assuming
   shorter path is preferred).

   If router D is not the final destination of the RREQ, but only an
   intermediate router that forwards the RREQ message, there are two
   possible approches 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 paths with lower
      costs.  This would lead to sub-optimal paths discovered.

   o  For LOADng [I-D.clausen-lln-loadng], the intermediate routers
      would always retransmit the RREQ carrying better paths 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.

   The "delay inversion" phenomenon stems from the fact that the delay
   imposed by intermediate routers can not really reflect the link
   metrics of related routers.  Even jitter is not used at all, it will
   happen -- and the application of jitter amplified such phenomenon.
   Using other link metrics, or reduced topology mechanisms (like
   Connected Dominating Set) will not mitigate the problem.  On the
   other hand, the delay inversion has direct relationship with the
   network size -- it is more often as the network grows [NBis2013].

5.  Reactive Jitter

   In order to reduce the impact of 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 (in the aspect of hop
   count, or other metrics), 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.

Yi, et al.               Expires August 18, 2014                [Page 6]

Internet-Draft            MANET Reactive Jitter            February 2014

5.1.  Window Jitter for Hop-count Metric

   For protocols like AODV [RFC3561], DSR [RFC4728], LOADng
   [I-D.clausen-lln-loadng] or AODVv2 [I-D.ietf-manet-aodvv2], 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
   [I-D.funkfeuer-manet-olsrv2-etx] and ETT

   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 [RFC6982].  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

Yi, et al.               Expires August 18, 2014                [Page 7]

Internet-Draft            MANET Reactive Jitter            February 2014

   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)",
              RFC 5148, February 2008.

8.2.  Informative References

              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-10 (work in progress),
              October 2013.

              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.

              Perkins, C., Ratliff, S., and J. Dowdell, "Dynamic MANET
              On-demand (AODVv2) Routing", draft-ietf-manet-aodvv2-03
              (work in progress), February 2014.

              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.

              Rogge, H. and E. Baccelli, "Packet Sequence Number based

Yi, et al.               Expires August 18, 2014                [Page 8]

Internet-Draft            MANET Reactive Jitter            February 2014

              directional airtime metric for OLSRv2",
              draft-rogge-baccelli-olsrv2-ett-metric-03 (work in
              progress), September 2013.

              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.

              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-
              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.

   [RFC6982]  Sheffer, Y. and A. Farrel, "Improving Awareness of Running
              Code: The Implementation Status Section", RFC 6982,
              July 2013.

Authors' Addresses

   Jiazi Yi
   LIX, Ecole Polytechnique

   Phone: +33 1 6933 4031
   Email: jiazi@jiaziyi.com
   URI:   http://www.jiaziyi.com/

Yi, et al.               Expires August 18, 2014                [Page 9]

Internet-Draft            MANET Reactive Jitter            February 2014

   Juan Antonio Cordero Fuertes
   ICTEAM, Universite catholique de Louvain

   Email: j.a.cordero@gmail.com

   Thomas Clausen
   LIX, Ecole Polytechnique
   91128 Palaiseau Cedex,

   Phone: +33-6-6058-9349
   Email: T.Clausen@computer.org
   URI:   http://www.thomasclausen.org

Yi, et al.               Expires August 18, 2014               [Page 10]