95 Ad Hoc Routing: Reactive (DSR)

In 60 Seconds

DSR discovers routes on-demand by flooding Route Requests and caching replies, making it ideal for sparse IoT networks where nodes transmit infrequently. Cache timeout is the single most critical tuning parameter – too short wastes energy on repeated discoveries, too long causes packet loss from stale routes.

Key Concepts

Reactive (On-Demand) Routing: Routes discovered only when a data source needs to send; avoids overhead for unused routes
DSR Route Discovery: RREQ broadcast + RREP unicast cycle; discovers route to destination when no cached route is available
Route Cache Usage: Before initiating discovery, DSR checks cache; cached route immediately available without broadcast
Source Route Header: DSR embeds complete path in packet header; intermediate nodes forward based on header, not routing table
Route Maintenance: DSR detection and recovery from broken links via RERR messages and route rediscovery
Multiple Routes: DSR can store and use multiple routes to the same destination; automatically switches if primary route fails
Passive ACK: Overhearing a packet forwarded by the next hop serves as confirmation the hop is operational
DSR Congestion: Heavy route discovery traffic during initial network formation or after mass topology change; backoff required

95.1 Learning Objectives

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

Explain DSR Protocol Mechanics: Describe how Dynamic Source Routing discovers paths on-demand using RREQ flooding and RREP unicast
Compare Reactive vs Proactive Routing: Evaluate trade-offs between DSR and DSDV in terms of overhead, latency, and energy efficiency
Apply Source Routing Concepts: Analyze how complete paths are embedded in packet headers and how route caching reduces discovery overhead
Design for IoT Scenarios: Select DSR when communication patterns match its strengths (sparse, battery-constrained networks)

Minimum Viable Understanding

DSR discovers routes only when needed: Instead of maintaining routing tables continuously (like DSDV), DSR floods a Route Request (RREQ) through the network and receives a Route Reply (RREP) with the complete path – this makes it ideal for battery-powered IoT devices that transmit infrequently.
Source routing embeds the full path in every packet: Unlike hop-by-hop routing where each node decides independently, DSR places the entire route (e.g., A->B->D->F) in the packet header, so intermediate nodes simply forward to the next hop in the list.
Route caching is both DSR’s greatest strength and weakness: Nodes overhear and cache routes from nearby traffic to avoid repeated flooding, but cached routes can become stale when nodes move – making cache timeout strategy the single most critical DSR tuning parameter.

Sensor Squad: The “Ask for Directions” Adventure!

Sammy the Sensor held up a tiny map. “Okay squad, today we’re learning about DSR – Dynamic Source Routing. It’s like asking for directions instead of keeping a giant map of everything!”

Lila the LED blinked excitedly. “So instead of memorizing every street like we did with DSDV, we just ask when we need to go somewhere?”

“Exactly!” said Sammy. “Imagine you want to send a letter to your friend across town, but you don’t know the way. Here’s what you do:”

Max the Microcontroller jumped in: “Step 1 – you shout really loud: ‘Does anyone know how to get to Lila’s house?’ Everyone who hears you adds their name to the question and passes it along. So it goes: ‘Sammy asked -> Max heard it -> Bella heard it -> Lila received it!’”

Bella the Battery smiled. “And when I finally get the question, I know the whole path! So I send back: ‘Tell Sammy the route is: Sammy -> Max -> Bella -> Lila!’ That’s the Route Reply!”

“The best part,” said Sammy, “is that I write the whole route on my letter like an address label: Via Max, then Bella, then Lila. Max doesn’t need to think – he just reads the label and passes it to Bella!”

Lila asked, “But what if Bella moves to a new house?”

Max frowned. “That’s the tricky part – the stale cache problem. If I remembered the old directions and tried to use them, the letter would get lost! I’d have to shout and ask for new directions all over again.”

Bella added her favorite part: “And the reason I love DSR is that when nobody is sending letters, we use ZERO energy on directions. With DSDV, we had to keep updating our maps even when nobody was mailing anything. For a battery like me, DSR is a dream!”

Key takeaway: DSR is like asking for directions only when you need to travel – saves energy when you’re staying home, but takes a moment to find the route when you do need to go somewhere!

