Internet of Things

ROLL on a roll!

"We want to highlight that the IETF offers the right environment to make the Internet work better in the context of IoT routing. One of the reasons for this is that participation is open to everyone."

By: Ines Robles

Date: April 24, 2018

line break image

Routing Over Low Power and Lossy Networks (ROLL) is a working group (WG) of the IETF that handles Internet of Things (IoT) routing topics [1]. ROLL started its work in February 2008 with the goal of developing a routing protocol suitable for low power and lossy networks (LLN). The working group was rechartered in 2016.

Why do we need a new routing protocol for these networks?

Because LLN have specific characteristics such as high rates of packet loss, relatively low throughput and highly asymmetric links. In general, these networks are also composed of constrained devices, meaning devices with restricted memory, energy and processing power.

Why don’t we use a pre-existing routing protocol?

One of the first ROLL WG activities was a study [2] that analyzed some of the existing IETF routing protocols such as OSPF, IS-IS, OLSRv2, AODV and RIP, and considered how they could be adapted to the following criteria: routing state, loss response, control cost, and link and node cost.

Why these criteria?

These criteria are shaped by the high-level requirements of the main use cases for ROLL such as home automation, urban LLNs and industrial routing. The conclusion of the analysis was that no existing protocol met all the criteria and thus a new protocol design was embarked upon. Consequently, the ROLL working group developed a distance-vector and source-routing protocol called IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL)[3]. RPL organizes the nodes in a topology with the form of a Directed Acyclic Graph (DAG) oriented to a root, thus we have a Destination Oriented DAG (DODAG). RPL has mechanisms for loop detection and DODAG Repair. The traffic flows between nodes that RPL supports are point to multipoint, multipoint to point and point to point.

What types of nodes can belong to a DODAG?

A DODAG is composed of three type of nodes:

  1. DODAG root: can be described as the ‘brain’ of the topology, is responsible for initializing the topology, keeping state on the whole topology, and managing the DODAG. A DODAG Root, in general, acts as the border router for the DODAG. We can observe a DODAG root in Figure 2 as node “A”.
  2. RPL Router Node: a device that has the capability to forward and generate RPL traffic. Intermediate RPL Router Nodes are located between the DODAG root and the leaf nodes. In Figure 2, the nodes “B” and “C” are RPL Routers.
  3. RPL Leaf Node: a device that is located at the edge of the topology. An RPL Leaf can be a router or a host, a host is a device that does not have the capability to forward RPL traffic. In Figure 2, the nodes “D”, “E” and “F” are RPL Leaves.

How is a DODAG formed?

An Objective Function (OF) defines how a DODAG is formed (e.g. specifies how a node should select its parent set) with the main goal of getting the best path to the DODAG root. The topology is built following routing metrics and/or constraints based on node or link characteristics [4]. For example, select a parent node based on a specific node residual energy level (node characteristics as constraint) or select the parent that belongs to a path with shortest end-to-end delay (link characteristics as metric). The DODAG is built by control messages sent through Internet Control Message Protocol (ICMPv6) packets. In Figure 1 we can observe the RPL stack.

The RPL Stack
Figure 1: The RPL Stack

What is 6LoWPAN (mentioned as part of the RPL Stack)?

IPv6 over Low-Power Wireless Personal Area Network (6LoWPAN) is a protocol that defines a way to compress IPv6 datagrams [5] to accomodate networks with a maximum data frame smaller than the IPv6 Maximum Transmission Unit (MTU). For example, IEEE 802.15.4 networks have a data frame of 127 octets and that is smaller than the IPv6 MTU of 1280 octets. Thus, 6LoWPAN provides a mechanism (header compression) to adapt IPv6 datagrams to constrained networks such as IEEE 802.15.4.

Which are the main control messages used to form a DODAG?

The main RPL Control Messages are:

  1. DODAG Information Solicitation (DIS) which a node sends to its neighbours to require routing information (DODAG Information Object (DIO)). DIS is similar to the Router Solicitation messages of the IPv6 Neighbour Discovery protocol;
  2. DODAG Information Object (DIO) which contains information that a node uses to discover an RPL Instance, determine its configuration parameters, a DODAG parent set and maintain the DODAG; and
  3. Destination Advertisement Object (DAO) which allows for propagation of destination information upward through the DODAG. A Destination Advertisement Object Acknowledgement (DAO-ACK) message is sent in response to a DAO.

Elements that identify and maintain a topology in RPL

Figure 2: Elements that identify and maintain a topology in RPL

Once you have formed a DODAG, how do you identify the whole topology?

RPL uses the following to identify and maintain a topology:

  1. An RPLInstanceID: an RPL Instance is a set of one or more DODAGs. An RPL node can belong to several RPL Instances, but in each one, the node can only belong to one DODAG. The RPLInstanceID is the identifier of the RPL Instance.
  2. The DODAGID, which, in general, is the global IPv6 address of the DODAG root.
  3. The version of the topology is identified through the DODAGVersionNumber, and;
  4. The rank, which we can think of as an indicator of the distance of the RPL node to the DODAG root. The rank decreases when the node is close to the DODAG root and increases when the node is far from the DODAG root. This is shown in Figure 2.

ROLL uses control messages to form the topology, then keeps track of a DODAG topology through the 4 elements listed above.

How does RPL transmit information through the DODAG?

