[Docs] [txt|pdf] [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: July 13, 2015                  ICTEAM, Universite catholique de
                                                                 Louvain
                                                              T. Clausen
                                                LIX, Ecole Polytechnique
                                                         January 9, 2015


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

Abstract

   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 July 13, 2015.

Copyright Notice

   Copyright (c) 2015 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 July 13, 2015                 [Page 1]


Internet-Draft            MANET Reactive Jitter             January 2015


   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  . . . . . . . . . .  8
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  8
   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  8
     8.1.  Normative References . . . . . . . . . . . . . . . . . . .  8
     8.2.  Informative References . . . . . . . . . . . . . . . . . .  8
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10




























Yi, et al.                Expires July 13, 2015                 [Page 2]


Internet-Draft            MANET Reactive Jitter             January 2015


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 [RFC7181], 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
   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 paths.


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 July 13, 2015                 [Page 3]


Internet-Draft            MANET Reactive Jitter             January 2015


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 July 13, 2015                 [Page 4]


Internet-Draft            MANET Reactive Jitter             January 2015


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

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



                                    JitterE=300ms
                           /----- E------\
                          /               \
                        A                  D
                          \               /
                            B--------C---/
                        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 July 13, 2015                 [Page 5]


Internet-Draft            MANET Reactive Jitter             January 2015


   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 July 13, 2015                 [Page 6]


Internet-Draft            MANET Reactive Jitter             January 2015


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] or DAT
   [I-D.ietf-manet-olsrv2-dat-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 implementations of the
   protocol defined by this specification at the time of posting of this
   Internet-Draft, and based on a proposal described in [RFC6982].  The
   description of implementations in this section is intended to assist
   the IETF in its decision processes in progressing drafts to RFCs.
   Please note that the listing of any individual implementation here
   does not imply endorsement by the IETF.  Furthermore, no effort has
   been spent to verify the information presented here that was supplied
   by IETF contributors.  This is not intended as, and must not be
   construed to be, a catalog of available implementations or their
   features.  Readers are advised to note that other implementations may
   exist.

   According to [RFC6982], "this will allow reviewers and working groups
   to assign due consideration to documents that have the benefit of
   running code, which may serve as evidence of valuable experimentation
   and feedback that have made the implemented protocols more mature.
   It is up to the individual working groups to use this information as
   they see fit".



Yi, et al.                Expires July 13, 2015                 [Page 7]


Internet-Draft            MANET Reactive Jitter             January 2015


   There is 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 -04 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)",
              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-12 (work in progress),
              October 2014.

   [I-D.funkfeuer-manet-olsrv2-etx]



Yi, et al.                Expires July 13, 2015                 [Page 8]


Internet-Draft            MANET Reactive Jitter             January 2015


              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-aodvv2]
              Perkins, C., Ratliff, S., Dowdell, J., and L. Steenbrink,
              "Dynamic MANET On-demand (AODVv2) Routing",
              draft-ietf-manet-aodvv2-06 (work in progress),
              December 2014.

   [I-D.ietf-manet-olsrv2-dat-metric]
              Rogge, H. and E. Baccelli, "Packet Sequence Number based
              directional airtime metric for OLSRv2",
              draft-ietf-manet-olsrv2-dat-metric-04 (work in progress),
              December 2014.

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

   [RFC7181]  Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg,
              "The Optimized Link State Routing Protocol Version 2",



Yi, et al.                Expires July 13, 2015                 [Page 9]


Internet-Draft            MANET Reactive Jitter             January 2015


              RFC 7181, April 2014.


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 July 13, 2015                [Page 10]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/