DISTANCE VECTOR ROUTING
ALGORITHM
Routing Table Generation at Each Node
Subject: Computer Networks
Distance Vector Routing Algorithm | Page 1
1. Aim
To implement the Distance Vector Routing (DVR) algorithm and compute the routing tables at
each node of a given subnet. The subnet is represented as a weighted graph where nodes are
routers and edge weights denote the delay (cost) between adjacent nodes. The program
iteratively applies the Bellman-Ford equation until all routing tables converge.
2. Software Requirements
Component Specification
Operating System Windows 10/11 or Linux (Ubuntu 20.04+)
Programming Language Python 3.8+ / C / Java
IDE / Editor VS Code, PyCharm, or any text editor
Compiler / Interpreter Python 3.8+ / GCC / JDK 11+
Libraries / Modules Standard I/O only (no external dependencies)
RAM Minimum 512 MB
Storage Minimum 50 MB free space
3. Description
3.1 What is Distance Vector Routing?
Distance Vector Routing is a dynamic routing protocol based on the Bellman-Ford shortest-path
algorithm. Each router (node) maintains a routing table that records the shortest known distance
(delay/cost) to every other node in the network, along with the next-hop neighbor to reach that
destination. Routers exchange their distance vectors only with direct neighbors and update their
own tables accordingly — a process called distributed asynchronous computation.
DVR is used in protocols such as RIP (Routing Information Protocol) and is foundational to
understanding how routers cooperate to find optimal paths without any single node having
global knowledge of the network.
3.2 Bellman-Ford Equation
The core update rule at each node is:
D(x, y) = min over all neighbors v { c(x, v) + D(v, y) }
Distance Vector Routing Algorithm | Page 2
Where D(x, y) is the estimated cost from node x to destination y, c(x, v) is the direct link cost
from x to neighbor v, and D(v, y) is neighbor v's estimated cost to y.
3.3 Example Subnet Graph
The following 5-node subnet (A, B, C, D, E) is used. Edge weights represent delay in
milliseconds between directly connected routers:
Subnet Topology Diagram
A
/ \
2 6
/ \
B---3---C
| |
1 4
| |
D---5---E
Edge list (bidirectional):
Link Node 1 Node 2 Delay (ms)
1 A B 2
2 A C 6
3 B C 3
4 B D 1
5 C E 4
6 D E 5
3.4 Algorithm Steps
• Initialize each node's routing table: distance to itself = 0, distance to all others = infinity.
• Each node shares its distance vector with all directly connected neighbors.
• Each node updates its own table using the Bellman-Ford equation upon receiving
neighbor vectors.
• Steps 2 and 3 repeat iteratively until no routing table changes (convergence).
• Final routing tables at each node show the optimal cost and next-hop to every
destination.
Distance Vector Routing Algorithm | Page 3
4. Expected Output — Final Routing Tables
After convergence (typically 3–4 iterations for this graph), the routing tables at each node are as
shown below. Each table lists the destination node, minimum cost (delay in ms), and the next
hop.
Node A — Routing Table
Destination Cost (ms) Next Hop
A 0 —
B 2 B
C 5 B
D 3 B
E 8 B
Node B — Routing Table
Destination Cost (ms) Next Hop
A 2 A
B 0 —
C 3 C
D 1 D
E 6 D
Node C — Routing Table
Destination Cost (ms) Next Hop
A 5 B
B 3 B
C 0 —
D 4 B
E 4 E
Distance Vector Routing Algorithm | Page 4
Node D — Routing Table
Destination Cost (ms) Next Hop
A 3 B
B 1 B
C 4 B
D 0 —
E 5 E
Node E — Routing Table
Destination Cost (ms) Next Hop
A 8 D
B 6 D
C 4 C
D 5 D
E 0 —
5. Summary
The Distance Vector Routing algorithm demonstrates how distributed routers can collectively
determine optimal paths across a network without any single router knowing the global topology.
Each router only communicates with its immediate neighbors, yet through iterative exchange
and the Bellman-Ford update rule, all routers converge to a globally consistent and optimal set
of routing tables.
In the example subnet with 5 nodes and 6 weighted links, the algorithm converges after a few
iterations. For instance, Node A reaches Node E (which is not directly connected) at a total cost
of 8 ms via the path A -> B -> D -> E, which is the shortest available path given the link delays.
Key characteristics of DVR reinforced by this program:
• Decentralized computation: each node calculates routes independently using only
neighbor information.
• Convergence: the algorithm terminates when no further updates occur across any node.
• Count-to-Infinity Problem: a known limitation where routing loops can cause costs to
increment indefinitely upon a link failure — mitigated in practice by split horizon or
poison reverse techniques.
Distance Vector Routing Algorithm | Page 5
• Protocol basis: DVR forms the foundation of RIP (Routing Information Protocol), widely
used in smaller networks.
This experiment strengthens understanding of dynamic routing, shortest-path computation, and
the trade-offs between distributed versus link-state routing approaches (such as Dijkstra-based
OSPF).
Distance Vector Routing Algorithm | Page 6