Introduction to Link State Routing Protocols | What is Link State Routing Protocols

Link state routing protocols maintain complete road map of the network in each router running a link state routing protocol. Each router running a link state routing protocol originates information about the router, its directly connected links, and the state of those links. This information is sent to all the routers in the network as multicast messages. Link-state routing always try to maintain full networks topology by updating itself incrementally whenever a change happen in network.

Each router in the network keeps a copy of it, without changing it. After obtaining the complete picture of network topology, each router will independently calculate its own best paths to reach the destination networks.

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.  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 Routing Protocols. On the other hand, Link State Routing Protocols require more CPU power and memory than Distance Vector Routing Protocol 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.