For Beginners: What Is Reactive Routing?

The Core Idea: Reactive routing means “find a route only when you need one.” Think of it like using a GPS app – you only look up directions when you’re about to drive somewhere, not every minute of every day.

Why Does This Matter for IoT?

Many IoT sensors only send data occasionally – maybe a soil moisture sensor reports once per hour. Keeping a full routing table updated continuously (like DSDV does) wastes precious battery life. DSR says: “Don’t bother with routes until you actually have data to send.”

The Three Key Messages in DSR:

Message	What It Does	Everyday Analogy
RREQ (Route Request)	“Does anyone know how to reach Node F?” – broadcast to everyone	Shouting “How do I get to the library?” in a crowded room
RREP (Route Reply)	“I know! The path is A->B->D->F” – sent back to the asker	Someone answers “Go left, right, then straight”
RERR (Route Error)	“The road between B and D is broken!” – warning to the source	A friend calls saying “That bridge is closed, find another way”

Source Routing = Address Label on a Package:

The unique thing about DSR is source routing: the sender writes the complete route on every packet, like writing delivery instructions on a package: “Deliver via Warehouse B, then Hub D, then Customer F.” Each stop just reads the label and forwards.

When to Use DSR:

Sensors that transmit rarely (once per minute or less)
Battery-powered devices where energy conservation is critical
Networks where not every node needs to talk to every other node

When NOT to Use DSR:

Real-time applications (the route discovery delay is too long)
Dense, frequent traffic (flooding RREQ for every new destination is expensive)

95.2 Overview

Dynamic Source Routing (DSR) is a reactive (on-demand) protocol where routes are discovered only when needed for active communication. Unlike proactive protocols that maintain routes continuously, DSR eliminates periodic overhead by discovering routes on-demand through network-wide flooding.

Overview diagram of DSR reactive routing protocol showing three phases: Route Discovery with RREQ flood and RREP reply, Data Transmission with source-routed packets, and Route Maintenance with RERR error handling, connected in a cycle

This topic is covered across three focused chapters:

95.3 Chapter Guide

95.3.1 DSR Fundamentals and Route Discovery

Core DSR concepts and the route discovery process

DSR protocol overview and unique characteristics
Route Request (RREQ) flooding mechanism
Route Reply (RREP) options and path selection
Source routing packet format
Complete route discovery example with sequence diagrams

Best for: Understanding how DSR works at the protocol level

95.3.2 DSR Caching and Route Maintenance

Route caching strategies and error handling

Route caching through overhearing
Cache management strategies (timeout, LRU, adaptive)
The stale cache problem in mobile networks
Route Error (RERR) mechanism
DSR advantages, disadvantages, and optimal use cases
Optimization techniques for IoT deployments

Best for: Understanding cache trade-offs and when DSR is appropriate

95.3.3 DSR Worked Examples and Practice

Practical calculations and real-world scenarios

Route discovery latency in emergency response networks
Cache timeout optimization for mobile asset tracking
Energy trade-off analysis for wildlife monitoring
Route error recovery in disaster response
Practice problems with detailed solutions

Best for: Applying DSR concepts to real-world IoT deployments

95.4 DSR Route Discovery Process

The following diagram illustrates how DSR discovers a route from Node A to Node F through intermediate nodes:

Sequence diagram showing DSR route discovery process where Node A broadcasts RREQ to neighbors B and C, B forwards to D, D forwards to F which is the destination, F sends RREP back through D and B to A with the complete path A-B-D-F, and then A sends source-routed data along the discovered path

95.5 DSR vs DSDV: Reactive vs Proactive

Understanding when to use reactive (DSR) versus proactive (DSDV) routing is a critical design decision for IoT networks:

Comparison diagram showing DSR reactive routing on the left with on-demand discovery, zero idle overhead, and discovery delay, versus DSDV proactive routing on the right with continuous table updates, immediate route availability, and constant energy cost, with a decision guide in the center indicating DSR is best for sparse traffic and DSDV for frequent traffic

95.6 Route Caching and the Stale Cache Problem

