ISIS路由協議中路由計算研究

摘 要：路由算法在路由器中至關重要，好的路由算法能夠提高路由器性能。分析了目前常用的幾種ISIS路由算法，SPF、ISPF和PRC以及工業界采用的簡化SPF算法。在此基礎上提出一種改進方案是半拓撲SPF算法，在較穩定的網絡中使得路由計算速度大大提高。

關鍵詞：ISIS； SPF； ISPF； PRC； 簡化SPF； 半拓撲SPF

中圖分類號：

TN915-34

文獻標識碼：A

文章編號：1004-373X(2011)19

-0094

-03

Routing Algorithm Analysis of ISIS Protocol

LI Jun-jie

(Beijing Jiaotong University， Beijing 100044， China)

Abstract： Routing algorithm is very important in the router， which can improve router′s performance. Several common ISIS routing algorithms such as SPF， ISPF， PRC and a simplified SPF algorithm used in the industry are analyzed. A semi-topological SPF is proposed， which improves route calculation speed greatly in the stable network.

Keywords： ISIS; SPF; ISPF; PRC; simplified SPF; semi-topological SPF

收稿日期：2011-04-18

OSPF協議過于復雜大大限制了支持的路由器的數量和路由的條數，ISIS路由協議相對于OSPF來說實現簡單，所以越來越多的企業采用ISIS協議作為網絡中的IGP協議［1］，如何更高效的實現ISIS協議是當前研究的熱點。路由計算是協議的核心部分，因此加快路由計算來加快路由收斂越來越受到重視，很多學者研究改進路由算法來加快路由計算。本文分析了幾種工業中應用的路由算法和它們的不足，在此基礎上提出一種半拓撲SPF算法。

1 常見的路由計算方案分析

1.1 SPF算法

SPF最短路徑優先算法，采用Dijkstra算法，在鏈路狀態路由協議中用來計算到網絡的最短路徑［2］。每臺路由器都是以自己為根節點，其他路由器為葉子節點，根據網絡拓撲信息生成一棵最短路徑樹SPT，然后計算出根節點到各個目的地的最短路徑，但 SPF并不保存這棵最短路徑樹，當鏈路狀態發生變化時，不論是否影響網絡的拓撲結構，SPF 只能再次全部重新計算一遍這棵最短路徑樹［3］。網絡規模擴大的時候，鏈路狀態變化頻率增加，SPF計算頻度增加，同時鏈路狀態數據庫隨之增大，每次SPF的計算時間也會很長，基于以上不足，工業界提出了ISPF算法和PRC結合的改進方案。

1.2 ISPF算法和PRC算法結合

1.2.1 ISPF算法介紹

ISPF(Incremental SPF)是指增量路由計算，它每次只對變化的一部分路由進行計算，而不是對全部路由重新計算［4］。ISPF改進了SPF算法，第一次計算時需要計算全部節點，之后只是計算受影響的節點，大大降低了CPU的占用率，提高了網絡收斂速度。ISPF算法實現的關鍵點是如何選取要計算的最小范圍和如何在選定的范圍內重新計算，同時要求：每次計算完成后保存SPT，記錄SPT上每個節點的路徑；建立節點同路由之間的對應關系，每次只更新變化節點的路由信息。

鏈路狀態變化對路由計算的影響：

(1) cost增加，處于刪除狀態的link看作是cost從有效值增加到無窮大。若link不是SPT上的有效路徑，cost增加后不影響SPT樹結構，不需重新計算；若link在SPT上，cost增加需要重新計算。

(2) cost減少，新增link可看作是cost從無窮減少到有效值。cost減少時無論link在不在SPT上都需要重新計算，因為此時可能影響其他路由器的路徑。

(3) 若僅僅是link的下一跳(鄰居路由器)變化或者協議類型變化(由ISIS變為OSPF)，cost不變，則不需重新計算，只需更新相關節點的下一跳。

(4) SPT上節點狀態變化對link的影響。節點處于刪除狀態，則與該節點相連的所有link都標記為刪除狀態，需要重新計算；節點處于過載狀態，則所有到達該節點的link都標記為受影響狀態，需要重新計算；節點從過載狀態恢復正常或者是新增節點，則SPT上節點到該節點的link都標記為受影響狀態，需要重新計算。

