Simulation of Distance Vector Routing Algorithm

Here’s a simple C program that simulates the Distance Vector Routing Protocol. The program models a small network of routers and computes the shortest paths between them

#include <stdio.h>

#define INFINITY 9999

#define MAX 10

int cost[MAX][MAX], dist[MAX][MAX], next_hop[MAX][MAX];

int nodes;

void initialize() {

    for (int i = 0; i < nodes; i++) {

        for (int j = 0; j < nodes; j++) {

            dist[i][j] = cost[i][j];

            next_hop[i][j] = j;

        }

    }

}

void updateRoutes() {

    int updated;

    do {

        updated = 0;

        for (int i = 0; i < nodes; i++) {

            for (int j = 0; j < nodes; j++) {

                for (int k = 0; k < nodes; k++) {

                    if (dist[i][j] > dist[i][k] + dist[k][j]) {

                        dist[i][j] = dist[i][k] + dist[k][j];

                        next_hop[i][j] = next_hop[i][k];

                        updated = 1;

                    }

                }

            }

        }

    } while (updated);

}

void display() {

    for (int i = 0; i < nodes; i++) {

        printf("\nRouter %d's Routing Table:\n", i + 1);

        printf("Destination\tCost\tNext Hop\n");

        for (int j = 0; j < nodes; j++) {

            printf("%d\t\t%d\t%d\n", j + 1, dist[i][j], next_hop[i][j] + 1);

        }

    }

}

int main() {

    printf("Enter the number of routers: ");

    scanf("%d", &nodes);

    printf("Enter the cost matrix (enter 9999 for no direct link):\n");

    for (int i = 0; i < nodes; i++) {

        for (int j = 0; j < nodes; j++) {

            scanf("%d", &cost[i][j]);

            if (i == j) {

                cost[i][j] = 0;

            }

        }

    }

    initialize();

    updateRoutes();

    display();

    return 0;

}

Try the following example

Output

Enter the number of routers: 5

Enter the cost matrix (enter 9999 for no direct link):

0 1 9999 9999 9999

1 0 6 9999 3

9999 6 0 2 9999

9999 9999 2 0 4

9999 3 9999 4 0

Router 1's Routing Table:

Destination     Cost    Next Hop

1               0       1

2               1       2

3               7       2

4               8       2

5               4       2

Router 2's Routing Table:

Destination     Cost    Next Hop

1               1       1

2               0       2

3               6       3

4               7       5

5               3       5

Router 3's Routing Table:

Destination     Cost    Next Hop

1               7       2

2               6       2

3               0       3

4               2       4

5               6       4

Router 4's Routing Table:

Destination     Cost    Next Hop

1               8       5

2               7       5

3               2       3

4               0       4

5               4       5

Router 5's Routing Table:

Destination     Cost    Next Hop

1               4       2

2               3       2

3               6       4

4               4       4

5               0       5

How the Program Works:

1. Input:

   • The user inputs the number of routers.
   • A cost matrix is provided, where 9999 represents no direct link between routers.

2. Initialization:

   • The distance table is initialized with the cost matrix. Each router sets its next hop to the destination directly if a direct link exists.

3. Updating Routes:

   • The Bellman-Ford algorithm iterates over the nodes and updates the distance vector until no further updates are needed.

4. Output:

• The program prints each router’s routing table, showing the cost to each destination and the next hop.

1. Input and Initialization

Step 1: Input the Number of Routers

• The user is prompted to enter the number of routers (nodes).
• Each router is treated as a node in the network.

Step 2: Input the Cost Matrix

• A matrix (cost[MAX][MAX]) is used to store the cost of direct links between routers:
  • If two routers are directly connected, the matrix holds the cost of that link.
  • If there is no direct link, the value INFINITY (9999) is used.
  • The cost to reach itself (cost[i][i]) is always 0.

Step 3: Initialize Distance and Next Hop

• The dist[MAX][MAX] matrix stores the shortest known distance to each destination for every router. Initially, it’s set to the values in the cost matrix.
• The next_hop[MAX][MAX] matrix stores the next router to which the packet should be sent to reach the destination. Initially, it’s set to the direct neighbor (j) for each destination.

---

2. Update the Routing Tables

The algorithm updates the routing tables iteratively to compute the shortest path using the Bellman-Ford principle.

Step 1: Iterate Over Each Router Pair

• The program checks if the cost of reaching a destination (j) through an intermediate router (k) is less than the current known cost (dist[i][j]).
• Formula: $$dist[i][j]>dist[i][k]+dist[k][j]$$ If true, the route is updated:
  • dist[i][j] = dist[i][k] + dist[k][j]
  • next_hop[i][j] = next_hop[i][k]

Step 2: Repeat Until Convergence

• The algorithm keeps updating the routing table until no further updates are made (no change in dist).
• This ensures the network has converged, and all routers have consistent routing tables.

---

3. Display the Routing Tables

Step 1: Print Routing Table for Each Router

• For each router (i), the routing table is displayed with:
• Destination: The target router.
• Cost: The total cost to reach the destination.
• Next Hop: The immediate neighbor through which the destination can be reached with the minimum cost.

Key Points:

• This program simulates a small network and demonstrates how routers adjust their routing tables based on neighbors’ information.
• The cost matrix can be modified to test different topologies and scenarios