20  RPL Core & DODAG

In 60 Seconds

RPL (Routing Protocol for Low-Power and Lossy Networks) organizes IoT devices into a tree-like structure called a DODAG, where each node has a RANK value that increases with distance from the root gateway. Four control messages (DIO, DIS, DAO, DAO-ACK) build and maintain the routing topology, while the Trickle algorithm dramatically reduces energy consumption by slowing message frequency in stable networks.

20.1 Learning Objectives

By the end of this chapter, you will be able to:

  • Distinguish DAG from DODAG explaining the structural properties of Directed Acyclic Graphs in routing
  • Analyze the RANK mechanism demonstrating how RANK prevents routing loops in RPL networks
  • Trace DODAG construction walking through the step-by-step process of building a routing topology
  • Classify control messages identifying DIO, DIS, DAO, and DAO-ACK by their roles and directions
  • Contrast routing modes evaluating trade-offs between Storing and Non-Storing modes
  • Design RPL strategies selecting appropriate parameters for constrained IoT network deployments
MVU: Minimum Viable Understanding

If you only have 5 minutes, understand these three concepts:

  1. DODAG is a tree-like routing structure with a single root (gateway) where all paths lead toward the root - data flows “uphill” from sensors to gateway

  2. RANK prevents routing loops - each node has a RANK value that increases with distance from root; packets can ONLY be forwarded to nodes with LOWER RANK (closer to root)

  3. Four control messages build the network: DIO (advertise DODAG downward), DIS (request info), DAO (advertise reachability upward), DAO-ACK (confirm receipt)

Key numbers to remember: Root RANK = 0; default MinHopRankIncrease = 256; trickle timer ranges from seconds (unstable) to hours (stable); RPL supports both Storing mode (nodes keep routing tables) and Non-Storing mode (root knows all routes).

Connect with Learning Hubs

Explore Further:

  • Knowledge Map: See how RPL connects to 6LoWPAN, IPv6, and IoT networking
  • Simulations Hub: Try RPL routing simulations and network topology tools
  • Quizzes Hub: Test your understanding of routing protocols and DODAG construction
  • Videos Hub: Watch RPL operation demonstrations and mesh network visualizations

Hands-On Practice:

RPL (Routing Protocol for Low-Power and Lossy Networks) is a routing protocol designed specifically for IoT networks where:

  • Devices have limited power (battery-operated sensors)
  • Connections are unreliable (wireless links that come and go)
  • Networks are large (hundreds or thousands of nodes)

The Problem RPL Solves:

Imagine you’re in a large building with thousands of wireless sensors. How does data from a sensor in the basement reach the internet gateway on the roof? It can’t send directly - the signal is too weak. Instead, data must “hop” through intermediate devices.

RPL creates an efficient map of these hops, ensuring:

  1. Data always finds a path to the gateway
  2. No data gets stuck in infinite loops
  3. The network adapts when devices fail or move

Real-World Analogy: Think of water flowing downhill to a river. RPL creates “digital downhill paths” where data naturally flows toward the gateway (like water flows to the river). The RANK system ensures data always moves “downhill” - never getting stuck going in circles.

Hey future network engineers! Let’s learn about RPL with a fun relay race!

Imagine This: You’re at a huge park with friends spread all around. You need to get a message to your teacher at the center, but you can only whisper to friends nearby.

The RPL Way:

  1. Teacher (ROOT) stands at the center and shouts: “I’m here! Pass messages to me!”
  2. Kids nearby hear it first - they’re “close” to teacher (low RANK)
  3. Kids farther away only hear from their nearby friends - they’re “farther” (higher RANK)
  4. Everyone knows which friend is “closer” to teacher

When you have a message:

  • Look for a friend with a LOWER number (closer to teacher)
  • Pass your message to them
  • They pass it forward until it reaches teacher!

Why can’t messages go backwards? That’s the RULE: Only pass to friends with LOWER numbers. This prevents your message from going in circles forever!

Teacher (0) <-- Friend A (100) <-- Friend B (200) <-- You (300)
                    Messages only flow this way! -->

The Cool Part: If Friend A goes to get snacks, you just find another friend with a lower number. The network heals itself!

Challenge: If you’re RANK 250 and have friends at RANK 150, 200, and 300, which friend should you pass your message to? (Answer: RANK 150 - lowest number!)

20.2 RPL Core Concepts

20.2.1 Directed Acyclic Graph (DAG)

DAG = Directed Acyclic Graph

A DAG is a graph structure where edges have direction (like one-way streets) and there are no cycles (you can never return to where you started by following the arrows).