ISPF第一次計算時要計算全部節點，之后只計算變化的部分，每次計算完成后要記錄整個拓撲關系，保存生成的最短路徑樹SPT，ISPF能夠形成一個直接反映網絡拓撲的“圖”狀數據庫，而計算出的SPT則保存在這個“圖”中［5］。當鏈路狀態發生變化時，根據上述原則判斷是否需重構SPT樹，若需要則按一定原則得到拓撲變化影響到的節點，然后在受影響的節點范圍內做SPF計算即ISPF，其他未受到影響的節點拓撲關系保持不變。根據增量計算結果更新SPT樹，并將受到影響節點的路由進行更新，即PRC部分路由計算。

1.2.2 PRC部分路由計算

PRC是部分路由計算，它與ISPF配合使用。PRC的原理也是只計算變化的那一部分，但PRC不需要計算節點路徑，而是根據ISPF算出來的SPT來更新路由［6］。如果ISPF計算后的SPT改變，PRC處理所有變化的節點上的所有路由；如果經過ISPF計算后的SPT并沒有變化，只有葉子節點變化，則PRC只處理變化的葉子節點的路由信息。

PRC計算是為了處理變化的ISIS路由，而ISIS路由的變化由葉子節點變化引起。系統節點的變化必然引起系統節點上葉子節點的變化，因此在PRC計算時要先處理變化的系統節點，然后處理變化的葉子節點。PRC算法實現時先提交變化節點，將節點下的路由放入路由變化表中，然后遍歷路由變化列表，將變化的路由下刷到路由管理的IP路由表。

1.2.3 ISPF算法的不足

網絡拓撲變化的位置不同，受到影響的范圍就不同，ISPF計算所消耗的時間就不同。最壞情況是整個拓撲受到影響，ISPF相當于進行了全部重新計算。ISPF算法進行路由計算的時間包括搜尋受影響節點的計算時間，增量路由計算的時間和PRC計算的時間。一般情況下搜尋受影響節點的計算和增量路由計算的時間總和會比計算全部拓撲的時間少，因此ISPF在大多數情況下能夠減少計算開銷、增加收斂速度。但ISPF算法實現流程過于復雜，在某種網絡中的計算效率比SPF還要差［7］，例如某一鏈路的變化引起整個拓撲結構的變化，則增量路由計算的時間其實是整個拓撲計算的時間，使用ISPF算法還增加了搜尋時間，此時ISPF算法反而會比傳統的SPF算法開銷更大，因此工業界又提出了簡化SPF算法。

1.3 簡化SPF算法

簡化SPF算法是先判斷鏈路的變化是否需要重構SPT樹，如果不影響SPT結構，采用PRC進行路由信息更新；如果影響到SPT，則所有節點直接進行全部的SPF計算重構SPT。簡化SPF算法需要記錄整個網絡的拓撲關系，保存每次SPF計算生成的SPT樹。此時PRC用來處理網絡拓撲不變而路由信息發生改變的情況，這樣就是根據網絡變化的不同情況做出最精簡的處理，使得路由計算處理工作量降到最低，從而大大節約路由計算所用時間［8］。

上面已經介紹了各種鏈路變化以及是否需要重構SPT，有些鏈路的變化是不需要重構SPT的。簡化SPF算法與ISPF計算時間相比，判定鏈路變化是否需要重新計算拓撲的時間復雜度比確定受影響的節點范圍的時間復雜度小得多，雖然計算全部拓撲的時間大于增量拓撲計算的時間，但對于節點變化影響大部分網絡拓撲時，簡化SPF算法能夠減少很多無效計算。但有時變化的節點靠近葉子節點，受影響的節點范圍很小，全部節點進行SPF計算又增加了路由計算時間，沒有充分利用原來的SPT［9］，因此本文提出了半拓撲SPF算法。

2 半拓撲SPF算法

半拓撲SPF算法是先判斷鏈路的變化是否影響網絡的拓撲結構，是否需要重構SPT樹，如果不影響SPT結構，直接采用PRC更新路由信息；如果影響到SPT，則判斷變化的鏈路指向的節點在網絡中的拓撲層次，若在上層則全部節點進行SPF計算，若在下層則采用ISPF找出受影響的節點進行變化部分的增量路由計算，重構SPT后采用PRC算法更新路由。半拓撲SPF算法需要記錄整個網絡的拓撲關系，同時要保存每次SPF計算生成的SPT樹，還要保存每個路由器所在的網絡層次。

