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/