RPL Objective Function 0
draft-ietf-roll-of0-04

Abstract

The Routing Protocol for Low Power and Lossy Networks (RPL) defines a generic Distance Vector protocol for Low Power and Lossy Networks (LLNs). RPL is instantiated to honor a particular routing objective/constraint by the adding a specific Objective Function (OF) that is designed to solve that problem. This specification defines a basic OF, OF0, that uses only the abstract properties exposed in RPL messages to maximize connectivity.

Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.) [RFC2119].

Status of this Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”

This Internet-Draft will expire on June 11, 2011.

Copyright Notice

Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

1.  Introduction
2.  Terminology
3.  Goal
4.  Selection of the Preferred Parent
5.  Selection of the Backup next_hop
6.  Abstract Interface with RPL core
7.  OF0 Constants and Variables
8.  IANA Considerations
9.  Security Considerations
10.  Acknowledgements
11.  References
    11.1.  Normative References
    11.2.  Informative References
§  Author's Address

1.  Introduction

The IETF ROLL Working Group has defined application-specific routing requirements for a Low Power and Lossy Network (LLN) routing protocol, specified in [I‑D.ietf‑roll‑building‑routing‑reqs] (Martocci, J., Riou, N., Mil, P., and W. Vermeylen, “Building Automation Routing Requirements in Low Power and Lossy Networks,” September 2009.), [I‑D.ietf‑roll‑home‑routing‑reqs] (Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirements in Low Power and Lossy Networks,” September 2009.), [RFC5673] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low-Power and Lossy Networks,” October 2009.), and [RFC5548] (Dohler, M., Watteyne, T., Winter, T., and D. Barthel, “Routing Requirements for Urban Low-Power and Lossy Networks,” May 2009.).

Considering the wide variety of use cases, link types and metrics, the Routing Protocol for Low Power and Lossy Networks (Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Vasseur, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” November 2010.) [I‑D.ietf‑roll‑rpl] was designed as a generic core that is agnostic to metrics and instantiated using Objective Functions.

RPL forms Destination Oriented Directed Acyclic Graphs (DODAGs) within instances of the protocol, each instance being set up to honor a particular routing objective/constraint of a given deployment. This instantiation is achieved by plugging into the RPL core a specific Objective Function (OF) that is designed to solve that problem to be addressed by that instance.

the Objective Function selects the DODAG iteration that a device joins, and a number of neighbor routers within that iteration as parents and siblings. The OF is also responsible for computing the Rank of the device, that abstracts a relative position within the DODAG and is used by the RPL core to enable a degree of loop avoidance and verify forward progression towards a destination, as specified in [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Vasseur, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” November 2010.).

This specification defines the Objective Function 0 (OF0), that corresponds to the Objective Code Point 0. OF0 does not leverage link layer metrics such as described in the metrics draft (Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. Barthel, “Routing Metrics used for Path Calculation in Low Power and Lossy Networks,” December 2010.) [I‑D.ietf‑roll‑routing‑metrics], but is only based on abstract information from the DIO base container, such as Rank and an administrative preference, that is transported in DIOs as DODAGPreference in [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Vasseur, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” November 2010.).

2.  Terminology

