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

CSL 332 Networking Lab KTU 2019 Scheme - Dr Binu V P

CSL 332 Networking Lab KTU BTech 2019 Scheme About Me Scheme Syllabus Experiments 1.Learn the Networking Commands and Network Configuration Files     Basic networking commands     More Networking commands     Network configuration Files     View the configuration and address of your network interface     Network Connectivity      View Active TCP connections     MAC address of another machine using ARP  2.  System calls in Network Programming 3.  Simple TCP/IP Client Server Program 4.  Simple UDP Client Server Program 5.Application Programs     Concurrent UDP Time Server     Checking Prime Numbers 6. Simulate ARQ Protocols  / sliding window protocols          Stop and Wait           Go-Back-N          Selective Repeat  7. Routing Protocols - Distance Vector and Link State   ...
3 comments
Read more

Stop and Wait ARQ

Here's a simple C program that demonstrates the Stop-and-Wait ARQ protocol. This basic implementation simulates the sender transmitting packets one at a time and waiting for an acknowledgment from the receiver. If the acknowledgment is not received, the sender retransmits the packet. Key Points: The sender sends one packet at a time. If the receiver acknowledges it (ACK), the sender sends the next packet. If the acknowledgment is lost, the sender retransmits after a timeout. C Program: Stop-and-Wait ARQ Simulation #include <stdio.h> #include <stdlib.h> #include <time.h> #include <unistd.h>  // for sleep() #define TIMEOUT 3  // Timeout duration in seconds #define TOTAL_PACKETS 5  // Number of packets to send int simulate_acknowledgment() {     // Simulate a 70% chance of successful acknowledgment     return rand() % 10 < 7; } int main() {     srand(time(0));  // Seed for random number generation     i...
Post a Comment
Read more

Simple TCP/IP Client Server Example

Socket Programming in C Socket programming is a method used in network communication that allows data to be sent and received between devices. It is a critical concept in computer networking and is widely used to develop client-server applications. In this blog post, we will explore the fundamentals of socket programming in C, focusing on TCP (Transmission Control Protocol) for reliable, connection-oriented communication. What is Socket Programming? Socket programming enables communication between two nodes on a network. A server listens for incoming client requests, and the client connects to the server to facilitate data exchange. Sockets provide a communication channel between two processes, either on the same machine or different machines connected via a network. Types of Sockets Stream Sockets (SOCK_STREAM): Uses TCP for communication. Provides reliable, connection-oriented communication. Data is transmitted in order and without loss. Datagram Sockets (SOCK_DGRAM): Uses UDP (User ...
Post a Comment
Read more