Link-state routing — Dijkstra, the LSDB, and SPF calculation

Link-state routing is the algorithm class OSPFv2, OSPFv3, and IS-IS belong to. Every router in an area floods its local state — its own router-id, the interfaces it owns, and the neighbours it can reach — into a shared topology database. Every router then runs the same Dijkstra calculation on that database and installs the best paths.

The mental model that separates a junior from a senior engineer is this: a link-state router never trusts another router’s routing decision. It trusts another router’s advertised topology. The decision is always made locally, from the same LSDB, by the same algorithm. This is why OSPF, properly designed, does not loop the way a naive RIP environment does — and why a single unstable link can drive a large area into repeated SPF recalculation.

Distance-vector vs link-state — what changes

A distance-vector protocol (RIP, IGRP, and EIGRP in its DUAL form) advertises what the route is: a destination, a metric, and an implicit “via me”. A link-state protocol advertises what the topology looks like and lets each receiver decide. BGP is a third class again — path-vector — where the advertised AS_PATH exists precisely to detect the loops a plain distance-vector cannot.

flowchart TB
  subgraph DV["Distance-vector"]
    RV1["R1: 'to 10.0.0.0/8 use me, metric 2'"] --> RV2["R2: 'to 10.0.0.0/8 use me, metric 3'"]
    RV2 --> RV3["R3: 'to 10.0.0.0/8 use R2, metric 4'"]
  end
  subgraph LS["Link-state"]
    LV["Each router: 'I am router-id X<br/>I have interface Y with cost Z<br/>I see neighbours A, B, C'"]
    LV --> LD["Every router computes its own<br/>SPF tree from a shared LSDB"]
  end

In the distance-vector model, R3 chooses the path that R2 advertised. The path is whatever R2 said. If R2 has a wrong view of the topology, R3 inherits the wrong view and amplifies it (count-to-infinity in RIP).

In the link-state model, each router runs Dijkstra against the same LSDB and computes the path independently. Two routers legitimately reach different answers about which path is best, because the tree is rooted at each of them, but they cannot disagree about what the network looks like. The LSDB is the shared truth; the SPF tree is a private computation.

How OSPF builds the LSDB

OSPF builds the LSDB through three primitives:

1. Hello — discovers neighbours and checks that the parameters that must match do match (area-id, network mask, hello and dead intervals, authentication, the E-bit in the options field).
2. LSA origination — every router originates Router LSAs (Type 1), the DR originates a Network LSA (Type 2) on each broadcast segment, ABRs originate Summary LSAs (Type 3/4) and ASBRs originate External LSAs (Type 5). LSAs are the units of topology data.
3. Reliable flooding — every LSA is acknowledged and retransmitted until it is. Each LSA carries an age that counts up; the originator re-originates it every 1800 seconds (LSRefreshTime) and a copy that reaches 3600 seconds (MaxAge) without a refresh is flushed from every LSDB that holds it.

sequenceDiagram
  participant R1
  participant R2
  R1->>R2: Hello (router-id 1.1.1.1)
  R2->>R1: Hello (router-id 2.2.2.2)
  R1->>R2: DD (database description)
  R2->>R1: DD (my LSDB summary)
  R1->>R2: LSR (request the LSAs I am missing)
  R2->>R1: LSU (the LSAs)
  R1->>R2: LSAck (acknowledged)
  Note over R1,R2: Both LSDBs are now identical<br/>Each router runs its own Dijkstra

Two ways a dead router is noticed, and they operate on very different timescales. If it had an adjacency, the dead interval (40 seconds by default) tears the adjacency down and the surviving neighbours immediately re-originate Router LSAs without it — convergence in tens of seconds. Only when nothing is adjacent to the failed router do its LSAs have to sit in the database until MaxAge, an hour later. The “self-healing at 60 minutes” property is the backstop, not the mechanism.

The VyOS engineer’s view of the LSDB:

vyos@r1:~$ show ip ospf database

       OSPF Router with ID (1.1.1.1)

              Router Link States (Area 0.0.0.0)

