Loading learning content...
OSPF's Link-State Database is a comprehensive map of network topology, but a map alone doesn't tell you which path to take. The transformation from raw topology data to actionable routing decisions happens through the SPF (Shortest Path First) calculation—OSPF's implementation of Dijkstra's algorithm.
Every time the LSDB changes—a new link appears, a cost is modified, or a router fails—OSPF runs the SPF algorithm to recompute the optimal paths to all destinations. This calculation produces the SPF tree, a shortest-path tree rooted at the calculating router that determines the next-hop for every reachable destination.
SPF calculation is where link-state theory becomes routing practice. Understanding this algorithm reveals why OSPF makes the forwarding decisions it does, how convergence time is affected by network size, and what optimizations make modern OSPF implementations efficient.
By the end of this page, you will understand: (1) How Dijkstra's algorithm applies to OSPF routing, (2) The complete step-by-step SPF tree construction process, (3) How costs and tie-breaking determine path selection, (4) SPF scheduling and throttling mechanisms, (5) Partial/incremental SPF optimizations, and (6) The relationship between SPF and OSPF convergence.
Dijkstra's algorithm, invented by Edsger Dijkstra in 1956, solves the single-source shortest path problem: given a graph with weighted edges, find the shortest path from a source node to all other nodes. OSPF directly implements this algorithm using the LSDB as the graph.
Algorithm Overview:
The algorithm maintains two conceptual sets:
Starting from the root (the router running the calculation), the algorithm repeatedly:
The Core Insight:
Once a node moves to the SPF tree, its shortest path is guaranteed. Why? Because all remaining candidates have equal or higher costs. Any path to this node through a candidate would be longer than the direct path we've already found.
Dijkstra's Algorithm - Pseudocode═══════════════════════════════════════════════════════════════════════════ function dijkstra(graph, source): // Initialize distances for each vertex v in graph: distance[v] = INFINITY predecessor[v] = NULL add v to candidate_list distance[source] = 0 // Main loop while candidate_list is not empty: // Select vertex with minimum distance u = vertex in candidate_list with minimum distance[u] if distance[u] == INFINITY: break // Remaining vertices unreachable // Move u to SPF tree remove u from candidate_list add u to spf_tree // Relax edges from u for each neighbor v of u: edge_cost = cost(u, v) alternative = distance[u] + edge_cost if alternative < distance[v]: distance[v] = alternative predecessor[v] = u return distance[], predecessor[] ═══════════════════════════════════════════════════════════════════════════ Key Concepts Applied to OSPF:────────────────────────────────────────────────────────────────────────────• graph: The LSDB (Link-State Database)• source: The router running SPF (self)• vertices: Routers (from Router LSAs) and stub networks• edges: Links between routers (from Router LSA link entries)• cost: Interface cost (derived from bandwidth or configured)• distance: Total cost from source to each destination• predecessor: Parent in SPF tree (determines next-hop) Time Complexity: O((V + E) log V) with priority queue• V = number of vertices (routers + networks)• E = number of edges (links)| Interface Type | Bandwidth | Default Cost | Calculation |
|---|---|---|---|
| Serial (T1) | 1.544 Mbps | 64 | 10⁸ ÷ 1,544,000 = 64 |
| Ethernet | 10 Mbps | 10 | 10⁸ ÷ 10,000,000 = 10 |
| Fast Ethernet | 100 Mbps | 1 | 10⁸ ÷ 100,000,000 = 1 |
| Gigabit Ethernet | 1000 Mbps | 1 | 10⁸ ÷ 1,000,000,000 = 1 (capped) |
| 10 Gigabit Ethernet | 10 Gbps | 1 | 10⁸ ÷ 10,000,000,000 = 1 (capped) |
The default cost formula (10⁸ ÷ bandwidth) produces identical costs for any link ≥100 Mbps. This means OSPF can't distinguish Fast Ethernet from 100 Gigabit Ethernet! Use auto-cost reference-bandwidth (e.g., 100000 for 100 Gbps reference) or manually set interface costs to properly differentiate high-speed links.
Let's trace through a complete SPF calculation on a realistic network topology. This step-by-step walkthrough demonstrates exactly how OSPF builds the shortest-path tree.
Example Network:
Network Topology for SPF Example═══════════════════════════════════════════════════════════════════════════ ┌─────┐ ┌─────│ R2 │─────┐ │ └─────┘ │ 10 │ │ 5 │ │ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │ Net │──5────│ R1 │────20─────│ R3 │────8──│ R4 │ │ A │ │ │ │ │ │ │ └─────┘ └──┬──┘ └─────┘ └──┬──┘ │ │ 15│ │3 │ │ │ ┌─────┐ │ └──────────│ R5 │──────────────┘ └──┬──┘ │12 │ ┌────┴────┐ │ Net B │ └─────────┘ Link Costs:• R1─R2: 10 • R2─R3: 5 • R3─R4: 8• R1─R3: 20 • R1─R5: 15 • R4─R5: 3• R1─NetA: 5 • R5─NetB: 12 SPF Calculation is run FROM R1's perspective.Step-by-Step SPF Calculation (from R1):
SPF Calculation from R1═══════════════════════════════════════════════════════════════════════════ INITIALIZATION:───────────────────────────────────────────────────────────────────────────SPF Tree: {R1} (root, cost 0)Candidates: {} (empty)Predecessor: R1.pred = NULL ═══════════════════════════════════════════════════════════════════════════ITERATION 1: Process R1 (just became part of SPF tree)───────────────────────────────────────────────────────────────────────────R1 has links to: R2(10), R3(20), R5(15), NetA(5) Add/update candidates: • R2: cost = 0 + 10 = 10, pred = R1 [NEW] • R3: cost = 0 + 20 = 20, pred = R1 [NEW] • R5: cost = 0 + 15 = 15, pred = R1 [NEW] • NetA: cost = 0 + 5 = 5, pred = R1 [NEW] SPF Tree: {R1}Candidates: {NetA(5), R2(10), R5(15), R3(20)} ↑ minimum cost ═══════════════════════════════════════════════════════════════════════════ITERATION 2: Select minimum from candidates → NetA(5)───────────────────────────────────────────────────────────────────────────Move NetA to SPF tree.NetA is a stub network (no further connections). SPF Tree: {R1, NetA(5)}Candidates: {R2(10), R5(15), R3(20)} ↑ minimum cost ═══════════════════════════════════════════════════════════════════════════ITERATION 3: Select minimum from candidates → R2(10)───────────────────────────────────────────────────────────────────────────Move R2 to SPF tree.R2 has links to: R1(10), R3(5) • R1: Already in SPF tree, skip • R3: current cost 20, alternative = 10 + 5 = 15 → BETTER! Update: R3.cost = 15, R3.pred = R2 SPF Tree: {R1, NetA(5), R2(10)}Candidates: {R5(15), R3(15)} ← R3 cost reduced from 20 to 15! ↑ minimum (tie, use Router ID – R3 < R5) ═══════════════════════════════════════════════════════════════════════════ITERATION 4: Select minimum → R3(15) [tie broken by RID or arbitrary]───────────────────────────────────────────────────────────────────────────Move R3 to SPF tree.R3 has links to: R1(20), R2(5), R4(8) • R1: Already in SPF tree, skip • R2: Already in SPF tree, skip • R4: cost = 15 + 8 = 23, pred = R3 [NEW] SPF Tree: {R1, NetA(5), R2(10), R3(15)}Candidates: {R5(15), R4(23)} ↑ minimum cost ═══════════════════════════════════════════════════════════════════════════ITERATION 5: Select minimum → R5(15)───────────────────────────────────────────────────────────────────────────Move R5 to SPF tree.R5 has links to: R1(15), R4(3), NetB(12) • R1: Already in SPF tree, skip • R4: current cost 23, alternative = 15 + 3 = 18 → BETTER! Update: R4.cost = 18, R4.pred = R5 • NetB: cost = 15 + 12 = 27, pred = R5 [NEW] SPF Tree: {R1, NetA(5), R2(10), R3(15), R5(15)}Candidates: {R4(18), NetB(27)} ← R4 cost reduced from 23 to 18! ↑ minimum cost ═══════════════════════════════════════════════════════════════════════════ITERATION 6: Select minimum → R4(18)───────────────────────────────────────────────────────────────────────────Move R4 to SPF tree.R4 has links to: R3(8), R5(3) • R3: Already in SPF tree, skip • R5: Already in SPF tree, skip SPF Tree: {R1, NetA(5), R2(10), R3(15), R5(15), R4(18)}Candidates: {NetB(27)} ↑ only remaining ═══════════════════════════════════════════════════════════════════════════ITERATION 7: Select minimum → NetB(27)───────────────────────────────────────────────────────────────────────────Move NetB to SPF tree.NetB is a stub network (no further connections). SPF Tree: {R1, NetA(5), R2(10), R3(15), R5(15), R4(18), NetB(27)}Candidates: {} ← EMPTY ═══════════════════════════════════════════════════════════════════════════SPF CALCULATION COMPLETE═══════════════════════════════════════════════════════════════════════════Resulting SPF Tree and Routing Table:
| Destination | Cost | Predecessor | Next-Hop | Out Interface |
|---|---|---|---|---|
| Network A | 5 | R1 | Direct | Eth0 (to NetA) |
| R2 | 10 | R1 | Direct | Eth1 (to R2) |
| R3 | 15 | R2 | R2 | Eth1 (to R2) |
| R5 | 15 | R1 | Direct | Eth2 (to R5) |
| R4 | 18 | R5 | R5 | Eth2 (to R5) |
| Network B | 27 | R5 | R5 | Eth2 (to R5) |
The predecessor chain determines the next-hop. For R4: pred = R5, and R5.pred = R1 (root). So the path is R1→R5→R4, and the next-hop is R5. For any destination, trace predecessors back to the root—the first hop after the root is the next-hop.
When multiple paths to a destination have the same total cost, OSPF can install all of them in the routing table. This is Equal-Cost Multi-Path (ECMP) routing, which provides load balancing and redundancy without any additional configuration.
When ECMP Occurs:
In our previous example, if the R1-R5 link cost were 10 instead of 15, then:
Let's create a clearer ECMP example:
ECMP Example Topology═══════════════════════════════════════════════════════════════════════════ ┌─────┐ ┌──10───│ R2 │───10──┐ │ └─────┘ │ ┌─────┐ ┌─────┐ │ R1 │ │ R4 │ └─────┘ └─────┘ │ ┌─────┐ │ └──10───│ R3 │───10──┘ └─────┘ SPF Calculation from R1:───────────────────────────────────────────────────────────────────────────To reach R4: • Path A: R1 → R2 → R4 = 10 + 10 = 20 • Path B: R1 → R3 → R4 = 10 + 10 = 20 Both paths have EQUAL COST! OSPF behavior:───────────────────────────────────────────────────────────────────────────Rather than picking one, OSPF installs BOTH next-hops: Destination: R4 (and any networks behind R4) Cost: 20 Next-Hops: [R2, R3] ← ECMP! Traffic to R4 is load-balanced across both paths. Routing Table Entry:───────────────────────────────────────────────────────────────────────────O 10.4.0.0/24 [110/20] via 10.1.2.2 (R2), 00:05:00, Eth0 [110/20] via 10.1.3.3 (R3), 00:05:00, Eth1ECMP Implementation Considerations:
| Aspect | Default Behavior | Configuration Option |
|---|---|---|
| Maximum paths | 4 (vendor default) | maximum-paths <1-32> under OSPF process |
| Hash algorithm | 5-tuple (src/dst IP, ports, protocol) | Often configurable; some platforms offer per-packet |
| Path selection | First equal-cost path found during SPF | Consistent per-flow hashing for stable paths |
| Failure handling | Remove failed path, continue using others | BFD for fast detection |
Modern implementations typically use per-flow hashing (based on packet 5-tuple) rather than per-packet load balancing. Per-packet balancing can cause out-of-order delivery, breaking TCP performance. Per-flow ensures all packets of a flow take the same path while still distributing different flows across paths.
SPF calculation consumes CPU resources. In a network with frequent changes, running SPF after every single LSA update would overload the router. OSPF implementations therefore use SPF scheduling and throttling to balance convergence speed against CPU protection.
SPF Throttling Mechanism:
Modern OSPF implementations use an exponential backoff algorithm for SPF scheduling:
SPF Throttling Algorithm═══════════════════════════════════════════════════════════════════════════ Parameters (Cisco IOS defaults shown):• spf-start: 5000 ms (5s) — Initial wait before first SPF after trigger• spf-hold: 10000 ms (10s) — Minimum time between consecutive SPFs• spf-max-wait: 10000 ms (10s) — Maximum holddown between SPFs Timeline Example:───────────────────────────────────────────────────────────────────────────T=0s: Network stable, no SPF scheduledT=1s: LSA received (topology change!) → SPF scheduled for T=1s + spf-start = T=6sT=2s: Another LSA received → SPF already scheduled, no changeT=6s: SPF runs (first) → Hold timer starts: next SPF no earlier than T=16sT=8s: Another LSA received → SPF scheduled for T=16s (respecting hold)T=16s: SPF runs (second, within hold) → Hold doubles: 10s → 20s (exponential backoff) → Next SPF no earlier than T=36sT=20s: More LSAs received → SPF scheduled for T=36sT=36s: SPF runs (third) → Hold doubles again: 20s → 40s, but capped at max-wait (10s) → Actually uses max-wait: next SPF no earlier than T=46s ... If no LSA changes for max-wait period: → Hold timer resets to initial spf-hold → System returns to default responsiveness Aggressive Settings for Fast Convergence:───────────────────────────────────────────────────────────────────────────router ospf 1 timers throttle spf 50 200 5000 • spf-start: 50 ms — Start SPF quickly after first change• spf-hold: 200 ms — Short gap for batch changes• spf-max-wait: 5000 ms — Cap backoff at 5 seconds These aggressive settings suit data centers where:• Links are reliable (fewer false triggers)• Fast convergence is critical (milliseconds matter)• CPU capacity is abundant (modern routers)SPF Throttling Benefits:
In addition to SPF throttling, OSPF throttles LSA generation and acceptance. This prevents a misbehaving router from overwhelming the OSPF domain with rapid LSA updates. The timers throttle lsa all command controls this behavior. Together, SPF and LSA throttling protect the network from routing instability.
Full SPF calculation processes the entire LSDB, which is expensive for large networks. Modern OSPF implementations include optimizations that avoid full recalculation when possible.
Optimization Levels:
| Technique | When Used | What It Avoids | CPU Savings |
|---|---|---|---|
| Full SPF | Network topology change (Router/Network LSA) | Nothing—complete recalculation | None (baseline) |
| Partial Route Calculation (PRC) | Type 3/5/7 LSA change (summary/external) | SPF tree recalculation | Significant (50-90%) |
| Incremental SPF (iSPF) | Small topology change (single link) | Recalculates only affected branches | Moderate (10-50%) |
Partial Route Calculation (PRC):
PRC recognizes that not all LSA changes require rebuilding the SPF tree. Inter-area and external routes (Type 3/5/7 LSAs) don't affect the intra-area topology—they're "attached" to the existing SPF tree.
When a Type 3 or Type 5 LSA changes:
Example:
Partial Route Calculation Example═══════════════════════════════════════════════════════════════════════════ Scenario: External route 10.99.0.0/16 exists via ASBR1 (cost 50) A new LSA announces the same route via ASBR2 (cost 30) Without PRC:───────────────────────────────────────────────────────────────────────────1. Receive new Type-5 LSA2. Trigger full SPF calculation (O(V+E) log V)3. Rebuild entire SPF tree4. Re-attach all external routes5. Install new route for 10.99.0.0/16 via ASBR2 With PRC:───────────────────────────────────────────────────────────────────────────1. Receive new Type-5 LSA2. Detect: LSA type is 5 (external), not 1/2 (topology)3. Skip SPF tree calculation entirely4. Recalculate only 10.99.0.0/16: • Current best: ASBR1 at cost (SPF to ASBR1) + 50 • New option: ASBR2 at cost (SPF to ASBR2) + 30 • Compare, select ASBR25. Install updated route CPU savings: 90%+ for external route changes in large networks Verification (Cisco IOS):───────────────────────────────────────────────────────────────────────────show ip ospf | include SPF SPF algorithm executed 15 times Number of external LSA 250. Checksum Sum 0x012345 debug ip ospf spf statistic OSPF: Schedule SPF early, router ID change OSPF: Begin SPF, process 1, router ID 1.1.1.1 OSPF: PRC finished, routes updated: 1Incremental SPF (iSPF):
iSPF optimizes full SPF for small topology changes by recognizing that a single link change only affects a portion of the SPF tree. Instead of rebuilding from scratch, iSPF:
iSPF is particularly effective when a leaf link changes—only destinations beyond that link need recalculation.
The specific names and implementations of SPF optimizations vary by vendor. Cisco uses "PRC" and "iSPF"; Juniper uses "partial SPF" terminology. The underlying concepts are similar, but check your platform's documentation for exact behavior and configuration.
OSPF convergence—the time from a network change to stable routing tables across all routers—is directly impacted by SPF calculation. Understanding the components of convergence time helps optimize network recovery.
Components of OSPF Convergence Time:
OSPF Convergence Timeline═══════════════════════════════════════════════════════════════════════════ Event: Link R1-R2 fails T=0ms: Physical link fails (carrier loss) │ ├─ [Failure Detection Time] │ • Interface down detection: ~50ms (carrier loss) │ • OR: BFD detection: ~150ms (3 × 50ms intervals) │ • OR: Hello dead interval: 40,000ms (worst case!) │T=50ms: R1 detects link down, generates new Router LSA │ ├─ [LSA Origination Time] │ • LSA creation and validation: ~1ms │ • Subject to LSA throttling (min 50ms between) │T=51ms: R1 floods LSA to other neighbors │ ├─ [Flooding Time] │ • Propagation to all routers in area │ • Per-hop: 1-5ms (packing + transmission) │ • Total: hops × per-hop delay │T=60ms: All routers in area have received new LSA │ ├─ [SPF Delay] │ • SPF throttle start time: 50-5000ms (configurable) │ • Batches rapid changes │T=110ms: SPF scheduled to run (assuming 50ms spf-start) │ ├─ [SPF Calculation Time] │ • Depends on network size and CPU │ • Small network: <10ms │ • Large enterprise: 50-200ms │ • Very large: 500ms-2s │T=120ms: SPF complete, new routes calculated │ ├─ [RIB/FIB Update Time] │ • Route table update: ~1ms │ • FIB programming: 1-50ms (depend on hardware) │T=130ms: Forwarding plane updated ───────────────────────────────────────────────────────────────────────────TOTAL CONVERGENCE: ~130ms (optimized) to 40+ seconds (default) Key Variables:• Failure detection dominates if using Hello dead interval• SPF delay is often the largest component for fast detection• FIB programming can be significant on large route tables| Component | Default | Optimized | How to Tune |
|---|---|---|---|
| Failure detection | 40s (Hello dead) | 50-150ms | Use BFD |
| LSA origination | 5s throttle | 50ms | timers throttle lsa all 50 50 5000 |
| SPF delay | 5-10s | 50-200ms | timers throttle spf 50 200 5000 |
| FIB programming | Platform-specific | Platform-specific | Use hardware with fast FIB updates |
Network Size Impact:
SPF calculation time grows with network complexity. While Dijkstra's algorithm is O((V+E) log V), real-world factors like memory access patterns, cache behavior, and implementation quality affect actual performance.
Large OSPF networks benefit from proper area design. SPF runs independently within each area. A change in Area 10 triggers SPF only in Area 10 (plus ABR recalculation for summaries). This contains SPF scope and improves convergence predictability.
Understanding what triggers SPF calculations and how long they take is essential for network monitoring and optimization. Most OSPF implementations provide detailed SPF statistics.
Monitoring Commands:
12345678910111213141516171819202122232425262728293031323334
! View SPF execution historyshow ip ospf | section SPF SPF algorithm executed 47 times ! Detailed SPF log (newer IOS versions)show ip ospf statistics Area 0: SPF algorithm executed 47 times SPF calculation time Delta : 4 msec SPF hold : 10000 msec SPF next : 00:00:05 ! Very detailed SPF timingshow ip ospf rib internal SPF logging detailed output ! Check what triggered last SPFdebug ip ospf spf statistic (careful - verbose!) OSPF: Begin SPF, process 1, router ID 1.1.1.1 OSPF: Starting SPF algorithm OSPF: SPF tree root is this router OSPF: SPF Time: 4 ms OSPF: LSA origin 2.2.2.2 arrived on GigabitEthernet0/0 ! View routing table to see SPF resultsshow ip route ospf | include O O 10.2.0.0/24 [110/20] via 10.1.1.2, 00:01:30, GigabitEthernet0/0 O 10.3.0.0/24 [110/30] via 10.1.1.2, 00:01:30, GigabitEthernet0/0 ! Cost verificationshow ip ospf interface brief Interface PID Area IP Address Cost State Nbrs Gi0/0 1 0 10.1.1.1 1 DR 1 Gi0/1 1 0 10.1.2.1 10 DR 1Junos Equivalent:
12345678910111213141516
# View SPF statisticsshow ospf statistics SPF runs : 23 Last full SPF : 00:05:32 ago # Detailed SPF events show ospf log Jan 15 10:30:15 SPF started for area 0.0.0.0 Jan 15 10:30:15 SPF done for area 0.0.0.0, RT calculated: 12 Jan 15 10:30:15 Total SPF time: 2 ms # View SPF tree (useful for debugging)show ospf route extensive # Monitor in real-timemonitor traffic interface ge-0/0/0 ospf| Metric | Normal Range | Investigation Trigger | Possible Causes |
|---|---|---|---|
| SPF runs/hour | < 10 (stable) | 50/hour | Flapping link, misconfiguration |
| SPF duration | < 100ms | 500ms | Large LSDB, slow CPU |
| SPF delay actual | Near configured | configured | Continuous changes triggering backoff |
| Route table churn | Minimal | Constant changes | Routing loops, summarization issues |
A high SPF run rate usually indicates an underlying problem—not an OSPF configuration issue. Investigate link stability (interface flapping), MTU mismatches causing neighbor drops, or misconfigured OSPF areas. Increasing SPF throttle just hides the symptom; find and fix the root cause.
We've explored OSPF's SPF calculation in depth—from Dijkstra's algorithm fundamentals to practical monitoring techniques. Let's consolidate the key concepts:
What's Next:
With SPF calculation producing shortest paths within an area, we need to examine how OSPF handles larger networks: Area Types. OSPF areas segment the network to limit LSA flooding and SPF scope, but different area types have different behaviors regarding which LSAs they permit.
You now understand how OSPF transforms its Link-State Database into forwarding decisions through SPF calculation. This knowledge is essential for network design (sizing areas appropriately), troubleshooting (understanding why specific paths are chosen), and optimization (tuning SPF timers for your environment).