94  DSDV Evaluation

In 60 Seconds

DSDV total overhead grows quadratically (O(n^2)) with network size – each node’s routing table grows linearly (O(n)), and because all n nodes broadcast these growing tables, total network-wide control traffic scales as O(n^2), making it unsuitable for networks above ~100 nodes. In sparse communication patterns, most routing table entries are never used but still consume bandwidth and battery. Choose DSDV only for small (<50 nodes), static, latency-critical networks with frequent all-to-all communication.

Minimum Viable Understanding
  • DSDV total overhead grows quadratically (O(n^2)) with network size: each node’s routing table grows linearly with n, and all n nodes broadcast these tables periodically, so total network-wide control traffic scales as O(n^2), making it unsuitable for large IoT deployments (>100 nodes).
  • DSDV wastes energy maintaining unused routes: In sparse communication patterns (e.g., sensors reporting to a single gateway), most routing table entries are never used but still consume bandwidth and battery.
  • Choose DSDV for small, static, latency-critical networks with frequent communication; choose reactive protocols (DSR/AODV) for battery-powered, sparse, or large-scale deployments.

“I have a problem,” sighed Max the Microcontroller. “I have been keeping directions to EVERY sensor in the network – all 100 of them – updated every 15 seconds.”

“Why?” asked Sammy the Sensor. “You only ever talk to me and the gateway!”

“That is what DSDV does – it keeps routes to everyone, just in case,” Max explained. “But I am exhausted! I send 100 route updates every 15 seconds, and 98 of those routes are never used!”

Bella the Battery looked pale. “No wonder my energy is draining so fast! That is like printing a phone book every 15 seconds just because you MIGHT call someone.”

“Exactly!” said Lila the LED. “For our small network of 10 sensors, it is fine. But for 100 sensors? The overhead eats up 16% of our bandwidth!”

Max made a decision. “For big networks with rare communication, we should switch to asking for directions only when we need them – that is reactive routing. Save DSDV for when we actually talk to everyone frequently.”

The squad learned that being always-prepared is great for small groups, but for large networks, sometimes it is smarter to ask for directions on demand!

Think of DSDV like a delivery company that keeps a real-time map to every single address in the country, updating it every 15 seconds. For a small town with 20 addresses, this works great – you always know how to reach anyone instantly. But for a big city with 10,000 addresses, you spend more time updating your maps than actually making deliveries!

When DSDV is a good fit:

  • Small network (under 50-100 nodes)
  • Most nodes talk to each other frequently
  • You need instant responses (no time to look up routes)
  • Devices have plenty of battery power

When DSDV is a poor fit:

  • Battery-powered sensors that rarely communicate
  • Large networks (hundreds of nodes)
  • Nodes that only talk to one gateway
  • Devices that sleep most of the time
Term Simple Explanation
O(n^2) overhead As the network doubles in size, the routing cost quadruples
Proactive overhead Energy spent maintaining routes you never use
Convergence time How long it takes all nodes to agree on correct routes after a change
Energy-aware routing Choosing routes that avoid low-battery nodes

94.1 Learning Objectives

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

  • Evaluate DSDV Limitations: Identify scenarios where DSDV is unsuitable for IoT deployments
  • Calculate Overhead: Assess the bandwidth and energy cost of maintaining proactive routing tables
  • Compare Proactive vs Reactive: Differentiate DSDV from reactive protocols like DSR and AODV
  • Apply Decision Frameworks: Select appropriate routing protocols based on network characteristics
  • Analyze Real Scenarios: Work through detailed examples of DSDV deployment trade-offs

94.2 Prerequisites

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

