Networking Working Group                                J. Tripathi, Ed.
Internet-Draft                                       J. de Oliveira, Ed.
Intended status: Informational                         Drexel University
Expires: May 16, 2010                                   JP. Vasseur, Ed.
                                                     Cisco Systems, Inc.
                                                       November 12, 2009

   Performance Evaluation of Routing Protocol for Low Power and Lossy
                             Networks (RPL)


   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.

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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on May 16, 2010.

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

Tripathi, et al.          Expires May 16, 2010                  [Page 1]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

   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.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the BSD License.

Table of Contents

   1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  Method . . . . . . . . . . . . . . . . . . . . . . . . . . . .  4
   4.  Simulation Setup . . . . . . . . . . . . . . . . . . . . . . .  4
   5.  Metrics to evaluate RPL  . . . . . . . . . . . . . . . . . . .  7
     5.1.  Simulation Results . . . . . . . . . . . . . . . . . . . .  7
   6.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  9
     6.1.  Normative References . . . . . . . . . . . . . . . . . . .  9
     6.2.  Informative References . . . . . . . . . . . . . . . . . .  9
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10

Tripathi, et al.          Expires May 16, 2010                  [Page 2]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

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

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

   RPL is designed to meet the core requirements specified in
   s],[I-D.ietf-roll-indus-routing-reqs] and [RFC5548].

   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.

Tripathi, et al.          Expires May 16, 2010                  [Page 3]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

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

   * 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].

Tripathi, et al.          Expires May 16, 2010                  [Page 4]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

                                     / | \
                                .---`  |  `----.
                               /       |        \
                             | \       | \       | \
                             |  `----. |  `----. |  `----.
                             |        \|        \|        \
                            (21)------(22)------(23)      (24)
                             |        /|        /|         |
                             |  .----` |  .----` |         |
                             | /       | /       |         |
                             |        /| \       | \       | \
                             |  .----` |  `----. |  `----. |  `----.
                             | /       |        \|        \|        \
                   .--------(41)      (42)      (43)------(44)------(45)
                  /         /         /| \       | \
            .----`    .----`    .----` |  `----. |  `----.
           /         /         /       |        \|        \
   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].

   I_max and I_doubling are initially taken as 1 second and 6 seconds,
   respectively, so that maximum time between two consecutive RA-DIO

Tripathi, et al.          Expires May 16, 2010                  [Page 5]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

   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

   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].

Tripathi, et al.          Expires May 16, 2010                  [Page 6]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

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].

   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.

Tripathi, et al.          Expires May 16, 2010                  [Page 7]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

   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

   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.

Tripathi, et al.          Expires May 16, 2010                  [Page 8]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

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

6.  References

6.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

6.2.  Informative References

              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.

              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.

              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.

              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.

              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.

Tripathi, et al.          Expires May 16, 2010                  [Page 9]

Internet-Draft      draft-tripathi-rpl-simulation-00       November 2009

              JP Vasseur, "Terminology in Low power And Lossy Networks,
              draft-ietf-roll-terminology-02 (work in progress)", May

   [RFC5548]  Dohler, M., Watteyne, T., Winter, T., and D. Barthel,
              "Routing Requirements for Urban Low-Power and Lossy
              Networks", RFC 5548, May 2009.

              J. Jurski, "Limited IP Header Compression over PPP,
              draft-jurski-pppext-iphc-02.txt (work in progress)", March

Authors' Addresses

   Joydeep Tripathi (editor)
   Drexel University
   3141 Chestnut Street 7-313
   Philadelphia, PA  19104


   Jaudelice C. de Oliveira (editor)
   Drexel University
   3141 Chestnut Street 7-313
   Philadelphia, PA  19104


   JP Vasseur (editor)
   Cisco Systems, Inc.
   1414 Massachusetts Avenue
   Boxborough, MA  01719


Tripathi, et al.          Expires May 16, 2010                 [Page 10]