《IS-IS網絡設計解決方案》一6.2 使用SPF算法計算IS-IS路由

本節書摘來自異步社群《is-is網絡設計解決方案》一書中的第6章，第6.2節，作者【美】abe martey，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視

is-is網絡設計解決方案

iso 10589附錄c2定義了使用spf算法進行is-is協定的路由計算。rfc 1195附錄c定義了spf算法的修改版本進而使is-is協定支援ip路由選擇。dijkstra算法産生網絡拓撲的最短路徑樹，進而确定去往不同目标的最短（最優）路徑并放入ip路由表。為了獲得ip路由的最佳路徑，ip子網會被看作是最短路徑樹的樹葉。網絡事件隻會導緻鍊路狀态資料包中ip可達性條目的改變，而不要求重新計算整個最短路徑樹。在這種狀況下，is-is協定隻需進行部分路由計算（partial route calculation，prc）而不是完整地運作spf算法。在大多數情況下，is-is路由計算中無處不在的prc優化了ip路由選擇收斂的執行效率。

前文曾提到spf算法的計算時間的階數o(llogn)，其中l為鍊路數量，n為節點數量。logn因子是由dijkstra算法操作的步驟2（見圖6-2）産生的。t集合中的元素會預先按照開銷進行排序進而避免在選擇最低開銷元素時進行線性搜尋。在排序的t集合中使用二進制搜尋機制并插入新條目所需的處理時間引入了logn因子。通過使用一個基于6位字段的有限路徑開銷（iso 10589中定義），可以将複雜性階數優化并降低為o(n)，進而消除了logn。這是通過使用快速的陣列排序資料結構，将節點按照路徑開銷而不是邏輯距離進行散列排序實作的。不幸的是，随着時間推移，在is-is網絡設計及其他is-is路由選擇應用（例如mpls流量工程）中，6位的度量字段已經不足以提供足夠的靈活性。在is-is中采用更大路徑開銷（寬度量）很明顯地要比小而有限的路徑開銷（窄度量）具有網路優化方面的優勢（見第5章）。

rfc 1195對is-is路由選擇的spf算法進行了修改，允許在多條等價路徑上實作負載均衡。但在通常情況下，dijkstra算法仍按照前文所述的過程工作。在rfc 1195附錄c中對spf算法的操作進行了很好的描述。在建構最短路徑樹時會使用以下三種清單：未知或候選清單（unknown or candidate list，unk）、實驗清單（tentative，tent）和已知路徑清單（known paths，paths）。當spf開始運作時，所有的節點放入unk中。随後在初始化時将源節點移入paths。節點會根據其下一跳及度量資訊放入tent，進而進一步檢查其是否可以放入paths。is-is為所有鄰居維護一個鄰接資料庫，為spf的運作提供tent中直連鄰居的下一跳資訊。對于非直連的主機，從paths中經過其父節點獲得第一跳資訊。存放在tent和paths中的條目是由三元組組成的：{n, d(n), adj(n)}，其中：

n=系統id；

d(n)=從源s到n的距離；

adj(n)=源s已知的n有效鄰接的集合。

在算法的每一步都需要檢查tent清單，具有到源的最小開銷的節點将被移入paths。當節點被放入paths後，該節點所通告的ip字首及相應的度量和下一跳資訊将放入is-is路由選擇資訊庫（is-is routing information base，rib）。如果放入paths中的節點的直連鄰居不在tent中，則将其移入tent并對其開銷進行相應的調整，以進行下一次選擇。

請注意ip内部及外部字首包括位址和掩碼在内共占8位元組，這些字首永遠都是葉子。