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

Abstract

The Routing Protocol for Low Power and Lossy Networks (RPL) defines a generic Distance Vector protocol that is adapted to such networks. RPL requires a specific Objective Function to establish a desired routing topology. This document specifies a basic Objective Function that relies only on RPL's basic Protocol Data Units; it does not use extensions such as RPL metric containers.

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 [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 November 06, 2011.

Copyright Notice

Copyright (c) 2011 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. Objective Function 0 Overview
• 4. OF0 operations
• 4.1. Computing Rank
• 4.2. Feasible successors selection
• 4.2.1. Selection of the Preferred Parent
• 4.2.2. Selection of the backup feasible successor
• 5. Abstract Interface with RPL core
• 6. OF0 Operands
• 6.1. Variables
• 6.2. Configurable parameters
• 6.3. Constants
• 7. IANA Considerations
• 8. Security Considerations
• 9. Acknowledgements
• 10. References
• 10.1. Normative References
• 10.2. Informative References
• Author's Address

1. Introduction

The Routing Protocol for Low Power and Lossy Networks [I-D.ietf-roll-rpl] was designed as a generic core that is agnostic to metrics and that is adapted to a given problem using Objective Functions (OF). This separation of Objective Functions from the core protocol specification allows RPL to adapt to meet the different optimization criteria required by the wide range of use cases.

RPL forms Destination Oriented Directed Acyclic Graphs (DODAGs) within instances of the protocol. Each instance is associated with a specialized Objective Function. A DODAG is periodically reconstructed in a new Version to enable a global reoptimization of the graph.

An Objective Function selects the DODAG Version that a device joins within an instance, and a number of neighbor routers within that DODAG Version as parents or feasible successors. The OF generates the Rank of the device, that represents an abstract distance to the root within the DODAG. In turn, the Rank is used by the generic RPL core to enable a degree of loop avoidance and verify forward progression towards a destination, as specified in [I-D.ietf-roll-rpl].

The Objective Function 0 (OF0) corresponds to the Objective Code Point 0 (OCP0). OF0 only requires the information in the RPL DIO base container, such as Rank and the DODAGPreference field that describes an administrative preference [I-D.ietf-roll-rpl]. The Rank of a node is obtained by adding a normalized scalar, rank_increase, to the Rank of a selected preferred parent. OF0 uses a unit MinHopRankIncrease of rank_increase of 0x100 so that Rank value can be stored in one octet. This allows up to at least 28 hops even when default settings are used and each hop has the worst rank_increase of 9.

Since there is no default OF or metric container in the RPL main specification, it might happen that, unless two given implementations follow the same guidance for a specific problem or environment, those implementations will not support a common OF with which they could interoperate. OF0 is designed to be common to all implementations that are not specifically designed to apply to a given case for which further guidance is provided. This is why it is very abstract as to how the link properties are transformed into a rank_increase and leaves that responsibility to implementation; rather, OF0 enforces normalized values for the rank_increase of a normal link and its acceptable range, as opposed to formulating the details of its computation. This is also why OF0 ignores metric containers.

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] and [I-D.ietf-roll-rpl].

The term feasible successor is used to refer to a neighbor that can possibly be used as a next-hop for upwards traffic following the loop avoidance and forwarding rules that the nodes implements and that are defined outside of this specification, in particular in the RPL specification.

3. Objective Function 0 Overview

The core RPL specification describes constraints on how nodes select potential parents, called a parent set, from their neighbors. All parents are feasible successors for upgoing traffic (towards the root). Additionally, RPL allows the use of parents in a subsequent Version of a same DODAG as feasible successors, in which case this node acts as a leaf in the subsequent DODAG Version. Further specifications might extend the set of feasible successors, for instance to nodes of a same Rank, aka siblings.

The Goal of the OF0 is for a node to join a DODAG Version 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. This can be achieved if the Rank of a node represents closely its distance to the root. This need is balanced with the other need of maintaining some path diversity. 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.

OF0 selects a preferred parent and a backup feasible successor if one is available. All the upward traffic is normally routed via the preferred parent. When the link conditions do not let an upward packet through the preferred parent, the packet is passed to the backup feasible successor.

OF0 assigns a step_of_rank to each link to another node that it monitors. The exact method for computing the step_of_rank is implementation-dependent.

4. OF0 operations

4.1. Computing Rank

One trivial OF0 implementation might compute the step_of_rank from as a classical administrative cost that is assigned to the link. Using a metric similar to hop count implies that the OF0 implementation only considers neighbors with good enough connectivity, for instance neighbors that are reachable over an Ethernet link, or a WIFI link in infrastructure mode.

In most wireless networks, a Rank that is analogous to an unweighted hop count favors paths with long distance links and poor connectivity properties. Other link properties such as the expected transmission count metric (ETX) [DeCouto03] should be used instead to compute the step_of_rank. For instance, the Minimum Rank Objective Function with Hysteresis [I-D.ietf-roll-minrank-hysteresis-of] provides guidance on how link cost can be computed and on how hysteresis can improve Rank stability.

An implementation MAY allow to stretch the step_of_rank with a stretch_of_rank up to no more than MAXIMUM_RANK_STRETCH in order to enable the selection of a feasible successor and maintain path diversity. The use of a stretch_of_rank augments the apparent distance from the node to the root and distorts the DODAG; it should be used with care so as to avoid instabilities due to greedy behaviours.