Route caching is DSR’s most powerful optimization – but also its greatest vulnerability:

Flowchart showing DSR route caching decision process: when a node needs to send data it checks its cache first, on cache hit it uses the cached route, on cache miss it initiates RREQ discovery, and during transmission if a link fails a RERR is generated which invalidates the cache entry and triggers re-discovery, with cache management strategies shown including timeout, LRU, and adaptive timeout

95.7 Learning Path

Recommended Sequence

First: Read DSR Fundamentals to understand the protocol mechanics
Then: Study Caching and Maintenance for operational considerations
Finally: Work through Examples and Practice to apply your knowledge

Prerequisites: Before starting, ensure you’ve covered: - Ad Hoc Routing: Proactive (DSDV) - for contrast with table-driven approach - Multi-Hop Fundamentals - for path discovery concepts

95.8 Quick Reference

Aspect	DSR Characteristic
Type	Reactive (on-demand)
Route Storage	Source routing (complete path in packet header)
Discovery	RREQ flood, RREP unicast
Maintenance	RERR on link failure
Overhead When Idle	Zero (no periodic updates)
Discovery Latency	Network diameter x per-hop delay
Best For	Sparse communication, battery-powered sensors
Avoid For	Real-time applications, dense traffic

Putting Numbers to It

For a 10-node network with 4-hop diameter and 10ms per-hop delay: Discovery latency = \(4 \text{ hops} \times 10 \text{ ms/hop} = 40\) ms for RREQ to reach destination + \(4 \times 10 = 40\) ms for RREP to return = 80ms total. Worked example: If packets arrive every 2 seconds, first packet waits 80ms (discovery), subsequent 99 packets use cached route (0ms discovery). Average latency = \(\frac{80 + 0 \times 99}{100} = 0.8\) ms/packet. Compare to DSDV: 0ms discovery always, but continuous 50-byte updates every 60s = \(10 \text{ nodes} \times 50B \times 1440/day = 720\) KB/day overhead. DSR’s on-demand approach wins for sparse traffic.

Show code

viewof dsr_network_nodes = Inputs.range([5, 200], {value: 10, step: 5, label: "Network nodes"})
viewof dsr_path_hops = Inputs.range([1, 10], {value: 4, step: 1, label: "Path length (hops)"})
viewof dsr_per_hop_ms = Inputs.range([1, 50], {value: 10, step: 1, label: "Per-hop delay (ms)"})
viewof dsr_pkts_per_day = Inputs.range([1, 500], {value: 12, step: 1, label: "Packets per day per node"})

Show code

{
  const rreq_discovery = dsr_network_nodes; // RREQ reaches all nodes
  const rrep_cost = dsr_path_hops;
  const data_cost = dsr_path_hops;
  const discovery_cost = rreq_discovery + rrep_cost + data_cost;
  const data_only_cost = data_cost;
  const discovery_latency_ms = dsr_path_hops * dsr_per_hop_ms * 2; // RREQ + RREP

  // Assume cache hit after first discovery (~95% for stationary)
  const dsr_avg = ((discovery_cost + (dsr_pkts_per_day - 1) * data_only_cost) / dsr_pkts_per_day).toFixed(1);
  const dsr_total = (dsr_network_nodes * dsr_pkts_per_day * parseFloat(dsr_avg)).toFixed(0);

  // DSDV: each node broadcasts full table every 60s
  const dsdv_daily = (dsr_network_nodes * 1440).toFixed(0); // 1 update/min

  return html`<div style="background:#f0f7ff;padding:12px;border-radius:6px;font-family:monospace">
    <b>DSR route discovery latency:</b> ${dsr_path_hops} hops × ${dsr_per_hop_ms}ms × 2 (RREQ+RREP) = <b>${discovery_latency_ms}ms</b><br>
    <b>DSR cost per route discovery:</b> ${rreq_discovery} (RREQ flood) + ${rrep_cost} (RREP) + ${data_cost} (data) = <b>${discovery_cost} packets</b><br>
    <b>DSR avg packets/report:</b> ~${dsr_avg} packets (95% cache hit rate)<br>
    <b>DSR daily total:</b> ${dsr_network_nodes} nodes × ${dsr_pkts_per_day} rpts × ${dsr_avg} = <b>${dsr_total} packets/day</b><br>
    <b>DSDV daily overhead:</b> ${dsr_network_nodes} nodes × 1440 updates = <b>${dsdv_daily} packets/day</b><br>
    <span style="color:${parseInt(dsr_total) < parseInt(dsdv_daily) ? '#16a085' : '#c0392b'}">
      ${parseInt(dsr_total) < parseInt(dsdv_daily) 
        ? 'DSR uses ' + (parseInt(dsdv_daily)/parseInt(dsr_total)).toFixed(1) + 'x LESS overhead than DSDV — use DSR'
        : 'DSDV overhead lower — consider DSDV for this traffic pattern'}
    </span>
  </div>`;
}

