Intra-Domain Routing with OSPF

OSPF is a link-state, intra-domain (interior gateway) routing protocol. "Intra-domain" means it routes traffic within a single Autonomous System (AS) — a network under one administrative authority, such as a university campus or an ISP's core — as opposed to inter-domain protocols like BGP that route between autonomous systems. The defining property of link-state protocols, inherited from Link-State Routing and Dijkstra's Algorithm, is that every router obtains a complete, identical map of the network's topology (the Link-State Database, LSDB) and independently computes shortest paths using Dijkstra's algorithm, rather than trusting neighbors' distance summaries as in distance-vector protocols. OSPF's key structural refinement over "plain" link-state routing is hierarchical area design. The AS is divided into areas, each identified by a 32-bit Area ID. One area, Area 0, is designated the backbone area and must be contiguous; every other (non-backbone) area must connect to the backbone, directly or via a virtual link. Routers with all interfaces in one area are internal routers; routers with interfaces in multiple areas are Area Border Routers (ABRs); routers connecting the AS to the outside world (e.g., to BGP) are Autonomous System Boundary Routers (ASBRs). Flooding of detailed topology information is confined to within an area — a router only needs the full LSDB for its own area, plus summarized reachability information for other areas, relayed by ABRs. This is the mechanism that keeps Dijkstra's per-router cost bounded even as the AS-wide router count grows into the thousands. OSPF represents topology as Link-State Advertisements (LSAs), each describing a piece of the graph: a router's links and their costs, a network's attached routers, or a summarized route to another area. LSAs are flooded reliably (with acknowledgments, sequence numbers, and aging) so that every router in the relevant area converges on an identical LSDB — this is the synchronized-database invariant that underlies OSPF's correctness. On broadcast-capable links (like Ethernet segments) with many attached routers, OSPF elects a Designated Router (DR) and Backup Designated Router (BDR) to avoid a full mesh of adjacencies, cutting flooding traffic from quadratic to linear in the number of attached routers.

1. Neighbor discovery — the Hello protocol. Each OSPF router periodically (default every 10 seconds on broadcast links, 30 seconds on non-broadcast) multicasts a Hello packet out each interface to the reserved multicast address `224.0.0.5` (AllSPFRouters). A Hello lists the sender's Router ID, area ID, Hello/Dead intervals, and the Router IDs of neighbors it has already heard from. Two routers become neighbors once they see each other listed (bidirectional communication confirmed), provided their Hello/Dead intervals, area ID, and authentication match.

2. Adjacency formation and the Designated Router. On point-to-point links, neighbors always become fully adjacent (they exchange full databases). On broadcast/multi-access networks (e.g., a shared Ethernet segment with `n` routers), forming `n(n-1)/2` full adjacencies would mean each of the `n` routers floods every LSA update to `n-1` others — Θ(n²) messages per update. OSPF instead elects a DR and BDR via a priority-based election during the Hello exchange; every other router becomes fully adjacent only to the DR and BDR, and the DR relays updates to everyone else. This reduces the flooding fan-out to Θ(n) — a direct, and provable, complexity improvement over full-mesh adjacency.

3. Database synchronization (the Exchange/Loading states). Two newly-adjacent routers exchange condensed LSA headers (Database Description packets), compute the set-difference against their own LSDB, and then explicitly request (Link State Request) and receive (Link State Update) the missing or newer LSAs. This is a reliable, bounded synchronization: every LSA exchange is acknowledged (Link State Acknowledgment), and each LSA carries a 32-bit sequence number plus an age field, so stale or duplicate copies are detected and discarded.

4. Flooding and aging. After initial synchronization, any change (a link going up/down, a cost change) triggers the affected router to originate a fresh LSA, flood it to all neighbors (who re-flood it onward, except back to the sender), and each recipient updates its LSDB and re-triggers its local Dijkstra computation. LSAs also self-expire: each carries an age that increments over time (`MaxAge`, typically 3600 seconds), forcing periodic refresh even without topology change — this guards against a stale entry silently lingering forever due to a lost flood.

5. Shortest-path computation. Once a router's LSDB for its area is complete and consistent, it runs Dijkstra's algorithm with itself as the source, treating each router and transit network as a graph node and each LSA-advertised link cost as an edge weight. The result is a Shortest Path Tree (SPT) rooted at the router; the next-hop toward each destination is read off the SPT and installed in the forwarding table.

