OSPF & Intra-AS Routing
The internet is not one flat graph. It is tens of thousands of separately administered networks stitched together. Routing is therefore split into two levels: routing within one administrative network, and routing between them.
Autonomous systems
An autonomous system (AS) is a collection of routers under a single administrative control - a university, an ISP, a large company - identified by a globally unique AS number (ASN). Routing inside an AS is that operator's own business; routing between ASes is a matter of policy and negotiation. This split is what lets the internet scale: no router needs the full internet topology, only the topology of its own AS plus summarised reachability for the rest.
Routing protocols come in two scopes to match this structure.
| Scope | Name | Role | Example |
|---|---|---|---|
| Within an AS | Interior Gateway Protocol (IGP) | Find best paths among the AS's own routers | OSPF, IS-IS, RIP |
| Between ASes | Exterior Gateway Protocol (EGP) | Exchange reachability across AS boundaries | BGP |
OSPF as a link-state protocol
OSPF (Open Shortest Path First) is the most widely deployed intra-AS protocol. It is a link-state protocol: each router floods Link-State Advertisements (LSAs) describing the state and cost of its own links to every other router in the area. Each router assembles these into an identical link-state database - a full map of the AS - and runs Dijkstra's shortest-path algorithm locally to build its forwarding table.
Because every router computes paths from the same map, OSPF converges quickly and consistently after a topology change: whoever detects a failed link floods an updated LSA, and every router recomputes.
Worked example: computing one router's shortest-path tree
Say an area has five routers - A, B, C, D, E - with these link costs (set by the administrator, roughly inverse to bandwidth):
| Link | Cost |
|---|---|
| A - B | 2 |
| A - C | 5 |
| B - C | 1 |
| B - D | 4 |
| C - D | 1 |
| D - E | 3 |
Router A runs Dijkstra from itself. It settles the nearest unsettled node each round and relaxes that node's neighbours:
| Round | Settles | Distance so far | Updated candidates |
|---|---|---|---|
| 1 | A (source) | A=0 | B=2 (via A), C=5 (via A) |
| 2 | B (cost 2, cheapest candidate) | A=0, B=2 | C=3 (via A-B-C, 2+1=3, beats the direct 5), D=6 (via A-B-D, 2+4=6) |
| 3 | C (cost 3, now cheapest) | A=0, B=2, C=3 | D=4 (via A-B-C-D, 3+1=4, beats the earlier 6) |
| 4 | D (cost 4) | A=0, B=2, C=3, D=4 | E=7 (via A-B-C-D-E, 4+3=7) |
| 5 | E (cost 7) | A=0, B=2, C=3, D=4, E=7 | all nodes settled |
The key moment is round 2: the direct A - C link costs 5, but going through B
costs only 2 + 1 = 3, so Dijkstra revises C's tentative distance downward
before ever settling it. Router A's final forwarding table sends anything destined
for C, D, or E out the link toward B, since B sits on every one of those shortest
paths.
Notable OSPF features:
- Cost-based metrics - link costs are set by the administrator (often derived from bandwidth), not fixed hop counts, so OSPF can prefer faster links.
- Authentication - LSAs can be authenticated so a rogue router cannot inject false topology.
- Equal-cost multipath - traffic can be balanced across multiple equal-cost paths.
Areas: why intra-AS routing scales
Flooding every LSA to every router works fine for a small AS, but in a large one the link-state database and the Dijkstra computation would grow expensive. OSPF solves this with a two-level hierarchy of areas.
- Routers are grouped into areas, each running its own link-state flooding and Dijkstra computation only within the area. A router keeps a detailed map of its own area, not the whole AS.
- A special backbone area (area 0) interconnects all other areas. Area border routers sit on the boundary and summarise their area's reachability into the backbone, rather than leaking every internal link.
- Because detailed topology stays local and only summaries cross area boundaries, the database and computation each router must handle stay bounded even as the AS grows.
This is the same scaling principle as address aggregation in the data plane: keep detail local, advertise summaries globally. It is exactly what BGP does at the next level up, between whole autonomous systems.
Before two OSPF routers exchange LSAs, they must form a neighbor adjacency, which involves exchanging Database Description packets sized to each router's configured MTU. A very common real-world misconfiguration - one router's interface set to the default 1500-byte MTU while its neighbor's was changed to 9000 (jumbo frames) for a storage network - causes the larger router's oversized DBD packets to be silently dropped. The two routers appear to be talking (they exchange Hello packets fine, since Hellos are small) but their adjacency state gets permanently stuck in ExStart, never reaching Full, so no LSAs are ever exchanged between them and no routes learned through that link. Because Hello still works, a quick health check that only looks for "is the neighbor listed" can miss this entirely - the fix is checking the adjacency state, not just neighbor presence, and confirming both ends agree on interface MTU.