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