Internet DRAFT - draft-gnawali-roll-etxof
draft-gnawali-roll-etxof
Networking Working Group O. Gnawali
Internet-Draft P. Levis
Intended status: Standards Track Stanford University
Expires: November 24, 2010 May 23, 2010
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 to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on November 24, 2010.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
Gnawali & Levis Expires November 24, 2010 [Page 1]
Internet-Draft draft-gnawali-roll-etxof-01 May 2010
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 BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. The ETX Objective Function . . . . . . . . . . . . . . . . . . 4
3.1. Computing the ETX Path metric . . . . . . . . . . . . . . . 4
3.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 5
3.3. Advertising the ETX Path metric . . . . . . . . . . . . . . 6
4. ETXOF Constants, Variables, and Parameters . . . . . . . . . . 6
5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 6
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 6
7. Security Considerations . . . . . . . . . . . . . . . . . . . . 6
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7
8.1. Normative References . . . . . . . . . . . . . . . . . . . 7
8.2. Informative References . . . . . . . . . . . . . . . . . . 7
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 7
Gnawali & Levis Expires November 24, 2010 [Page 2]
Internet-Draft draft-gnawali-roll-etxof-01 May 2010
1. Introduction
An objective function allows RPL [I-D.ietf-roll-rpl] 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] 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 [RFC2119].
This terminology used in this document is consistent with the
terminologies described in [I-D.ietf-roll-terminology],
[I-D.ietf-roll-rpl], and [I-D.ietf-roll-routing-metrics].
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.
Gnawali & Levis Expires November 24, 2010 [Page 3]
Internet-Draft draft-gnawali-roll-etxof-01 May 2010
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] 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
Gnawali & Levis Expires November 24, 2010 [Page 4]
Internet-Draft draft-gnawali-roll-etxof-01 May 2010
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.
Gnawali & Levis Expires November 24, 2010 [Page 5]
Internet-Draft draft-gnawali-roll-etxof-01 May 2010
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.
Gnawali & Levis Expires November 24, 2010 [Page 6]
Internet-Draft draft-gnawali-roll-etxof-01 May 2010
8. References
8.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
8.2. Informative References
[I-D.ietf-roll-routing-metrics]
Vasseur, J. and D. Networks, "Routing Metrics used for
Path Calculation in Low Power and Lossy Networks",
draft-ietf-roll-routing-metrics-01 (work in progress),
October 2009.
[I-D.ietf-roll-rpl]
Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
Protocol for Low power and Lossy Networks",
draft-ietf-roll-rpl-05 (work in progress), December 2009.
[I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-01 (work in
progress), May 2009.
Authors' Addresses
Omprakash Gnawali
Stanford University
S255 Clark Center, 318 Campus Drive
Stanford, CA 94305
USA
Phone: +1 650 725 6086
Email: gnawali@cs.stanford.edu
Philip Levis
Stanford University
358 Gates Hall, Stanford University
Stanford, CA 94305
USA
Email: pal@cs.stanford.edu
Gnawali & Levis Expires November 24, 2010 [Page 7]
