RPL

Owned by OpenWSN Admin
Last updated: Nov 19, 2012 by Thomas Watteyne

Status

IETF ROLL is an active working group. The working documents it has produced are which are most applicable to the OpenWSN project are:

In all likelihood, subsequent revisions of these two documents will be merged to form the RPL RFC, sometimes in mid-2010.

One may be interested in reading the application requirements identified by IETF ROLL prior to developing RPL. There requirements are divided in the next 4 application domain

Overview

RPL is a routing protocol. It operates on top of 802.15.4e. The routing layer (aka layer 3) is responsible for relaying packets across multiple hops separating source and destination nodes. It is divided into a forwarding engine, which uses a routing table to decide which neighbor node is the next hop for that packet, and a routing protocol, which populate that routing table. RPL is a routing protocol.

RPL is designed for Low Power and Lossy Wireless Networks such as Wireless Sensor Networks. It hence it optimized for collection networks (where nodes periodically report measurements to a small number of collection points) with infrequent communication from the collection point to individual nodes. RPL dubs collection traffic Multi-Point-to-Point (MP2P) and configuration traffic Point-To-Multi-Point (P2MP). RPL does not support Point-To-Point (P2P) traffic well, although workarounds can be used.

For MP2P traffic, RPL builds a gradient into the network, grounded at the collection points called Low power and lossy network Border Router (LBR). Each node is assigned a rank such that rank increases as the node is far from the LBR. In RPL, this gradient is called a Destination Oriented Directed Acyclic Graph (DODAG). Forwarding a packet to the LBR roughly consist in picking the neighbor node with the lowest rank.

Nodes running RPL exchange signaling information to setup and maintain the DODAG. This information is exchanged as a new type of ICMPv6 message called the RPL Control Message. The 1B code in the ICMPv6 header is used to differentiate between different sub-type. The sub-type used to build the DODAG is called DAG Information Object (DIO). All the nodes in the network regularly issue a DIO which serves as a heartbeat to indicate their rank. The instant at which a node issues a DIO is governed by a Trickle timer which is reset only when an inconsistency arises. This way, when topology is stable, very little DIOs are exchanged.

P2MP is enabled by piecewise source routing: when issuing a message for a specific node in the network, the LBR prepends the sequence of nodes that need to be traversed to get to the destination to the packet. To learn this sequence, each node in the network is asked to transmit a Destination Advertisement Object (DAO) to the LBR (another subtype of the ICMPv6 RPL Control Message). At each hop, the relaying node appends its identifier to the Reverse Route Stack in the DAO, so that the LBR knows what nodes were traversed by the DAO.

Simulation Results

We replay the behavior of RPL over connectivity traces gathered in a real-world deployment. Traces ensure fairness in the comparison as only the MAC protocol changes; such fairness is hard to achieve when using different deployments.

The connectivity traces are collected by J. Ortiz and D. Culler in a UC Berkeley office space. They are obtained as follows. 46 IEEE802.15.4-compliant TelosB motes are deployed in a 50x50m indoor environment, and are constantly listening for packets. One after the other, each mote transmits a burst of 100 packets - with an 20ms inter-packet time and a transmission power of 0dBm - on each of the 16 frequency channels. Timers are used to ensure that all nodes switch channels simultaneously. Note that, because bursts are sent in sequence, there are no collisions. All non-transmitting nodes record the timestamp of the packets received, their source address, and the frequency channel the packets are received on. After all 46 nodes have sent a burst, each node reports what packets it has received. This process is repeated in 17 runs. A single run completes in 13 minutes; several hours separate subsequent runs.

The image to the left depicts the position of the nodes with their rank, and shows clearly the gradient converging to LBR node 141 (note that 141 should have rank=1, not 0). http://wsn.eecs.berkeley.edu/connectivity/ is a web interface we have built to enable anyone to visualize and download the raw data. In particular, it lets you explore RPL's DODAG formation for different parameters.

Frame formats

RPL messages are ICMPv6 RPL Control Messages, i.e. they follow the ICMPv6 format, with a type of 155 (this number was request to the Internet Assigned Numbers Authority IANA, the organism responsible for keeping track of such things, but not confirmed yet in revision 5 of the RPL draft).

The ICMPv6 header has a Code field which defines sub-types. RPL defines three subtypes:

  • DIO contains a DIO Basecontainer option which specifies the sequence number and DAGID, a.o., as well as the following suboptions:
    • DAG metric container to propagate node and link metric which a node uses to calculate its rank;
    • Destination Prefic used to announce the prefix' reachable through that DAG;
    • DAG configuration for the LBR to announce the configuration of the DAG.
  • DAO contains a.o. the Reverse Route Stack used by the LBR to contact an individual node in the network;
  • DIS carries no additional RPL Control Message body and is used to solicit a DIO from a neighbor.

Frame format are defined in Section 6.1 (pp.19-29) of draft-ietf-roll-rpl-05.

Note that RPL assumes the presence of an IPv6 header in the packet (possibly compacted using RPL), and uses the IPv6 flow label for loop detection. This is detailed in Section 6.9 (pp.49-50) of draft-ietf-roll-rpl-05.

State

A node running RPL needs to maintain the following timers:

  • DIO Timer: one for each DODAG it is part of;
  • DAG Sequence Number Increment Timer: one for each DODAG it is root of;
  • DelayDIO Timer: up to one for each DA parent;
  • RemoveTimer: up to one per neighbor.

A node running RPL needs to maintain the following state:

  • a list of candidate neighbors
  • information for each DODAG it is part of (DAGID, DAGObjectCodePoint, set of Destination Prefixes, set of DAG parents, DAGSequenceNumber)
  • a routing table (for each entry: Destination Prefix, Destination Prefix Length, Lifetime, Next hop)