Link State Routing

Ka Kavitha V Updated 08 Oct 2026

12 min read ·Lesson 31 of 45

Link State Routing

Every router in a network has one core job: when a packet arrives, decide which outgoing link gets it closer to its destination. To make that decision well, a router needs to know what the network actually looks like — not just its own neighbors, but the full layout of routers and links beyond them. Link State Routing is a dynamic routing strategy built around that idea: give every router a complete, identical map of the network, and let each one independently compute the best paths from that map.

This is the approach behind two of the most widely deployed interior routing protocols on the Internet today: OSPF and IS-IS.

What Is Link State Routing?

Link State Routing is a routing method in which each router:

Discovers the routers it is directly connected to and the cost of each connection.
Shares that information with every other router in the network (not just its neighbors).
Uses the complete set of information, from every router, to build an identical map of the whole network topology.
Independently calculates the shortest path to every destination using Dijkstra's Shortest Path First (SPF) algorithm.

The defining trait of Link State Routing is captured in its name: routers exchange information about the state of their links, not about entire routing tables. Every router ends up solving the same shortest-path problem on the same map, so their conclusions are consistent with each other by construction.

Real-World Analogy

Picture a city where every driver is handed an identical, continuously updated map showing every road, every intersection, and live traffic conditions. Instead of asking a neighbor "which way should I go next?" at every turn, each driver reads the full map and plans a complete route from where they are to the destination.

That is the essence of Link State Routing:

Every router holds a complete map of the network.
Every router calculates its own routes independently.
Because everyone is working from the same map, their routing decisions stay consistent with each other.

This is different from Distance Vector Routing, where a router only knows what its neighbors tell it about distances ("I can reach network X in 3 hops") without ever seeing the actual topology. Link State Routing trades a bit more complexity for a much more accurate, loop-resistant picture of the network.

How Link State Routing Works

Building and using the network map happens in five stages.

Step 1: Discover Neighbors

A router first identifies which other routers it is directly connected to. It does this by exchanging small "Hello" messages over each of its interfaces — any router that responds is a confirmed, directly connected neighbor.

For example:

Router A is connected to Router B and Router C.
Router B is connected to Router A and Router D.

At this point, each router only knows about its immediate neighborhood — nothing further.

Step 2: Create a Link State Advertisement (LSA)

Each router packages what it has learned about its local connections into a message called a Link State Advertisement (LSA).

An LSA typically contains:

