Implementation of Distance Vector Routing (DVR) Algorithm in C++

Distance Vector Routing (DVR) is a fundamental algorithm in computer networking used for finding the shortest path between nodes in a network. This blog post explores a C++ implementation of the DVR algorithm, demonstrating how it calculates and updates routing tables dynamically.

What is Distance Vector Routing?

DVR is a decentralized routing protocol where each router maintains a table containing the shortest distance to every other router in the network. Periodically, routers exchange this information with their neighbors, updating their tables accordingly.

C++ Implementation

The following C++ code demonstrates the DVR algorithm by:

Initializing a network graph with user-defined distances.
Sharing distance vectors between nodes.
Iteratively updating routing tables until convergence.

#include <iostream>
#include <limits>

using namespace std;

const int INF = std::numeric_limits<int>::max();

int main() {
    int graph[50][50], via[50][50], final[50][50];
    int i, j, k, t;
    int nn;

    cout << "\n Enter Number of Nodes: ";
    cin >> nn;

    // Initialize graph with INF
    for (i = 0; i < nn; i++) {
        for (j = 0; j < nn; j++) {
            graph[i][j] = (i == j) ? 0 : INF;
        }
    }

    // Dynamic character allocation for node names
    char ch[50];
    for (i = 0; i < nn; i++) {
        ch[i] = 'A' + i; // Assign A, B, C, D...
    }

    // Get input distances
    for (i = 0; i < nn; i++) {
        for (j = i + 1; j < nn; j++) {
            cout << "\n Enter Distance between " << ch[i] << " - " << ch[j] << " (use -1 for no connection): ";
            cin >> t;
            if (t != -1) {
                graph[i][j] = graph[j][i] = t;
            }
        }
    }

    // Initialize via table
    for (i = 0; i < nn; i++) {
        for (j = 0; j < nn; j++) {
            via[i][j] = -1;
        }
    }

    bool updated;
    do {
        updated = false;

        // Distance vector algorithm: Updating distances
        for (i = 0; i < nn; i++) {
            for (j = 0; j < nn; j++) {
                final[i][j] = graph[i][j];
                via[i][j] = i;

                for (k = 0; k < nn; k++) {
                    if (graph[i][k] != INF && graph[k][j] != INF) {
                        int newDist = graph[i][k] + graph[k][j];
                        if (newDist < final[i][j]) {
                            final[i][j] = newDist;
                            via[i][j] = k;
                            updated = true;
                        }
                    }
                }
            }
        }
    } while (updated); // Repeat until no changes occur

    // Displaying final routing table
    cout << "\nAfter Convergence:";
    for (i = 0; i < nn; i++) {
        cout << "\n" << ch[i] << " Table";
        cout << "\nNode\tDist\tVia";
        for (j = 0; j < nn; j++) {
            cout << "\n" << ch[j] << "\t";
            if (final[i][j] == INF)
                cout << "INF";
            else
                cout << final[i][j];
            cout << "\t";
            if (i == via[i][j])
                cout << "-";
            else
                cout << ch[via[i][j]];
        }
    }
    return 0;
}

Explanation of Key Components of the Code

1. Graph Initialization

The program initializes a graph where INF represents no direct path between nodes.

for (i = 0; i < nn; i++) {
    for (j = 0; j < nn; j++) {
        graph[i][j] = (i == j) ? 0 : INF;
    }
}

2. User Input

Users enter distances between nodes, setting -1 for no connection.

cout << "\n Enter Distance between " << ch[i] << " - " << ch[j] << " : ";
cin >> t;
if (t != -1) {
    graph[i][j] = graph[j][i] = t;
}

3. Distance Sharing

Each node shares its distance vector with neighbors.

for (i = 0; i < nn; i++) {
    for (j = 0; j < nn; j++) {
        via[i][j] = -1;
    }
}

4. Routing Table Updates

The program iterates over possible paths, updating routing tables with the shortest known distance.

if (graph[i][k] != INF && graph[k][j] != INF) {
    int newDist = graph[i][k] + graph[k][j];
    if (newDist < final[i][j]) {
        final[i][j] = newDist;
        via[i][j] = k;
        updated = true;
    }
}

5. Iteration Until Convergence

The algorithm continues updating the tables until no further changes occur, ensuring full propagation of shortest paths.

} while (updated); // Repeat until no changes occur

6. Final Display

The updated routing table displays the shortest paths and their corresponding next-hop nodes.

cout << "\n" << ch[i] << " Table";
cout << "\nNode\tDist\tVia";

Sample Input & Output

Input:

Enter Number of Nodes: 3
Enter Distance between A - B: 4
Enter Distance between A - C: 2
Enter Distance between B - C: 5

Output:

A Table
Node   Dist   Via
A      0      -
B      4      -
C      2      -

B Table
Node   Dist   Via
A      4      -
B      0      -
C      5      -

C Table
Node   Dist   Via
A      2      -
B      5      -
C      0      -

This implementation of Distance Vector Routing in C++ demonstrates how routers can determine the shortest paths between nodes. By iterating until convergence, the algorithm ensures accurate and stable routing tables. The DVR algorithm is a foundational concept in network routing and is widely used in real-world protocols like RIP (Routing Information Protocol).

Try modifying the code to experiment with different network topologies and see how the algorithm adapts!

@ankurm