6. Inter-area routing. An ABR runs Dijkstra separately for each area it touches, and then summarizes reachable destinations from one area as Summary LSAs (Type 3) injected into adjacent areas (typically into the backbone, and from the backbone outward to other areas). This means a router in a non-backbone area does not see the internal topology of other areas — only aggregated distances — bounding both database size and the exposed topology. ``` // OSPF core loop, per router R in area A initialize LSDB[A] = { R's own Router-LSA } initialize neighbor table = {} on receive Hello from interface i: if Hello.areaID != A or auth fails: discard if Hello lists R.RouterID: mark neighbor bidirectional if link type is broadcast/multi-access: participate in DR/BDR election using Hello.priority else: add sender to neighbor table (one-way) on neighbor becomes FULL (databases synchronized): // triggered after Database Description + LSR/LSU/LSAck exchange mark adjacency FULL schedule SPF recomputation on topology change detected locally (interface up/down, cost change): origin_LSA = build_LSA(R, changed_links) origin_LSA.seq += 1 origin_LSA.age = 0 LSDB[A][R] = origin_LSA flood(origin_LSA, exclude = incoming_interface) schedule SPF recomputation on receive LSA L from neighbor N (via LSU): existing = LSDB[A][L.originator] if existing is None or L.seq > existing.seq or L.age == MaxAge: LSDB[A][L.originator] = L send LSAck to N flood(L, exclude = interface_from(N)) schedule SPF recomputation else: // stale or duplicate — do not re-flood send LSAck to N (if L.seq == existing.seq, no update needed) procedure schedule_SPF_recomputation(): // coalesced: run once after a short delay to absorb bursts G = build_graph(LSDB[A]) // nodes = routers/networks, edges = LSA links SPT, dist = Dijkstra(G, source = R) // standard link-state shortest-path tree forwarding_table = extract_next_hops(SPT) if R is ABR: for each other area A2 that R also serves: summarize(area A, dist) -> Type-3 Summary LSAs injected into A2 install(forwarding_table) ``` The following figure shows a small AS with two non-backbone areas joined by the backbone through two Area Border Routers.

Per-router computational cost. Let a single area contain `N` router/network nodes and `E` link-state edges. Each router runs Dijkstra's algorithm on this graph whenever the area's LSDB changes materially. Using a binary heap, Dijkstra runs in ``` O((N + E) log N) ``` time per invocation — the standard bound: each of `N` extract-min operations costs `O(log N)`, and each of `E` edge relaxations costs `O(log N)` for a possible heap decrease-key. Because OSPF confines detailed topology to an area, `N` and `E` are the size of one area, not the whole AS. This is precisely the payoff of area partitioning: without it, every router in a 5,000-router AS would run Dijkstra over a 5,000-node graph on every change; with areas of, say, 200 routers each, the per-event cost drops roughly by the ratio of `(N_total log N_total)` to `(N_area log N_area)` — a substantial constant-factor (often 10–50×) reduction in practice, though asymptotically the exponent is unchanged.

Flooding cost. In the worst case, flooding one new LSA to all `n` routers in an area over a spanning-tree-like flooding pattern costs `O(n)` messages (each router forwards to its neighbors once, and duplicate suppression via sequence numbers prevents re-flooding). Without the DR/BDR mechanism, a broadcast segment with `k` attached routers would need `O(k²)` adjacency-level exchanges (each pair separately synchronizing and each flooding to every other). With a DR and BDR, only `2k` adjacencies are needed (each router to DR, each router to BDR), and the DR performs the fan-out — an asymptotic improvement from quadratic to linear in `k`.

Space. Each router stores the full LSDB of its own area(s): `O(N + E)` entries, plus summarized Type-3/Type-4/Type-5 LSAs for external and inter-area reachability, typically `O(D)` where `D` is the number of distinct destination prefixes summarized. This is far smaller than storing the entire AS topology when area sizes are bounded.

