OSPF SPF 樹的生成秘密

🎭 故事

場景：五個城市的最短路線圖

Router A 現在掌握了完整的 LSDB（Link State Database）。它知道網路中有 5 台路由器和它們之間的連接：

       Router A（我）
           |
       Cost: 10
           |
       Router B
      /        \
   10/          \20
    /            \
Router C ---- Router D
        Cost:15      Cost:5
    |
    | Cost: 8
    |
  Router E

每條線上都標著 Cost（成本），代表通過這條路線需要付出的代價。Router A 現在要決定：去每個目的地的最便宜路線是什麼？

流程：Dijkstra 的魔法

初始狀態：A 到自己的距離為 0，到其他所有路由器的距離為 ∞。

第一次計算：Router A 看著和自己直接相連的鄰居：A→B 成本 10、A→C 成本 15。更新後，B 的距離最小（10），確認 B 為最近的鄰居。去 B 的最短路線：A → B（成本 10）✓

第二次計算：通過 B 計算 B 的鄰居：A→B→C 總成本 20（比直連的 15 更新為 20？不，20 > 15，不更新）。等等——A 到 C 的直連成本是 15，A→B→C 是 20，所以直連更便宜。A 到 D：A→B→D = 10+20 = 30。確認 C（距離 15）為次近。去 C 的最短路線：A → C（成本 15）✓

第三次計算：通過 C 計算 C 的鄰居：A→C→D = 15+15 = 30（不比 30 更短，持平）；A→C→E = 15+8 = 23。更新 E 的距離為 23。未確認中 D 和 E 都是最短...取 D（成本 30）。去 D 的最短路線：A → B → D 或 A → C → D（成本 30）✓

第四次計算：只剩 E，距離 23 已是最小。去 E 的最短路線：A → C → E（成本 23）✓

結果：SPF 樹建成了

Dijkstra 算法完成，Router A 有了完整的 SPF 樹（最短路徑樹），對應的路由表：

最後：Convergence（收斂）

當 Router A、B、C、D、E 都完成了 Dijkstra 計算後，整個網路達到 Convergence（收斂）——所有路由器都根據相同的信息做出了一致的路由決策。此時資料流量不會繞圈、不會有黑洞路由、網路運行最高效。

OSPF 的核心魔力：透過讓每台路由器「以自己為根」，各自運行同一份 Dijkstra 算法，最終全網路得出一致的最短路徑決策。

📍 技術摘要

Dijkstra 算法的核心思想

1. 初始化：自己的距離為 0，其他的為 ∞
2. 重複選擇：找出未確認中距離最小的路由器，確認它
3. 更新鄰居：通過該路由器計算到其鄰居的距離，如果更短則更新
4. 重複直到：所有路由器都被確認

Cost 的計算

Cost = Reference Bandwidth / Actual Bandwidth

範例：
- 10Gbps 介面：100 Mbps / 10,000 Mbps = 0.01 → 取 1
- 1Gbps 介面：100 Mbps / 1,000 Mbps = 0.1 → 取 1
- 100Mbps 介面：100 Mbps / 100 Mbps = 1
- 10Mbps 介面：100 Mbps / 10 Mbps = 10

預設 Reference Bandwidth = 100 Mbps（舊網路標準）。在高速網路中建議調高 Reference Bandwidth：auto-cost reference-bandwidth 10000（單位 Mbps）。

SPF 計算觸發條件

• LSDB 變化：有新的 LSA 到達
• 鏈路故障：某個介面掛線（Cost 變化）
• 定期重算：SPF Throttling（避免頻繁計算，設有最小計算間隔）

⚠️ 常見誤解