RFC 6687
Performance Evaluation of the Routing Protocol for Low-Power and Lossy Networks (RPL)
Performance Evaluation of RPL ✨
Okay bestie, this one is the RPL performance evaluation, and it's giving real-world data realness 💅 It's an Independent Submission from J. Tripathi, Ed., J. de Oliveira, Ed. (Drexel University), and JP. Vasseur, Ed. (Cisco Systems, Inc.), dated October 2012. It's marked Category: Informational, with ISSN 2070-1721. It doesn't obsolete or update any other RFC, since its header has no Obsoletes or Updates line. 🎀
It's all about the Routing Protocol for Low-Power and Lossy Networks (RPL) 🦋 The authors tested it on a small outdoor sensor deployment and on a big smart meter network, using detailed simulations built on real-life scenarios. The plain-text version doesn't show every plot, so if you want the full picture, grab the PDF version too 📈
Abstract ✨
This document is an evaluation of how RPL performs in two real-life setups: a small outdoor deployment of sensor nodes, and a large-scale smart meter network. The team ran detailed simulations to get a bunch of routing performance metrics out of those scenarios. Several plots for those metrics only show up in the PDF, so go look there if you want them 🌸
Status of This Memo 🌈
This document is not an Internet Standards Track specification. It's published purely for informational purposes 💜
It's a contribution to the RFC Series, separate from any other RFC stream. The RFC Editor picked to publish it at their discretion, and they make no claim about whether it's valuable for implementing or deploying anything. Documents the RFC Editor approves for publication can't become any level of Internet Standard. See Section 2 of RFC 5741 for the details ✨
For the current status, any errata, and how to give feedback, check http://www.rfc-editor.org/info/rfc6687 🍓
Copyright Notice 🎀
Copyright (c) 2012 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 (http://trustee.ietf.org/license-info) as they stood on the publication date. Please read those carefully, because they spell out your rights and restrictions for this document 🫶
Table of Contents 📑
1. Introduction ....................................................2
2. Terminology .....................................................3
3. Methodology and Simulation Setup ................................4
4. Performance Metrics .............................................7
4.1. Common Assumptions .........................................7
4.2. Path Quality ...............................................7
4.3. Routing Table Size ........................................10
4.4. Delay Bound for P2P Routing ...............................10
4.5. Control Packet Overhead ...................................11
4.6. Loss of Connectivity ......................................13
5. RPL in a Building Automation Routing Scenario ..................18
5.1. Path Quality ..............................................18
5.2. Delay .....................................................19
6. RPL in a Large-Scale Network ...................................19
6.1. Path Quality ..............................................19
6.2. Delay .....................................................21
6.3. Control Packet Overhead ...................................21
7. Scaling Property and Routing Stability .........................22
8. Comments .......................................................24
9. Security Considerations ........................................25
10. Acknowledgements ..............................................25
11. Informative References ........................................251. Introduction 🦋
Designing a routing protocol for Low-Power and Lossy Networks (LLNs) is a major challenge, mainly because the data rates are low, packets fail to arrive pretty often, and the nodes have strict energy limits 😭 The IETF ROLL Working Group took that on and specified the Routing Protocol for Low-Power and Lossy Networks (RPL) in [RFC6550] 👑
RPL is designed to meet the core requirements in [RFC5826], [RFC5867], [RFC5673], and [RFC5548] ✨
This document adds a performance evaluation of RPL against several metrics of interest. It uses real data and topologies inside a discrete event simulator that was built to reproduce the protocol's behaviour 🧚
The metrics it evaluates are:
- Path quality metrics, such as ETX path cost, ETX path stretch, ETX fractional stretch, and hop distance stretch, as defined in Section 2 ("Terminology") 💅
- Control plane overhead 🌸
- End-to-end delay between nodes ⭐
- Ability to cope with unstable situations (link churns, node dying) 💀
- Required resource constraints on nodes (routing table size) 🔥
Some of these metrics show up in the RFCs above, and others were added to cover the challenges and unique requirements of LLNs discussed in [RFC6550]. For example, routing in a home automation deployment has strict time bounds on protocol convergence after any topology change, as mentioned in Section 3.4 of [RFC5826]. [RFC5673] asks for bounded and guaranteed end-to-end delay for routing in an industrial deployment, and [RFC5548] is happy with comparatively loose latency bounds for end-to-end communication. [RFC5548] also mandates scalability in terms of protocol performance for a network of size ranging from 10^2 to 10^4 nodes 🌈
Simulation can't formally prove that a protocol works in every situation. But it can give a good level of confidence in protocol behaviour under highly stressful conditions, if and only if real-life data is used 🙈 It's especially useful when the theoretical model assumptions might not apply to these networks and scenarios. In this document, real deployed network data traces were used to model link behaviours and network topologies 🍓
2. Terminology 💜
Please refer to [ROLL-TERMS] and [RFC6550] for terminology. On top of that, the following terms are defined here 🎀
PDR: Packet Delivery Ratio.
CDF: Cumulative Distribution Function.
Expected Transmission Count (ETX Metric): This is the expected number of transmissions needed to reach the next hop, found as the inverse of the link PDR. So at every hop, if the link quality (PDR) is high, the expected number of transmissions to reach the next hop can be as low as 1. But if the PDR for that particular link is low, multiple transmissions may be needed 📡
ETX Path Cost: This is the sum of the ETX value for each link on the route a packet takes towards the destination 🛣️
ETX Path Cost Stretch: This is the difference between the number of expected transmissions (ETX Metric) taken by a packet travelling from source to destination on a route set by RPL, and on a route set by a hypothetical ideal shortest path routing protocol that uses link ETX as its metric 🦋
ETX Fractional Stretch (fractional stretch factor of link ETX metric against ideal shortest path): This is the ratio of ETX path stretch to ETX path cost for the shortest path route between the source-destination pair 🌸
Hop Distance Stretch (stretch factor for node hop distance against ideal shortest path): This is the difference between the number of hops taken by a packet travelling from source to destination on a route set by RPL, and on a route set by a hypothetical ideal shortest path algorithm, with both using ETX as the link cost. The fractional hop distance stretch is computed as the ratio of path stretch to the count value between a source-destination pair, for the hypothetical shortest path route that optimises ETX path cost 🧚
To be continued in part 2 💖✨
3. Methodology and Simulation Setup ✨
okay so bestie, for this one RPL got run through OMNeT++ 💻🦋 It's a well-known discrete event simulator written in C++ and NEtwork Description (NED). Castalia-2.2 [Castalia-2.2] was used as the Wireless Sensor Network Simulator framework inside OMNeT++. The output and events got visualized with the Network AniMator, or NAM, which ships with the NS (Network Simulator) [NS-2].
Quick note: no versions of NS itself were used in this study. The visualization tool was just borrowed for verification purposes 🫶
Here's the thing that makes this study lowkey iconic: theoretical models can have assumptions that just don't hold for lossy links, so the team used real-life data for two parts of the simulations 🔥
- Link Failure Model: derived from time-varying real network traces that contain the packet delivery probability for each link, over all channels, for both indoor network deployment and outdoor network deployment.
- Topology: gathered from the real-life deployment (the traces mentioned above), as opposed to random topology simulations.
They used a 45-node topology deployed as an outdoor network (shown in Figure 1) and a 2442-node topology gathered from a smart meter network deployment 🌸 In Figure 1, links between a most preferred parent node and child nodes are shown in red. Links shown in black are also part of the topology, they just aren't between a preferred parent and child node.
Figure 1 [See the PDF.]
Figure 1: Outdoor Network Topology with 45 Nodes.Note that this is just a start to validate the simulation before moving on to large-scale networks 🧚
A set of time-varying link quality data was gathered from a real network deployment to form a database for the simulations. Each link in the topology randomly "picks up" a link model (trace) from that database 💅 Each link has a Packet Delivery Ratio (PDR) that changes with time (in the simulation, a new PDR is read from the database every 10 minutes) according to the gathered data. Packets are dropped randomly from that link with probability (1 - PDR). Every time a packet is about to be sent, the module generates a random number using the Mersenne Twister random number generation method. That number gets compared to the PDR to decide whether the packet gets dropped. Each link uses a different random number generator, so the simulator keeps true randomness and links don't end up correlated 👑
Also, the packet drop applies to all kinds of data and control packets (RPL), including the DIO, DAO, and DIS packets defined in [RFC6550] 😭 Figure 2 shows a typical temporal characteristic of links from the indoor network traces used in the simulations. It's giving chaos in the best way: several links have perfect connectivity, some drop as low as a 10% PDR, and several swing between 30% and 80%, sharply flipping back and forth between a high value (strong connectivity) and a low value (weak connectivity) 🎀
Figure 2 [See the PDF.]
Figure 2: Example of Link Characteristics.In the RPL simulator, the LBR (LLN Border Router) or the Directed Acyclic Graph (DAG) root is the first to start sending out DIO messages, and the DAG gets gradually constructed 🌈 RPL uses trickle timers. The protocol sets a minimum time period with which the nodes start re-issuing DAOs, and that minimum period is denoted by the trickle parameter Imin. RPL also sets an upper limit on how many times this time period can be doubled, denoted by the parameter DIOIntervalDoublings, as defined in [RFC6550]. For the simulation, Imin is initially set to 1 second and DIOIntervalDoublings is equal to 16, which means the maximum time between two consecutive DIO emissions by a node (under a steady network condition) is 18.2 hours ⏰ The trickle time interval for emitting DIO messages starts at the initial value of 1 second and then changes over simulation time, as mentioned in [RFC6206].
Another goal of this study is to give network administrators some insight into how to tweak the trickle values 🍓 These recommendations could then be used in applicability statement documents.
Every node in the network other than the LBR or DAG root also emits DAO messages as specified in [RFC6550] 💜 This initially populates the routing tables with the prefixes received from children via the DAO messages, to support Point-to-Point (P2P) and Point-to-Multipoint (P2MP) traffic in the "down" direction. During these simulations, it is assumed that each node is capable of storing route information for other nodes in the network (the storing mode of RPL) 🦋
For nodes implementing RPL, the routing table memory requirement varies according to the position in the DODAG (Destination-Oriented DAG), as you'd expect ✨ The (worst-case) assumption is that there is no route summarization (aggregation) in the network. So a node closer to the DAG has to store more entries in its routing table 😭 It's also assumed that all nodes have equal memory capacity to store the routing states.
For simulations of the indoor network, each node sends traffic according to a Constant Bit Rate (CBR) to all other nodes in the network over the simulation period. Each node generates a new data packet every 10 seconds. Each data packet is 127 bytes, including 802.15.4 PHY/MAC headers and RPL packet headers. All control packets are also encapsulated with 802.15.4 PHY/MAC headers. To make things more realistic, 80% of the packets generated by each node are destined to the root, and the remaining 20% are uniformly assigned to nodes other than the root. So yes, the root receives a considerably larger amount of data than everyone else 👑 These values may be revised when studying P2P traffic, so that a majority of traffic goes to all nodes instead of the root. In the later part of the simulation, a typical home/building routing scenario is also simulated, and different path quality metrics are computed for that traffic pattern 🏠
The packets are routed through the DODAG built by RPL according to the mechanisms specified in [RFC6550] 🫶
A number of RPL parameters are varied (such as the packet rate from each source and the time period for emitting a new DAG sequence number) to observe their effect on the performance metric of interest 🔥
4. Performance Metrics 💅
4.1. Common Assumptions 🌸
As the DAO messages feed the routing tables in the network, the tables grow with time and with the size of the network. Nevertheless, no constraint was imposed on the size of the routing table or on how much information a node can store 🧚 The routing table size isn't expressed in Kbytes of memory usage. It's measured as the number of entries for each node. Each entry has the next-hop node and the path cost associated with the destination node.
The link ETX (Expected Transmission Count) metric is used to build the DODAG and is specified in [RFC6551] ✨
4.2. Path Quality 🦋
Hop Count: okay so for every source-destination pair, we count the hops for both RPL and shortest path routing 🗺️ Shortest path routing is a hypothetical ideal protocol that would always find the shortest path in terms of ETX path cost (or whichever metric is in use) across the network. It's the gold standard we're comparing against 🏆
The Cumulative Distribution Function (CDF) of the hop count for all paths (n * (n - 1) in an n-node network) is plotted in Figure 3 for both RPL and shortest path routing. The CDF at 4 hops is around 80% for RPL and 90% for shortest path routing ✨ In other words, for this topology, 90% of paths are 4 hops or less with ideal shortest path routing, while with RPL P2P routing, 90% of paths are no more than 5 hops. Not bad for a P2P scheme that isn't optimized, right? 🥹 The path quality of RPL is close to an optimized P2P routing mechanism for this topology, and that's honestly so iconic 👑
Part of the reason might be that the DAG root sits at the center of the network, so routing through the DAG root is often close to optimal (shortest path) routing 🎯 This result could be different in a topology where the DAG root is at one end of the network, so don't take it as gospel for every setup 🙈
Figure 3 [See the PDF.]
Figure 3: CDF of Hop Count versus Hop Count.
ETX Path Cost: in the simulation, the total ETX path cost (defined in the Terminology section) from source to destination is computed for each packet 🧮
Figure 4 shows the CDF of the total ETX path cost, with both RPL and shortest path routing. Again, the ETX path cost from all sources to all destinations is close to that of shortest path routing for the network 💖
Figure 4 [See the PDF.]
Figure 4: CDF of Total ETX Path Cost along Path versus ETX Path Cost.
Path Stretch: the path stretch metric covers the stretch factor for both hop distance and ETX path cost (as defined in the Terminology section) 📏 The hop distance stretch is the difference between the number of hops a packet takes while following a route built via RPL and the number of hops taken by shortest path routing (using link ETX as the metric). The ETX path cost stretch is also provided 🌸
The CDFs of both path stretch metrics are plotted against the value of the corresponding path stretch over all packets in Figures 5 and 6, for hop distance stretch and ETX path stretch respectively 📊 Here's the tea ☕ For a few packets, the RPL path has fewer hops than the ideal shortest path, where path ETX is minimized along the DAG. That happens because there are a few source-destination pairs where the total ETX path cost is equal to or less than the ideal path's, even though the packet takes more hops 🤯 The RPL implementation ignores a 20% change in total ETX path cost before switching to a new parent or emitting a new DIO. So it doesn't necessarily give the shortest path in terms of total ETX path cost. The result is a few paths with smaller hop counts but larger (or equal) total ETX path cost 🙃
Figure 5 [See the PDF.]
Figure 5: CDF of Hop Distance Stretch versus Hop Distance Stretch Value.
Figure 6 [See the PDF.]
Figure 6: CDF of ETX Path Stretch versus ETX Path Stretch Value.
The data for the CDF of the hop count and ETX path cost for the ideal shortest path (SP) and a path built via RPL, along with the CDF of the routing table size, is in Table 1 below. Figures 3 to 7 relate to the data in this table 📋
+---------+--------+---------+-----------+------------+-------------+
| CDF | Hop | Hop | ETX Cost | ETX Cost | Routing |
| (%age) | (SP) | (RPL) | (SP) | (RPL) | Table Size |
+---------+--------+---------+-----------+------------+-------------+
| 0 | 1.0 | 1.0 | 1 | 1.0 | 0 |
| 5 | 1.0 | 1.03 | 1 | 1.242 | 1 |
| 10 | 2.0 | 2.0 | 2 | 2.048 | 2 |
| 15 | 2.0 | 2.01 | 2 | 2.171 | 2 |
| 20 | 2.0 | 2.06 | 2 | 2.400 | 2 |
| 25 | 2.0 | 2.11 | 2 | 2.662 | 3 |
| 30 | 2.0 | 2.42 | 2 | 2.925 | 3 |
| 35 | 2.0 | 2.90 | 3 | 3.082 | 3 |
| 40 | 3.0 | 3.06 | 3 | 3.194 | 4 |
| 45 | 3.0 | 3.1 | 3 | 3.41 | 4 |
| 50 | 3.0 | 3.15 | 3 | 3.626 | 4 |
| 55 | 3.0 | 3.31 | 3 | 3.823 | 5 |
| 60 | 3.0 | 3.50 | 3 | 4.032 | 6 |
| 65 | 3.0 | 3.66 | 3 | 4.208 | 7 |
| 70 | 3.0 | 3.92 | 4 | 4.474 | 7 |
| 75 | 4.0 | 4.16 | 4 | 4.694 | 7 |
| 80 | 4.0 | 4.55 | 4 | 4.868 | 8 |
| 85 | 4.0 | 4.70 | 4 | 5.091 | 9 |
| 90 | 4.0 | 4.89 | 4 | 5.488 | 10 |
| 95 | 4.0 | 5.65 | 5 | 5.923 | 12 |
| 100 | 5.0 | 7.19 | 9 | 10.125 | 44 |
+---------+--------+---------+-----------+------------+-------------+
Table 1: Path Quality CDFs.Overall, the path quality metrics tell us a lot about how the protocol performs when minimizing ETX path cost is the goal for forming the DAG 🫶 As we've seen, the protocol doesn't always find an optimum path, especially for peer-to-peer communication. But it does cut down on control overhead, since it picks a non-optimized path and that means fewer unnecessary parent selection and DIO message forwarding events 📉 Even with this specific implementation technique, around 30% of packets travel the same number of hops as an ideal shortest path routing mechanism, and 20% of packets see the same number of attempted transmissions to reach the destination 🎀 On average, the implementation costs only a few extra transmission attempts and saves a large number of control packet transmissions. That's a trade I'd take every time 💜
4.3. Routing Table Size 🧚
The goal here is to see how the number of entries per node is distributed 🔍 Figure 7 shows the CDF of the number of routing table entries for all nodes. Note that 90% of the nodes need to store fewer than 10 entries in their routing table for the topology under study 🌈 The LBR doesn't have the same power or memory constraints as regular nodes, so it can hold entries for all the nodes in the network 💪 The requirement to accommodate devices with low storage capacity was mandated in [RFC5673], [RFC5826], and [RFC5867] 📜 However, when RPL runs in storing mode, some nodes closer to the LBR or DAG root will need more memory to store larger routing tables 🧠
Figure 7 [See the PDF.]
Figure 7: CDF of Routing Table Size with Respect to Number of Nodes.
4.4. Delay Bound for P2P Routing ⏱️
For delay-sensitive applications, like home and building automation, optimizing the end-to-end delay is critical 🚨 Figure 8 shows the upper bound and the distributions of delay for paths between any two given nodes, for different hop counts between the source and destination. Here, the hop count is the number of hops a packet travels to reach the destination when using RPL paths. This hop distance does not correspond to the shortest path distance between two nodes 🙅♀️ Each packet is 127 bytes long, and with a 240-kbps radio, the transmission delay works out to approximately 4 milliseconds (ms) ⚡
Figure 8 [See the PDF.]
Figure 8: Comparison of Packet Latency, for Different Path Lengths, Expressed in Hop Count.
RFCs 5673 [RFC5673] and 5548 [RFC5548] mention a requirement for end-to-end delivery delay to stay within a bounded latency ⏳ For example, according to the industrial routing requirement, non-critical closed-loop applications may have a latency requirement as low as 100 ms, while monitoring services may tolerate a delay on the order of seconds 🏭 The results show that about 99% of end-to-end communication (where the maximum hop count is 7 hops) is bounded within the 100-ms requirement, for the topology under study 🥳 Heads up though 🚩 Due to poor link conditions, packets may be dropped, which triggers retransmission and can cause larger end-to-end delivery delays. Nodes near the LBR may also become congested at high traffic loads, which can lead to higher end-to-end delay too 😭
4.5. Control Packet Overhead ✨
Okay bestie, control plane overhead is a big deal in LLNs 🔒 We absolutely have to keep it bounded, or everything gets messy. RPL's signature move is trickle timers, which slash the number of control packets by getting rid of redundant messages 💅 So this metric checks the overhead in two situations: when things are stable (no network element failures, so no extra overhead) and when stuff breaks 💀
Data and control plane traffic comparison for each node: Figure 9 compares how many data packets each node sent (forwarded ones included) against how many control packets (DIO and DAO messages) it sent. This is for every individual node, using link ETX to optimize the DAG 🌸 Each node makes a new data packet every 10 seconds. Here's the tea: a lot of traffic gets routed straight through the DAG root itself 👑 The x axis is the node ID. As expected, the nodes near the DAG root that act as routers (not leaves) handle way more data than everyone else 🍓 Nodes 12, 36, and 38 are the main examples. They sit next to the DAG root, route most of the data packets, and show many more data transmissions than the rest, as you can see in Figure 9 🦋 Their control traffic is negligible, which backs up the vibe that RPL's control plane traffic is negligible on these topologies 🫶 Leaf nodes have comparable amounts of data and control transmissions, since they don't route any data 🧚
Figure 9 [See the PDF.]
Figure 9: Amount of Data and Control Packets Transmitted against
Node Id Using Link ETX as Routing Metric.Data and control packet transmission with respect to time: Figures 10, 11, and 12 show the data and control packets sent by node 12 (low rank in the DAG, closer to the root), node 43 (in the middle), and node 31 (a leaf node) 🎀 The counts are taken for each 10-minute interval for that particular node, so you can see the ratio between data and control packets exchanged in the network 📈 Nodes closer to the root have a higher share of data packets (as expected), and their control traffic is negligible next to all that data 💖 For a node near the root, the amount of data traffic in an interval swings hard over time. That's because the destination of packets from the same source changes every interval, while 20% of the packets are destined to the DAG root 🌈 So the traffic pattern shifts a lot from one interval to the next for these nodes ✨ For nodes farther from the root, the data-to-control ratio is smaller, since their data traffic is greatly reduced 🥺
Figure 10 [See the PDF.]
Figure 10: Amount of Data and Control Packets Transmitted
for Node 12.
Figure 11 [See the PDF.]
Figure 11: Amount of Data and Control Packets Transmitted
for Node 43.
Figure 12 [See the PDF.]
Figure 12: Amount of Data and Control Packets Transmitted
for Node 31.The control traffic load has a wave-like pattern 🌊 The control packets for each node drop fast as the DODAG stabilizes, thanks to trickle timers 🧘♀️ But when a new DODAG sequence is advertised (a global repair of the DODAG), the trickle timers reset, and the nodes start emitting DIOs frequently again to rebuild the DODAG 😭 For a node closer to the DAG root, data packets far outnumber control packets and wobble somewhat around a mean value 🌸 The control packets show a saw-tooth behavior 🦷 When the ETX link metric is used, a change in PDR changes the ETX link metric from a node to its child. That can make the node pick a new parent and change the child's DAG rank 💅 This resets the trickle timer and triggers a new DIO 🔥 Issuing a new DODAG sequence number also triggers DODAG re-computation and resets the trickle timers 🧚 So the number of control packets hits a high value in one interval and then comes back down in the next few intervals 📉 A high-control interval just means the timers to emit a new DIO got reset more often ⏰ As the network settles, the control packets get less dense 🫧 For leaf nodes, control packets are comparable to data packets, because leaf nodes are more likely to face DODAG rank changes than nodes closer to the DAG root when the link ETX values in the topology change dynamically 👑
4.6. Loss of Connectivity 💔
okay so, picture this: a link fails, and a node loses its parents, both the preferred one and the backup (if it even has one) 😭. Now it has no path to the DAG root and it's officially in its no-service era. RPL has two ways to fix this, called global repair and local repair 🛠️.
In this doc, the simulations look at how long data packets get dropped because of a loss of connectivity in two setups: a) only global repair, where the DODAG gets rebuilt when the DAG root emits new DODAG sequence numbers, and b) local repair (poisoning the sub-DAG when connectivity is lost) on top of global repair. The vibe is to tune how often the DAG root makes new DODAG sequence numbers, and to see what happens when you change that frequency for global repair alone and for global plus local repair together. The expectation is that more frequent increments of DODAG sequence numbers mean a shorter loss of connectivity, but it costs you a higher rate of control packets in the network 📈. When both global and local repair are used, the results show the trade-off between how long a node may stay without service and the total number of control packets 🎀.
Figure 13 shows the CDF of time a node spends without service when the data packet rate is one packet every 10 seconds and a new DODAG sequence number is generated every 10 minutes ✨. This plot shows how global repair behaves without any local repair scheme. When all of a node's parents are temporarily unreachable, the time until it hears a DIO from another node gets recorded, and that's its time without service 🥺. We define the DAG repair timer as the interval at which the LBR increments the DAG sequence number, which triggers a global re-optimization 🔁. In some cases, the time without service can go all the way up to the DAG repair timer value, because until a DIO is heard, the node has no parent and so no route to the LBR or to any nodes outside its own sub-DAG 💀. Honestly, that's a clear sign of no connectivity and no service for that node.
Figure 13 [See the PDF.]
Figure 13: CDF: Loss of Connectivity with Global Repair.
The effect of the DAG repair timer on time without service is plotted in Figure 14, where the source rate is 20 seconds/packet, and in Figure 15, where the source sends a packet every 10 seconds 🧚.
Figure 14 [See the PDF.]
Figure 14: CDF: Loss of Connectivity for Different Global Repair Period, Source Rate 20 Seconds/Packet.
Figure 15 [See the PDF.]
Figure 15: CDF: Loss of Connectivity for Different Global Repair Period, Source Rate 10 Seconds/Packet.
The data for Figures 13 and 15 is in Table 2 📊. The table shows how the CDF of time without connectivity to the LBR goes up as the period for emitting new DAG sequence numbers gets longer, when nodes generate a packet every 10 seconds.
+---------+------------------+------------------+-------------------+
| CDF | Repair Period | Repair Period | Repair Period |
| (%age) | 10 Minutes | 30 Minutes | 60 Minutes |
+---------+------------------+------------------+-------------------+
| 0 | 0.464 | 0.045 | 0.027 |
| 5 | 0.609 | 0.424 | 0.396 |
| 10 | 1.040 | 1.451 | 0.396 |
| 15 | 1.406 | 3.035 | 0.714 |
| 20 | 1.934 | 3.521 | 0.714 |
| 25 | 2.113 | 5.461 | 1.856 |
| 30 | 3.152 | 5.555 | 1.856 |
| 35 | 3.363 | 7.756 | 6.173 |
| 40 | 4.9078 | 8.604 | 6.173 |
| 45 | 8.575 | 9.181 | 14.751 |
| 50 | 9.788 | 21.974 | 14.751 |
| 55 | 13.230 | 30.017 | 14.751 |
| 60 | 17.681 | 31.749 | 16.166 |
| 65 | 29.356 | 68.709 | 16.166 |
| 70 | 34.019 | 92.974 | 302.459 |
| 75 | 49.444 | 117.869 | 302.459 |
| 80 | 75.737 | 133.653 | 488.602 |
| 85 | 150.089 | 167.828 | 488.602 |
| 90 | 180.505 | 271.884 | 488.602 |
| 95 | 242.247 | 464.047 | 488.602 |
| 100 | 273.808 | 464.047 | 488.602 |
+---------+------------------+------------------+-------------------+Table 2: Loss of Connectivity Time, Data Rate - 10 Seconds / Packet.
The data for Figure 14 is in Table 3 💅. This table shows how the CDF of time without connectivity to the LBR goes up as the period for emitting new DAG sequence numbers gets longer, when nodes generate a packet every 20 seconds.
+---------+------------------+------------------+-------------------+
| CDF | Repair Period | Repair Period | Repair Period |
| (%age) | 10 Minutes | 30 Minutes | 60 Minutes |
+---------+------------------+------------------+-------------------+
| 0 | 0.071 | 0.955 | 0.167 |
| 5 | 0.126 | 2.280 | 1.377 |
| 10 | 0.403 | 2.926 | 1.409 |
| 15 | 0.902 | 3.269 | 1.409 |
| 20 | 1.281 | 16.623 | 3.054 |
| 25 | 2.322 | 21.438 | 5.175 |
| 30 | 2.860 | 48.479 | 5.175 |
| 35 | 3.316 | 49.495 | 10.30 |
| 40 | 3.420 | 93.700 | 25.406 |
| 45 | 6.363 | 117.594 | 25.406 |
| 50 | 11.500 | 243.429 | 34.379 |
| 55 | 19.703 | 277.039 | 102.141 |
| 60 | 22.216 | 284.660 | 102.141 |
| 65 | 39.211 | 285.101 | 328.293 |
| 70 | 63.197 | 376.549 | 556.296 |
| 75 | 88.986 | 443.450 | 556.296 |
| 80 | 147.509 | 452.883 | 1701.52 |
| 85 | 154.26 | 653.420 | 2076.41 |
| 90 | 244.241 | 720.032 | 2076.41 |
| 95 | 518.835 | 1760.47 | 2076.41 |
| 100 | 555.57 | 1760.47 | 2076.41 |
+---------+------------------+------------------+-------------------+Table 3: Loss of Connectivity Time, Data Rate - 20 Seconds / Packet.
Figure 16 shows how the DAG global repair timer period affects control traffic 📉. As expected, when new DAG sequence numbers are generated more often, control traffic goes down, because DIO messages are sent less frequently to rebuild the DODAG. The catch is that cutting control traffic this way means more loss of connectivity when only global repair is used 😬.
Figure 16 [See the PDF.]
Figure 16: Amount of Control Traffic for Different Global Repair Periods.
From these results, it's clear that the time the protocol takes to re-establish routes and converge after an unexpected link or device failure is pretty long 🐢. [RFC5826] says that "the routing protocol MUST converge within 0.5 seconds if no nodes have moved". Clearly, a repair mechanism based only on new DAG sequence numbers wouldn't meet that requirement. So a local repair mechanism was adopted: poisoning the sub-DAG and issuing a DIS 🙌.
The effect of the DAG repair timer on time without service when local repair is turned on is shown in Figure 17, where the source rate is 20 seconds/packet 👀. Figures 18 and 19 compare the CDF of loss of connectivity for global repair and for global plus local repair. These are semi-log plots, with the x axis in logarithmic scale and the y axis in linear scale. Figure 18 is for a packet every 10 seconds and Figure 19 is for a packet every 20 seconds. In both, the x axis shows time on a log scale and the y axis shows the CDF on a linear scale. The big takeaway is that using local repair (with poisoning of the sub-DAG) greatly reduces loss of connectivity 🔥.
Figure 17 [See the PDF.]
Figure 17: CDF: Loss of Connectivity for Different DAG Repair Timer Values for Global+Local Repair, Source Rate 20 Seconds/Packet.
Figure 18 [See the PDF.]
Figure 18: CDF: Loss of Connectivity for Global Repair and Global+Local Repair, Source Rate 10 Seconds/Packet.
Figure 19 [See the PDF.]
Figure 19: CDF: Loss of Connectivity for Global Repair and Global+Local Repair, Source Rate 20 Seconds/Packet.
Figure 20 compares the control plane overhead for global repair only with the global plus local repair mechanism. It shows that RPL improves convergence time for very little extra overhead ⭐. Looking at Figure 19, in 85% of the cases the protocol finds connectivity to the LBR for the concerned nodes within a fraction of a second when local repair is used. With only global repair, the repair periods are 150-154 seconds, as seen in Figures 13 and 14 💀.
Figure 20 [See the PDF.]
Figure 20: Number of Control Packets for Different DAG Sequence Number Period, for Both Global Repair and Global+Local Repair.
5. RPL in a Building Automation Routing Scenario 🏠✨
Okay, this section is a total plot twist 🫶. In the earlier traffic pattern, most of what any node generated was destined for the root. Here we look at a different pattern, which is way more common in a home or building routing scenario 🌸. In these simulations, nodes send 60% of their total generated traffic to the physically 1-hop distant node, 20% to a 2-hop distant node, and the other 20% gets spread across the other nodes in the network 🦋. The metrics they look at include the CDF of path quality metrics such as hop count, ETX path cost, average hop distance stretch, ETX path stretch, and delay for P2P routing, for all pairs of nodes 📊. Keeping a low delay bound for P2P traffic is a huge deal, because apps in home and building routing usually have low delay tolerance 💜.
5.1. Path Quality ✨
okay so Figure 21 is the CDF of hop count for both RPL and ideal shortest path routing, using the traffic pattern we just talked about 💅 Figure 22 is the CDF of the expected number of transmissions (ETX) for each packet to reach its destination 🎀 Figures 23 and 24 show the CDF of the stretch factor for these two metrics. To make the stretch factor make sense, we'll look at Figure 24 in a sec 🧚 For all paths built by RPL, 85% of the time, the path cost is less than the path cost for the ideal shortest path plus one. no cap, that's a whole vibe 🫶
Figure 21 [See the PDF.]
Figure 21: CDF of End-to-End Hop Count for RPL and
Ideal Shortest Path in Home Routing.Figure 22 [See the PDF.]
Figure 22: CDF of ETX Path Cost Metric for RPL and
Ideal Shortest Path in Home Routing.Figure 23 [See the PDF.]
Figure 23: CDF of Hop Distance Stretch from Ideal Shortest Path.Figure 24 [See the PDF.]
Figure 24: CDF of ETX Metric Stretch from Ideal Shortest Path.5.2. Delay ⏱️
okay bestie, to get a feel for the maximum delay you can see in this traffic pattern, we looked at how long RPL takes for different numbers of hops to the destination 🦋 Figure 25 shows how the end-to-end packet latency is spread out for different packets with different hop counts in the network.
Figure 25 [See the PDF.]
Figure 25: Packet Latency for Different Hop Counts in RPL.For this deployment scenario, 60% of the traffic has been restricted to a 1-hop neighborhood 🏡 So, intuitively, the protocol is expected to give path qualities that are close to those of ideal shortest path routing for most of the paths 💖 From the CDF of the hop count and ETX path cost, it is clear that peer-to-peer paths are more often closer to an ideal shortest path ✨ The end-to-end delay for distances within 2 hops is less than 60 ms for 99% of the delivered packets, while packets traversing 5 hops or more are delivered within 100 ms 99% of the time. literally iconic 😭 These results demonstrate that for a normal routing scenario of an LLN deployment in a building, RPL performs fairly well without incurring much control plane overhead, and it can be applied for delay-critical applications as well. periodt 👑
6. RPL in a Large-Scale Network 🌈
okay so in this section we're going full big-network mode 🌸 We're simulating RPL in a large network and checking how well it scales by looking at a few performance metrics: the latency and path cost stretch, and the amount of control packets 🧠 The 2442-node smart meter network with its matching link traces was used in this scalability study. To simulate a more realistic scenario for a smart meter network, 100% of the packets generated by each node are destined to the root. Therefore, no traffic is destined to nodes other than the root. main character energy 💅
6.1. Path Quality 🦋
To check RPL's scalability, we compare the CDF of the ETX path cost in the large-scale smart meter network to a hypothetical ideal shortest path routing protocol that minimizes the total ETX path cost (Figure 26). In this simulation, the path stretch is also calculated for each packet that goes through the network. The path stretch is the difference between the path cost a packet takes while following a route built via RPL and a path computed using an ideal shortest path routing protocol. The CDF of the ETX fractional stretch, which is the ETX metric stretch value divided by the ETX path cost of an ideal shortest path, is plotted in Figure 27.
The fractional hop distance stretch value, as defined in the Terminology section, is shown in Figure 28.
Looking at the path quality plots, it is obvious that RPL works in a non-optimal way in this deployment scenario as well 🥺 However, on average, for each source-destination pair, the ETX fractional stretch is limited to 30% of the ideal shortest path cost. This fraction is higher for paths with shorter distances and lower for paths where the source and destination are far apart. The negative stretch factor for the hop count is an interesting feature of this deployment 👀 It's due to RPL's decision to not switch to another parent where the improvement in path quality is not significant. As mentioned previously, in this implementation, a node will only switch to a new parent if the advertised ETX path cost to the LBR through the new candidate parent is 20% better than the old one. The nodes tend to hear DIOs from a smaller hop count first, and later don't always shift to a larger hop count and smaller ETX path cost. Since the traffic is mostly going to the DAG root, some P2P paths built via RPL do end up with a smaller hop count from source to destination, albeit at a larger ETX path cost 🍓
As observed in Figure 26, 90% of the packets transmitted during the simulation have a (shortest) ETX path cost to destination less than or equal to 12. However, via RPL, 90% of the packets will follow paths that have a total ETX path cost of up to 14. Though all packets are destined to the LBR, it's worth noting that this implementation ignores a change of up to 20% in total ETX path cost. Figures 27 and 28 show that all paths have a very low ETX fractional stretch factor as far as the total ETX path cost is concerned, and some of the paths have lower hop counts to the LBR or DAG root as well when compared to the hop count of the ideal shortest path ✨
Figure 26 [See the PDF.]
Figure 26: CDF of Total ETX Path Cost versus ETX Path Cost.Figure 27 [See the PDF.]
Figure 27: CDF of ETX Fractional Stretch versus
ETX Fractional Stretch Value.Figure 28 [See the PDF.]
Figure 28: CDF of Fractional Hop Count Stretch.6.2. Delay ⏰
Figure 29 shows how end-to-end packet latency is spread out for different hop counts in the network. According to [RFC5548], Urban LLNs (U-LLNs) are delay tolerant, and the information, except for critical alarms, should arrive within a fraction of the reporting interval (within a few seconds) 🫶 The packet generation for this deployment has been set higher than usual to create high traffic volume, and nodes generate data once every 30 seconds. Still, the end-to-end latency for most of the packets is squeezed between 500 ms and 1 s, where the upper limit corresponds to packets traversing longer paths (greater than or equal to 6 hops) 🚀
Figure 29 [See the PDF.]
Figure 29: End-to-End Packet Delivery Latency
for Different Hop Counts.6.3. Control Packet Overhead 📦
Figure 30 compares the data packets (originated and forwarded) and the control packets (DIO and DAO messages) transmitted by each node (link ETX is used as the routing metric). Here you can see that, even with the large scale of the network, the amount of control traffic in the protocol is negligible compared to data packet transmission 🙈 The smaller node ID for this network indicates closer proximity to the DAG root, and nodes with high ID numbers are farther away from the DAG root. Also, as expected, Figures 31, 32, and 33 show that the (non-leaf) nodes closer to the DAG root have many more data packet transmissions than other nodes. The leaf nodes have comparable amounts of data and control packet transmissions, since they don't take part in routing the data 🌷 As seen before, the data traffic for a child node has much less variation than the nodes closer to the DAG root. This variation decreases as DAG depth increases. In this topology, Nodes 1, 2, and 3, etc., are direct children of the LBR 🧚
Figure 30 [See the PDF.]
Figure 30: Data and Control Packet Comparison.Figure 31 [See the PDF.]
Figure 31: Data and Control Packets over Time for Node 1.Figure 32 [See the PDF.]
Figure 32: Data and Control Packets over Time for Node 78.Figure 33 [See the PDF.]
Figure 33: Data and Control Packets over Time for Node 300.In Figure 34, the effect of the global repair period timer on control packet overhead is shown 🔥
Figure 34 [See the PDF.]
Figure 34: Numbers of Control Packets for Different
Global Repair Timer Periods.7. Scaling Property and Routing Stability ✨
okay so the big question here is how much CPU drama one node has to deal with 😭 An important metric is the maximum load any node experiences (CPU usage), measured as the number of control packets that node transmits. To see how RPL scales in large-scale networks, we also need to look at how many packets the RPL nodes handle across networks of different sizes. It's giving scaling check 💅
In these simulations, at any given interval, the node with the maximum control overhead load gets identified. Its control overhead is plotted against time for three networks under study. Network 'A' has 45 nodes and is shown in Figure 1 (Section 3). Network 'B' is another deployed outdoor network with 86 nodes. Network 'C' is the large deployed smart meter network with 2442 nodes, as mentioned earlier in this document 🌸
In Figure 35, the maximum control loads are compared across network sizes. For the 45-node network, the maximum number of control packets in the network stays within 50 packets per 1-minute interval. For the 86-node and 2442-node networks, that limit stretches to 100 and 2 * 10^3 packets per 1-minute interval, respectively 📈
Figure 35 [See the PDF.]
Figure 35: Scaling Property of Maximum Control Packets
Processed by Any Node over Time.ngl, for a network made of low-power devices on lossy links, it is of the utmost importance that routing packets don't get flooded through the whole network and that the routing topology stays as stable as possible 🦋 Any change in routing information, especially parent-child relationships, resets the timer, which leads to emitting new DIOs. It also changes the node's path metric to reach the root. That change kicks off a whole chain of control plane messages (RPL packets) in the DODAG. So it's super important to carefully control when DIO control packets get triggered, using thresholds 🎀
In this study, the team looked at the tolerance value that gets applied before a DIO reflecting a new path cost is emitted. Four cases were considered:
- No change in DAG depth of a node is ignored;
- The implementation ignores a 10% change in the ETX path cost to the DAG root. That is, if the change in total path cost to the root/LBR, whether from DIO reception from the most preferred parent or from shifting to another parent, is less than 10%, the node will not advertise the new metric to the root;
- The implementation ignores a 20% change in ETX path cost to the DAG root for any node before deciding to advertise a new depth;
- The implementation ignores a 30% change in the total ETX path cost to the DAG root of a node before deciding to advertise a new depth.
This choice does affect the optimum path quality to the DAG root. As shown in Figure 36, with 0% tolerance, 95% of the paths used have an ETX fractional stretch factor of less than 10%. With 10% and 20% tolerance levels, 95% of paths have a 15% and 20% ETX fractional path stretch. The payoff is that increased routing stability and decreased control overhead are the profit gained from that extra 10% increase in path length or ETX path cost, whichever is used as the metric to optimize the DAG 💖
Figure 36 [See the PDF.]
Figure 36: ETX Fractional Stretch Factor
for Different Tolerance Levels.Since the threshold also affects the path a packet takes, the study also shows how the threshold changes routing stability, meaning how many times P2P paths change between a source and a destination 🌈 For Network 'A' (shown in Figure 1) and the large smart meter network 'C', the CDF of path change is plotted in Figures 37 and 38, respectively. It's plotted against the fraction of path change for different thresholds, which trigger the emission of a new DIO upon path cost change.
If X packets get transferred from source A to destination B, and out of those X times, Y times the path between that source-destination pair changes, then the fraction of path change is Y/X * 100%. This metric is computed over all source-destination pairs, and the CDF goes on the y axis 🧚
Figure 37 [See the PDF.]
Figure 37: Distribution of Fraction of Path Change for Network A.Figure 38 [See the PDF.]
Figure 38: Distribution of Fraction of Path Change
for Large Network C.The document also compares the CDF of the fraction of path change across three networks: A, B, and C 👑 Figure 39 shows how each of the three networks changes its P2P path when a 30% change in metric cost to the root is ignored before shifting to a new parent.
Figure 39 [See the PDF.]
Figure 39: Comparison of Distribution of Fraction of Path Change.8. Comments 🫶
the sim results here all back up the expected protocol behavior for the topologies and traffic model used in the study ✨ For the specific scenarios discussed, the protocol meets the desired delay and convergency requirements and shows self-healing properties without any external intervention. And the control overhead is negligible, only a small fraction of the data traffic 🔥
RPL gave near-optimum path quality for most of the packets in these scenarios. It's also able to trade off control overhead for path quality through configurable parameters, such as decisions about when to switch to a new parent, depending on the application and device requirements. So RPL can trade off routing stability for control overhead too 💅 Finally, since urban LLN deployments need the protocol to scale, the study shows it scaling to larger topologies, several thousand nodes, for the topologies considered in this implementation 🌸
9. Security Considerations 💀
This document describes investigations performed in the Castalia wireless sensor network simulator. It does not consider packets on the Internet. [RFC6550] describes security considerations for RPL networks 🔒
10. Acknowledgements 🫶
The authors would like to acknowledge Jerald P. Martocci, Mukul Goyal, Emmanuel Monnerie, Philip Levis, Omprakash Gnawali, and Craig Partridge for their valuable and helpful suggestions about metrics to include and for overall feedback 💖
11. Informative References 📚
[Castalia-2.2]
Boulis, A., "Castalia: Revealing pitfalls in designing
distributed algorithms in WSN", Proceedings of the 5th
international conference on Embedded networked sensor
systems (SenSys'07), pp. 407-408, 2007.
[NS-2] "The Network Simulator version 2 (ns-2)",
<http://www.isi.edu/nsnam/ns/>.
[OMNeTpp] Varga, A., "The OMNeT++ Discrete Event Simulation System",
Proceedings of the European Simulation
Multiconference (ESM'2001), June 2001.
[RFC5548] Dohler, M., Ed., Watteyne, T., Ed., Winter, T., Ed., and
D. Barthel, Ed., "Routing Requirements for Urban Low-Power
and Lossy Networks", RFC 5548, May 2009.
[RFC5673] Pister, K., Ed., Thubert, P., Ed., Dwars, S., and T.
Phinney, "Industrial Routing Requirements in Low-Power and
Lossy Networks", RFC 5673, October 2009.
[RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation
Routing Requirements in Low-Power and Lossy Networks",
RFC 5826, April 2010.
[RFC5867] Martocci, J., Ed., De Mil, P., Riou, N., and W. Vermeylen,
"Building Automation Routing Requirements in Low-Power and
Lossy Networks", RFC 5867, June 2010.
[RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
"The Trickle Algorithm", RFC 6206, March 2011.
[RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J.,
Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur,
JP., and R. Alexander, "RPL: IPv6 Routing Protocol for
Low-Power and Lossy Networks", RFC 6550, March 2012.
[RFC6551] Vasseur, JP., Ed., Kim, M., Ed., Pister, K., Dejean, N.,
and D. Barthel, "Routing Metrics Used for Path Calculation
in Low-Power and Lossy Networks", RFC 6551, March 2012.
[ROLL-TERMS]
Vasseur, JP., "Terminology in Low power And Lossy
Networks", Work in Progress, September 2011.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@coe.drexel.edu
JP. Vasseur (editor)
Cisco Systems, Inc.
11, Rue Camille Desmoulins
Issy Les Moulineaux 92782
France
EMail: jpv@cisco.com📦 where this page comes from
- ietf: rfc6687 2012-10
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms