Link State Routing Algorithm

What is a Link State Routing Algorithm?

Before learning about the Link State Routing Algorithm, let us briefly discuss the term Routing.

Routing is a process of establishing the routes that data packets must follow to reach the destination. In this process, a routing table is created, which contains the information regarding routes that data packets follow. Now, various routing algorithms are there which are used to decide the best optimal route that the incoming data packet must be transmitted.

The best or optimal path is the path from the source to the destination router, having the least connection cost. For example, refer to the routers shown in the image below.

If a packet needs to be transmitted from Router-1 to Router-2, then it can follow two paths.

1. Directly from Router-1 to Router-2, the cost of this traveling is 6.
2. It can also go from Router-1 to Router-2, via path: Router-1 --> Router-3 --> Router-2. The cost of this traveling is (2 + 3) = 5.

So, the data packet will be sent from the second path i.e. Router-1 --> Router-3 --> Router-2.

The Link State Routing Algorithm is an interior protocol used by every router to share information or knowledge about the rest of the routers on the network. The link state routing algorithm is distributed by which every router computes its routing table.

With the knowledge of the network topology, a router can make its routing table. Now, for developing the routing table, a router uses a shortest path computation algorithm like Dijkstra's algorithm along with the knowledge of the topology. The routing table created by each router is exchanged with the rest of the routers present in the network, which helps in faster and more reliable delivery of data.

A router does not send its entire routing table with the rest of the routers in the inter-network. It only sends the information of its neighbors. A router broadcasts this information and contains information about all of its directly connected routers and the connection cost.

Now, the process of transferring the information about a router's neighbors is termed flooding. A router transfers the information to all the inter-network routers except its neighbors. Every router that receives the information sends the information copies to all its neighbors. In this way, all the routers of the inter-connected network have the same copy of the information.

This information exchange only occurs when there is a change in the information. Hence, the link state routing algorithm is effective. Refer to the image below for the basic overview of the router and updation done by the link state routing algorithm.

Link State Routing Protocols

A routing protocol is a routing algorithm that provides the best path from the source to the destination.

In the link state routing protocol, a router transmits its IP address, MAC address, and signature to its neighboring routers. Now, using the information (i.e. IP address, MAC address, and signature), the neighboring routers create a record by combining the IP address and the MAC. This information helps the router to transmit the data packet through the optimal path. It also tells a router about the various possible paths.

Let us discuss the various protocols that use the link state routing protocol.

OSPF or Open Shortest Path First is a routing protocol that uses the link state routing algorithm to exchange information (about neighboring routers, cost of the route, etc.) among the inter-network routers.

The OLSR or Optimized Link State Routing Protocol is an optimized link state routing protocol that is used in mobile ad hoc networks and wireless ad hoc networks. The OLSR sends a hello message to identify the connected neighboring routers and the connection cost. Along with the hello message, it also uses the Topology Control messages.

Phases of Link State Routing

Let us now discuss the two phases of the link state routing algorithm. The two phases of the link state routing algorithm are:

1. Reliable Flooding: As discussed, a router shares its information using the flooding technique. In this first phase, the information about neighbors is gathered and transmitted. The first phase, i.e. reliable flooding, is divided into two phases: the initial state and the final state.

   • Initial State: In the initial state of reliable flooding, each router gets to know the cost of connection of its neighbors.
   • Final State: In the final state of the reliable flooding, the information about the entire router network (graph) is known by each router.

2. Route Calculation: In the second phase, i.e., the route calculation, every router uses the shortest path computation algorithm like Dijkstra's algorithm to calculate the cheapest i.e., most optimal routes to every router.

Features of Link State Routing Algorithm

Let us now discuss the various features of the link state routing algorithm.

1. Link state packet: The link state packet is a small data packet containing the information about the routing information.
2. Link state database: The information about a particular router's neighbors and the cost of connection is gathered in the form of the link state database.
3. Shortest path computation algorithm: As discussed above, the Dijkstra Algorithm is used to compute the shortest path or the most optimal path to reach a certain router.
4. Routing table: Routing is a table containing the list of all the paths and interfaces.