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/ |