95.9 Common Pitfalls

Common DSR Pitfalls and Misconceptions

1. Assuming DSR is always more efficient than DSDV DSR eliminates idle overhead, but route discovery floods the entire network. If a node discovers routes frequently (e.g., many unique destinations or rapid mobility invalidating caches), accumulated RREQ floods can exceed DSDV’s periodic updates. Rule of thumb: DSR wins when duty cycle < 1%; DSDV wins when duty cycle > 10%.

2. Setting cache timeouts too long in mobile networks Long cache timeouts (e.g., 5+ minutes) in networks with mobile nodes lead to stale routes. Packets are sent along broken paths, generating RERR overhead and delivery delays. Fix: Use adaptive timeouts based on observed mobility – short timeouts (30-60s) for mobile nodes, longer (5-10 min) for stationary nodes.

3. Ignoring the header overhead of source routing DSR embeds the complete route in every packet header. For a 10-hop path, this adds 10 x 4 = 40 bytes per packet. On constrained IoT networks with small MTUs (e.g., IEEE 802.15.4 with 127-byte frames), this overhead can consume 30%+ of available payload. Mitigation: DSR is best suited for networks with short path lengths (< 5 hops).

4. Not leveraging promiscuous mode for caching Many DSR implementations miss the opportunity to cache routes overheard in promiscuous mode. A node overhearing traffic between other nodes can extract and cache the source route – dramatically reducing future discovery floods. Always enable promiscuous caching in IoT deployments.

5. Using DSR for real-time or time-critical applications The initial route discovery delay (network diameter x per-hop delay) can be hundreds of milliseconds to seconds in large networks. Applications requiring guaranteed latency bounds (alarms, actuator control) should use proactive routing or pre-established routes.

95.10 Worked Example: Smart Agriculture Sensor Network

Worked Example: DSR for a Soil Monitoring Deployment

Scenario: A smart agriculture farm deploys 50 battery-powered soil moisture sensors across a 500m x 500m field. Each sensor reports to a gateway once every 2 hours. The sensors are stationary (mounted on stakes). Average path length to the gateway is 4 hops. Each hop takes ~10ms for transmission.

Question: Should this deployment use DSR or DSDV? Calculate the overhead for each protocol.

Step 1: Calculate DSR overhead per reporting cycle

Each sensor needs to discover a route (if not cached) before sending data:

RREQ flood: In a 50-node network, an RREQ reaches all nodes = ~50 packets (each node rebroadcasts once)
RREP: 4-hop unicast = 4 packets
Data transmission: 4-hop source-routed = 4 packets
Total per report (cache miss): 50 + 4 + 4 = 58 packets
Total per report (cache hit): 0 + 0 + 4 = 4 packets

Since sensors are stationary, cache hit rate after first discovery is approximately 95%:

First report: 58 packets
Subsequent reports: 4 packets each
Average over 12 reports/day: (58 + 11 x 4) / 12 = 8.5 packets/report
Network total: 50 sensors x 12 reports x 8.5 avg = 5,100 packets/day

Step 2: Calculate DSDV overhead per day

DSDV sends periodic updates regardless of data traffic:

Full table dump: Every 60 seconds, each node broadcasts its routing table
Table size: 50 entries per node
Update packets per node per minute: ~1 packet (compressed incremental updates)
Network total: 50 nodes x 1 update/min x 1,440 min/day = 72,000 packets/day

