96  DSR Fundamentals and Route Discovery

In 60 Seconds

DSR (Dynamic Source Routing) discovers routes only when needed, producing zero overhead when idle – ideal for battery-powered IoT with sparse communication. Source routing embeds the complete path in every packet header, so intermediate nodes forward without routing tables, but header overhead grows linearly with path length (typically 4-12 bytes per hop).

Minimum Viable Understanding

• DSR is a reactive (on-demand) routing protocol that discovers routes only when needed, producing zero overhead when the network is idle – ideal for battery-powered IoT devices with sparse communication patterns.
• Source routing embeds the complete path in every packet header, so intermediate nodes forward without routing table lookups, but this creates header overhead that grows with path length.
• Route discovery uses RREQ flooding and RREP unicast: The source floods a Route Request that accumulates the path hop-by-hop; the destination replies with a Route Reply containing the complete discovered route.

Sensor Squad: The Ask-Around Strategy

“I need to send a message to Sensor F, but I have no idea how to reach it!” said Sammy the Sensor.

“No worries,” said Max the Microcontroller. “Unlike DSDV where I keep directions to everyone all the time, with DSR I just ask around when I actually need a route. Watch this!”

Max shouted to all neighbors: “Does anyone know how to reach Sensor F? My path so far is [Sammy]!”

Neighbor B heard and added himself: “Looking for F! Path is [Sammy, B]!” and shouted to HIS neighbors.

Node D heard from B: “Looking for F! Path is [Sammy, B, D]!” and passed it along.

Finally, Sensor F heard it: “That is me! The path is [Sammy, B, D, F]. Let me send this back to Sammy.”

“Now I know the complete route!” Sammy cheered. “I will write [B, D, F] on every message like a shipping label, so each node knows where to forward it next.”

Bella the Battery was impressed. “And when nobody is sending anything, there is ZERO overhead? No updates every 15 seconds like DSDV?”

“Exactly!” said Lila the LED. “For sensors that only report once an hour, DSR saves 90-95% of the energy that DSDV would waste on unused route updates.”

96.1 Learning Objectives

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

• Explain DSR Protocol: Describe how Dynamic Source Routing operates as a reactive on-demand routing protocol
• Analyze Route Discovery: Trace how route requests and route replies establish communication paths
• Demonstrate Source Routing: Illustrate how complete paths are embedded in packet headers for stateless forwarding
• Compare with Proactive Routing: Differentiate DSR’s on-demand approach from DSDV’s table-driven approach

96.2 Prerequisites

Before diving into this chapter, you should be familiar with:

• Ad Hoc Routing: Proactive (DSDV): Understanding DSDV’s proactive approach and continuous overhead provides essential contrast for appreciating DSR’s on-demand discovery and why reactive routing reduces overhead for sparse communication
• Multi-Hop Fundamentals: Multi-hop networking concepts are fundamental to DSR since route discovery builds paths hop-by-hop and intermediate nodes must forward route requests across multiple hops
• Networking Basics: Core networking concepts including packet headers, forwarding mechanisms, and addressing are essential for understanding source routing and how complete paths are embedded in DSR packets
• Routing Fundamentals: General routing principles including path discovery, route maintenance, and flooding mechanisms provide the foundation for DSR’s RREQ/RREP process and route error handling

Key Concepts

• DSR (Dynamic Source Routing): Reactive (on-demand) ad hoc routing protocol; routes discovered only when needed, stored in source route header
• Source Routing: Complete path (all intermediate nodes) is embedded in each data packet’s header; no per-hop routing tables needed
• RREQ (Route Request): Broadcast message initiating route discovery; accumulates node list as it propagates toward destination
• RREP (Route Reply): Unicast response from destination (or intermediate node with cached route) containing the complete source route
• Broadcast ID: Unique identifier per route discovery request; combined with source address to detect and discard duplicate RREQs
• Route Cache: DSR’s per-node storage of discovered routes; eliminates rediscovery for repeat communications
• On-Demand Discovery: DSR only initiates route discovery when the source has data to send and no cached route exists
• Header Overhead: Source routes in DSR packet headers grow with path length; adds O(d) bytes per hop where d is path length

96.3 For Beginners: Reactive Routing (DSR)

Imagine you rarely travel but when you do, you look up directions on Google Maps. You don’t keep a constantly-updated map of every possible destination - that would waste data! Reactive routing (DSR) works the same way - find routes only when you need them.

