draft-ietf-roll-minrank-hysteresis-of-03.txt		draft-ietf-roll-minrank-hysteresis-of-04.txt
	Networking Working Group O. Gnawali		Networking Working Group O. Gnawali
	Internet-Draft P. Levis		Internet-Draft P. Levis
	Intended status: Standards Track Stanford University		Intended status: Standards Track Stanford University
	Expires: November 4, 2011 May 03, 2011		Expires: November 18, 2011 May 17, 2011
	The Minimum Rank Objective Function with Hysteresis		The Minimum Rank Objective Function with Hysteresis
	draft-ietf-roll-minrank-hysteresis-of-03		draft-ietf-roll-minrank-hysteresis-of-04
	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 Objective Function with Hysteresis (MRHOF), an objective		Minimum Rank Objective Function with Hysteresis (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 44		skipping to change at page 1, line 44
	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 November 4, 2011.		This Internet-Draft will expire on November 18, 2011.
	Copyright Notice		Copyright Notice
	Copyright (c) 2011 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
	skipping to change at page 2, line 27		skipping to change at page 2, line 27
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
	2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3		2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
	3. The Minimum Rank Objective Function with Hysteresis . . . . . 4		3. The Minimum Rank Objective Function with Hysteresis . . . . . 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.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 6		3.3. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 6
	3.4. Advertising the Path Cost . . . . . . . . . . . . . . . . 7		3.4. Advertising the Path Cost . . . . . . . . . . . . . . . . 7
	3.5. Working Without Metric Containers . . . . . . . . . . . . 7		3.5. Working Without Metric Containers . . . . . . . . . . . . 7
	4. Using MRHOF for Metric Maximization . . . . . . . . . . . . . 7		4. Using MRHOF for Metric Maximization . . . . . . . . . . . . . 7
	5. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 8		5. MRHOF Variables and Parameters . . . . . . . . . . . . . . . . 8
			5.1. Manageability . . . . . . . . . . . . . . . . . . . . . . 9
	6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9		6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9
	7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9		7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
	8. Security Considerations . . . . . . . . . . . . . . . . . . . 9		8. Security Considerations . . . . . . . . . . . . . . . . . . . 9
	9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9		9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
	9.1. Normative References . . . . . . . . . . . . . . . . . . . 9		9.1. Normative References . . . . . . . . . . . . . . . . . . . 10
	9.2. Informative References . . . . . . . . . . . . . . . . . . 9		9.2. Informative References . . . . . . . . . . . . . . . . . . 10
	Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10		Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
	1. Introduction		1. Introduction
	An objective function specifies how RPL [I-D.ietf-roll-rpl] selects		An objective function specifies how RPL [I-D.ietf-roll-rpl] selects
	paths. Objective functions can choose paths based on routing metrics		paths. Objective functions can choose paths based on routing metrics
	or constraints. For example, if an RPL instance uses an objective		or constraints. For example, if an RPL instance uses an objective
	function that minimizes hop-count, RPL will select paths with minimum		function that minimizes hop-count, RPL will select paths with minimum
	hop count.		hop count.
	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 it available		link or a node [I-D.ietf-roll-routing-metrics] and make it available
	for route selection. These metrics are advertised in RPL Destination		for route selection. These metrics are advertised in RPL Destination
	Information Object (DIO) messages using a Metric Container suboption.		Information Object (DIO) messages using a Metric Container suboption.
	An objective function can use these metrics to choose routes.		An objective function can use these metrics to choose routes. The
			only exception is the ETX metric, which is used without the metric
			container as described in Section 3.5.
	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. An objective function is responsible for		associated with a route. An objective function is responsible for
	computing a node's advertised Rank value based on the Rank of its		computing a node's advertised Rank value based on the Rank of its
	potential parents, metrics, and other network properties.		potential parents, metrics, and other network properties.
	This specification describes MRHOF, an objective function for RPL.		This specification describes MRHOF, an objective function for RPL.
	MRHOF uses hysteresis while selecting the path with the smallest		MRHOF uses hysteresis while selecting the path with the smallest
	skipping to change at page 6, line 27		skipping to change at page 6, line 27
	3. A node MAY declare itself as a Floating root, and hence no		3. A node MAY declare itself as a Floating root, and hence no
	preferred parent, depending on the configuration.		preferred parent, depending on the configuration.
	4. If the selected metric for a link is greater than		4. If the selected metric for a link is greater than
	MAX_LINK_METRIC, the node SHOULD exclude that link from		MAX_LINK_METRIC, the node SHOULD exclude that link from
	consideration for parent selection.		consideration for parent selection.
	5. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY		5. If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY
	declare itself as a Floating root.		declare itself as a Floating root.
	6. If the configuration disallows a node to be a Floating root and		6. If ALLOW_FLOATING_ROOT is 0 and no neighbors are discovered, the
	no neighbors are discovered, the node does not have a preferred		node does not have a preferred parent, and MUST set
	parent, and MUST set cur_min_path_cost to MAX_PATH_COST.		cur_min_path_cost to MAX_PATH_COST.
	Except in the cases above, the candidate neighbor on the path with		Except in the cases above, the candidate neighbor on the path with
	the smallest path cost is the preferred parent. A node MAY include a		the smallest path cost is the preferred parent. A node MAY include a
	total of PARENT_SET_SIZE candidate neighbors in the parent set. The		total of PARENT_SET_SIZE candidate neighbors in the parent set. The
	cost of path through the nodes in the parent set is smaller than or		cost of path through the nodes in the parent set is smaller than or
	equal to the cost of the paths through any of the nodes that are not		equal to the cost of the paths through any of the nodes that are not
	in the parent set. If the cost of the path through the preferred		in the parent set. If the cost of the path through the preferred
	parent and the worst parent is too large, a node MAY keep a smaller		parent and the worst parent is too large, a node MAY keep a smaller
	parent set.		parent set.
	3.3. Computing Rank		3.3. Computing Rank
	The DAG roots set their rank to MIN_PATH_COST for the selected		The DAG roots set their rank to MIN_PATH_COST for the selected
	metric.		metric.
	Once a non-root node selects its parent set, it can use the following		Once a non-root node selects its parent set, it can use the following
	table to covert the the path cost of the worst parent (written as		table to covert the path cost of the worst parent (written as Cost in
	Cost in the table) to its rank:		the table) to its rank:
	+--------------------+------------+		+--------------------+------------+
	| Node/link Metric | Rank |		| Node/link Metric | Rank |
	+--------------------+------------+		+--------------------+------------+
	| Node Energy | 255 - Cost |		| Node Energy | 255 - Cost |
	| Hop-Count | Cost |		| Hop-Count | Cost |
	| Latency | Cost/65536 |		| Latency | Cost/65536 |
	| Link Quality Level | Cost |		| Link Quality Level | Cost |
	| ETX | Cost |		| ETX | Cost |
	+--------------------+------------+		+--------------------+------------+
	Table 1: Conversion of metric to rank.		Table 1: Conversion of metric to rank.
	Nodes MUST support at least one of the above metrics. Nodes SHOULD		Nodes MUST support at least one of the above metrics. Nodes SHOULD
	support the ETX metric.		support the ETX metric.
	Node rank is undefined for these node/link metrics: Node state and		Node rank is undefined for these node/link metrics: Node state and
	attributes, throughput, and link color. If the rank is undefined,		attributes, throughput, and link color. If the rank is undefined,
	the node MUST join one of the neighbors as a leaf node.		the node must join one of the neighbors as a leaf node according to
			[I-D.ietf-roll-rpl].
	3.4. Advertising the Path Cost		3.4. Advertising the Path Cost
	Once the preferred parent is selected, the node sets its		Once the preferred parent is selected, the node sets its
	cur_min_path_cost variable to the path cost corresponding to the		cur_min_path_cost variable to the path cost corresponding to the
	preferred parent. Thus, cur_min_path_cost is the cost of the minimum		preferred parent. Thus, cur_min_path_cost is the cost of the minimum
	cost path from the node to the root. The value of the		cost path from the node to the root. The value of the
	cur_min_path_cost is carried in the metric container corresponding to		cur_min_path_cost is carried in the metric container corresponding to
	the selected metric when DIO messages are sent.		the selected metric when DIO messages are sent.
			If ETX is the selected metric, cur_min_path_cost is directly used as
			Rank and never advertised in a metric container.
	3.5. Working Without Metric Containers		3.5. Working Without Metric Containers
	In the absence of metric container, MRHOF uses ETX as its metric. It		In the absence of metric container, MRHOF uses ETX as its metric. It
	locally computes the ETX of links to its neighbors and adds this		locally computes the ETX of links to its neighbors and adds this
	value to their advertised Rank to compute the associated Rank of		value to their advertised Rank to compute the associated Rank of
	routes. Once parent selection and rank computation is performed		routes. Once parent selection and rank computation is performed
	using the ETX metric, the node advertises a Rank equal to the ETX		using the ETX metric, the node advertises a Rank equal to the ETX
	cost and SHOULD NOT include a metric container in its DIO messages.		cost and MUST NOT include a metric container in its DIO messages.
	4. Using MRHOF for Metric Maximization		4. Using MRHOF for Metric Maximization
	MRHOF cannot be directly used for parent selection using metrics		MRHOF cannot be directly used for parent selection using metrics
	which require finding paths with maximum value of the selected		which require finding paths with maximum value of the selected
	metric, such as path reliability. It is possible to convert such a		metric, such as path reliability. It is possible to convert such a
	metric maximization problem to a metric minimization problem and use		metric maximization problem to a metric minimization problem for some
	MRHOF provided:		metrics and use MRHOF provided:
	There is a fixed and well-known maximum metric value corresponding		There is a fixed and well-known maximum metric value corresponding
	to the best path. This is the path cost for the DAG root.		to the best path. This is the path cost for the DAG root. For
	Example, the best link reliability has a value of 1.		example, the logarithm of the best link reliability has a value of
			0.
	Metrics are all positive. Example, link reliability is always		The metrics in the maximization problem are all negative. The
	positive.		logarithm of the link reliability is always negative.
	For metrics meeting the above conditions, the problem of maximizing		For metrics meeting the above conditions, the problem of maximizing
	the metric value is equivalent to minimizing the negative of the		the metric value is equivalent to minimizing the modified metric
	metric value. MRHOF is not required to work with these metrics.		value, e.g., logarithm of link reliability. MRHOF is not required to
			work with these metrics.
	5. MRHOF Variables and Parameters		5. MRHOF Variables and Parameters
	MRHOF uses the following variable:		MRHOF uses the following variable:
	cur_min_path_cost: The cost of the path from a node through its		cur_min_path_cost: The cost of the path from a node through its
	preferred parent to the root computed at the last parent		preferred parent to the root computed at the last parent
	selection.		selection.
	MRHOF uses the following parameters:		MRHOF uses the following parameters:
	skipping to change at page 8, line 42		skipping to change at page 8, line 45
	MIN_PATH_COST: The minimum allowed value for the path metric of		MIN_PATH_COST: The minimum allowed value for the path metric of
	the selected path.		the selected path.
	PARENT_SWITCH_THRESHOLD: The difference between metric of the path		PARENT_SWITCH_THRESHOLD: The difference between metric of the path
	through the preferred parent and the minimum-metric path in order		through the preferred parent and the minimum-metric path in order
	to trigger the selection of a new preferred parent.		to trigger the selection of a new preferred parent.
	PARENT_SET_SIZE: The number of candidate parents, including the		PARENT_SET_SIZE: The number of candidate parents, including the
	preferred parent, in the parent set.		preferred parent, in the parent set.
			ALLOW_FLOATING_ROOT: If set to 1, allows a node to become a
			floating root.
	The parameter values are assigned depending on the selected metric.		The parameter values are assigned depending on the selected metric.
	The best values for these parameters should be experimentally		The best values for these parameters should be experimentally
	determined. The working group has long experience routing with the		determined. The working group has long experience routing with the
	ETX metric. Based on those experiences, these ETX parameters are		ETX metric. Based on those experiences, these values are
	known to work in many settings:		RECOMMENDED:
	MAX_LINK_METRIC: 10. Disallow links with greater than 10 expected		MAX_LINK_METRIC: 10. Disallow links with greater than 10 expected
	transmission count on the selected path.		transmission count on the selected path.
	MAX_PATH_COST: 100. Disallow paths with greater than 100 expected		MAX_PATH_COST: 100. Disallow paths with greater than 100 expected
	transmission count.		transmission count.
	MIN_PATH_COST: 0. At root, the expected transmission count is 0.		MIN_PATH_COST: 0. At root, the expected transmission count is 0.
	PARENT_SWITCH_THRESHOLD: 1.5. Switch to a new path only if it is		PARENT_SWITCH_THRESHOLD: 1.5. Switch to a new path only if it is
	expected to require at least 1.5 fewer transmission than the		expected to require at least 1.5 fewer transmission than the
	current path.		current path.
	PARENT_SET_SIZE: 3. If the preferred parent is not available, two		PARENT_SET_SIZE: 3. If the preferred parent is not available, two
	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
			root.
			5.1. Manageability
			The parameters MAX_LINK_METRIC, MAX_PATH_COST, MIN_PATH_COST,
			PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and ALLOW_FLOATING_ROOT
			should be configurable.
	6. Acknowledgements		6. Acknowledgements
	Thanks to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur,		Thanks to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur,
	and Phoebus Chen for their comments.		and Phoebus Chen for their comments.
	7. IANA Considerations		7. IANA Considerations
	This specification requires an allocated OCP. A value of 1 is		This specification requires an allocated OCP. A value of 1 is
	requested.		requested.
	skipping to change at page 9, line 34		skipping to change at page 10, line 4
	This specification requires an allocated OCP. A value of 1 is		This specification requires an allocated OCP. A value of 1 is
	requested.		requested.
	8. Security Considerations		8. Security Considerations
	Security considerations to be developed in accordance to the output		Security considerations to be developed in accordance to the output
	of the WG.		of the WG.
	9. References		9. References
	9.1. Normative References		9.1. Normative References
			[I-D.ietf-roll-routing-metrics]
			Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
			Barthel, "Routing Metrics used for Path Calculation in Low
			Power and Lossy Networks",
			draft-ietf-roll-routing-metrics-19 (work in progress),
			March 2011.
			[I-D.ietf-roll-rpl]
			Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
			Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
			Vasseur, "RPL: IPv6 Routing Protocol for Low power and
			Lossy Networks", draft-ietf-roll-rpl-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.
	9.2. Informative References		9.2. Informative References
	[I-D.ietf-roll-routing-metrics]
	Vasseur, J. and D. Networks, "Routing Metrics used for
	Path Calculation in Low Power and Lossy Networks",
	draft-ietf-roll-routing-metrics-01 (work in progress),
	October 2009.
	[I-D.ietf-roll-rpl]
	Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
	Protocol for Low power and Lossy Networks",
	draft-ietf-roll-rpl-05 (work in progress), December 2009.
	[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
	Networks", draft-ietf-roll-terminology-01 (work in		Networks", draft-ietf-roll-terminology-05 (work in
	progress), May 2009.		progress), March 2011.
	Authors' Addresses		Authors' Addresses
	Omprakash Gnawali		Omprakash Gnawali
	Stanford University		Stanford University
	S255 Clark Center, 318 Campus Drive		S255 Clark Center, 318 Campus Drive
	Stanford, CA 94305		Stanford, CA 94305
	USA		USA
	Phone: +1 650 725 6086		Phone: +1 650 725 6086
End of changes. 22 change blocks.
	38 lines changed or deleted		61 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/