單元 10 路由演算法與跨網域政策

學習目標與問題

以單元 03 查表為基礎，區分轉送與路由控制，演練 Dijkstra 及距離向量，理解 OSPF 和 BGP 解決不同問題。最短路徑不一定是組織願意使用的路徑。

10.1 資料平面與控制平面

轉送為每個封包查表選出口；路由控制交換拓樸或可達資訊，產生可供轉送的路由。靜態路由由人設定，動態路由可對變動重新計算，仍要等待偵測與收斂。封包到達的當下，裝置使用的是當時有效的表，不是全網瞬間的完美檢視。

10.2 鏈路狀態與 Dijkstra

鏈路狀態模型讓節點取得拓樸及成本，再算到各目的地最短路徑。A-B=2、A-C=5、B-C=1、B-D=4、C-D=1，假設無向、成本非負且同步一致。

演算法可用下列虛擬碼重現；本例假設非負邊權：

dist[A] = 0; 其他 dist = 無限; 未確定 = 所有節點
while 未確定不為空:
    u = 未確定中 dist 最小者
    若 dist[u] 為無限: 結束（剩餘節點不可達）
    從未確定移除 u
    for u 的每個仍未確定鄰居 v:
        若 dist[u] + cost(u,v) < dist[v]:
            dist[v] = dist[u] + cost(u,v); prev[v] = u

到 D 路徑 A-B-C-D 成本 4。若成本相同，可有多個正確最短路徑；實作的 tie-breaking 或 ECMP 影響結果。OSPF 使用鏈路狀態思想，實際包含 area、鄰接、泛洪與不同 LSA，不能把小圖當完整 OSPF 封包流程。

10.3 距離向量

距離向量以鄰居通告的距離更新：D_x(y)=min_v[c(x,v)+D_v(y)]。節點不必知道完整拓樸，但資訊可能過時。鏈路失效時兩個鄰居可能互相相信對方有路，逐步增加成本，形成 count-to-infinity。split horizon、poison reverse 等可減少部分問題，不能宣稱消除所有任意拓樸的暫態迴路。

例：原 B 可直接到 D，C 經 B。B-D 斷時，假設未啟用 poison reverse，若 C 還公告舊路徑，B 可能改經 C，而 C 仍經 B。需要觀察訊息順序、失效通告和收斂，不只最終表。

10.4 BGP 與政策

自治系統 AS 是路由政策管理邊界。BGP 交換前綴可達資訊與屬性；AS_PATH 協助表達經過的 AS 及迴路避免，選路還受 LOCAL_PREF 等政策影響。更短 AS_PATH 不保證先於本地政策，也不等於物理距離短或延遲低。

企業可能優先付費較低的鏈路，或禁止把某兩個上游之間的流量當免費 transit。可達性宣告與資料封包實際轉送都是需要驗證的狀態。RPKI origin validation 可檢查起源 AS 與前綴授權，不能驗證整條 AS 路徑或保證沒有劫持。

實驗、習題與檢核

L07 重算成本變動，列出同成本路徑。延伸畫三節點距離向量失效時序。

1. 手算上表 A 到各節點最短路徑。
2. B-C 成本改 10，A 到 D 有哪些最短路徑？
3. 路由協定收斂前為何可能有黑洞或暫態迴路？
4. 為何 BGP 不能只使用 Dijkstra 的最短距離決定路由？

檢核：能區分前綴匹配、路徑成本、政策優先和實際量測。來源：RFC 2328（OSPFv2）、RFC 2453（RIP）、RFC 4271（BGP）、RFC 6811（Origin Validation）。