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

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 30, 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 Setup
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 Setup

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). Each link has some PDR which varies with time (in the simulation, the PDR is re-read from the database every 5 minutes). Each time a packet arrives at the Radio of a node, the module generates a random number by the Mersenne Twister Random number generation method. The random number is compared to the PDR to determine whether the packet should be dropped or not. Note that each link use a different random number generator to maintain true randomness in the simulator, and to avoid correlation between links. Also, the packet drop applies to all kind of packets, viz. data, RA-DIO, NA-DAO, Ack packets, etc.

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

We currently concentrate on hop counts, ETX, routing table size and data and overhead comparisons but further revision will address several other metrics as in [I‑D.ietf‑roll‑routing‑metrics] (Vasseur, JP, Kim, M., Pister, K., Chong, H., “Routing Metrics used for Path Calculation in Low Power and Lossy Networks, draft-ietf-roll-routing-metrics-03 (work in progress),” April 2009.).

Number of Hops: For each pair of source and destination, we compute average number of hops for both RPL and shortest path routing. The Cumulative Distribution Function (CDF) of hop distance for all paths (which is equal to n*(n-1) in an n node network) in the network with respect to number of hops is plotted in figure 2a for both RPL and shortest path routing. As we can see, the CDF corresponding to 4 hops is around 55% for RPL and 90% for shortest path routing. This means, for the given topology, 90% of paths will have a path length of 4 hops or less with an ideal shortest path routing methodology, whereas in RPL p2p routing, 55% of paths will have a length shorter or equal to 4 hops.

Figure 2a

Figure 2a: CDF: hop distance versus number of hops.

Total ETX: When optimizing ETX metric along the path is used as OCP, the total ETX along the path is computed for each pair. In Figure 2b, we plot the CDF of the total number of ETX to deliver a packet from a source to any destination node with respect to total ETX of the path.

Figure 2b

Figure 2b: CDF: Total number of ETX to deliver a packet with respect to total path ETX.

Routing Table Size: The cdf of routing table size with respect to number of nodes is shown in figure 2c. For example, the CDF corresponding to routing table size = 5 is almost 75%. This means that 75% of the nodes in the network have a routing table size of 5 entries or less. Similarly, we can see 95% of nodes have routing table size of 15 entries or less. Note that, in this simulation, all nodes are capable of storing routing information, and the above values are topology and implementation specific.

Figure 2c

Figure 2c.: CDF of routing table size with respect to number of nodes.

Data and Overhead comparison for each node: In Figure 3, we compare the amount of data packetstransmitted (both transmitted and forwarded) and control packets (RA_DIO and NA-DAO) transmitted for each node when minimizing ETX is used OCP along the DAG. To be noted that some nodes, which are closer to sink and which act as forwarders, have much more data packet transmission than other nodes. The leaf nodes have comparable amount of data and control packet transmission, as they do not take part in routing the data.

Figure 3

Figure 3: Amount of data and control packets transmitted for each node when minimizing ETX is used OCP along the DAG.

Data and Control Packet Transmission with respect to time: In figure 4a, 4b and 4c the amount of data and control packets transmitted for node 12 (high rank in DAG), node 33 (in the middle) and node 54 (a leaf node)are shown, respectively. These values stands for number of packets transmitted for each 500 seconds intervals, to help understand what is the density of data and control packet exchange in the network. We can see, for a node closer to sink, the data packet amount is much higher than control packet, and somewhat oscillatory around a mean value. The control packet amount exhibits a 'saw-tooth' behavior, mainly because as ETX was used, and as when PDR changes, ETX for a child node to its parent changes, which results in changing DAG depth of the child. This event resets the trickle timer and emit RA-DIO. So, we can observe that number of control packets attains a high value for one interval, and the amount comes down to lower values for subsequent intervals. Also, for leaf nodes the amount of control packets are more than data packets, as leaf nodes are more prone to face changes in their DAG depth as opposed to nodes closer to sink when the link PDR in the topology changes dynamically.

Figure 4a

Figure 4a.: Amount of data and control packets transmitted for node 12.

Figure 4b

Figure 4b.: Amount of data and control packets transmitted for node 33.

Figure 4c

Figure 4c.: Amount of data and control packets transmitted for node 54.

6.  References

6.1. Normative References

6.2. Informative References

Authors' Addresses