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/