97  DSR Caching and Route Maintenance

In 60 Seconds

Route caching avoids repeated flooding by storing overheard routes, but cached routes go stale in mobile networks. Set cache lifetime close to the average mobility interval – a mismatch of 2x or more causes either excessive stale-route failures or wasteful rediscovery. RERR (Route Error) messages propagate back to the source when a link breaks, triggering cache invalidation and new discovery if no backup exists.

Minimum Viable Understanding
  • Route caching avoids repeated flooding by storing overheard routes for future reuse, but cached routes become stale in mobile networks where topology changes faster than cache expiration.
  • Cache timeout must match mobility: Set cache lifetime close to the average mobility interval – too long causes stale routes and wasted transmissions, too short causes excessive route discoveries.
  • Route maintenance uses RERR (Route Error) messages: When a forwarding node detects a broken link, it sends RERR back to the source, which invalidates the cached route and initiates new discovery if no backup route exists.

“I need to send data to the Gateway again,” said Sammy the Sensor. “Last time, Max found a route through B, then D, then Gateway. Do I have to flood the network again to find it?”

“No way!” said Max the Microcontroller. “I remembered that route from last time – it is in my cache. I also overheard Lila sending data through C and E to the Gateway, so I cached THAT route too. Two routes for the price of one discovery!”

“That sounds too good to be true,” said Bella the Battery cautiously. “What if Node D moved away since last time?”

“That is the stale cache problem,” Max admitted. “If I use my cached route and D is gone, my packet hits a dead end at B. B will send back an error message saying ‘Link to D is broken!’ Then I delete that route from my cache and try my backup route through C and E.”

“So caching is like remembering shortcuts,” Lila the LED summarized. “Great when the roads have not changed, but dangerous if a road closed and you did not know. In a neighborhood where roads change every 90 seconds, your 5-minute-old memory is probably wrong!”

“Exactly,” Max agreed. “For networks where things move fast, I set my memory to forget routes after just 45 seconds. For stable networks, I can remember them for 10 minutes.”

Route caching is DSR’s secret weapon for efficiency. Instead of flooding the entire network every time you want to send a packet, you remember routes you discovered or overheard:

How caching works:

  1. You discover a route to the Gateway: [A, B, D, Gateway]
  2. You store it in your cache (like a bookmark)
  3. Next time you need to reach the Gateway, you use the cached route instantly – no flooding needed!
  4. Even better: if you overhear someone else’s route discovery, you cache their route too

The problem with caching:

  • Networks change over time (nodes move, batteries die, interference appears)
  • A cached route from 5 minutes ago might go through a node that is no longer there
  • Using a stale route wastes energy: the packet travels partway, fails, and you have to start over

The solution – cache timeouts:

Network Type Mobility Recommended Timeout
Static WSN Nodes fixed 5-10 minutes
Slow mobility Walking speed 45-90 seconds
Fast mobility Vehicles 5-15 seconds
Very dynamic Random Disable caching

97.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
  • Explain Route Maintenance: Describe how DSR detects and recovers from link failures using RERR messages
  • Apply DSR Optimizations: Configure optimization techniques for IoT deployments
  • Diagnose DSR Networks: Identify stale routes, broken paths, and discovery failures in DSR deployments

97.2 Prerequisites

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

Key Concepts

  • Route Cache: DSR’s memory of discovered routes; every node stores source routes it has used or overheard
  • Cache Promiscuous Mode: Overhearing routes from neighbor transmissions and caching them without explicit discovery
  • Stale Cache Entry: A cached route that no longer works due to node movement; leads to unnecessary RREQ floods if used
  • Route Maintenance: DSR mechanism for detecting and responding to broken links on active source routes
  • Route Error (RERR) Message: Notification sent back to data source when a forwarding failure occurs; triggers route cache purge
  • Cache Timeout: Maximum age before evicting a cached route; balances freshness against rediscovery overhead
  • Salvaging: When a forwarding node detects link failure, it may substitute an alternative cached route without notifying the source
  • Route Reply Cache: Storing routes received in route reply messages; enables future data forwarding without rediscovery

