Link-state routing protocols are also known as shortest-path first protocols. They maintain a complete picture of all the routers running a link-state routing protocol in the entire network. All routers running a link-state routing protocol originate information about themselves and their directly connected routers, links, and the state of those links as multicast messages.
The link-state router tries to maintain a complete network topology by updating itself whenever a change occurs. Link-state routing protocols are based on the Shortest Path First (SPF) algorithm to find the best path to a destination. The Shortest Path First (SPF) algorithm is also known as the Dijkstra algorithm. OSPF is the most common example of a link-state routing protocol.
Example Topology
[See Topology Diagram 1: R1, R2, and R3 Base Topology]
The examples throughout this guide reference a small three-router network:
| Router | Interface | Connects To | Network |
|---|---|---|---|
| R1 | Fa0/0 | R2 | 192.168.1.0/24 |
| R1 | Fa0/1 | Local LAN | 192.168.0.0/24 |
| R1 | (second interface) | R3 | 192.168.3.0/24 |
| R2 | Fa0/1 | Local LAN | 192.168.2.0/24 |
| R2 | Fa0/0 | R1 | 192.168.1.0/24 |
| R3 | Fa0/1 | Local LAN | 192.168.4.0/24 |
| R3 | Fa0/0 | R1 | 192.168.3.0/24 |
R1 sits at the center of this small topology, connected to R2 on one side and R3 on the other, with its own directly attached LAN as well. This is the topology used in the discovery, Hello protocol, and SPF tree examples below.
Link-State Routing Process
The link-state process is functionally identical for OSPFv2 (IPv4) and OSPFv3 (IPv6), differing mainly in addressing. Below, we outline each step with examples based on the reference topology above.
Step 1: Link and Link-State Discovery
Each router learns about its own links and directly connected networks. When a router interface is configured with an IP address and subnet mask and is in a no shutdown state, it becomes part of that network. Before both configuration steps are complete, physical connectivity alone is not enough for the interface to participate.
Once the interface is fully configured and active, the router learns about its own directly connected networks. Without any routing protocol running yet, these directly connected networks already become entries in the routing table simply by virtue of being active interfaces.
Link-state routers pass information about themselves, their directly connected links, and the state of those links to every other router in the area. Each router forwards this information unchanged, so every router ends up with identical raw information about the network and independently calculates its own best paths from that shared data.
Example — R1’s link-state information:
| Link | Network | Interface | Neighbor | Type |
|---|---|---|---|---|
| Link 1 | 192.168.1.0/24 | Fa0/0 | R2 | Ethernet |
| Link 2 | 192.168.0.0/24 | Fa0/1 | (LAN, no router neighbor) | Ethernet |
| Link 3 | 192.168.3.0/24 | (second interface) | R3 | Ethernet |
The link-state information generated for each link includes: the interface’s IPv4 address and subnet mask, the type of network (Ethernet, Serial, etc.), the cost of that link, and any neighbor routers discovered on that link.
Step 2: Hello Protocol
Routers running a link-state protocol use a Hello protocol to establish and maintain neighbor relationships with other routers on directly connected networks. A neighbor is any other router running the same link-state protocol. Hello packets serve both neighbor discovery and ongoing keep-alive/recovery functions.
[See Topology Diagram 2: R1 Receiving Hello Messages]
R1 sends Hello packets out every active interface. R2 and R3, running the same protocol, respond with their own Hello packets, and both routers add each other to their respective neighbor tables. If an interface has no responding neighbor (for example, R1’s Fa0/1 interface facing its own local LAN, where no other router is present), the link-state process simply doesn’t continue on that specific interface, it isn’t an error, just an interface with no protocol neighbor to form an adjacency with.
[See Topology Diagram 3: R2 and R3 Identifying Themselves to R1]
Once R2 and R3 receive R1’s Hello packets, they each reply with their own Hello packet identifying themselves (“Hello, I am R2” and “Hello, I am R3”), which is what allows R1 to add each of them to its neighbor table by their actual router identity, not just by interface.
Hello packets continue to be exchanged between established neighbors as a keep-alive function. If a router stops receiving Hello packets from a specific neighbor, that neighbor is eventually considered unreachable and removed from the adjacency table.
OSPF Hello Timing Specifics
After the initial Hello exchange, routers add each other to their neighbor tables. Hello packets themselves are not stored in the OSPF link-state database, they exist purely for neighbor discovery and liveness detection. On broadcast networks, if a Hello packet has not been received from a neighbor for 40 seconds (the default Dead Interval, four times the default 10-second Hello Interval), that neighbor is marked down.
Brief outages are handled gracefully: if a link drops and recovers within about 20 seconds, OSPF may not even register a meaningful disruption. For longer outages, OSPF’s LSA aging mechanism governs what happens to routing information about the affected link.
Every LSA has a maximum age of 3600 seconds (1 hour), per RFC 2328; once an LSA reaches this age without being refreshed, it is flushed from the database and must be reflooded as new information when the link returns. In practice, this means a link that has been down long enough for its LSAs to reach MaxAge will effectively look like a brand-new route to the rest of the network once it comes back up, rather than a restored existing one.
Step 3: Building the Link State Packet (LSP)
The third step is building the Link-State Packet (LSP), containing the state of each of the router’s directly connected links: neighbor identity, link type, and link cost. The LSP is what a router actually generates and shares with the rest of the network, once adjacencies have been established, the router can build this packet from its own confirmed link-state information.
Example — R1’s LSP, based on the reference topology:
- R1 → R2; Fa0/0; network 192.168.1.0/24; Cost 1
- R1 → local LAN; Fa0/1; network 192.168.0.0/24; Cost 1
- R1 → R3; second interface; network 192.168.3.0/24; Cost 1
LSPs are not sent periodically the way Hello packets are. They are sent once during initial protocol startup, and afterward only when a genuine topology change occurs, a link failing, recovering, or a new network being added.
Step 4: Flooding the LSP
[See Topology Diagram 4: Larger Six-Router Network for LSP Flooding]
After building its LSP, each router floods it out to all of its neighbors, this is the fourth step, and it happens in every area for every router’s own LSP. Neighboring routers receive the LSP, store it in their own link-state database, and then reflood it out every interface except the one it arrived on. This process repeats hop by hop until every router in the area has received a copy.
To see why flooding matters more in a larger network, consider a six-router topology: R1 (with its own LAN) connects to R2, which connects onward to R5 through two possible paths, a direct link to R5 (cost 20) and an alternate path via R4. R5 also connects up to R3 and out to R6 (with its own LAN).
If the link between R3 and R5 (network 192.168.3.0/24) goes down, R5 generates an updated LSP reflecting that change and floods it to R2 and R4. Those routers, in turn, reflood it onward, and within a few seconds every router in the topology, including R1 and R6 at opposite ends of the network, has the updated information, without needing a separate individual notification to each one.
Each LSP carries a sequence number and aging information, allowing every router to determine whether an incoming LSP represents new information or a stale duplicate of something already in its database. This mechanism is what keeps flooding from looping indefinitely, once a router has already processed a given LSP’s current sequence number, it recognizes and discards any redundant copies rather than reflooding them again.
Because flooding completes before the SPF calculation begins, and flooding itself propagates quickly hop by hop rather than waiting on any periodic timer, link-state protocols generally achieve fast convergence compared to distance-vector protocols.
Step 5: Building the SPF Tree
[See Topology Diagram 5: R1’s Completed SPF Tree]
Once a router has received LSPs from every other router in its area, it uses its full link-state database and the SPF (Dijkstra) algorithm to independently build its own SPF tree. The algorithm starts from the router’s own directly connected networks and costs, then progressively works outward through the LSPs received from other routers, calculating the shortest cumulative-cost path to every known network.
Using the reference topology, R1’s SPF tree roots at R1 itself, with direct branches to R2 (cost 1) and R3 (cost 1), and its own local LAN 192.168.0.0/24 (cost 1) as a leaf directly off the root. Every router in the area builds this tree independently, using the exact same underlying link-state database, since all routers received identical flooded information. This is why link-state databases must be identical across every router in the same area: any inconsistency would cause different routers to calculate different, potentially conflicting paths to the same destination.
Step 6: Building the Link-State Database
Building the link-state database is the final step. Every router stores the LSPs it receives from every other router in the area, forming a complete map of the area’s topology, from which the router computes its best path to every destination network.
Each router maintains a separate link-state database per area it belongs to, since flooding and SPF calculation both happen independently within each area. The database is also called the topological database, and every router within the same area maintains an identical topological database for that area, built from router link advertisements, network link advertisements, and, in non-stub areas, summary and external route advertisements.
Summary of the Link-State Process
- Each router learns about its own directly connected networks and links by detecting interfaces in the up state.
- Routers say “hello” to neighbors on directly connected networks, forming adjacencies.
- Each router builds a Link-State Packet (LSP) containing the state of each directly connected link, neighbor, neighbor ID, link type, and link cost.
- Each router floods its LSP to all neighbors; those neighbors store it and reflood it onward until every router in the area has a copy.
- Every router uses its now-complete link-state database to independently build an SPF tree via Dijkstra’s algorithm and calculate the best path to every destination network.
Important Terms
| Term | Definition |
|---|---|
| Topological database | The complete set of information collected from LSAs/LSPs for an area |
| SPF algorithm | The Dijkstra-based algorithm used to calculate the shortest-path tree from the link-state database |
| Routing table | The final list of known destination networks and the interface/next-hop used to reach each |
| LSA | Link-State Advertisement — the OSPF-specific term for the small packet of routing information exchanged between routers describing local topology |
| LSP | Link-State Packet — the general term (used across link-state protocols) for the packet describing a router’s neighbors, costs, and connected networks |
Advantages and Disadvantages
Advantages
- Fast Convergence — LSPs are flooded immediately upon receipt (out every interface except the one they arrived on), without waiting on any periodic timer, enabling rapid network-wide convergence after a change.
- Full Topological Map — Every router builds a complete SPF tree of the area, allowing independent calculation of the genuinely shortest path to every destination.
- Hierarchical Design — Multiple areas allow route summarization and better scalability than a single flat topology.
- Event-Driven Updates — After initial flooding, LSPs are sent only when something actually changes, and contain only information about the affected link, not periodic full updates.
Disadvantages
- Memory Requirements — Maintaining the full link-state database and SPF tree requires meaningfully more memory than a distance-vector protocol’s simpler routing table.
- Processing Requirements — The SPF (Dijkstra) algorithm requires more CPU time than simpler distance-vector algorithms like Bellman-Ford, since it computes a complete shortest-path tree rather than incrementally comparing distances.
- Bandwidth Requirements — Initial LSP flooding, and reflooding after significant topology changes, consumes bandwidth, particularly noticeable in unstable networks experiencing frequent link flaps.
Protocols That Use Link-State Routing
Two routing protocols are the standard examples of link-state routing: OSPF (Open Shortest Path First) and IS-IS (Intermediate System to Intermediate System).
OSPF
OSPF is the most widely deployed link-state protocol, originally designed by the IETF starting around 1987. OSPFv2, for IPv4 networks, is defined in RFC 2328. OSPFv3, for IPv6 networks (and also capable of supporting IPv4 address families), was originally defined in RFC 2740, since superseded by RFC 5340, the current standard.
OSPF is an open standard supported on virtually all enterprise routing platforms, uses the Dijkstra algorithm for a loop-free topology, provides fast convergence through triggered, incremental LSA updates, and is a classless protocol supporting VLSM and hierarchical area-based route summarization.
IS-IS
IS-IS is an open standard routing protocol designed by the International Organization for Standardization (ISO), described in ISO 10589. It was originally designed for the OSI protocol suite rather than TCP/IP; Integrated IS-IS (also called Dual IS-IS) later added support for IP networks alongside OSI.
IS-IS is particularly associated with internet service providers and carriers, valued for its scalability in very large networks, and is often considered easier to scale to large topologies than OSPF. It carries a payload of reachability data largely agnostic to what that payload actually contains.
CCNA Exam Pointers
- Link-state protocols: OSPF and IS-IS; both use the Dijkstra (SPF) algorithm
- Process order: Discovery → Hello → Build LSP → Flood LSP → Build SPF Tree → Build Link-State Database
- OSPF default timers: Hello 10s / Dead 40s (broadcast networks)
- LSA MaxAge = 3600 seconds (1 hour) — after this, an LSA is flushed and must be reflooded as new
- LSPs/LSAs are not periodic after initial flooding; sent only on genuine topology change
- Link-state databases must be identical across all routers in the same area for consistent SPF calculation
- OSPFv2 = RFC 2328 (IPv4); OSPFv3 = RFC 5340 (current, supersedes RFC 2740) (IPv6, also supports IPv4 AF)
- IS-IS: ISO 10589, originally OSI-only, Integrated/Dual IS-IS adds IP support
- Link-state advantages: fast convergence, full topology map, hierarchical scalability, event-driven updates
- Link-state disadvantages: higher memory, CPU, and initial bandwidth requirements than distance-vector
Conclusion
Link-state routing protocols achieve their fast, accurate convergence through a consistent, predictable process: each router discovers its own links, forms adjacencies via the Hello protocol, builds an LSP describing those links, floods that LSP to every other router in the area, and independently calculates the shortest path to every destination using the SPF algorithm. Because every router works from an identical flooded database, the resulting paths remain consistent and loop-free across the entire area. OSPF and IS-IS remain the two dominant real-world implementations of this model, each proven at scale across enterprise and service-provider networks alike.
Frequently Asked Questions
What are link-state routing protocols?
Link-state routing protocols, also called shortest-path first protocols, maintain a complete view of the network topology by having every router share information about itself and its directly connected links via flooded messages. Each router uses this shared information, identical across all routers in the area, to independently calculate the shortest path to every destination using the SPF (Dijkstra) algorithm. OSPF and IS-IS are the two standard examples.
How does the discovery step work in link-state routing?
A router learns about its directly connected networks once an interface is configured with an IP address and subnet mask and set to the “no shutdown” state. This automatically adds that network as an entry in the routing table, even before any routing protocol begins exchanging information, and it’s the foundation the router later builds its own LSP from.
What is the role of the Hello protocol in link-state routing?
The Hello protocol establishes and maintains neighbor relationships between routers running the same link-state protocol on directly connected networks. It handles both initial neighbor discovery and ongoing keep-alive monitoring; if Hello packets stop arriving from a neighbor for the Dead Interval (40 seconds by default on OSPF broadcast networks), that neighbor is marked unreachable and removed from the adjacency table.
What information is included in a Link-State Packet (LSP)?
An LSP contains the state of each of a router’s directly connected links: the interface’s IP address and subnet mask, the network type (Ethernet, serial, etc.), the cost of that link, and any neighbors discovered on it. This information is flooded unchanged to every other router in the area, forming the raw material each router uses to build its own link-state database and SPF tree.
How does flooding occur in link-state routing?
After building its LSP, a router sends it to all directly connected neighbors. Each receiving router stores the LSP and reforwards it out every interface except the one it arrived on, and this continues hop by hop until every router in the area has a copy. Sequence numbers and aging information included in each LSP allow routers to recognize and discard duplicate or stale copies, preventing the flooding process from looping indefinitely.
What is the SPF tree in link-state protocols?
The SPF tree is the shortest-path tree each router independently calculates from its complete link-state database using the Dijkstra algorithm, starting from its own directly connected networks and costs and working outward through the flooded LSP information from every other router. Because every router in an area shares an identical link-state database, each router’s independently calculated SPF tree remains consistent with every other router’s, which is essential for loop-free, accurate routing across the area.
