247  DSDV Protocol Operation: Updates and Topology Changes

247.1 Learning Objectives

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

  • Implement Periodic Updates: Describe the full-dump and incremental update mechanisms in DSDV
  • Handle New Node Joins: Trace how route advertisements propagate when nodes join the network
  • Manage Link Breaks: Explain the route invalidation process using infinity metrics and sequence numbers
  • Calculate Convergence Time: Estimate how long topology changes take to propagate through the network

247.2 Prerequisites

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

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

247.3.1 Periodic Full-Dump Updates

%% fig-alt: "DSDV periodic update sequence diagram showing nodes A, B, C, and D exchanging full routing tables every 15 seconds. Each node broadcasts its complete routing table to all neighbors simultaneously, triggering network-wide table synchronization. Demonstrates proactive routing's continuous maintenance overhead."

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%

sequenceDiagram
    participant A as Node A
    participant B as Node B
    participant C as Node C
    participant D as Node D

    Note over A,D: Every 15 seconds
    A->>B: Full routing table
    A->>D: Full routing table
    B->>A: Full routing table
    B->>C: Full routing table
    B->>D: Full routing table
    C->>B: Full routing table
    D->>B: Full routing table
    D->>F: Full routing table

    Note over A,D: All nodes update tables

Figure 247.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

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

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
graph TB
    subgraph DSDV_Overhead["DSDV Proactive Overhead (100 nodes)"]
        D1["Update Interval: 15 seconds"]
        D2["Messages per cycle:<br/>100 nodes x broadcast = 100"]
        D3["Messages per minute: 400"]
        D4["Active nodes needed: 100%<br/>(all must listen)"]
    end

    subgraph DSR_Overhead["DSR Reactive Overhead (10% active)"]
        R1["Discovery on-demand only"]
        R2["Active routes: 10 nodes"]
        R3["Messages per minute: 20-40<br/>(only when needed)"]
        R4["Sleeping nodes: 90%<br/>(massive energy savings)"]
    end

    subgraph Decision["Protocol Selection"]
        DEC{Traffic Pattern?}
        DEC -->|"Frequent, all nodes"| CHOOSE_D["Choose DSDV<br/>Zero latency worth overhead"]
        DEC -->|"Sparse, few nodes"| CHOOSE_R["Choose DSR<br/>90% energy savings"]
    end

    D3 --> DEC
    R3 --> DEC

    style DSDV_Overhead fill:#E67E22,color:#fff
    style DSR_Overhead fill:#16A085,color:#fff
    style Decision fill:#2C3E50,color:#fff
    style CHOOSE_D fill:#E67E22,color:#fff
    style CHOOSE_R fill:#16A085,color:#fff

Figure 247.2: Overhead comparison between DSDV (proactive) and DSR (reactive) for a 100-node network

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

247.4.1 New Node Join Sequence

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

%% fig-alt: "DSDV new node join sequence showing Node K broadcasting initial route advertisement, Node A discovering new neighbor and propagating route update, Nodes B and D learning multi-hop paths to K. Demonstrates route convergence: Node D receives two paths (2-hop via A, 3-hop via B) and selects shorter route based on DSDV's hop-count metric."

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%

sequenceDiagram
    participant K as Node K<br/>(New)
    participant A as Node A
    participant B as Node B
    participant D as Node D

    Note over K: Joins network
    K->>A: <K,K,0,101>
    Note over A: Add route to K
    A->>B: <K,A,1,101>
    A->>D: <K,A,1,101>
    Note over B,D: Add route to K via A
    B->>D: <K,A,2,101>
    Note over D: Choose best route

Figure 247.4: DSDV new node join sequence showing route advertisement propagation

247.4.2 Step-by-Step Process

  1. Node K broadcasts: <K, K, 0, 101>
    • Destination: K (itself)
    • Next Hop: K (direct)
    • Hops: 0 (source)
    • Seq #: 101 (initial)
  2. Node A receives:
    • Creates entry: <K, K, 1, 101> (1 hop via direct link to K)
    • Propagates to neighbors: <K, A, 1, 101>
  3. Node B receives from A:
    • Creates entry: <K, A, 2, 101> (2 hops: B-A-K)
    • Propagates to neighbors: <K, A, 2, 101>
  4. 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.

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)

247.6 Knowledge Check

Question: A multi-hop network has a route A-B-C-D. Link B-C fails. How do DSR and DSDV handle this differently?

DSR (reactive): Node B detects failure (no ACK from C) - sends ROUTE ERROR to source A - A removes cached route - initiates new route discovery - finds alternate path A-E-F-D. DSDV (proactive): Node B detects failure - sets metric to infinity - broadcasts update with incremented sequence number - all nodes update tables - eventually propagate new routes. Recovery time: DSR faster (targeted) but requires rediscovery. DSDV slower (network-wide propagation) but maintains alternate routes.

247.7 Convergence Time Analysis

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

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

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

247.8 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

Continue to DSDV Evaluation and Trade-offs to learn about DSDV’s limitations for IoT, detailed worked examples, and how to calculate routing overhead for your deployments.