--- 1/draft-ietf-manet-jitter-01.txt 2007-08-28 22:12:13.000000000 +0200 +++ 2/draft-ietf-manet-jitter-02.txt 2007-08-28 22:12:13.000000000 +0200 @@ -1,22 +1,22 @@ Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Intended status: Informational C. Dearlove -Expires: December 31, 2007 BAE Systems Advanced Technology +Expires: February 25, 2008 BAE Systems Advanced Technology Centre B. Adamson Naval Research Laboratory - June 29, 2007 + August 24, 2007 Jitter considerations in MANETs - draft-ietf-manet-jitter-01 + draft-ietf-manet-jitter-02 Status of this Memo By submitting this Internet-Draft, each author represents that any 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 aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that @@ -27,21 +27,21 @@ 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at 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 (C) The IETF Trust (2007). Abstract This document provides recommendations for jittering (randomly modifying timing) of control traffic transmissions in MANET routing protocols to reduce the probability of packet collisions. @@ -50,28 +50,28 @@ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 5. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5.1. Periodic Message Generation . . . . . . . . . . . . . . . 7 5.2. Externally Triggered Message Generation . . . . . . . . . 8 5.3. Message Forwarding . . . . . . . . . . . . . . . . . . . . 9 5.4. Maximum Jitter Determination . . . . . . . . . . . . . . . 10 - 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 - 7. Security Considerations . . . . . . . . . . . . . . . . . . . 12 - 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 - 8.1. Normative References . . . . . . . . . . . . . . . . . . . 13 - 8.2. Informative References . . . . . . . . . . . . . . . . . . 13 - Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 14 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15 - Intellectual Property and Copyright Statements . . . . . . . . . . 16 + 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 + 7. Security Considerations . . . . . . . . . . . . . . . . . . . 13 + 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14 + 8.1. Normative References . . . . . . . . . . . . . . . . . . . 14 + 8.2. Informative References . . . . . . . . . . . . . . . . . . 14 + Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 15 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16 + Intellectual Property and Copyright Statements . . . . . . . . . . 17 1. Introduction In a wireless network, simultaneous packet transmission by nearby nodes is undesirable as, depending on the medium access control and other lower layer mechanisms, the interference between these transmissions may cause at best increased delay, and at worst complete packet loss. The problems of simultaneous packet transmissions are amplified if @@ -94,23 +94,28 @@ apparent reason why it should not restart its corresponding message schedule. This may result in nodes responding to the same change also sending future messages simultaneously. Forwarding - If nodes forward messages they receive from other nodes, then nearby nodes will commonly receive and forward the same message. If forwarding is performed immediately then the resulting packet transmissions may interfere with each other. A possible solution to these problems is to employ jitter, a - deliberate random variation in timing. This document discusses - applying jitter to packet transmissions, with the purpose of avoiding - collisions, with particular reference to the features listed above. + deliberate random variation in timing. Such jitter is employed in + e.g. [2], [3] and [4], in which transmission intervals are reduced by + 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 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [1]. Additionally, this document uses the following terminology: Node - A MANET router which implements a message sending protocol. @@ -146,41 +151,41 @@ 3. Applicability Statement The mechanisms described in this document are applicable to any MANET protocol in which simultaneous transmissions by different nodes are undesirable and which contains mechanisms, such as periodic message transmission, triggered message transmission, or message forwarding, which either make the simultaneous transmission more likely, or cause it to be repeated when it occurs. This particularly applies to protocols using broadcast transmissions in wireless networks, where - proactive MANET routing protocols such as [2] employ scheduled - messages, where reactive MANET routing protocols such as [3] employ + proactive MANET routing protocols such as [5] employ scheduled + messages, where reactive MANET routing protocols such as [6] 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 approach of this document is 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 [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 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) [2]. + Routing Protocol) [5]. 4. Protocol Overview and Functioning This document does not specify a protocol, nor does it mandate specific node or protocol behavior. Rather, it outlines mechanisms for message transmission (and retransmission) applicable in MANET routing protocols and other protocols employing a periodic or triggered message schedule and running over wireless interfaces where simultaneous transmissions from two (or more) adjacent nodes causes delays, packet losses and other problems. Any protocol using jitter @@ -262,26 +267,36 @@ messages treated as described in 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. It is however appropriate to also allow this interval to be reduced by jitter, so that when a message is transmitted the next message is allowed after a time (MESSAGE_MIN_INTERVAL - jitter), where jitter SHOULD be generated uniformly in an interval between zero and MAXJITTER (using a value of MAXJITTER appropriate to periodic message - transmission). This is because otherwise, when external triggers are - more frequent than MESSAGE_MIN_INTERVAL, it takes the role of - MESSAGE_INTERVAL and the arguments applying to jittering of the - latter also apply to the former. This also permits - MESSAGE_MIN_INTERVAL to equal MESSAGE_INTERVAL even when jitter is - used. + 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 + 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 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). @@ -304,22 +319,22 @@ MESSAGE_INTERVAL based on received message times. For several possible reasons (differing parameters, message rescheduling, extreme random values) a node may receive a message while still waiting to forward an earlier message of the same type originating from the same node. This is possible without jitter, but may occur more often with it. The appropriate action to take is protocol specific (typically to discard the earlier message or to forward both, possible modifying timing to maintain message order). - In many cases, including [2] and protocols using the full - functionality of [4], messages are transmitted hop by hop in + In many cases, including [5] and protocols using the full + functionality of [7], 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. @@ -347,23 +362,25 @@ o When messages are periodically generated, all of the following that are relevant apply to each instance of MAXJITTER: * it MUST NOT be negative; * it MUST NOT be greater than MESSAGE_INTERVAL/2; * 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 dependent on the medium access control and lower layers, the selection of the MAXJITTER parameter should be appropriate to those mechanisms. 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, where node density should be considered @@ -384,38 +401,46 @@ 8. References 8.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. 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. - [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. - [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 Progress draft-ietf-manet-packetbb-07.txt, June 2007. Appendix A. Acknowledgements The authors would like to acknowledge the MANET working group and the OLSRv2 Design team, in particular Joe Macker and Justin Dean (both NRL), for their contributions and discussions in developing and testing the concepts retained in this document, and Alan Cullen (BAE 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 Christensen (then, both Aalborg University). Authors' Addresses Thomas Heide Clausen LIX, Ecole Polytechnique, France Phone: +33 6 6058 9349 Email: T.Clausen@computer.org