draft-ietf-roll-minrank-hysteresis-of-06.txt   draft-ietf-roll-minrank-hysteresis-of-07.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: September 7, 2012 March 6, 2012 Expires: September 10, 2012 March 9, 2012
The Minimum Rank with Hysteresis Objective Function The Minimum Rank with Hysteresis Objective Function
draft-ietf-roll-minrank-hysteresis-of-06 draft-ietf-roll-minrank-hysteresis-of-07
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 38 skipping to change at page 1, line 38
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 September 7, 2012. This Internet-Draft will expire on September 10, 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 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.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 . . . . . . . . . . . . . 8 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 . . . . . . . . . . . . . . . . . . . . . . . 11 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
9. Security Considerations . . . . . . . . . . . . . . . . . . . 11 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.1. Normative References . . . . . . . . . . . . . . . . . . . 12 10.1. Normative References . . . . . . . . . . . . . . . . . . . 12
10.2. Informative References . . . . . . . . . . . . . . . . . . 12 10.2. Informative References . . . . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13
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. For example, if an RPL instance uses an objective function paths. For example, if an RPL instance uses an objective function
that minimizes hop-count, RPL will select paths with minimum hop that minimizes hop-count, RPL will select paths with minimum hop
count. RPL requires that all nodes in a network use a common OF; count. RPL requires that all nodes in a network use a common OF;
relaxing this requirement may be a subject of future study. relaxing this 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
skipping to change at page 7, line 31 skipping to change at page 7, line 31
+--------------------+------------+ +--------------------+------------+
| 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.
Rank is undefined for these node/link metrics: Node state and 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 RPL Leaf node according the node must join one of the neighbors as a RPL Leaf node according
to [I-D.ietf-roll-rpl]. to [I-D.ietf-roll-rpl].
MRHOF uses this Rank value to compute the Rank it associates with the MRHOF uses this Rank value to compute the Rank it associates with the
path through each member of the parent set. The Rank associated with path through each meqber of the parent set. The Rank associated with
a path through a member of the parent set is the maximum of the a path through a member of the parent set is the maximum of two
corresponding calculated Rank value from above and that node's values. The first is corresponding Rank value calculated with the
advertised Rank plus MinHopRankIncrease. table above, the second is the that node's advertised Rank plus
MinHopRankIncrease.
A node sets its Rank to the maximum of three values: A node sets its Rank to the maximum of three values:
1. The Rank associated with the path through the preferred parent 1. The Rank calculated for the path through the preferred parent
2. The Rank of the member of the parent set with the highest 2. The Rank of the member of the parent set with the highest
advertised Rank plus one advertised Rank plus one
3. The Rank of the path through the member of the parent set with 3. The largest calculated Rank among paths through the parent set,
the highest path cost, minus MaxRankIncrease minus MaxRankIncrease
The first case is the Rank associated with the path through the The first case is the Rank associated with the path through the
preferred parent. The second case covers requirement 4 of Rank preferred parent. The second case covers requirement 4 of Rank
advertisements in Section 8.2.1 of [I-D.ietf-roll-rpl]. The third advertisements in Section 8.2.1 of [I-D.ietf-roll-rpl]. The third
case ensures that a node does not advertise a Rank which then case ensures that a node does not advertise a Rank which then
precludes it from using members of its parent set. precludes it from using members of its parent set.
Note that the third case means that a node advertises a conservative
Rank value based on members of its parent set, which might be
significantly higher than the Rank calculated for the path through
the preferred parent. Accordingly, picking a parent set whose paths
have a large range of Ranks will likely result in sub-optimal
routing: nodes will not choose good paths because they are advertised
as much worse than they actually are. The exact selection of a
parent set is an implementation decision.
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 its cur_min_path_cost variable to the path cost corresponding to its
preferred parent. It then calculates the metric it will advertise in preferred parent. It then calculates the metric it will advertise in
its metric container. This value is the path cost of the member of its metric container. This value is the path cost of the member of
the parent set with the highest path cost. Thus, while the parent set with the highest path cost. Thus, while
cur_min_path_cost is the cost through the preferred parent, a node cur_min_path_cost is the cost through the preferred parent, a node
advertises the highest cost path from the node to the root through a advertises the highest cost path from the node to the root through a
member of the parent set. The value of the highest cost path is member of the parent set. The value of the highest cost path is
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, cur_min_path_cost is directly used as If ETX is the selected metric, a node SHOULD NOT advertise it in a
Rank and never advertised in a metric container. metric container. Instead, a node MUST advertise an approximation of
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
holding an ETX metric, MRHOF MUST ignore the ETX metric value in its
Rank calculations.
DODAG Roots advertise a metric value which computes to a cost of DODAG Roots advertise a metric value which computes to a cost of
MIN_PATH_COST. MIN_PATH_COST.
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
 End of changes. 12 change blocks. 
16 lines changed or deleted 30 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/