Key Concepts

  • DSDV Performance Metrics: Packet delivery ratio (PDR), end-to-end delay, routing overhead, and network throughput under varying mobility
  • Routing Overhead: Additional control traffic (routing table updates) as a percentage of total network traffic
  • Settling Time: Delay between route change and convergence to new stable routes; determines how quickly DSDV adapts to topology changes
  • Mobility Model: Mathematical model describing node movement patterns (random waypoint, random walk, group mobility) used in simulation
  • Network Density Effects: How node density affects routing overhead, connectivity, and delivery ratio in DSDV
  • Sequence Number Stale Routes: DSDV uses sequence numbers to discard outdated routes; stale sequence numbers cause loop-prone forwarding
  • Triggered vs Periodic Updates: DSDV uses both types; triggered updates provide faster convergence, periodic updates maintain consistency
  • DSDV vs DSR Comparison: Proactive (DSDV) vs reactive (DSR) performance trade-offs in terms of delay, overhead, and adaptability

94.3 DSDV Limitations for IoT

Estimated Time: ~8 min | Difficulty: Intermediate | Unit: P04.C05.U04

Critical DSDV Drawbacks

1. High Overhead

  • Periodic route updates consume bandwidth continuously
  • Every node broadcasts to all neighbors regularly
  • Overhead grows with network size: O(n^2) messages

2. Power Consumption

  • Battery-powered IoT nodes must wake up for periodic broadcasts
  • Listening for neighbor updates drains power
  • Unsuitable for ultra-low-power duty-cycled nodes

3. Scalability Issues

  • Large routing tables for networks with hundreds of nodes
  • Memory-constrained IoT devices may struggle
  • Update propagation delay increases with network diameter

4. Wasted Effort

  • Maintains routes to all nodes, even if never contacted
  • For sparse communication patterns, most routes unused
  • Many IoT deployments have hub-and-spoke traffic (sensors to gateway)

5. Mobility Overhead

  • Frequent topology changes trigger many updates
  • Mobile scenarios generate excessive control traffic
  • Convergence time can be slow for rapid topology changes

94.3.1 When to Use DSDV

Good Fit:

  • Network relatively static
  • Most nodes communicate frequently
  • Network size is moderate (<50-100 nodes)
  • Power budget allows continuous operation
  • Latency-sensitive applications (routes pre-computed)

Poor Fit:

  • Battery-powered sensors
  • Sparse communication patterns
  • Large networks (>100 nodes)
  • High mobility environments
  • Duty-cycled sleep schedules

94.4 Proactive vs Reactive Trade-offs

94.5 Worked Examples

94.5.1 Example 1: Route Selection with Competing Paths

Worked Example: DSDV Route Selection

Scenario: A smart factory uses DSDV routing for real-time machine monitoring. Node M (machine sensor) needs to send an alert to Node G (gateway). Node M has received two route advertisements from different neighbors:

Given:

  • Route 1 (via Node A): Destination G, Next Hop A, 3 hops, Sequence Number 156
  • Route 2 (via Node B): Destination G, Next Hop B, 2 hops, Sequence Number 152
  • Node M needs to select the best route and update its routing table

Steps:

  1. Compare sequence numbers first (DSDV’s primary criterion):

    • Route 1: seq = 156
    • Route 2: seq = 152
    • Route 1 has higher sequence number (156 > 152)

  2. Apply DSDV selection rule:

    • Higher sequence number = fresher route information
    • Route 1 (seq=156) reflects more recent network topology
    • Route 2 (seq=152) is 4 update cycles old and may include stale links

  3. Do NOT compare hop counts (sequences differ):

    • Even though Route 2 is shorter (2 hops vs. 3 hops)
    • Hop count is only compared when sequence numbers are equal

  4. Install Route 1 in routing table:

    +-------------+-----------+-------+--------+
| Destination | Next Hop  | Hops  | Seq #  |
+-------------+-----------+-------+--------+
| Node G      | Node A    | 3     | 156    |
+-------------+-----------+-------+--------+

Result: Node M selects Route 1 (via A, 3 hops, seq=156) despite Route 2 being shorter. The sequence number 156 guarantees this route reflects the current network state.

Key Insight: DSDV’s “freshness first” rule prevents routing loops caused by stale information. A longer but current route is always safer than a shorter but outdated route.

94.5.2 Example 2: Overhead Calculation for IoT Deployment

Worked Example: DSDV Overhead Calculation

