Type of Routing Protocols:

1. Unicast Routing Protocol
2. Multicast Routing Protocol
3. Broadcast Routing Protocol

There are three major protocols for unicast routing:

1. Distance Vector Routing
2. Link State Routing
3. Path-Vector Routing

Link State Routing –
Link state routing is the second family of routing protocols. While distance-vector routers use a distributed algorithm to compute their routing tables, link-state routing uses link-state routers to exchange messages that allow each router to learn the entire network topology. Based on this learned topology, each router is then able to compute its routing table by using the shortest path computation.

Features of link state routing protocols –

• Link state packet – A small packet that contains routing information.
• Link state database – A collection of information gathered from the link-state packet.
• Shortest path first algorithm (Dijkstra algorithm) – A calculation performed on the database results in the shortest path
• Routing table – A list of known paths and interfaces.

Calculation of shortest path –
To find the shortest path, each node needs to run the famous Dijkstra algorithm. This famous algorithm uses the following steps:

• Step-1: The node is taken and chosen as a root node of the tree, this creates the tree with a single node, and now set the total cost of each node to some value based on the information in Link State Database
• Step-2: Now the node selects one node, among all the nodes not in the tree-like structure, which is nearest to the root, and adds this to the tree. The shape of the tree gets changed.
• Step-3: After this node is added to the tree, the cost of all the nodes not in the tree needs to be updated because the paths may have been changed.
• Step-4: The node repeats Step 2. and Step 3. until all the nodes are added to the tree

PPT Link state routing protocol

Click here to open the PPT  –   Link State Routing