92 DSDV Proactive Routing
Sensor Squad: The Always-Ready Phone Book
“How do I send a message to Sensor F on the other side of the building?” asked Sammy the Sensor.
“Easy!” said Max the Microcontroller, pulling out a big notebook. “I keep a phone book with directions to EVERY sensor in the network. Let me check… To reach F, send your message to neighbor B, who will pass it to D, who will pass it to F. Three hops!”
“Wow, that was instant!” said Sammy. “When did you figure that out?”
“I did not wait until you asked,” Max explained. “Every 15 seconds, all of us share our phone books with our neighbors. So I ALWAYS have up-to-date directions ready.”
Bella the Battery looked concerned. “Does not all that sharing use up energy?”
“It does,” Max admitted. “But here is the clever part – every route has a freshness number, like an expiration date on milk. If I hear about two routes to the same place, I always pick the fresher one, even if it is a longer path. A longer fresh route beats a shorter stale one because the short route might go through a sensor that moved away!”
Lila the LED summarized: “So DSDV is like an always-updated GPS – great when you need instant directions, but it costs energy to keep everything current.”
92.1 Learning Objectives
By the end of this chapter, you will be able to:
- Explain DSDV Protocol: Describe how Destination-Sequenced Distance Vector operates as a proactive routing protocol
- Analyze Routing Tables: Distinguish how nodes maintain complete routing tables for all destinations
- Apply Sequence Numbers: Demonstrate how sequence numbers prevent routing loops and enable fresh route selection
- Evaluate Route Selection: Determine optimal routes based on sequence numbers and hop counts
92.2 Prerequisites
Before diving into this chapter, you should be familiar with:
- Ad Hoc Fundamentals: Core concepts of ad hoc networking including self-organization, infrastructure-less operation, and peer-to-peer communication
- Multi-hop Fundamentals: Understanding multi-hop routing concepts and path establishment
- Networking Basics: Fundamental networking concepts including routing tables, hop counts, packet forwarding, and distance-vector algorithms
- Routing Fundamentals: General routing principles, including path selection, routing metrics, and loop prevention
Key Concepts
- DSDV (Destination-Sequenced Distance-Vector): Proactive ad hoc routing protocol; every node maintains complete routing table updated via periodic broadcasts
- Distance-Vector Algorithm: Each node knows next-hop and distance (hops) to every destination; learns routes from neighbor advertisements
- Sequence Number: Even number assigned by destination; DSDV uses increasing sequence numbers to reject stale routes and prevent loops
- Routing Table Entry: Contains destination, next hop, metric (hop count), sequence number, and install time
- Triggered Update: Immediate routing table broadcast triggered by topology change (link failure, new neighbor); for fast convergence
- Periodic Update: Full routing table broadcast at regular intervals; maintains consistency and detects silent node failures
- Infinity Metric: A broken link is advertised with hop count = infinity and new sequence number to propagate unreachability
- Settling Time: Dampening period after receiving a route update before rebroadcasting; reduces oscillation during instability
92.3 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
How DSDV Works: The Phone Book Analogy
Every node maintains a “phone book” (routing table) listing how to reach every other node:
My Routing Table (Node D):
To reach Node A: Send to neighbor B (2 hops away)
To reach Node F: Send to neighbor F (1 hop away)
To reach Node G: Send to neighbor F (3 hops away)Periodic Updates - The Gossip Network:
Every 15 seconds, nodes broadcast their routing tables to neighbors (like gossiping about who lives where). When you hear an update: 1. If it’s a new destination, add it to your table 2. If it’s a shorter path to known destination, update your table 3. If it’s the same destination via longer path, ignore it
Sequence Numbers - The Freshness Date:
Problem: What if a route is outdated (road closed)? DSDV uses sequence numbers like expiration dates on food: - Higher sequence number = fresher information - Always trust fresher routes, even if they’re longer - Example: Route with seq#42 and 5 hops beats route with seq#40 and 2 hops (fresher wins!)
| 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 |
92.4 What is DSDV?
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.
92.4.1 Proactive Routing Characteristics
- Proactive protocols:
- Maintain routes to all destinations continuously, even when not actively communicating
Key Characteristics:
- Routes always available (no discovery delay)
- Periodic route updates broadcast throughout network
- Higher overhead (continuous maintenance traffic)
- Good for networks where most nodes communicate frequently
92.4.2 DSDV Routing Table Structure
Each node maintains a table with entries:
| Destination | Next Hop | Hops | Seq # |
|---|---|---|---|
| Node A | Node B | 2 | 42 |
| Node C | Node C | 1 | 17 |
| Node D | Node B | 3 | 38 |
Fields:
- Destination: Target node address
- Next Hop: Immediate neighbor to forward packet to
- Hops Required: Distance metric (hop count)
- Destination Sequence Number: Freshness indicator assigned by destination
92.5 Example Network Topology
Consider this ad hoc network:
92.5.1 Node D’s Routing Table
| Destination | Next Hop | Hops | Seq # | Route |
|---|---|---|---|---|
| A | B | 2 | 042 | D-B-A |
| B | B | 1 | 156 | D-B |
| C | B | 2 | 234 | D-B-C |
| E | F | 2 | 392 | D-F-E |
| F | F | 1 | 076 | D-F |
| G | F | 3 | 128 | D-F-E-G |
| H | F | 2 | 050 | D-F-H |
92.5.2 Route Selection Decision Process
92.6 DSDV Route Updates
Nodes exchange routing information periodically or when topology changes.
Update Message Format:
<Destination, Next Hop, Hop Count, Sequence Number>Route Selection Rules:
- Prefer fresher routes: If sequence numbers differ, choose higher sequence number
- Prefer shorter routes: If sequence numbers equal, choose lower hop count
- Update on change: Broadcast updates when topology changes
92.7 Sequence Number Mechanism
The sequence number is DSDV’s key innovation that distinguishes it from traditional distance-vector protocols.
92.7.1 Why Sequence Numbers Matter
In traditional distance-vector routing (like RIP), the “count-to-infinity” problem occurs when a link fails:
- Node A loses route to destination X
- Node B still has stale route “to X via A, 2 hops”
- A asks B for route, gets “via B, 3 hops” (B thinks via A works)
- B asks A for route, gets “via A, 4 hops” (A thinks via B works)
- Hop count keeps increasing until reaching infinity threshold
DSDV solves this with sequence numbers:
- Each destination generates its own sequence numbers (even numbers)
- When a route breaks, intermediate nodes increment sequence number (to odd)
- Higher sequence number always wins, regardless of hop count
- Stale routes are immediately identified and discarded
92.7.2 Route Selection Algorithm
if (new_seq_number > current_seq_number):
# Fresher route - always adopt
update_route(new_route)
elif (new_seq_number == current_seq_number):
if (new_hop_count < current_hop_count):
# Same freshness, shorter path
update_route(new_route)
else:
# Stale route - discard
ignore(new_route)
Interactive: DSDV Route Selection Simulator
Enter two competing routes to the same destination and see which DSDV selects.
Putting Numbers to It
DSDV routing table size and update overhead scale linearly with network size. For a network with \(N\) nodes:
\[\text{Table size} = N \times E_{\text{bytes/entry}}\]
where each entry stores destination address (4 bytes), next hop (4 bytes), hop count (1 byte), and sequence number (2 bytes) = 11 bytes total.
Worked example: A 50-node sensor network with 15-second update intervals:
- Table size per node: \(50 \times 11 = 550\) bytes
- Updates per hour: \(3600 / 15 = 240\) updates
- Overhead per node: \(240 \times 550 = 132{,}000\) bytes/hour = 129 KB/hour
- Network-wide overhead: \(50 \times 129 = 6{,}450\) KB/hour ≈ 6.3 MB/hour
For comparison, if the network carries only 50 sensor readings/hour at 64 bytes each, useful data is only 3.2 KB/hour—the routing overhead is 2,016× larger than payload data. This is why DSDV is unsuitable for sparse communication patterns.
92.8 Worked Example: DSDV Table Update Walkthrough
Scenario: A 6-node wildlife tracking network in a nature reserve. Nodes A-F are GPS-tagged bird feeders that relay observation data. Each node runs DSDV with 15-second update intervals.
Initial topology (all links active):
A --- B --- C
| |
D --- E --- FStep 1: Node D’s initial routing table after convergence
| Dest | Next Hop | Hops | Seq # | Path |
|---|---|---|---|---|
| A | A | 1 | 100 | D-A |
| B | A | 2 | 200 | D-A-B |
| C | E | 3 | 300 | D-E-F-C |
| E | E | 1 | 400 | D-E |
| F | E | 2 | 500 | D-E-F |
Step 2: Link A-D breaks (bird feeder A’s antenna is damaged)
Node D detects the link failure and marks routes through A as broken by incrementing to odd sequence numbers:
| Dest | Next Hop | Hops | Seq # | Status |
|---|---|---|---|---|
| A | – | INF | 101 | Broken (odd seq) |
| B | – | INF | 201 | Broken (routed via A) |
| C | E | 3 | 300 | OK |
| E | E | 1 | 400 | OK |
| F | E | 2 | 500 | OK |
Step 3: D receives update from E containing {A via E, 2 hops, seq 102} and {B via E, 3 hops, seq 202}
Route selection logic: - Route to A: new seq 102 > current seq 101? Yes -> adopt new route (D-E-…-A) - Route to B: new seq 202 > current seq 201? Yes -> adopt new route (D-E-…-B)
Final converged table for D:
| Dest | Next Hop | Hops | Seq # | Path |
|---|---|---|---|---|
| A | E | 5 | 102 | D-E-F-C-B-A |
| B | E | 4 | 202 | D-E-F-C-B |
| C | E | 3 | 300 | D-E-F-C |
| E | E | 1 | 400 | D-E |
| F | E | 2 | 500 | D-E-F |
Why the longer path is correct: D now routes to A via 5 hops instead of 1 hop (direct). This seems wasteful, but the direct link is broken and this is the only remaining path in the topology. DSDV’s sequence number mechanism detected the failure (odd seq 101), propagated the information, and reconverged within 2 update cycles (30 seconds). Traditional distance-vector (RIP) would have counted to infinity over 16+ update cycles.
Energy cost of convergence: Each update broadcasts the full routing table (5 entries x 12 bytes = 60 bytes). With 6 nodes sending 2 triggered updates each: 6 x 2 x 60 = 720 bytes of control traffic to reconverge. For a CC2420 radio at 250 kbps and 52 mW TX power, this costs approximately 0.15 mJ – negligible for a solar-powered feeder.
92.9 Knowledge Check
92.10 Test Your Understanding
How It Works: DSDV Route Selection Process
When a node receives multiple route advertisements for the same destination, it follows this decision sequence:
Step 1: Compare Sequence Numbers
- Extract destination sequence numbers from competing routes
- Higher sequence number indicates fresher topology information
- If sequences differ, select the route with higher sequence number (ignore hop count)
Step 2: Compare Hop Counts (Only If Sequences Equal)
- If both routes have identical sequence numbers
- Select the route with fewer hops for efficiency
- Install the winning route in the routing table
Step 3: Forward Using Routing Table
- Look up next hop for destination in routing table
- Forward packet to indicated neighbor
- No per-packet route discovery needed
Example: Route A (seq=156, 3 hops) vs Route B (seq=152, 2 hops) → Choose Route A despite being longer because seq 156 > seq 152 → Freshness guarantees correctness; hop count only breaks ties
92.11 DSDV vs Other Proactive Protocols: Why Sequence Numbers Matter
DSDV was not the only proactive routing protocol designed for ad hoc networks. Understanding how it compares to alternatives reveals why certain design choices persist in modern protocols like OLSR and BATMAN.
| Feature | DSDV | OLSR (Optimized Link State) | BATMAN (Better Approach To Mobile Ad-hoc Networking) |
|---|---|---|---|
| Routing approach | Distance-vector with sequence numbers | Link-state with MPR optimization | Distributed, no single topology view |
| Loop prevention | Sequence numbers (destination-generated) | Link-state database (consistent topology) | OGM (Originator Message) sequence numbers |
| Update mechanism | Full-dump + incremental triggered | TC (Topology Control) via MPRs only | OGM flooding with TTL-based dampening |
| Per-node storage | O(N) routing entries | O(N) link-state entries + MPR set | O(N) OGM records |
| Overhead (50 nodes) | ~6.3 MB/hour (full tables every 15s) | ~1.2 MB/hour (only MPR nodes relay) | ~2.8 MB/hour (small OGM packets) |
| Convergence | 15-30 seconds (periodic) | 5-10 seconds (link-state flooding) | 10-20 seconds (OGM propagation) |
| Scalability limit | ~50 nodes (quadratic table growth) | ~200 nodes (MPR reduces flooding) | ~300 nodes (simple OGM structure) |
| Standard | Academic (Perkins & Bhagwat, 1994) | RFC 3626 (IETF, 2003) | Open-source (freifunk.net, 2007) |
| Real-world use | Research/education | Mesh networks (OLPC, military) | Community mesh (Freifunk, Guifi.net) |
Why DSDV’s Sequence Number Idea Won: While DSDV itself was superseded by more scalable protocols, its core innovation – destination-generated sequence numbers for loop prevention – was adopted by AODV (RFC 3561) and influenced OLSR and RPL. The idea that only the destination can generate authoritative sequence numbers prevents the “count-to-infinity” problem that plagued classical distance-vector protocols like RIP. AODV combined DSDV’s sequence numbers with DSR’s on-demand discovery, creating the most widely cited ad hoc routing protocol. DSDV remains essential for understanding this lineage.
Practical Threshold: If your IoT network has fewer than 30 nodes and stable topology (e.g., stationary agricultural sensors), DSDV’s simplicity makes it a reasonable choice – every node always knows the route to every other node, and the routing overhead (~2 MB/hour for 30 nodes) is manageable on 250 kbps IEEE 802.15.4 links. Beyond 50 nodes, switch to OLSR (mesh networks) or RPL (IoT sensor networks).
Try It Yourself: DSDV Routing Table Simulation
Setup: Simulate a 6-node network’s routing convergence using pen and paper.
Network Topology:
A --- B --- C
| |
D --- E --- FExercise Steps:
- Initialize: Each node creates a routing table with only itself (0 hops, seq=1)
- Round 1: Nodes broadcast their tables to direct neighbors
- Node A hears from B and D
- Update A’s table with routes to B (1 hop, seq=1) and D (1 hop, seq=1)
- Round 2: Nodes broadcast updated tables
- Node A now advertises routes to B, D (plus itself)
- Node B advertises routes to A, C
- Continue for all nodes
- Round 3-4: Propagate until all nodes reach all destinations
- Link Failure: Remove link B-C, set affected routes to infinity with seq+1
- Reconvergence: Trace how the infinity metric propagates
What to Observe:
- How many update rounds until full convergence (all nodes know all routes)?
- What happens when you remove a link—does the broken route information spread faster than alternative routes form?
- Try a 10-node network—notice how routing table size grows linearly but total network overhead grows quadratically
Expected Outcome: After 3-4 rounds, all nodes have shortest paths to all destinations. After link failure, infinity metric propagates within 1-2 rounds, then new routes form.
92.12 Concept Relationships
| Concept | Relationship | Connected Concept |
|---|---|---|
| Destination Sequence Numbers | Enable loop-free routing by ensuring | Route Freshness Priority |
| Proactive Updates | Maintain continuous route availability for | Zero-Latency Forwarding |
| Routing Table Size | Scales linearly with network size creating | O(N) Memory Requirements |
| Periodic Updates | Generate consistent overhead regardless of | Actual Communication Patterns |
| Hop Count Metric | Serves as tie-breaker after comparing | Sequence Number Freshness |
92.13 See Also
- DSDV Protocol Operation - Update mechanisms and topology change handling
- DSDV Evaluation and Trade-offs - Performance analysis and limitations
- Ad Hoc Routing: Reactive (DSR) - On-demand alternative approach
- Ad Hoc Routing: Hybrid (ZRP) - Balanced proactive-reactive approach
- Routing Fundamentals - General routing principles and metrics
Common Pitfalls
1. Confusing DSDV Sequence Numbers With IP Sequence Numbers
DSDV sequence numbers are assigned by the destination node (even numbers for valid routes, odd for broken). They increase monotonically and are used to choose between routes — higher sequence number wins, regardless of metric. Confusing these with TCP sequence numbers or other protocol counters causes incorrect route selection analysis.
2. Underestimating Periodic Update Overhead in Large Networks
Each periodic update broadcasts a full routing table. For a 100-node network, each routing table entry is ~20 bytes, so a full update is ~2 KB per node per interval. With 100 nodes and 1-second intervals, network-wide update traffic is 200 KB/s — potentially more than application traffic in low-data-rate networks.
3. Not Accounting for Settling Time in Latency Calculations
DSDV introduces settling time delay before acting on route updates. Applications that expect immediate convergence after a topology change may experience additional delay equal to the settling time. This adds to end-to-end latency during topology transitions.
4. Assuming DSDV Prevents All Routing Loops
DSDV’s sequence numbers prevent count-to-infinity routing loops that plague classic distance-vector. However, transient loops can still occur during the interval between receiving a new sequence number and propagating it to all neighbors. Assume brief transient loops are possible during convergence.
92.14 Summary
This chapter covered the fundamentals of DSDV (Destination-Sequenced Distance Vector) proactive routing:
- Proactive Nature: DSDV maintains complete routing tables to all destinations continuously, enabling immediate packet forwarding without discovery delays
- Routing Table Structure: Each node stores destination, next hop, hop count, and sequence number for every network destination
- Sequence Numbers: The key innovation that ensures route freshness and prevents routing loops by always preferring higher sequence numbers
- Route Selection: Prioritizes freshness (sequence number) over efficiency (hop count) to guarantee correctness
- Periodic Updates: Nodes broadcast routing tables regularly to maintain network-wide consistency
What’s Next
| If you want to… | Read this |
|---|---|
| See DSDV protocol operation in detail | DSDV Protocol Operation |
| Evaluate DSDV performance vs alternatives | DSDV Evaluation |
| Compare with reactive routing (DSR) | DSR Fundamentals and Route Discovery |
| Learn hybrid routing (ZRP) | Ad Hoc Routing: Hybrid (ZRP) |
| Review all proactive routing approaches | Ad-Hoc Multi-Hop Routing |