The terminology used in this document is consistent with and incorporates that described in `Terminology in Low power And Lossy Networks' [I‑D.ietf‑roll‑terminology] (Vasseur, J., “Terminology in Low power And Lossy Networks,” September 2010.) and [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Vasseur, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” November 2010.).

3.  Goal

The Goal of the OF0 is to join a DODAG iteration that offers connectivity to a specific set of nodes or to a larger routing infrastructure. For the purpose of OF0, Grounded thus means that the root provides such connectivity. How that connectivity is asserted and maintained is out of scope.

Objective Function 0 is designed to find the nearest Grounded root. In the absence of a Grounded root, LLN inner connectivity is still desirable and floating DAGs will form, rooted at the nodes with the highest administrative preference.

The metric used in OF0 is an administratively defined scalar cost that is trivially added up along a path to compute the RPL Rank, as defined in [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Vasseur, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” November 2010.). As a result, the Rank if a node is analogous to a weighted hop count of the path to the root. Using a metric that in essence is similar to hop count implies that the quality of the connectivity should be asserted so that only neighbors with a good enough connectivity are presented to the OF. How that connectivity is asserted and maintained is out of scope.

Hop count used in wireless networks will tend to favor paths with long distance links and non optimal connectivity properties. As a result, the link selection must be very conservative, and the available link set is thus constrained. In some situations, this might end up partitioning the network. For those reasons, though it can be used on wired links and wired link emulations such as WIFI infrastructure mode, OF0 is generally not recommended for wireless networks.

The default step of Rank is DEFAULT_RANK_INCREMENT for each hop. An implementation MAY allow a step between MINIMUM_RANK_INCREMENT and MAXIMUM_RANK_INCREMENT to reflect a large variation of link quality by units of MINIMUM_RANK_INCREMENT. In other words, the least significant octet in the Rank is not used.

It MAY stretch its step of Rank by up to MAXIMUM_RANK_STRETCH in order to enable the selection of a sibling when only one parent is available. For instance, say that a node computes a step of Rank of 4 units of MINIMUM_RANK_INCREMENT from a preferred parent with a Rank of 6 units resulting in a Rank of 10 units for this node. Say that with that Rank of 10 units, this node would end up with only one parent and no sibling, though there is a neighbor with a Rank of 12 units. In that case, the node is entitled to stretch its step of Rank by a value of 2 units, thus using a step of Rank of 6 units so as to reach a Rank of 12 units and find a sibling. But the node is not entitled to use a step of Rank larger than 6 units since that would be a greedy behavior that would deprive the neighbor of this node of a successor. Also, if the neighbor had exposed a Rank of 16 units, the stretch of Rank from 10 to 16 units would have exceeded MAXIMUM_RANK_STRETCH of 4 units and thus the neighbor would not have been selectable even as a sibling.

Optionally, the administrative preference of a root MAY be configured to supercede the goal to reach Grounded root. In that case, nodes will associate to the root with the highest preference available, regardless of whether that root is Grounded or not. Compared to a deployment with a multitude of Grounded roots that would result in a same multitude of DODAGs, such a configuration may result in possibly less but larger DODAGs, as many as roots configured with the highest priority in the reachable vincinity.

OF0 selects a preferred parent and a backup next_hop if one is available. The backup next_hop might be a parent or a sibling. All the traffic is routed via the preferred parent. When the link conditions do not let a packet through the preferred parent, the packet is passed to the backup next_hop.

4.  Selection of the Preferred Parent

As it scans all the candidate neighbors, OF0 keeps the parent that is the best for the following criteria (in order):

1. [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Vasseur, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” November 2010.) spells out the generic rules for a node to reparent and in particular the boundaries to augment its Rank within a DODAG iteration. A candidate that would not satisfy those rules MUST NOT be considered.
2. An implementation should validate a router prior to selecting it as preferred. This validation process is implementation and link type dependent, and is out of scope. A router that has been validated is preferrable.
3. When multiple interfaces are available, a policy might be locally configured to prioritize them and that policy applies first; that is a router on a higher order interface is preferable.
4. In the absence of a Grounded DODAG iteration, the router with a higher administrative preference SHOULD be preferred. Optionally, this selection applies regardless of whether the DODAG is Grounded or not.
5. A router that offers connectivity to a grounded DODAG iteration SHOULD be preferred over one that does not.
6. When comparing 2 routers that belong to the same DODAG, a router that offers connectivity to the freshest sequence SHOULD be preferred.
7. When computing a resulting Rank for this node from a parent Rank and a Step of Rank from that parent, the parent that causes the lesser resulting Rank SHOULD be preferred.
8. A DODAG iteration for which there is an alternate parent SHOULD be preferred. This check is optional. It is performed by computing the backup next_hop while assuming that the router that is currently examined is finally selected as preferred parent.
9. The DODAG iteration that was in use already SHOULD be preferred.
10. The preferred parent that was in use already SHOULD be preferred.
11. A router that has announced a DIO message more recently SHOULD be preferred.

5.  Selection of the Backup next_hop

• When multiple interfaces are available, a router on a higher order interface is preferable.
• The preferred parent MUST be ignored.
• A Router that is not in the same DODAG as the preferred parent, either in the current or a subsequent iteration, MUST be ignored.
• A Router with a Rank that is higher than the Rank computed for this node out of the preferred parent SHOULD NOT be selected as parent, to avoid greedy behaviors. It MAY still be selected as sibling if no better Back-up next hop is found.
• A router with a lesser Rank SHOULD be preferred.
• A router that has been validated as usable by an implementation dependant validation process SHOULD be preferred.
• The backup next_hop that was in use already SHOULD be preferred.

6.  Abstract Interface with RPL core

Objective Function 0 interacts with the core RPL in the following ways:

Processing DIO:

This core RPL triggers the OF when a new DIO was received. OF0 analyses the information in the DIO and may select the source as a parent or sibling.

Providing DAG information

The OF0 support can be required to provide the DAG information for a given instance to the RPL core. This includes the material that is contained in a DIO base header.

Providing a Parent List

The OF0 support can be required to provide the list of the parents for a given instance to the RPL core. This includes the material that is contained in the transit option for that parent.

Trigger

The OF0 support may trigger the RPL core to inform it that a change occurred. This indicates whether the change requires a new DIO to be fired, trickle timers to be reset, etc...

7.  OF0 Constants and Variables

OF0 uses the following constants:

MinHopRankIncrease:

256

DEFAULT_RANK_INCREMENT:

4 * MinHopRankIncrease

MINIMUM_RANK_INCREMENT:

1 * MinHopRankIncrease

MAXIMUM_RANK_INCREMENT:

16 * MinHopRankIncrease

MAXIMUM_RANK_STRETCH:

4 * MinHopRankIncrease

8.  IANA Considerations

IThis specification requires the assignment of an OCP for OF0. The value of 0 is suggested.

9.  Security Considerations

Security Considerations for OCP/OF are to be developed in accordance with recommendations laid out in, for example, [I‑D.tsao‑roll‑security‑framework] (Tsao, T., Alexander, R., Daza, V., and A. Lozano, “A Security Framework for Routing over Low Power and Lossy Networks,” March 2010.).

10.  Acknowledgements

Most specific thanks to Tim Winter, JP Vasseur, Julien Abeille, Mathilde Durvy, Teco Boot, Navneet Agarwal and Henning Rogge for in-depth review and first hand implementer's feedback.

11.  References

11.1. Normative References

11.2. Informative References

Author's Address