97.3 Route Caching

Estimated Time: ~12 min | Difficulty: Advanced | Unit: P04.C07.U03

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

97.3.1 How Route Caching Works

Diagram showing DSR route caching via promiscuous overhearing: Node B overhears a packet with route [A,C,D,E] and adds it to its cache, enabling future direct use of the cached route without flooding
Figure 97.1: DSR route caching through overhearing

97.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

97.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

97.3.4 The Stale Cache Problem

Common 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.

97.4 Route Maintenance

Estimated Time: ~10 min | Difficulty: Advanced | Unit: P04.C07.U04

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

97.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

97.5 DSR Characteristics Summary

DSR 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

97.6 DSR Optimizations for IoT

Estimated Time: ~8 min | Difficulty: Advanced | Unit: P04.C07.U05

97.6.1 1. Aggressive Route Caching

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

97.6.2 2. Piggybacking

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

97.6.4 4. Gratuitous Route Reply

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

97.7 Knowledge Check

97.8 Test Your Understanding

Cross-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
How It Works: DSR Route Cache Management

When a DSR node encounters another node and receives route information, it follows this process:

Step 1: Overhear Route Information

  • Node listens promiscuously to nearby transmissions
  • Extracts source routes from overheard packets
  • Example: Overhears packet with route [A, B, D, F] from A to F

Step 2: Cache Decision (Should I store this route?)

  • Check if route destination is useful (not already cached with better route)
  • Verify route freshness (packet timestamp, hop count)
  • Check cache capacity (if full, apply eviction policy)

Step 3: Store Route in Cache

  • Add route to local route cache table
  • Assign timestamp (for TTL expiration)
  • Mark route quality score (based on recent use, link quality)

Step 4: Cache Lookup (When sending data)

  • Check cache for existing route to destination
  • If found and not expired → use cached route (skip discovery)
  • If not found or expired → initiate route discovery (RREQ flood)

Step 5: Cache Maintenance

  • Timeout-based: Remove routes older than cache_timeout (e.g., 60 seconds)
  • Error-based: Invalidate routes upon receiving RERR (Route Error) messages
  • LRU eviction: When cache full, remove least recently used route

Step 6: Adaptive Timeout (Advanced)

  • Monitor route error rate: high errors → reduce timeout
  • Track link duration: short links → shorter cache lifetime
  • Adjust cache timeout = f(mobility, error rate, link duration)

97.9 Cache Performance in Real Deployments

Understanding how DSR cache performance varies with mobility and network density helps architects set appropriate cache timeouts and choose between DSR and table-driven alternatives.

Measured Performance: DSR Cache Hit Rates Under Different Conditions

The following data is derived from ns-2 simulation studies validated against real testbed measurements (CMU Monarch project, Rice University DAPNet, and MIT Roofnet).

Test Setup: 50 nodes in a 1,000 m x 1,000 m area, 250 m transmission range, 10 CBR flows (4 packets/second each), simulation time 900 seconds.

Mobility Model Speed Cache Hit Rate Avg. Stale Routes Route Discoveries/min Optimal Cache Timeout
Static (no movement) 0 m/s 98% < 1% 0.3 300 s (or infinite)
Random waypoint (pedestrian) 1-2 m/s 82% 8% 2.1 30-60 s
Random waypoint (vehicle) 5-15 m/s 61% 22% 7.4 10-15 s
Random waypoint (highway) 20-30 m/s 34% 41% 18.6 3-5 s
Group mobility (platoon) 10 m/s 73% 12% 4.2 20-30 s

