251  DSR Caching and Route Maintenance

251.1 Learning Objectives

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

  • Evaluate Route Caching: Assess benefits and drawbacks of route caching in different mobility scenarios
  • Design Cache Strategies: Select appropriate caching strategies based on network mobility characteristics
  • Understand Route Maintenance: Explain how DSR detects and recovers from link failures
  • Apply DSR Optimizations: Implement optimization techniques for IoT deployments
  • Troubleshoot DSR Networks: Diagnose stale routes, broken paths, and discovery failures

251.2 Prerequisites

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

251.3 Route Caching

⏱️ ~12 min | ⭐⭐⭐ Advanced | 📋 P04.C07.U03

DSR nodes cache overheard routes for efficiency, reducing the need for repeated route discoveries.

251.3.1 How Route Caching Works

%% fig-alt: "DSR route caching through overhearing. Node A sends data to F via route [B,D,F]. Node C, positioned near Node B, overhears the transmission and extracts route information. Node C caches multiple learned routes: complete route to F via [B,D,F], partial route to D via [B,D], and neighbor discovery that B is adjacent to A. This passive learning reduces future route discovery overhead."
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%

graph TB
    subgraph Scenario["Route Caching Scenario"]
        A["Node A"] -->|"DATA to F via B-D-F"| B["Node B"]
        B --> D["Node D"]
        D --> F["Node F"]
        C["Node C<br/>Overhears"]
    end

    B -.->|Overhears| C

    subgraph Cache["Node C's Cache"]
        C1["Route to F:<br/>via B-D-F"]
        C2["Route to D:<br/>via B-D"]
        C3["B is neighbor<br/>of A"]
    end

    C --> Cache

    style A fill:#16A085,stroke:#2C3E50,color:#fff
    style B fill:#16A085,stroke:#2C3E50,color:#fff
    style C fill:#E67E22,stroke:#2C3E50,color:#fff
    style D fill:#16A085,stroke:#2C3E50,color:#fff
    style F fill:#16A085,stroke:#2C3E50,color:#fff
    style C1 fill:#2C3E50,stroke:#16A085,color:#fff
    style C2 fill:#2C3E50,stroke:#16A085,color:#fff
    style C3 fill:#2C3E50,stroke:#16A085,color:#fff

Figure 251.1: DSR route caching through overhearing

251.3.2 Benefits of Route Caching

  • Reduced route discovery overhead: Use cached routes instead of flooding
  • Faster communication: Skip discovery phase if route cached
  • Learn from others’ communication: Overhear and cache routes
  • Multiple routes: Cache alternate paths for redundancy

251.3.3 Cache Management Strategies

  • Timeout: Remove stale routes after period of inactivity
  • LRU replacement: Evict least recently used when cache full
  • Adaptive timeout: Adjust based on node mobility patterns

251.3.4 The Stale Cache Problem

WarningCommon Misconception: “Reactive = Always More Efficient”

Misconception: Since DSR only discovers routes when needed, it’s always more energy-efficient than proactive routing.

Reality: DSR efficiency depends heavily on communication patterns, not protocol design alone.

Why This Is Wrong:

  • Sparse communication: If sensor transmits once per hour, DSR is 90%+ more efficient (no periodic overhead)
  • Dense communication: If sensor transmits every 10 seconds, DSR becomes LESS efficient than DSDV!

The Math:

Assume 100-node network, 5-hop average path:

Scenario DSDV Overhead DSR Overhead Winner
1 transmission/hour 100 updates/hour × 100 nodes = 10,000 packets 1 RREQ flood (500 packets) + 1 RREP (5 packets) = 505 packets DSR (20× better)
1 transmission/10s Same 10,000 packets/hour 360 transmissions × 505 packets = 181,800 packets DSDV (18× better)

Key Insight: DSR route discovery floods entire network (high cost). If you flood frequently, accumulated overhead exceeds DSDV’s periodic updates.

Correct Approach:

  • DSR: Infrequent communication (<1% duty cycle), unpredictable traffic
  • DSDV: Continuous communication (>10% duty cycle), predictable traffic
  • Cache effectiveness: DSR improves dramatically with successful caching (no flooding), but cache hit rate depends on topology stability

Real Example: Smart agriculture - soil sensor reports once every 2 hours. Route discovery (500 packets) amortized over 2 hours = 4 packets/min. DSDV continuous updates = 100+ packets/min. DSR wins by 25×. But for real-time plant growth monitoring (sampling every 30s), DSDV becomes more efficient.

251.4 Route Maintenance

⏱️ ~10 min | ⭐⭐⭐ Advanced | 📋 P04.C07.U04

When a cached route breaks, DSR uses Route Error (RERR) messages to notify the source and trigger recovery.

251.4.2 Route Error (RERR) Message

  • Generated by node detecting link failure
  • Sent back to original source
  • Contains broken link identification
  • Source removes affected routes from cache

251.5 DSR Characteristics Summary

ImportantDSR Summary

Advantages: - Low overhead: No periodic updates when network idle - Scalable: Overhead proportional to actual communication - Multiple routes: Can discover and cache alternate paths - Loop-free: Source routing prevents routing loops inherently - Reactive nature: Adapts quickly to topology changes affecting active routes