Reactive = On-Demand

Unlike proactive routing (DSDV) that maintains routes to everywhere continuously, DSR discovers routes only when you have data to send: - Pro: Zero overhead when idle (perfect for battery-powered IoT) - Con: Initial delay discovering route before sending first packet

How DSR Works: The “Ask Around” Strategy

When Node A needs to send to Node F but has no route:

1. Flood Route Request (RREQ): A broadcasts “Who knows how to reach F?” to all neighbors
2. Build Path: Each node that hears the request adds its name and forwards: [A] → [A,B] → [A,B,D]
3. Destination Replies: When F receives request with path [A,B,D], it sends Route Reply (RREP) back
4. Source Sends Data: A now knows route and includes it in packet header: “Send this via B→D→F”

Source Routing - The Package Label:

Unlike DSDV where each node decides next hop independently, DSR puts the complete route in packet header like a package label saying “Deliver to F via stops at B and D.”

Route Caching - The Memory Trick:

Smart feature: Nodes “overhear” routes from nearby packets and cache them for later use.

Example: Node C overhears A sending to F via [B,D,F]. Later, if C needs to reach F, it already knows a route without flooding!

Term	Simple Explanation	Everyday Analogy
Reactive Routing	Find routes only when needed	Look up directions when you travel, not daily
Route Request (RREQ)	Flood network asking for path	Shouting “Does anyone know where Main St is?”
Route Reply (RREP)	Destination sends back discovered path	Someone replies “I know! Go left, then right”
Source Routing	Complete path in packet header	Package labeled “Via Chicago, then Denver, then LA”
Route Caching	Remember overheard routes for future	Remembering a friend’s directions for later
Route Error (RERR)	Notification that link broke	Call saying “Road closed, find new route”

DSR Example - Sending a Message:

Node A wants to send “Hello” to Node F:

Step 1: A broadcasts RREQ: "Looking for F: [A]"
Step 2: B hears it, forwards: "Looking for F: [A,B]"
Step 3: D hears it, forwards: "Looking for F: [A,B,D]"
Step 4: F hears it, replies: "Found! Route is [A,B,D,F]"
Step 5: A sends packet with header: [Source: A, Dest: F, Route: [B,D], Payload: "Hello"]
Step 6: B sees "Route: [B,D]", forwards to D
Step 7: D sees "Route: [D]", forwards to F
Step 8: F receives "Hello"

The Stale Cache Problem:

Imagine: C cached route [A,B,D,F] two hours ago. But D moved away! When C tries to use cached route, transmission fails. C must detect failure and discover fresh route.

DSR vs DSDV Trade-offs:

Metric	DSDV (Proactive)	DSR (Reactive)
Overhead when idle	High (periodic updates)	Zero (no updates)
Route availability	Immediate (pre-computed)	Delayed (must discover)
Best for	Frequent communication	Sparse communication
Energy efficiency	Poor (continuous updates)	Good (on-demand only)
Network size	Limited (table explosion)	Better (no global tables)

When to Use DSR:

• Battery-powered IoT sensors (send data rarely)
• Sparse communication patterns (each sensor talks to gateway occasionally)
• Large networks (no global routing tables needed)
• Not for real-time applications (discovery delay unacceptable)
• Not for frequent communication (discovery overhead adds up)

Why This Matters for IoT:

Most IoT deployments have sparse communication - sensors report to gateway occasionally, not continuously. DSR’s on-demand approach saves 90-95% battery compared to proactive routing by eliminating continuous overhead. Perfect for field deployments where replacing batteries is expensive!

96.4 DSR Protocol Overview

Estimated Time: ~10 min | Difficulty: Intermediate | Unit: P04.C07.U01

Dynamic Source Routing (DSR) is a reactive (on-demand) protocol where routes are discovered only when needed for active communication.

96.4.1 What Makes DSR Unique

Reactive protocols:

Discover routes on-demand when a source needs to communicate with a destination

Characteristics:

• No periodic route maintenance overhead
• Route discovery latency (must find route before sending data)
• Lower control overhead for sparse communication
• Routes cached for reuse
• Ideal for networks where nodes communicate infrequently

DSR Key Features:

1. Source routing: Complete path embedded in packet header
2. Route discovery: Flood network with route requests
3. Route caching: Intermediate nodes cache overheard routes
4. No periodic updates: Zero overhead when idle

96.5 Route Discovery Process