Step 3: Compare

Metric	DSR	DSDV
Daily routing overhead	5,100 packets	72,000 packets
Energy ratio	1x (baseline)	14x more energy
Route availability	~40ms discovery delay (first time)	Immediate
Stale route risk	Low (stationary nodes)	N/A (continuous updates)

Conclusion: DSR is the clear winner for this scenario. The sensors are stationary (high cache hit rate), communicate infrequently (2-hour intervals), and are battery-powered (energy is critical). DSR uses 14x less energy on routing overhead.

Key insight: The stationary nature of nodes is crucial. If these sensors were on mobile livestock trackers moving constantly, the cache hit rate would drop dramatically, and DSR overhead would increase significantly.

95.11 DSR Source Routing Packet Structure

Every DSR data packet carries the full route in its header, allowing intermediate nodes to forward without consulting routing tables:

Diagram showing the DSR source-routed packet structure with fields for Source Address (A), Destination Address (F), Route Length (3 hops), Route List containing B then D then F as hop addresses, Hop Index starting at 0 and incrementing at each forwarding node, and the Data Payload, illustrating how each intermediate node reads the hop index to determine the next forwarding destination

95.12 Knowledge Check

Test your understanding of DSR reactive routing concepts:

Worked Example: Emergency Response Network DSR Deployment

Scenario: A disaster response team deploys 80 mobile communication units across a flood zone. Units move frequently as rescue operations progress. Each unit needs to communicate with a central coordination hub to report status and receive assignments.

Given:

80 mobile units scattered across 5 km² area
Average movement speed: 3-5 km/h (walking pace)
Communication range: 500m per unit
Average path length: 5 hops
Message frequency: Every 2 minutes per unit
Network topology changes every 15-30 minutes as units relocate

Step 1: Calculate RREQ flood overhead per route discovery

RREQ reaches all 80 units = 80 broadcast transmissions
RREP unicast back = 5 packets (5-hop path)
Total discovery cost = 80 + 5 = 85 packets per route discovery

Step 2: Determine cache timeout strategy With units moving at 3-5 km/h and 500m range, a link breaks approximately every 6-10 minutes. Using a 5-minute cache timeout: - First message: 85 packets (discovery) + 5 packets (data) = 90 packets - Next 2 messages (within 5 min): 5 packets each = 10 packets - After timeout: New discovery needed

Average per message over 15 minutes (7 messages): (90 + 10 + 90 + 10) / 7 = 28.6 packets/message

Step 3: Compare with DSDV alternative

DSDV periodic updates: 80 units × 1 update/30s = 2.67 updates/second
Over 15 minutes: 2.67 × 900s = 2,403 packets
Per message equivalent: 2,403 / 7 = 343 packets/message overhead

Result: DSR reduces routing overhead by 92% (28.6 vs 343 packets/message) in this mobile scenario, despite frequent cache invalidations.

Key Insight: Even with aggressive mobility forcing frequent re-discoveries, DSR’s on-demand approach beats DSDV’s continuous overhead when message frequency is low (every 2 minutes). If message frequency increased to every 10 seconds, DSDV would become competitive.

Decision Framework: Choosing Cache Timeout Values

When designing a DSR deployment, cache timeout is the most critical tuning parameter. Use this framework:

Network Characteristic	Recommended Timeout	Rationale
Stationary nodes (sensors on buildings)	5-10 minutes	Links rarely break; longer timeout reduces discovery overhead
Slow mobility (pedestrians, 1-5 km/h)	2-5 minutes	Balance between stale routes and discovery frequency
Moderate mobility (vehicles in traffic, 10-30 km/h)	30-60 seconds	Topology changes frequently; short timeout prevents excessive RERR messages
High mobility (highway vehicles, >60 km/h)	Don’t use DSR	Route discovery cannot keep pace with topology changes; use proactive protocols
Mixed mobility (some stationary, some mobile)	Adaptive per-node	Track RERR rate per destination; decrease timeout if >10% RERR rate observed

Adaptive timeout algorithm:

