Network Working Group T. Clausen Request for Comments: 5148 LIX, Ecole Polytechnique, France Category: Informational C. Dearlove BAE Systems Advanced Technology Centre B. Adamson U.S. Naval Research Laboratory February 2008 Jitter Considerations in Mobile Ad Hoc Networks (MANETs) Status of This Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
AbstractThis document provides recommendations for jittering (randomly modifying timing) of control traffic transmissions in Mobile Ad hoc NETwork (MANET) routing protocols to reduce the probability of transmission collisions. 1. Introduction ....................................................2 2. Terminology .....................................................3 3. Applicability Statement .........................................4 4. Protocol Overview and Functioning ...............................4 5. Jitter ..........................................................5 5.1. Periodic Message Generation ................................5 5.2. Externally Triggered Message Generation ....................6 5.3. Message Forwarding .........................................7 5.4. Maximum Jitter Determination ...............................8 6. Security Considerations .........................................9 7. References .....................................................10 7.1. Normative References ......................................10 7.2. Informative References ....................................10 Appendix A. Acknowledgements ......................................11
A possible solution to these problems is to employ jitter, a deliberate random variation in timing. Such jitter is employed in e.g., , , and , in which transmission intervals for regularly scheduled messages are reduced by a small, bounded and random amount in order to desynchronize transmitters and thereby avoid overloading the transmission medium as well as receivers. This document discusses and provides recommendations for applying jitter to control packet transmissions in Mobile Ad hoc NETworks (MANETs), with the purpose of avoiding collisions, with particular reference to the features listed above. RFC2119 . Additionally, this document uses the following terminology: Node - A MANET router that implements a message sending protocol. MANET interface - A network device participating in a MANET. A node may have one or more MANET interfaces. Message - An entity carrying protocol information intended for exchange between nodes. Messages are transmitted over MANET interfaces embedded in packets. Packet - An entity embedding zero or more messages for transmission over a MANET interface of the node. Transmission - A packet being sent over a MANET interface of the node. A transmission can be due to either a message being generated or a message being forwarded. Generation - Creation of a new message (rather than a received and forwarded message) for transmission over one or more MANET interfaces of the node. Typically, a node will generate messages based on a message schedule (periodic or otherwise) or as a response to changes in circumstances. Forwarding - Retransmission of a received message (whether modified or unchanged) over one or more MANET interfaces of the node. Collision - A specific instance of interference, where two or more nodes transmit a packet at the same time and within the same signal space (at the same frequency and/or encoding) such that
another, closely located, node that should receive and decode these packets instead fails to do so, and loses one or more of the packets. 5] employ scheduled messages, where reactive MANET routing protocols such as  employ event-triggered messages, and where both employ message forwarding. These mechanisms are intended for application where the underlying medium access control and lower layers do not provide effective mechanisms to avoid such collisions. Where these layers do provide effective mechanisms, the recommendations of this document are not needed. The approach described in this document uses random variations in timing to achieve a reduction in collisions. Alternatives using, for example, pseudo-random variation based on node identity, may be considered, but are not discussed by this document. Any protocol based on  and using the message forwarding mechanism facilitated by that structure is a particular candidate for application of at least some of these mechanisms. The document has been generalized from the jitter mechanism used in the proactive MANET routing protocol OLSR (the Optimized Link State Routing Protocol) .
not adversely affect timeouts or other mechanisms that may be based on message late arrival or failure to arrive. By basing the message transmission time on the previous transmission time, rather than by jittering a fixed clock, nodes can become completely desynchronized, which minimizes their probability of repeated collisions. This is particularly useful when combined with externally triggered message generation and rescheduling. The jitter value SHOULD be generated uniformly in an interval between zero and MAXJITTER. Note that a node will know its own MESSAGE_INTERVAL value and can readily ensure that any MAXJITTER value used satisfies the conditions in Section 5.4. Section 5.1. When messages are triggered, whether or not they are also periodically transmitted, a protocol MAY impose a minimum interval between messages of the same type, denoted MESSAGE_MIN_INTERVAL. In the case that such an interval is not required, MESSAGE_MIN_INTERVAL is considered to be zero. When MESSAGE_MIN_INTERVAL is non-zero, it is however appropriate to also allow this interval to be reduced by jitter. Thus, when a message is transmitted, the next message is allowed after a time (MESSAGE_MIN_INTERVAL - jitter). This jitter SHOULD be generated uniformly in an interval between zero and MAXJITTER (using a value of MAXJITTER appropriate to periodic message transmission). It might appear counterintuitive to have a defined MESSAGE_MIN_INTERVAL, yet allow this to be reduced by jittering. For periodic messages, setting MESSAGE_INTERVAL, MAXJITTER and 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 in this highly dynamic case, jittering 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 postpone generation of the triggered message. If a node is then triggered to generate a message of the same type while waiting, it can generate a single message. If however the node generates a message when it is triggered, and then receives a another trigger while waiting to send that message, then the appropriate action to take is protocol specific (typically to discard the earlier message or to transmit both, possibly modifying timing to maintain message order). 5] and protocols using the full functionality of , messages are transmitted hop-by-hop in
potentially multi-message packets, and some or all of those messages 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 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 intended uniform distribution, it is necessary to choose a single 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 values, as that produces a jitter with a non-uniform distribution and a reduced mean value. In addition, the protocol MAY permit control messages received in different packets to be combined, possibly also with locally generated control messages (periodically generated or triggered), as supported by . However, in this case, the purpose of the jitter will be accomplished by choosing any of the independently scheduled times for these events as the single forwarding time; this may have to be the earliest time to achieve all constraints. This is because without combining messages, a transmission would be due at this time anyway.
o As well as the decision as to whether to use jitter being dependent on the medium access control and lower layers, the selection of the MAXJITTER parameter SHOULD be appropriate to those mechanisms. For example, MAXJITTER should be significantly greater than (e.g., an order of magnitude greater than) any medium access control frame period. o As jitter is intended to reduce collisions, greater jitter, i.e., an increased value of MAXJITTER, is appropriate when the chance of collisions is greater. This is particularly the case with increased node density, which is significant relative to (the square of) the interference range rather than useful signal range. o The choice of MAXJITTER used when forwarding messages MAY also take into account the expected number of times that the message may be sequentially forwarded, up to the network diameter in hops, so that the maximum accumulated delay is bounded.
 Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.  Moy, J., "OSPF Database Overflow", RFC 1765, March 1995.  Marlow, D., "Host Group Extensions for CLNP Multicasting", RFC 1768, March 1995.  Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A Border Gateway Protocol 4 (BGP-4)", RFC 4271, January 2006.  Clausen, T., Ed., and P. Jacquet, Ed., "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003.  Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003.  Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized MANET Packet/Message Format", Work in Progress.
5], introduced the concept of jitter on control traffic, which was tested thoroughly by Gitte Hansen and Lars Christensen (then, both Aalborg University). http://www.ThomasClausen.org/ Christopher Dearlove BAE Systems Advanced Technology Centre Phone: +44 1245 242194 EMail: firstname.lastname@example.org URI: http://www.baesystems.com/ Brian Adamson U.S. Naval Research Laboratory Phone: +1 202 404 1194 EMail: email@example.com URI: http://www.nrl.navy.mil/
Full Copyright Statement Copyright (C) The IETF Trust (2008). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at firstname.lastname@example.org.