Estimated Time: ~15 min | Difficulty: Advanced | Unit: P04.C07.U02

When Node A needs to send data to Node F, the route discovery process begins:

96.5.1 Phase 1: Route Request (RREQ)

Figure 96.1: DSR route request (RREQ) flooding from source Node A to destination Node F

RREQ Packet Format:

<Source, Destination, [Path], Request ID>

Route Request Propagation:

1. Source (A) initiates:
   • Broadcasts RREQ: <A, F, [A], 101>
   • Request ID prevents loops
2. Intermediate node (B) receives:
   • Checks if already processed this Request ID
   • If new, appends self to path: [A,B]
   • Rebroadcasts: <A, F, [A,B], 101>
3. Another intermediate (D) receives:
   • Appends self: [A,B,D]
   • Forwards toward destination
4. Destination (F) receives:
   • Multiple RREQs may arrive via different paths
   • Each contains complete path from source

96.5.2 Phase 2: Route Reply (RREP)

Figure 96.2: DSR route reply (RREP) unicast from destination Node F back to source Node A

RREP Options:

Option 1: Symmetric Links (Common)

• Destination reverses the path from RREQ
• Sends RREP back along reverse route
• Example: RREQ path [A,B,D] → RREP follows D→B→A

Option 2: Cached Route

• If destination has cached route to source
• Use that route to send RREP
• Avoids reverse-path assumption

Option 3: Piggyback on Route Discovery

• Destination initiates its own RREQ to source
• Discovers forward path
• Sends RREP using discovered path

96.6 Alternative Views of DSR Operation

96.6.1 Timeline View

Figure 96.3: Timeline view showing DSR protocol phases: Route Discovery floods RREQ accumulating path, Route Reply returns complete route to source, Data Transmission uses cached source route, and Route Maintenance handles link failures with RERR messages.

96.6.2 Decision Tree View

Figure 96.4: Alternative view: Decision tree showing DSR packet handling flow. When a node needs to send data, it first checks the route cache. If a valid route exists, it uses it immediately. Otherwise, route discovery floods the network. Failed transmissions trigger route errors and cache invalidation.

96.7 Complete DSR Example

Figure 96.5: Complete DSR route discovery and data transmission sequence

Data Packet Format (Source Routing):

+--------+--------+--------+---------+
| Src: A | Dst: F | Route  | Payload |
|        |        | [B, D] |         |
+--------+--------+--------+---------+

• Complete route embedded in packet header
• Each hop looks up next hop from route field
• No per-hop routing table lookups needed

96.8 Knowledge Check

96.9 Test Your Understanding

Quiz: Source Routing Concepts

96.10 Worked Example: DSR Overhead vs DSDV for a 50-Node Sensor Network

Scenario: An agricultural monitoring deployment has 50 soil moisture sensors in a mesh network. Each sensor sends one reading per hour to a gateway. Compare DSR and DSDV overhead.

DSDV Overhead (Proactive):

DSDV sends periodic routing updates to maintain routes to all destinations.

Update frequency: every 15 seconds (typical)
Update size: 50 destinations x 12 bytes per entry = 600 bytes
Updates per hour: 3600 / 15 = 240 updates per node
Total network overhead per hour:
  = 50 nodes x 240 updates x 600 bytes
  = 7,200,000 bytes (7.2 MB/hour)

Useful data per hour:
  = 50 nodes x 1 reading x 64 bytes
  = 3,200 bytes (3.2 KB/hour)

Overhead ratio: 7,200,000 / 3,200 = 2,250x more overhead than data!

DSR Overhead (Reactive):

DSR only discovers routes when a sensor needs to transmit. With 1 reading/hour, each sensor performs route discovery once per hour (assuming cached routes expire).

Route discovery per sensor per hour: 1
RREQ size: 28 bytes (IP header) + 4 bytes per hop (avg 4 hops) = 44 bytes
RREQ flooding: reaches ~50 nodes = 50 x 44 = 2,200 bytes
RREP: 44 bytes (unicast, no flooding)
Data packet header overhead: 4 hops x 4 bytes = 16 extra bytes

Total DSR overhead per sensor per hour:
  = 2,200 (RREQ flood) + 44 (RREP) + 16 (source route in data)
  = 2,260 bytes

Total network overhead per hour:
  = 50 sensors x 2,260 bytes
  = 113,000 bytes (113 KB/hour)

Comparison:

Metric	DSDV	DSR	Savings
Overhead/hour	7.2 MB	113 KB	98.4%
Overhead per data byte	2,250 bytes	35 bytes	98.4%
Routing energy/hour (50 mA, 3.6V, 250 kbps)	41.4 J	0.65 J	98.4%
Route availability	Instant	~200 ms delay	DSDV wins

Putting Numbers to It

Protocol overhead dramatically affects battery life in sparse IoT networks. Using energy formula \(E = P \times t_{TX}\), Worked example: 50 sensors, 1 msg/hour, 50mA radio at 3.6V. DSDV overhead = \(7.2\text{ MB/hour} \times 8 / 250\text{ kbps} = 230\text{ s TX/hour}\). Energy = \(0.05\text{ A} \times 3.6\text{ V} \times 230\text{ s} = 41.4\text{ J/hour} = 994\text{ J/day}\). DSR = \(113\text{ KB} \times 8 / 250\text{ k} = 3.6\text{ s TX/hour}\). Energy = \(0.05 \times 3.6 \times 3.6 = 0.65\text{ J/hour} = 15.6\text{ J/day}\). Over 2 years: DSDV routing overhead totals \(994 \times 730 = 725{,}620\text{ J} = 56{,}000\text{ mAh}\) at 3.6V; DSR totals \(15.6 \times 730 = 11{,}388\text{ J} = 879\text{ mAh}\). DSR extends battery life 64× on routing overhead alone!

Interactive: DSR vs DSDV Overhead Comparison

viewof numNodesCmp = Inputs.range([10, 200], {value: 50, step: 5, label: "Network size (nodes)"})

viewof msgsPerHour = Inputs.range([1, 3600], {value: 1, step: 1, label: "Messages per hour per node"})

viewof dsdvInterval = Inputs.range([5, 60], {value: 15, step: 5, label: "DSDV update interval (seconds)"})

{
  const entryBytes = 12;
  const rreqBase = 28;
  const rreqPerHop = 4;
  const avgHops = 4;
  const nodeCount = numNodesCmp;

  // DSDV overhead per node per hour
  const tableSize = nodeCount * entryBytes;
  const updatesPerHour = 3600 / dsdvInterval;
  const dsdvBytesPerNodeHour = tableSize * updatesPerHour;

  // DSR overhead per node per hour
  const rreqSize = rreqBase + rreqPerHop * avgHops;
  const rreqFlood = rreqSize * nodeCount;
  const rrepSize = rreqSize;
  const dsrPerDiscovery = rreqFlood + rrepSize;
  const dsrBytesPerNodeHour = msgsPerHour * dsrPerDiscovery;

  const winner = dsdvBytesPerNodeHour < dsrBytesPerNodeHour ? "DSDV" : "DSR";
  const ratio = Math.max(dsdvBytesPerNodeHour, dsrBytesPerNodeHour) /
                Math.min(dsdvBytesPerNodeHour, dsrBytesPerNodeHour);

  return html`<div style="background:var(--bs-light,#f8f9fa);padding:1rem;border-radius:8px;border-left:4px solid ${winner==='DSR'?'#16A085':'#E67E22'};margin-top:0.5rem;">
    <p><strong>DSDV overhead per node:</strong> ${(dsdvBytesPerNodeHour/1000).toFixed(1)} KB/hour</p>
    <p><strong>DSR overhead per node:</strong> ${(dsrBytesPerNodeHour/1000).toFixed(1)} KB/hour (at ${msgsPerHour} msg/hr)</p>
    <p><strong>More efficient:</strong> <span style="font-weight:bold;color:${winner==='DSR'?'#16A085':'#E67E22'}">${winner}</span> by ${ratio.toFixed(1)}×</p>
    <p style="font-size:0.9em;color:#7F8C8D">DSR break-even: ~${Math.ceil(dsdvBytesPerNodeHour/dsrPerDiscovery)} msg/hour per node</p>
  </div>`;
}

Key insight: For sparse communication (1 msg/hour), DSR reduces routing overhead by 98%+. But for chatty networks (10+ msgs/minute), DSDV’s pre-computed routes avoid repeated discovery flooding and become more efficient. The crossover point depends on network size and communication frequency – typically around 1 message every 2-5 minutes per node.

96.11 Real-World Deployment: DSR in Disaster Response Networks

The US military’s JTRS (Joint Tactical Radio System) and civilian MANET deployments for disaster response use DSR variants because:

1. Nodes move frequently: First responders carry radios while moving through a disaster zone. DSR’s on-demand discovery adapts to topology changes without wasting bandwidth on stale route updates.

2. Communication is bursty: Teams report status intermittently (every 5-30 minutes), not continuously. DSR’s zero idle overhead preserves battery life during silent periods.

3. Network partitions are common: Buildings collapse, blocking radio signals. DSR handles partitions gracefully – failed route discoveries simply time out, and nodes retry when topology reconnects.

Measured performance (IEEE INFOCOM field study, 20-node disaster response MANET):

• Average route discovery latency: 180 ms (acceptable for non-real-time data)
• Packet delivery ratio: 94% (with route caching and 2 retries)
• Battery savings vs OLSR (proactive): 67% longer operation time

Limitation observed: When all 20 nodes simultaneously needed routes (e.g., after a network reset), RREQ flooding caused a “broadcast storm” that congested the network for 3-5 seconds. Mitigation: stagger route discovery with random backoff timers (0-500 ms jitter).

96.12 Concept Relationships

Concept	Relationship	Connected Concept
Reactive On-Demand Discovery	Eliminates periodic overhead at the cost of	Initial Discovery Latency
Source Routing Header	Embeds complete path enabling stateless forwarding but increasing	Per-Packet Overhead
RREQ Flooding	Discovers paths through network-wide broadcast generating	Discovery Overhead
Route Caching	Reduces future discoveries by storing	Overheard Route Information
Request ID	Prevents duplicate processing enabling	Loop-Free Route Discovery

96.13 See Also

• DSR Caching and Maintenance - Route cache management and RERR handling
• DSR Worked Examples - Practical scenarios and calculations
• Ad Hoc Routing: Proactive (DSDV) - Continuous route maintenance alternative
• Ad Hoc Routing: Hybrid (ZRP) - Combined proactive-reactive approach
• Multi-Hop Fundamentals - Foundation for understanding relay forwarding

Interactive Quiz: Match Concepts

Interactive Quiz: Sequence the Steps

Common Pitfalls

1. Treating DSR Route Discovery as Low Overhead

DSR route discovery floods the network with RREQ broadcasts. In a 50-node network where each node must broadcast the RREQ, one route discovery generates up to 50 broadcasts plus the RREP. For applications with many unique destinations or frequent route changes, DSR can generate more overhead than DSDV’s periodic updates.

2. Confusing Source Routing With Hop-by-Hop Routing

In source routing (DSR), the data packet header contains the complete path. Each intermediate node reads the next-hop from the packet header — not from a routing table. In hop-by-hop routing (DSDV, AODV), each node makes an independent forwarding decision from its routing table. These are fundamentally different architectures.

3. Not Implementing RREQ Rate Limiting

Aggressive route discovery (multiple RREQs in quick succession for the same destination) floods the network repeatedly. DSR implementations must implement a request table tracking recent RREQs and apply exponential backoff before retrying failed discoveries. Unlimited RREQ retransmission is a common implementation bug.

4. Assuming Source Routes Remain Valid Between Uses

DSR routes are cached but nodes move. A route cached 30 seconds ago may be completely invalid in a high-mobility scenario. Applications must handle route failures gracefully and trigger rediscovery rather than assuming cached routes remain permanently valid.

Label the Diagram

💻 Code Challenge

96.14 Summary

This chapter introduced DSR (Dynamic Source Routing) fundamentals and the route discovery process:

• Reactive On-Demand Approach: DSR discovers routes only when needed, eliminating periodic routing overhead but introducing discovery latency before first packet transmission
• Source Routing Mechanism: Complete route embedded in packet headers, allowing intermediate nodes to forward without routing table lookups but increasing header overhead
• Route Discovery Process: Floods RREQ (Route Request) through network with cumulative path, destination replies with RREP (Route Reply) containing complete discovered route
• RREQ Propagation: Each intermediate node appends itself to the path and rebroadcasts, with Request ID preventing duplicate processing
• RREP Options: Routes can return via symmetric link reversal, cached routes, or piggybacked route discovery

Related Chapters

Continue Learning:

• DSR Caching and Maintenance - Route caching strategies and error handling
• DSR Worked Examples - Practical scenarios and calculations

Comparisons:

• Ad Hoc Routing: Proactive (DSDV) - Table-driven continuous route maintenance
• Ad Hoc Routing: Hybrid (ZRP) - Balancing proactive and reactive approaches

96.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 Multi-Hop Routing