91  Ad Hoc Routing: Proactive (DSDV)

In 60 Seconds

DSDV is a proactive routing protocol where every node maintains a routing table for ALL destinations, providing instant route availability at the cost of continuous O(n^2) update overhead. Sequence numbers prevent routing loops by ensuring fresher information always wins over stale data, regardless of hop count. Best suited for small, stable networks (<50 nodes) with frequent communication where zero route discovery latency justifies the constant maintenance cost.

Minimum Viable Understanding

• DSDV (Destination-Sequenced Distance Vector) is a proactive routing protocol where every node continuously maintains a routing table with entries for ALL destinations, providing instant route availability at the cost of constant update overhead
• Sequence numbers are the key innovation: they prevent routing loops by ensuring fresher route information always takes priority over stale data, regardless of hop count
• DSDV is best suited for small, relatively stable networks (<50 nodes) with frequent communication, where the cost of continuous updates is justified by zero route discovery latency

Sensor Squad: The Always-Updated Address Book

“How does DSDV routing work?” asked Sammy the Sensor.

Max the Microcontroller pulled out a big notebook. “Imagine I keep an address book with directions to EVERY sensor in our network. Every 15 seconds, I update it by asking all my neighbors for THEIR address books!”

“That sounds tiring!” said Bella the Battery. “You’re constantly updating even if nobody needs to send a message!”

“True,” Max admitted, “but when Sammy DOES need to send a message, I already know the exact path – no waiting! It’s like having a GPS that’s always on versus one you have to boot up each time.”

Lila the LED raised an important point: “But what about old directions? What if a sensor moved and the path is wrong?”

“That’s where SEQUENCE NUMBERS come in!” Max said proudly. “Every time a sensor updates its info, it stamps it with a number – like a date. If I have directions stamped ‘50’ and someone offers directions stamped ‘51’, I take the newer one, even if it’s a longer route. Freshness beats shortness!”

The Squad’s DSDV summary:

• Every node keeps a COMPLETE address book (routing table)
• Updated every 15 seconds by swapping info with neighbors
• Sequence numbers = expiration dates that prevent using old/wrong routes
• Fast delivery (routes always ready) but drains battery from constant updates

91.1 Learning Objectives

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

• Explain DSDV Protocol: Describe Destination-Sequenced Distance Vector as a proactive routing protocol and its design rationale
• Analyze Routing Tables: Examine how nodes maintain complete routing tables for all destinations and process updates
• Apply Sequence Numbers: Use sequence numbers to prevent routing loops and demonstrate route freshness selection
• Evaluate Route Selection: Determine optimal routes based on sequence numbers and hop counts for competing path scenarios
• Compare Proactive vs Reactive: Differentiate DSDV from reactive protocols like DSR and AODV with specific trade-off criteria
• Calculate Overhead: Compute the bandwidth and energy cost of maintaining proactive routing tables for specific network sizes

91.2 Prerequisites

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

• Wireless Sensor Networks: Understanding WSN fundamentals provides context for why ad hoc routing is needed in infrastructure-less IoT deployments where nodes must self-organize without central coordination
• WSN Overview and Fundamentals: WSN concepts like node constraints, energy limitations, and distributed operation are critical for evaluating DSDV’s suitability for battery-powered IoT networks
• Networking Basics: Fundamental networking concepts including routing tables, hop counts, packet forwarding, and distance-vector algorithms are essential prerequisites for understanding DSDV’s operation
• Routing Fundamentals: General routing principles, including path selection, routing metrics, and loop prevention, provide the foundation for DSDV’s sequence number mechanism and route selection logic

91.3 Chapter Overview

Destination-Sequenced Distance-Vector (DSDV) is a proactive (table-driven) routing protocol where each node maintains a complete routing table with entries for all network destinations. This chapter series provides comprehensive coverage of DSDV across three focused chapters.

Figure 91.1: Schematic of an ad hoc network showing nodes dynamically forming mesh topology without infrastructure

91.4 Chapter Series

This topic is covered in three focused chapters:

91.4.1 1. DSDV Fundamentals: Proactive Routing Tables

Read Chapter: DSDV Fundamentals

Covers the core concepts of DSDV including:

• What makes DSDV a proactive protocol
• Routing table structure (destination, next hop, hop count, sequence number)
• The sequence number mechanism for preventing routing loops
• Route selection rules: freshness before efficiency
• Example network topology with complete routing table walkthrough

Estimated Time: ~25 minutes

91.4.2 2. DSDV Protocol Operation: Updates and Topology Changes

Read Chapter: DSDV Protocol Operation

Covers DSDV’s dynamic behavior including:

• Periodic full-dump updates (every 15 seconds)
• Incremental updates triggered by topology changes
• How new nodes join and advertise routes
• Link break detection and route invalidation
• Sequence number increments for broken routes
• Convergence time analysis

Estimated Time: ~30 minutes

91.4.3 3. DSDV Evaluation: Trade-offs and Worked Examples

Read Chapter: DSDV Evaluation

Covers practical application and limitations including:

• DSDV limitations for IoT (overhead, power, scalability)
• When to use DSDV vs reactive protocols
• Worked Example: Route selection with competing paths
• Worked Example: Overhead calculation for IoT deployment
• Worked Example: Energy-aware route selection
• Worked Example: Convergence time after topology change
• Common misconceptions about DSDV

Estimated Time: ~35 minutes

91.5 Quick Reference

For Beginners: Proactive Routing (DSDV)

Imagine you’re planning a road trip and want to know the best route to every city in your country. You could either (1) keep an always-updated map showing routes to everywhere, or (2) only look up directions when you actually decide to visit a specific city. Proactive routing (DSDV) is like option 1 - always maintaining routes even before you need them.

Proactive = Always Ready

Think of DSDV like a GPS that constantly updates routes to all destinations: - Pro: When you want to go somewhere, the route is immediately available (zero delay) - Con: Your GPS is constantly working and draining battery updating routes you may never use

Term	Simple Explanation	Everyday Analogy
Proactive Routing	Maintain routes continuously before needed	Always-updated GPS
Routing Table	List of how to reach all destinations	Phone book with addresses
Hop Count	Number of intermediate nodes on path	Number of stops on bus route
Sequence Number	Freshness indicator for route	Expiration date on milk
Distance Vector	Share hop-count info with neighbors	Tell neighbors how far cities are
Periodic Update	Regularly broadcast routing info	Weekly neighborhood newsletter

When to Use DSDV:

• Network is relatively stable (nodes don’t move much)
• Communication is frequent (many nodes talk often)
• Low latency is critical (can’t wait for route discovery)
• Power budget is adequate (continuous updates drain batteries)

91.6 Key Concepts Summary

