skip to content

In OSPF, how does a router run SPF by hand over a five-router area, and what happens when two paths tie on cost?

level: middleimportance: must knowfreq 32%

answer

  1. two sets: tree and candidates
  2. cheapest candidate becomes final
  3. lower replaces, equal merges
  4. next hops inherited from parent
  5. stubs attached in stage two

basics

~20 s

OSPF's SPF moves the cheapest tentative vertex from a candidate list onto the shortest-path tree, then updates its neighbours' totals. Equal-cost totals merge their next hops instead of picking one, and stub networks are attached as leaves at the end.

solid answer

~50 s

RFC 2328's SPF keeps a **tree** of final vertices and a **candidate list** of tentative ones. It starts with the root, the router itself, on the tree, reads its router-LSA, and puts each neighbour on the candidate list at that link's cost. It then repeatedly moves the **cheapest candidate** onto the tree and examines that vertex's links. A **lower** total replaces a candidate's distance and next hops, an **equal** total **adds** its next hops, and a higher one is ignored. A vertex inherits its next hops from its parent, unless the parent is the root. When the candidate list is empty, stub networks are added as leaves. In a five-router area where R1 reaches R2 at cost 10 both directly and through R3, R2 ends up with two next hops, and every router reached through R2 inherits both.

code

pseudocode · 17 lines
pseudocode
tree = {R1: dist 0}
candidates = {}
V = R1
repeat:
    for each link V -> W with cost c in V's router-LSA:
        if W is a stub network: skip            # added in stage 2
        if W has no LSA, a MaxAge LSA, or no link back to V: skip
        if W is on tree: skip
        D = dist(V) + c
        hops = {link to W} if V == R1 else nexthops(V)
        if W not in candidates or D < candidates[W].dist:
            candidates[W] = (D, hops)
        else if D == candidates[W].dist:
            candidates[W].hops = candidates[W].hops + hops
    if candidates is empty: stop
    V = cheapest candidate (a network before a router on a tie)
    move V from candidates to tree

go deeper

for a junior

Recall that SPF places the cheapest unplaced router first and that a path's cost is the sum of its links' costs, not its number of hops.

for a middle

Walk the candidate list on paper: replace on a lower total, merge next hops on an equal one, and say why a candidate's cost is final only when it joins the tree.

for a senior

Use the trace to reason about forwarding: inherited next hops, why a neighbour does not send traffic back, and which equal-cost limits are implementation choices.

for a principal

Relate the trace to design: how cost choices create or remove equal-cost paths, and how many parallel paths a design can really count on after a failure.

