Distance Vector Routing Program In C

Understanding Distance Vector Routing

Let's briefly examine the operation of Distance Vector Routing before progressing to the program implementation. To determine the optimal path to a specific destination, distance vector routing algorithms operate on the principle of neighboring nodes sharing routing data. Every node maintains a routing table that specifies the expenses associated with reaching other nodes within the network.

The algorithm refreshes the routing tables by selecting the most cost-effective routes while iterating through every network node. This process of updating the routing tables continues iteratively until they reach a stable and convergent state. Through exchanging information with neighboring nodes and evaluating the expenses associated with different paths to a specific destination, the routing tables are modified.

Program Design

We need to define the data structures and algorithmic procedures prior to commencing the development of the Distance Vector Routing application in C. Now, let's delve into the program's structure:

Data Structures

✅ Node: A network node is represented by this structure. It includes details including the node's ID, routing table information, and a list of nearby nodes.
✅ Routing Table: Every node in the network keeps a routing table with entries for every other node. Each entry contains the destination node ID, the next hop node ID, and the transportation expense needed to get there.

Functions

✅ initialize_node: This function creates a blank routing table and initializes a node with its ID.
✅ add_neighbor: The provided node's list of neighbors is expanded by this function by adding a neighbouring node.
✅ updateroutingtable: Based on data received from a node's nearby nodes, this function modifies the routing table of that node. It weighs the expenses of various routes to each destination and chooses the one with the lowest cost.
✅ printroutingtable: This function displays a node's routing table.
✅ main: The primary purpose for the program. The network is built up first, the nodes are connected, and the distance vector routing algorithm is run until convergence.

Program Implementation

Let's delve into the details of the C program implementation for distance vector routing. Here is the essential component:

Example


#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 10

// Structure to represent a node in the network
typedef struct Node {
    int id;
    int routing_table[MAX_NODES][3]; // [destination, next_hop, cost]
    int num_neighbors;
    struct Node* neighbors[MAX_NODES];
} Node;

// Function to initialize a node
void initialize_node(Node* node, int id) {
    node->id = id;
    node->num_neighbors = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        for (int j = 0; j < 3; j++) {
            node->routing_table[i][j] = -1;
        }
    }
}

// Function to add a neighbor to a node
void add_neighbor(Node* node, Node* neighbor) {
    if (node->num_neighbors < MAX_NODES) {
        node->neighbors[node->num_neighbors] = neighbor;
        node->num_neighbors++;
    }
}

// Function to update the routing table of a node
void update_routing_table(Node* node) {
    for (int i = 0; i < node->num_neighbors; i++) {
        Node* neighbor = node->neighbors[i];
        for (int j = 0; j < MAX_NODES; j++) {
            if (neighbor->routing_table[j][0] != -1) {
                int destination = neighbor->routing_table[j][0];
                int cost = neighbor->routing_table[j][2];
                int total_cost = cost + 1; // Assuming a cost of 1 for each hop
                if (node->routing_table[destination][0] == -1 ||
                    total_cost < node->routing_table[destination][2]) {
                    // Update the routing table entry
                    node->routing_table[destination][0] = destination;
                    node->routing_table[destination][1] = neighbor->id;
                    node->routing_table[destination][2] = total_cost;
                }
            }
        }
    }
}

// Function to print the routing table of a node
void print_routing_table(Node* node) {
    printf("Routing table of Node %d:\n", node->id);
    printf("---------------------------\n");
    printf("| Destination | Next Hop | Cost |\n");
    printf("---------------------------\n");
    for (int i = 0; i < MAX_NODES; i++) {
        if (node->routing_table[i][0] != -1) {
            printf("|     %2d      |    %2d    |  %2d  |\n", node->routing_table[i][0],
                   node->routing_table[i][1], node->routing_table[i][2]);
        }
    }
    printf("---------------------------\n");
}

int main() {
    // Create nodes
    Node nodes[MAX_NODES];
    for (int i = 0; i < MAX_NODES; i++) {
        initialize_node(&nodes[i], i);
    }

    // Add neighbors
    add_neighbor(&nodes[0], &nodes[1]);
    add_neighbor(&nodes[0], &nodes[2]);
    add_neighbor(&nodes[1], &nodes[0]);
    add_neighbor(&nodes[1], &nodes[3]);
    add_neighbor(&nodes[2], &nodes[0]);
    add_neighbor(&nodes[2], &nodes[3]);
    add_neighbor(&nodes[3], &nodes[1]);
    add_neighbor(&nodes[3], &nodes[2]);

    // Run distance vector routing algorithm
    int convergence = 0;
    int iteration = 0;
    while (!convergence) {
        convergence = 1;
        printf("Iteration %d\n", iteration);
        for (int i = 0; i < MAX_NODES; i++) {
            update_routing_table(&nodes[i]);
        }

        // Check for convergence
        for (int i = 0; i < MAX_NODES; i++) {
            for (int j = 0; j < MAX_NODES; j++) {
                if (nodes[i].routing_table[j][0] != -1 &&
                    nodes[i].routing_table[j][2] != nodes[i].routing_table[j][2]) {
                    convergence = 0;
                    break;
                }
            }
            if (!convergence) {
                break;
            }
        }

        // Print routing tables
        for (int i = 0; i < MAX_NODES; i++) {
            print_routing_table(&nodes[i]);
        }

        iteration++;
        printf("\n");
    }

    return 0;
}

Output:

Output


Iteration 0
Routing table of Node 0:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 1:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 2:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 3:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 4:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 5:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 6:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 7:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 8:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------
Routing table of Node 9:
---------------------------
| Destination | Next Hop | Cost |
---------------------------
---------------------------

Conclusion

In this article, we explored the implementation of a Distance Vector Routing application in the C programming language. This software manages and maintains the routing tables of various network nodes through the utilization of different data structures and functions. By executing the program, you can observe the convergence of routing tables and the optimal routes identified by the Distance Vector Routing algorithm. This methodology provides a solid foundation for further exploration and testing in the field of routing.