Directed Acyclic Graph example showing nodes connected with directed arrows flowing downward, demonstrating the acyclic property where following any edge sequence never returns to the starting node

Directed Acyclic Graph (DAG) structure showing one-way paths with no cycles
Figure 20.1: Directed Acyclic Graph (DAG) structure showing one-way paths with no cycles

Key Properties of DAGs:

Property Description Routing Benefit
Directed Edges have direction (arrows) Data flows in predictable direction
Acyclic No cycles exist Guarantees loop-free routing
Graph Nodes connected by edges Flexible network topology

Why Use DAG for Routing?

  • Loop-free by design: The acyclic property mathematically guarantees no routing loops
  • Hierarchical structure: Creates natural parent-child relationships for forwarding
  • Efficient aggregation: Data naturally flows toward common destinations
  • Multiple paths: Unlike trees, DAGs allow redundant paths for reliability

20.2.2 DODAG (Destination Oriented DAG)

RPL uses DODAG: A DAG with a single root node that serves as the destination for all upward traffic.

Destination Oriented Directed Acyclic Graph (DODAG) with single ROOT node at top (Rank 0), intermediate nodes at Rank 256 and 512, leaf nodes at Rank 768, all paths flowing toward root

DODAG topology with ROOT at top (RANK 0) and increasing RANK values moving away from root
Figure 20.2: DODAG topology with ROOT at top (RANK 0) and increasing RANK values moving away from root
Comparison diagram showing generic DAG on left with multiple possible roots versus DODAG on right with single designated root node, illustrating how DODAG constrains the graph structure for routing purposes
Figure 20.3: Comparison of generic DAG versus DODAG with single designated root
RPL DAG and DODAG structure showing border router as root with tree-like formation where all nodes have paths leading upward to the single root destination
Figure 20.4: RPL DAG and DODAG structure showing border router as root with tree-like formation

DODAG Properties:

Property Description Example
Single Root One destination node (border router/gateway) IPv6 border router connecting to internet
Upward Routes All paths lead toward root Sensor data flows to gateway
RANK Hierarchy Position relative to root (root = 0) Root=0, children=256, grandchildren=512
Multiple Parents Nodes can have backup parents Resilience if primary parent fails
Key Insight: DODAG vs Tree

A DODAG is NOT the same as a tree:

  • Tree: Each node has exactly ONE parent
  • DODAG: Nodes can have MULTIPLE parents (for redundancy)

This distinction is crucial for IoT reliability - if one parent fails, data can route through an alternate parent.

20.2.3 RANK: Loop Prevention Mechanism

RANK is a scalar value representing a node’s position relative to the root. It is the fundamental mechanism RPL uses to prevent routing loops.

RANK loop prevention mechanism showing ROOT at Rank 0, Node A at Rank 100, Node B at Rank 250, Node C at Rank 370, with valid forward links toward root and a forbidden backward link from C to A that would create a routing loop

RANK mechanism showing valid forwarding to lower RANK and forbidden paths to higher RANK
Figure 20.5: RANK mechanism: packets forward only to lower-RANK neighbors, mathematically preventing loops
RPL RANK mechanism diagram showing root at minimum RANK value, with RANK increasing monotonically as nodes are positioned farther from root, preventing loops by ensuring packets always move toward lower RANK values
Figure 20.6: RPL RANK mechanism showing monotonically increasing RANK with distance from root

RANK Rules:

Rule Description Purpose
Root RANK = 0 Root has minimum RANK value Establishes reference point
RANK increases away from root Children have higher RANK than parents Creates hierarchy
Forward to lower RANK Packets sent to nodes with lower RANK Ensures progress toward root
Never parent higher RANK Cannot select parent with higher RANK Prevents loops

RANK Calculation Formula:

RANK(node) = RANK(parent) + RankIncrease

Where RankIncrease depends on the Objective Function and considers:

  • Link cost (ETX - Expected Transmission Count)
  • Signal quality (RSSI, LQI)
  • Energy consumption
  • Latency requirements
  • Hop count

RANK calculation combines hop distance with link quality into a single scalar value.

\[\text{RANK} = \text{RANK}_{\text{parent}} + (\text{ETX} \times \text{MinHopRankIncrease})\]

where \(\text{ETX} = \frac{\text{Probes Sent}}{\text{Probes Acknowledged}}\) measures link quality (1.0 = perfect, higher = lossy).

For example, consider a 3-hop path with default MinHopRankIncrease = 256:

\[\begin{align*} \text{Root} &: \text{RANK} = 0 \\ \text{Node A} &: \text{RANK} = 0 + (1.2 \times 256) = 307 \\ \text{Node B} &: \text{RANK} = 307 + (1.5 \times 256) = 691 \\ \text{Node C} &: \text{RANK} = 691 + (1.1 \times 256) = 973 \end{align*}\]

