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)
draft-tripathi-roll-rpl-simulation-00
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.
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 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
(http://trustee.ietf.org/license-info) 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
[I-D.ietf-roll-terminology].
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].
RPL is designed to meet the core requirements specified in
[I-D.ietf-roll-home-routing-reqs],[I-D.ietf-roll-building-routing-req
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
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].
Tripathi, et al. Expires May 16, 2010 [Page 4]
Internet-Draft draft-tripathi-rpl-simulation-00 November 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].
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
[I-D.ietf-roll-rpl].
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
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.
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
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
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
6.2. Informative References
[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-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-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.
[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.
[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.
Tripathi, et al. Expires May 16, 2010 [Page 9]
Internet-Draft draft-tripathi-rpl-simulation-00 November 2009
[I-D.ietf-roll-terminology]
JP Vasseur, "Terminology in Low power And Lossy Networks,
draft-ietf-roll-terminology-02 (work in progress)", May
2009.
[RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel,
"Routing Requirements for Urban Low-Power and Lossy
Networks", RFC 5548, May 2009.
[draft-iphc]
J. Jurski, "Limited IP Header Compression over PPP,
draft-jurski-pppext-iphc-02.txt (work in progress)", March
2007.
Authors' Addresses
Joydeep Tripathi (editor)
Drexel University
3141 Chestnut Street 7-313
Philadelphia, PA 19104
USA
Email: jt369@drexel.edu
Jaudelice C. de Oliveira (editor)
Drexel University
3141 Chestnut Street 7-313
Philadelphia, PA 19104
USA
Email: jau@ece.drexel.edu
JP Vasseur (editor)
Cisco Systems, Inc.
1414 Massachusetts Avenue
Boxborough, MA 01719
USA
Email: jpv@cisco.com
Tripathi, et al. Expires May 16, 2010 [Page 10]