In OSPF, what does a router's SPF calculation take as input, and what does it produce?
answer
- one map, many roots
- the router itself is the root
- summed interface costs, not hops
- tree becomes intra-area routes
- rerun when LSA contents change
basics
~20 sAn OSPF router runs Dijkstra's shortest-path-first algorithm over its area's link-state database with itself as the root. The result is a shortest-path tree giving the lowest total cost and next hops to every destination, which becomes its routing table.
solid answer
~50 sThe input is the area's **link-state database**: the router-LSAs and network-LSAs that every router in the area holds identical copies of. Each link carries the outgoing interface cost its owner advertises. The router runs Dijkstra's algorithm with **itself as the root**, so every router builds a *different* tree from the *same* map. The output is a **shortest-path tree**. For each router and network it gives the lowest sum of link costs from the root and the next hop or hops to use, and it keeps every equal-cost path. Stub networks are added to the tree afterwards, then inter-area and external routes are derived from it, and the result is installed as the OSPF routing table. All routers compute from one consistent database, so once the databases have converged their next hops agree and forwarding does not loop.
go deeper
Recall three facts: the input is the area's link-state database, the root is the router itself, and the output is the lowest-total-cost path and next hop to every destination.
Explain the graph: routers, transit networks and stub networks as vertices, per-direction interface costs on the arcs, the both-ends check on links, and why every equal-cost path is kept.
Show what surrounds the run: an area border router runs one SPF per area, summary and external routes hang off the tree, and a refresh with unchanged contents triggers nothing.
Discuss the bargain link-state routing makes: CPU on every router in exchange for loop-free, consistent paths, and how area size limits what each run costs.
## What "SPF" means in OSPF OSPF (Open Shortest Path First) is a **link-state** interior gateway protocol. Inside an area, its routers do not trade finished routes with their neighbours. Every router in the area collects a description of the whole area and computes its own routes from it. That computation is the **shortest-path-first (SPF)** calculation: Dijkstra's algorithm applied to the area's topology. RFC 2328 (OSPF version 2, an Internet Standard) specifies it in Section 16, and OSPF for IPv6 (RFC 5340) keeps the same calculation. ## The input: one area's link-state database - The **link-state database (LSDB)** is the set of link-state advertisements (LSAs) a router holds for one area. Flooding keeps every router's copy identical, but how it does that is a separate subject. - SPF reads two kinds of LSA as the topology. **Router-LSAs** (type 1) are one per router and list its links and their costs. **Network-LSAs** (type 2) are one per transit multi-access network, originated by its Designated Router, and list the routers attached to it. - RFC 2328 models the database as a **directed graph** whose vertices are routers, transit networks and stub networks. An arc leaving a router carries the **cost of that router's outgoing interface**. The operator configures that cost, it must be greater than zero, and it sits in a 16-bit field of the router-LSA. Arcs from a network to its attached routers cost 0. - Costs are per direction. The cost from R1 to R2 is what R1 advertises, and R2 may advertise a different cost back. - An LSA that has reached `MaxAge` is ignored. A link between two transit vertices is used only when both ends describe it, so a vertex whose LSA has no link back is skipped. ## Running it: every router is its own root Each router runs SPF **with itself as the root**. This is the point candidates most often miss: the database is identical across the area, but the trees are not. R1's tree tells R1 how to reach everything, and R2's tree, built from the same map, tells R2. Dijkstra grows the tree outward from the root. At each step it places the unplaced vertex with the lowest total cost, and it stops when every reachable vertex is placed. A router attached to several areas, an **area border router**, runs a separate SPF for each attached area, because each area has its own database. ## The output: a tree of lowest-cost paths For every vertex it reaches, the run records: 1. the **distance from the root**, which is the sum of the interface costs along the cheapest path; 2. the **next hops**: the outgoing interface to forward on and, on a multi-access network, the neighbour's address; 3. the **parent** on the tree, which is what makes it a tree. When two paths tie on total cost, the run keeps both next hops. RFC 2328 notes that, strictly, the result is therefore not always a tree. The name stuck from the literature. | | Input | Output | |---|---|---| | What | Router-LSAs and network-LSAs of one area | Shortest-path tree rooted at this router | | Unit | Link costs, per direction | Total path cost per destination | | Same on every router? | Yes, once flooding has converged | No, each tree has a different root | | Becomes | Nothing on its own | Intra-area routes in the routing table | ## From tree to routing table RFC 2328 rebuilds the routing table from scratch on a full run, in order: - **Stage 1** builds the tree over routers and transit networks only. - **Stage 2** hangs **stub networks** onto the tree as leaves. A stub network is, for example, a router's LAN with no other OSPF router on it. Its distance is the advertising router's distance plus the stub link's cost. - **Inter-area routes** are then added from summary-LSAs, and **external routes** from AS-external-LSAs. Both use the distance the tree gave to the router that advertised them. Which LSAs carry those routes, and how far they are flooded, belongs to the subject of OSPF areas. ## Why independent computation stays consistent All routers in an area compute from the same database with the same rule, lowest total cost, so their choices agree. Each next hop is a router whose own tree continues along a shortest path toward the destination. Once the databases agree, that consistency keeps hop-by-hop forwarding loop-free. Just after a change, some routers have recomputed and others have not, and short **micro-loops** are possible in that window. That is one reason routers are careful about when they rerun SPF. ## When it runs again A recalculation follows when an LSA's contents change: a link goes down, a cost changes, a router appears. A periodic refresh that changes only the sequence number and checksum does not trigger one. Which changes need a full run, and how a router batches a burst of changes into fewer runs, are the next layers of this subject.
- Why does each OSPF router compute a different tree from an identical database?Because each router puts itself at the root. Dijkstra measures every distance from the root, so the same graph yields R1's tree on R1 and R2's tree on R2. What makes the trees consistent with each other is the shared database and the shared rule, lowest total cost. They are not the same tree.
- Does an OSPF router run SPF over the whole autonomous system at once?No. SPF runs per area, over that area's database. An area border router runs one SPF per attached area. Destinations in other areas arrive as summary-LSAs, which carry a cost from the advertising area border router rather than the remote topology, so they are added after the tree is built.
- Why does RFC 2328 say the result is not strictly a tree?Because of equal-cost multipath. When two paths to a vertex tie on total cost, SPF keeps both sets of next hops, so a vertex can have more than one parent path. RFC 2328 keeps the word tree because the literature uses it.
Every driver in a city holds the same printed map, but each plans routes from their own front door. The map is shared; the route plans are personal. An OSPF area works the same way: one link-state database, a different shortest-path tree on every router.
saying these in an interview costs you the question
- OSPF picks the route with the fewest router hops to the destination.
- Every router in an OSPF area ends up with the same shortest-path tree.
- SPF runs once over the whole OSPF domain, all areas together.
- OSPF routers in an area send each other their routing tables to run SPF on.
- Only the router that detected a failure needs to rerun SPF.