OSPF Routing, in depth: adjacencies, LSAs and flooding, SPF with the two-way check and ECMP, areas and convergence

Link-state routing in one page

There are two families of routing protocol. In distance-vector routing (RIP, and conceptually BGP) each router tells its neighbours its distance to every destination, and each router runs a distributed Bellman-Ford over those claims; see Bellman-Ford and distance-vector routing. Nobody sees the topology, which is why bad news travels slowly and loops can form while it does. In link-state routing each router describes only its own links, floods that description unchanged to every router in the area, and every router computes routes from the same complete database.

That gives OSPF three jobs: keep adjacencies up; flood link-state advertisements (LSAs) so every router holds an identical link-state database (LSDB); and run shortest-path-first (SPF), which is Dijkstra, over it. Routers with different databases compute inconsistent paths, and packets can loop until flooding catches up.

Neighbours and adjacencies

Routers send Hello packets on each OSPF interface, by default every 10 seconds on broadcast and point-to-point networks, and declare a neighbour dead after the dead interval, 40 seconds by default. Hellos carry the area, the timers, authentication and the list of neighbours already heard, so a router reaches the 2-Way state when it sees its own router ID in the neighbour's Hello. Area ID, hello and dead intervals, subnet on broadcast links and some option flags must match or the neighbour never forms.

From 2-Way, routers that need a full adjacency go through ExStart (agree who leads the exchange and the starting sequence number), Exchange (send database description packets listing the LSA headers each holds), Loading (request the LSAs they are missing or hold older copies of) and finally Full. On a broadcast segment such as an Ethernet LAN with many routers, full adjacencies between every pair would be quadratic, so the routers elect a designated router (DR) and a backup (BDR). Everyone forms a full adjacency only with the DR and BDR, and the DR originates a network LSA that represents the segment as a single pseudo-node in the graph. On two-router links, use the point-to-point network type to skip both.

LSAs, the database and flooding

An LSA is a small record with a header (type, link-state ID, advertising router, sequence number, age and checksum) and a body. The types you meet in an OSPFv2 network are:

Freshness is decided by the header. A higher sequence number wins; with equal sequence numbers, a higher checksum wins, and then age rules break the tie. Sequence numbers start at 0x80000001. Each originator refreshes its LSAs every 30 minutes (LSRefreshTime), and an LSA whose age reaches MaxAge, one hour, is flushed from every database. To withdraw an LSA early, the originator floods it with its age set to MaxAge.

Flooding is reliable and hop by hop: a router that receives a newer LSA installs it, acknowledges it and sends it out of every other interface in the area, and retransmits until acknowledged. Older or duplicate copies are not re-flooded. RFC 2328 also rate-limits origination (MinLSInterval, 5 seconds) and acceptance (MinLSArrival, 1 second) of the same LSA, the first defence against a flapping link.

SPF: Dijkstra on the link-state database

The graph OSPF runs Dijkstra on has two kinds of vertex: routers, and transit networks (the pseudo-nodes from network LSAs). Edges come from router LSA links and network LSA attachments. Stub prefixes, such as a LAN with no other OSPF router, are leaves added after the tree is built. Three details distinguish SPF in OSPF from the textbook algorithm.

• The two-way check. An edge from V to W is used only if W's LSA also lists a link back to V. A router that still advertises a link to a neighbour that has died, or a half-configured link, cannot attract traffic into a black hole.
• Equal-cost multipath. When a second path with exactly the same cost reaches a vertex, its next hops are merged rather than discarded, so the routing table installs several next hops and the forwarding plane spreads flows across them; see ECMP for how hashing keeps each flow on one path.
• Next-hop inheritance. A router only needs the first hop of each path. Neighbours of the root get themselves as next hop; every other vertex inherits the next-hop set of the vertex it was reached through.

import heapq

def ospf_spf(lsdb, stubs, root):
    """lsdb:  {router: {neighbour: cost}}   one entry per router LSA (point-to-point links)
    stubs: {router: {prefix: cost}}       stub networks advertised by each router
    Returns {destination: (cost, frozenset(next_hops))} for routers and prefixes."""
    dist, hops, done = {root: 0}, {root: set()}, set()
    heap = [(0, root)]
    while heap:
        d, v = heapq.heappop(heap)
        if v in done or d > dist[v]:
            continue                                   # stale heap entry
        done.add(v)
        for w, cost in lsdb.get(v, {}).items():
            if v not in lsdb.get(w, {}):               # two-way check (RFC 2328, 16.1)
                continue
            nd = d + cost
            via = {w} if v == root else hops[v]        # next-hop inheritance
            if w not in dist or nd < dist[w]:
                dist[w], hops[w] = nd, set(via)
                heapq.heappush(heap, (nd, w))
            elif nd == dist[w] and w not in done:
                hops[w] |= via                         # equal cost: keep both paths
    routes = {r: (dist[r], frozenset(hops[r])) for r in done if r != root}
    for r in done:                                     # stub prefixes hang off the tree
        for prefix, cost in stubs.get(r, {}).items():
            cand = (dist[r] + cost, frozenset(hops[r]))
            if prefix not in routes or cand[0] < routes[prefix][0]:
                routes[prefix] = cand
            elif cand[0] == routes[prefix][0]:
                routes[prefix] = (cand[0], routes[prefix][1] | cand[1])
    return routes

The heap gives the usual O((V + E) log V) bound; the heap operations themselves are covered in Heap Operations. For an area of a few hundred routers the computation takes milliseconds on a modern control-plane CPU, which is why the timers around SPF matter more than its asymptotics.

Worked example