Correctness argument. OSPF's correctness reduces to two guarantees layered on top of Dijkstra's known-correct shortest path computation: 1. Database synchronization invariant. The reliable flooding protocol (sequence numbers + acknowledgments + retransmission on timeout + MaxAge expiry) guarantees that, absent partition, every router in an area eventually holds a set of LSAs that is identical and reflects the most recent originator for each entry. This is an eventual-consistency property: after a bounded number of flooding rounds following the last topology change (bounded by the area's diameter), all routers converge to the same LSDB. 2. Local Dijkstra correctness. Dijkstra's algorithm is provably correct for graphs with non-negative edge weights (OSPF costs are configured as positive integers): the standard greedy-exchange argument shows that the first time a node is popped from the priority queue, its tentative distance equals its true shortest-path distance, because any alternative path would have to pass through a node not yet finalized, whose distance is already ≥ the current minimum. Combining these: if every router in the area computes Dijkstra over the same graph, each router's shortest-path tree is mutually consistent — i.e., if router A's SPT says the next hop toward router C is B, then B's own SPT (over the same graph) will continue the path correctly, so no forwarding loops arise as long as databases remain synchronized. This is the crucial invariant that link-state protocols provide and distance-vector protocols do not automatically guarantee (count-to-infinity is precisely a failure of exactly this invariant).

Honest tradeoffs. Area partitioning buys scalability at the cost of routing optimality: because Summary LSAs only carry an aggregate distance (not full topology), a router may pick a suboptimal inter-area path when multiple ABRs offer routes into another area — OSPF cannot always find the true AS-wide shortest path once summarization hides topology (this is the classic "no optimal inter-area routing" limitation, sometimes visualized as OSPF's version of the "two ABR problem"). Additionally, convergence after a failure is not instantaneous: it requires Hello-based failure detection (bounded by the Dead interval, default 40 seconds, though sub-second Bidirectional Forwarding Detection is commonly layered on top), flooding propagation delay, and SPF recomputation delay (often deliberately throttled/coalesced to avoid computational storms during periods of instability — a real operational tension between fast convergence and CPU protection).

Consider a small Area 1 with four routers: R1, R2, R3, R4, connected as below, with link costs shown (costs are typically inversely related to bandwidth in real deployments; here we use illustrative integers).

Step 1 — Router-LSA origination. Each router builds a Router-LSA listing its interfaces and costs. R1's LSA: `{link to R2: cost 5, link to R3: cost 2}`. R3's LSA: `{link to R1: cost 2, link to R2: cost 1, link to R4: cost 4}`, and so on symmetrically.

Step 2 — Flooding. Suppose R1 comes up last. It floods its Router-LSA to R2 and R3, both of which install it, send LSAck, and re-flood to their other neighbors (R2 re-floods to R4; R3 re-floods to R4). R4, receiving the same LSA twice (once via R2, once via R3), installs it on the first copy and discards the duplicate (same Router-LSA, same sequence number) after sending an LSAck — this duplicate suppression is exactly what keeps flooding at `O(n)` rather than exploding combinatorially.

Step 3 — Synchronized LSDB. After flooding settles, all four routers hold an identical set of four Router-LSAs, describing the weighted graph above.

Step 4 — Dijkstra from R1's perspective. R1 runs Dijkstra with itself as source.

Final shortest-path tree at R1: R1→R3 (cost 2), R1→R3→R2 (cost 3), R1→R3→R4 (cost 6). Notice the path R1→R2 directly would cost 5, worse than the 3 achieved via R3 — this is exactly the kind of non-obvious shortest path that link-state computation, not naive distance-vector hop-counting, correctly discovers. R1 installs next-hop R3 for both destinations R2 and R4, since both lie on the tree branch through R3.

Step 5 — An ABR summarizes. Suppose R4 is actually an ABR also serving Area 0. R4 does not flood the raw Router-LSA graph of Area 1 into Area 0; instead it originates a Type-3 Summary LSA such as `{destination: R1's subnet, cost: 6}` (its own computed distance), hiding the internal topology (R1–R3–R4 chain) from routers in other areas — they see only "distance 6 to reach that subnet via R4," not the internal graph.

Step 6 — A link failure. If link R3–R2 (cost 1) fails, R3 and R2 each detect it (via missed Hellos, Dead interval expiry, or an immediate link-down interrupt) and originate fresh Router-LSAs with higher sequence numbers omitting that link. These flood through the area; every router — including R1 — recomputes Dijkstra. R1's new tree: R1→R3 (2), R1→R2 (5, direct, since the R3–R2 shortcut is gone), R1→R3→R4 (6, unaffected since it never used the failed link). The forwarding table updates only where necessary (R2's next hop switches from R3 to direct), demonstrating that OSPF convergence is local to the affected destinations, not a full table rebuild from scratch conceptually — though implementations do rerun Dijkstra wholesale for simplicity.

OSPF emerged from the Internet Engineering Task Force's effort to replace the earlier distance-vector RIP protocol, which suffered from slow convergence and count-to-infinity problems in larger networks. The protocol's design drew directly on link-state ideas already validated in ARPANET's internal routing redesign and in the IS-IS protocol developed contemporaneously for OSI networks — OSPF and IS-IS remain the two dominant link-state IGPs in production networks today, often compared feature-for-feature.

OSPF is one of the two dominant Interior Gateway Protocols running inside enterprise networks, university campuses, and ISP core networks worldwide (the other being IS-IS, structurally similar but historically favored by some large carriers). Data center fabrics, campus backbones, and multi-building enterprise networks configure OSPF areas to mirror physical or organizational boundaries — a headquarters building might be Area 0, each branch office its own non-backbone area. Cloud providers' internal backbone networks and large-scale ISPs use OSPF (or IS-IS) as the IGP that computes reachability to every internal router and link, information which is then fed as input to Inter-Domain Routing with BGP — BGP relies on the IGP to resolve next-hop reachability for routes learned from other autonomous systems, making OSPF (or IS-IS) a foundational layer beneath every inter-domain routing decision. Traffic engineering extensions (OSPF-TE) let OSPF distribute additional link attributes (bandwidth, delay) used by MPLS traffic engineering to compute constrained paths, extending the same link-state database mechanism far beyond simple shortest-path forwarding.

Ask the tutor: How would OSPF's area design change if a network operator wanted to minimize convergence time after frequent link flaps, versus minimizing steady-state routing table size?