Scenario: An industrial IoT deployment manager needs to evaluate whether DSDV is suitable for a sensor network monitoring a chemical plant.

Given:

  • Network size: 80 sensor nodes
  • DSDV update interval: 15 seconds
  • Routing table entry size: 12 bytes (destination, next-hop, hops, seq#)
  • Wireless link capacity: 250 kbps (typical 802.15.4)
  • Each node has routes to all other nodes: 79 entries
  • Maximum acceptable control overhead: 15% of link capacity

Steps:

  1. Calculate routing table size per node:
    • Entries: 79 (routes to all other nodes)
    • Size per entry: 12 bytes
    • Total table size: 79 x 12 = 948 bytes
  2. Calculate update frequency per node:
    • Update interval: 15 seconds
    • Updates per minute: 60/15 = 4 updates/minute
    • Updates per hour: 4 x 60 = 240 updates/hour
  3. Calculate network-wide broadcast overhead:
    • Each node broadcasts 948 bytes every 15 seconds
    • Per node per minute: 948 x 4 = 3,792 bytes/minute
    • Network total: 80 nodes x 3,792 = 303,360 bytes/minute
    • Converting to bits: 303,360 x 8 = 2,426,880 bits/minute
    • Per second: 2,426,880 / 60 = 40,448 bps
  4. Calculate overhead percentage:
    • Link capacity: 250,000 bps
    • Control overhead: 40,448 bps
    • Percentage: 40,448 / 250,000 = 16.2%
  5. Compare to threshold:
    • Calculated: 16.2%
    • Acceptable: 15%
    • DSDV exceeds acceptable overhead by 1.2%

Result: DSDV routing overhead is 16.2% of link capacity, exceeding the 15% threshold. Options include: (1) increase update interval to 20 seconds (reduces overhead to 12.1%), (2) use incremental updates instead of full table broadcasts, or (3) switch to reactive routing if traffic is sparse.

Key Insight: DSDV overhead scales as O(N^2) - both table size and number of broadcasting nodes grow with N. For networks exceeding 50-100 nodes, carefully calculate overhead.

Adjust the parameters below to see how DSDV overhead changes with network size and update frequency.

94.5.3 Example 3: Energy-Aware Route Selection

Worked Example: Energy-Aware Routing Under Battery Constraints

Scenario: A precision agriculture deployment uses 45 soil sensors across a 20-hectare vineyard. After 6 months of operation, several central relay nodes have critically low batteries.

Given:

  • 45 sensor nodes, 3 gateway nodes
  • Current routing: DSDV with pure hop-count metric
  • Node battery status after 6 months:
    • 12 nodes: >80% battery (peripheral sensors)
    • 18 nodes: 50-80% battery (moderate traffic)
    • 12 nodes: 20-50% battery (busy relay nodes)
    • 3 nodes: <20% battery (critical central relays: N7, N12, N23)
  • Critical relay node N12 forwards 40% of all network traffic
  • Path A (current): Sensor S - N5 - N12 - Gateway (3 hops, N12 at 15% battery)
  • Path B (alternate): Sensor S - N8 - N15 - N22 - Gateway (4 hops, minimum battery 65%)

Steps:

  1. Calculate current path energy distribution:
    • Path A (3 hops): N5, N12, Gateway
    • N12 energy/day: 2,880 packets x 1.2mJ = 3.46J
    • N12 also relays for 40% of network: Total drain ~15J/day
  2. Estimate remaining lifetime on Path A:
    • N12 battery: 15% of 2000mAh = 3,888J (at 3.6V)
    • Remaining days: 3,888J / 15J = 259 days before N12 dies
    • N12 dying partitions network into 3 isolated segments!
  3. Design energy-aware routing metric:
    • Modified metric: cost = hop_count x (1 / remaining_battery^2)
    • Path A cost: 3 x (1/0.15^2) = 3 x 44.4 = 133.3
    • Path B cost: 4 x (1/0.65^2) = 4 x 2.37 = 9.5
    • Path B is 14x cheaper despite being 1 hop longer!
  4. Project network lifetime improvement:
    • Without energy-aware routing: N12 dies in 259 days
    • With energy-aware routing: Offload N12 traffic to Path B
    • N12 new drain: 9J/day (60% of original) - 432 days remaining

Result: Energy-aware DSDV extends network lifetime from 259 days to 432+ days (67% improvement) by routing traffic away from battery-critical nodes.

Key Insight: Standard DSDV’s hop-count metric optimizes for latency, not lifetime. Incorporating residual energy into the routing metric dramatically improves lifetime.

94.5.4 Example 4: Convergence Time After Major Topology Change

Worked Example: DSDV Convergence Time Calculation

Scenario: A smart city traffic monitoring network uses DSDV routing among 60 intersection nodes. A construction project disables 5 adjacent nodes (N15-N19) simultaneously.

Given:

  • 60 intersection nodes in grid topology
  • DSDV update interval: 15 seconds (periodic full dump)
  • Triggered update delay: 200ms (incremental on topology change)
  • Network diameter: 8 hops (longest shortest path)
  • Nodes disabled: N15, N16, N17, N18, N19 (contiguous block)
  • Routes affected: 23 nodes had paths through disabled region
  • Packet processing time: 5ms per routing table entry
  • Wireless propagation: ~1ms per hop

Steps:

  1. Calculate triggered update propagation:
    • t=0ms: N15-N19 go offline
    • t=100ms: Neighboring nodes detect missing HELLO
    • t=200ms: Neighbors generate triggered updates with infinity metric
  2. First wave of route invalidation:
    • t=200ms: N10 broadcasts: <N15, infinity, seq+1>, ...
    • Processing time at each recipient: 5 entries x 5ms = 25ms
    • Propagation to next hop: 1ms
    • t=226ms: 8 second-tier neighbors receive invalidation
  3. Calculate full convergence time:
    • Maximum distance from disabled zone to affected node: 6 hops
    • Per-hop delay: 25ms processing + 1ms propagation = 26ms
    • Invalidation complete: t = 200ms + (6 x 26ms) = 356ms
  4. Calculate new route discovery time:
    • New routes propagate from edge nodes toward center
    • Maximum propagation: 4 hops from alternate route source
    • New routes installed: t = 356ms + (4 x 26ms) = 460ms
  5. Consider periodic update alignment:
    • Worst case: Must wait for next periodic cycle (15 seconds)
    • Worst-case convergence: 15.2 seconds
  6. Calculate packet loss during convergence:
    • Traffic rate: 10 packets/second through affected routes
    • Best case (460ms): ~5 packets lost
    • Worst case (15.2s): 152 packets lost

Result: DSDV converges in 460ms best-case (triggered updates) or 15.2 seconds worst-case (periodic updates).

Key Insight: For critical infrastructure, reduce periodic update interval (e.g., 5 seconds) and implement reliable triggered updates.

DSDV overhead grows quadratically with network size. Using formula \(O_{per\_node} = (N-1) \times entry\_size \times updates\_per\_second\), Worked example: 80 nodes, 12 bytes/entry, 1/15 updates/s per node. Per-node bandwidth = \(79 \times 12 \times (1/15) \approx 63.2 \text{ bytes/s} = 506 \text{ bps}\). Network-wide aggregate = \(80 \times 506 = 40,480 \text{ bps}\). At 250 kbps per link, this consumes approximately 16.2% of per-link capacity just for routing. For 100 nodes, the aggregate overhead jumps to \(100 \times 99 \times 12 / 15 \approx 63,360 \text{ bps} \approx 25.3\%\) — routing now dominates the network.

94.6 Knowledge Check

Scenario: You’re deploying a fleet of 50 delivery drones that must coordinate routes in real-time to avoid collisions. Drones communicate within 200m range and move at 10 m/s. Communication is frequent (every 2 seconds).

Think about:

  1. Should you use DSDV (proactive) or DSR (reactive) routing for this network?
  2. What are the energy and latency trade-offs?
  3. How does mobility affect your routing protocol choice?

Key Insight: DSDV is well-suited for this scenario despite its overhead. Why? (1) Frequent communication (every 2s) means reactive route discovery would occur almost continuously. (2) Low latency requirement - collision avoidance requires <100ms response time. DSDV provides instant forwarding. (3) Mains-powered or frequently-recharged drones can afford the energy overhead.

94.7 Common Misconceptions

Misconception: In DSDV, the route with the fewest hops is always selected as the best path.

Reality: DSDV prioritizes sequence numbers over hop count. A route with a higher sequence number will be selected even if it has significantly more hops.

Why This Matters:

Route A Route B
2 hops 5 hops
seq=100 seq=105
Older Fresher

DSDV selects Route B because: 1. Sequence 105 reflects more recent topology 2. Route A might traverse failed links detected at seq=101-104 3. A longer but current path beats a shorter broken path

Selection Algorithm:

if (seq_A > seq_B): select A
elif (seq_A == seq_B):
    if (hops_A < hops_B): select A
    else: select B
else: select B

Impact: In mobile networks, prioritizing freshness reduces packet loss from 15-20% to <2%.

94.9 Concept Relationships

Concept Relationship Connected Concept
DSDV Overhead Grows quadratically (O(n²)) with Network Size
Sequence Numbers Ensure freshness priority over Hop Count Metrics
Proactive Updates Generate continuous overhead compared to Reactive On-Demand Discovery
Route Convergence Affects network recovery time after Topology Changes
Energy-Aware Metrics Extend network lifetime by avoiding Low-Battery Relay Nodes

94.10 See Also

Common Pitfalls

DSDV performs well in static or low-mobility environments where route table updates are infrequent. Testing only with stationary nodes hides DSDV’s critical weakness — high routing overhead and poor performance under high mobility. Always evaluate in scenarios spanning the full mobility range.

Packet delivery ratio alone does not capture DSDV’s trade-offs. A network with 95% PDR but 80% routing overhead is delivering only 20% useful data. Always measure routing overhead separately and calculate network efficiency as PDR adjusted for overhead fraction.

Settling time is when routing tables stabilize after a topology change. Network convergence includes propagating updates to all nodes. In large networks, updates propagate hop-by-hop; convergence time scales with network diameter. Measuring local settling time underestimates full network recovery time.

In dense networks (50+ nodes), DSDV routing table broadcasts can cause broadcast storms as every node rebroadcasts updates. The network may spend more time broadcasting routing information than carrying data. Evaluate DSDV with density as a variable, not just mobility.

94.11 Summary

This chapter covered DSDV evaluation, trade-offs, and practical application:

  • Key Limitations: High overhead (O(n^2)), power consumption, scalability issues, and wasted effort maintaining unused routes
  • Optimal Use Cases: Static networks with frequent communication, moderate size (<50-100 nodes), adequate power budgets, and latency-sensitive applications
  • Overhead Calculation: Control traffic grows quadratically with network size; calculate before deploying
  • Energy-Aware Extensions: Incorporating battery levels into routing metrics can extend network lifetime by 67%+
  • Convergence Analysis: Best-case convergence uses triggered updates (sub-second); worst-case waits for periodic interval
  • Protocol Selection: Choose DSDV for frequent, latency-critical traffic; choose reactive (DSR) for sparse, energy-constrained deployments

Deep Dives:

Comparisons:

Implementation:

Interactive Learning:

  • Simulations Hub - Network topology visualizer for comparing DSDV routing patterns
  • Knowledge Map - Explore relationships between routing protocols

Common Challenges:

Video Resources:

  • Videos Hub - Visual explanations of distance-vector algorithms

94.12 What’s Next

If you want to… Read this
Compare with reactive DSR routing DSR Fundamentals and Route Discovery
Study hybrid ZRP approach Ad Hoc Routing: Hybrid (ZRP)
Learn DSDV fundamentals DSDV Proactive Routing
Explore DTN for disconnected networks DTN Store-Carry-Forward
Review all ad hoc routing protocols Ad Hoc Networks Review