RPL has two modes of operation: storing (fully stateful) or non-storing (fully source-routed) mode. In the non-storing case, a packet will go to the DODAG root, and then be sent to the destination. In storing mode, a packet can be sent directly to the destination by a common parent (ancestor) between the source and the destination.

RPL disseminates information through the DODAG in the way that requires the least configuration in the nodes, thus the nodes operate mostly autonomously. The mechanism is based on the Trickle algorithm [6], where basically a node transmits when the node’s information is not aligned with its neighbours to resolve inconsistencies quickly. When the node’s information is aligned with its neighbours, the node slows the communication rate exponentially (e.g. two packets per hour).

Which other protocols have been defined by the ROLL working group?

ROLL also developed a Multicast Protocol for Low-Power and Lossy Networks (MPL) which transmits information using the Trickle algorithm or through flooding operation. Current proposals describe multicast using Bloom Filters [7] or Bit Index Explicit Replication (BIER) [8]. ROLL also defined a way to comprise RPL routing information through IPv6 over a Low-Power Wireless Personal Area Network Routing Header (6LoRH) [9].

Which other proposals is the working group considering currently?

The working group is also working on a reactive P2P route discovery mechanism for asymmetric links, which is based on the Ad Hoc On-demand Distance Vector Routing (AODV) protocol for RPL [10]. Another working group topic is a proposal that tries to set some kind of storing routes into a non-storing mode network [11]. ROLL also has a document that describes optimal ways to get an efficient route invalidation mechanism [12]. YANG models are part of the chartered work items, and currently ROLL has a proposal on YANG for MPL [13]. Additionally, the working group has a document that describes the use cases for carrying routing information in data-plane packets, source routing header and IPv6-in-IPv6 encapsulation [14].

Do we have open source code for RPL?

The main open source operating systems for IoT include RPL implementations, such as ContikiRPL [15] (Contiki-OS), RPL lite [16] (Contiki-NG), TinyRPL [17] (Tiny-OS) and RIOT-RPL [18] (RIOT-OS). These operating systems offer tutorials to help anyone interested to start evaluating the protocol.

We want to highlight that the IETF offers the right environment to make the Internet work better in the context of IoT routing. One of the reasons for this is that participation is open to everyone. Thus, everyone can propose an improvement to the protocol. Additionally it is pretty straightforward to work in coordination with another working groups to improve the proposals, since the expertise of different areas is shared.

Which IETF working groups interact most closely with ROLL?

ROLL interacts with the BIER working group on a proposal for BIER multicast. ROLL also works closely with other IoT-related working groups. For example, RPL has been adopted by the IPv6 Time Slot Channel Hopping mode of IEEE 802.15.4 (6tisch) protocol stack (6tisch working group), thus ROLL works on RPL mechanisms that are needed in the 6tisch working group. ROLL is also aligned with the IPv6 Maintenance (6man) working group.

References

[1] https://datatracker.ietf.org/wg/roll/about/, last accessed 01.04.2018.

[2] Levis, P. et al. “Overview of existing routing protocols for low power and lossy networks.” Internet Engineering Task Force, Internet-Draft draft-ietf-roll-protocols-survey-07 (2009).

[3] Thubert, P., et al. & Alexander, R.(2012). RPL: IPv6 routing protocol for low power and lossy networks. RFC 6550.

[4] Vasseur, JP, et al. Routing metrics used for path calculation in low-power and lossy networks. No. RFC 6551. 2012.

[5] Thubert, P. et al. “Compression format for IPv6 datagrams over IEEE 802.15. 4-based networks.” (2011).

[6] Levis, P., et al. J. Ko,” The Trickle Algorithm. RFC 6206, March, 2011.

[7] Bergmann, O. et al. “Constrained-Cast: Source-Routed Multicast for RPL” draft-ietf-roll-ccast-01 (2018)

[8]Thubert, P., “RPL-BIER” draft-thubert-roll-bier-01 (2018)

[9] Toutain, Laurent, et al. “IPv6 over Low-Power Wireless Personal Area Network (6LoWPAN) Routing Header.” (2017).

[10] Perkins, C. et al. “Asymmetric AODV-P2P-RPL in Low-Power and Lossy Networks (LLNs)” draft-ietf-roll-aodv-rpl-03 (2018)

[11] Thubert, P. et al. “Root initiated routing state in RPL” draft-ietf-roll-dao-projection-03 (2018)

[12] Jadhav, R. et al. “Efficient Route Invalidation” draft-ietf-roll-efficient-npdao-03 (2018)

[13] Van der Stok, P. et al. “A YANG model for Multicast Protocol for Low power and lossy Networks (MPL) draft-ietf-roll-mpl-yang-01 (2018)”

[14] Robles, M. et al. “When to use RFC 6553, 6554 and IPv6-in-IPv6”, draft-ietf-roll-useofrplinfo-22 (2018)

[15] https://github.com/contiki-os/contiki/blob/master/core/net/rpl/rpl.c, last accessed 09.04.2018

[16] https://github.com/contiki-ng/contiki-ng/tree/develop/os/services/rpl-border-router, last accessed 09.04.2018

[17] http://tinyos.stanford.edu/tinyos-wiki/index.php/TinyRPL, last accessed 09.04.2018

[18] https://github.com/RIOT-OS/RIOT/tree/master/sys/include/net/gnrc/rpl, last accessed 09.04.2018.

No Comments to Show

Leave a Reply

Your email address will not be published. Required fields are marked *