draft-ietf-roll-minrank-hysteresis-of-09.txt | draft-ietf-roll-minrank-hysteresis-of-10.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 24, 2012 Stanford University | Expires: October 28, 2012 Stanford University | |||
April 22, 2012 | April 26, 2012 | |||
The Minimum Rank with Hysteresis Objective Function | The Minimum Rank with Hysteresis Objective Function | |||
draft-ietf-roll-minrank-hysteresis-of-09 | draft-ietf-roll-minrank-hysteresis-of-10 | |||
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 24, 2012. | This Internet-Draft will expire on October 28, 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 27 | skipping to change at page 2, line 27 | |||
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 . . . . . . . . . . . . 8 | 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 . . . . . . . . . . . . . . . . . . . 10 | 6.1. Device Configuration . . . . . . . . . . . . . . . . . . . 10 | |||
6.2. Device Monitoring . . . . . . . . . . . . . . . . . . . . 11 | 6.2. Device Monitoring . . . . . . . . . . . . . . . . . . . . 11 | |||
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 | 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11 | |||
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 . . . . . . . . . . . . . . . . . . 12 | |||
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. | |||
skipping to change at page 4, line 41 | skipping to change at page 4, line 41 | |||
MRHOF may be used with any additive metric listed in [RFC6551] as | MRHOF may be used with any additive metric listed in [RFC6551] as | |||
long the routing objective is to minimize the given routing metric. | long the routing objective is to minimize the given routing metric. | |||
Nodes MUST support at least one of these metrics: node energy, hop | Nodes MUST support at least one of these metrics: node energy, hop | |||
count, latency, link quality level, and ETX. Nodes SHOULD support | count, latency, link quality level, and ETX. Nodes SHOULD support | |||
the ETX metric. MRHOF does not support non-additive metrics. | the ETX metric. MRHOF does not 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 the metric value that most closely computes to a Rank of | |||
MinHopRankIncrease. | ||||
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. | |||
Otherwise, nodes compute the path cost for each candidate neighbor | Otherwise, nodes compute the path cost for each candidate neighbor | |||
reachable on an interface. The path cost of a neighbor represents | reachable on an interface. The path cost of a neighbor represents | |||
the cost of the path, in terms of the selected metric, from a node to | the cost of the path, in terms of the selected metric, from a node to | |||
the root of the DODAG through that neighbor. A non-root node | the root of the DODAG through that neighbor. A non-root node | |||
computes a neighbor's path cost by adding two components: | computes a neighbor's path cost by adding two components: | |||
skipping to change at page 8, line 40 | skipping to change at page 8, line 43 | |||
carried in the metric container corresponding to the selected metric | carried in the metric container corresponding to the selected metric | |||
when DIO messages are sent. | when DIO messages are sent. | |||
If ETX is the selected metric, a node SHOULD NOT advertise it in a | If ETX is the selected metric, a node SHOULD NOT advertise it in a | |||
metric container. Instead, a node MUST advertise an approximation of | metric container. Instead, a node MUST advertise an approximation of | |||
its ETX in its advertised Rank value, following the rules described | its ETX in its advertised Rank value, following the rules described | |||
in Section 3.3. If a node receives a DIO with a metric container | in Section 3.3. If a node receives a DIO with a metric container | |||
holding an ETX metric, MRHOF MUST ignore the ETX metric value in its | holding an ETX metric, MRHOF MUST ignore the ETX metric value in its | |||
Rank calculations. | Rank calculations. | |||
DODAG Roots advertise a metric value which computes to a cost of | DODAG Roots advertise a metric value which mostly closely computes to | |||
MIN_PATH_COST. | a Rank value of MinHopRankIncrease. | |||
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 MUST NOT include a metric container in its DIO messages. | cost and MUST NOT include a metric container in its DIO messages. | |||
skipping to change at page 9, line 42 | skipping to change at page 9, line 43 | |||
selection. | selection. | |||
MRHOF uses the following parameters: | MRHOF uses the following parameters: | |||
MAX_LINK_METRIC: Maximum allowed value for the selected link | MAX_LINK_METRIC: Maximum allowed value for the selected link | |||
metric for each link on the path. | metric for each link on the path. | |||
MAX_PATH_COST: Maximum allowed value for the path metric of a | MAX_PATH_COST: Maximum allowed value for the path metric of a | |||
selected path. | selected path. | |||
MIN_PATH_COST: The minimum allowed value for the path metric of | ||||
the selected path. | ||||
PARENT_SWITCH_THRESHOLD: The difference between the cost of the | PARENT_SWITCH_THRESHOLD: The difference between the cost of the | |||
path through the preferred parent and the minimum cost path in | path through the preferred parent and the minimum cost path in | |||
order to trigger the selection of a new preferred parent. | order 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 | ALLOW_FLOATING_ROOT: If set to 1, allows a node to become a | |||
floating root. | floating root. | |||
skipping to change at page 10, line 20 | skipping to change at page 10, line 20 | |||
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 values are | ETX metric. Based on those experiences, these values are | |||
RECOMMENDED: | 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. | ||||
PARENT_SWITCH_THRESHOLD: 172. Switch to a new path only if it is | PARENT_SWITCH_THRESHOLD: 172. Switch to a new path only if it is | |||
expected to require at least 1.5 fewer transmissions than the | expected to require at least 1.5 fewer transmissions than the | |||
current path. As ETX is encoded as number of transmissions times | current path. As ETX is encoded as number of transmissions times | |||
128, this is a threshold of 172. | 128, this is a threshold of 172. | |||
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 | ALLOW_FLOATING_ROOT: 0. Do not allow a node to become a floating | |||
skipping to change at page 10, line 45 | skipping to change at page 10, line 43 | |||
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 [RFC6551] are not used and | the exception that metrics as specified in [RFC6551] are not used and | |||
do not require management. | do not require 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 | PARENT_SWITCH_THRESHOLD, PARENT_SET_SIZE, and ALLOW_FLOATING_ROOT. | |||
ALLOW_FLOATING_ROOT. An implementation MAY allow these parameters to | An implementation MAY allow these parameters to be configured | |||
be configured dynamically at run time once a network has been | dynamically at run time once a network has been deployed. | |||
deployed. | ||||
A MRHOF implementation SHOULD support the DODAG Configuration option | A MRHOF implementation SHOULD support the DODAG Configuration option | |||
as described in [RFC6550] and apply the parameters it specifies. | as described in [RFC6550] and apply the parameters it specifies. | |||
Care should be taken in the relationship between the MRHOF | Care should be taken in the relationship between the MRHOF | |||
PARENT_SWITCH_THRESHOLD parameter and the RPL MaxRankIncrease | PARENT_SWITCH_THRESHOLD parameter and the RPL MaxRankIncrease | |||
parameter. For example, if MaxRankIncrease is smaller than | parameter. For example, if MaxRankIncrease is smaller than | |||
PARENT_SWITCH_THRESHOLD, a RPL node using MRHOF could enter a | PARENT_SWITCH_THRESHOLD, a RPL node using MRHOF could enter a | |||
situation where its current preferred parent causes the nodes Rank to | situation where its current preferred parent causes the nodes Rank to | |||
increase more than MaxRankIncrease but MRHOF does not change | increase more than MaxRankIncrease but MRHOF does not change | |||
preferred parents: this could cause the node to leave the routing | preferred parents: this could cause the node to leave the routing | |||
topology even though there may be other members of the parent set | topology even though there may be other members of the parent set | |||
which would allow the node's Rank to remain within MaxRankIncrease. | which would allow the node's Rank to remain within MaxRankIncrease. | |||
End of changes. 11 change blocks. | ||||
19 lines changed or deleted | 13 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/ |