Link ID         ADV Router      Age  Seq#       CkSum  Link count
1.1.1.1         1.1.1.1         1245 0x80000005 0x9ab2 3
2.2.2.2         2.2.2.2          893 0x80000004 0x44cc 2
3.3.3.3         3.3.3.3         1762 0x80000003 0x1234 2

              Net Link States (Area 0.0.0.0)

Link ID         ADV Router      Age  Seq#       CkSum
10.0.0.4        2.2.2.2          893 0x80000002 0xaabb

The columns mean: Link ID identifies the LSA (the router-id for a Type 1, the DR’s interface address for a Type 2); ADV Router is who originated it; Age is the LSA’s age in seconds, counting up toward MaxAge; Seq# is the sequence counter that decides which of two copies is newer; CkSum is the Fletcher checksum over the LSA contents; and for Router LSAs, Link count is how many links that router described.

A healthy area has one Type 1 per router in the area, one Type 2 per broadcast segment that has a DR and at least one adjacency, a Type 3 set from each ABR, and a Type 5 set from each ASBR.

The SPF calculation — Dijkstra in 60 seconds

Dijkstra’s algorithm computes the shortest path from a root to every other node in a graph with non-negative weights. OSPF uses it with the router running the calculation as the root and the LSDB as the graph; the result is the SPF tree, which determines the intra-area best paths.

flowchart LR
  Root["R1 (root)"] --> N1["R2 (cost 4 from R1)"]
  N1 --> N2["R3 (cost 7 from R2)"]
  N2 --> N3["R4 (cost 2 from R3)"]
  Root --> Tree["SPF tree from R1:<br/>R1 to R2 (4)<br/>R1 to R3 via R2 (11)<br/>R1 to R4 via R2 then R3 (13)"]

The stages, as RFC 2328 section 16 defines them and FRR implements them:

1. Build the graph from the area’s Type 1 and Type 2 LSAs.
2. Initialise the candidate list with the local router as root at cost 0.
3. Take the cheapest candidate, add it to the tree, and expand its own LSA’s links as new candidates.
4. Repeat until the candidate list is empty.
5. Install intra-area routes from the tree, including the stub links each Router LSA carries.

Two further passes follow the tree itself: inter-area routes are computed from the Type 3 and Type 4 LSAs using the cost to the ABR as the base, and AS-external routes from the Type 5 and Type 7 LSAs using the cost to the ASBR. Those passes do not re-run Dijkstra; they walk the tree that Dijkstra just produced.

Cost matters at scale. The classic complexity bound for Dijkstra with a priority queue is O((N + E) log N) for N nodes and E edges, so an area of a few hundred routers is a sub-millisecond-to-millisecond calculation on a modern CPU. Read the real number rather than a textbook estimate — FRR reports it directly, and it is one of the few places where a router will tell you exactly how expensive its own control plane is.

How FRR runs SPF — the triggers and the throttle

SPF does not run once per LSA. FRR compares an arriving LSA with the copy it already holds and schedules work according to what actually changed:

That last row is the one that surprises people. A quiet network still floods every LSA every 30 minutes, and none of those refreshes cost an SPF, because FRR checks whether the new copy differs from the old one before scheduling anything.

Reading the SPF state out of the router:

vyos@r1:~$ show ip ospf

 OSPF Routing Process, Router ID: 1.1.1.1
Supports only single TOS (TOS0) routes
This implementation conforms to RFC2328
RFC1583Compatibility flag is disabled
Initial SPF scheduling delay 0 millisec(s)
Minimum hold time between consecutive SPFs 50 millisec(s)
Maximum hold time between consecutive SPFs 5000 millisec(s)
Hold time multiplier is currently 1
SPF algorithm last executed 1m54s ago
Last SPF duration 62 usecs
SPF timer is inactive
Number of areas attached to this router: 1
Area ID: 0.0.0.0 (Backbone)
 Number of interfaces in this area: Total: 2, Active: 2
 Number of fully adjacent neighbors in this area: 2
 Area has no authentication
 SPF algorithm executed 47 times
 Number of LSA 4

Six lines in that output are the whole operational story:

