93 DSDV Protocol Operation

In 60 Seconds

DSDV maintains routing tables through two update types: periodic full-dumps every ~15 seconds (broadcasting complete tables) and triggered incremental updates for critical changes. Link breaks are handled by setting hop count to infinity and incrementing the sequence number, ensuring broken-route information propagates and overrides stale cached entries.

Minimum Viable Understanding

Two update types maintain routing tables: Periodic full-dump updates (every ~15 seconds, broadcasting the complete table) ensure consistency, while incremental triggered updates propagate critical changes faster with less overhead.
Link breaks are handled by setting hop count to infinity and incrementing the sequence number, ensuring the “broken route” information propagates quickly and overrides any stale cached entries.
Convergence time ranges from sub-second (triggered updates) to ~15 seconds (periodic), depending on whether topology changes trigger immediate incremental updates or must wait for the next periodic cycle.

Sensor Squad: The Neighborhood Newsletter

“Time for our weekly neighborhood newsletter!” announced Max the Microcontroller. “Everyone shares their routing tables with neighbors.”

“But what if something changes between newsletters?” asked Sammy the Sensor. “What if Sensor F moves away right after we published?”

“Great question!” said Max. “We have TWO ways to share news. First, the regular newsletter every 15 seconds – that is the full dump. But if something big happens, like a link breaking, we send an emergency bulletin right away – that is a triggered update.”

Suddenly, Lila the LED shouted, “The link to Sensor F just broke!”

Max sprang into action. “Quick! Mark all routes through F as BROKEN with an infinity distance. And here is the key – bump up the freshness number! If our old route to F had freshness 76, we mark the broken route as freshness 77. That way, everyone knows this broken news is NEWER than their working route.”

“Why does the number matter?” asked Bella the Battery.

“Because if someone still has the old route with freshness 76, they might ignore our update thinking theirs is just as good. But freshness 77 is higher, so they MUST accept our broken-route news and stop sending packets into a dead end!”

The squad learned that in DSDV, bad news must travel fast – and incrementing the sequence number makes sure it does!

For Beginners: How DSDV Keeps Routes Updated

DSDV nodes share routing information in two ways, like a school that has both a regular newsletter and an emergency announcement system:

Full-dump updates (every 15 seconds): Like a weekly newsletter listing all routes. Ensures everyone eventually gets all information, but uses a lot of bandwidth.
Incremental updates (on topology change): Like an emergency announcement. When a link breaks or a new node joins, nearby nodes immediately broadcast just the changed routes. Faster and cheaper than a full dump.

When a link breaks:

The detecting node sets the broken route’s hop count to infinity (meaning “unreachable”)
It increments the sequence number so this “broken” news is treated as fresher than the old “working” route
All nodes receiving this update discard their old route and look for alternatives

Term	Simple Explanation
Full dump	Broadcasting your entire routing table to neighbors
Incremental update	Broadcasting only the routes that changed
Infinity metric	Setting hop count to “infinite” to indicate a broken route
Triggered update	An update sent immediately when something changes

93.1 Learning Objectives

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

Compare Update Mechanisms: Distinguish between full-dump and incremental update mechanisms in DSDV
Trace Node Integration: Analyze how route advertisements propagate when nodes join the network
Explain Link Break Recovery: Describe the route invalidation process using infinity metrics and sequence numbers
Calculate Convergence Time: Estimate how long topology changes take to propagate through the network

93.2 Prerequisites

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

DSDV Fundamentals: Understanding routing tables, sequence numbers, and route selection rules
Ad Hoc Fundamentals: Core concepts of ad hoc networking
Routing Fundamentals: General routing principles and distance-vector algorithms

Key Concepts

Route Advertisement: DSDV nodes broadcast their routing table to neighbors; neighbors merge received entries with their own tables
Metric Increment: When forwarding a route advertisement, each node increments the hop count by 1 (distance-vector principle)
Best Route Selection: Among entries to the same destination, prefer higher sequence number; among equal sequence numbers, prefer lower metric
Route Deletion: Broken link detected (hello message timeout); advertise destination with infinity metric and new (even) sequence number
Full Dump vs Incremental Update: Full dump sends complete routing table; incremental sends only changed entries since last broadcast
Hello Mechanism: Periodic link-layer “hello” messages detect neighbor availability; timeout indicates link failure
Network Convergence: All nodes having consistent routing tables; may take multiple update intervals in large networks
Dampening: Holding period before advertising a new route; prevents oscillation when routes fluctuate rapidly

