Performance Evaluation of Routing Protocol for Low Power and Lossy Networks (RPL)
draft-tripathi-rpl-simulation-00

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 April 22, 2010.

Copyright Notice

Copyright (c) 2009 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 in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Abstract

This document presents a performance evaluation of RPL in a single DAG scenario, and comparison of the same with shortest path routing in a LLN. Metrics to capture the significant performance aspects are identified and detailed simulations are carried out on a set of real-life scenarios.

Table of Contents

1.  Terminology
2.  Introduction
3.  Method
4.  Simulation Set-up
5.  Metrics to evaluate RPL
    5.1.  Simulation Results
6.  References
    6.1.  Normative References
    6.2.  Informative References
§  Authors' Addresses

1.  Terminology

DAG - Directed Acyclic Graph.

LBR - Low power and lossy network Border Router

RA-DIO - Router Advertisement DAG Information Option message

DAO - Destination Advertisement Option

PDR - Packet Delivery Ratio

Please refer to additional terminology in [I‑D.ietf‑roll‑terminology] (JP Vasseur, “Terminology in Low power And Lossy Networks, draft-ietf-roll-terminology-02 (work in progress),” May 2009.).

2.  Introduction

Designing routing in low power devices and lossy link networks imposes great challenges, mainly due to low data rates, high probability of packet delivery failure, and strict energy constraint in nodes. The IETF ROLL Working Group has specified RPL in [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., et al., “RPL: Routing Protocol for Low Power and Lossy Networks, draft-ietf-roll-rpl-03 (work in progress),” October 2009.).

RPL is designed to meet the core requirements specified in [I‑D.ietf‑roll‑home‑routing‑reqs] (Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-08 (work in progress),” September 2009.),[I‑D.ietf‑roll‑building‑routing‑reqs] (Martocci, J., Riou, N., Mil, P., and W. Vermeylen, “Building Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-building-routing-reqs-07 (work in progress),” September 2009.),[I‑D.ietf‑roll‑indus‑routing‑reqs] (Pister, K., Thubert, P., Dwars, S., Phinney, T., “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-06 (work in progress),” June 2009.) and [RFC5548] (Dohler, M., Watteyne, T., Winter, T., and D. Barthel, “Routing Requirements for Urban Low-Power and Lossy Networks,” May 2009.).

This document’s contributions are:

* To provide a simulation study of RPL in various real-life deployment scenarios;

* To include preliminary evaluation metrics that will be enriched in further revision. Metrics of interest will be of various nature: Path quality metrics; Control place overhead; Ability to cope with unstable situations (link churns, node dying); Required resource constraints on nodes (routing table size, etc.).

It is to be noted that while simulation cannot prove formally that a protocol operates properly in all situations, it could give a good level of confidence in protocol behavior in highly stressful conditions, if and only if real data are used, as opposed to theoretical models that may not be applicable to such networks/scenarios. Therefore, we used real deployed network data to create our link model.

3.  Method

RPL was simulated using OMNET++, a well known event based simulator written in C++ and NED. We also used the Castalia-2.2 Wireless Sensor Network Simulator framework within OMNET++. OMNET++ is freely available for academic research use. The output and events in the simulating are visualized with the help of the Network AniMator or NAM, which is distributed with NS(Network Simulator). Note that NS or any of its versions were not used in this simulation study. Only the visualization tool was borrowed for verification purposes. As noted, real link layer data gathered from networks deployed on the field were used to compute the PDR (Packet Delivery Ratio) for each of the links in the network. We do not use theoretical models but real-life data for two aspects of the simulations:

* Link failure model: Time varying real network traces containing packet delivery probability for each link and over all channels for both indoor network deployment and outdoor network deployment were used. Thus, different types of link characteristics are used in the study.

* Topology: The topologies are gathered from real-life deployment (traces mentioned above) as opposed to random topology simulations. are repeated here:

4.  Simulation Set-up

We simulate RPL for a given 23 node topology, shown in Figure 1. This topology is here repeated for the sake of completeness. It is the topology shown in Figure 8 in Appendix B of [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., et al., “RPL: Routing Protocol for Low Power and Lossy Networks, draft-ietf-roll-rpl-03 (work in progress),” October 2009.).

                                     (LBR)
                                     / | \
                                .---`  |  `----.
                               /       |        \
                            (11)------(12)------(13)
                             | \       | \       | \
                             |  `----. |  `----. |  `----.
                             |        \|        \|        \
                            (21)------(22)------(23)      (24)
                             |        /|        /|         |
                             |  .----` |  .----` |         |
                             | /       | /       |         |
                            (31)------(32)------(33)------(34)
                             |        /| \       | \       | \
                             |  .----` |  `----. |  `----. |  `----.
                             | /       |        \|        \|        \
                   .--------(41)      (42)      (43)------(44)------(45)
                  /         /         /| \       | \
            .----`    .----`    .----` |  `----. |  `----.
           /         /         /       |        \|        \
        (51)------(52)------(53)------(54)------(55)------(56)

