draft-ietf-manet-jitter-01.txt   draft-ietf-manet-jitter-02.txt 
Mobile Ad hoc Networking (MANET) T. Clausen Mobile Ad hoc Networking (MANET) T. Clausen
Internet-Draft LIX, Ecole Polytechnique, France Internet-Draft LIX, Ecole Polytechnique, France
Intended status: Informational C. Dearlove Intended status: Informational C. Dearlove
Expires: December 31, 2007 BAE Systems Advanced Technology Expires: February 25, 2008 BAE Systems Advanced Technology
Centre Centre
B. Adamson B. Adamson
Naval Research Laboratory Naval Research Laboratory
June 29, 2007 August 24, 2007
Jitter considerations in MANETs Jitter considerations in MANETs
draft-ietf-manet-jitter-01 draft-ietf-manet-jitter-02
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 38 skipping to change at page 1, line 38
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on December 31, 2007. This Internet-Draft will expire on February 25, 2008.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2007).
Abstract Abstract
This document provides recommendations for jittering (randomly This document provides recommendations for jittering (randomly
modifying timing) of control traffic transmissions in MANET routing modifying timing) of control traffic transmissions in MANET routing
protocols to reduce the probability of packet collisions. protocols to reduce the probability of packet collisions.
skipping to change at page 2, line 22 skipping to change at page 2, line 22
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6
5. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.1. Periodic Message Generation . . . . . . . . . . . . . . . 7 5.1. Periodic Message Generation . . . . . . . . . . . . . . . 7
5.2. Externally Triggered Message Generation . . . . . . . . . 8 5.2. Externally Triggered Message Generation . . . . . . . . . 8
5.3. Message Forwarding . . . . . . . . . . . . . . . . . . . . 9 5.3. Message Forwarding . . . . . . . . . . . . . . . . . . . . 9
5.4. Maximum Jitter Determination . . . . . . . . . . . . . . . 10 5.4. Maximum Jitter Determination . . . . . . . . . . . . . . . 10
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
7. Security Considerations . . . . . . . . . . . . . . . . . . . 12 7. Security Considerations . . . . . . . . . . . . . . . . . . . 13
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.1. Normative References . . . . . . . . . . . . . . . . . . . 13 8.1. Normative References . . . . . . . . . . . . . . . . . . . 14
8.2. Informative References . . . . . . . . . . . . . . . . . . 13 8.2. Informative References . . . . . . . . . . . . . . . . . . 14
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 14 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 15
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16
Intellectual Property and Copyright Statements . . . . . . . . . . 16 Intellectual Property and Copyright Statements . . . . . . . . . . 17
1. Introduction 1. Introduction
In a wireless network, simultaneous packet transmission by nearby In a wireless network, simultaneous packet transmission by nearby
nodes is undesirable as, depending on the medium access control and nodes is undesirable as, depending on the medium access control and
other lower layer mechanisms, the interference between these other lower layer mechanisms, the interference between these
transmissions may cause at best increased delay, and at worst transmissions may cause at best increased delay, and at worst
complete packet loss. complete packet loss.
The problems of simultaneous packet transmissions are amplified if The problems of simultaneous packet transmissions are amplified if
skipping to change at page 3, line 40 skipping to change at page 3, line 40
apparent reason why it should not restart its corresponding apparent reason why it should not restart its corresponding
message schedule. This may result in nodes responding to the same message schedule. This may result in nodes responding to the same
change also sending future messages simultaneously. change also sending future messages simultaneously.
Forwarding - If nodes forward messages they receive from other Forwarding - If nodes forward messages they receive from other
nodes, then nearby nodes will commonly receive and forward the nodes, then nearby nodes will commonly receive and forward the
same message. If forwarding is performed immediately then the same message. If forwarding is performed immediately then the
resulting packet transmissions may interfere with each other. resulting packet transmissions may interfere with each other.
A possible solution to these problems is to employ jitter, a A possible solution to these problems is to employ jitter, a
deliberate random variation in timing. This document discusses deliberate random variation in timing. Such jitter is employed in
applying jitter to packet transmissions, with the purpose of avoiding e.g. [2], [3] and [4], in which transmission intervals are reduced by
collisions, with particular reference to the features listed above. a small, bounded and random percentage in order to desynchronize
transmitters and thereby avoid overloading the transmission medium as
well as receivers. This document discusses applying jitter to packet
transmissions in Mobile Ad hoc NETworks (MANETs), with the purpose of
avoiding collisions, with particular reference to the features listed
above.
2. Terminology 2. Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [1]. document are to be interpreted as described in RFC2119 [1].
Additionally, this document uses the following terminology: Additionally, this document uses the following terminology:
Node - A MANET router which implements a message sending protocol. Node - A MANET router which implements a message sending protocol.
skipping to change at page 5, line 14 skipping to change at page 5, line 14
3. Applicability Statement 3. Applicability Statement
The mechanisms described in this document are applicable to any MANET The mechanisms described in this document are applicable to any MANET
protocol in which simultaneous transmissions by different nodes are protocol in which simultaneous transmissions by different nodes are
undesirable and which contains mechanisms, such as periodic message undesirable and which contains mechanisms, such as periodic message
transmission, triggered message transmission, or message forwarding, transmission, triggered message transmission, or message forwarding,
which either make the simultaneous transmission more likely, or cause which either make the simultaneous transmission more likely, or cause
it to be repeated when it occurs. This particularly applies to it to be repeated when it occurs. This particularly applies to
protocols using broadcast transmissions in wireless networks, where protocols using broadcast transmissions in wireless networks, where
proactive MANET routing protocols such as [2] employ scheduled proactive MANET routing protocols such as [5] employ scheduled
messages, where reactive MANET routing protocols such as [3] employ messages, where reactive MANET routing protocols such as [6] employ
event-triggered messages, and where both employ message forwarding. event-triggered messages, and where both employ message forwarding.
These mechanisms are intended for application where the underlying These mechanisms are intended for application where the underlying
medium access control and lower layers do not provide effective medium access control and lower layers do not provide effective
mechanisms to avoid such collisions. Where these layers do provide mechanisms to avoid such collisions. Where these layers do provide
effective mechanisms, the approach of this document is not needed. effective mechanisms, the approach of this document is not needed.
The approach described in this document uses random variations in The approach described in this document uses random variations in
timing to achieve a reduction in collisions. Alternatives using, for timing to achieve a reduction in collisions. Alternatives using, for
example, pseudo-random variation based on node identity, may be example, pseudo-random variation based on node identity, may be
considered, but are not discussed by this document. considered, but are not discussed by this document.
Any protocol based on [4] and using the message forwarding mechanism Any protocol based on [7] and using the message forwarding mechanism
facilitated by that structure is a particular candidate for facilitated by that structure is a particular candidate for
application of at least some of these mechanisms. application of at least some of these mechanisms.
The document has been generalized from the jitter mechanism used in The document has been generalized from the jitter mechanism used in
the proactive MANET routing protocol OLSR (The Optimized Link State the proactive MANET routing protocol OLSR (The Optimized Link State
Routing Protocol) [2]. Routing Protocol) [5].
4. Protocol Overview and Functioning 4. Protocol Overview and Functioning
This document does not specify a protocol, nor does it mandate This document does not specify a protocol, nor does it mandate
specific node or protocol behavior. Rather, it outlines mechanisms specific node or protocol behavior. Rather, it outlines mechanisms
for message transmission (and retransmission) applicable in MANET for message transmission (and retransmission) applicable in MANET
routing protocols and other protocols employing a periodic or routing protocols and other protocols employing a periodic or
triggered message schedule and running over wireless interfaces where triggered message schedule and running over wireless interfaces where
simultaneous transmissions from two (or more) adjacent nodes causes simultaneous transmissions from two (or more) adjacent nodes causes
delays, packet losses and other problems. Any protocol using jitter delays, packet losses and other problems. Any protocol using jitter
skipping to change at page 8, line 38 skipping to change at page 8, line 38
messages treated as described in Section 5.1. messages treated as described in Section 5.1.
When messages are triggered, whether or not they are also When messages are triggered, whether or not they are also
periodically transmitted, a protocol MAY impose a minimum interval periodically transmitted, a protocol MAY impose a minimum interval
between messages of the same type, denoted MESSAGE_MIN_INTERVAL. It between messages of the same type, denoted MESSAGE_MIN_INTERVAL. It
is however appropriate to also allow this interval to be reduced by is however appropriate to also allow this interval to be reduced by
jitter, so that when a message is transmitted the next message is jitter, so that when a message is transmitted the next message is
allowed after a time (MESSAGE_MIN_INTERVAL - jitter), where jitter allowed after a time (MESSAGE_MIN_INTERVAL - jitter), where jitter
SHOULD be generated uniformly in an interval between zero and SHOULD be generated uniformly in an interval between zero and
MAXJITTER (using a value of MAXJITTER appropriate to periodic message MAXJITTER (using a value of MAXJITTER appropriate to periodic message
transmission). This is because otherwise, when external triggers are transmission).
more frequent than MESSAGE_MIN_INTERVAL, it takes the role of
MESSAGE_INTERVAL and the arguments applying to jittering of the It might appear counterintuitive to have a defined
latter also apply to the former. This also permits MESSAGE_MIN_INTERVAL, yet allow this to be reduced by jittering. For
MESSAGE_MIN_INTERVAL to equal MESSAGE_INTERVAL even when jitter is periodic messages, setting MESSAGE_INTERVAL, MAXJITTER and
used. MESSAGE_MIN_INTERVAL such that (MESSAGE_INTERVAL-MAXJITTER) >
MESSAGE_MIN_INTERVAL would ensure at least MESSAGE_MIN_INTERVAL would
elapse between two subsequent message transmissions. In a highly
dynamic network with triggered messages, however, external
circumstances might be such that external triggers are more frequent
than MESSAGE_MIN_INTERVAL, effectively making MESSAGE_MIN_INTERVAL
take the role of MESSAGE_INTERVAL as the "default" interval at which
messages are transmitted. Thus, in order to avoid synchronization
also in this highly dynamic case, jitterering should be applied to
MESSAGE_MIN_INTERVAL. This also permits MESSAGE_MIN_INTERVAL to
equal MESSAGE_INTERVAL even when jitter is used.
When a triggered message is delayed by jitter, the node MAY also When a triggered message is delayed by jitter, the node MAY also
postpone generation of the triggered message. If a node is then postpone generation of the triggered message. If a node is then
triggered to generate a message of the same type while waiting, it triggered to generate a message of the same type while waiting, it
can generate a single message. If however the node generates a can generate a single message. If however the node generates a
message when it is triggered, and then receives a another trigger message when it is triggered, and then receives a another trigger
while waiting to send that message then the appropriate action to while waiting to send that message then the appropriate action to
take is protocol specific (typically to discard the earlier message take is protocol specific (typically to discard the earlier message
or to transmit both, possibly modifying timing to maintain message or to transmit both, possibly modifying timing to maintain message
order). order).
skipping to change at page 9, line 32 skipping to change at page 9, line 42
MESSAGE_INTERVAL based on received message times. MESSAGE_INTERVAL based on received message times.
For several possible reasons (differing parameters, message For several possible reasons (differing parameters, message
rescheduling, extreme random values) a node may receive a message rescheduling, extreme random values) a node may receive a message
while still waiting to forward an earlier message of the same type while still waiting to forward an earlier message of the same type
originating from the same node. This is possible without jitter, but originating from the same node. This is possible without jitter, but
may occur more often with it. The appropriate action to take is may occur more often with it. The appropriate action to take is
protocol specific (typically to discard the earlier message or to protocol specific (typically to discard the earlier message or to
forward both, possible modifying timing to maintain message order). forward both, possible modifying timing to maintain message order).
In many cases, including [2] and protocols using the full In many cases, including [5] and protocols using the full
functionality of [4], messages are transmitted hop by hop in functionality of [7], messages are transmitted hop by hop in
potentially multi-message packets, and some or all of those messages potentially multi-message packets, and some or all of those messages
may need to be forwarded. For efficiency this should be in a single may need to be forwarded. For efficiency this should be in a single
packet, and hence the forwarding jitter of all messages received in a packet, and hence the forwarding jitter of all messages received in a
single packet should be the same. (This also requires that a single single packet should be the same. (This also requires that a single
value of MAXJITTER is used in this case.) For this to have the value of MAXJITTER is used in this case.) For this to have the
intended uniform distribution it is necessary to choose a single intended uniform distribution it is necessary to choose a single
random jitter for all messages. It is not appropriate to give each random jitter for all messages. It is not appropriate to give each
message a random jitter and then to use the smallest of these jitter message a random jitter and then to use the smallest of these jitter
values, as that produces a jitter with a non-uniform distribution and values, as that produces a jitter with a non-uniform distribution and
a reduced mean value. a reduced mean value.
skipping to change at page 10, line 27 skipping to change at page 10, line 37
o When messages are periodically generated, all of the following o When messages are periodically generated, all of the following
that are relevant apply to each instance of MAXJITTER: that are relevant apply to each instance of MAXJITTER:
* it MUST NOT be negative; * it MUST NOT be negative;
* it MUST NOT be greater than MESSAGE_INTERVAL/2; * it MUST NOT be greater than MESSAGE_INTERVAL/2;
* it SHOULD be significantly less than MESSAGE_INTERVAL; * it SHOULD be significantly less than MESSAGE_INTERVAL;
* it MUST NOT be greater than MESSAGE_MIN_INTERVAL; o If MESSAGE_MIN_INTERVAL > 0, then:
* it SHOULD NOT be greater than MESSAGE_MIN_INTERVAL/2. * MAXJITTER MUST NOT be greater than MESSAGE_MIN_INTERVAL;
* MAXJITTER SHOULD NOT be greater than MESSAGE_MIN_INTERVAL/2.
o As well as the decision as to whether to use jitter being o As well as the decision as to whether to use jitter being
dependent on the medium access control and lower layers, the dependent on the medium access control and lower layers, the
selection of the MAXJITTER parameter should be appropriate to selection of the MAXJITTER parameter should be appropriate to
those mechanisms. those mechanisms.
o As jitter is intended to reduce collisions, greater jitter, i.e. o As jitter is intended to reduce collisions, greater jitter, i.e.
an increased value of MAXJITTER, is appropriate when the chance of an increased value of MAXJITTER, is appropriate when the chance of
collisions is greater. This is particularly the case with collisions is greater. This is particularly the case with
increased node density, where node density should be considered increased node density, where node density should be considered
skipping to change at page 13, line 14 skipping to change at page 14, line 14
8. References 8. References
8.1. Normative References 8.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, BCP 14, March 1997. Levels", RFC 2119, BCP 14, March 1997.
8.2. Informative References 8.2. Informative References
[2] Clausen, T. and P. Jacquet, "The Optimized Link State Routing [2] Moy, J., "OSPF Database Overflow", RFC 1768, March 1995.
[3] Marlow, D., "Host Group Extensions for CLNP Multicasting",
RFC 1768, March 1995.
[4] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 4
(BGP-4)", RFC 4271, January 2006.
[5] Clausen, T. and P. Jacquet, "The Optimized Link State Routing
Protocol", RFC 3626, October 2003. Protocol", RFC 3626, October 2003.
[3] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand [6] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand
Distance Vector (AODV) Routing", RFC 3561, July 2003. Distance Vector (AODV) Routing", RFC 3561, July 2003.
[4] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized [7] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized
MANET Packet/Message Format", Work In MANET Packet/Message Format", Work In
Progress draft-ietf-manet-packetbb-07.txt, June 2007. Progress draft-ietf-manet-packetbb-07.txt, June 2007.
Appendix A. Acknowledgements Appendix A. Acknowledgements
The authors would like to acknowledge the MANET working group and the The authors would like to acknowledge the MANET working group and the
OLSRv2 Design team, in particular Joe Macker and Justin Dean (both OLSRv2 Design team, in particular Joe Macker and Justin Dean (both
NRL), for their contributions and discussions in developing and NRL), for their contributions and discussions in developing and
testing the concepts retained in this document, and Alan Cullen (BAE testing the concepts retained in this document, and Alan Cullen (BAE
Systems) for his careful review of this specification. OLSRv1, as Systems) for his careful review of this specification. OLSRv1, as
specified in [2], introduced the concept of jitter on control specified in [5], introduced the concept of jitter on control
traffic, which was tested thoroughly by Gitte Hansen and Lars traffic, which was tested thoroughly by Gitte Hansen and Lars
Christensen (then, both Aalborg University). Christensen (then, both Aalborg University).
Authors' Addresses Authors' Addresses
Thomas Heide Clausen Thomas Heide Clausen
LIX, Ecole Polytechnique, France LIX, Ecole Polytechnique, France
Phone: +33 6 6058 9349 Phone: +33 6 6058 9349
Email: T.Clausen@computer.org Email: T.Clausen@computer.org
 End of changes. 17 change blocks. 
33 lines changed or deleted 58 lines changed or added

This html diff was produced by rfcdiff 1.34. The latest version is available from http://tools.ietf.org/tools/rfcdiff/