- IS – IS i.e., intermediate system to intermediate system and
- OSPF i.e., the open shortest path first
Idea behind the Link State Routing
- 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.
- 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.
- 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.
- Filling the routing table: The table is filled with best shortest paths obtained in the above step for every two nodes.
- 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.