Link state protocols are based on Shortest Path First (SPF) algorithm to find the best path to a destination. Shortest Path First (SPF) algorithm is also known as Dijkstra algorithm, since it is conceptualized by Dijkstra. In Shortest Path First (SPF) algorithm, whenever a link's state changes, a routing update called a Link-State Advertisement (LSA) is exchanged between routers. When a router receives an LSA routing update, the link-state algorithm is used to recalculate the shortest path to affected destinations. Link-state routing always try to maintain full networks topology by updating itself incrementally whenever a change happen in network. Each router constructs a map of the complete network. An example of Link State protocol is OSPF (Open Shortest Path First).
Some important terms related with Link State Routing Protocols
• Link-state advertisements (LSAs) – A link-state advertisement (LSA) is a small packet of routing information that is sent between routers.
• Topological database – A topological database is a collection of information gathered from LSAs.
• SPF algorithm (Dijkstra algorithm) – The shortest path first (SPF) algorithm is a calculation performed on the database resulting in the SPF tree.
• Routing tables – A list of the known paths and interfaces.
Link State Routing Protocols converge more quickly and they are less prone to routing loops than Distance Vector algorithms. On the other hand, Link State Routing Protocols require more CPU power and memory than distance vector algorithms. Link State Protocols use a hierarchical structure that limits the distance that a Link-State Advertisement (LSA) need to travel. Link State Protocols use multicasts to share the routing information. Only the routers which run Link State protocol only process the updates. Link State routers send updates only when there is a change in the state of the network (incremental updates).
Link-state algorithms can be more complex and expensive to implement and support.