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/