Key Observations:

  1. Static networks: Cache hit rates above 95% mean DSR’s route caching is highly effective. The rare discoveries are for initial route setup. Cache timeouts can be very long (minutes).

  2. Pedestrian mobility (1-2 m/s): Cache hit rates remain high (82%) because topology changes slowly relative to packet transmission. A 30-second timeout balances freshness against discovery overhead. This matches smart building and warehouse IoT scenarios.

  3. Vehicular mobility (5-15 m/s): Cache hit rates drop below 65%, and 22% of cached routes are stale at any given time. At this mobility level, DSR starts losing its advantage over proactive protocols like DSDV, which maintain routes continuously. This is the crossover point where DSR overhead (from frequent discoveries) approaches DSDV overhead (from periodic updates).

  4. Highway mobility (20+ m/s): DSR cache is more harmful than helpful – 41% stale routes means nearly half of cached routes lead to delivery failures followed by RERR + rediscovery. At this speed, proactive protocols or location-based routing (GPSR) are better choices.

  5. Group mobility (platoons): Higher hit rates than individual random waypoint at the same speed because group members maintain relative positions. Relevant for drone swarms, vehicle convoys, and military formations.

Decision Framework: When to Use DSR vs. Alternatives

Network Characteristic DSR Route Caching DSDV (Proactive) AODV (Reactive, No Source Route)
Static / low mobility (< 2 m/s) Best choice – cache hit > 80%, minimal overhead Wastes bandwidth on periodic updates for unchanged topology Good but lacks DSR’s multi-path caching advantage
Moderate mobility (2-10 m/s) Viable with tuned timeouts (10-30 s) Competitive – proactive updates track changes Better than DSR at scale (no source route header overhead)
High mobility (> 10 m/s) Poor – stale caches cause cascading failures Good for small networks (< 50 nodes) Best reactive choice (lower overhead than DSR)
Dense network (> 50 nodes/km2) Cache pollution risk – too many overheard routes Excessive table exchange overhead Better scalability than both DSR and DSDV
Sparse network (< 10 nodes/km2) Excellent – caching reduces costly discoveries across long paths Tables mostly empty, periodic updates wasted Similar to DSR but without multi-path benefit

Practical Rule: If your IoT deployment has nodes moving faster than walking speed (> 2 m/s) AND more than 30 nodes, DSR’s route caching becomes a liability rather than an asset. Switch to AODV or a hybrid protocol (ZRP) that limits caching to local zones.

Scenario: A warehouse inventory system uses 100 mobile sensors on forklifts and robots. Sensors move at 2-5 m/s, communication range 50m. Current DSR cache timeout is 60 seconds, causing 40% stale route failures.

Analysis:

Mobility Calculation:

  • Average speed: 3.5 m/s (mix of forklifts and robots)
  • In 60 seconds, nodes move: 3.5 m/s × 60s = 210m
  • Communication range: 50m
  • Nodes that were 1-hop neighbors (0-50m apart) can be 160-260m apart after 60s (no longer reachable)

Optimal Cache Timeout:

  • Target: Nodes should move <25m during cache lifetime (stay within half the communication range for buffer)
  • Calculation: 25m / 3.5 m/s = 7.1 seconds
  • Recommended timeout: 7 seconds (conservative) or 10 seconds (balanced)

Cache timeout must match mobility to minimize stale routes. Using formula \(T_{cache} = \frac{R_{radio}/2}{v_{node}}\) where \(R_{radio}\) is communication range and \(v_{node}\) is velocity, Worked example: Warehouse sensors move at 3.5 m/s, radio range 50m. Optimal timeout = \((50/2) / 3.5 = 7.1s\). With current 60s timeout, nodes move \(3.5 \times 60 = 210m\) — 4× beyond radio range! This causes 40% stale routes. Reducing to 10s allows \(3.5 \times 10 = 35m\) movement (within range), reducing stale routes from 40% to 8% and improving delivery from 72% to 93%.

Performance Comparison (simulation with 100 nodes, 10 CBR flows):

Cache Timeout Cache Hit Rate Stale Routes Route Discoveries/min Packet Delivery
60s (current) 45% 40% 8.2 72%
30s 62% 22% 5.4 84%
10s (optimal) 78% 8% 3.1 93%
5s 81% 4% 2.8 94%
0s (disabled) 0% 0% 12.5 88%

