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]