252 DSR Worked Examples and Practice
252.1 Learning Objectives
By the end of this chapter, you will be able to:
- Calculate Route Discovery Latency: Compute end-to-end discovery times based on network parameters
- Optimize Cache Timeout: Determine optimal cache lifetimes for different mobility scenarios
- Analyze Energy Trade-offs: Compare discovery strategies for battery-constrained deployments
- Design Recovery Strategies: Plan route error recovery for mission-critical applications
252.2 Prerequisites
Before diving into this chapter, you should be familiar with:
- DSR Fundamentals and Route Discovery: Understanding RREQ/RREP mechanisms and source routing is essential for the worked examples
- DSR Caching and Maintenance: Route caching strategies and RERR handling are prerequisites for the optimization scenarios
252.3 Worked Example 1: Route Discovery in Emergency Response
Scenario: A wildfire response team deploys portable radio nodes across a forest. Incident Commander (Node IC) at the command post needs to send evacuation orders to Firefighter Team 3 (Node F3) located 2 km away. The network has never communicated between these nodes before, so no cached route exists.
Given: - Network nodes: IC (source), R1, R2, R3, R4, F3 (destination) - Topology: IC neighbors R1, R2; R1 neighbors R3; R2 neighbors R3, R4; R3 neighbors F3; R4 neighbors F3 - RREQ packet size: 40 bytes base + 4 bytes per hop - RREP packet size: 40 bytes + complete route - Radio range: 300m, data rate: 115 kbps
Steps: 1. IC initiates route discovery: - IC broadcasts RREQ: <IC, F3, [IC], ID=1001> - R1 and R2 receive the RREQ
- First hop forwarding:
- R1 appends self:
<IC, F3, [IC,R1], ID=1001>, forwards to R3 - R2 appends self:
<IC, F3, [IC,R2], ID=1001>, forwards to R3 and R4
- R1 appends self:
- Second hop forwarding:
- R3 receives from R1: path = [IC,R1,R3]
- R3 receives from R2: path = [IC,R2,R3] (same ID=1001, discards duplicate)
- R3 forwards first received:
<IC, F3, [IC,R1,R3], ID=1001>to F3 - R4 forwards:
<IC, F3, [IC,R2,R4], ID=1001>to F3
- Destination receives RREQ:
- F3 receives via R3: path = [IC,R1,R3,F3]
- F3 receives via R4: path = [IC,R2,R4,F3] (same ID, discards)
- F3 sends RREP with first path: route = [IC,R1,R3,F3]
- RREP returns to source:
- F3 → R3 → R1 → IC
- RREP:
<F3, IC, route=[IC,R1,R3,F3]>
- Calculate discovery latency:
- Each hop: transmission (40 bytes / 115 kbps = 2.8 ms) + propagation (<1 ms) + processing (~5 ms) ≈ 10 ms
- RREQ: 3 hops × 10 ms = 30 ms
- RREP: 3 hops × 10 ms = 30 ms
- Total discovery: ~60 ms
Result: IC discovers route [IC → R1 → R3 → F3] in approximately 60 ms. IC caches this route and can now send evacuation orders. The route [IC,R2,R4,F3] was discovered but not used because it arrived second. IC should cache both paths for redundancy.
Key Insight: DSR’s route discovery latency depends on network diameter (hop count), not network size. A 1000-node network with 5-hop diameter has similar discovery latency to a 50-node network with 5-hop diameter. The flood overhead increases with network size, but latency is hop-bound.
252.4 Worked Example 2: Cache Timeout Optimization
Scenario: A logistics company uses asset trackers on shipping containers in a port yard. Containers are moved by cranes and trucks, causing frequent topology changes. The network uses DSR with route caching. The operations team observes high packet loss (35%) and suspects stale cached routes.
Given: - 200 container trackers reporting to 5 gateway nodes - Current cache timeout: 300 seconds (5 minutes) - Average container movement interval: 90 seconds - Packet transmission frequency: every 60 seconds per tracker - Observed metrics: 35% packet loss, average 2.1 retries per successful delivery - Route discovery takes ~100 ms
Steps: 1. Analyze mobility vs. cache timeout mismatch: - Containers move every 90 seconds on average - Cache timeout: 300 seconds - Cache is 3.3× longer than mobility interval - High probability cached routes are stale when used
- Calculate stale cache probability:
- Probability container moves in 300s: 1 - e^(-300/90) ≈ 96%
- Most cached routes become invalid before expiration
- This explains 35% packet loss (stale routes fail)
- Calculate optimal cache timeout:
- Target: Cache valid for most of its lifetime
- Conservative: cache_timeout < movement_interval
- Recommended: cache_timeout = 0.5 × movement_interval = 45 seconds
- More aggressive: cache_timeout = movement_interval = 90 seconds
- Evaluate trade-offs:
- 45s timeout: More discoveries (every 45s worst case), but ~15% stale probability
- 90s timeout: Fewer discoveries, but ~50% stale probability at expiration
- 300s timeout (current): Minimal discoveries, but 96% stale probability (current problem)
- Estimate improvement with 60s timeout:
- Stale probability: 1 - e^(-60/90) ≈ 49%
- But: transmission every 60s means cache is used almost immediately after creation
- Effective stale probability at first use: ~25%
- Packet loss reduction: 35% → ~10% (65% improvement)
Result: Reducing cache timeout from 300 seconds to 60 seconds should reduce packet loss from 35% to approximately 10%. The trade-off is increased route discovery overhead (from ~0.3 discoveries/minute to ~1 discovery/minute per tracker), but this is acceptable given the 65% improvement in delivery success.
Key Insight: Optimal DSR cache timeout should be approximately equal to or less than the average mobility interval. When cache_timeout >> mobility_interval, stale routes dominate. When cache_timeout << mobility_interval, discovery overhead dominates. The sweet spot balances freshness against discovery cost. For highly mobile environments, consider disabling caching entirely and discovering fresh routes for each transmission.
252.5 Worked Example 3: Energy Trade-off Analysis
Scenario: A wildlife tracking network monitors endangered elephants across a 50km² reserve. GPS collars on 30 elephants form an ad-hoc network to relay location data to ranger stations. The network uses DSR routing, and rangers need to optimize the discovery strategy for both battery life and tracking responsiveness.
Given: - 30 elephant collar nodes, transmission range 500m - Average distance between collars: 1.2km (requires multi-hop) - Typical path length: 4-6 hops to reach gateway - RREQ packet size: 40 bytes + 4 bytes per hop accumulated - RREP packet size: 40 bytes + complete route (24 bytes for 6-hop path) - Radio power: 100mW transmit, 50mW receive - Data rate: 19.2 kbps - Collar battery: 5000mAh, must last 2 years - Location update frequency: every 15 minutes - Route lifetime before movement invalidates: ~45 minutes
Steps: 1. Calculate route discovery energy cost: - RREQ flooding: Broadcasts to all 30 nodes - RREQ size at destination: 40 + (6 × 4) = 64 bytes - Transmission time per node: 64 × 8 / 19200 = 26.7ms - RREQ energy per node: 100mW × 26.7ms = 2.67mJ - Network-wide RREQ: 30 × 2.67mJ = 80.1mJ
Calculate RREP energy:
- RREP travels 6 hops: 64 bytes each
- Per-hop transmit: 100mW × 26.7ms = 2.67mJ
- Per-hop receive: 50mW × 26.7ms = 1.33mJ
- 6-hop RREP total: 6 × (2.67 + 1.33) = 24mJ
- Total discovery: 80.1 + 24 = 104.1mJ
Compare discovery strategies:
Strategy A: Fresh discovery every transmission (no caching)
- Discoveries per day: 96 (every 15 min)
- Daily energy: 96 × 104.1mJ = 9,994mJ ≈ 10J
- 2-year energy: 730 days × 10J = 7,300J = 2,028mAh at 3.6V
- 41% of battery for routing alone!
Strategy B: Cache routes for 45 minutes
- Discoveries per day: 32 (every 45 min)
- Daily energy: 32 × 104.1mJ = 3,331mJ ≈ 3.3J
- 2-year energy: 730 × 3.3J = 2,409J = 669mAh
- 13% of battery for routing
Strategy C: Adaptive caching (45min when stationary, 15min when moving)
- Elephants stationary 70% of time, moving 30%
- Stationary discoveries: 0.7 × 32 = 22.4/day
- Moving discoveries: 0.3 × 96 = 28.8/day
- Total: 51.2 discoveries/day × 104.1mJ = 5,330mJ
- 2-year energy: 1,463mAh = 29% of battery
Calculate latency impact:
- Discovery latency: 6 hops × 30ms/hop = 180ms RREQ + 180ms RREP = 360ms
- Strategy A: 360ms delay on every transmission (unacceptable for poaching alerts)
- Strategy B: 360ms delay every 3rd transmission on average
- Strategy C: Immediate for cached routes (~95% of time), 360ms for 5%
Result: Strategy B (45-minute cache) provides the best balance, consuming only 13% of battery for routing while maintaining acceptable responsiveness. Stale route probability is ~35% at cache expiration, but DSR’s route error mechanism handles failures gracefully.
Key Insight: DSR’s energy efficiency depends critically on cache hit rate. For slowly-moving networks (elephants walk ~2-4 km/h), long cache timeouts dramatically reduce discovery overhead. The 45-minute cache aligns with typical movement patterns—elephants change position significantly every 30-60 minutes. For faster-moving targets (vehicles at 50 km/h), cache timeout should shrink to 5-10 minutes.
252.6 Worked Example 4: Route Error Recovery
Scenario: A post-earthquake search and rescue operation deploys a temporary ad-hoc network. Rescue workers carry radio nodes while searching collapsed buildings. A team leader (Node TL) needs to send survivor locations to the command post (Node CP), but the network is highly dynamic with workers constantly moving.
Given: - Network: 25 rescue worker nodes, 3 command post nodes - Terrain: Urban rubble, transmission range varies 50-150m - Current route: TL → W1 → W2 → W3 → CP (4 hops) - Worker W2 moves out of range of W1 at t=0 - Route cache contains this path from discovery 90 seconds ago - Survivor location report queued at TL (critical priority) - RERR (Route Error) processing time: 15ms per hop - New route discovery: ~200ms expected
Steps: 1. Timeline of failure detection and recovery:
t=0ms: Worker W2 moves out of W1’s range
t=0ms: TL sends survivor report using cached route [W1,W2,W3,CP]
t=35ms: Packet arrives at W1
t=35-135ms: W1 attempts transmission to W2 - First attempt: No ACK (100ms timeout) - t=135ms: W1 detects link failure
Route Error propagation:
t=135ms: W1 generates RERR: “Link W1-W2 broken”
- RERR packet: 32 bytes (error type, broken link, affected routes)
t=150ms: RERR arrives at TL (15ms transmission)
t=150ms: TL processes RERR:
- Removes route [TL,W1,W2,W3,CP] from cache
- Checks for alternate cached routes to CP: NONE FOUND
- Must initiate new route discovery
New route discovery:
t=150ms: TL broadcasts RREQ for CP
- RREQ floods network, accumulating path
t=250ms: CP receives RREQ via new path [TL,W1,W4,W5,CP]
- Note: W4 recently moved into W1’s range
t=350ms: TL receives RREP with new 4-hop route
t=350ms: TL caches new route and retransmits survivor report
Calculate total recovery time:
- Initial transmission attempt: 35ms
- Link failure detection: 100ms
- RERR propagation: 15ms
- Route discovery: 200ms
- Total: 350ms from send to successful route establishment
Impact on critical message delivery:
- Original expected latency (if route worked): ~140ms (4 hops × 35ms)
- Actual latency with failure: 350ms + 140ms = 490ms
- Delay caused by stale route: 350ms
Mitigation strategy for critical messages:
- Pre-compute backup routes during idle periods
- If TL had cached [TL,W4,W5,CP] as backup:
- Recovery: RERR (15ms) + cache lookup (5ms) + send (140ms) = 160ms
- Saves 330ms on critical message delivery
Result: DSR’s route error mechanism recovered from link failure in 350ms, acceptable for non-critical data but potentially problematic for time-sensitive survivor reports. Pre-caching backup routes reduces recovery to 160ms.
Key Insight: DSR’s RERR mechanism is reactive—it only detects failures after a transmission attempt fails. For mission-critical applications in dynamic networks, supplement DSR with proactive route maintenance: periodically probe cached routes with lightweight “route alive” packets, and pre-compute backup paths during idle periods. The 100ms ACK timeout is the dominant factor in failure detection; reducing it improves responsiveness but increases false positives from temporary interference.
252.7 Additional Practice
Scenario: A precision agriculture network has 100 battery-powered soil sensors reporting to a gateway. Each sensor transmits once per hour. The network uses DSR with aggressive route caching (10-minute timeout). Tractors occasionally move through the field, temporarily blocking sensor-gateway links.
Think about: 1. Is aggressive route caching beneficial here? 2. What happens when a tractor blocks a cached route? 3. How should cache timeout be adjusted for this environment?
Key Insight: Aggressive caching is problematic in this mobile-obstacle scenario. Analysis: (1) Communication pattern: Sensors transmit once per hour (3600s). Route discovery latency (500ms) is negligible compared to sensing interval. Caching benefit is minimal since route won’t be reused for another hour, and 10-minute cache may expire before reuse anyway. (2) Mobility impact: Tractors move through field → cached routes become stale. Sensor tries cached 3-hop route, but hop 2 now blocked by tractor. Transmission fails, sensor detects ROUTE ERROR, flushes cache, initiates new discovery. Wasted energy: Failed transmission (~50 mAh) + new discovery (~30 mAh) vs. discovering fresh route immediately (~30 mAh). Stale cache costs 60% extra energy. (3) Optimal strategy: Disable caching entirely or use very short timeout (1-2 minutes). Since communication is once per hour, each transmission should discover fresh route. Discovery overhead (30 mAh every hour) is trivial compared to sensor battery budget. Alternative: Use environmental sensors to predict cache invalidation—if accelerometer detects tractor vibration, proactively invalidate cached routes. General rule: Cache aggressively when communication >> mobility. Cache conservatively when mobility >> communication.
Scenario: A disaster response network spans 5km with 200 nodes, average 8 hops between nodes and command center. DSR source routing includes complete path in every packet header. Each node ID is 2 bytes, packet payload is 20 bytes.
Think about: 1. What percentage of packet is routing overhead? 2. How does this impact wireless transmission energy? 3. When does source routing overhead become prohibitive?
Key Insight: Source routing overhead is significant: 8 hops × 2 bytes = 16 bytes routing header. Total packet: 16 bytes (header) + 20 bytes (payload) = 36 bytes. Overhead ratio: 16/36 = 44% of packet is routing information! Energy impact: Wireless transmission energy is proportional to packet size. 44% overhead means 44% extra energy per packet. For battery-powered nodes transmitting 1000 packets over deployment lifetime, this wastes 440 packet-equivalents of energy. At 30 mAh per packet, that’s 13,200 mAh wasted (equivalent to 2-3 AA batteries). When overhead becomes prohibitive: (1) Network diameter > 10 hops: 10 hops × 2 bytes = 20 bytes overhead. For 10-byte payload, overhead is 66%! (2) Large node IDs: IPv6 addresses (16 bytes each) → 8 hops × 16 bytes = 128 bytes overhead >> payload. (3) Frequent communication: Overhead repeated every packet. Mitigation strategies: (1) Route compression: Use route indices instead of full paths. Gateway maintains route table, packets include index (2 bytes) instead of full path (16 bytes). Reduces overhead from 44% to 9%. (2) Hop-by-hop routing: Use routing tables (like DSDV) for frequent communication. Source routing benefits vanish when communication is constant. (3) Header compression: 6LoWPAN-style compression for common routes. Design guideline: DSR works best for sparse communication across short paths (≤5 hops). For dense communication or long paths, consider table-driven protocols.
252.8 Visual Reference Gallery
This visualization captures the infrastructure-less nature of ad hoc networks where DSR enables on-demand route discovery between any pair of nodes.
This diagram shows how DSR fits within the broader taxonomy of ad hoc routing protocols as a reactive, source-routing approach.
This figure illustrates the route discovery mechanism central to DSR, where route requests flood the network and replies return along discovered paths.
252.9 Summary
This chapter provided practical DSR worked examples covering:
- Route Discovery Latency: Discovery time depends on network diameter (hop count), not network size; emergency response scenario showed ~60ms for 3-hop discovery
- Cache Timeout Optimization: Optimal cache timeout should approximate mobility interval; port logistics scenario showed reducing timeout from 300s to 60s improved delivery from 65% to 90%
- Energy Trade-offs: Wildlife tracking example demonstrated 45-minute caching consuming only 13% battery vs. 41% for fresh discovery per transmission; cache hit rate is critical for energy efficiency
- Route Error Recovery: Disaster response scenario showed 350ms recovery time from link failure; pre-caching backup routes reduces recovery to 160ms for mission-critical applications
- Source Routing Overhead: Large network diameters cause significant header overhead (44% for 8-hop, 20-byte payload); consider hop-by-hop routing for dense communication
Foundation: - DSR Fundamentals and Route Discovery - Core DSR concepts - DSR Caching and Maintenance - Cache strategies and RERR
Comparisons: - Ad Hoc Routing: Proactive (DSDV) - Table-driven continuous route maintenance - Ad Hoc Routing: Hybrid (ZRP) - Balancing proactive and reactive approaches
Learning: - Simulations Hub - Route discovery visualizations
252.10 What’s Next
The next chapter explores Ad Hoc Routing: Hybrid (ZRP), covering the Zone Routing Protocol which combines proactive routing within local zones and reactive discovery between zones to balance the trade-offs of DSDV and DSR.