draft-ietf-roll-minrank-hysteresis-of-08.txt		draft-ietf-roll-minrank-hysteresis-of-09.txt
	Networking Working Group O. Gnawali		Networking Working Group O. Gnawali
	Internet-Draft University of Houston		Internet-Draft University of Houston
	Intended status: Standards Track P. Levis		Intended status: Standards Track P. Levis
	Expires: October 22, 2012 Stanford University		Expires: October 24, 2012 Stanford University
	April 20, 2012		April 22, 2012
	The Minimum Rank with Hysteresis Objective Function		The Minimum Rank with Hysteresis Objective Function
	draft-ietf-roll-minrank-hysteresis-of-08		draft-ietf-roll-minrank-hysteresis-of-09
	Abstract		Abstract
	The Routing Protocol for Low Power and Lossy Networks (RPL) uses		The Routing Protocol for Low Power and Lossy Networks (RPL) uses
	objective functions to construct routes that optimize or constrain		objective functions to construct routes that optimize or constrain
	the routes it selects and uses. This specification describes the		the routes it selects and uses. This specification describes the
	Minimum Rank with Hysteresis Objective Function (MRHOF), an objective		Minimum Rank with Hysteresis Objective Function (MRHOF), an objective
	function that selects routes that minimize a metric, while using		function that selects routes that minimize a metric, while using
	hysteresis to reduce churn in response to small metric changes.		hysteresis to reduce churn in response to small metric changes.
	MRHOF works with metrics that are additive along a route, and the		MRHOF works with metrics that are additive along a route, and the
	skipping to change at page 1, line 39		skipping to change at page 1, line 39
	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 October 22, 2012.		This Internet-Draft will expire on October 24, 2012.
	Copyright Notice		Copyright Notice
	Copyright (c) 2012 IETF Trust and the persons identified as the		Copyright (c) 2012 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
	skipping to change at page 2, line 21		skipping to change at page 2, line 21
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
	2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3		2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
	3. The Minimum Rank with Hysteresis Objective Function . . . . . 4		3. The Minimum Rank with Hysteresis Objective Function . . . . . 4
	3.1. Computing the Path cost . . . . . . . . . . . . . . . . . 4		3.1. Computing the Path cost . . . . . . . . . . . . . . . . . 4
	3.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 5		3.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 5
	3.2.1. When Parent Selection Runs . . . . . . . . . . . . . . 6		3.2.1. When Parent Selection Runs . . . . . . . . . . . . . . 6
	3.2.2. Parent Selection Algorithm . . . . . . . . . . . . . . 6		3.2.2. Parent Selection Algorithm . . . . . . . . . . . . . . 6
	3.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 7		3.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 7
	3.4. Advertising the Path Cost . . . . . . . . . . . . . . . . 8		3.4. Advertising the Path Cost . . . . . . . . . . . . . . . . 8
	3.5. Working Without Metric Containers . . . . . . . . . . . . 9		3.5. Working Without Metric Containers . . . . . . . . . . . . 8
	4. Using MRHOF for Metric Maximization . . . . . . . . . . . . . 9		4. Using MRHOF for Metric Maximization . . . . . . . . . . . . . 9
	5. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 9		5. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 9
	6. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 10		6. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 10
	6.1. Device Configuration . . . . . . . . . . . . . . . . . . . 11		6.1. Device Configuration . . . . . . . . . . . . . . . . . . . 10
	6.2. Device Monitoring . . . . . . . . . . . . . . . . . . . . 11		6.2. Device Monitoring . . . . . . . . . . . . . . . . . . . . 11
	7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12		7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12
	8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12		8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
	9. Security Considerations . . . . . . . . . . . . . . . . . . . 12		9. Security Considerations . . . . . . . . . . . . . . . . . . . 12
	10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12		10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
	10.1. Normative References . . . . . . . . . . . . . . . . . . . 12		10.1. Normative References . . . . . . . . . . . . . . . . . . . 12
	10.2. Informative References . . . . . . . . . . . . . . . . . . 13		10.2. Informative References . . . . . . . . . . . . . . . . . . 13
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13
	1. Introduction		1. Introduction
	An objective function specifies how RPL [RFC6550] selects paths. For		An objective function specifies how RPL [RFC6550] selects paths. For
	example, if an RPL instance uses an objective function that minimizes		example, if an RPL instance uses an objective function that minimizes
	hop-count, RPL will select paths with minimum hop count. RPL		hop-count, RPL will select paths with minimum hop count. RPL
	requires that all nodes in a network use a common OF; relaxing this		requires that all nodes in a network use a common OF; relaxing this
	requirement may be a subject of future study.		requirement may be a subject of future study.
	The nodes running RPL might use a number of metrics to describe a		The nodes running RPL might use a number of metrics to describe a
	link or a node [I-D.ietf-roll-routing-metrics] and make these metrics		link or a node [RFC6551] and make these metrics available for route
	available for route selection. RPL advertises metrics in RPL		selection. RPL advertises metrics in RPL Destination Information
	Destination Information Object (DIO) messages with a Metric Container		Object (DIO) messages with a Metric Container suboption. An
	suboption. An objective function can use these metrics to choose		objective function can use these metrics to choose routes.
	routes.
	To decouple the details of an individual metric or objective function		To decouple the details of an individual metric or objective function
	from forwarding and routing, RPL describes routes through a value		from forwarding and routing, RPL describes routes through a value
	called Rank. Rank, roughly speaking, corresponds to the distance		called Rank. Rank, roughly speaking, corresponds to the distance
	associated with a route. RPL defines how nodes decide on paths based		associated with a route. RPL defines how nodes decide on paths based
	on Rank and advertise their Rank. An objective function defines how		on Rank and advertise their Rank. An objective function defines how
	nodes calculate Rank, based on the Rank of its potential parents,		nodes calculate Rank, based on the Rank of its potential parents,
	metrics, and other network properties.		metrics, and other network properties.
	This specification describes MRHOF, an objective function for RPL.		This specification describes MRHOF, an objective function for RPL.
	skipping to change at page 4, line 4		skipping to change at page 3, line 51
	that are not additive.		that are not additive.
	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].
	The terminologies used in this document are consistent with the		The terminologies used in this document are consistent with the
	terminologies described in [I-D.ietf-roll-terminology] and		terminologies described in [I-D.ietf-roll-terminology] and [RFC6551].
	[I-D.ietf-roll-routing-metrics].
	The terminologies used in this document are also consistent with the		The terminologies used in this document are also consistent with the
	terminologies described in RFC 6550 [RFC6550], except the term Rank.		terminologies described in [RFC6550], except the term Rank. In this
	In this document, Rank refers to the value of the Rank field, not		document, Rank refers to the value of the Rank field, not DAGRank as
	DAGRank as in RFC 6550 [RFC6550].		in [RFC6550].
	This document introduces three terms:		This document introduces three terms:
	Selected metric: The metric chosen by the network operator to use		Selected metric: The metric chosen by the network operator to use
	for path selection. This metric can be any additive metric		for path selection. This metric can be any additive metric
	listed in [I-D.ietf-roll-routing-metrics].		listed in [RFC6551].
	Path cost: Path cost quantifies a property of an end-to-end path.		Path cost: Path cost quantifies a property of an end-to-end path.
	Path cost is obtained by summing up the selected metric of the		Path cost is obtained by summing up the selected metric of the
	links or nodes along the path. Path cost can be used by RPL to		links or nodes along the path. Path cost can be used by RPL to
	compare different paths.		compare different paths.
	Worst parent: The node in the parent set with the largest path cost.		Worst parent: The node in the parent set with the largest path cost.
	3. The Minimum Rank with Hysteresis Objective Function		3. The Minimum Rank with Hysteresis Objective Function
	The Minimum Rank with Hysteresis Objective Function, MRHOF, is		The Minimum Rank with Hysteresis Objective Function, MRHOF, is
	designed to find the paths with the smallest path cost while		designed to find the paths with the smallest path cost while
	preventing excessive churn in the network. It does so by finding the		preventing excessive churn in the network. It does so by finding the
	minimum cost path and switching to that path only if it is shorter		minimum cost path and switching to that path only if it is shorter
	(in terms of path cost) than the current path by at least a given		(in terms of path cost) than the current path by at least a given
	threshold.		threshold.
	MRHOF may be used with any additive metric listed in		MRHOF may be used with any additive metric listed in [RFC6551] as
	[I-D.ietf-roll-routing-metrics] as long the routing objective is to		long the routing objective is to minimize the given routing metric.
	minimize the given routing metric. Nodes MUST support at least one		Nodes MUST support at least one of these metrics: node energy, hop
	of these metrics: node energy, hop count, latency, link quality		count, latency, link quality level, and ETX. Nodes SHOULD support
	level, and ETX. Nodes SHOULD support the ETX metric. MRHOF does not		the ETX metric. MRHOF does not support non-additive metrics.
	support non-additive metrics.
	3.1. Computing the Path cost		3.1. Computing the Path cost
	Root nodes (Grounded or Floating) set the variable cur_min_path_cost		Root nodes (Grounded or Floating) set the variable cur_min_path_cost
	to MIN_PATH_COST.		to MIN_PATH_COST.
	If a non-root node does not have metrics to compute the path cost		If a non-root node does not have metrics to compute the path cost
	through any of the candidate neighbors, it MUST join one of the		through any of the candidate neighbors, it MUST join one of the
	candidate neighbors as a RPL Leaf.		candidate neighbors as a RPL Leaf.
	skipping to change at page 10, line 48		skipping to change at page 10, line 38
	candidate parents are still available without triggering a new		candidate parents are still available without triggering a new
	round of route discovery.		round of route discovery.
	ALLOW_FLOATING_ROOT: 0. Do not allow a node to become a floating		ALLOW_FLOATING_ROOT: 0. Do not allow a node to become a floating
	root.		root.
	6. Manageability		6. Manageability
	Section 18 of [RFC6550] depicts the management of RPL. This		Section 18 of [RFC6550] depicts the management of RPL. This
	specification inherits from that section and its subsections, with		specification inherits from that section and its subsections, with
	the exception that metrics as specified in		the exception that metrics as specified in [RFC6551] are not used and
	[I-D.ietf-roll-routing-metrics] are not used and do not require		do not require management.
	management.
	6.1. Device Configuration		6.1. Device Configuration
	An implementation SHOULD allow the following parameters to be		An implementation SHOULD allow the following parameters to be
	configured at installation time: MAX_LINK_METRIC, MAX_PATH_COST,		configured at installation time: MAX_LINK_METRIC, MAX_PATH_COST,
	MIN_PATH_COST, PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and		MIN_PATH_COST, PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and
	ALLOW_FLOATING_ROOT. An implementation MAY allow these parameters to		ALLOW_FLOATING_ROOT. An implementation MAY allow these parameters to
	be configured dynamically at run time once a network has been		be configured dynamically at run time once a network has been
	deployed.		deployed.
	skipping to change at page 11, line 39		skipping to change at page 11, line 28
	Because of the partially-coupled relationship between Rank and metric		Because of the partially-coupled relationship between Rank and metric
	values, networks using MRHOF require care in setting		values, networks using MRHOF require care in setting
	MinHopRankIncrease. A large MinHopRankIncrease will cause MRHOF to		MinHopRankIncrease. A large MinHopRankIncrease will cause MRHOF to
	be unable to select paths with different hop counts but similar		be unable to select paths with different hop counts but similar
	metric values. If MinHopRankIncrease is large enough that its		metric values. If MinHopRankIncrease is large enough that its
	increment is greater than that caused by link cost, then metrics will		increment is greater than that caused by link cost, then metrics will
	be used to select a preferred parent but the advertised Rank will be		be used to select a preferred parent but the advertised Rank will be
	a simple hopcount. This behavior might be desirable, but it also		a simple hopcount. This behavior might be desirable, but it also
	might be unintended: care is recommended.		might be unintended: care is recommended.
			RPL's Rank advertisement rules can require a DODAG Root to advertise
			a Rank higher than its corresponding ETX value, as a DODAG Root
			advertises a Rank of MinHopRankIncrease. Because all DODAG Roots
			within a DODAG Version advertise the same Rank, this constant value
			typically does not affect route selection. Nevertheless, it means
			that if a DODAG Version has a MinHopRankIncrease of M and a path has
			an advertised ETX of E, then the actual ETX of the path is likely
			closer to a value of E-M than a value of E.
	6.2. Device Monitoring		6.2. Device Monitoring
	A MRHOF implementation should provide an interface for monitoring its		A MRHOF implementation should provide an interface for monitoring its
	operation. At a minimum, the information provided should include:		operation. At a minimum, the information provided should include:
	DAG information as specified in Section 6.3.1 of [RFC6550], and		DAG information as specified in Section 6.3.1 of [RFC6550], and
	including the DODAGID, the RPLInstanceID, the Mode of Operation,		including the DODAGID, the RPLInstanceID, the Mode of Operation,
	the Rank of this node, the current Version Number, and the value		the Rank of this node, the current Version Number, and the value
	of the Grounded flag.		of the Grounded flag.
	skipping to change at page 12, line 35		skipping to change at page 12, line 35
	elements. If those elements were compromised, then an implementation		elements. If those elements were compromised, then an implementation
	of MRHOF might generate the wrong path for a packet, resulting in it		of MRHOF might generate the wrong path for a packet, resulting in it
	being misrouted. Therefore, deployments are RECOMMENDED to use RPL		being misrouted. Therefore, deployments are RECOMMENDED to use RPL
	security mechanisms if there is a risk that routing information might		security mechanisms if there is a risk that routing information might
	be modified or spoofed.		be modified or spoofed.
	10. References		10. References
	10.1. Normative References		10.1. Normative References
	[I-D.ietf-roll-routing-metrics]
	Barthel, D., Vasseur, J., Pister, K., Kim, M., and N.
	Dejean, "Routing Metrics used for Path Calculation in Low
	Power and Lossy Networks",
	draft-ietf-roll-routing-metrics-19 (work in progress),
	March 2011.
	[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate		[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
	Requirement Levels", BCP 14, RFC 2119, March 1997.		Requirement Levels", BCP 14, RFC 2119, March 1997.
	[RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,		[RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,
	Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.		Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.
	Alexander, "RPL: IPv6 Routing Protocol for Low-Power and		Alexander, "RPL: IPv6 Routing Protocol for Low-Power and
	Lossy Networks", RFC 6550, March 2012.		Lossy Networks", RFC 6550, March 2012.
			[RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D.
			Barthel, "Routing Metrics Used for Path Calculation in
			Low-Power and Lossy Networks", RFC 6551, March 2012.
	10.2. Informative References		10.2. Informative References
	[I-D.ietf-roll-security-framework]		[I-D.ietf-roll-security-framework]
	Tsao, T., Alexander, R., Dohler, M., Daza, V., and A.		Tsao, T., Alexander, R., Dohler, M., Daza, V., and A.
	Lozano, "A Security Framework for Routing over Low Power		Lozano, "A Security Framework for Routing over Low Power
	and Lossy Networks", draft-ietf-roll-security-framework-07		and Lossy Networks", draft-ietf-roll-security-framework-07
	(work in progress), January 2012.		(work in progress), January 2012.
	[I-D.ietf-roll-terminology]		[I-D.ietf-roll-terminology]
	Vasseur, J., "Terminology in Low power And Lossy		Vasseur, J., "Terminology in Low power And Lossy
End of changes. 14 change blocks.
	33 lines changed or deleted		35 lines changed or added
This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/