The step_of_rank is expressed in units of MINIMUM_STEP_OF_RANK. As a result, the least significant octet in the RPL Rank is not used. The default step_of_rank is DEFAULT_STEP_OF_RANK for each hop. An implementation MUST maintain the stretched step_of_rank between MINIMUM_STEP_OF_RANK and MAXIMUM_STEP_OF_RANK, which allows to reflect a large variation of link quality.

The gap between MINIMUM_STEP_OF_RANK and MAXIMUM_RANK_STRETCH may not be sufficient in every case to strongly distinguish links of different types or categories in order to favor, say, powered over battery-operated or wired over wireless, within a same DAG.

An implementation SHOULD allow a configurable factor called Rank-factor and to apply the factor on all links and peers.

An implementation MAY recognizes sub-categories of peers and links, such as different MAC types, in which case it SHOULD be able to configure a more specific Rank-factor to those categories. The Rank-factor SHOULD be set between MINIMUM_RANK_FACTOR and MAXIMUM_RANK_FACTOR.

The step_of_rank Sp that is computed for that link is multiplied by the Rank-factor Rf and then possibly stretched by a stretch_of_rank Sr. The resulting rank_increase Ri is added to the Rank of preferred parent R(P) to obtain that of this node R(N):

R(N) = R(P) + Ri where Ri = (Rf*Sp + Sr) * MinHopRankIncrease

Optionally, the administrative preference of a root MAY be configured to supersede the goal to join a Grounded DODAG. 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 vicinity.

4.2. Feasible successors selection

4.2.1. Selection of the Preferred Parent

As it scans all the candidate neighbors, OF0 performs in order the following checks and keeps the parent that is the best for the first criterion that makes a difference:

1. [I-D.ietf-roll-rpl] spells out the generic rules for a node to reparent and in particular the boundaries to augment its Rank within a DODAG Version. 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 preferable.
3. When multiple interfaces are available, a policy might be locally configured to order them and that policy applies first; that is a router on a higher order interface in the policy is preferable.
4. If the administrative preference of the root is configured to supersede the goal to join a Grounded DODAG, a router that offers connectivity to a more preferable root SHOULD be preferred.
5. A router that offers connectivity to a grounded DODAG Version SHOULD be preferred over one that does not.
6. A router that offers connectivity to a more preferable root SHOULD be preferred.
7. When comparing 2 routers that belong to the same DODAG, a router that offers connectivity to the freshest DODAG Version SHOULD be preferred.
8. The parent that causes the lesser resulting Rank for this node, as specified in Section 4.1, SHOULD be preferred.
9. A DODAG Version for which there is an alternate parent SHOULD be preferred. This check is optional. It is performed by computing the backup feasible successor while assuming that the router that is currently examined is finally selected as preferred parent.
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.

4.2.2. Selection of the backup feasible successor

When selecting a backup feasible successor, the OF performs in order the following checks:

1. When multiple interfaces are available, a router on a higher order interface is preferable.
2. The backup feasible successor MUST NOT be the preferred parent.
3. The backup feasible successor MUST be either in the same DODAG Version as this node or in an subsequent DODAG Version.
4. Along with RPL rules, a Router in the same DODAG Version as this node and with a Rank that is higher than the Rank computed for this node MUST NOT be selected as a feasible successor.
5. A router with a lesser Rank SHOULD be preferred.
6. A router that has been validated as usable by an implementation dependant validation process SHOULD be preferred.
7. The backup feasible successor that was in use already SHOULD be preferred.

5. 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 OF is called to provide information about a given instance. This includes material from the DIO base header, the role (router, leaf), and the Rank of this node.

Providing a Parent List:

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

Trigger:

The OF0 support may trigger the RPL core to inform it that a change occurred. This can be used to indicate whether the change requires a new DIO to be fired or whether trickle timers need to be reset.

6. OF0 Operands

6.1. Variables

OF0 uses the following variables:

step_of_rank (unsigned integer):

an intermediate computation based on the link properties with a certain neighbor.

rank-increase (unsigned integer):

delta between the Rank of the preferred parent and self

6.2. Configurable parameters

OF0 can use the following optional parameters:

stretch_of_rank (unsigned integer):

an optional augmentation to the step-of-rank of the preferred parent to allow the selection of additional parents.

rank_factor (unsigned integer):

A configurable factor that is used to multiply the effect of the link properties in the rank_increase computation.

6.3. Constants

OF0 fixes the following constants:

MinHopRankIncrease:

256

DEFAULT_STEP_OF_RANK:

3

MINIMUM_STEP_OF_RANK:

1

MAXIMUM_STEP_OF_RANK:

9

DEFAULT_RANK_STRETCH:

0

MAXIMUM_RANK_STRETCH:

5

DEFAULT_RANK_FACTOR:

1

MINIMUM_RANK_FACTOR:

1

MAXIMUM_RANK_FACTOR:

4

7. IANA Considerations

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

8. 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].

9. Acknowledgements

Most specific thanks to Philip Levis and Phoebus Chen for their help in finalizing this document.

Many thanks also 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.

10. References

10.1. Normative References

10.2. Informative References

Author's Address