Jitter Consideration for Reactive Protocol in Mobile Ad Hoc Networks (MANETs)
draft-yi-manet-reactive-jitter-00

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]