Network Working Group J. Yi
Internet-Draft LIX, Ecole Polytechnique
Intended status: Informational J. Cordero
Expires: May 8, 2014 ICTEAM, Universite catholique de
Louvain
T. Clausen
LIX, Ecole Polytechnique
November 4, 2013
Jitter Consideration for Reactive Protocols in Mobile Ad Hoc Networks
(MANETs)
draft-yi-manet-reactive-jitter-02
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 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
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 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].
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
[I-D.clausen-lln-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
considers:
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
[I-D.ietf-manet-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".
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, 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
[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 [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
[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-10 (work in progress),
October 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 airtime metric for OLSRv2",
draft-rogge-baccelli-olsrv2-ett-metric-03 (work in
progress), September 2013.
[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.
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,
France
Phone: +33-6-6058-9349
Email: T.Clausen@computer.org
URI: http://www.thomasclausen.org
Yi, et al. Expires May 8, 2014 [Page 9]