%% fig-alt: "DSR route request (RREQ) flooding from source Node A to destination Node F. Node A broadcasts RREQ with path [A] to neighbors B and C. Node B appends itself and forwards RREQ [A,B] to D. Node C forwards RREQ [A,C] to E. Both paths eventually reach destination F with different accumulated paths showing hop-by-hop route discovery."
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
graph LR
A["Node A<br/>Source"] -->|"RREQ: A→F, Path:A, ID:101"| B["Node B"]
A -->|"RREQ: A→F, Path:A, ID:101"| C["Node C"]
B -->|"RREQ: A→F, Path:A-B, ID:101"| D["Node D"]
C -->|"RREQ: A→F, Path:A-C, ID:101"| E["Node E"]
D -->|"RREQ: A→F, Path:A-B-D, ID:101"| F["Node F<br/>Destination"]
E -->|"RREQ: A→F, Path:A-C-E, ID:101"| F
style A fill:#E67E22,stroke:#2C3E50,color:#fff
style B fill:#16A085,stroke:#2C3E50,color:#fff
style C fill:#16A085,stroke:#2C3E50,color:#fff
style D fill:#16A085,stroke:#2C3E50,color:#fff
style E fill:#16A085,stroke:#2C3E50,color:#fff
style F fill:#E67E22,stroke:#2C3E50,color:#fff
250 DSR Fundamentals and Route Discovery
250.1 Learning Objectives
By the end of this chapter, you will be able to:
- Understand DSR Protocol: Explain Dynamic Source Routing as a reactive on-demand routing protocol
- Analyze Route Discovery: Describe how route requests and route replies establish communication paths
- Explain Source Routing: Understand how complete paths are embedded in packet headers
- Compare with Proactive Routing: Differentiate DSR’s on-demand approach from DSDV’s table-driven approach
250.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
TipFor 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:
- Flood Route Request (RREQ): A broadcasts “Who knows how to reach F?” to all neighbors
- Build Path: Each node that hears the request adds its name and forwards:
[A] → [A,B] → [A,B,D] - Destination Replies: When F receives request with path
[A,B,D], it sends Route Reply (RREP) back - 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!
250.3 DSR Protocol Overview
Dynamic Source Routing (DSR) is a reactive (on-demand) protocol where routes are discovered only when needed for active communication.
250.3.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:
- Source routing: Complete path embedded in packet header
- Route discovery: Flood network with route requests
- Route caching: Intermediate nodes cache overheard routes
- No periodic updates: Zero overhead when idle
250.4 Route Discovery Process
When Node A needs to send data to Node F, the route discovery process begins:
250.4.1 Phase 1: Route Request (RREQ)
RREQ Packet Format:
<Source, Destination, [Path], Request ID>Route Request Propagation:
- Source (A) initiates:
- Broadcasts RREQ:
<A, F, [A], 101> - Request ID prevents loops
- Broadcasts RREQ:
- 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>
- Another intermediate (D) receives:
- Appends self:
[A,B,D] - Forwards toward destination
- Appends self:
- Destination (F) receives:
- Multiple RREQs may arrive via different paths
- Each contains complete path from source
250.4.2 Phase 2: Route Reply (RREP)
%% fig-alt: "DSR route reply (RREP) unicast from destination Node F back to source Node A. After receiving RREQ, Node F sends RREP containing complete discovered path [A,B,D,F] back through reverse route. RREP travels F to D to B to A, delivering full source route to originating node."
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
graph RL
F["Node F<br/>Destination"] -->|"RREP: Route A-B-D-F"| D["Node D"]
D -->|"RREP: Route A-B-D-F"| B["Node B"]
B -->|"RREP: Route A-B-D-F"| A["Node A<br/>Source"]
style F fill:#E67E22,stroke:#2C3E50,color:#fff
style D fill:#16A085,stroke:#2C3E50,color:#fff
style B fill:#16A085,stroke:#2C3E50,color:#fff
style A fill:#E67E22,stroke:#2C3E50,color:#fff
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
250.5 Alternative Views of DSR Operation
250.5.1 Timeline View
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
sequenceDiagram
participant SRC as Source A
participant INT as Network<br/>(Intermediate)
participant DST as Destination F
participant CACHE as Route Cache
Note over SRC,DST: ROUTE DISCOVERY PHASE
SRC->>INT: RREQ: Path [A]
Note over INT: Append self to path
INT->>INT: Forward: Path [A,B,D]
INT->>DST: RREQ arrives: Path [A,B,D]
Note over SRC,DST: ROUTE REPLY PHASE
DST->>INT: RREP: Complete route [A,B,D,F]
INT->>SRC: RREP delivered
Note over CACHE: Cache route for reuse
SRC->>CACHE: Store [A,B,D,F]
Note over SRC,DST: DATA TRANSMISSION PHASE
SRC->>DST: Data via source route header [B,D,F]
Note over SRC,DST: ROUTE MAINTENANCE
DST--xINT: Link breaks!
INT->>SRC: RERR: Link D-F failed
SRC->>CACHE: Invalidate route
250.5.2 Decision Tree View
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
flowchart TD
START([Node A needs to<br/>send to Node F]) --> CHECK{Check Route<br/>Cache}
CHECK -->|Route Found| VALID{Is cached<br/>route valid?}
CHECK -->|No Route| DISCOVER[Initiate Route<br/>Discovery RREQ]
VALID -->|Fresh cache| USE[Use Cached Route<br/>Send Data Immediately]
VALID -->|Stale/expired| DISCOVER
DISCOVER --> FLOOD[Flood RREQ<br/>to Neighbors]
FLOOD --> WAIT{Wait for<br/>RREP}
WAIT -->|RREP received| CACHE[Cache New Route]
WAIT -->|Timeout| RETRY{Retry<br/>count?}
CACHE --> USE
RETRY -->|< 3 retries| FLOOD
RETRY -->|>= 3 retries| FAIL[Route Discovery<br/>Failed]
USE --> SEND[Send Data with<br/>Source Route Header]
SEND --> LINK{Link<br/>OK?}
LINK -->|Success| DONE([Data Delivered])
LINK -->|Failure| RERR[Generate RERR<br/>Remove from Cache]
RERR --> DISCOVER
style START fill:#16A085,color:#fff
style CHECK fill:#2C3E50,color:#fff
style VALID fill:#2C3E50,color:#fff
style DISCOVER fill:#E67E22,color:#fff
style CACHE fill:#16A085,color:#fff
style USE fill:#16A085,color:#fff
style FAIL fill:#E74C3C,color:#fff
style DONE fill:#16A085,color:#fff
style RERR fill:#E74C3C,color:#fff
250.6 Complete DSR Example
%% fig-alt: "Complete DSR route discovery and data transmission sequence. Node A needs route to F, broadcasts RREQ with path [A]. RREQ propagates through network accumulating path: [A] to [A,B] to [A,B,D]. Node F receives RREQ, sends RREP back with complete path [A,B,D,F]. Node A caches route and sends data packets with source route embedded in header [B,D,F], each hop extracts next destination from route."
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
sequenceDiagram
participant A as Node A<br/>(Source)
participant B as Node B
participant D as Node D
participant F as Node F<br/>(Dest)
Note over A: Need route to F
A->>B: RREQ: [A]
A->>D: RREQ: [A]
B->>D: RREQ: [A,B]
D->>F: RREQ: [A,B,D]
Note over F: Route discovered
F->>D: RREP: [A,B,D,F]
D->>B: RREP: [A,B,D,F]
B->>A: RREP: [A,B,D,F]
Note over A: Route cached
A->>B: DATA via [B,D,F]
B->>D: DATA via [D,F]
D->>F: DATA
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
250.7 Knowledge Check
250.8 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
NoteRelated 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
250.9 What’s Next
The next chapter covers DSR Caching and Maintenance, exploring how nodes cache overheard routes, manage cache lifetimes, and handle route errors when links break.