• The three throttle values — the effective delay, minimum hold and maximum hold, in milliseconds. Read them here. Do not trust a remembered default: FRR’s own compiled-in defaults and the defaults VyOS’s CLI writes into the FRR configuration are not the same numbers, and a set you made months ago is invisible in any table but this one.
• Hold time multiplier — the current backoff level. At 1 the network is quiet. A multiplier that has climbed is the router telling you it is already defending itself against churn.
• SPF algorithm last executed and Last SPF duration — when, and how expensive. A duration in the tens of microseconds is a small area; a duration in the milliseconds is a large one.
• SPF algorithm executed N times, inside the per-area block — the cumulative count for that area since the process started. This is the number to trend. Sample it twice a minute apart and you have a rate; the rate, not the absolute value, is the diagnostic.

A healthy area adds a handful of SPF runs per day during scheduled changes and link events. An unhealthy one adds hundreds or thousands per hour — the “SPF storm” failure mode.

The SPF throttle timers

VyOS exposes FRR’s three-value SPF throttle as three separate leaves:

set protocols ospf timers throttle spf delay 200
set protocols ospf timers throttle spf initial-holdtime 1000
set protocols ospf timers throttle spf max-holdtime 10000

Those three leaves render into one FRR line of the form timers throttle spf DELAY INITIAL-HOLD MAX-HOLD, and the values mean:

• delay — how long FRR waits after the first topology change before running SPF at all. It exists so that a burst of LSAs arriving together costs one SPF rather than one each.
• initial-holdtime — the minimum gap between two consecutive SPF runs when churn continues.
• max-holdtime — the ceiling for that gap. Between the initial hold and the maximum, FRR backs off: each successive run during sustained churn multiplies the hold, which is what the Hold time multiplier line reports. When the network goes quiet, the multiplier resets.

All three are in milliseconds. Verify what is actually in force with show ip ospf rather than with the values you just typed — that is the only view that reflects both your set commands and whatever default the platform supplied.

These are rarely worth changing. If a site finds itself raising them, the real problem is upstream: a flapping neighbour, an interface that should be passive, or a hardware fault.

How it fails — production failure modes

The link-state model has its own failure modes, distinct from the distance-vector ones.

The two databases never synchronise

Two adjacent routers hold different databases and neither converges on the other. The adjacency sits in ExStart or Exchange and never reaches Full.

The usual cause is an IP MTU mismatch, and the mechanism is explicit in the protocol rather than accidental: every Database Description packet carries the sending interface’s MTU in its header. A receiver whose own interface MTU is smaller rejects the DD outright. The adjacency never gets past the database-summary stage, so no LSA is ever exchanged.

Diagnostic: show ip ospf neighbor shows the neighbour parked in ExStart or Exchange; show ip ospf interface prints the local MTU and shows whether MTU mismatch detection is enabled; ospfd logs an explicit MTU-mismatch line naming both values.

Fix: align the MTU on both sides (set interfaces ethernet eth1 mtu 9000, or leave both at the default 1500). The escape hatch, set protocols ospf interface eth1 mtu-ignore, tells OSPF to skip the check — it will let the adjacency form, and it will let an oversized LSU be dropped silently later, which is a worse failure to debug than the one it hid.

The SPF storm

The per-area SPF counter climbs faster than you can read it. ospfd sits at the top of top. The console gets sluggish.

Cause: a flapping adjacency or an unstable link, usually on a segment with several routers so each flap costs every router an SPF.

Diagnostic: show ip ospf neighbor shows a neighbour whose Up Time keeps resetting; the log shows repeated adjacency changes for the same neighbour.

Fix: stabilise the flapping side. Raising max-holdtime throttles how often the router recalculates; it does not reduce how often the topology changes, and the LSA flooding continues regardless.

The interface that is silently passive

A passive OSPF interface sends no Hellos and forms no adjacency. Its subnet is still advertised — it appears in this router’s Router LSA as a stub link, so the rest of the area routes toward it — but no neighbour will ever come up across it.

That is exactly what you want on a user-facing VLAN, and it is a half-hour outage when it lands on a transit link by accident. The symptom is asymmetric and confusing: the prefix is reachable from the rest of the area, so the “is OSPF working?” test passes, while the adjacency you were expecting simply never appears in show ip ospf neighbor, with no error anywhere.

On VyOS 1.5 the per-interface flag is:

set protocols ospf interface eth2 passive

