Link-State Routing: Principles, Mechanics, and a Worked Example

Link-state routing is a class of routing algorithms where each router learns the full network topology (within its routing scope) by exchanging link-state information, then computes shortest paths locally using a shortest-path algorithm (commonly Dijkstra’s algorithm). In contrast to distance-vector routing, link-state routing does not rely on hop-by-hop iterative counting; instead it uses topology dissemination followed by local recomputation. Key elements include: link-state advertisement (LSA) flooding, a topology database (LSDB) maintained by every router, and the shortest-path first (SPF) calculation that yields the forwarding table.

A widely deployed link-state protocol is OSPF (Open Shortest Path First), defined as a link-state interior gateway protocol that floods LSAs and computes routes with SPF. Link-state routing also underpins IS-IS (Intermediate System to Intermediate System), which similarly floods link-state packets and uses SPF within routing levels.

Core idea: “share topology, then compute”

In link-state routing, each router:

1. Discovers the status and metric of its own links to neighbors.
2. Creates a link-state advertisement describing those links.
3. Floods the advertisement to other routers (typically via controlled flooding within an area).
4. Each router stores received LSAs in a topology database.
5. Each router runs SPF on the database to compute the shortest-path tree and select next hops.

This separation—dissemination of topology followed by local shortest-path computation—is the defining difference versus distance-vector routing.

Why it matters: once LSAs are fully flooded, SPF computation is deterministic given the same LSDB, producing consistent routes and typically faster convergence after topology changes than pure distance-vector mechanisms. OSPF’s operation is described around LSAs, flooding, and SPF computation.

Visualizing the SPF step with a graph

After LS flooding, each router has the same LSDB (within its scope). SPF treats the LSDB as a weighted graph:

• vertices = routers (or nodes)
• edges = links with costs/metrics

Then it computes shortest path distances from the local node to all others. Dijkstra’s algorithm is the canonical SPF approach used to compute least-cost paths from a single source over a weighted graph. OSPF explicitly uses SPF for route computation.

Worked Example: Link-State Routing on a Small Network

Network topology and link costs

Assume router R1 is the local router that will compute routes. The network graph (within the routing area/scope) is:

• Links:
  • R1—R2 cost 2
  • R1—R3 cost 5
  • R2—R3 cost 1
  • R2—R4 cost 2
  • R3—R4 cost 3

Each router would originate an LSA describing its own local links (e.g., R2’s LSA lists links to R1, R3, and R4 with their costs). Flooding disseminates these LSAs so that R1’s LSDB contains the full weighted graph.

Deriving the forwarding next hops

From the computed shortest paths:

• To R2: path is R1 → R2, next hop = R2
• To R3: path is R1 → R2 → R3 (since $2 + 1 = 3$ is less than direct $5$), next hop = R2
• To R4: path is R1 → R2 → R4 (cost $2+2=4$), next hop = R2

This is exactly what the SPF result (shortest-path tree) supplies: the parent/predecessor relationships define the next hop for each destination.

How this maps to OSPF/IS-IS behavior

For OSPF, routers send and receive LSAs, populate the LSDB, and compute shortest paths using SPF (shortest-path first). OSPF also organizes topology into areas to control flooding scope and reduce database size.

For IS-IS, routers exchange link-state packets (LSPs) within configured routing levels; the protocol follows the same link-state idea of flooding topology information and running SPF to compute routes.