The ETX Objective Function for RPL
draft-gnawali-roll-etxof-01

Abstract

The ETX metric of a wireless link is the expected number of transmissions required to successfully transmit and acknowledge a packet on the link. The Routing Protocol for Low Power and Lossy Networks (RPL) allows the use of objective functions to construct routes that optimize or constrain a routing metric on the paths. This specification describes ETXOF, an objective function that minimizes ETX. The RPL path computation using ETXOF results in minimum-ETX paths from the nodes to the DAG roots, i.e., paths that minimize the number of packet transmissions for packet delivery from nodes in the network to the DAG root.

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 24, 2010.

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.  The ETX Objective Function
    3.1.  Computing the ETX Path metric
    3.2.  Parent Selection
    3.3.  Advertising the ETX Path metric
4.  ETXOF Constants, Variables, and Parameters
5.  Acknowledgements
6.  IANA Considerations
7.  Security Considerations
8.  References
    8.1.  Normative References
    8.2.  Informative References
§  Authors' Addresses

1.  Introduction

An objective function allows RPL [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., and R. Team, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” December 2009.) to optimize or constrain the routing metric of a path. RPL achieves this goal by selecting the parent among the alternate parents as dictated by that objective function. For example, if an RPL instance uses an objective function that minimizes hop-count, RPL will select paths with minimum hop count. Different objective functions optimize or constrain different metrics.

The ETX metric describes the expected number of transmissions required to successfully transmit and acknowledge a packet on a wireless link. The ETX metric is commonly used in wireless routing to distinguish between paths that require a large number of packet transmissions from those that require a smaller number of packet transmissions for successful packet delivery and acknowledgement. The nodes running RPL might use a number of mechanisms to estimate the ETX metric of a link [I‑D.ietf‑roll‑routing‑metrics] (Vasseur, J. and D. Networks, “Routing Metrics used for Path Calculation in Low Power and Lossy Networks,” October 2009.) and make it available for route selection.

This specification describes ETXOF, an ETX Objective function for RPL. ETXOF is an objective function that allows RPL to find a minimum-ETX path from the nodes to a root in the DAG instance. The minimum-ETX path between a node and the DAG root is the path (among other paths between the source and the destination) that requires the least number of packet transmissions per packet delivery to the DAG root. Thus, minimum-ETX paths are generally also the most energy-efficient paths in the network.

2.  Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "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].

This terminology used in this document is consistent with the terminologies described in [I‑D.ietf‑roll‑terminology] (Vasseur, J., “Terminology in Low power And Lossy Networks,” May 2009.), [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., and R. Team, “RPL: IPv6 Routing Protocol for Low power and Lossy Networks,” December 2009.), and [I‑D.ietf‑roll‑routing‑metrics] (Vasseur, J. and D. Networks, “Routing Metrics used for Path Calculation in Low Power and Lossy Networks,” October 2009.).

This document introduces one term:

Path metric:

Path metric quantifies a property of an end-to-end path. Path metrics can be used by RPL to compare different paths.

3.  The ETX Objective Function

The ETX Objective Function, ETXOF, is designed to find the path that can be used to deliver a packet from a node to the root in a DAG instance with the least number of transmissions. It does so by using the ETX metric defined in [I‑D.ietf‑roll‑routing‑metrics] (Vasseur, J. and D. Networks, “Routing Metrics used for Path Calculation in Low Power and Lossy Networks,” October 2009.) as the link metric, computing a ETX Path metric based on the ETX link metric, and choosing paths with the smallest path ETX.

3.1.  Computing the ETX Path metric

Nodes compute the ETX Path metric for each candidate neighbor reachable on all the interfaces. The ETX Path metric represents the ETX cost of the path from a node to the root of the DODAG through the neighbor.

Root nodes (Grounded or Floating) set the variable min_path_etx to MIN_ETX_PATH_CONST.

A non-root node computes the ETX Path metric for a path to the root through each candidate neighbor by adding these two components:

1. The ETX metric for the link to a candidate neighbor
2. The min_path_etx advertised by that neighbor.

A node SHOULD compute the ETX Path metric for the path through each candidate neighbor reachable through all interfaces. If a node cannot compute the ETX path metric for the path through a candidate neighbor, the node MUST NOT make that candidate neighbor its preferred parent.

If the ETX metric of the link to a neighbor is not available, the ETX Path metric for the path through that neighbor SHOULD be set to INFINITY. This metric value will prevent this path from being considered for path selection, hence avoiding potentially high ETX paths.

The ETX Path metric corresponding to a neighbor MUST be re-computed each time:

1. The ETX metric of the link to the candidate neighbor is updated.
2. A node receives a new min_path_etx advertisement from the candidate neighbor.

This computation MAY also be performed periodically. However, long intervals between periodic computation or deferring the computation for too long after new min_path_etx advertisements or updates to the link metric prevents a node from making parent selection decision based on the most up-to-date link and path quality information.

3.2.  Parent Selection

After computing the ETX Path metric for all the candidate neighbors reachable through all the interfaces for the current DODAG iteration, a node selects the preferred parent. This process is called parent selection.

A node MUST select a candidate neighbor as its preferred parent if the ETX Path metric corresponding to that neighbor is smaller than the ETX Path metric corresponding to the rest of the neighbors, except as indicated below:

1. If the ETX Path metric of the current preferred parent is greater than the smallest ETX Path metric by less than PARENT_SWITCH_ETX_THRESHOLD, the node MAY continue to use the current preferred parent.
2. A node MAY declare itself as a Floating root, and hence no preferred parent, depending on the configuration.
3. If the ETX metric for a link is greater than MAX_ETX_LINK_CONST, the node SHOULD exclude that link from consideration for parent selection.
4. If min_path_etx is greater than MAX_ETX_PATH_CONST, the node MAY declare itself as a Floating root.
5. If the configuration disallows a node to be a Floating root and no neighbors are discovered, the node does not have a preferred parent, and MUST set min_path_etx to INFINITY.
6. If the ETX Path metric corresponding to multiple candidate neighbors are equal to min_path_etx, a node MAY use a different objective function to select the preferred parent among the candidates with the ETX Path metric equal to min_path_etx. If the current preferred parent is one of the candidates with the ETX Path metric equal to min_path_etx, the node SHOULD continue to use the current preferred parent. Continuing to use the same parent prevents potential churn in the network.

3.3.  Advertising the ETX Path metric

Once the preferred parent is selected, the node sets its min_path_etx variable to the ETX Path metric corresponding to the preferred parent. Thus, min_path_etx is the cost of the minimum-ETX path from the node to the root. The value of the min_path_etx is carried in the metric container whenever DIO messages are sent.

4.  ETXOF Constants, Variables, and Parameters

ETXOF uses the following variable:

min_path_etx: The ETX path metric of the path from a node through its preferred parent to the root computed at the last parent selection.

ETXOF uses the following constants:

MIN_ETX_LINK_CONST: 1.0

MIN_ETX_PATH_CONST: 1.0

ETXOF uses the following parameters:

MAX_ETX_LINK_CONST: Maximum allowed link ETX.

MAX_ETX_PATH_CONST: Maximum allowed path ETX.

PARENT_SWITCH_ETX_THRESHOLD: The difference between ETX of the path through the preferred parent and the minimum-ETX path to trigger new preferred parent selection.

5.  Acknowledgements

6.  IANA Considerations

This specification requires an allocated OCP for ETX. A value of 1 is requested.

7.  Security Considerations

Security considerations to be developed in accordance to the output of the WG.

8.  References

8.1. Normative References

8.2. Informative References

Authors' Addresses