Skip to main content

Simulation of Link State Routing Algorithm

Link-State Routing Algorithm

The Link-State Routing Algorithm is a dynamic routing protocol that ensures all routers in a network have a consistent and complete view of the network's topology. Each router uses this information to compute the shortest path to every other router using Dijkstra's Algorithm.

Key Steps in Link-State Routing

  1. Neighbor Discovery:

    • Each router identifies its directly connected neighbors and the cost (link metrics) to reach them.
    • This is done using a protocol such as Hello packets.

  2. Link-State Advertisement (LSA) Flooding:

    • Each router creates a Link-State Packet (LSP) containing:
      • Its ID.
      • List of neighbors and their respective link costs.
    • The LSP is flooded across the entire network, ensuring all routers receive the same topology information.

  3. Topology Database Creation:

    • Each router constructs a Link-State Database (LSDB), which represents the entire network topology.
    • This database is built using the received LSAs from all routers.

  4. Shortest Path Calculation (Dijkstra's Algorithm):

    • Using the LSDB, each router computes the shortest path tree (SPT) with itself as the root.
    • The shortest path is computed using Dijkstra's Algorithm, which finds the least-cost path to each destination.

  5. Forwarding Table Construction:

    • Based on the SPT, the router builds its forwarding table, indicating the next hop to reach each destination.

C Program: Link-State Routing Algorithm
#include <stdio.h>
#include <limits.h>

#define MAX 10
#define INF 9999

void dijkstra(int graph[MAX][MAX], int nodes, int start) {
    int cost[MAX][MAX], distance[MAX], visited[MAX], next_hop[MAX];
    int i, j, count, min_distance, next_node;

    // Initialize cost matrix
    for (i = 0; i < nodes; i++) {
        for (j = 0; j < nodes; j++) {
            if (graph[i][j] == 0) {
                cost[i][j] = INF;
            } else {
                cost[i][j] = graph[i][j];
            }
        }
    }

    // Initialize distance, visited, and next_hop arrays
    for (i = 0; i < nodes; i++) {
        distance[i] = cost[start][i];
        visited[i] = 0;
        if (distance[i] != INF && i != start) {
            next_hop[i] = i; // Initially, the next hop is the direct neighbor
        } else {
            next_hop[i] = -1; // No route yet
        }
    }

    distance[start] = 0;
    visited[start] = 1;
    count = 1;

    // Main loop to calculate shortest paths
    while (count < nodes - 1) {
        min_distance = INF;
        next_node = -1;

        // Find the node with the smallest tentative distance
        for (i = 0; i < nodes; i++) {
            if (!visited[i] && distance[i] < min_distance) {
                min_distance = distance[i];
                next_node = i;
            }
        }

        if (next_node == -1) {
            break; // No more reachable nodes
        }

        visited[next_node] = 1;

        // Update distances for neighbors of the next node
        for (i = 0; i < nodes; i++) {
            if (!visited[i] && cost[next_node][i] != INF) {
                if (distance[next_node] + cost[next_node][i] < distance[i]) {
                    distance[i] = distance[next_node] + cost[next_node][i];
                    next_hop[i] = next_hop[next_node]; // Update next hop
                }
            }
        }
        count++;
    }

    // Print the results
    printf("\nRouting Table for Router %d:\n", start + 1);
    printf("Destination\tCost\tNext Hop\n");
    for (i = 0; i < nodes; i++) {
        if (i != start) {
            printf("%d\t\t%d\t", i + 1, distance[i]);
            if (next_hop[i] != -1) {
                printf("%d\n", next_hop[i] + 1);
            } else {
                printf("No route\n");
            }
        }
    }
}

int main() {
    int graph[MAX][MAX], nodes, i, j, start;

    printf("Enter the number of routers: ");
    scanf("%d", &nodes);

    printf("Enter the cost adjacency matrix (use 0 for no direct link):\n");
    for (i = 0; i < nodes; i++) {
        for (j = 0; j < nodes; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    printf("Enter the source router: ");
    scanf("%d", &start);

    dijkstra(graph, nodes, start - 1);

    return 0;
}

Try The Following 

Output:

Enter the number of routers: 4
Enter the cost adjacency matrix (use 0 for no direct link):
0 1 4 0
1 0 2 6
4 2 0 3
0 6 3 0
Enter the source router: 1

Routing Table for Router 1:
Destination     Cost    Next Hop
2               1       2
3               3       2
4               6       2

Program Explanation

  1. Graph Input:

    • The user enters the adjacency matrix, where:
      • graph[i][j] represents the cost of the link between router i and router j.
      • Use 0 to indicate no direct connection between routers.

  2. Cost Matrix Initialization:

    • The cost matrix is derived from the adjacency matrix. If graph[i][j] == 0, the cost is set to INF (9999).

  3. Dijkstra's Algorithm:

    • Initialization:
      • The distance array stores the shortest known distances from the source to each router.
      • The visited array tracks whether a router's shortest path has been finalized.
      • The next_hop array tracks the next hop to reach each destination.
    • Iteration:
      • Find the nearest unvisited router.
      • Update distances to its neighbors if a shorter path is found.
    • Termination:
      • Stop when all reachable routers have been visited.

  4. Routing Table:

    • For each destination, the table shows:
      • Destination router.
      • Total cost of the shortest path.
      • The next hop router on the shortest path.

Comments

Post a Comment

Popular posts from this blog

Server/Client Communication-python

The basic mechanisms of client-server setup are: A client app send a request to a server app.  The server app returns a reply.  Some of the basic data communications between client and server are: File transfer - sends name and gets a file.  Web page - sends url and gets a page.  Echo - sends a message and gets it back.  Client server communication uses socket.              To connect to another machine, we need a socket connection. What's a connection?  A relationship between two machines, where two pieces of software know about each other. Those two pieces of software know how to communicate with each other. In other words, they know how to send bits to each other. A socket connection means the two machines have information about each other, including network location (IP address) and TCP port. (If we can use anology, IP address is the phone number and the TCP port is the extension).  A so...
19 comments
Read more

Banker's Algorithm

Banker's algorithm is a deadlock avoidance algorithm. It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not. Consider there are n account holders in a bank and the sum of the money in all of their accounts is S. Everytime a loan has to be granted by the bank, it subtracts the loan amount from the total money the bank has. Then it checks if that difference is greater than S. It is done because, only then, the bank would have enough money even if all the n account holders draw all their money at once. Banker's algorithm works in a similar way in computers. Whenever a new process is created, it must exactly specify the maximum instances of each resource type that it needs. Let us assume that there are n processes and m resource types. Some data structures are used to implement the banker's algorithm. They are: Available: It is an array of length m . It represents the number of available resourc...
7 comments
Read more

Inter Process Communication-Message Queue

Interprocess communication (IPC) is a set of programming interfaces that allow a programmer to coordinate activities among different program processes that can run concurrently in an operating system. This allows a program to handle many user requests at the same time. Since even a single user request may result in multiple processes running in the operating system on the user's behalf, the processes need to communicate with each other. The IPC interfaces make this possible. Each IPC method has its own advantages and limitations so it is not unusual for a single program to use all of the IPC methods . Message Based Communication Messages are a very general form of communication. Messages can be used to send and receive formatted data streams between arbitrary processes. Messages may have types. This helps in message interpretation. The type may specify appropriate permissions for processes. Usually at the receiver end, messages are put in a queue. Messages may also be fo...
13 comments
Read more