timeout_base = 120 seconds
timeout_actual = timeout_base × (1 - RERR_rate_last_hour)
// If RERR rate = 20%, timeout = 96 seconds
// If RERR rate = 5%, timeout = 114 seconds

Decision checklist:

Measured average link lifetime (time between node movements)
Set timeout to 50-70% of average link lifetime
Monitor RERR-to-data-packet ratio (should be <10%)
If RERR ratio >20%, decrease timeout by 25%
If RERR ratio <2%, increase timeout by 50%

Common Mistake: Ignoring Source Route Header Overhead

The Error: Deploying DSR on IEEE 802.15.4 networks (127-byte frames) without accounting for source route header size. With a 7-hop path, the source route header consumes 28 bytes (7 × 4 bytes per address), leaving only 99 bytes for payload and other headers after MAC overhead.

Why It Happens: Developers test DSR in simulators with artificial topologies that produce short 2-3 hop paths. Real deployments often see 5-8 hop paths, especially in dense networks.

The Impact:

For 10-hop paths: 40 bytes header = 31% of frame is routing overhead
Fragmentation required for larger payloads, adding 50-100ms latency
Effective payload reduced from 80 bytes to 40 bytes

The Fix:

Pre-deployment path analysis: Survey actual site, measure typical path lengths
Path length limits: Configure DSR to reject paths >6 hops, force sender to find alternate routes
Hierarchical routing: Use gateway nodes every 4-5 hops to segment long paths
Protocol choice: If average path length >6 hops, consider AODV (which uses hop-by-hop routing with smaller per-packet overhead) instead of DSR

Detection: Monitor “payload size after routing header” metric. If median payload <50 bytes, source routing overhead is excessive.

Interactive Quiz: Match Concepts

Interactive Quiz: Sequence the Steps

95.13 Enhanced Summary

95.13.1 Key Takeaways

Concept	Details
Protocol Type	Reactive (on-demand) – routes discovered only when data needs to be sent
Core Messages	RREQ (flood to discover), RREP (unicast path back), RERR (report broken links)
Source Routing	Complete path embedded in every packet header; intermediate nodes forward by reading header
Route Caching	Nodes overhear and cache routes; reduces repeated discovery floods
Stale Cache Risk	Mobile nodes invalidate cached routes; adaptive timeout is critical tuning parameter
Energy Tradeoff	Zero idle overhead (beats DSDV for sparse traffic); expensive per-discovery flood (loses to DSDV for dense traffic)
Header Overhead	Source route adds N x 4 bytes per packet (N = hops); significant on constrained links like 802.15.4
Best IoT Fit	Battery-powered sensors, infrequent reporting, stationary or low-mobility deployments

95.13.2 DSR Decision Checklist

Before choosing DSR for your IoT deployment, verify:

Communication is sparse: Sensors transmit less than once per minute
Battery life is critical: Devices cannot afford continuous routing overhead
Network mobility is low to moderate: Stationary or slowly-moving nodes (high cache hit rates)
Path lengths are short: Typically < 5 hops (to limit source routing header overhead)
Latency tolerance: Application can tolerate initial route discovery delay (hundreds of ms)
Not real-time: No strict latency guarantees required for actuator control or alarms

95.13.3 What You Should Be Able to Do Now

After studying this chapter and its sub-chapters, you should be able to:

Explain the three phases of DSR operation (discovery, transmission, maintenance)
Calculate DSR overhead vs DSDV overhead for a given communication pattern
Design cache timeout strategies for mixed stationary/mobile IoT networks
Identify when DSR is inappropriate (dense traffic, real-time, long paths)
Trace a complete RREQ/RREP/DATA/RERR message flow through a multi-hop network

95.15 What’s Next

If you want to…	Read this
Learn DSR caching and route maintenance	DSR Caching and Route Maintenance
Work through DSR examples	DSR Worked Examples and Practice
Compare with proactive DSDV routing	DSDV Proactive Routing
Study hybrid ZRP approach	Ad Hoc Routing: Hybrid (ZRP)
Review all ad hoc routing protocols	Ad Hoc Networks Review

💻 Code Challenge