Distance Vector Routing (DVR) is a decentralised routing protocol where each router maintains a table containing its estimated shortest distance to every other router in the network. Routers exchange these distance vectors with their neighbours, and each router updates its own table whenever a shorter path is discovered. The algorithm continues iterating until no table changes occur — a state known as convergence. DVR is the conceptual basis for real-world protocols such as RIP (Routing Information Protocol).
This C++ program simulates DVR on a user-defined network. The user specifies the number of nodes and the distances between directly connected node pairs. The program iteratively updates routing tables until convergence and then prints each node’s final routing table showing the shortest distance and the next-hop node to reach every destination.
C++ Program: Distance Vector Routing Algorithm
#include <iostream>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max(); // Represents no known path
int main()
{
int nodeCount;
cout << "\n Enter Number of Nodes: ";
cin >> nodeCount;
// directDist[src][dst] = direct link cost between src and dst (INF if no direct link)
int directDist[50][50];
for (int src = 0; src < nodeCount; src++)
{
for (int dst = 0; dst < nodeCount; dst++)
{
directDist[src][dst] = (src == dst) ? 0 : INF;
}
}
// Assign node labels A, B, C, D, ...
char nodeName[50];
for (int nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++)
{
nodeName[nodeIndex] = 'A' + nodeIndex;
}
// Read direct link distances between each pair of nodes
for (int src = 0; src < nodeCount; src++)
{
for (int dst = src + 1; dst < nodeCount; dst++)
{
int linkCost;
cout << "\n Enter Distance between "
<< nodeName[src] << " - " << nodeName[dst]
<< " (use -1 for no connection): ";
cin >> linkCost;
if (linkCost != -1)
{
directDist[src][dst] = linkCost;
directDist[dst][src] = linkCost; // Assume symmetric (undirected) links
}
}
}
// viaNode[src][dst] = intermediate node used on the current best path from src to dst
int viaNode[50][50];
for (int src = 0; src < nodeCount; src++)
for (int dst = 0; dst < nodeCount; dst++)
viaNode[src][dst] = -1;
// bestDist[src][dst] = best known shortest distance from src to dst
int bestDist[50][50];
// --- Iterative Distance Vector update loop ---
bool updated;
do
{
updated = false;
for (int src = 0; src < nodeCount; src++)
{
for (int dst = 0; dst < nodeCount; dst++)
{
bestDist[src][dst] = directDist[src][dst];
viaNode[src][dst] = src; // Default: reach dst directly from src
// Try routing through each intermediate node k
for (int via = 0; via < nodeCount; via++)
{
if (directDist[src][via] != INF && directDist[via][dst] != INF)
{
int candidateDist = directDist[src][via] + directDist[via][dst];
if (candidateDist < bestDist[src][dst])
{
bestDist[src][dst] = candidateDist;
viaNode[src][dst] = via;
updated = true;
}
}
}
}
}
// Propagate the improved distances back into directDist for the next iteration
for (int src = 0; src < nodeCount; src++)
for (int dst = 0; dst < nodeCount; dst++)
directDist[src][dst] = bestDist[src][dst];
} while (updated); // Repeat until no further improvements (convergence)
// --- Print final routing tables ---
cout << "\n After Convergence:";
for (int src = 0; src < nodeCount; src++)
{
cout << "\n\n" << nodeName[src] << " Routing Table";
cout << "\n Node\tDist\tVia";
for (int dst = 0; dst < nodeCount; dst++)
{
cout << "\n" << nodeName[dst] << "\t";
if (bestDist[src][dst] == INF)
cout << "INF";
else
cout << bestDist[src][dst];
cout << "\t";
if (src == viaNode[src][dst])
cout << "-"; // Direct connection, no intermediate hop
else
cout << nodeName[viaNode[src][dst]];
}
}
cout << "\n";
return 0;
}
How the Code Works
Step 1 — Initialisation: The directDist matrix is filled with INF for all pairs except self-loops (cost 0). Node names A, B, C, … are assigned automatically.
Step 2 — Input: For each pair of nodes, the user enters the direct link cost or -1 for no connection. Because links are symmetric, both directDist[src][dst] and directDist[dst][src] are set to the same value.
Step 3 — Distance Vector Update: In each iteration, for every source-destination pair, the algorithm tries all possible intermediate nodes (via). If routing through via yields a shorter total distance than the currently known best, bestDist and viaNode are updated and the updated flag is set.
Step 4 — Propagation: After each full sweep, the improved distances are written back into directDist so subsequent iterations can build on them. This simulates routers sharing their updated distance vectors with neighbours.
Step 5 — Convergence: The outer do-while loop exits as soon as a full sweep produces no updates, meaning all routes have stabilised.
Step 6 — Output: For each source node, a routing table is printed showing the shortest distance and the intermediate node (via) to reach every destination. A - in the Via column means the destination is directly reachable with no intermediate hop.
Sample Output
Enter Number of Nodes: 4
Enter Distance between A - B (use -1 for no connection): 1
Enter Distance between A - C (use -1 for no connection): -1
Enter Distance between A - D (use -1 for no connection): 4
Enter Distance between B - C (use -1 for no connection): 2
Enter Distance between B - D (use -1 for no connection): -1
Enter Distance between C - D (use -1 for no connection): 3
After Convergence:
A Routing Table
Node Dist Via
A 0 -
B 1 -
C 3 B
D 4 -
B Routing Table
Node Dist Via
A 1 -
B 0 -
C 2 -
D 5 C
C Routing Table
Node Dist Via
A 3 B
B 2 -
C 0 -
D 3 -
D Routing Table
Node Dist Via
A 4 -
B 5 C
C 3 -
D 0 -
Output Explanation
With 4 nodes and direct links A–B=1, A–D=4, B–C=2, C–D=3, the algorithm discovers that A can reach C more cheaply via B (cost 1+2=3) than via any direct path. Node B reaches D via C (cost 2+3=5), since there is no direct B–D link. The - in the Via column confirms a direct link is used for those entries. All routing tables are consistent at convergence.
See Also
- Implementation of Dijkstra Algorithm in C++ — centralised shortest-path algorithm
- Implementation of Hamming Code in C++ — error correction in transmitted frames
- Implementation of CRC Algorithm in C++ — error detection using polynomial division
- Illustrating Working of Bit-Map Protocol in C++ — MAC layer channel access
- Implementing Socket Programming in Java — TCP client-server communication
Conclusion
Distance Vector Routing elegantly shows how distributed algorithms converge to a globally optimal solution through purely local information exchange. Each router knows only its own distances and what its neighbours have told it — yet the entire network converges to correct shortest paths. This implementation uses a flat array-based approach that is easy to trace; a production DVR system would replace the arrays with per-router message-passing threads and introduce timers to handle link failures and the count-to-infinity problem.