Figure 1: Network topology for preliminary simulation results.

Note that this is just a start to validate the simulation before using large scale networks.

A database of time varying link quality data, gathered from real network deployment, was created. Each link in the topology randomly 'picks up' a link model from the database, and the link’s PDR varies according to the gathered data. Packets are dropped randomly from that link with probability (1 - PDR).

In simulating RPL, the LBR first initiates sending out RA-DIO, and gradually the DAG is constructed. The trickle time interval for emitting the RA-DIO assumes the initial value of 1s, and then changes over simulation time as mentioned in the draft [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., et al., “RPL: Routing Protocol for Low Power and Lossy Networks, draft-ietf-roll-rpl-03 (work in progress),” October 2009.).

I_max and I_doubling are initially taken as 1 second and 6 seconds, respectively, so that maximum time between two consecutive RA-DIO emissions by a node (under a steady network condition) is 1 minute. Another objective of this study is to give insight to the network administrator on how to tweak the trickle values. We plan to run simulations for large scale networks with varied parameters and show how quickly the network will stabilize, comparing data/control traffic and studying the tradeoff between reactivity and lifetime.

Each node in the network, other than the LBR, also emits NA-DAO, to initially set up the routing table for all the nodes in the network. We assume that each node is capable of storing route information for other nodes in the network. In the next revision we will incorporate nodes without storage capability and see the influence of extra states on the nodes and the additional control plane overhead to propagate the route records.

In this simulation study, RPL is compared to an ideal shortest path routing, where each node has the forwarding information for every destination in the network. The shortest path refers to a path where either the number of hops or ETX of packet delivery (depending on the OCP used) along the path is minimum for any given source and destination pair. To be noted, this comparison aims at giving an insight on how worse the Point-to-Point path may be compared to the ideal path.

For nodes implementing RPL, the routing table memory requirement varies depending on the position in the DAG. We make the worst-case assumption that there is no route summarization in the network. Thus a node closer to the DAG will have to store more routing entries. Further revision of this document will explore the influence of performing route summarization along the DAG, which could be performed thanks to a newly defined Objective Function. Also, initially we assume that all nodes have equal capacity to store the routing states of nodes in its sub-DAG.

Each node also periodically (a few packets per hour)sends CBR (Constant Bit Rate) traffic to all other nodes in the network over the simulation period.

The packets are routed through the DAG as mentioned in [I‑D.ietf‑roll‑rpl] (Winter, T., Thubert, P., et al., “RPL: Routing Protocol for Low Power and Lossy Networks, draft-ietf-roll-rpl-03 (work in progress),” October 2009.).

We do not make any assumption on the link layer, thus potential gains in terms of header compression provided by 6loWPAN is not under consideration [draft‑iphc] (J. Jurski, “Limited IP Header Compression over PPP, draft-jurski-pppext-iphc-02.txt (work in progress),” March 2007.).

5.  Metrics to evaluate RPL

Routing Table Size: As the NA-DAO messages help to construct the routing table in the node, we record the routing table size for each node in the network. Currently, the routing table size is not in exact Kb of memory usage, but we measure it in terms of number of entries for each node. Each entry has next hop node and distance associated with the destination node. In further revision we will use a single full 128-bit address per leaf plus a few bits to store other information and flags.

Hops to destination: We record the number of hops each packet travels. The aim of this metric is to determine how optimal is the path computed by the DAG compared to an optimal path computed by an “ideal” shortest path routing protocol. This allows for evaluating if the path cost is good enough, in particular for applications involving point-to-point traffic.

Although simulations have been run on different and realistic topologies showing consistent results, the metrics discussed here may vary with the network topology.

5.1.  Simulation Results

Routing Table Size :

Number of Hops:

We currently concentrate on hop counts, but further revision will address several metrics as in [I‑D.ietf‑roll‑routing‑metrics] (, “Routing Metrics used for Path Calculation in Low Power and Lossy Networks, draft-ietf-roll-routing-metrics-00 (work in progress),” April 2009.), such as reliability, energy, etc., with the objective of evaluating RPL’s path quality for new metrics, combination of metrics and constraints.

6.  References

6.1. Normative References

6.2. Informative References

Authors' Addresses