The originating router's ID
A list of its directly connected neighbors
The status of each link (up or down)
The cost (metric) of each link
A sequence number (so older, duplicate copies of the same LSA can be distinguished from newer ones)
An age value (so stale information eventually expires if it isn't refreshed)

For example, Router A's LSA states that it can reach Router B at a cost of 2 and Router C at a cost of 5. It says nothing about routers further away — A only reports what it can see directly.

Step 3: Flood the LSA

A router sends its LSA to all of its directly connected neighbors. Each of those neighbors makes a copy, forwards it to its own neighbors, and so on, until every router in the network has received a copy of every other router's LSA. This process is called flooding.

Flooding is reliable: a router acknowledges each LSA it receives, and sequence numbers prevent old or duplicate copies from being reprocessed or from overwriting newer information.

Why flooding matters: if even one router missed an LSA, it would be working from an incomplete or outdated map. That mismatch can produce incorrect routing decisions and, in some cases, routing loops. Flooding is what guarantees every router converges on the same view of the network.

Step 4: Build the Link State Database (LSDB)

Every router stores all the LSAs it has received — including its own — in a structure called the Link State Database (LSDB). Because every router floods its LSA to the entire network, and every router stores every LSA it receives, all routers within the same routing area end up with an identical LSDB.

The LSDB is effectively a complete, shared map of the network. For the small network used in the earlier example, a router's LSDB might summarize the topology like this:

Router	Connected To	Cost
A	B	2
A	C	5
B	D	3
C	D	1

From this table alone, any router can reconstruct the entire topology: which routers exist, how they connect, and at what cost.

Step 5: Calculate Shortest Paths

Once a router has a complete LSDB, it runs Dijkstra's Shortest Path First (SPF) algorithm against it, treating itself as the source. SPF computes the lowest-cost path from that router to every other router in the network. The results are installed into the router's routing table, which is what actually gets consulted when forwarding packets.

Because every router runs SPF on an identical map, their individual routing tables stay mutually consistent — each one correctly points toward the next hop on the true shortest path.

Understanding Link Cost (Metric)

Every link in the network is assigned a numeric cost, also called a metric. SPF uses these costs to decide which path is "best" — generally, a lower total cost means a better path.

Cost can be derived from several factors, including:

Bandwidth (higher-bandwidth links often get a lower cost)
Delay
Reliability
Administrative preference set by a network engineer

For example, suppose there are two possible paths from A to D:

Path	Total Cost
A → B → D	4
A → C → D	8

SPF selects A → B → D, because its total cost (4) is lower than the alternative (8) — even though the second path might involve fewer physical hops in some other topology. Cost, not hop count, is what Link State Routing optimizes for.

Why only routers assign cost: link cost is deliberately a router-managed value, not something end devices or application traffic can influence. If every device on the network could alter how a link's cost was perceived, routers would reach inconsistent conclusions about the "best" path, and the network could become unstable. Keeping cost assignment exclusively in the hands of routers keeps path calculations predictable and consistent across the whole network.

Dijkstra's Algorithm (SPF) in Detail

Dijkstra's algorithm is the computational core of every Link State Routing protocol. Given a source router and a map of costs between all routers, it finds the lowest-cost path from that source to every other router.

Notation used in the algorithm:

c(i,j) — the cost of the direct link between node i and node j
D(v) — the current best-known cost from the source to node v
P(v) — the previous node ("predecessor") on the best-known path to v
N — the set of nodes whose shortest path has already been finalized

The algorithm:

Initialize: Set D(source) = 0. Set D(v) = cost of the direct link for every neighbor of the source (or infinity if there is no direct link). Set D(v) = infinity for every other node. N starts empty.
Repeat until every node is in N:
- Select the node not yet in N with the smallest D(v), and add it to N.
- For each neighbor v of the node just added (call it w), update:
```
D(v) = min( D(v), D(w) + c(w, v) )
```
  In words: check whether reaching v by going through w is cheaper than the best path found so far. If it is, D(v) is updated and P(v) is set to w.

The algorithm always expands outward from the cheapest known node, which guarantees that once a node is added to N, its shortest-path cost is final and will never be improved later.

Worked Example

Consider a small network of five routers — A, B, C, D, and E — connected as follows:

Link	Cost
A – B	2
A – D	1
D – E	1
D – C	3
E – B	3
E – C	1

Running SPF from Router A proceeds like this:

Step	Node Added to N	D(B)	D(C)	D(D)	D(E)
1	A	2 (via A)	∞	1 (via A)	∞
2	D (cost 1)	2 (via A)	4 (via D)	—	2 (via D)
3	B or E (tie at 2) — take B	—	4 (via D)	—	2 (via D)
4	E (cost 2)	—	3 (via E)	—	—
5	C (cost 3)	—	—	—	—

The final shortest-path costs from Router A are:

A → D = 1 (direct)
A → B = 2 (direct)
A → E = 2 (via A → D → E)
A → C = 3 (via A → D → E → C)

Notice that the shortest path to C is not the direct-looking route through D (A → D → C, cost 1 + 3 = 4); it's cheaper to route through E instead (A → D → E → C, cost 1 + 1 + 1 = 3). This is exactly the kind of non-obvious result SPF is designed to catch — a router scanning the map by eye might easily pick the costlier path.

These final values become the entries in Router A's routing table.

Key Operating Principles

Three design choices distinguish Link State Routing from other routing strategies:

1. Neighborhood knowledge, not full tables. A router only ever reports what it directly knows — its own links and their costs. It never forwards someone else's routing table. This keeps individual messages small and avoids one router's errors being blindly propagated by another.

2. Flooding to the whole network. Even though each router only reports its local neighborhood, that information is distributed everywhere, so every router can assemble the same global picture.

3. Event-driven updates. Routers don't need to resend their LSAs on every clock tick. A new LSA is generated and flooded only when something actually changes — a link fails, a new connection comes up, or a cost changes. (Protocols also send infrequent periodic refreshes as a safety net, covered below.) Together, these three principles mean updates travel quickly when something changes, but the network isn't flooded with redundant traffic when nothing has.

Major Components of Link State Routing

Link State Advertisement (LSA): The message format that carries a router's local topology information. Sequence numbers prevent duplicate or stale LSAs from corrupting the database, and the flooding mechanism ensures changes propagate quickly.

Link State Database (LSDB): The structure where every router stores all LSAs it has received. Since all routers in an area receive the same LSAs, they maintain identical databases — which is what guarantees consistent routing decisions.

Shortest Path First (SPF) Algorithm: Dijkstra's algorithm, run against the LSDB, to compute loop-free, optimal-cost paths to every destination. When multiple paths to the same destination share the lowest cost, the router can install all of them and load-balance traffic across them — a feature known as Equal-Cost Multi-Path (ECMP).

Periodic and Triggered Updates: LSAs are re-sent in two circumstances:

Periodic refresh — occasionally, even with no topology change, so stale entries don't accidentally expire.
Triggered update — immediately, whenever a real change occurs (a link going down, a new neighbor appearing, a cost changing).

Relying mainly on triggered updates (rather than frequent periodic broadcasts) is what gives Link State Routing fast convergence and relatively low bandwidth overhead.

Hierarchical Design (Areas): In large networks, flooding every LSA to every router can produce a very large LSDB and heavy SPF computation. Link State protocols solve this by dividing the network into areas. OSPF, for example, organizes a network around a central backbone area (Area 0), with other regular areas connecting to it. Routers inside an area keep a detailed map of that area only, and exchange summarized (rather than full-detail) information about other areas. This keeps each router's LSDB smaller, improves scalability, and makes troubleshooting easier because problems are generally contained within one area.