[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                                J. Cordero
Expires: May 8, 2014                    ICTEAM, Universite catholique de
                                                              T. Clausen
                                                LIX, Ecole Polytechnique
                                                        November 4, 2013

 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 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 May 8, 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 May 8, 2014                  [Page 1]

Internet-Draft            MANET Reactive Jitter            November 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 May 8, 2014                  [Page 2]

Internet-Draft            MANET Reactive Jitter            November 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 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 routes, or in 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 routes.

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 May 8, 2014                  [Page 3]

Internet-Draft            MANET Reactive Jitter            November 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

   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

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

Yi, et al.                 Expires May 8, 2014                  [Page 4]

Internet-Draft            MANET Reactive Jitter            November 2013

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

Yi, et al.                 Expires May 8, 2014                  [Page 5]

Internet-Draft            MANET Reactive Jitter            November 2013

   the cope of that same RREQ again with the shorter path.

   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.

Yi, et al.                 Expires May 8, 2014                  [Page 6]

Internet-Draft            MANET Reactive Jitter            November 2013

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

Yi, et al.                 Expires May 8, 2014                  [Page 7]

Internet-Draft            MANET Reactive Jitter            November 2013

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

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

Yi, et al.                 Expires May 8, 2014                  [Page 8]

Internet-Draft            MANET Reactive Jitter            November 2013

   [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/

   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 May 8, 2014                  [Page 9]