A link state routing protocol is a type of network routing protocol where every router builds a complete map of the entire network, then independently calculates the best path to every destination. This stands in contrast to simpler approaches where routers only know what their immediate neighbors tell them. Link state protocols power most modern enterprise and service provider networks, with OSPF and IS-IS being the two most widely deployed examples.
How Link State Routing Works
The process follows a logical sequence. First, each router discovers its neighbors by sending out “hello” messages on all of its connections. When a neighboring router responds, both sides now know who they’re directly connected to and how costly that connection is (measured in metrics like bandwidth or delay).
Next, each router packages up what it learned about its own connections into a small data structure called a link state advertisement, or LSA. This LSA contains the router’s identity, which links it has, the state of each link (up or down), and the cost of using it. The router then floods this LSA to every other router in the network. Flooding works simply: when a router receives an LSA it hasn’t seen before, it saves a copy and forwards it to all of its other neighbors. This chain reaction ensures every router eventually gets every LSA.
Once a router has collected LSAs from all the other routers, it assembles them into a link state database. This database is essentially a complete map of the network’s topology: every router, every connection, and every cost. All routers in the same network area end up with identical copies of this database.
Finally, each router runs a shortest path algorithm against that map to calculate the best route from itself to every destination. The result is a routing table tailored to that router’s specific position in the network.
The Shortest Path Calculation
The algorithm most link state protocols use is Dijkstra’s algorithm, created by computer scientist Edsger Dijkstra in 1956. It works by starting at the router’s own position and exploring outward step by step. At each step, it looks at the “frontier” of nodes connected to the area it has already explored and picks the one reachable at the lowest total cost. Knowing the shortest path to nearby routers helps it find the shortest paths to more distant ones, building outward until every destination has been reached.
Each connection in the network carries a numeric weight representing its cost. This might reflect bandwidth, delay, or an administratively assigned value. The shortest path between any two routers is the route whose weights add up to the smallest total number. Because every router has the same complete map, they all agree on the topology, but each one calculates paths from its own perspective.
What Makes It Different From Distance Vector
The older approach to routing, called distance vector, works on a fundamentally different principle. Distance vector routers don’t have a map of the network. Instead, each router only knows what its directly connected neighbors report: “I can reach destination X at cost Y.” Routers pass these summaries to each other hop by hop, and each one trusts its neighbors’ math. Cisco’s learning resources describe this as “routing by rumor.”
This difference has real consequences. Because distance vector routers calculate routes in a distributed, hop-by-hop fashion, changes in the network propagate slowly. If a link goes down, the bad news has to travel from neighbor to neighbor, and routers along the way may temporarily send traffic in loops before the network settles on a new path. The more routers along a route, the longer this convergence takes.
Link state routers, by contrast, converge faster because every router has accurate, firsthand information from all other routers in the network. When a link fails, the affected router immediately floods a new LSA. Every other router receives it, updates its map, and recalculates paths independently. There’s no chain of rumors to unwind.
The Link State Database
The link state database (LSDB) is the core data structure that gives link state protocols their power. It’s the collected set of all LSAs a router has received, and it represents a full graph of the network. Each LSA in the database contains specific fields: the originating router’s ID, the links it connects to, the cost of each link, a sequence number (so routers can tell which version is newest), and an age value (so stale entries eventually expire).
Different types of LSAs describe different parts of the network. Router LSAs, for instance, list all outgoing interfaces of a router along with the state and cost of each link. Other LSA types describe connections between network segments, summarize routes from other areas, or advertise external destinations. Together, they give every router enough information to reconstruct the full topology.
Organizing Large Networks With Areas
Maintaining a complete map of a very large network gets expensive. Every router needs enough memory to store the entire LSDB and enough processing power to run the shortest path algorithm against it. During initial synchronization, when routers first exchange all their LSAs, the flooding overhead can be significant. As the network grows, so do these resource demands.
To solve this, link state protocols divide large networks into areas. OSPF, for example, uses a multi-area design where an autonomous system is split into collections of contiguous routers and networks. Each area maintains its own LSDB, and routers within an area only need the full topology of that area, not the entire network. A central backbone area connects the other areas together and handles routing between them.
This design has several benefits. Reducing the area size confines the impact of route recalculations to a smaller scope. If a link fails in one area, only the routers in that area need to rerun their shortest path calculations. Routers in other areas are unaffected. The routing table shrinks because much of the detail from other areas gets summarized into compact route summaries rather than full topology data. The result is faster convergence, lower memory usage, and less CPU overhead on each individual router.
Common Link State Protocols
OSPF (Open Shortest Path First) is the most widely used link state protocol in enterprise networks. It operates within a single organization’s network, supports the area hierarchy described above, and works over both IPv4 and IPv6. OSPF is an open standard, meaning any vendor’s equipment can run it.
IS-IS (Intermediate System to Intermediate System) follows the same link state principles but originated from a different standards body. It’s the protocol of choice for many internet service providers and large-scale networks. IS-IS also supports hierarchical design, using “levels” instead of areas to achieve similar scalability benefits.
Both protocols share the same fundamental mechanics: neighbor discovery, LSA flooding, a synchronized topology database, and shortest path calculation. The differences between them are largely in packet formatting, how they define their hierarchies, and which environments they’re traditionally deployed in. For most practical purposes, they deliver the same core capability: fast, loop-free routing based on a complete picture of the network.
Tradeoffs to Understand
Link state protocols demand more from router hardware than simpler alternatives. Storing the full LSDB requires more memory, and running Dijkstra’s algorithm on every topology change requires more processing power. In small networks with limited hardware, this overhead may not be justified. Distance vector protocols like RIP work fine for simple, small topologies where fast convergence isn’t critical.
The flooding mechanism, while essential for keeping all routers synchronized, generates traffic on the network itself. In a stable network this is minimal, since LSAs are only flooded when something changes (or periodically to refresh aging entries). But during major outages where many links fail simultaneously, a burst of LSAs can temporarily increase load on both the network and the routers processing them.
Despite these costs, the benefits of accurate topology information, fast convergence, and loop-free routing make link state protocols the standard choice for any network of meaningful size or complexity. The area-based hierarchy keeps resource demands manageable even in networks with thousands of routers.