簡單網絡的SPT結構圖如圖1所示。第一次路由計算時對全部節點進行SPF計算，構造SPT時同時標記每個路由器所在的網絡層次，因為存在等價路由，所以節點所屬層次按最小的層次算，如圖1中第二層左面的節點，它同時也在第三層，這時就按第二層來算。當變化的鏈路影響拓撲結構時，找出這條鏈路的目的節點，若該節點所在的層次小于全網層次的50%，則認為是上層網絡受到影響，否則就是下層網絡受到影響，如上面的SPT結構圖共有6層，若1層和2層節點受影響，則全部節點進行SPF計算重構SPT，其他層節點受影響時，則采用ISPF算法尋找受影響的節點進行增量路由計算。若是新增節點則找出所有和該節點建立鄰居的節點的最小層次，判斷該最小層次的下一層在網絡中的層次，因為該新增節點的源節點路由不變不需重新計算；若是SPT上節點發生變化則判斷該節點所在的層次，然后依據該層次進行判斷采用哪種算法。

圖1 最短路徑樹SPT

半拓撲SPF算法進行路由計算的時間包括判定變化的鏈路是否需要重新進行拓撲計算的時間，判定采用哪種路由算法的時間，拓撲計算的時間和PRC計算的時間。當受影響的節點在網絡上半層時，半拓撲SPF算法比簡化SPF算法多了判斷采用那種路由算法的時間，但該時間極短，與ISPF算法相比少了尋找受影響節點的時間，雖然全部節點進行SPF計算時間比部分路由計算多，但總體上還是優于ISPF算法；當受影響的節點在網絡的下半層時，半拓撲SPF算法相對于ISPF算法多了判斷采用那種路由算法的時間，相對于簡化SPF，找出受影響的節點再進行增量路由計算的時間小于全部節點進行SPF計算的時間。從總體上看半拓撲SPF算法是以犧牲較小的內存空間換取了路由計算速度的提高。

3 結 語

本文主要分析了幾種路由算法，SPF是比較傳統的算法，但現在的網絡拓撲復雜而且變化頻繁，導致路由量巨大，路由計算速度慢，于是工業界采用增量計算ISPF和PRC算法來加快路由計算，但當拓撲變化發生在拓撲結構的上層時，ISPF比SPF計算更復雜，由此工業界提出了簡化SPF，但當拓撲變化發生在拓撲結構的下層時又增加了計算時間，因此本文提出半拓撲SPF算法，從總體上看此算法最優。節點總數不變時減少網絡層次，增加每臺路由器的鄰接路由器數量可以改善網絡結構［10］。改進的路由算法結合優化的網絡結構能進一步提高路由計算的速度。

參 考 文 獻

［1］別碧勇.ISIS路由協議及其在IP網絡工程設計中的應用［J］.鐵道勘測與設計，2006(1)：47-53.

［2］華為技術有限公司.DA000009 IS-IS路由協議ISSUE 3.0［M］.深圳:華為技術有限公司，2007.

［3］何濤.ISIS協議在IP網絡中的設計與應用［D］.北京：北京郵電大學，2007.

［4］Stim.ISIS的幾種快速收斂特性［EB/OL］.［2007-10-31］.http://www.net130.com，2007.

［5］華為技術有限公司.IGP快速收斂技術白皮書［M］.深圳:華為技術有限公司，2007.

［6］任榮錦.IP網絡中IGP路由快速收斂的探討與實現［D］.廣州：華南理工大學，2006.

［7］李園花，李健，趙凱.基于鏈路狀態路由快速收斂技術的研究［J］.網絡安全技術與應用，2009(3)：9-11.

［8］佚名.IS-IS快速收斂技術白皮書［M］.杭州:杭州華三通信技術有限公司，2007.

［9］高占春，柴廣宏.ATN路由器中路由算法IS-IS的研究與改進［J］.數據通信，2005(3)：35-38.

［10］鄧永平，徐建峰.IGP路由收斂分析及優化［J］.電信科學，2005(4)：13-15.