Concept	Description
Proactive Routing	Routes maintained continuously to all destinations
Routing Table	Complete list of (destination, next-hop, hops, seq#) entries
Sequence Numbers	Freshness indicator; higher = more recent topology info
Route Selection	Sequence number first, then hop count if equal
Periodic Updates	Full table broadcast every 15 seconds (default)
Triggered Updates	Incremental changes on topology events
Link Break	Set hops to infinity, increment seq# to propagate quickly
Overhead	O(n^2) messages; grows with network size

Quick Check: DSDV Route Selection

Putting Numbers to It

In a 100-node network, each node maintains 99 routing table entries. With periodic updates every 60 seconds, the network generates \(100 \times 99 \times (1 \text{ update/min}) \times 1440 \text{ min/day} = 14,\!256,\!000\) routing messages per day. Worked example: If each update is 50 bytes, total daily overhead = \(14.26M \times 50B = 713\) MB just for routing tables. This quadratic scaling (\(O(n^2)\)) is why DSDV is not recommended for networks larger than 50-100 nodes.

viewof dsdv_nodes = Inputs.range([10, 500], {value: 100, step: 10, label: "Number of nodes"})
viewof dsdv_update_bytes = Inputs.range([10, 200], {value: 50, step: 10, label: "Update packet size (bytes)"})
viewof dsdv_period_sec = Inputs.range([5, 120], {value: 60, step: 5, label: "Update period (seconds)"})

{
  const updates_per_day = (86400 / dsdv_period_sec);
  const msgs_per_day = dsdv_nodes * (dsdv_nodes - 1) * updates_per_day;
  const bytes_per_day = msgs_per_day * dsdv_update_bytes;
  const mb_per_day = (bytes_per_day / 1e6).toFixed(1);
  const gb_per_day = (bytes_per_day / 1e9).toFixed(3);
  return html`<div style="background:#f0f7ff;padding:12px;border-radius:6px;font-family:monospace">
    <b>Network:</b> ${dsdv_nodes} nodes, ${dsdv_period_sec}s update period<br>
    <b>Messages/day:</b> ${dsdv_nodes} × ${dsdv_nodes - 1} × ${updates_per_day.toFixed(0)} = <b>${msgs_per_day.toLocaleString()}</b><br>
    <b>Total overhead:</b> <b>${mb_per_day} MB/day</b> (${gb_per_day} GB/day)<br>
    <span style="color:${bytes_per_day > 5e8 ? '#c0392b' : '#16a085'}">
      ${bytes_per_day > 5e8 ? 'WARNING: Overhead exceeds 500 MB/day — consider DSR or ZRP' : 'Overhead within acceptable range'}
    </span>
  </div>`;
}

Test Your Understanding

Question 1: What makes DSDV a “proactive” routing protocol?

1. It reacts quickly to network changes by flooding route requests
2. It maintains routing tables to all destinations continuously, before any data needs to be sent
3. It only discovers routes when a packet needs to be sent
4. It uses zones to limit routing overhead

Answer

b) It maintains routing tables continuously. Proactive (table-driven) routing means every node always has a complete routing table with entries for all network destinations, updated through periodic broadcasts. Routes are available immediately when data needs to be sent – zero discovery delay. The trade-off is constant overhead from periodic updates, even when no data traffic exists.

Question 2: In DSDV, Node A has two routes to destination D: Route 1 (sequence #50, 3 hops) and Route 2 (sequence #52, 5 hops). Which route does DSDV select?

1. Route 1 – it has fewer hops (3 < 5)
2. Route 2 – it has a higher sequence number (52 > 50), indicating fresher information
3. Neither – DSDV uses both routes for load balancing
4. Route 1 – lower sequence numbers are more trustworthy

Answer

b) Route 2, because sequence number 52 > 50. DSDV’s key rule is: freshness (sequence number) always takes priority over efficiency (hop count). Route 2’s higher sequence number means it reflects more recent topology information. Even though it is 2 hops longer, it is more likely to be valid. Hop count only breaks ties when sequence numbers are equal.

Question 3: When is DSDV a poor choice for an IoT deployment?

1. When the network has fewer than 50 nodes
2. When communication is frequent and continuous
3. When the network is large (>200 nodes), mobile, and has sparse traffic
4. When low latency is required for data delivery

Answer

c) Large, mobile networks with sparse traffic. DSDV’s periodic updates create O(N^2) overhead regardless of traffic volume. With 200+ mobile nodes sending infrequent data, the routing overhead vastly exceeds actual data traffic. Mobility also causes constant route invalidation and re-convergence. For this scenario, reactive routing (DSR/AODV) or hybrid routing (ZRP) would be far more efficient.

91.7 Related Chapters

Deep Dives

• Ad Hoc Routing: Reactive (DSR) - On-demand routing for sparse traffic
• Ad Hoc Routing: Hybrid (ZRP) - Combining proactive and reactive approaches
• Multi-hop Fundamentals - Multi-hop network concepts

Comparisons

• Routing Fundamentals - Distance-vector vs link-state routing
• RPL Fundamentals - Proactive routing for low-power networks

Implementation

• Ad-hoc Production and Review - Production frameworks and multi-path routing
• Ad-hoc Labs and Quiz - Protocol simulation exercises

Cross-Hub Connections

Interactive Learning:

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

Common Challenges:

• Knowledge Gaps Hub - Clarifications on proactive vs reactive routing trade-offs

Video Resources:

• Videos Hub - Visual explanations of distance-vector algorithms and sequence number mechanisms

91.8 Knowledge Check

Quiz: Ad Hoc Routing: Proactive (DSDV)

Worked Example: DSDV Sequence Number Conflict Resolution

Scenario: Node D receives two competing route advertisements for destination F. Calculate which route wins.

Given:

• Current route: D → E → F (2 hops, seq#48)
• Update from A: D → A → B → F (3 hops, seq#52)
• Update from C: D → C → F (2 hops, seq#50)

Steps:

1. Compare sequence numbers (freshness first):
   • Current: seq=48, Update A: seq=52, Update C: seq=50
   • Update A has highest sequence (52) → Most recent
2. Select based on sequence number:
   • Winner: Update A (seq=52), despite being 3 hops vs 2
   • Rationale: Seq#52 > Seq#50 > Seq#48 indicates A’s info is newest

Result: D updates route to F via A (3 hops, seq#52), even though C’s route is shorter. Freshness beats efficiency in DSDV.

Key Insight: This prevents routing loops when topology changes. If D used C’s shorter but older route, it might create a loop if C-F link actually broke (generating seq#49 invalidation that D hasn’t seen yet).

Decision Framework: DSDV vs DSR Protocol Selection

Network Characteristic	DSDV (Proactive)	DSR (Reactive)
Topology change rate	<2 changes/hour	>5 changes/hour
Transmission frequency	>1 pkt/min	<1 pkt/5min
Network size	<50 nodes	50-200 nodes
Latency requirement	<100ms	>500ms tolerable
Memory available	50+ KB	10-20 KB
Energy source	Mains/solar	Battery (2-5 year)
Decision	✓ Use DSDV	✓ Use DSR

Break-Even Point: When transmission frequency × discovery cost > update cost, DSDV wins.

Common Mistake: DSDV in Large Mobile Networks

The Mistake: Deploying DSDV in 200+ node networks with moderate mobility, causing 60-80% bandwidth consumption by routing updates alone.

Impact: 200 nodes × 199 routes × 50 bytes × 120 updates/hour = 238 MB/hour overhead for maintaining routes rarely used.

Solution: Switch to DSR (on-demand) or ZRP (hybrid) for networks >100 nodes with sparse traffic.

Interactive Quiz: Match Concepts

Interactive Quiz: Sequence the Steps

Common Pitfalls

1. Ignoring Overhead for Large Networks

Students assume DSDV scales like reactive protocols. In reality, each destination requires a routing table entry and periodic broadcasts, giving O(n^2) update overhead. For networks >50 nodes, this overhead can saturate the channel — benchmark with realistic node counts before deploying.

2. Confusing Full Dumps with Incremental Updates

DSDV uses two update types: full routing table dumps (expensive, rare) and incremental updates (small, frequent). Sending full dumps too often wastes bandwidth; sending them too rarely leaves stale entries. Tune the dump interval relative to link change frequency.

3. Misunderstanding Sequence Number Freshness

Sequence numbers always increase from the destination node. A higher sequence number means newer information and always wins over stale data — even if the new route has more hops. Confusing this leads to incorrect tie-breaking logic in implementations.

4. Deploying DSDV in Highly Mobile Scenarios

DSDV assumes routes remain valid long enough to be useful. In highly mobile environments (vehicles, drones), routes become stale before periodic updates propagate, wasting channel capacity. Use reactive (AODV/DSR) or hybrid (ZRP) protocols for high-mobility deployments.

Label the Diagram

91.9 What’s Next

If you want to…	Read this
Study DSDV routing table internals	DSDV Fundamentals
See how DSDV handles topology changes	DSDV Operation and Updates
Compare DSDV performance with reactive protocols	DSDV Evaluation
Learn DSR reactive routing	Ad-hoc Routing: Reactive (DSR)
Explore hybrid ZRP routing	Ad-hoc Routing: Hybrid (ZRP)

💻 Code Challenge