OSPF 協議 SPF 算法原理深度解析:鏈路狀態數據庫、區域劃分與 Dijkstra 計算
OSPF(Open Shortest Path First)採用鏈路狀態算法,核心計算機制為 SPF 算法(Dijkstra 算法)。本文系統闡述 OSPF 核心特性、基本概念、報文格式、數據庫建立更新、圖論模型與有限狀態機。
一、OSPF 核心特性
- 鏈路狀態數據庫 (LSDB):全網拓撲圖,每台路由器維護同一區域內一致的 LSDB。RIP 僅知下一跳,OSPF 掌握全網拓撲。
- 32 位序號機制:每個 LSA 擁有序號,增長限制(5 秒/次),序號越大越新鮮,防止舊信息泛洪。
- 快速收斂:拓撲變化觸發 LSA 更新,毫秒級泛洪,各路由器獨立重新 SPF 計算新路由表。
- 全網同步:頻繁交換 Hello/LSA 維持 LSDB 一致性。
- 直承載 IP:OSPF 直接封裝在 IP 數據報中(協議號 89),無 UDP 開銷,報文短小。結構:IP 頭(20B) + OSPF 頭(24B) + Type 1-5 LSA。
- 擴展性:路由器鏈路狀態僅涉及鄰接關係,與網絡規模無關。
二、核心概念定義
- 鏈路狀態:路由器與哪些網絡/路由器相鄰,及轉發代價。
- 自治系統 (AS):擁有自主選擇內部路由協議權限的互聯網絡。
- IGP:AS 內部路由協議(OSPF、RIP、IS-IS、EIGRP)。
- 區域:OSPF 將 AS 劃分為多個區域(Area),每區域維護獨立 LSDB,區域邊界路由器 (ABR) 連接多區域,核心區域 (Area 0) 負責區域間路由傳遞。減少路由信息交換量,限制故障範圍。
- LSDB:包含本區域所有路由器 LSA(Type 1 Router LSA、Type 2 Network LSA、Type 3/4 Summary LSA、Type 5/7 External LSA)。
- OSPF 主幹:Area 0,由 ABR、跨區域鏈路組成,負責區域間路由傳遞。ASBR 引入外部路由。
- 指定路由器 (DR) / 備用 DR (BDR):多路訪問網絡(以太網)中選舉,減少鄰接關係數量(N 個路由器僅建立 N-1 個鄰接),DR 代表網段發送 Network LSA。
三、OSPF 5 類報文類型
| 類型 | 名稱 | 功能 |
| 1 | Hello | 發現/維持鄰居可達性,協商參數,選舉 DR/BDR |
| 2 | Database Description (DD) | 交換 LSDB 摘要(LSA 首部),決定需請求哪些完整 LSA |
| 3 | Link State Request (LSR) | 請求特定 LSA 詳細信息 |
| 4 | Link State Update (LSU) | 泛洪發送完整 LSA 更新拓撲 |
| 5 | Link State Acknowledgment (LSAck) | 確認收到 LSU,確保可靠泛洪 |
四、LSDB 建立與更新流程
- 鄰居發現:Hello 間隔 10s,Dead 間隔 40s(4 倍)。雙向通信確認建立鄰居。
- 數據庫同步:ExStart → Exchange(交換 DD) → Loading(發送 LSR 請求缺失 LSA,接收 LSU) → Full 狀態,LSDB 同步完成。
- 拓撲變化泛洪:LSA 變更 → 產生新 LSA(序號+1) → LSU 泛洪全區域/全網 → 接收端檢查序號/校驗和 → 新則安裝並轉發,舊則丟棄並回 LSAck。
- 定期刷新:每 30 分鐘(1800s)刷新 LSA(序號+1),防止老化失效(MaxAge 3600s)。
五、圖論模型:最短路徑樹 (SPT)
節點 = 路由器 或 網絡(Stub 網絡/轉播網絡)。邊 = 物理連接,帶權值。OSPF 以路由器為根構建 SPT,路徑成本 = 累加接口 Cost(參考帶寬 100Mbps/接口帶寬)。轉發遵循最小成本路徑原則。
六、Hello 協議有限狀態機 (FSM)
多路訪問網絡必須:1) 無硬件故障檢測,需協議層保活;2) 防止全互聯產生 N(N-1)/2 鄰接。FSM 狀態流轉:
Down → Init(收到 Hello) → 2-Way(雙向通信,非 DR/BDR 止步於此)
→ ExStart(雙向+主從協商,成為鄰接) → Exchange → Loading → Full
DR/BDR 與所有路由器建立 Full 鄰接,其他路由器僅與 DR/BDR 建立 Full,相互間停留 2-Way,大幅減少鄰接開銷。