93.3 DSDV Update Mechanisms

Estimated Time: ~15 min | Difficulty: Advanced | Unit: P04.C05.U03

DSDV uses two types of updates to maintain routing tables across the network.

93.3.1 Periodic Full-Dump Updates

Sequence diagram of DSDV periodic full-dump update cycle: at t=0, t=15s, and t=30s, each node broadcasts its complete routing table to all neighbors, ensuring network-wide consistency even without triggered changes — Figure 93.1: DSDV periodic update sequence showing nodes exchanging full routing tables every 15 seconds

Periodic Update Characteristics:

Broadcast complete routing table to all neighbors
Default interval: 15 seconds (configurable)
Ensures all nodes eventually receive all routes
High overhead but guarantees consistency

93.3.2 Incremental Updates

When topology changes occur between periodic updates, nodes can send incremental updates containing only the changed routes.

Incremental Update Advantages:

Triggered by topology changes
Only changed routes advertised
Reduces overhead compared to full table broadcast
Faster propagation of important changes

Bar chart comparing DSDV and DSR control overhead in a 100-node network, showing DSDV generating constant high overhead from periodic broadcasts while DSR generates lower overhead only during route discovery events — Figure 93.2: Overhead comparison between DSDV (proactive) and DSR (reactive) for a 100-node network

93.4 Handling New Node Joins

When a new node joins the network or moves into range of existing nodes, DSDV propagates route information to integrate the new node.

Sequence diagram showing DSDV response to new link formation with nodes detecting new neighbor, updating routing tables with shortened paths, incrementing sequence numbers, and broadcasting route updates to propagate new topology information — Figure 93.3: DSDV protocol behavior when a new link appears - route updates propagating through network

93.4.1 New Node Join Sequence

Scenario: Node K joins and comes within range of Node A

Step-by-step sequence showing new Node K joining the network: K broadcasts initial advertisement, Node A creates a 1-hop entry and forwards it, Node B creates a 2-hop entry, and Node D receives competing routes via A (2 hops) and B (3 hops), selecting the shorter path via A — Figure 93.4: DSDV new node join sequence showing route advertisement propagation

93.4.2 Step-by-Step Process