Result: Reducing cache timeout from 60s to 10s improves packet delivery from 72% to 93% by reducing stale routes from 40% to 8%, while route discovery overhead decreases by 62% (8.2 → 3.1 discoveries/min).

Tradeoff: Going below 5s provides minimal benefit (94% vs. 93% delivery) but increases discovery overhead. The 10-second timeout is the sweet spot for this mobility pattern.

Choose between DSR (reactive) and DSDV (proactive) based on network characteristics:

Network Characteristic DSR (Reactive) DSDV (Proactive) Recommendation
Traffic pattern Infrequent (<10 msgs/min) Continuous (>60 msgs/min) DSR for sparse, DSDV for dense
Topology stability High mobility (>2 m/s) Low mobility (<1 m/s) DSR for dynamic, DSDV for stable
Network size Small-medium (<50 nodes) Any size DSR scales poorly beyond 100 nodes
Latency tolerance Can tolerate 1-3s discovery Needs <100ms first packet DSDV for latency-critical
Cache effectiveness >60% hit rate achievable N/A DSR if cache hit >60%, else DSDV
Energy budget Limited (battery) Moderate DSR for energy-constrained if sparse traffic

Hybrid Example: Use DSR for event-driven alarms (1% of traffic, sporadic), DSDV for periodic monitoring (99% of traffic, predictable).

Decision Rule:

  • If (traffic_rate < 10 msgs/min AND mobility < 5 m/s): DSR recommended
  • If (traffic_rate > 60 msgs/min OR requires <100ms latency): DSDV recommended
  • If (between thresholds): Test both protocols in simulation with your specific traffic pattern
Common Mistake: Aggressive Route Caching in High-Mobility Networks

The Mistake: Enabling aggressive caching (cache every overheard route, long timeouts) to minimize route discoveries, without accounting for mobility-induced staleness.

Real Impact: A vehicular ad-hoc network (VANET) with 50 vehicles traveling at 60 km/h (16.7 m/s) uses DSR with 60-second cache timeout.

The Numbers:

  • Vehicle speed: 60 km/h = 16.7 m/s
  • Communication range: 300m (802.11p)
  • In 60 seconds, vehicles move 1 km → Cached routes completely invalid
  • Cached route probability of success: <10% after 30 seconds
  • Each failed cached route attempt wastes 3 retransmissions before triggering RERR
  • Measured packet delivery ratio: 45% (vs. 78% with proper cache timeout)

Correct Approach for High Mobility:

  1. Mobility-adaptive caching: Reduce cache timeout based on observed link duration
    • Measure time between route discovery and first RERR
    • Set cache timeout = 0.5 × average link duration
    • For 60 km/h vehicles: Link duration ≈ 300m / 16.7 m/s = 18s → Cache timeout = 9s
  2. Link quality weighting: Cache routes with strong signal strength (RSSI > -75 dBm) for longer
    • Strong links (RSSI > -75): 15s timeout
    • Weak links (RSSI < -85): 3s timeout
    • Discard routes immediately when RSSI drops below threshold
  3. Predictive cache invalidation: Use GPS velocity vectors to predict when nodes will exit range
    • If relative velocity >30 m/s (converging/diverging): 5s timeout
    • If relative velocity <10 m/s (parallel travel): 20s timeout

Result with Adaptive Caching:

  • Packet delivery ratio: 45% → 81% (80% improvement)
  • Average end-to-end latency: 850ms → 340ms (60% reduction)
  • Stale route rate: 38% → 9% (76% reduction)

Implementation (simplified):

uint32_t calculateCacheTimeout(Route* route) {
    int8_t rssi = route->getAverageRSSI();
    float linkDuration = route->getObservedLinkDuration();

    if (rssi > -75 && linkDuration > 30) {
        return 15000; // Strong, stable link: 15s
    } else if (rssi < -85 || linkDuration < 5) {
        return 3000;  // Weak or unstable: 3s
    } else {
        return (linkDuration / 2) * 1000; // Default: half observed duration
    }
}

