OSPF in depth

If the idea of a link-state protocol is new, start with dynamic routing on networks.jelia.nyc: it shows OSPF flooding a map and running Dijkstra over a network you can break. This chapter assumes that picture and opens up the protocol that makes it work. The rules here come from RFC 2328, OSPF version 2, published in April 1998 and still the standard for IPv4.

OSPF does not use TCP or UDP. Its packets are carried directly inside IP with protocol number 89, which means OSPF has to provide its own reliability: it numbers, acknowledges and retransmits what matters. On broadcast links it sends to two reserved multicast groups, 224.0.0.5 (all OSPF routers) and 224.0.0.6 (the designated routers), with a TTL of 1 so nothing leaves the local link. OSPF for IPv6 uses FF02::5 and FF02::6 the same way.

Every OSPF packet starts with the same 24-byte header carrying the sender's router ID, a 32-bit number written like an IPv4 address that names the router for life, and the area ID of the link it was sent on. Behind the header is one of only five packet types. Everything the protocol does, from first contact to keeping a thousand-router database in step, is a conversation in these five.

A router running OSPF on an interface multicasts a Hello every HelloInterval. A Hello is short, but it does three jobs. It announces "I am here." It states the parameters the sender insists on. And it lists every router the sender has heard on this link, which is how two routers find out that they can hear each other in both directions.

Before a router accepts a neighbor, it checks the received Hello against its own settings. If certain fields differ, the Hello is silently thrown away. Nothing is logged by the protocol itself, and the neighbor simply never appears. Most "OSPF won't come up" tickets are one of these fields.

Section 10 of RFC 2328 describes each neighbor relationship as a finite-state machine. Each router keeps one state per neighbor, and the two ends move through the states together as the conversation progresses. The names are worth learning, because they are what every router's show command prints, and the state a neighbor is stuck in tells you which step failed.

The step from 2-Way to ExStart is where the routers decide whether to become adjacent at all. On a point-to-point link they always do. On a LAN, a router only forms adjacencies with the designated router and the backup, for reasons the next section explains. In ExStart, each side sends an empty DBD claiming to be master; the one with the higher router ID wins and sets the DBD sequence number. In Exchange, they trade DBDs listing every LSA header in their databases. Each compares the other's list with its own, and anything it lacks, or holds in an older version, goes on a request list. In Loading, the LSRs go out and the LSUs come back. When both request lists are empty, both are Full.

The MTU check happens in the DBD, not the Hello, which is why an MTU mismatch produces such a confusing symptom. Hellos are small and pass fine, so the routers reach 2-Way. Then each DBD carries the sender's interface MTU, and RFC 2328 section 10.6 says a router must reject a DBD whose MTU is larger than it can receive without fragmentation. The router with the smaller MTU keeps rejecting, the other keeps retransmitting, and the pair sits in ExStart or Exchange indefinitely. Instrument 1 lets you watch it happen.

Picture ten routers on one Ethernet segment. If every pair formed a full adjacency, that would be 10 × 9 ÷ 2 = 45 adjacencies, each with its own database exchange and its own copy of every flooded LSA. When one router announced a change, it would arrive at each of the others nine times. OSPF's answer is to elect one router on the segment as the designated router (DR) and a second as the backup designated router (BDR). Every other router, called a DROther, becomes fully adjacent with only those two.

A router sends an update to 224.0.0.6, which only the DR and BDR listen to. The DR then re-floods it to 224.0.0.5, where everyone hears it once. The DR has a second job: it originates a network LSA (type 2) for the segment, listing every router attached to it. In the SPF graph the LAN becomes a single "pseudo-node" with a spoke to each router, instead of a tangle of router-to-router links.

The election uses the priority field in the Hello (0 to 255, default 1). The highest priority wins; ties go to the highest router ID; priority 0 means "never elect me." Crucially, the election is not pre-emptive. If a router with priority 255 boots on a segment that already has a DR, it does not take over. It waits for the DR to fail, at which point the BDR is promoted and a new BDR is elected. That stability is deliberate, because every change of DR means new adjacencies and a new network LSA. It also means the DR is often whichever router happened to boot first, which surprises people who set priorities and expect them to apply immediately.

