What is the idea behind link state routing?

There are two main classes of the routing protocols out of which one is the link state routing protocol on which we shall focus in this article. The other class of the routing protocols is the distance vector routing protocols.

In computer communications, the link state routing protocol is applied in the packet switching networks. 

We can give two main examples of the link state routing protocol namely:

1. IS – IS i.e., intermediate system to intermediate system and
2. OSPF i.e., the open shortest path first

Almost every switching node is capable of performing the link – state routing in the network. Switching nodes can be defined as the nodes that can forward the packets. We call these nodes as routers in the internet.

Idea behind the Link State Routing

 

- A map is constructed by every node concerning its connectivity with the network. 

- This map is actually in a graph’s form. 

- This graph shows all the connections that exist between the various nodes in the graph. 

- The next “best logical path” is then calculated independently by each node to every destination in the network based up on its possibility. 

- The routing table of the node will then be formed by this collection of the best paths.

- This is in total contrast with the second class of the routing protocols.

- In the distance vector routing protocols, the routing table of a node is also shared by its neighbors whereas in the link state routing protocol, only the connectivity related information is passed between the nodes. 

- The simplest configuration of the link state routing protocols is the one that has no area. 

- This implies that each node possesses a map of the whole network. 

- The first main stage involves providing map of the network to each node. 

For doing the following, subsidiary steps are followed:

1. Determination of the neighboring nodes: Each node determines to which all neighboring nodes it is connected to. Also, it needs to know whether over the links through which it is connected are fully working or not. A reach-ability protocol is used for accomplishing this task. This protocol is run regularly but in separation from the neighboring nodes.
2. Distribution of the map information: The link state advertisement is the short message that is made by the node in case of some modification in the connectivity periodically.

- The above obtained set of such link state advertisements is used for the creation of the map of the entire network. 

- The second stage involves production of the routing tables through the map inspection. 

This again involves a number of steps:

1. Calculation of the shortest paths: Shortest path from one node to other nodes is determined by running a shortest path routing algorithm over the entire map. The commonly used algorithm is the Dijkstra’s algorithm.
2. Filling the routing table: The table is filled with best shortest paths obtained in the above step for every two nodes.  
3. Optimizations: We gave a glance of the simple form of this algorithm but in practical applications this form is used along with a number of optimizations. Whenever a change is detected in the network connectivity, the shortest path tree has to be immediately recomputed and then the routing table must be recreated. A method was discovered by the BBN technologies for recomputing only the affected part of the tree.

- Routing loops can be formed if working of the nodes using the exactly same map is not proper. 

- For adhoc networks such as the mobile networks, the optimized form of the protocol i.e., the optimized link state routing protocol is used.