When an OSPF router installs a changed LSA, which changes force a full SPF run and which allow a cheaper recalculation?

## Why the cost of a change matters A full SPF run is one of the most expensive things an OSPF router does in steady operation. It rebuilds the shortest-path tree of every attached area, then every route that depends on those trees. In a large area that changes often, a full run and a single-prefix update are the difference between a busy control plane and a quiet one. RFC 2328 (OSPFv2) states which change costs what, and OSPF for IPv6 (RFC 5340) applies the same rules to its own LSA types. ## Step one: did the contents change? When a new LSA instance is installed, whether it arrived by flooding or the router originated it, Section 13.2 compares it with the old instance. Only these count as a change in contents: - the **Options** field changed; - one instance has reached **MaxAge** and the other has not; - the **length** field in the LSA header changed; - the **body**, meaning anything after the 20-byte header, changed. A new **LS sequence number** and **LS checksum** on their own are not a change. So the refresh a router performs on each of its own LSAs every 30 minutes triggers no recalculation anywhere. ## The ladder RFC 2328 sets | Changed LSA | What must be recalculated | RFC 2328 section | |---|---|---| | Router-LSA (type 1) or network-LSA (type 2) | The entire routing table, starting with SPF for each attached area | 13.2, 16 | | Summary-LSA, type 3 (network) | The best route to that one destination | 16.5 | | Summary-LSA, type 4 (AS boundary router) | The route to that ASBR, then possibly every AS-external route | 16.5 | | AS-external-LSA (type 5) | The best route to that one prefix, or nothing if an internal route exists | 16.6 | | Refresh with unchanged contents | Nothing | 13.2 | ## Why a topology change rebuilds every area A router-LSA or network-LSA describes links, so changing one can change any distance in its area's tree. RFC 2328 goes further and requires SPF for **every** area the router is attached to, not only the area whose database changed. The reason is that an **AS boundary router** can sit in more than one area. A change in the area that currently gives the best route can make an intra-area route through a different area the better one. A note in RFC 2328 adds that an implementation keeping more state can recalculate just one area. That is an optimisation, not a requirement. A full rebuild runs in this order: 1. Invalidate the routing table and keep the old one for comparison. 2. Build each attached area's tree: transit vertices first, stub networks second. 3. Add inter-area routes from summary-LSAs. 4. On an area border router attached to a transit area, check that area's summary-LSAs for better paths. 5. Compute external routes from AS-external-LSAs. ## The cheaper recalculations A **summary-LSA** (Section 16.5) describes a destination outside the area as a cost from an area border router, so a changed one rarely needs the tree. - On a router that is not an area border router, or for a backbone summary-LSA, the router invalidates that destination's inter-area route and reruns the inter-area calculation for that destination only. - If the result changes the path to an ASBR (a type 4 summary) or to a forwarding address, **all** AS-external-LSAs are re-examined. If the destination has become unreachable, external routes are rechecked for that one destination. - On an area border router, for a summary-LSA in a **transit area** (an area that a virtual link crosses), a **cost increase** forces the complete calculation, starting with SPF. For an **AS-external-LSA** (Section 16.6), nothing is recomputed if an intra-area or inter-area route to the prefix already exists, because internal routes take precedence. Otherwise the external calculation runs for that prefix only. ## Incremental and partial computation: implementation territory - **Incremental SPF** repairs only the part of a tree a change affects, such as re-parenting the subtree behind a failed link, instead of rebuilding from the root. RFC 2328 mentions such algorithms as more efficient, citing 1978 ARPANET work, and calls them **beyond the scope** of the specification. Whatever method is used must produce the identical tree. - **Partial route computation** recomputes routes for changed prefixes without rebuilding the tree. RFC 8405 names full SPF, incremental SPF and partial route computation side by side and calls the choice among them "a local consideration". - Some implementations handle a router-LSA change that touches only **stub-network links** as a stage-2 update, because stub links never alter the transit tree. RFC 2328 itself still lists any change to a router-LSA's body as a full recalculation. - OSPF for IPv6 moves prefixes out of router-LSAs and network-LSAs into separate LSAs, which makes a prefix-only change easy for an implementation to isolate. Even so, RFC 5340 lists changes to Intra-Area-Prefix-LSAs and Link-LSAs among those that recalculate the entire routing table. ## What it means in operation - A flapping **transit** link in a big area is expensive everywhere in that area. Every router's tree changes, and every area border router reruns SPF for all of its areas. - A flapping prefix that other areas see only as a **summary**, or that enters as an **external** route, costs far less per event. That is one argument for summarising at area borders. - How often these runs happen is controlled separately: SPF throttling batches a burst of changes into fewer runs.