21 RPL DODAG Construction Process
21.1 DODAG Construction Process
Learning Objectives
By the end of this section, you will be able to:
- Trace the step-by-step DODAG construction algorithm from root initialization to steady state
- Differentiate the roles of DIO, DIS, and DAO messages in network formation
- Diagram message flows during DODAG formation for a given topology
- Estimate timing and convergence of RPL networks based on Trickle parameters
RPL builds the DODAG through control messages:
For Beginners: DODAG Construction
A DODAG (Destination-Oriented Directed Acyclic Graph) is the tree-like network structure that RPL builds. Imagine organizing a relay race where each runner passes the baton toward a finish line – RPL organizes devices so that sensor data flows efficiently upward through the network to a collection point, avoiding loops.
Sensor Squad: Building the Relay Chain!
“How does a DODAG actually get built?” asked Sammy the Sensor. “Do all the devices just magically know where to send data?”
“Not at all – it happens step by step, like organizing a relay race,” explained Max the Microcontroller. “First, the ROOT gateway shouts out a DIO message: ‘Hey everyone, I am the destination! My RANK is zero!’ The devices closest to the root hear this first and join the tree.”
“Then those devices shout their own DIO messages,” continued Lila the LED. “They say ‘I heard the root! My RANK is 256. Join through me!’ And the next layer of devices joins. It ripples outward like dropping a stone in a pond – layer by layer until every device has a path to the root.”
“Once everyone has joined, they send DAO messages back UP the tree,” added Bella the Battery. “These messages say ‘Hey root, I exist and you can reach me through this path.’ It is like everyone signing in at the front desk so the building knows who is on each floor. If a device wants to request information immediately instead of waiting, it sends a DIS message – like raising your hand to ask a question!”
21.2 DODAG Construction: Visual Algorithm
This condensed visual sequence shows the 5 key phases of DODAG construction. Each diagram focuses on one step, making the algorithm easy to understand and remember.
21.2.1 Step 1: Root Initialization
What happens: Root broadcasts DIO containing Rank=0, DODAG ID, and objective function. Neighboring nodes receive but haven’t processed yet.
21.2.2 Step 2: First-Hop Join
What happens: Nodes hear DIO, calculate Rank = Parent_Rank + Link_Cost, and select root as parent. Node C has higher Rank (384) due to poorer link quality.
21.2.3 Step 3: Multi-Hop Expansion
What happens: First-hop nodes broadcast their own DIO messages. Second-hop nodes (D, E) join with Rank = 256 + 256 = 512. Process ripples outward hop-by-hop until all nodes join the DODAG.
21.2.4 Step 4: DAO Propagation
What happens: Nodes send DAO (Destination Advertisement Object) messages toward the root to establish downward routes. This enables the root (and intermediate nodes in storing mode) to send data to specific nodes.
21.2.5 Step 5: Steady State
What happens: DODAG complete! Trickle algorithm now maintains consistency with minimal overhead—DIO messages become rare when network is stable. If a node fails, neighbors detect it and repair locally.
Algorithm Summary
| Step | Action | Messages | Result |
|---|---|---|---|
| 1 | Root init | DIO broadcast | DODAG announced |
| 2 | First-hop join | DIO received | Nodes calculate Rank, select parent |
| 3 | Multi-hop expand | DIO ripple outward | All nodes join progressively |
| 4 | Downward routes | DAO toward root | Root learns paths to all nodes |
| 5 | Steady state | Trickle-controlled DIO | Minimal overhead, self-healing |
21.3 Step-by-Step DODAG Construction
21.4 DODAG Formation: Step-by-Step Visual Guide
The following sequence shows how a DODAG forms step-by-step in a real network. This progressive visualization helps you understand the temporal dynamics of RPL—not just the final topology, but how nodes discover each other and build the routing structure over time.
Understanding how RPL networks self-organize from chaos to hierarchy is crucial for troubleshooting and optimization. This 7-step visual progression shows the complete DODAG construction process with real timing information.
21.4.1 Understanding DAG vs DODAG First
Key Difference: A DAG can have multiple independent trees with separate roots. A DODAG has exactly one root (the gateway/border router) where all paths converge. This single-destination orientation is perfect for IoT’s many-to-one traffic pattern (sensors to cloud).
21.5 The 7-Step DODAG Formation Process
This visual sequence shows how RPL transforms unorganized nodes into a self-healing hierarchical network. Pay attention to the timing and message flow at each step—understanding the process is more important than memorizing the final topology.
21.5.1 Step 1: Initial State - Unorganized Network
Network State:
- One designated root (border router/gateway) at top
- Multiple sensor nodes powered on and ready
- All connections are potential (dotted lines = physical radio range)
- Nodes don’t know their parents or RANK values yet
- Network needs to self-organize from chaos to hierarchy
What nodes know: Their own address, radio is on, listening for RPL messages
What nodes don’t know: Who is the root, what DODAG to join, which neighbor to use as parent
Real-world timing: This is the state at t=0 seconds when you power on a network
21.5.2 Step 2: Root Broadcasts DIO (t = 0-2 seconds)
Root Initiates DODAG (DIO Broadcast)
The root initiates DODAG construction by broadcasting DIO (DODAG Information Object) messages:
- Message content: “I am the root, RANK = 0, DODAG_ID = [IPv6 address], Objective Function = ETX”
- Who receives: All nodes within radio range of root (first-hop neighbors, shown in row 2)
- Propagation: Multicast to all neighbors (efficient broadcast using IPv6 multicast)
- RANK announced: Root advertises RANK = 0
- Analogy: Root announces “I’m here! I’m in charge!” to nearby nodes
First-hop nodes receive DIO:
- Calculate their own RANK:
RANK = 0 + rank_increase(typically 100-256) - Select root as their parent (best option available)
- Store DODAG_ID and configuration
Real-world timing: DIO sent immediately on root startup (t=0-2s), then controlled by trickle timer
Key insight: Only nodes in radio range hear this first DIO. Network expands outward in a “ripple effect” as these nodes forward DIOs in later steps.
21.5.3 Step 3: First-Hop Nodes Join and Propagate (t = 2-5 seconds)
Nodes Join and Send DAO Messages Upward
First-hop nodes (row 2) now participate in DODAG:
- Nodes send DAO (Destination Advertisement Object) messages upward to root:
- Message content: “I am reachable via you, my address is [IPv6]”
- Direction: Child to Parent (upward toward root)
- Purpose: Build downward routes so root can send commands/updates to specific nodes
- Storing mode: Root stores routing table entry: “Node X reachable via this interface”
- Nodes send own DIOs to their neighbors (row 3):
- Advertise their RANK (e.g., RANK = 256)
- Propagate DODAG information outward
- Enable row 3 nodes to join in next step
- Analogy: “Hey parent! You can send things to me” (DAO upward) + “Hey neighbors! Join this DODAG” (DIO outward)
Real-world timing: DAO sent 1-3 seconds after receiving DIO (in Storing mode)
Ripple effect: Network expands outward as each layer joins and forwards DIOs to the next layer
21.5.4 Step 4: DODAG Expands Outward (t = 5-10 seconds)
Deeper Nodes Request and Join
Nodes in rows 3 and 4 (farther from root) now join DODAG:
- Some nodes send DIS (DODAG Information Solicitation):
- Message content: “Hello? Is there a DODAG here? Send me DIO!”
- Purpose: Speed up discovery instead of waiting for periodic DIOs
- When sent: New node joining, or node woke from sleep and missed DIOs
- Response: Neighbors immediately reply with DIO messages
- Nodes receive DIOs from row 2 neighbors:
- Calculate their RANK:
RANK = parent_RANK + rank_increase(e.g., 256 + 200 = 456) - Select parent with best metrics (lowest RANK, good link quality)
- May hear DIOs from multiple potential parents
- Calculate their RANK:
- Nodes establish position in DODAG hierarchy:
- Store parent pointer, RANK value, DODAG_ID
- Determine which “floor” they’re on in the building analogy
Real-world timing: DIS accelerates joining from 10-30s (waiting for DIOs) to 2-5s (proactive request)
Trickle timer interaction: DIS resets trickle timer on recipients, causing them to send DIOs sooner for faster convergence
21.5.5 Step 5: DAO Messages Flow Upward (t = 10-20 seconds)
All Nodes Send DAO to Build Downward Routes
Now that all nodes have joined and selected parents, they advertise their reachability:
- All nodes send DAO upward toward root:
- Leaf nodes send DAO to their parents
- Intermediate nodes aggregate DAOs from children and forward upward
- Storing mode: Each parent stores “Node X reachable via child Y”
- Non-Storing mode: Only root stores complete topology
- DAOs propagate upward hop-by-hop:
- Row 4 to Row 3 to Row 2 to Root
- Each hop adds routing information
- Purpose: Build downward routes so root/parents can send packets to specific nodes
Real-world timing: DAO messages sent every 30-60 seconds (controlled by DAO timer)
Overhead: In 50-node network, ~50 DAO messages total (one per node) over 10-20 seconds
21.5.6 Step 6: Root Confirms Routes (t = 20-30 seconds)
Root Sends DAO-ACK Confirmations
Root (or parents in Storing mode) send DAO-ACK to acknowledge DAO messages:
- Message content: “I received your DAO, I know how to reach you now”
- Direction: Parent to Child (downward, following the DAO path in reverse)
- Purpose:
- Reliability: Confirm routing table updated successfully
- Error detection: If DAO-ACK doesn’t arrive, node retransmits DAO after timeout
- Root authority: “I am the root, I see you and know how to route to you”
- Optional: DAO-ACK can be disabled in low-reliability networks to reduce overhead
Real-world timing: DAO-ACK sent immediately after receiving DAO (1-2 seconds)
Storing vs Non-Storing: In Storing mode, each parent sends DAO-ACK. In Non-Storing mode, only root sends DAO-ACK (since only root stores routes).
21.5.7 Step 7: Steady State - DODAG Complete (t = 30+ seconds)
DODAG Formation Complete! Network is now operational with bidirectional routing:
- Upward routes (sensors to root): Each node knows its parent (parent pointer)
- Leaf nodes have one primary parent (solid line in diagram)
- Intermediate nodes may store backup parents (dotted lines = alternate paths)
- Default route: “Send to parent” (no routing table needed for upward)
- Memory: 4-8 bytes per node (just parent pointer)
- Downward routes (root to sensors): Built via DAO messages
- Storing mode: Each node has routing table for descendants (10-100 KB total)
- Non-Storing mode: Only root has routing table, uses source routing (root needs 10-100 KB, nodes need 0 bytes)
- Network operational: Data can flow:
- Upward: Sensor readings to cloud (many-to-one)
- Downward: Commands/firmware to actuators (one-to-many)
- Point-to-point: Sensor to actuator via common ancestor
Key observation: Leaf nodes (bottom row) have one primary route to root, but network maintains alternate paths (dotted lines) for fault tolerance. If primary parent fails, node switches to backup parent instantly (no global reconfiguration needed).
Maintenance overhead: After convergence, trickle timer backs off to 10-60 minute DIO intervals, using less than 1% of bandwidth
21.6 DODAG Formation Timing Summary
Understanding the temporal progression helps you diagnose network formation issues and optimize convergence time:
| Step | Time | Action | Key Timing Factors |
|---|---|---|---|
| 1. Initial | t=0s | Unorganized network | Power-on, all nodes listening |
| 2. Root DIO | t=0-2s | Root broadcasts first DIO | Immediate on startup |
| 3. First-hop join | t=2-5s | Row 2 joins, sends DAO+DIO | DIO processing + RANK calc |
| 4. Ripple expansion | t=5-10s | Rows 3-4 join via DIS/DIO | DIS accelerates (vs waiting for periodic DIO) |
| 5. DAO upward | t=10-20s | All nodes send DAO to root | DAO timer (30-60s default, can be faster) |
| 6. DAO-ACK confirm | t=20-30s | Root confirms all routes | ACK sent immediately after DAO |
| 7. Steady state | t=30s+ | Network operational | Trickle backs off to 10-60 min DIOs |
Convergence time for 50-node network: Typically 30-120 seconds depending on: - Trickle timer settings: Aggressive (Imin=10ms) vs conservative (Imin=1s) - Network depth: 3-hop network converges faster than 7-hop - DIS usage: Proactive DIS reduces convergence from 120s to 30s - Radio conditions: Packet loss increases retransmissions and delays
Putting Numbers to It
DODAG formation time grows with network depth. For a network with maximum depth \(d\) hops and average DIO interval \(T_{\text{DIO}}\):
\[T_{\text{form}} \approx d \times (T_{\text{DIO}} + T_{\text{RTT}})\]
For example: A 5-hop network with 4-second DIO interval and 50ms RTT:
\[T_{\text{form}} \approx 5 \times (4s + 0.05s) = 20.25s\]
However, with Trickle backoff, later hops may wait longer. Practical measurement for 50 nodes at 4-hop depth with \(I_{\min} = 2s\) shows convergence around 30-45 seconds. Adding DIS (solicitation) cuts this to ~15 seconds by eliminating wait for periodic DIOs at each hop.
Critical applications: Use aggressive timers (10s convergence), accept higher control overhead
Battery-optimized deployments: Tolerate slower formation (2-5 min), minimize DIO/DAO frequency
21.7 Message Flow: Complete Sequence Diagram
This enhanced sequence diagram shows the complete message exchange during DODAG formation, including timing and RANK calculation:
Key insights from message flow:
- RANK increases hop-by-hop: e.g., 0 to 307 to 589 to 1229 (based on cumulative link ETX, not just hop count)
- DIO flows downward (away from root), DAO flows upward (toward root)
- DIS accelerates discovery (Node C doesn’t wait for periodic DIO from B)
- DAO aggregation: Node B’s DAO to A includes both B and C reachability
- Convergence: 30 seconds typical for small network, up to 120s for large/deep networks
21.8 Enhanced Message Flow: Detailed DODAG Building Sequence
This section provides an in-depth walkthrough of exactly what happens during DODAG formation, with specific message contents, timing details, and node state changes. Understanding this level of detail is crucial for troubleshooting and optimizing RPL networks.
21.8.1 Message Types and Their Roles
Before diving into the sequence, let’s understand the four core RPL control messages:
Message Direction Summary:
- DIO: Flows downward (away from root) - Builds DODAG topology
- DIS: Sent to neighbors - Requests DIOs to accelerate joining
- DAO: Flows upward (toward root) - Builds downward routing tables
- DAO-ACK: Flows downward (from root/parents) - Confirms DAO received
21.8.2 Detailed Step-by-Step Message Exchange
Let’s walk through a concrete example with specific node addresses, message contents, and timing. This example shows a 12-node smart building network forming its DODAG.
Network Setup:
- Root: Border router (BR) at address
fd00::1, connected to Internet - Nodes: 11 sensor nodes (addresses
fd00::2throughfd00::c) - Topology: 4-layer hierarchy (root + 3 layers of sensors)
- Radio: IEEE 802.15.4, range ~30m per hop
- Objective Function: ETX (Expected Transmission Count)
Key Observations from Detailed Exchange:
Parent Selection is Metric-Based: Node C receives DIOs from both Node A (RANK 307) and Node B (RANK 384), but chooses Node A because the total path cost (parent RANK + link ETX) is lower (589 vs 896)
DAO Aggregation: When Node C sends its DAO to Node A, Node A aggregates both its own reachability (fd00::2) and Node C’s reachability (fd00::4) into a single DAO forwarded to the root
Bidirectional Confirmation: DAO-ACK messages flow back down the same path, confirming each hop that the route was successfully installed
Timing Dependencies: Each step depends on the previous completing:
- DIOs must arrive before nodes can calculate RANK
- RANK must be calculated before nodes send DAO
- DAO must arrive before DAO-ACK can be sent
Trickle Timer Behavior: After initial formation (~30s), DIO interval increases from 10s to 30s to 1min to 10min to minimize overhead once topology is stable
21.9 Understanding RANK Calculation in Formation
As the DODAG forms, each node calculates its RANK based on the Objective Function (OF):
Example with ETX (Expected Transmission Count) metric:
Root: RANK = 0
First-hop node (good link, ETX = 1.2):
RANK = 0 + (ETX x 256) = 0 + 307 = 307
Second-hop node (good link from first-hop, ETX = 1.1):
RANK = 307 + (1.1 x 256) = 307 + 282 = 589
Leaf node (poor link from second-hop, ETX = 2.5):
RANK = 589 + (2.5 x 256) = 589 + 640 = 1229RANK increases as you move away from root. Nodes always forward upward to lower RANK (toward root), preventing loops. The rate of increase depends on link quality—poor links cause larger RANK jumps, discouraging routes through unreliable paths.
21.9.1 Interactive: Multi-Hop RANK Tracer
Trace cumulative RANK across up to three hops with configurable ETX values:
Objective Functions:
- OF0 (RFC 6552): Hop count or ETX (simple, widely supported)
- MRHOF (RFC 6719): Minimum Rank with Hysteresis (avoids parent flapping)
- Custom OFs: Energy-aware, latency-optimized, security-enhanced (application-specific)
21.10 Complete DODAG Formation Overview
Summary of DODAG Formation:
This comprehensive view shows the complete temporal evolution of RPL DODAG construction:
- Initial chaos - Unorganized nodes with potential connections
- Root broadcast - DIO messages establish DODAG identity (RANK 0)
- Upward advertisement - DAO messages build downward routing paths
- Position discovery - DIS messages accelerate node integration
- Route confirmation - DAO-ACK validates routing table entries
- Final hierarchy - Operational tree with fault-tolerant alternate paths
Key pedagogical insight: Understanding the process (how DODAG forms over time) is more important than memorizing the final topology. When troubleshooting RPL networks, you’ll diagnose issues by observing DIO/DAO/DIS message flows during formation, not by looking at static routing tables.
Real-world timing: In a 50-node sensor network, complete DODAG formation typically takes 30-120 seconds depending on trickle timer settings, radio conditions, and network depth (max hops from root). Critical applications use aggressive timers (10s convergence), while battery-optimized deployments tolerate slower formation (2-5 min) for reduced control overhead.
21.11 Hands-On: RPL DODAG Simulation
The DODAG construction process and objective function concepts become much clearer when you simulate them in code. The Python script below builds a small RPL network, calculates RANK values using both OF0 (hop count) and MRHOF (ETX), and shows how different objective functions produce different routing trees.
21.11.1 Python: Build a DODAG with OF0 vs MRHOF
This simulation creates a 10-node network and demonstrates how the choice of objective function affects parent selection and path quality.
# --- RPL DODAG Construction Simulator ---
# Demonstrates: RANK calculation, parent selection, OF0 vs MRHOF
import random
class RPLNode:
"""A node in an RPL DODAG."""
def __init__(self, node_id, position):
self.id = node_id
self.position = position # (x, y) coordinates
self.rank = float('inf')
self.parent = None
self.children = []
def __repr__(self):
parent_id = self.parent.id if self.parent else "None"
return f"Node {self.id}: rank={self.rank}, parent={parent_id}"
def distance(a, b):
"""Euclidean distance between two nodes."""
return ((a.position[0] - b.position[0])**2 +
(a.position[1] - b.position[1])**2) ** 0.5
def etx_from_distance(dist, radio_range=100):
"""
Estimate ETX (Expected Transmission Count) from distance.
Close nodes: ETX ~1.0 (perfect link). Far nodes: ETX >3.0 (lossy link).
Beyond radio range: ETX = infinity (unreachable).
"""
if dist > radio_range:
return float('inf')
# Model: ETX increases with distance (simplified log-distance path loss)
prr = max(0.1, 1.0 - (dist / radio_range) ** 2) # Packet Reception Rate
return 1.0 / prr # ETX = 1/PRR
def build_dodag(nodes, root_id, objective_function="MRHOF", radio_range=100):
"""
Simulate RPL DODAG construction using DIO propagation.
Args:
nodes: List of RPLNode objects
root_id: ID of the root node (border router)
objective_function: "OF0" (hop count) or "MRHOF" (ETX-based)
radio_range: Maximum communication range in meters
"""
root = nodes[root_id]
root.rank = 0
root.parent = None
# BFS-like propagation simulating DIO messages rippling outward
queue = [root]
visited = {root.id}
while queue:
current = queue.pop(0)
# Find neighbors within radio range (simulate DIO reception)
for node in nodes:
if node.id in visited:
continue
dist = distance(current, node)
if dist > radio_range:
continue
# Calculate candidate RANK based on objective function
etx = etx_from_distance(dist, radio_range)
if objective_function == "OF0":
# OF0: RANK = parent_rank + 256 (fixed increment per hop)
candidate_rank = current.rank + 256
elif objective_function == "MRHOF":
# MRHOF: RANK = parent_rank + ETX * 256 (link-quality weighted)
candidate_rank = current.rank + int(etx * 256)
else:
raise ValueError(f"Unknown OF: {objective_function}")
# Accept this parent if it offers a better (lower) RANK
if candidate_rank < node.rank:
# Detach from old parent
if node.parent:
node.parent.children.remove(node)
# Attach to new parent
node.rank = candidate_rank
node.parent = current
current.children.append(node)
if node.id not in visited:
visited.add(node.id)
queue.append(node)
return root
def print_dodag(root, indent=0):
"""Print DODAG tree structure."""
prefix = " " * indent + ("+-" if indent > 0 else "")
etx_info = ""
if root.parent:
dist = distance(root, root.parent)
etx = etx_from_distance(dist)
etx_info = f" (link ETX={etx:.1f})"
print(f"{prefix}Node {root.id} [RANK={root.rank}]{etx_info}")
for child in root.children:
print_dodag(child, indent + 1)
def trace_path(node):
"""Trace upward path from a node to the root."""
path = []
current = node
total_hops = 0
while current:
path.append(current.id)
current = current.parent
total_hops += 1
return path, total_hops - 1
# --- Create a 10-node smart building network ---
random.seed(42) # Reproducible results
positions = [
(50, 0), # Node 0: Root (border router at entrance)
(20, 30), # Node 1: Hallway sensor
(80, 30), # Node 2: Hallway sensor
(10, 60), # Node 3: Office A
(40, 60), # Node 4: Conference room
(70, 60), # Node 5: Office B
(90, 60), # Node 6: Server room
(25, 90), # Node 7: Break room (far)
(60, 90), # Node 8: Lab (far)
(85, 95), # Node 9: Storage (farthest)
]
print("=== RPL DODAG Construction: OF0 vs MRHOF ===\n")
print("Network: 10-node smart building, radio range = 60m\n")
for of_name in ["OF0", "MRHOF"]:
# Fresh nodes for each run
nodes = [RPLNode(i, pos) for i, pos in enumerate(positions)]
root = build_dodag(nodes, root_id=0, objective_function=of_name, radio_range=60)
print(f"--- {of_name} (Objective Function) ---")
print_dodag(root)
# Trace path from farthest node to root
farthest = nodes[9]
path, hops = trace_path(farthest)
print(f"\nPath from Node 9 (storage) to Root: {' -> '.join(map(str, path))}")
print(f"Hops: {hops}, Final RANK: {farthest.rank}")
print()
print("Key differences:")
print(" OF0: Equal rank increment per hop (256). Minimizes hop count.")
print(" Good for: low latency, simple implementation")
print(" MRHOF: Rank increment weighted by link ETX. Avoids lossy links.")
print(" Good for: reliable delivery, reducing retransmissions")
print(" A node with ETX=2.5 (lossy) gets RANK penalty of 640 with MRHOF")
print(" but only 256 with OF0 -- so MRHOF routes around bad links.")What to observe: With OF0, all single-hop neighbors get the same RANK (256) regardless of link quality. A node two hops away always has RANK 512. With MRHOF, a nearby node with a clean link (ETX=1.1) gets RANK 282, while a node with a lossy link (ETX=2.5) gets RANK 640 – even if they are the same number of hops away. This means MRHOF routes traffic through reliable links, while OF0 may route through unreliable links just because they are fewer hops. This directly demonstrates why MRHOF is preferred for most IoT deployments, as described in the Objective Functions section above.
Worked Example: Calculating RANK Values for a 6-Node Smart Lighting Network
A smart building has 6 LoRaWAN lights forming an RPL DODAG using MRHOF (Minimum Rank with Hysteresis Objective Function) with ETX (Expected Transmission Count) metric. Calculate RANK for each node and determine parent selection.
Network Topology (Radio Links with ETX):
Root (Border Router)
├─ Node A (ETX=1.2 from Root)
├─ Node B (ETX=1.8 from Root)
└─ Node C (ETX=2.5 from Root)
Node A can hear:
└─ Node D (ETX=1.5 from A)
Node B can hear:
├─ Node D (ETX=2.0 from B)
└─ Node E (ETX=1.3 from B)
Node C can hear:
└─ Node E (ETX=3.0 from C)RANK Calculation Formula (MRHOF with ETX):
RANK = Parent_RANK + (ETX × 256)
Where:
- ETX = Expected Transmission Count (1.0 = perfect link, >3.0 = unreliable)
- 256 = RANK_FACTOR (scaling constant to preserve precision)
- Root RANK = 0Step 1: First-Hop Nodes (A, B, C select Root as parent)
Node A:
Parent: Root (RANK = 0)
Link ETX: 1.2
RANK_A = 0 + (1.2 × 256) = 307Node B:
Parent: Root (RANK = 0)
Link ETX: 1.8
RANK_B = 0 + (1.8 × 256) = 461Node C:
Parent: Root (RANK = 0)
Link ETX: 2.5
RANK_C = 0 + (2.5 × 256) = 640Step 2: Second-Hop Node D (chooses between A or B)
Option 1: Node D selects A as parent
RANK_D (via A) = RANK_A + (ETX_D-A × 256)
= 307 + (1.5 × 256)
= 307 + 384
= 691Option 2: Node D selects B as parent
RANK_D (via B) = RANK_B + (ETX_D-B × 256)
= 461 + (2.0 × 256)
= 461 + 512
= 973Decision: Node D selects Node A as parent (RANK 691 < 973). Even though B is closer to Root by hop count, the better link quality through A results in lower total RANK.
Step 3: Second-Hop Node E (chooses between B or C)
Option 1: Node E selects B as parent
RANK_E (via B) = RANK_B + (ETX_E-B × 256)
= 461 + (1.3 × 256)
= 461 + 333
= 794Option 2: Node E selects C as parent
RANK_E (via C) = RANK_C + (ETX_E-C × 256)
= 640 + (3.0 × 256)
= 640 + 768
= 1408Decision: Node E selects Node B as parent (RANK 794 < 1408).
Final DODAG Hierarchy:
Root (RANK=0)
├─ Node A (RANK=307, ETX=1.2)
│ └─ Node D (RANK=691, ETX=1.5 from A)
├─ Node B (RANK=461, ETX=1.8)
│ └─ Node E (RANK=794, ETX=1.3 from B)
└─ Node C (RANK=640, ETX=2.5) [no children - worst link to Root]Key Insight: Node D is 2 hops from Root via A (total RANK 691), but if it had chosen the 2-hop path via B, RANK would be 973 (41% higher). MRHOF optimizes for link quality, not hop count, which is why Node D avoided the lossy B→D link (ETX=2.0) in favor of the better A→D link (ETX=1.5).
Decision Framework: Choosing RPL Objective Function (OF0 vs MRHOF vs Custom)
You’re deploying 500 environmental sensors in a forest. Which objective function should your DODAG use?
| Criterion | OF0 (RFC 6552) | MRHOF (RFC 6719) | Custom Energy-Aware | Best For |
|---|---|---|---|---|
| Metric | Hop count | ETX (link quality) | Battery % + ETX | Network optimization goal |
| RANK Calculation | Fixed increment (256 per hop) | ETX × 256 (variable) | (ETX × 128) + (100 - Battery%) × 128 | Path selection |
| Parent Flapping | Low (stable) | Medium (MRHOF adds hysteresis) | High (battery changes) | Network stability |
| Memory | Minimal (~1KB) | Low (~2KB for ETX tracking) | Medium (~3KB for battery + ETX) | Constrained devices |
| Battery Optimization | None | Indirect (reliable links) | Direct (avoids low-battery nodes) | Battery-powered sensors |
| Implementation Complexity | Simple (reference code: 200 lines) | Moderate (reference: 500 lines) | High (custom: 800+ lines) | Development time |
Decision Criteria:
Use OF0 (Hop Count) if:
- All links are reliable (wired/short-range wireless)
- Network topology is simple (star, tree)
- Devices have minimal memory (4KB RAM total)
- Example: Home automation (5-10 devices, Wi-Fi mesh)
- Benefit: Simplest implementation, lowest memory
- Cost: Doesn’t adapt to link quality changes
Use MRHOF (ETX-based) if:
- Wireless network with variable link quality
- Need to route around interference/obstacles
- Moderate to high battery capacity (rechargeable/solar)
- Example: Smart agriculture (100-500 sensors, outdoor)
- Benefit: Best general-purpose choice (routes around bad links automatically)
- Cost: Requires ETX measurement (adds 2KB memory)
Use Custom Energy-Aware OF if:
- Battery life is critical constraint
- Non-rechargeable batteries (10-year target)
- Traffic is bursty (some nodes relay more data)
- Example: Remote environmental monitoring (1000+ sensors, battery-only)
- Benefit: Extends network lifetime by load-balancing across nodes
- Cost: Complex implementation, potential parent flapping
Recommended for Most IoT Deployments:
MRHOF with ETX (used in 80%+ of production RPL networks): - Automatically avoids lossy wireless links (ETX >2.5) - Hysteresis prevents constant parent switching - Well-tested reference implementations available (Contiki-NG, RIOT OS) - Memory overhead acceptable for ESP32/nRF52-class devices
Custom OF only if:
- You have specific optimization needs (e.g., thermal management, security zones)
- You can afford extensive testing (custom OFs often have bugs in edge cases)
- Battery life simulation shows >30% improvement vs MRHOF
Common Mistake: Assuming DIO Message Frequency Equals Network Overhead
The Error: A developer reads that RPL nodes send DIO (DODAG Information Object) messages to advertise the network and calculates overhead as: “100 nodes × DIO every 60 seconds × 50 bytes = 5KB/min = constant overhead.” They conclude RPL is too chatty for battery-powered networks.
Why It’s Wrong: RPL uses the Trickle algorithm to adapt DIO transmission rate based on network stability. DIO frequency is not constant—it exponentially backs off when the network is stable and only increases during topology changes.
Trickle Algorithm Behavior:
Initial formation (first 2 minutes):
- Imin = 10ms, Imax = 60 seconds
- DIO sent every 10ms → 20ms → 40ms → 80ms (doubling each interval)
- High frequency enables fast DODAG construction (30-60 seconds)
- Energy: ~5 mAh during formation
Steady state (after network stabilizes):
- Interval reaches Imax = 60 minutes (3600 seconds)
- DIO sent once per hour per node
- 100 nodes × 1 DIO/hour × 50 bytes = 5 KB/hour (not per minute!)
- Energy: ~0.05 mAh/hour (100× lower than formation)
Topology change (link failure):
- Interval resets to Imin = 10ms
- Rapid DIOs repair affected sub-tree (30 seconds)
- Interval backs off again to ImaxReal-World Measurement (from Contiki-NG deployment study, 2020):
A 200-node smart building network measured over 30 days:
Formation phase (day 1):
- DIO transmissions: 15,000 messages (all nodes finding parents)
- Energy: 3.2 mAh per node
Steady state (days 2-30):
- DIO transmissions: 720 messages per node (1 per hour × 24 hours × 30 days)
- Energy: 0.4 mAh per node (98% reduction vs. formation)
3 Link failures (days 7, 15, 22):
- DIO bursts: ~500 messages each event (localized repair)
- Energy: 0.3 mAh per event
Total 30-day overhead: 3.2 + 0.4 + 0.9 = 4.5 mAh
vs. Developer's assumption: 5 KB/min × 60 min × 24 hr × 30 days = 216,000 KBWhy This Matters:
The developer’s assumption (constant DIO rate) would predict 48× higher energy consumption than reality. This misconception has led developers to incorrectly reject RPL in favor of static routing, sacrificing fault tolerance for minimal energy savings.
How to Avoid:
- Understand Trickle: DIOs are frequent only during formation and repair
- Measure actual traffic: Use Wireshark on a test network for 24-48 hours
- Configure Imax appropriately: For ultra-low-power networks, set Imax = 2-4 hours (default 1 hour)
- Don’t fear DIO overhead: In stable networks, RPL control traffic is <0.1% of total bandwidth
Key Concepts
- DODAG Root: The sink node at the top of the RPL DODAG tree, typically a border router; all upward traffic flows toward this node.
- DIO Message Propagation: The process by which DODAG membership information spreads outward from the root through DIO broadcasts; each receiving node joins and begins broadcasting.
- RANK-based Loop Avoidance: RPL’s primary loop prevention mechanism: nodes only forward upward toward lower-RANK nodes, making loops structurally impossible in the upward direction.
- DODAG Stability: A state where the network topology has settled and Trickle timers have slowed DIO transmission; indicates routing has converged.
- Floating DODAG: A DODAG with no fixed root, used when connectivity to the border router is lost; nodes maintain local routing but have no upstream IP connectivity.
Common Pitfalls
1. Not Waiting for Full DODAG Convergence Before Testing
DODAG construction takes time — especially in deep, multi-hop networks. Testing application connectivity before full DODAG convergence results in packets being dropped by nodes that haven’t yet joined. Wait for convergence indicators (stable DAO flow, consistent routing tables) before running application tests.
2. Assuming DODAG Construction Completes in Order
DODAG construction is not strictly level-by-level — a node 4 hops away may join before a node 2 hops away if link quality differences cause DIO propagation delays. Design applications to handle partial DODAG availability gracefully.
3. Not Configuring Multiple DODAGs for Large Networks
A single DODAG with a single root creates a bottleneck at the root for very large networks. Consider deploying multiple DODAGs with multiple border routers and configuring RPL instance IDs to distribute load.
21.12 Summary
This chapter covered the complete DODAG construction process:
- 5-Phase Algorithm: Root initialization, first-hop join, multi-hop expansion, DAO propagation, and steady state
- Message Types: DIO (advertises DODAG), DIS (requests information), DAO (builds downward routes), DAO-ACK (confirms routes)
- 7-Step Formation: Progressive network self-organization from chaos to hierarchy with specific timing at each step
- RANK Calculation: Objective function-based metric that increases with distance from root and accounts for link quality
- Convergence Timing: 30-120 seconds typical for 50-node network, depending on trickle timer and network depth
21.13 Knowledge Check
21.14 Concept Relationships
DODAG construction is central to RPL operation and connects to many concepts:
Foundation:
- RPL Introduction - Why DODAG topology prevents loops and conserves energy
- Routing Fundamentals - Distance-vector routing principles
Uses:
- RANK calculation - Position in hierarchy (lower = closer to root)
- DIO messages - Advertise DODAG information outward from root
- DAO messages - Build downward routing tables toward leaves
- DIS messages - Accelerate discovery for new nodes
Controlled By:
- RPL Trickle Algorithm - Adaptive timing for DIO transmissions
- Objective Functions (OF0, MRHOF) - Determine RANK calculation formula
Enables:
- Storing vs Non-Storing Modes - Different routing table strategies
- Upward routing - Default routes via parent pointers
- Downward routing - DAO-built routing tables
Demonstrated In:
- RPL DODAG Visual Guide - Step-by-step diagrams
- RPL Worked Example - 10-node network calculations
21.15 See Also
RFC Specifications:
- RFC 6550 Section 3: “DODAG Construction and Maintenance” - Official algorithm
- RFC 6550 Section 6: “Upward Routes” - Parent selection and default routing
- RFC 6550 Section 9: “Downward Routes” - DAO message format and processing
- RFC 6206: “Trickle Algorithm” - DIO timing control
Related Chapters:
- RPL DODAG Message Flow - Detailed message exchanges
- RPL DODAG Trickle - Energy-efficient maintenance
- RPL DODAG Visual Guide - 7-step formation timeline
Implementation Guides:
- Contiki-NG RPL Tutorial - Code walkthrough of DODAG formation
- RIOT OS RPL Documentation - Alternative implementation perspective
- Zolertia RE-Mote Platform Guide - RPL on real hardware
Academic Resources:
- Vasseur & Dunkels “Interconnecting Smart Objects with IP” Ch. 5 - DODAG formation details
- Tripathi et al. “Performance Evaluation of RPL” - Empirical convergence analysis
- Korte et al. “RPL: Routing for the Internet of Things” - Comprehensive protocol overview
Debugging Tools:
- Wireshark RPL Dissector - Capture DIO/DAO/DIS messages
- Contiki Cooja Simulator - Visualize DODAG formation in real-time
- RPL Border Router Debug Console - Monitor message timing
Comparison Topics:
- Thread Network Formation - Similar but different approach
- Zigbee Tree Formation - Alternative hierarchical routing
- AODV Route Discovery - On-demand vs proactive (RPL)
21.16 What’s Next
| Next | Chapter |
|---|---|
| Calculate | RPL Worked Example |
| Visualize | RPL DODAG Visual Guide |
| Energy efficiency | RPL Trickle Algorithm |
| Routing modes | RPL Trickle and Modes |