draft-ietf-roll-trickle-06.txt		draft-ietf-roll-trickle-07.txt
	Networking Working Group P. Levis		Networking Working Group P. Levis
	Internet-Draft Stanford University		Internet-Draft Stanford University
	Intended status: Standards Track T. Clausen		Intended status: Standards Track T. Clausen
	Expires: June 9, 2011 LIX, Ecole Polytechnique		Expires: July 9, 2011 LIX, Ecole Polytechnique
	J. Hui		J. Hui
	Arch Rock Corporation		Arch Rock Corporation
	O. Gnawali		O. Gnawali
	Stanford University		Stanford University
	J. Ko		J. Ko
	Johns Hopkins University		Johns Hopkins University
	December 6, 2010		January 5, 2011
	The Trickle Algorithm		The Trickle Algorithm
	draft-ietf-roll-trickle-06		draft-ietf-roll-trickle-07
	Abstract		Abstract
	The Trickle algorithm allows nodes in a lossy shared medium (e.g.,		The Trickle algorithm allows nodes in a lossy shared medium (e.g.,
	low power and lossy networks) to exchange information in a highly		low power and lossy networks) to exchange information in a highly
	robust, energy efficient, simple, and scalable manner. Dynamically		robust, energy efficient, simple, and scalable manner. Dynamically
	adjusting transmission windows allows Trickle to spread new		adjusting transmission windows allows Trickle to spread new
	information on the scale of link-layer transmission times while		information on the scale of link-layer transmission times while
	sending only a few messages per hour when information does not		sending only a few messages per hour when information does not
	change. A simple suppression mechanism and transmission point		change. A simple suppression mechanism and transmission point
	skipping to change at page 1, line 46		skipping to change at page 1, line 46
	Internet-Drafts are working documents of the Internet Engineering		Internet-Drafts are working documents of the Internet Engineering
	Task Force (IETF). Note that other groups may also distribute		Task Force (IETF). Note that other groups may also distribute
	working documents as Internet-Drafts. The list of current Internet-		working documents as Internet-Drafts. The list of current Internet-
	Drafts is at http://datatracker.ietf.org/drafts/current/.		Drafts is at http://datatracker.ietf.org/drafts/current/.
	Internet-Drafts are draft documents valid for a maximum of six months		Internet-Drafts are draft documents valid for a maximum of six months
	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."
	This Internet-Draft will expire on June 9, 2011.		This Internet-Draft will expire on July 9, 2011.
	Copyright Notice		Copyright Notice
	Copyright (c) 2010 IETF Trust and the persons identified as the		Copyright (c) 2011 IETF Trust and the persons identified as the
	document authors. All rights reserved.		document authors. All rights reserved.
	This document is subject to BCP 78 and the IETF Trust's Legal		This document is subject to BCP 78 and the IETF Trust's Legal
	Provisions Relating to IETF Documents		Provisions Relating to IETF Documents
	(http://trustee.ietf.org/license-info) in effect on the date of		(http://trustee.ietf.org/license-info) in effect on the date of
	publication of this document. Please review these documents		publication of this document. Please review these documents
	carefully, as they describe your rights and restrictions with respect		carefully, as they describe your rights and restrictions with respect
	to this document. Code Components extracted from this document must		to this document. Code Components extracted from this document must
	include Simplified BSD License text as described in Section 4.e of		include Simplified BSD License text as described in Section 4.e of
	the Trust Legal Provisions and are provided without warranty as		the Trust Legal Provisions and are provided without warranty as
	skipping to change at page 2, line 29		skipping to change at page 2, line 29
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
	2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3		2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
	3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4		3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4
	4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5		4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5
	4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5		4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5
	4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6		4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6
	5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6		5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6
	6. Operational Considerations . . . . . . . . . . . . . . . . . . 7		6. Operational Considerations . . . . . . . . . . . . . . . . . . 7
	6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7		6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7
	6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7		6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7
	6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 7		6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 8
	6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8		6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8
	6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8		6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8
	6.6. Relationship Between k and Imin . . . . . . . . . . . . . 8		6.6. Relationship Between k and Imin . . . . . . . . . . . . . 9
	6.7. Tweaks and Improvements to Trickle . . . . . . . . . . . . 9		6.7. Tweaks and Improvements to Trickle . . . . . . . . . . . . 9
	6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9		6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9
	7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10		7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
	8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10		8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
	9. Security Considerations . . . . . . . . . . . . . . . . . . . 10		9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
	10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11		10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
	10.1. Normative References . . . . . . . . . . . . . . . . . . . 11		10.1. Normative References . . . . . . . . . . . . . . . . . . . 11
	10.2. Informative References . . . . . . . . . . . . . . . . . . 11		10.2. Informative References . . . . . . . . . . . . . . . . . . 11
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
	skipping to change at page 4, line 30		skipping to change at page 4, line 30
	respond in milliseconds.		respond in milliseconds.
	Trickle sends all messages to a local communication address. The		Trickle sends all messages to a local communication address. The
	exact address used can depend on both the underlying IP protocol as		exact address used can depend on both the underlying IP protocol as
	well as how the higher layer protocol uses Trickle. In IPv6, for		well as how the higher layer protocol uses Trickle. In IPv6, for
	example, it can be the link-local multicast address or another local		example, it can be the link-local multicast address or another local
	multicast address, while in IPv4 it can be the broadcast address		multicast address, while in IPv4 it can be the broadcast address
	(255.255.255.255).		(255.255.255.255).
	There are two possible results to a Trickle message: either every		There are two possible results to a Trickle message: either every
	node that hears the message finds its data is consistent with their		node that hears the message finds the message data is consistent with
	own state, or a recipient detects an inconsistency. Detection can be		its own state, or a recipient detects an inconsistency. Detection
	the result of either an out-of-date node hearing something new, or an		can be the result of either an out-of-date node hearing something
	updated node hearing something old. As long as every node		new, or an updated node hearing something old. As long as every node
	communicates somehow - either receives or transmits - some node will		communicates somehow - either receives or transmits - some node will
	detect the need for an update.		detect the need for an update.
	For example, consider a simple case where "up to date" is defined by		For example, consider a simple case where "up to date" is defined by
	version numbers (e.g., network configuration). If node A transmits		version numbers (e.g., network configuration). If node A transmits
	that it has version V, but B has version V+1, then B knows that A		that it has version V, but B has version V+1, then B knows that A
	needs an update. Similarly, if B transmits that it has version V+1,		needs an update. Similarly, if B transmits that it has version V+1,
	A knows that it needs an update. If B broadcasts or multicasts		A knows that it needs an update. If B broadcasts or multicasts
	updates, then all of its neighbors can receive them without having to		updates, then all of its neighbors can receive them without having to
	advertise their need. Some of these recipients might not even have		advertise their need. Some of these recipients might not have even
	heard A's transmission.		heard A's transmission.
	In this example, it does not matter who first transmits, A or B;		In this example, it does not matter who first transmits, A or B;
	either case will detect the inconsistency. All that matters is that		either case will detect the inconsistency. All that matters is that
	some nodes communicate with one another at some nonzero rate. As		some nodes communicate with one another at some nonzero rate. As
	long as the network is connected and there is some minimum		long as the network is connected and there is some minimum
	communication rate for each node, the network will reach eventual		communication rate for each node, the network will reach eventual
	consistency.		consistency.
	The fact that Trickle communication can be either transmission or		The fact that Trickle communication can be either transmission or
	skipping to change at page 6, line 37		skipping to change at page 6, line 37
	timer resets, Trickle sets I to Imin, resets c to 0, and sets t		timer resets, Trickle sets I to Imin, resets c to 0, and sets t
	to random point in the interval, taken from the range [I/2, I),		to random point in the interval, taken from the range [I/2, I),
	that is, values greater than or equal to I/2 and less than I. If		that is, values greater than or equal to I/2 and less than I. If
	I is equal to Imin, resetting a Trickle timer does nothing.		I is equal to Imin, resetting a Trickle timer does nothing.
	Trickle can also reset the timer in response to external		Trickle can also reset the timer in response to external
	"events."		"events."
	The terms consistent, inconsistent and event are in quotes because		The terms consistent, inconsistent and event are in quotes because
	their meaning depends on how a protocol uses Trickle.		their meaning depends on how a protocol uses Trickle.
			The only time the Trickle algorithm transmits is at step 3 of the
			above algorithm. This means there is an inherent delay between
			detecting an inconsistency (shrinking I to Imin) and responding to
			that inconsistency (transmitting at time t in the new interval).
			This is intentional. Immediately responding to detecting an
			inconsistency can cause a broadcast storm, where many nodes respond
			at once and in a synchronized fashion. By making responses follow
			the Trickle algorithm (with the minimal interval size), a protocol
			can benefit from Trickle's suppression mechanism and scale across a
			huge range of node densities.
	5. Using Trickle		5. Using Trickle
	A protocol specification that uses Trickle MUST specify:		A protocol specification that uses Trickle MUST specify:
	o Default values for Imin, Imax, and k. Because link layers can		o Default values for Imin, Imax, and k. Because link layers can
	vary widely in their properties, the default value of Imin SHOULD		vary widely in their properties, the default value of Imin SHOULD
	be specified in terms of the worst-case latency of a link layer		be specified in terms of the worst-case latency of a link layer
	transmission. For example, a specification should say "the		transmission. For example, a specification should say "the
	default value of Imin is 4 times the worst case link layer		default value of Imin is 4 times the worst case link layer
	latency" and should not say "the default value of Imin is 500		latency" and should not say "the default value of Imin is 500
	skipping to change at page 7, line 12		skipping to change at page 7, line 22
	first link-layer transmission of the frame assuming an idle		first link-layer transmission of the frame assuming an idle
	channel (does not include backoff, virtual carrier sense, etc.).		channel (does not include backoff, virtual carrier sense, etc.).
	o What constitutes a "consistent" transmission.		o What constitutes a "consistent" transmission.
	o What constitutes an "inconsistent" transmission.		o What constitutes an "inconsistent" transmission.
	o What "events," if any, besides inconsistent transmissions that		o What "events," if any, besides inconsistent transmissions that
	reset the Trickle timer.		reset the Trickle timer.
			o What information a node transmits in Trickle messages.
	6. Operational Considerations		6. Operational Considerations
	It is RECOMMENDED that a protocol which uses Trickle includes		It is RECOMMENDED that a protocol which uses Trickle includes
	mechanisms to inform nodes of configuration parameters at runtime.		mechanisms to inform nodes of configuration parameters at runtime.
	However, it is not always possible to do so. In the cases where		However, it is not always possible to do so. In the cases where
	different nodes have different configuration parameters, Trickle may		different nodes have different configuration parameters, Trickle may
	have unintended behaviors. This section outlines some of those		have unintended behaviors. This section outlines some of those
	behaviors and operational considerations as educational exercises.		behaviors and operational considerations as educational exercises.
	6.1. Mismatched Redundancy Constants		6.1. Mismatched Redundancy Constants
	skipping to change at page 12, line 4		skipping to change at page 12, line 14
	[Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for		[Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for
	wireless sensor networks", Proceedings of the 6th ACM		wireless sensor networks", Proceedings of the 6th ACM
	Conference on Embedded Networked Systems SenSys 2008,		Conference on Embedded Networked Systems SenSys 2008,
	November 2008,		November 2008,
	<http://portal.acm.org/citation.cfm?id=1460412.1460415>.		<http://portal.acm.org/citation.cfm?id=1460412.1460415>.
	[I-D.ietf-roll-rpl]		[I-D.ietf-roll-rpl]
	Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,		Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
	Kelsey, R., Levis, P., Pister, K., Struik, R., and J.		Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
	Vasseur, "RPL: IPv6 Routing Protocol for Low power and		Vasseur, "RPL: IPv6 Routing Protocol for Low power and
	Lossy Networks", draft-ietf-roll-rpl-15 (work in		Lossy Networks", draft-ietf-roll-rpl-17 (work in
	progress), November 2010.		progress), December 2010.
	[Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker,		[Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker,
	"Trickle: A Self-Regulating Algorithm for Code Propagation		"Trickle: A Self-Regulating Algorithm for Code Propagation
	and Maintenance in Wireless Sensor Networks"", Proceedings		and Maintenance in Wireless Sensor Networks"", Proceedings
	of the First USENIX/ACM Symposium on Networked Systems		of the First USENIX/ACM Symposium on Networked Systems
	Design and Implementation NSDI 2004, March 2004,		Design and Implementation NSDI 2004, March 2004,
	<http://portal.acm.org/citation.cfm?id=1251177>.		<http://portal.acm.org/citation.cfm?id=1251177>.
	[Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S.,		[Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S.,
	Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A.		Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A.
End of changes. 13 change blocks.
	15 lines changed or deleted		27 lines changed or added
This html diff was produced by rfcdiff 1.40. The latest version is available from http://tools.ietf.org/tools/rfcdiff/