draft-ietf-roll-trickle-03.txt		draft-ietf-roll-trickle-04.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: February 19, 2011 LIX, Ecole Polytechnique		Expires: February 20, 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
	August 18, 2010		August 19, 2010
	The Trickle Algorithm		The Trickle Algorithm
	draft-ietf-roll-trickle-03		draft-ietf-roll-trickle-04
	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
	selection allows Trickle's communication rate to scale		selection allows Trickle's communication rate to scale
	logarithmically with density. This document describes Trickle and		logarithmically with density. This document describes the Trickle
	considerations in its use.		algorithm and considerations in its use.
	Status of this Memo		Status of this Memo
	This Internet-Draft is submitted to IETF in full conformance with the		This Internet-Draft is submitted to IETF in full conformance with the
	provisions of BCP 78 and BCP 79.		provisions of BCP 78 and 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
	other groups may also distribute working documents as Internet-		other groups may also distribute working documents as Internet-
	Drafts.		Drafts.
	skipping to change at page 2, line 6		skipping to change at page 2, line 6
	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 February 19, 2011.		This Internet-Draft will expire on February 20, 2011.
	Copyright Notice		Copyright Notice
	Copyright (c) 2010 IETF Trust and the persons identified as the		Copyright (c) 2010 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
	described in the BSD License.		described in the BSD License.
	Table of Contents		Table of Contents
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
	2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3		2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
	3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 3		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 . . . . . . . . . . . . . . . . . . 5		4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6
	5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6		5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6
	6. Operational Considerations . . . . . . . . . . . . . . . . . . 6		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 . . . . . . . . . . . . . . . . . . . . . 7
	6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7		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 . . . . . . . . . . . . . 8
	6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8		6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8
	6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9		6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9
	7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9		7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
	8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10		8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
	9. Security Considerations . . . . . . . . . . . . . . . . . . . 10		9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
	10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10		10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
	10.1. Normative References . . . . . . . . . . . . . . . . . . . 10		10.1. Normative References . . . . . . . . . . . . . . . . . . . 10
	10.2. Informative References . . . . . . . . . . . . . . . . . . 10		10.2. Informative References . . . . . . . . . . . . . . . . . . 10
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
	1. Introduction		1. Introduction
	The Trickle algorithm establishes a density-aware local communication		The Trickle algorithm establishes a density-aware local communication
	skipping to change at page 4, line 29		skipping to change at page 4, line 29
	is simple to implement, and requires very little state. Current		is simple to implement, and requires very little state. Current
	implementations use 4-11 bytes of RAM and are 50-200 lines of C		implementations use 4-11 bytes of RAM and are 50-200 lines of C
	code[Levis08].		code[Levis08].
	While Trickle was originally designed for reprogramming protocols		While Trickle was originally designed for reprogramming protocols
	(where the data is the code of the program being updated), experience		(where the data is the code of the program being updated), experience
	has shown it to be a powerful mechanism that can be applied to wide		has shown it to be a powerful mechanism that can be applied to wide
	range of protocol design problems, including control traffic timing,		range of protocol design problems, including control traffic timing,
	multicast propagation, and route discovery. This flexibility stems		multicast propagation, and route discovery. This flexibility stems
	from being able to define, on a case-by-case basis, what constitutes		from being able to define, on a case-by-case basis, what constitutes
	"agreement" or an "inconsistency."		"agreement" or an "inconsistency;" Section Section 6.8 presents a few
			examples of how the algorithm can be used.
	This document describes the Trickle algorithm and provides guidelines		This document describes the Trickle algorithm and provides guidelines
	for its use. It also states requirements for protocol specifications		for its use. It also states requirements for protocol specifications
	that use Trickle. This document does not provide results on		that use Trickle. This document does not provide results on
	Trickle's performance or behavior, nor does it explain the		Trickle's performance or behavior, nor does it explain the
	algorithm's design in detail: interested readers should refer to		algorithm's design in detail: interested readers should refer to
	[Levis04] and [Levis08].		[Levis04] and [Levis08].
	2. Terminology		2. Terminology
	The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",		The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
	"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and		"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
	"OPTIONAL" in this document are to be interpreted as described in RFC		"OPTIONAL" in this document are to be interpreted as described in RFC
	2119 [RFC2119].		2119 [RFC2119].
			Additionally, this document introduces the following terminology:
			Trickle communication rate: the sum of the number of messages sent
			or received by the Trickle algorithm in an interval.
	3. Trickle Algorithm Overview		3. Trickle Algorithm Overview
	Trickle's basic primitive is simple: every so often, a node transmits		Trickle's basic primitive is simple: every so often, a node transmits
	data unless it hears a few other transmissions whose data suggest its		data unless it hears a few other transmissions whose data suggest its
	own transmission is redundant. Examples of such data include routing		own transmission is redundant. Examples of such data include routing
	state, software update versions, and the last heard multicast packet.		state, software update versions, and the last heard multicast packet.
	This primitive allows Trickle to scale to thousand-fold variations in		This primitive allows Trickle to scale to thousand-fold variations in
	network density, quickly propagate updates, distribute transmission		network density, quickly propagate updates, distribute transmission
	load evenly, be robust to transient disconnections, handle network		load evenly, be robust to transient disconnections, handle network
	repopulations, and impose a very low maintenance overhead: common		repopulations, and impose a very low maintenance overhead: one
	uses require on the order of a few packets per hour yet can respond		example use, routing beacons in the CTP protocol [Gnawali09],
	in milliseconds.		requires sending on the order of a few packets per hour yet can
			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 broadcast: 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 its data is consistent with their
	own state, or a recipient detects an inconsistency. Detection can be		own state, or a recipient detects an inconsistency. Detection can be
	the result of either an out-of-date node hearing something new, or an		the result of either an out-of-date node hearing something new, or an
	updated node hearing something old. As long as every node		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
	skipping to change at page 5, line 43		skipping to change at page 5, line 50
	advertise their need. Some of these recipients might not even have		advertise their need. Some of these recipients might not even have
	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 communication can be either transmission or reception		The fact that Trickle communication can be either transmission or
	enables the Trickle algorithm to operate in sparse as well as dense		reception enables the Trickle algorithm to operate in sparse as well
	networks. A single, disconnected node must transmit at the Trickle		as dense networks. A single, disconnected node must transmit at the
	communication rate. In a lossless, single-hop network of size n, the		Trickle communication rate. In a lossless, single-hop network of
	Trickle communication rate at each node equals the sum of the Trickle		size n, the Trickle communication rate at each node equals the sum of
	transmission rates across all nodes. The Trickle algorithm blaances		the Trickle transmission rates across all nodes. The Trickle
	the load in such a scenario, as each node's Trickle transmission rate		algorithm balances the load in such a scenario, as each node's
	is 1/nth of the Trickle communication rate. Sparser networks require		Trickle transmission rate is 1/nth of the Trickle communication rate.
	more transmissions per node, but utilization of the radio channel		Sparser networks require more transmissions per node, but utilization
	over space will not increase. This is an important property in		of the radio channel over space will not increase. This is an
	wireless networks and other shared media, where the channel is a		important property in wireless networks and other shared media, where
	valuable shared resource. Additionally, reducing transmissions in		the channel is a valuable shared resource. Additionally, reducing
	dense networks conserves system energy.		transmissions in dense networks conserves system energy.
	4. Trickle Algorithm		4. Trickle Algorithm
	This section describes the Trickle algorithm.		This section describes the Trickle algorithm.
	4.1. Parameters and Variables		4.1. Parameters and Variables
	A Trickle timer has three configuration parameters: the minimum		A Trickle timer has three configuration parameters: the minimum
	interval size Imin, the maximum interval size Imax, and a redundancy		interval size Imin, the maximum interval size Imax, and a redundancy
	constant k:		constant k:
	skipping to change at page 12, line 9		skipping to change at page 12, line 22
	<http://portal.acm.org/citation.cfm?id=1460412.1460415>.		<http://portal.acm.org/citation.cfm?id=1460412.1460415>.
	[I-D.hui-6man-trickle-mcast]		[I-D.hui-6man-trickle-mcast]
	Hui, J. and R. Kelsey, "Multicast Forwarding Using		Hui, J. and R. Kelsey, "Multicast Forwarding Using
	Trickle", draft-hui-6man-trickle-mcast-00 (work in		Trickle", draft-hui-6man-trickle-mcast-00 (work in
	progress), July 2010.		progress), July 2010.
	[I-D.ietf-roll-rpl]		[I-D.ietf-roll-rpl]
	Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing		Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
	Protocol for Low power and Lossy Networks",		Protocol for Low power and Lossy Networks",
	draft-ietf-roll-rpl-10 (work in progress), June 2010.		draft-ietf-roll-rpl-11 (work in progress), July 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. 17 change blocks.
	31 lines changed or deleted		37 lines changed or added
This html diff was produced by rfcdiff 1.38. The latest version is available from http://tools.ietf.org/tools/rfcdiff/