Run the function on the topology in the diagram. The LSDB is {'R1': {'R2': 5, 'R3': 2}, 'R2': {'R1': 5, 'R3': 3, 'R4': 1}, 'R3': {'R1': 2, 'R2': 3, 'R5': 6}, 'R4': {'R2': 1, 'R5': 2}, 'R5': {'R3': 6, 'R4': 2}} and R5 advertises the stub 10.0.5.0/24 with cost 1.

1. Settle R1 at 0. Tentative: R3 = 2 via R3, R2 = 5 via R2.
2. Settle R3 at 2. Relax R3 to R2: 2 + 3 = 5 equals the current 5, so R2's next hops become {R2, R3}. Relax R3 to R5: 8 via R3.
3. Settle R2 at 5. Relax R2 to R4: 6 with inherited next hops {R2, R3}.
4. Settle R4 at 6. Relax R4 to R5: 6 + 2 = 8 equals the current 8, so R5's next hops grow to {R3} plus {R2, R3}, which is {R2, R3}.
5. Settle R5 at 8. Add the stub: 10.0.5.0/24 at cost 9, next hops {R2, R3}.

Costs come from configuration. Many implementations default to a reference bandwidth of 100 Mbit/s divided by interface bandwidth, so 1 Gbit/s and 100 Gbit/s links both cost 1. Set the reference above your fastest link on every router, or set costs explicitly.

Areas and inter-area routing

A single area works well up to some hundreds of routers, depending on link churn and hardware. Beyond that, every flap anywhere triggers SPF everywhere and the LSDB grows with the whole network. Areas cap both. Routers inside an area see full topology only for that area. Area border routers (ABRs) connect an area to the backbone, area 0, and advertise each area's prefixes to the others as type 3 summary LSAs that carry a prefix and a cost, not topology.

Between areas OSPF therefore behaves like distance-vector routing, and a strict hierarchy prevents loops: all inter-area traffic crosses area 0, which must be contiguous, and ABRs aggregate prefixes into summary ranges so a flap inside an area stays inside it. Stub areas replace type 5 externals with a default route; NSSAs let a local boundary router inject externals as type 7 LSAs.

Convergence and timers

Convergence after a failure is a sequence of steps, each with its own timer: detect the failure, originate a new router LSA, flood it, wait for the SPF delay, compute, and update the forwarding table. With default timers, detection dominates: a neighbour that disappears without the interface going down is noticed only when the 40-second dead interval expires. Bidirectional Forwarding Detection (BFD, RFC 5880) runs lightweight probes, often every 50 to 300 milliseconds, and tells OSPF within a few probe intervals. Where the physical link goes down, the interface event is faster still.

SPF itself is throttled with an exponential back-off: the first SPF after a quiet period runs after a short initial delay, and if more changes arrive the wait doubles up to a maximum (RFC 8405 standardises one such algorithm), so a flapping link cannot pin every control-plane CPU. A change to a type 3 or type 5 LSA needs only a partial route calculation, not a new tree. On routers with many prefixes the forwarding table update often takes longer than SPF, and loop-free alternates (RFC 5286) precompute backup next hops to repair traffic locally first.

A configuration in FRRouting showing these pieces:

interface eth0
 ip ospf area 0
 ip ospf network point-to-point
 ip ospf bfd
!
router ospf
 ospf router-id 10.255.0.1
 auto-cost reference-bandwidth 400000
 timers throttle spf 50 200 5000
 passive-interface lo

Check the exact syntax and units against the documentation of your FRR or vendor release; throttle defaults and command names differ between implementations.

Failure modes

• Neighbours stuck in ExStart or Exchange. Almost always an interface MTU mismatch: database description packets from the side with the larger MTU are dropped. Fix the MTU rather than disabling the check.
• Neighbours never reach 2-Way. Mismatched area, hello or dead interval, authentication or subnet, or a filter dropping multicast to 224.0.0.5.
• Duplicate router IDs. Two routers originate LSAs with the same advertising router and keep overwriting each other, causing constant flooding and SPF runs. Set router IDs explicitly from a loopback plan.
• SPF storms. A flapping link or a bad optic triggers continuous SPF. Look at SPF run counters, add interface dampening or a carrier-delay hold-down, and keep the throttle sane.
• Unexpected paths. Default reference bandwidth makes fast links equal, or costs differ in each direction. Compare costs from both ends of each link.
• Partitioned backbone. A failure splits area 0 and inter-area routes vanish on one side even though physical paths exist through a non-backbone area.

Operating OSPF and choosing it

Day to day, three views answer most questions: the neighbour table (every expected neighbour Full, or 2-Way for DROther pairs on a LAN), the LSDB (are the expected LSAs present, and are sequence numbers stable or climbing fast), and the OSPF routing table with its next hops. On FRR and on Cisco IOS these are show ip ospf neighbor, show ip ospf database and show ip route ospf. Export SPF run counts, LSA origination and receive rates, and adjacency changes to your monitoring system, and alert on rate changes rather than absolute values. Keep a script that parses the LSDB into the dictionary format above and recomputes paths offline; it turns "why does traffic go that way" into a reproducible answer.

Alternatives: IS-IS does the same link-state job directly over layer 2 and is common in provider networks; BGP scales to larger tables and expresses policy, so many large data centres run only BGP.

What to do next

1. Run the SPF function above on the worked LSDB, then add a link and re-check the next-hop sets by hand.
2. On a lab of three to five FRR containers, bring up OSPF and watch neighbours move through the states with debug logging on.
3. Break it on purpose: mismatch an MTU, duplicate a router ID, flap a link, and note what each looks like in the neighbour table and LSDB.
4. Set the reference bandwidth above your fastest link everywhere, or set explicit costs, and verify costs match in both directions.
5. Enable BFD on links where sub-second detection matters and measure end-to-end convergence with a traffic generator.
6. Split into areas only when churn or LSDB size demands it, keep area 0 contiguous, and summarise at ABRs.