Disadvantages: - Route discovery latency: Delay before first packet transmission - Header overhead: Complete route in every packet - Scalability of headers: Route length grows with network diameter - Stale cache problem: Cached routes may be broken without detection - Flood overhead: Route discovery floods entire network

Best For: - Networks with low traffic volume - Sparse communication patterns (sensor → gateway) - Relatively static topology between communication sessions - Small to medium network diameter - Applications tolerant of initial discovery delay

251.6 DSR Optimizations for IoT

⏱️ ~8 min | ⭐⭐⭐ Advanced | 📋 P04.C07.U05

251.6.1 1. Aggressive Route Caching

  • Cache every route overheard
  • Reduces discovery frequency
  • Trade memory for reduced transmissions

251.6.2 2. Piggybacking

  • Attach route cache to data packets
  • Proactive route dissemination without flooding
  • Helps neighbors build route databases

251.6.4 4. Gratuitous Route Reply

  • Intermediate nodes with cached routes reply directly
  • Reduces discovery latency
  • Risk of stale route if cache outdated

251.7 Knowledge Check

TipTest Your Understanding

Question 1: Why is route caching beneficial in DSR but can cause problems in highly mobile networks?

Explanation: Route caching: Nodes store overheard routes for future use. Benefits (stable networks): Zero discovery latency, reduced control overhead, instant communication. Problems (mobile networks): Nodes move → cached route A→B→C→D breaks (C moved away) → transmission fails → retry with stale cache → multiple failures → finally new discovery → wasted energy and latency. Stale cache detection: Timeout-based (delete after 60s) vs. failure-based (delete on ROUTE ERROR). Mobile networks: Aggressive cache invalidation or disable caching entirely. Optimal caching: Cache lifetime = f(node mobility, network density). Vehicular networks (high mobility): 5-10s cache. WSN (static nodes): 5-10min cache. DSR works best in networks with predictable, slow topology changes.

Question 2: A sensor network uses AODV routing. Node A sends data to sink node S through route A→B→C→S. Node C’s battery dies. How long until Node A discovers the failure and finds a new route?

Explanation: AODV failure detection: (1) HELLO messages: Nodes broadcast HELLO every 1 second to neighbors (RFC 3561 standard). (2) Failure detection: Node B expects HELLO from C. After 3 missed HELLOs (3 seconds), B marks C as unreachable. (3) Error propagation: B generates RERR (Route Error) message listing unreachable destination S, sends to upstream nodes (A). Time: ~3-4 seconds. (4) Route rediscovery: A receives RERR, invalidates route, initiates new RREQ flood. New route A→D→E→S discovered. Time: 2-3 seconds for RREQ/RREP round-trip. Total recovery: 5-7 seconds typical. Optimizations: Increase HELLO frequency (500ms) for faster detection but higher overhead. Use link-layer feedback (802.11 ACK) for immediate failure detection (<100ms). Alternative: Local repair - B attempts to find alternate path to S before notifying A (saves ~2s but may find suboptimal route). Real deployment: Smart building sensor network - temperature sensor data tolerates 5-10s delay during route recovery, but critical alerts need faster detection (use link-layer feedback).

NoteCross-Hub Connections

Related Learning Resources:

  • Simulations Hub: Try the Network Routing Simulator to visualize DSR route discovery, compare RREQ flooding patterns, and experiment with different cache timeout strategies in mobile vs. static topologies
  • Videos Hub: Watch “Reactive Routing Protocols” video series showing animated DSR operation, route caching benefits/drawbacks, and comparison with AODV
  • Knowledge Gaps Hub: Common DSR misconceptions - “Why doesn’t DSR scale to large networks?”, “When is aggressive caching harmful?”, “Source routing vs. hop-by-hop routing trade-offs”
  • Quizzes Hub: Test your DSR knowledge with scenario-based questions on route discovery latency, cache staleness, and protocol selection for different IoT deployments

251.8 Summary

This chapter covered DSR route caching and maintenance mechanisms:

  • Route Caching Strategy: Nodes cache overheard routes for future reuse, reducing discovery frequency in stable networks but causing stale route problems in mobile environments
  • Cache Management: Timeout-based expiration, LRU replacement, and adaptive timeouts based on mobility patterns help balance cache freshness against discovery overhead
  • Route Maintenance: Uses RERR (Route Error) messages to notify sources of broken links, triggering cache invalidation and new route discovery if no alternate cached routes available
  • Stale Cache Trade-offs: Cache timeout should align with node mobility interval - too long causes stale routes, too short causes excessive discoveries
  • Optimization Techniques: Expanding ring search limits flooding, aggressive caching reduces discoveries, gratuitous replies from intermediate nodes lower latency, and piggybacking shares route information

Continue Learning: - DSR Worked Examples - Practical scenarios and calculations

Deep Dives: - Ad Hoc Routing: Proactive (DSDV) - Table-driven continuous route maintenance - Ad Hoc Routing: Hybrid (ZRP) - Balancing proactive and reactive approaches - Multi-hop Fundamentals - Path discovery and forwarding

Implementation: - Ad-hoc Production and Review - Route caching and maintenance strategies - Ad-hoc Labs and Quiz - DSR simulation and testing

251.9 What’s Next

The next chapter provides DSR Worked Examples, with detailed calculations for route discovery latency, cache timeout optimization, energy trade-off analysis, and route error recovery scenarios.