## The area Five routers are joined by point-to-point links, each with the same cost in both directions. OSPF allows a different cost in each direction; keeping them symmetric just shortens the trace. R5 also advertises a stub LAN, `10.5.5.0/24`, with cost 1. | Link | Cost | |---|---| | R1 to R2 | 10 | | R1 to R3 | 5 | | R2 to R3 | 5 | | R2 to R4 | 10 | | R3 to R5 | 30 | | R4 to R5 | 5 | The trace computes **R1's** view. Every router holds the same router-LSAs, and R1 is the root of its own run. ## The two sets RFC 2328 Section 16.1 keeps two sets: - the **shortest-path tree**: vertices whose cheapest distance is final; - the **candidate list**: vertices reached by some path, though not necessarily the cheapest one yet. Each candidate carries a distance and a set of **next hops**. Take the vertex just added to the tree, V, and read its LSA. Look at each link from V to a transit vertex W. Skip W if it has no LSA, if its LSA is at `MaxAge`, if its LSA has no link back to V, or if W is already on the tree. Otherwise compute **D = distance(V) + cost(V to W)**, then: 1. if W is not a candidate, or D is **lower** than its candidate distance, set W's distance to D and its next hops to this path's; 2. if D is **equal**, **add** this path's next hops to W's set; 3. if D is **higher**, leave W alone. Then move the **cheapest candidate** onto the tree and repeat. When a transit network and a router tie as cheapest, the network goes first, so that every equal-cost path is found. The run ends when the candidate list is empty. **Next hops:** a vertex reached directly from the root gets the root's own interface toward it. A vertex further away **inherits** its parent's next hops. ## The trace "via {R2, R3}" means "out the link to R2 and out the link to R3". | Step | Added to tree (distance) | Links examined | Candidate list afterwards | |---|---|---|---| | 1 | R1 (0) | R1 to R2 = 10; R1 to R3 = 5 | R2 10 via {R2}; R3 5 via {R3} | | 2 | R3 (5) | R3 to R2 = 5 + 5 = 10, equal, so add next hop; R3 to R5 = 5 + 30 = 35 | R2 10 via {R2, R3}; R5 35 via {R3} | | 3 | R2 (10) | R2 to R4 = 10 + 10 = 20 | R4 20 via {R2, R3}; R5 35 via {R3} | | 4 | R4 (20) | R4 to R5 = 20 + 5 = 25, lower than 35, so replace | R5 25 via {R2, R3} | | 5 | R5 (25) | R5's links reach only vertices already on the tree | empty, so stage 1 ends | What the trace shows: - **A candidate's distance is provisional.** R5 sat at 35 after step 2, and the path through R4 cut it to 25 two steps later. A distance is final only once its vertex joins the tree. - **Ties are kept, not broken.** At step 2 the path through R3 to R2 cost 10, the same as the direct link, so R2 got two next hops. R4 and R5 then inherited both. - **Fewer hops is not better.** The two-hop path R1, R3, R5 costs 35. The four-hop paths cost 25 and win. ## The resulting routes | Destination | Cost | Next hops from R1 | Equal-cost paths | |---|---|---|---| | R3 | 5 | R3 | R1-R3 | | R2 | 10 | R2, R3 | R1-R2; R1-R3-R2 | | R4 | 20 | R2, R3 | R1-R2-R4; R1-R3-R2-R4 | | R5 | 25 | R2, R3 | R1-R2-R4-R5; R1-R3-R2-R4-R5 | | 10.5.5.0/24 | 26 | R2, R3 | through R5 | The stub LAN is added in **stage 2**. Stub networks are not vertices in the main loop. Once the tree is built, each reachable router's stub links are attached at that router's distance plus the stub cost, here 25 + 1 = 26, and they inherit the router's next hops. ## Why handing R5's traffic to R3 does not loop R3 has a direct cost-30 link to R5, so it is tempting to think that R1 sends traffic to R3 and R3 then uses that link. But R3 runs its own SPF over the same database. From R3, the path through R2 and R4 to R5 costs 5 + 10 + 5 = 20, cheaper than 30, so R3 forwards to R2. Every router computes from the same map with the same rule, so each hop moves the packet along a shortest path. ## What OSPF leaves to the implementation - RFC 2328 Section 16.8 does not require a router to keep every equal-cost path. It may keep a fixed number, and that maximum is an implementation choice. - How traffic is spread across the kept next hops is a forwarding decision; SPF only supplies the set. - How the candidate list is stored, for example a heap or a plain list, is up to the implementation. RFC 2328 requires only that any method produce the identical tree.

  • R3 has a direct cost-30 link to R5, yet R1 sends some of R5's traffic to R3. Why does that not loop or take the 30-cost link?
    R3 runs its own SPF over the same database. From R3, the path through R2 and R4 to R5 costs 5 + 10 + 5 = 20, which beats 30, so R3 forwards to R2. With consistent databases, every hop forwards along a shortest path, so the packet keeps getting closer and never returns.
  • Must an OSPF router keep every equal-cost next hop its SPF run finds?
    No. RFC 2328 Section 16.8 lets an implementation keep only a fixed number of equal-cost routes, and says this does not affect the algorithms. The maximum is an implementation choice. How traffic is then split across the kept paths is a forwarding decision, not part of SPF.
  • In OSPF's SPF, what keeps a link that only one of its two routers advertises out of the tree?
    Step 2(b) of the stage-1 algorithm. Before W is considered, W's LSA must contain a link back to V; otherwise the link is skipped. Any link back to V is enough, even one that is not the matching half; a router whose LSA describes no link to V at all cannot be reached through V.

saying these in an interview costs you the question

  • When two OSPF paths tie on cost, the one with fewer hops is used.
  • A router's SPF distance is final as soon as it enters the candidate list.
  • SPF keeps only the first of several equal-cost paths it discovers.
  • SPF uses the cost the far-end router advertises for the link back toward it.
  • Stub networks are processed as ordinary vertices inside the main Dijkstra loop.