Lesson: Cache aggressiveness must inversely scale with mobility. Static cache timeouts fail in dynamic networks.

Scenario: You’re deploying a mobile sensor network where nodes move at walking speed (1.5 m/s) with 100m radio range.

Exercise Steps:

  1. Calculate mobility interval (time until topology changes significantly):
    • Mobility interval = radio_range / node_velocity
    • Fill in: = 100m / 1.5 m/s = ? seconds
  2. Determine optimal cache timeout using half-range rule:
    • Formula: cache_timeout = (radio_range / 2) / node_velocity
    • Calculate: (100m / 2) / 1.5 m/s = ? seconds
  3. Estimate cache hit rate:
    • If nodes transmit every 30 seconds
    • Cache timeout from step 2
    • Will routes still be cached when needed? (compare 30s to cache timeout)
  4. Estimate stale route probability (conservative exponential model):
    • Formula: P(stale) ≈ cache_timeout / mobility_interval (for low ratios)
    • Plug in your cache timeout value from step 2
    • For <10% stale routes, need cache_timeout < 0.1 × mobility_interval ≈ 6.7s
    • Note: the half-range formula (step 2) gives a practical starting point; stricter deployments should use the 10% rule.
  5. Trade-off analysis:
    • Longer timeout → Higher hit rate but more stale routes
    • Shorter timeout → Fresher routes but more discoveries
    • Find the sweet spot for your mobility pattern

What to Observe:

  • How does doubling node velocity affect optimal cache timeout?
  • What happens if you set cache timeout to 5 minutes for fast-moving nodes?
  • When does it make sense to disable caching entirely?

Expected Outcome: Mobility interval = 100/1.5 = 66.7s. Half-range timeout = (100/2)/1.5 = 33.3s ≈ 33 seconds. Stricter <10% stale target requires ~6.7s. Doubling velocity to 3 m/s halves the optimal timeout to ~16s (half-range) or ~3.3s (strict).

97.10 Concept Relationships

Concept Relationship Connected Concept
Route Caching Reduces discovery overhead by storing Overheard Route Information
Cache Timeout Must match network mobility to balance Route Freshness vs Discovery Cost
Stale Cache Problem Causes packet loss when topology changes faster than Cache Expiration Rate
RERR Messages Propagate link failure notifications triggering Cache Invalidation
Adaptive Timeout Adjusts cache lifetime based on observed Link Duration and Error Rate

97.11 See Also

Common Pitfalls

Without cache timeouts, DSR accumulates stale routes as nodes move. Data is forwarded along broken paths, generating RERR messages and repeated RREQ floods. Always implement cache expiration with appropriate timeouts calibrated to expected node mobility speed.

Promiscuous route caching can fill the cache with overheard routes that are never used. In high-density networks, the cache fills with partial routes that become stale quickly. Benchmark cache hit rates to verify that promiscuous caching is helping rather than filling memory with useless entries.

When link failure is detected, the forwarding node generates a RERR — but this may not reach the source if the return path is also broken. Sources should implement RREQ retry after packet delivery failures, not just wait for RERR. RERR delivery is best-effort in mobile environments.

A link failure in DSR invalidates only routes that use the broken link segment, not the entire cache. Invalidating all cached routes on any failure causes unnecessary rediscovery overhead. Implement targeted cache invalidation that only removes routes containing the failed hop.

97.12 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:

Deep Dives:

Implementation:

97.13 What’s Next

If you want to… Read this
Study DSR route discovery fundamentals DSR Fundamentals and Route Discovery
Work through DSR examples DSR Worked Examples and Practice
Compare with proactive DSDV routing DSDV Proactive Routing
Learn about DTN for intermittent links DTN Store-Carry-Forward
Review ad hoc network production patterns Ad Hoc Networks Review