Not every link needs any of this. On a point-to-point link, such as a fiber between two routers or a /31, there is exactly one possible neighbor, so there is no election and no network LSA. Many operators configure their Ethernet links between two routers as point-to-point for exactly that reason: adjacencies form faster and the database is smaller. NBMA networks, such as old Frame Relay clouds, elect a DR but cannot multicast, so neighbors are configured by hand.

Once routers are Full, the job changes from catching up to keeping up. The unit of information is the LSA, a link-state advertisement: one router's statement about one thing, such as "these are my links and their costs." When something changes, the router responsible re-originates the LSA and floods it. Each neighbor that receives it checks whether it is new, installs it, acknowledges it, and passes it on out of every other interface in the same area. The same LSA reaches every router in the area within a few hops' worth of delay.

Because OSPF runs on bare IP, the flooding is made reliable by hand. A router keeps each LSA it sends on a retransmission list for that neighbor until an acknowledgement comes back, and resends every RxmtInterval (5 seconds is the RFC's sample value for a LAN). Acknowledgements can be explicit, a Link State Acknowledgment packet, or implicit: if the neighbor floods the same LSA back, that counts as receipt.

Every LSA starts with a 20-byte header, and three fields in it decide what "new" means.

Type, Link State ID and advertising router together name an LSA. When two copies with the same name meet, the router compares them in a fixed order from section 13.1 of RFC 2328: the higher sequence number wins; if those are equal, the higher checksum wins; if still equal, a copy at MaxAge wins; otherwise, if the ages differ by more than 15 minutes (MaxAgeDiff), the younger copy wins. Otherwise they are the same instance.

The age field is what lets the database clean itself. An LSA's age climbs in every database. Its originator refreshes it every 30 minutes with a new sequence number, resetting the age to zero, so a healthy LSA never gets old. If the originator dies, nobody refreshes its LSAs, and after an hour they reach MaxAge and are flushed everywhere. A router that wants to withdraw an LSA on purpose does the same thing early: it sets the age to MaxAge and floods it, and every router deletes its copy. Engineers call this premature aging.

OSPFv2 defines eleven LSA types once you count the extensions, but six of them carry ordinary IPv4 routing, and knowing those six is the difference between reading an OSPF database and staring at it. The important column is the last one: how far each type floods. That flooding scope is what areas exist to control.

Types 1 and 2 are the map: together they describe every router, every link and every cost inside an area, with enough detail to run Dijkstra. Types 3 and 4 are not maps at all. They are distance-vector style summaries, "I can reach this, at this cost," which the next section shows is a deliberate choice. Type 5 carries the outside world into OSPF, and since an external route is the same everywhere, one copy floods everywhere. In a network that redistributes a few thousand external prefixes, type 5s are usually most of the database.

Link state has a scaling problem built in. Every router stores every type 1 and 2 LSA for its area, every change floods to every router, and every router re-runs SPF. Double the network and you more than double the work on every box. Areas break the domain into pieces. Inside an area, routers share the full map. Between areas, only summaries cross.

Area 0 is the backbone. A router with interfaces in more than one area is an area border router (ABR) and keeps a separate database for each of its areas. A router that brings external routes into OSPF is an autonomous system boundary router (ASBR). An ABR runs SPF in each of its areas, then advertises each destination it found into the other areas as a type 3 summary carrying only the prefix and its cost. A router in area 1 that sees a type 3 from its ABR doesn't know the path inside area 2; it knows the ABR's cost to the destination and adds its own cost to reach the ABR.

That is distance vector, the same "trust my neighbor's number" logic as Chapter 04, and distance vector can loop. OSPF prevents loops by forcing a strict shape. All inter-area traffic passes through area 0, and an ABR only computes inter-area routes from summaries it heard over the backbone. With a hub-and-spoke shape there is no cycle of areas for a rumour to travel around, so no count-to-infinity. That is why every area must touch area 0. An area attached only to another non-backbone area receives no inter-area routes at all. The repair for that case is a virtual link: a configured tunnel through a transit area that makes a distant ABR count as attached to the backbone. It works, and it is usually a sign the design should be fixed instead.

Summaries are where areas pay off. An ABR can be configured with a range, such as 198.51.100.0/24 for area 1, and then advertises the whole area as one type 3 instead of one per subnet. A link flapping inside area 1 no longer changes anything outside it, because the range stays up while any part of it is reachable. That containment of churn is often worth more than the memory saved.

Many areas have only one or two ways out. For them, thousands of type 5 externals carry no information: every external destination is reached through the ABRs anyway. A stub area refuses type 5 and type 4 LSAs; its ABRs inject a single default route as a type 3 instead. RFC 2328 also lets the ABR suppress some or all of the other type 3 summaries into a stub, which vendors call a totally stubby area: the routers inside see their own area's map plus one default route per ABR, and nothing else. The price is that a stub area cannot contain an ASBR, and a virtual link cannot pass through it.

That restriction is awkward when a branch site's area should be stub but has one router redistributing a few local routes. RFC 3101 (January 2003) defined the not-so-stubby area, NSSA, for that case. An NSSA still blocks type 5 from outside, but an ASBR inside it may originate type 7 LSAs, which flood only within the NSSA. At the border, one ABR is elected translator (by highest router ID, unless configured) and re-originates each type 7 as a type 5 for the rest of the domain.

With a synchronised database, each router builds a graph from the type 1 and type 2 LSAs of each area, puts itself at the root, and runs Dijkstra's algorithm to find the cheapest path to every node. networks.jelia.nyc walks through Dijkstra step by step; here, what matters is what OSPF does around it. Intra-area routes come from the tree. Inter-area routes come from adding the cost to each ABR to the cost in its type 3s. External routes come from type 5s and type 7s, either adding the internal cost to the ASBR (external type 1) or ignoring it and using only the external metric (external type 2, the usual default). When the same prefix is learned more than one way, OSPF prefers, in order: intra-area, inter-area, external type 1, external type 2, regardless of cost.

Not every change needs a full SPF. If only type 3, 4 or 5 LSAs change, the tree inside the area is unchanged, and RFC 2328 section 16.5 lets a router recompute just the affected routes. That is called partial SPF. Implementations add incremental SPF, which repairs only the damaged part of the tree after a type 1 or 2 change. And because a burst of changes can trigger a burst of SPF runs, routers delay the first run a few milliseconds and back off when changes keep coming. RFC 8405 standardized such a back-off algorithm; how to tune it, and how to repair traffic before SPF even finishes, is the subject of Chapter 07.

The numbers Dijkstra adds up are interface costs, 16-bit values from 1 to 65535 that each router assigns to its own outgoing interfaces. You can set them by hand, but most networks let the router derive them from bandwidth.

That default was chosen when 100 Mb/s was fast. Today it makes every link of 100 Mb/s or more cost exactly 1, so OSPF sees a 100 Gb/s backbone link and a 100 Mb/s backup link as equal and picks paths by hop count. The fix is to raise the reference bandwidth above the fastest link you expect, and to do it on every router at once: the FRRouting documentation is blunt that the setting must be consistent across the domain, because routers that disagree about costs compute different shortest paths, and different paths in a hop-by-hop network can mean loops.

• Fix the router ID. Set it explicitly, usually to a loopback address. A router ID picked automatically from an interface can change on reboot, and every LSA the router owns changes name with it.
• Make two-router Ethernet links point-to-point. No DR election, no wait timer, no type 2 LSA, and faster adjacency.
• Check MTU first when a neighbor sticks in ExStart or Exchange. Some implementations offer an option to ignore the MTU check; matching the MTUs is the real fix, because the large packets would be dropped later anyway.
• Use cryptographic authentication. It prevents a misconfigured or rogue box on a LAN from injecting LSAs. Plain-text passwords do not.
• Summarize at area borders, with addressing planned for it. A range only helps if each area's prefixes are contiguous.
• Keep area 0 contiguous and well connected. A partitioned backbone breaks inter-area routing in ways that are slow to diagnose.
• Make edge areas stub or NSSA when they have one way out. It shrinks their routers' databases more than anything else, as Instrument 3 shows.

OSPF is not the only link-state protocol. Chapter 06 covers IS-IS, which solves the same problems with a different packet format and a different idea of areas, and which many of the largest networks prefer.