# Link State Routing ## What is Link State Routing Link state routing is a class of routing algorithms in which every router builds a complete map of the network topology and independently calculates the best path to every destination. Each router collects information about all its directly connected links and their costs, packages this information into a link state advertisement, and floods the advertisement to every other router in the network. When a router has received link state advertisements from all routers, it has a complete and identical picture of the network topology. It then uses Dijkstra's shortest path first algorithm to calculate the optimal path from itself to every other destination. ## Flooding Link State Advertisements When a router first comes up or when the state of one of its links changes, it creates a link state advertisement containing its router ID, a sequence number, and a list of its neighbors with the cost of each link. The router sends this advertisement out all its interfaces. Each router that receives the advertisement checks whether it has seen this advertisement before by comparing the sequence number. If the advertisement is new, the router stores it, updates its topology database, and forwards the advertisement out all interfaces except the one it was received on. This process ensures every router receives the complete link state advertisement from every other router. ## Dijkstra's Algorithm Once a router has collected link state advertisements from all routers, it applies Dijkstra's shortest path first algorithm to the topology database. The algorithm starts with the router itself as the root of the shortest path tree. In each iteration, it selects the unvisited node with the smallest current distance from the root and examines all its neighbors. If the path through the current node provides a shorter distance to a neighbor than the neighbor's current best distance, the neighbor's distance is updated. This continues until all nodes have been visited. The result is a shortest path tree rooted at the local router, from which the routing table is built. ## OSPF as Link State Protocol OSPF, the Open Shortest Path First protocol, is the most widely used link state routing protocol. It divides networks into areas to improve scalability. All routers within an area have identical topology databases for that area. Area border routers summarize routing information between areas. OSPF uses cost as its metric, where cost is typically inversely proportional to bandwidth. OSPF converges quickly when network changes occur because link state advertisements are flooded immediately when changes happen, rather than waiting for periodic updates as in distance vector protocols. ## Advantages over Distance Vector Link state routing converges faster than distance vector routing because each router has a complete view of the topology and can recalculate routes immediately when it receives updated link state information. Link state routing is not susceptible to the count-to-infinity problem because it does not rely on neighboring routers' distance estimates. Each router independently calculates routes from the topology database.