Node K broadcasts: <K, K, 0, 101>
- Destination: K (itself)
- Next Hop: K (direct)
- Hops: 0 (source)
- Seq #: 101 (initial)
Node A receives:
- Creates entry: <K, K, 1, 101> (1 hop via direct link to K)
- Propagates to neighbors: <K, A, 1, 101>
Node B receives from A:
- Creates entry: <K, A, 2, 101> (2 hops: B-A-K)
- Propagates to neighbors: <K, A, 2, 101>
Node D receives:
- From A: <K, A, 2, 101> (route: D-A-K, 2 hops)
- From B: <K, B, 3, 101> (route: D-B-A-K, 3 hops)
- Chooses route via A (same seq #, lower hop count)

Result: All nodes learn about Node K and establish shortest-path routes within a few update cycles.

Academic Resource: Cambridge Mobile and Sensor Systems

Cambridge lecture slide illustrating DSDV (Destination-Sequenced Distance Vector) protocol response when a new wireless link forms between nodes, showing how routing table updates propagate through the network with incremented sequence numbers to ensure all nodes learn the shorter path while preventing routing loops

DSDV protocol behavior when a new link appears in the network topology

Source: University of Cambridge, Mobile and Sensor Systems Course (Prof. Cecilia Mascolo)

93.5 Handling Link Breaks

When nodes move apart or links fail, routes must be invalidated quickly to prevent packets from being sent to unreachable destinations.

Sequence diagram illustrating DSDV link failure handling with nodes detecting broken link, marking affected routes with infinity metric, incrementing sequence numbers to invalidate stale paths, and broadcasting updates to trigger network-wide route recalculation — Figure 93.5: DSDV protocol behavior when a link breaks - routing table updates and sequence number increments

93.5.1 Link Break Scenario

Scenario: Link between Node D and Node F breaks

Ad hoc network mesh diagram with 8 nodes highlighting the failed wireless link between Node D and Node F, showing which routes are affected and which alternate paths remain available through other nodes — Figure 93.6: Ad hoc network topology showing broken link between Node D and Node F

93.5.2 Node D’s Response to Link Failure

Sequence diagram of Node D's DSDV link failure response: detecting the broken D-F link, setting hop count to infinity for affected routes, incrementing sequence numbers (even to odd), and broadcasting triggered updates to propagate invalidation across the network — Figure 93.7: DSDV link failure handling sequence showing route invalidation propagation

93.5.3 Invalidation Process

Detect failure: Node D notices no updates from F (timeout)
Mark routes as broken:
- Set hop count to infinity
- Increment sequence number (to make update “fresh”)
- This ensures broken route info propagates faster than stale good routes

Broadcast broken route updates:

<F, -, infinity, 077>  // Old seq was 076, now 077
<E, -, infinity, 393>  // Old seq was 392, now 393
<G, -, infinity, 129>  // Old seq was 128, now 129
<H, -, infinity, 051>  // Old seq was 050, now 051

Neighbors receive and process:
- See higher sequence number - route is fresher
- See infinity hop count - route is broken
- Delete or mark as invalid
Alternate routes converge:
- Other nodes with valid alternate paths broadcast their routes
- D eventually receives route to F via B-C-E-F
- New route installed

93.5.4 Why Increment Sequence Number?

Without incrementing, nodes might ignore the broken-route update because they have a cached entry with the same sequence number. Incrementing ensures the “broken” information propagates quickly.

Key Insight: The sequence number increment for broken routes is the mechanism that prevents routing loops during topology changes. A node detecting a failure generates a sequence number higher than any previously seen, guaranteeing all other nodes will accept the invalidation.

Putting Numbers to It

Sequence number increments ensure broken-route news travels faster than stale good-route news. Using rule \(seq_{broken} = seq_{old} + 1\), Worked example: Node D’s route to F had seq=76. When link D-F breaks at t=0, D broadcasts seq=77 with infinity metric. Node B still has seq=76 (working route). Because 77 > 76, B accepts the invalidation immediately, deleting the route within milliseconds. Without incrementing (both seq=76), DSDV’s “higher seq wins” tie-breaker fails. B keeps the stale route for 15+ seconds until next periodic update, causing \(15s \times 10pkts/s = 150\) packets sent into a dead end.

93.6 Knowledge Check

Concept Check: DSDV Link Failure Recovery

93.7 Convergence Time Analysis

Understanding how quickly DSDV converges after topology changes is critical for deployment planning.

93.7.1 Factors Affecting Convergence

Factor	Impact	Typical Value
Update interval	Time to first propagation	15 seconds
Network diameter	Hops for full propagation	2-10 hops
Processing delay	Per-node table processing	5-25 ms
Wireless delay	Per-hop transmission	1-10 ms

93.7.2 Convergence Calculation

For a network with diameter D hops and update interval T:

Best case (triggered updates work): D x (processing + transmission delay)
Worst case (wait for periodic): T + D x (processing + transmission delay)

Example: 8-hop diameter, 15s interval, 26ms per hop - Best case: 8 x 26ms = 208ms - Worst case: 15s + 208ms = 15.2 seconds

Interactive: DSDV Convergence Time Calculator

Show code

{
  const perHop = procDelayMs + txDelayMs;
  const bestMs = diameter * perHop;
  const worstMs = updateIntervalSec * 1000 + bestMs;
  return html`<div style="background:var(--bs-light,#f8f9fa);padding:1rem;border-radius:8px;border-left:4px solid #16A085;margin-top:0.5rem;">
    <p><strong>Per-hop delay:</strong> ${procDelayMs} + ${txDelayMs} = ${perHop} ms</p>
    <p><strong>Best-case convergence</strong> (triggered updates): <span style="color:#16A085;font-weight:bold">${bestMs} ms (${(bestMs/1000).toFixed(2)} s)</span></p>
    <p><strong>Worst-case convergence</strong> (wait for periodic): <span style="color:#E74C3C;font-weight:bold">${(worstMs/1000).toFixed(2)} seconds</span></p>
    <p style="font-size:0.9em;color:#7F8C8D">Worst case = update interval (${updateIntervalSec}s) + ${diameter} hops × ${perHop}ms</p>
  </div>`;
}

How It Works: DSDV Link Break Detection and Recovery

When a link fails in DSDV, the network recovers through a multi-step sequence:

Step 1: Failure Detection (at detecting node)

Node B expects periodic HELLO messages from neighbor C every 3 seconds
After 3 missed HELLOs (9 seconds), B concludes link B-C has failed
B immediately triggers route invalidation process

Step 2: Route Invalidation (broken route advertisement)

B sets hop count to INFINITY for all routes through C
B increments destination sequence number for each affected destination
Example: Route to D was (via C, 3 hops, seq=128) → becomes (-, ∞, seq=129)
Higher sequence number ensures this “broken” news overrides stale “working” routes

Step 3: Triggered Update Broadcast

B broadcasts incremental update containing only changed routes
Update format: <Destination, Next Hop=-, Hops=∞, Seq=old+1>
Neighbors receive invalidation and update their own tables

Step 4: Update Propagation (multi-hop spread)

Nodes receiving the update check if it affects their routes
If they routed through B to reach D, they also invalidate (set ∞, increment seq)
Invalidation propagates hop-by-hop across network within seconds

Step 5: Alternate Route Discovery

Nodes with valid alternate paths broadcast their routes
Example: Node E has route D via F (4 hops, seq=128)
E hears about broken route (seq=129), broadcasts its alternate route with seq=129
Nodes receive alternate routes and install them

Step 6: Convergence

Within 15-30 seconds (worst case: wait for periodic update cycle)
All nodes have updated routing tables avoiding the broken link
Network communication resumes via alternate paths

Try It Yourself: DSDV Link Failure Simulation

Exercise: Trace how DSDV handles a link failure in a 7-node network.

Given Topology:

A --- B --- C --- D
      |     |
      E --- F --- G

Initial Routing Table at Node A (after convergence): | Dest | Next Hop | Hops | Seq # | |——|———-|——|——-| | B | B | 1 | 100 | | C | B | 2 | 200 | | D | B | 3 | 300 | | E | B | 2 | 400 | | F | B | 3 | 500 | | G | B | 4 | 600 |

Failure Event: Link B-C breaks at t=0.

Your Tasks:

Mark which routes in A’s table are affected (hint: all routes through B-C)
Calculate B’s triggered update: which destinations get seq+1 and hops=∞?
After A receives B’s update, what does A’s table look like?
Trace how the broken route information propagates to nodes E, F, G
Identify an alternate path from A to D (hint: A-B-E-F-C-D)
Calculate the convergence time if updates take 26ms per hop and network diameter is 5 hops

What to Observe:

Invalidation (infinity metric) spreads faster than new routes form
Sequence number increment ensures stale caches are discarded
Some nodes may be temporarily unreachable during reconvergence

Expected Result: After ~200ms (best case with triggered updates) or ~15s (worst case waiting for periodic), alternate routes are established.

93.8 Why DSDV for IoT Ad Hoc Networks?

DSDV is often the first proactive routing protocol students encounter, and understanding its trade-offs explains why modern IoT protocols like RPL evolved differently.

When DSDV makes sense:

Networks with fewer than 50 nodes where routing table overhead is manageable
Relatively stable topologies with infrequent link changes (fewer than 1 change per minute)
Applications requiring instant forwarding – DSDV’s proactive tables mean zero route discovery delay for the first packet

When DSDV fails:

Large mobile networks (100+ nodes): A 100-node network generates 100 x 99 = 9,900 routing entries per full-dump cycle. At 15-second intervals, this consumes 10-15% of available bandwidth just for routing overhead
High mobility (walking speed or faster): Triggered updates cascade through the network, and by the time a route stabilizes, the topology has already changed again
Energy-constrained sensors: Every full-dump reception forces the radio into active mode, consuming 50-100 mW even for irrelevant routes to distant nodes

Worked Example: DSDV Routing Overhead for a 50-Node WSN

Scenario: A stationary 50-node environmental monitoring WSN using DSDV with 15-second full-dump intervals.

Calculation:

Each routing entry: destination (4 bytes) + next hop (4 bytes) + hop count (1 byte) + sequence number (2 bytes) = 11 bytes
Routes per node: 49 (one per destination)
Full-dump size per node: 49 x 11 = 539 bytes
Full-dump broadcasts per 15 seconds (all nodes): 50 x 539 = 26,950 bytes
Hourly overhead: 26,950 x (3,600/15) = 6.47 MB/hour for routing alone
At 250 kbps (typical for IEEE 802.15.4): routing consumes 6.47 MB / (250 kbps x 3,600s / 8) = 5.7% of bandwidth

Verdict: At 50 nodes and 5.7% overhead, DSDV is viable for this stationary deployment. However, doubling to 100 nodes quadruples routing entries (9,900 routes), pushing overhead past 20% – the point where routing traffic competes with sensor data for bandwidth. This quadratic scaling is why RPL (with its tree-based routing) replaced distance-vector approaches for large IoT networks.

93.9 Concept Relationships

Concept	Relationship	Connected Concept
Periodic Full-Dump Updates	Ensure network-wide consistency but generate	High Bandwidth Overhead
Incremental Triggered Updates	Propagate topology changes faster than	Periodic Update Cycles
Infinity Metric	Signals broken routes and triggers	Route Invalidation Propagation
Sequence Number Increment	Ensures broken route news overrides	Stale Cached Routes
Convergence Time	Depends on network diameter and	Update Propagation Mechanism

93.10 See Also

DSDV Fundamentals - Core routing table structure and sequence numbers
DSDV Evaluation and Trade-offs - Performance analysis and limitations
Ad Hoc Routing: Reactive (DSR) - On-demand alternative for topology changes
RPL Fundamentals - Tree-based routing for IoT
Routing Fundamentals - General routing principles

Interactive Quiz: Match Concepts

Interactive Quiz: Sequence the Steps

Common Pitfalls

1. Mixing Full Dump and Incremental Update Intervals

DSDV uses full dumps and incremental updates with different intervals. Applying the wrong interval calculation causes either excessive overhead (too frequent full dumps) or inconsistent routing tables (too infrequent full dumps missing incremental updates). Understand and apply both intervals correctly in analysis.

2. Forgetting the Metric Increment When Propagating Routes

When node A receives a route to destination D with metric 2 from neighbor B, node A stores metric 3 (2+1) for D via B. Forgetting to increment the metric gives incorrect hop counts, causing all nodes to think they are directly adjacent to every destination — a critical calculation error in routing analysis.

3. Not Handling Simultaneous Updates From Multiple Neighbors

A node may receive conflicting updates for the same destination from multiple neighbors simultaneously. DSDV’s tie-breaking rules (higher sequence number, then lower metric) must be applied consistently. Incorrect tie-breaking causes route oscillation and inconsistent forwarding.

4. Assuming Hello Timeouts Always Equal Link Failure

A missed hello message may indicate link failure, interference, or high channel load. DSDV immediately advertises a broken link after a configurable number of missed hellos. Tuning this threshold is critical — too sensitive causes false link failures; too tolerant delays recovery from genuine failures.

Label the Diagram

💻 Code Challenge

93.11 Summary

This chapter covered DSDV protocol operation and topology change handling:

Periodic Updates: Full routing tables broadcast every 15 seconds to ensure network-wide consistency
Incremental Updates: Triggered by topology changes to propagate important information quickly
New Node Integration: Joining nodes broadcast initial advertisements that propagate through the network
Link Break Handling: Failed routes marked with infinity metric and incremented sequence numbers for rapid invalidation
Sequence Number Role: Incrementing sequence numbers for broken routes ensures invalidation propagates faster than stale valid routes
Convergence Time: Depends on network diameter and whether triggered or periodic updates propagate the change

What’s Next

If you want to…	Read this
Evaluate DSDV performance	DSDV Evaluation
Compare with DSR reactive routing	DSR Fundamentals and Route Discovery
Study DSDV fundamentals	DSDV Proactive Routing
Learn hybrid ZRP routing	Ad Hoc Routing: Hybrid (ZRP)
Review all ad hoc routing protocols	Ad-Hoc Multi-Hop Routing