This means Node C prefers Node B as parent (RANK 691) over a hypothetical Node D with RANK 800, even though both are one hop away. The cumulative path quality matters more than simple hop count.

20.3 Interactive: RANK Calculator

Explore how RANK accumulates across hops with different link quality values:

Worked Example:

Step-by-step RANK calculation showing ROOT at 0, Node A calculates 0+100=100, Node B calculates 100+150=250, Node C calculates 250+120=370

RANK calculation example showing cumulative RANK values based on link costs
Figure 20.7: RANK calculation example showing cumulative RANK values based on link costs

Loop Prevention in Action:

  • Node C (RANK 370) can choose Node A (RANK 100) as parent
  • Node A (RANK 100) CANNOT choose Node C (RANK 370) as parent
  • This asymmetry mathematically guarantees no routing loops
RANK vs Hop Count

RANK ≠ Hop Count - This is a common misconception!

RANK considers link quality, not just distance:

Scenario Hops RANK Increase Total RANK
Good link, 1 hop 1 100 100
Poor link, 1 hop 1 300 300
Good links, 2 hops 2 100 + 100 200

Result: A node may prefer 2 hops via good links (RANK 200) over 1 hop via a poor link (RANK 300). This optimizes for reliability, not just hop count.

20.4 DODAG Construction Process

RPL builds the DODAG through four types of control messages that work together to establish and maintain routing paths.

20.4.1 RPL Control Messages Overview

RPL control messages overview showing DIO flowing downward to advertise DODAG, DIS flowing any direction to request information, DAO flowing upward to advertise reachability, and DAO-ACK confirming receipt

RPL Control Messages: DIO, DIS, DAO, and DAO-ACK and their roles in DODAG construction
Figure 20.8: RPL Control Messages: DIO, DIS, DAO, and DAO-ACK and their roles in DODAG construction

Control Message Summary:

Message Direction Purpose Triggers
DIO Downward (multicast) Advertises DODAG existence and parameters Trickle timer, DIS receipt
DIS Any (multicast/unicast) Requests DIO from neighbors New node joining, lost connectivity
DAO Upward (unicast) Advertises node reachability Node joins DODAG, topology change
DAO-ACK Downward (unicast) Confirms DAO receipt DAO with ACK request
Progressive DODAG construction diagram showing Step 1: root broadcasts DIO, Step 2: nearby nodes join and calculate RANK, Step 3: joined nodes broadcast their own DIO, Step 4: process continues until all nodes are part of DODAG
Figure 20.9: Building a DODAG showing progressive node joining and RANK assignment

20.4.2 Step-by-Step DODAG Construction

DODAG construction sequence diagram showing 5 steps: ROOT initiates with DIO broadcast, nodes receive and join calculating RANK, nodes propagate DIO to further neighbors, upward routes established via parent pointers, downward routes built via DAO messages
Figure 20.10: DODAG construction sequence showing DIO propagation, parent selection, and DAO route advertisement

20.4.3 Detailed Construction Steps

Step 1: Root Initiates DODAG

Root node (border router/gateway): 1. Creates DODAG: Assigns unique DODAG ID 2. Sets RANK = 0: Root has minimum RANK 3. Broadcasts DIO: Sends DODAG Information Object (multicast)

DIO Contents:

  • DODAG ID (IPv6 address)
  • RANK (0 for root)
  • Objective function (routing metric)
  • DODAG configuration (timers, etc.)

RPL construction steps showing four progressive stages: Step 1 root broadcasts DIO, Step 2 nearby nodes join and calculate RANK, Step 3 joined nodes rebroadcast DIO further, Step 4 all reachable nodes have joined DODAG ## Step 2: Nodes Receive DIO and Join

Node receives DIO:

  1. Decision: Join this DODAG or wait for others?
    • Compare DODAG rank, objective function
    • May receive DIOs from multiple DODAGs
  2. Calculate RANK: RANK = parent_RANK + increase
  3. Select parent: Choose sender of DIO (if acceptable)
  4. Update state: Store DODAG ID, parent, RANK

Multiple DIO Sources:

  • Node may hear DIOs from multiple neighbors
  • Chooses best parent (lowest RANK, best link quality)
  • May maintain backup parents (loop-free)

20.5 Step 3: Nodes Propagate DIO

After joining DODAG:

  1. Node becomes part of DODAG
  2. Sends own DIO: Advertises DODAG to neighbors
  3. DIO contents: Own RANK, DODAG ID, etc.
  4. Trickle timer: Controls DIO frequency (adaptive)

