Skip to content

Documentation: RPL

Simon Duquennoy edited this page Feb 14, 2019 · 26 revisions

About RPL

RPL is an IPv6 routing protocol for lossy and low-power networks specified in RFC 6550, which is implemented in Contiki-NG's IPv6 network stack. RPL builds and maintains a Destination-Oriented Directed Acyclic Graph (DODAG) topology that originates from a designated RPL root node, which typically also serves as a border router to the Internet. Routing information is disseminated through broadcast beacons aperiodically using Trickle timers. The topology is built according to a certain goal by an objective function. Such a goal can be to minimize the Estimated Transmission Count (ETX) on the path from the node to the RPL root, as is in our implementations of the two Objective Functions we support, MRHOF and 0F0.

RPL supports different directions of traffic:

  • Upward routing: from any node to a root.
  • Downward routing: from the root to any node.
  • Any-to-any routing: where traffic flows between arbitrary pairs of nodes in the DODAG by routing upwards to their closest common ancestor (or the root in non-storing mode) in the DODAG, and then downward to the destination node.

All upward routing is handled by having each node on the path toward the root forwarding traffic through a preferred parent. Downward routing can be handled with two different types of modes: non-storing and storing mode. For non-storing mode, IPv6 source routing is employed, which means that nodes do not have to store routing tables for nodes below them in the DODAG. On the other hand, packets can get large if many hops are along the path, whose addresses would then need to be embedded in the source routing header. For storing mode, routing tables are stored on each node, which can impose a significant memory footprint in large networks and be hard to maintain consistently, but there is on the other hand no need for potentially large source routing headers in the IPv6 packets.

Implementations

Contiki-NG provides two implementations of RPL with different attributes: RPL Classic and RPL Lite.

RPL Classic

RPL Classic is the continuation of the original Contiki's RPL implementation: ContikiRPL. This implementation was created as early as 2009, while the RPL standard was still under development. Over the years, it has gotten a lot of functionality that has been added to the RPL RFC and related RFCs, such as support for multiple instances and DODAGs, storing and non-storing mode, multicasting, and more. Hence, at the price of supporting a lot of functionality from standards and Internet drafts, the implementation has become complex and thus has gotten a large ROM footprint.

RPL Lite

RPL Lite is Contiki-NG's default RPL implementation. It started as a major rewrite of the 2017 version of ContikiRPL, with a focus on the most important and stable functionality, as the community has experienced in many deployments and research experiments. RPL Lite removes support for storing mode in favor of non-storing mode, and removes the complexity of handling multiple instances and DODAGs. Through these changes, RPL Lite typically exhibits better performance and has a considerably smaller ROM footprint. On the flip side of these optimizations, it has a lower interoperability level with other implementations, which may use storing mode for instance.

RPL Lite: topology formation and configuration

We review here how RPL Lite builds a topology and the configuration parameters that matter most in this process. For an extensive list of configuration parameters, see https://github.com/contiki-ng/contiki-ng/blob/master/os/net/routing/rpl-lite/rpl-conf.h

DAG Advertisement

When a node starts running as DAG root (whether it is border router or not), it will advertise the DAG with DIOs (DODAG Information Object). DIO transmissions follow a Trickle timer. Some important configuration parameters are:

  • NETSTACK_MAX_ROUTE_ENTRIES: the number of routing entries at the root, which must be set to at least the network size
  • RPL_CONF_SUPPORTED_OFS: a list of Objective Functions embedded in the node, any of which can be selected at run-time
  • RPL_CONF_OF_OCP: the Objective Function advertised by the root.
  • RPL_CONF_DIO_INTERVAL_MIN: the minimum Trickle interval is 2^RPL_CONF_DIO_INTERVAL_MIN milliseconds. A value of 12 for instance results in 4.096 seconds.
  • RPL_CONF_DIO_INTERVAL_DOUBLINGS: the maximum Trickle interval is 2^(RPL_CONF_DIO_INTERVAL_MIN+RPL_CONF_DIO_INTERVAL_DOUBLINGS) milliseconds. A value of 8 (with a min doubling interval of 12) results in a maximum period of 1048.576 seconds (about 17 minutes).
  • RPL_CONF_DIO_REDUNDANCY: the Trickle redundancy constant, used to suppress DIO transmissions in dense networks. Disabled by default in RPL Lite (value of 0).

Joining

Nodes willing to join a network will transmit periodic DIS (DODAG Information Solicitation) to trigger Trickle reset at neighboring nodes, and increase their chances to hear a DIO:

  • RPL_CONF_DIS_INTERVAL: the interval at which nodes looking for a DAG or a parent will send DIS messages

Whenever hearing a DIO, the node might choose to join the DAG. The first thing needed then is to select a RPL preferred parent. Because RPL Lite focuses on reliability, nodes do not select a parent until they have a precise estimate of their link quality to the neighbor (the link-stats module provides a freshness indicator for that purpose). Nodes will then perform link-probing to assess their neighbors' link:

  • RPL_CONF_PROBING_SEND_FUNC: the probing function. By default, probing is simply a unicast DIO to the target neighbor
  • RPL_CONF_PROBING_INTERVAL: the interval at which background probing is done, in clock ticks
  • RPL_CONF_PROBING_DELAY_FUNC: the function that calculates the next delay. By default, the delay is dynamic: if there is urgent need for probing (when the node has no usable parent), probing will happen within seconds, else, some random interval based on RPL_CONF_PROBING_INTERVAL
  • RPL_CONF_PROBING_SELECT_FUNC: the function that selects the next probing target. The default function probes the urgent probing target if any, or the preferred parent if its link statistics need refresh. Otherwise, it picks at random between (1) selecting the best neighbor with non-fresh link statistics, or (2) selecting the least recently updated neighbor

Preferred parent selection

After enough probing, the node will select a neighbor as preferred parent. This is according to the selected Objective Function and metric. By default, MRHOF and ETX are used. There are a number of important configuration parameters for link estimation and Objective Function:

  • LINK_STATS_CONF_INIT_ETX_FROM_RSSI: this is part of the link-stats module. When set (default), nodes estimate their neighbors' link quality when first hearing from them, based on the RSSI of, e.g, an incoming DIO. For a deeper understanding of how this is calculated, as well as how link quality is later maintained, take a look at link-stats.c
  • RPL_MRHOF_CONF_SQUARED_ETX: when set, MRHOF will square the link ETX before adding it to the parent rank for path cost calculation. This results in more reliable paths, as it penalizes higher link ETX. Stronger links are typically selected, at the expense of longer paths and higher churn. The feature is disabled by default, as the higher churn can result in unstable operation in networks with poor links. Check out rpl-mrhof.c or rpl-of0.c for more configuration options.

Route registration

Once a preferred parent is chosen, a node will then register itself through a DAO (Destination Advertisement Object). In non-storing mode (only mode in RPL lite), the DAO is sent directly to the root, using global IPv6 addresses. Upon receiving the DAO, the root will add the node to its routing state: it will store the child-parent relationship, used later for source routing. In RPL Lite, by default, DAO messages have the 'K' bit set, which means they must be acknowledged by the root:

  • RPL_CONF_DAO_RETRANSMISSION_TIMEOUT: the delay after which nodes resend their DAO in case no DAO-ACK was received
  • RPL_CONF_DAO_MAX_RETRANSMISSIONS: the maximum number of DAO retransmissions
  • RPL_CONF_DEFAULT_LIFETIME_UNIT: the unit, in seconds, used for lifetime in DAO messages
  • RPL_CONF_DEFAULT_LIFETIME: the lifetime, in lifetime units, advertised in DAO messages. The DAG root will delete the route after this lifetime expires. Nodes will resend a DAO automatically within 1-2 minutes before expiry.

After receiving a DAO-ACK, nodes know they are fully part of the network and reachable. Only then will they start advertising DIOs in turn, and let more nodes join, forming a multi-hop mesh network.

  • RPL_CONF_DEFAULT_LEAF_ONLY: if this is set, the node will join but only as a leaf, i.e., it will not send any DIO and will never be selected as parent

DAG maintenance

When a node is part of a DAG, it will constantly maintain link estimates via probing, keep its preferred parent up to date, and advertise the DAG root accordingly. RPL local repairs (reset Trickle timer, reset link statistics) are performed when needed as required in the standard. When a node undergoes a significant rank change, it will also reset its Trickle timer for quicker topology update:

  • RPL_CONF_SIGNIFICANT_CHANGE_THRESHOLD: the rank change threshold for Trickle reset. Whenever the current rank differs form the last advertised rank by at least this threshold, the node resets its Trickle.

When a node finds no more suitable preferred parent, it will start poisoning, i.e., advertise an infinite rank to let its sub-DAG know it no longer is a valid parent. It will then leave the network after a delay:

  • RPL_CONF_DELAY_BEFORE_LEAVING: the delay after which a node actually leaves a network, by default, 5 minutes.

During this delay, the node performs poisoning. Meanwhile, it also starts sending periodic DIS again, in hope to discover a new usable parent. If this happens, the node will directly stop poisoning and consider itself part of the DAG again. If not, it will eventually leave the DAG after the delay and send DIS until it joins a new DAG.

Clone this wiki locally
You can’t perform that action at this time.