The fleet-wide inversion — everything passive unless named — is:

set protocols ospf passive-interface default
set protocols ospf interface eth1 passive disable

passive disable is the exception marker: with passive-interface default in place, only the interfaces carrying it will speak OSPF. This is the safer default for an edge router with many user VLANs and two uplinks, because a new VLAN is silent until someone deliberately makes it speak. The older per-interface passive-interface eth2 form was migrated to interface eth2 passive in VyOS 1.4; if you are reading a configuration that still uses it, you are reading a 1.3-era document.

Validation — what proves the link-state model is healthy

show ip ospf
show ip ospf neighbor
show ip ospf interface
show ip ospf database
show ip ospf database self-originate
show ip ospf route
show ip route ospf
show log | match ospfd

A healthy result on a stable network:

• show ip ospf database — every router that should be in the area has a Type 1; every broadcast segment with a DR has a Type 2; nothing is sitting near MaxAge (3600) that ought to be refreshed at 1800.
• show ip ospf database self-originate — exactly the LSAs this router originated, and no more. Its most useful reading is negative: if this router’s own Type 1 is missing here, the router is not participating in the area at all and every other symptom follows from that.
• show ip ospf neighbor — every adjacency that should exist is Full, except on a broadcast segment where two DROthers correctly stop at 2-Way. Passive interfaces produce no entry at all, which is why “the neighbour is missing” and “the neighbour is down” are different diagnoses.
• show ip ospf — the per-area SPF counter growing at a sane rate, the hold-time multiplier back at 1.
• show ip ospf route — the OSPF-internal view of what SPF produced, before zebra filtered it by administrative distance. When a prefix is in show ip ospf route but not in show ip route ospf, OSPF computed it and something else won the RIB — a static route, or another protocol with a better distance. That is a different problem from OSPF not computing it at all, and only these two commands together separate them.

A misbehaving network tells a different story. The first time an operator sees the per-area SPF count jump by hundreds between two samples, they are looking at an SPF storm. The first time they see a neighbour parked in ExStart, they are looking at an MTU mismatch. The first time they see a neighbour stuck in Init, they are looking at the next lesson.

Rollback

VyOS rollback is not one command, and the differences matter under pressure.

While the change is still uncommitted, in configuration mode:

compare
discard

compare prints the candidate against the running configuration; discard throws the candidate away.

For a change you are about to commit over the very link it affects, commit with a timer:

commit-confirm 5
commit

commit-confirm 5 commits and starts a five-minute countdown. If you do not follow it with a plain commit to confirm, VyOS reverts to the previous configuration by itself. This is the mechanism that saves an operator who has just locked themselves out of the router — and OSPF changes on an uplink are exactly that risk.

To undo a change that is already committed, the direct route is to delete or re-set the nodes you touched and commit again — the diff you took before the change tells you exactly which nodes those are. VyOS also keeps a revision archive, listed with show system commit, with show system commit diff N for what a given revision altered. Reading that archive is routine; restoring from it is not. The rollback command loads a stored revision wholesale and applies it by rebooting the router, which makes it a recovery tool rather than a way to back a single OSPF change out. Confirm how it behaves on your release before you plan a maintenance window around it.

Capture the state before you touch anything, so the post-change diff is evidence rather than memory:

show configuration commands | grep ospf > /config/user-data/ospf-before.txt
show ip ospf database > /config/user-data/lsdb-before.txt

Production discipline

Cross-course references

• The Proxmox course’s networking primitives sit on top of either an IGP or static routing. The link-state model explains why a Corosync link failure converges in well under a second while a statically routed environment needs a human.
• The Linux course’s XIX-Linux-NetFoundations covers the kernel FIB and the role of zebra in installing what SPF produced — the step between show ip ospf route and show ip route ospf.
• Part XVII (XVII-VyOS-RoutingFund) covers adjacency, control plane vs data plane, and IGP vs EGP in generic terms; this lesson specialises them to OSPF.
• Part XIX (XIX-VyOS-OSPFConfig) is the configuration counterpart: this lesson builds the model, that one sets the tree up.
• RFC 2328 section 13 (flooding), section 16 (SPF), and appendix E for the canonical definitions.

Quiz