Trickle Algorithm:

  • Stable network: Send DIOs infrequently (minutes to hours)
  • Network changes: Send DIOs frequently (seconds)
  • Reduces overhead while maintaining responsiveness
Step 4: Build Upward Routes

Upward routes (towards root) established automatically: - Each node knows its parent (from DIO selection) - Default route: Send to parent (towards root) - No routing table needed for upward routes (just parent pointer)

Example:

Node 3 -> Node 1 -> Root
(N3 knows parent is N1, N1 knows parent is Root)
Step 5: Build Downward Routes (Storing Mode)

Downward routes (from root to nodes) require DAO messages:

  1. Node sends DAO to parent:
    • “I am reachable via you”
    • Includes node’s address and prefixes
  2. Parent updates routing table:
    • “Node X is reachable via this child”
  3. Parent propagates DAO towards root:
    • Aggregates reachability information
  4. Root knows all nodes:
    • Complete routing table for downward routes

DAO-ACK (optional): - Parent confirms DAO receipt - Reliability for critical networks

Common Mistake: Forgetting MinHopRankIncrease Impact on Network Depth

The Error: Deploying a large multi-hop network (10+ hops deep) without adjusting the default MinHopRankIncrease value of 256.

Why It’s Problematic:

RANK is a 16-bit unsigned integer (0-65535). With MinHopRankIncrease = 256: - Maximum theoretical hops: 65535 / 256 = 256 hops - Practical limit with ETX 1.8: 65535 / (256 × 1.8) ≈ 142 hops, but parent-selection instability appears much earlier (~20-30 hops)

Real-World Example - Warehouse Network (2021):

A logistics company deployed 300 sensors across a 200,000 sq ft warehouse: - Network depth: 12 hops from border router to farthest sensors - MinHopRankIncrease: 256 (default) - Average ETX per link: 1.8 (concrete walls, metal racks)

The Problem:

Farthest sensor RANK = 12 hops x 256 x 1.8 ETX = 5,530
Acceptable (< 65535), but sensors at 13-15 hops experienced:
- RANK values approaching local maximums for neighbor comparison
- Constant parent switching (thrashing)
- 40% packet delivery rate

The Solution:

Reduce MinHopRankIncrease to extend usable network depth:

New MinHopRankIncrease = 128 (half the default)
Farthest sensor RANK = 12 x 128 x 1.8 = 2,765
Supports deeper topology with more headroom before instability

Results:

  • Sensors at 13-15 hops: RANK = 3,000-3,800 (valid and stable)
  • Packet delivery rate: 40% -> 92%
  • Parent switching reduced by 85%
  • Network converged in 45 seconds vs 8+ minutes

How to Avoid:

  1. Calculate RANK headroom before deployment:

    Max stable hops ≈ 65535 / (MinHopRankIncrease × Avg_ETX) / 2

    (Divide by 2 as a safety margin for RANK comparison stability)

  2. Configure MinHopRankIncrease based on network size:

    • Small networks (< 5 hops): 256 (default, fine granularity)
    • Medium networks (5-10 hops): 128 (balance)
    • Large networks (10-20 hops): 64 (supports deep topologies)
    • Very large (20+ hops): 32 (minimum differentiation)

  3. Monitor RANK values during deployment:

    • RANK at 5 hops with default settings: ~1,300-1,600 (healthy)
    • RANK > 50,000: Warning - approaching overflow risk
    • RANK > 60,000: Critical - reduce MinHopRankIncrease immediately

Trade-off: Lower MinHopRankIncrease reduces path differentiation. With MinHopRankIncrease = 32, links with ETX 1.0 vs 1.5 may round to the same RANK value, reducing optimal parent selection accuracy. Only reduce when network depth requires it.

Key Concepts

  • RPL (Routing Protocol for LLNs): An IPv6 distance-vector routing protocol (RFC 6550) building a Destination Oriented Directed Acyclic Graph (DODAG) optimized for constrained IoT networks.
  • DODAG (Destination Oriented Directed Acyclic Graph): The directed graph formed by RPL where all paths lead toward the DODAG root (border router); prevents routing loops structurally.
  • RANK: A scalar value indicating a node’s position in the DODAG; nodes only route toward lower-RANK nodes (the root), preventing loops.
  • Objective Function (OF): The algorithm determining how RANK is calculated and how parent nodes are selected; e.g., OF0 (hop count), MRHOF (ETX-based).
  • DIO (DODAG Information Object): An RPL control message broadcast by nodes to advertise their DODAG membership and RANK; used by new nodes to join the DODAG.
  • DAO (Destination Advertisement Object): An RPL control message sent upward through the DODAG to register routes; enables the root to maintain downward routing tables in Storing Mode.
  • ETX (Expected Transmissions): A link quality metric counting the expected number of transmissions required to deliver a packet; accounts for link loss rate.

20.6 Summary and Key Takeaways

RPL (Routing Protocol for Low-Power and Lossy Networks) is the de facto standard for routing in constrained IoT networks. This chapter covered the fundamental concepts that make RPL work.

20.6.1 Core Concepts Recap

Mind map showing RPL core concepts: DODAG structure at center, branching to RANK mechanism, Control Messages (DIO, DIS, DAO, DAO-ACK), Routing Modes (Storing vs Non-Storing), and Loop Prevention properties

RPL Core Concepts Summary mind map
Figure 20.11: RPL Core Concepts Summary

20.6.2 Key Takeaways

Concept Key Point Remember
DAG vs DODAG DODAG has single root, DAG can have multiple destinations “D” for Destination-Oriented
RANK Scalar value preventing loops by ensuring “downhill” forwarding Root RANK = 0, increases with distance
DIO DODAG Information Object - advertises network downward “I am here, join my DODAG”
DAO Destination Advertisement Object - reports reachability upward “I am reachable via this path”
Storing vs Non-Storing Trade-off between memory (routing tables) and root burden Memory-constrained -> Non-Storing

20.6.3 Common Pitfalls to Avoid

Avoid These Mistakes
  1. Confusing RANK with hop count - RANK considers link quality, not just distance
  2. Assuming tree topology - DODAG allows multiple parents for redundancy
  3. Ignoring trickle timer - Critical for balancing responsiveness vs. overhead
  4. Forgetting about bidirectional traffic - Upward routes are automatic; downward requires DAO

20.6.4 Quick Reference Card

Item Value/Description
RFC RFC 6550 (RPL Specification)
Default RANK increment 256 (MinHopRankIncrease)
Trickle timer range Seconds (unstable) to hours (stable)
Objective Functions OF0 (hop count), MRHOF (ETX-based)
ICMPv6 Type 155 (RPL Control Messages)

RPL prevents routing loops through a simple but powerful mechanism: RANK monotonicity. Here’s how it works:

Step 1: Root Initialization

  • Border router sets its RANK to 0
  • Broadcasts DIO message with RANK=0

Step 2: First-Hop Nodes Calculate RANK

  • Node receives DIO from root (RANK=0)
  • Measures link quality: ETX = Expected Transmissions = 1.2 (good link)
  • Calculates: RANK = Parent_RANK + (ETX × MinHopRankIncrease)
  • RANK = 0 + (1.2 × 256) = 307

Step 3: Multi-Hop Propagation

  • Second-hop node hears DIO from first-hop node (RANK=307)
  • Measures ETX to first-hop = 1.5
  • Calculates: RANK = 307 + (1.5 × 256) = 691

Step 4: Parent Selection Rule

  • Node ONLY selects parents with lower RANK than itself
  • Example: Node with RANK=691 can choose parent with RANK=307 or 512
  • Node with RANK=691 cannot choose parent with RANK=800 (higher RANK = loop risk)

Step 5: Loop Prevention Guarantee

  • RANK always increases moving away from root
  • Packets forwarded “upward” always go to lower-RANK neighbors
  • Mathematical impossibility of returning to same node (no cycles)

Why ETX Matters:

  • ETX = 1.0: Perfect link (1 transmission per successful delivery)
  • ETX = 1.5: Good link (average 1.5 attempts needed)
  • ETX = 3.0: Poor link (3 retries typical)
  • Poor links -> larger RANK increase -> discouraged as parents

This mechanism is automatic and distributed - no centralized controller needed.

RPL builds upon:

RPL connects to:

RPL enables:

  • IoT sensor networks (environmental monitoring, smart buildings)
  • Smart city deployments (street lighting, parking)
  • Industrial automation (factory floor sensors)
  • Agricultural monitoring (soil sensors across large fields)

20.7 What’s Next

Previous Up Next
Routing Labs: Algorithms Routing Fundamentals RPL DODAG Construction

Now that you understand RPL core concepts and DODAG construction, you’re ready to explore:

20.7.1 Immediate Next Steps

  1. RPL Routing Modes - Deep dive into Storing vs Non-Storing modes, source routing headers, and when to use each mode

  2. RPL Production Deployment - Real-world deployment considerations, objective function selection, and troubleshooting

20.7.3 Hands-On Practice

Test your understanding with these interactive tools: