摘 要：路由算法在路由器中至關(guān)重要，好的路由算法能夠提高路由器性能。分析了目前常用的幾種ISIS路由算法，SPF、ISPF和PRC以及工業(yè)界采用的簡(jiǎn)化SPF算法。在此基礎(chǔ)上提出一種改進(jìn)方案是半拓?fù)銼PF算法，在較穩(wěn)定的網(wǎng)絡(luò)中使得路由計(jì)算速度大大提高。

關(guān)鍵詞：ISIS； SPF； ISPF； PRC； 簡(jiǎn)化SPF； 半拓?fù)銼PF

中圖分類號(hào)：

TN915-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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協(xié)議過(guò)于復(fù)雜大大限制了支持的路由器的數(shù)量和路由的條數(shù)，ISIS路由協(xié)議相對(duì)于OSPF來(lái)說(shuō)實(shí)現(xiàn)簡(jiǎn)單，所以越來(lái)越多的企業(yè)采用ISIS協(xié)議作為網(wǎng)絡(luò)中的IGP協(xié)議［1］，如何更高效的實(shí)現(xiàn)ISIS協(xié)議是當(dāng)前研究的熱點(diǎn)。路由計(jì)算是協(xié)議的核心部分，因此加快路由計(jì)算來(lái)加快路由收斂越來(lái)越受到重視，很多學(xué)者研究改進(jìn)路由算法來(lái)加快路由計(jì)算。本文分析了幾種工業(yè)中應(yīng)用的路由算法和它們的不足，在此基礎(chǔ)上提出一種半拓?fù)銼PF算法。

1 常見(jiàn)的路由計(jì)算方案分析

1.1 SPF算法

SPF最短路徑優(yōu)先算法，采用Dijkstra算法，在鏈路狀態(tài)路由協(xié)議中用來(lái)計(jì)算到網(wǎng)絡(luò)的最短路徑［2］。每臺(tái)路由器都是以自己為根節(jié)點(diǎn)，其他路由器為葉子節(jié)點(diǎn)，根據(jù)網(wǎng)絡(luò)拓?fù)湫畔⑸梢豢米疃搪窂綐?shù)SPT，然后計(jì)算出根節(jié)點(diǎn)到各個(gè)目的地的最短路徑，但 SPF并不保存這棵最短路徑樹(shù)，當(dāng)鏈路狀態(tài)發(fā)生變化時(shí)，不論是否影響網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，SPF 只能再次全部重新計(jì)算一遍這棵最短路徑樹(shù)［3］。網(wǎng)絡(luò)規(guī)模擴(kuò)大的時(shí)候，鏈路狀態(tài)變化頻率增加，SPF計(jì)算頻度增加，同時(shí)鏈路狀態(tài)數(shù)據(jù)庫(kù)隨之增大，每次SPF的計(jì)算時(shí)間也會(huì)很長(zhǎng)，基于以上不足，工業(yè)界提出了ISPF算法和PRC結(jié)合的改進(jìn)方案。

1.2 ISPF算法和PRC算法結(jié)合

1.2.1 ISPF算法介紹

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

鏈路狀態(tài)變化對(duì)路由計(jì)算的影響：

(1) cost增加，處于刪除狀態(tài)的link看作是cost從有效值增加到無(wú)窮大。若link不是SPT上的有效路徑，cost增加后不影響SPT樹(shù)結(jié)構(gòu)，不需重新計(jì)算；若link在SPT上，cost增加需要重新計(jì)算。

(2) cost減少，新增link可看作是cost從無(wú)窮減少到有效值。cost減少時(shí)無(wú)論link在不在SPT上都需要重新計(jì)算，因?yàn)榇藭r(shí)可能影響其他路由器的路徑。

(3) 若僅僅是link的下一跳(鄰居路由器)變化或者協(xié)議類型變化(由ISIS變?yōu)镺SPF)，cost不變，則不需重新計(jì)算，只需更新相關(guān)節(jié)點(diǎn)的下一跳。

(4) SPT上節(jié)點(diǎn)狀態(tài)變化對(duì)link的影響。節(jié)點(diǎn)處于刪除狀態(tài)，則與該節(jié)點(diǎn)相連的所有l(wèi)ink都標(biāo)記為刪除狀態(tài)，需要重新計(jì)算；節(jié)點(diǎn)處于過(guò)載狀態(tài)，則所有到達(dá)該節(jié)點(diǎn)的link都標(biāo)記為受影響狀態(tài)，需要重新計(jì)算；節(jié)點(diǎn)從過(guò)載狀態(tài)恢復(fù)正?；蛘呤切略龉?jié)點(diǎn)，則SPT上節(jié)點(diǎn)到該節(jié)點(diǎn)的link都標(biāo)記為受影響狀態(tài)，需要重新計(jì)算。

ISPF第一次計(jì)算時(shí)要計(jì)算全部節(jié)點(diǎn)，之后只計(jì)算變化的部分，每次計(jì)算完成后要記錄整個(gè)拓?fù)潢P(guān)系，保存生成的最短路徑樹(shù)SPT，ISPF能夠形成一個(gè)直接反映網(wǎng)絡(luò)拓?fù)涞摹皥D”狀數(shù)據(jù)庫(kù)，而計(jì)算出的SPT則保存在這個(gè)“圖”中［5］。當(dāng)鏈路狀態(tài)發(fā)生變化時(shí)，根據(jù)上述原則判斷是否需重構(gòu)SPT樹(shù)，若需要?jiǎng)t按一定原則得到拓?fù)渥兓绊懙降墓?jié)點(diǎn)，然后在受影響的節(jié)點(diǎn)范圍內(nèi)做SPF計(jì)算即ISPF，其他未受到影響的節(jié)點(diǎn)拓?fù)潢P(guān)系保持不變。根據(jù)增量計(jì)算結(jié)果更新SPT樹(shù)，并將受到影響節(jié)點(diǎn)的路由進(jìn)行更新，即PRC部分路由計(jì)算。

1.2.2 PRC部分路由計(jì)算

PRC是部分路由計(jì)算，它與ISPF配合使用。PRC的原理也是只計(jì)算變化的那一部分，但PRC不需要計(jì)算節(jié)點(diǎn)路徑，而是根據(jù)ISPF算出來(lái)的SPT來(lái)更新路由［6］。如果ISPF計(jì)算后的SPT改變，PRC處理所有變化的節(jié)點(diǎn)上的所有路由；如果經(jīng)過(guò)ISPF計(jì)算后的SPT并沒(méi)有變化，只有葉子節(jié)點(diǎn)變化，則PRC只處理變化的葉子節(jié)點(diǎn)的路由信息。

PRC計(jì)算是為了處理變化的ISIS路由，而ISIS路由的變化由葉子節(jié)點(diǎn)變化引起。系統(tǒng)節(jié)點(diǎn)的變化必然引起系統(tǒng)節(jié)點(diǎn)上葉子節(jié)點(diǎn)的變化，因此在PRC計(jì)算時(shí)要先處理變化的系統(tǒng)節(jié)點(diǎn)，然后處理變化的葉子節(jié)點(diǎn)。PRC算法實(shí)現(xiàn)時(shí)先提交變化節(jié)點(diǎn)，將節(jié)點(diǎn)下的路由放入路由變化表中，然后遍歷路由變化列表，將變化的路由下刷到路由管理的IP路由表。

1.2.3 ISPF算法的不足

網(wǎng)絡(luò)拓?fù)渥兓奈恢貌煌艿接绊懙姆秶筒煌?，ISPF計(jì)算所消耗的時(shí)間就不同。最壞情況是整個(gè)拓?fù)涫艿接绊?，ISPF相當(dāng)于進(jìn)行了全部重新計(jì)算。ISPF算法進(jìn)行路由計(jì)算的時(shí)間包括搜尋受影響節(jié)點(diǎn)的計(jì)算時(shí)間，增量路由計(jì)算的時(shí)間和PRC計(jì)算的時(shí)間。一般情況下搜尋受影響節(jié)點(diǎn)的計(jì)算和增量路由計(jì)算的時(shí)間總和會(huì)比計(jì)算全部拓?fù)涞臅r(shí)間少，因此ISPF在大多數(shù)情況下能夠減少計(jì)算開(kāi)銷、增加收斂速度。但I(xiàn)SPF算法實(shí)現(xiàn)流程過(guò)于復(fù)雜，在某種網(wǎng)絡(luò)中的計(jì)算效率比SPF還要差［7］，例如某一鏈路的變化引起整個(gè)拓?fù)浣Y(jié)構(gòu)的變化，則增量路由計(jì)算的時(shí)間其實(shí)是整個(gè)拓?fù)溆?jì)算的時(shí)間，使用ISPF算法還增加了搜尋時(shí)間，此時(shí)ISPF算法反而會(huì)比傳統(tǒng)的SPF算法開(kāi)銷更大，因此工業(yè)界又提出了簡(jiǎn)化SPF算法。

1.3 簡(jiǎn)化SPF算法

簡(jiǎn)化SPF算法是先判斷鏈路的變化是否需要重構(gòu)SPT樹(shù)，如果不影響SPT結(jié)構(gòu)，采用PRC進(jìn)行路由信息更新；如果影響到SPT，則所有節(jié)點(diǎn)直接進(jìn)行全部的SPF計(jì)算重構(gòu)SPT。簡(jiǎn)化SPF算法需要記錄整個(gè)網(wǎng)絡(luò)的拓?fù)潢P(guān)系，保存每次SPF計(jì)算生成的SPT樹(shù)。此時(shí)PRC用來(lái)處理網(wǎng)絡(luò)拓?fù)洳蛔兌酚尚畔l(fā)生改變的情況，這樣就是根據(jù)網(wǎng)絡(luò)變化的不同情況做出最精簡(jiǎn)的處理，使得路由計(jì)算處理工作量降到最低，從而大大節(jié)約路由計(jì)算所用時(shí)間［8］。

上面已經(jīng)介紹了各種鏈路變化以及是否需要重構(gòu)SPT，有些鏈路的變化是不需要重構(gòu)SPT的。簡(jiǎn)化SPF算法與ISPF計(jì)算時(shí)間相比，判定鏈路變化是否需要重新計(jì)算拓?fù)涞臅r(shí)間復(fù)雜度比確定受影響的節(jié)點(diǎn)范圍的時(shí)間復(fù)雜度小得多，雖然計(jì)算全部拓?fù)涞臅r(shí)間大于增量拓?fù)溆?jì)算的時(shí)間，但對(duì)于節(jié)點(diǎn)變化影響大部分網(wǎng)絡(luò)拓?fù)鋾r(shí)，簡(jiǎn)化SPF算法能夠減少很多無(wú)效計(jì)算。但有時(shí)變化的節(jié)點(diǎn)靠近葉子節(jié)點(diǎn)，受影響的節(jié)點(diǎn)范圍很小，全部節(jié)點(diǎn)進(jìn)行SPF計(jì)算又增加了路由計(jì)算時(shí)間，沒(méi)有充分利用原來(lái)的SPT［9］，因此本文提出了半拓?fù)銼PF算法。

2 半拓?fù)銼PF算法

半拓?fù)銼PF算法是先判斷鏈路的變化是否影響網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，是否需要重構(gòu)SPT樹(shù)，如果不影響SPT結(jié)構(gòu)，直接采用PRC更新路由信息；如果影響到SPT，則判斷變化的鏈路指向的節(jié)點(diǎn)在網(wǎng)絡(luò)中的拓?fù)鋵哟?，若在上層則全部節(jié)點(diǎn)進(jìn)行SPF計(jì)算，若在下層則采用ISPF找出受影響的節(jié)點(diǎn)進(jìn)行變化部分的增量路由計(jì)算，重構(gòu)SPT后采用PRC算法更新路由。半拓?fù)銼PF算法需要記錄整個(gè)網(wǎng)絡(luò)的拓?fù)潢P(guān)系，同時(shí)要保存每次SPF計(jì)算生成的SPT樹(shù)，還要保存每個(gè)路由器所在的網(wǎng)絡(luò)層次。

簡(jiǎn)單網(wǎng)絡(luò)的SPT結(jié)構(gòu)圖如圖1所示。第一次路由計(jì)算時(shí)對(duì)全部節(jié)點(diǎn)進(jìn)行SPF計(jì)算，構(gòu)造SPT時(shí)同時(shí)標(biāo)記每個(gè)路由器所在的網(wǎng)絡(luò)層次，因?yàn)榇嬖诘葍r(jià)路由，所以節(jié)點(diǎn)所屬層次按最小的層次算，如圖1中第二層左面的節(jié)點(diǎn)，它同時(shí)也在第三層，這時(shí)就按第二層來(lái)算。當(dāng)變化的鏈路影響拓?fù)浣Y(jié)構(gòu)時(shí)，找出這條鏈路的目的節(jié)點(diǎn)，若該節(jié)點(diǎn)所在的層次小于全網(wǎng)層次的50%，則認(rèn)為是上層網(wǎng)絡(luò)受到影響，否則就是下層網(wǎng)絡(luò)受到影響，如上面的SPT結(jié)構(gòu)圖共有6層，若1層和2層節(jié)點(diǎn)受影響，則全部節(jié)點(diǎn)進(jìn)行SPF計(jì)算重構(gòu)SPT，其他層節(jié)點(diǎn)受影響時(shí)，則采用ISPF算法尋找受影響的節(jié)點(diǎn)進(jìn)行增量路由計(jì)算。若是新增節(jié)點(diǎn)則找出所有和該節(jié)點(diǎn)建立鄰居的節(jié)點(diǎn)的最小層次，判斷該最小層次的下一層在網(wǎng)絡(luò)中的層次，因?yàn)樵撔略龉?jié)點(diǎn)的源節(jié)點(diǎn)路由不變不需重新計(jì)算；若是SPT上節(jié)點(diǎn)發(fā)生變化則判斷該節(jié)點(diǎn)所在的層次，然后依據(jù)該層次進(jìn)行判斷采用哪種算法。

圖1 最短路徑樹(shù)SPT

半拓?fù)銼PF算法進(jìn)行路由計(jì)算的時(shí)間包括判定變化的鏈路是否需要重新進(jìn)行拓?fù)溆?jì)算的時(shí)間，判定采用哪種路由算法的時(shí)間，拓?fù)溆?jì)算的時(shí)間和PRC計(jì)算的時(shí)間。當(dāng)受影響的節(jié)點(diǎn)在網(wǎng)絡(luò)上半層時(shí)，半拓?fù)銼PF算法比簡(jiǎn)化SPF算法多了判斷采用那種路由算法的時(shí)間，但該時(shí)間極短，與ISPF算法相比少了尋找受影響節(jié)點(diǎn)的時(shí)間，雖然全部節(jié)點(diǎn)進(jìn)行SPF計(jì)算時(shí)間比部分路由計(jì)算多，但總體上還是優(yōu)于ISPF算法；當(dāng)受影響的節(jié)點(diǎn)在網(wǎng)絡(luò)的下半層時(shí)，半拓?fù)銼PF算法相對(duì)于ISPF算法多了判斷采用那種路由算法的時(shí)間，相對(duì)于簡(jiǎn)化SPF，找出受影響的節(jié)點(diǎn)再進(jìn)行增量路由計(jì)算的時(shí)間小于全部節(jié)點(diǎn)進(jìn)行SPF計(jì)算的時(shí)間。從總體上看半拓?fù)銼PF算法是以犧牲較小的內(nèi)存空間換取了路由計(jì)算速度的提高。

3 結(jié) 語(yǔ)

本文主要分析了幾種路由算法，SPF是比較傳統(tǒng)的算法，但現(xiàn)在的網(wǎng)絡(luò)拓?fù)鋸?fù)雜而且變化頻繁，導(dǎo)致路由量巨大，路由計(jì)算速度慢，于是工業(yè)界采用增量計(jì)算ISPF和PRC算法來(lái)加快路由計(jì)算，但當(dāng)拓?fù)渥兓l(fā)生在拓?fù)浣Y(jié)構(gòu)的上層時(shí)，ISPF比SPF計(jì)算更復(fù)雜，由此工業(yè)界提出了簡(jiǎn)化SPF，但當(dāng)拓?fù)渥兓l(fā)生在拓?fù)浣Y(jié)構(gòu)的下層時(shí)又增加了計(jì)算時(shí)間，因此本文提出半拓?fù)銼PF算法，從總體上看此算法最優(yōu)。節(jié)點(diǎn)總數(shù)不變時(shí)減少網(wǎng)絡(luò)層次，增加每臺(tái)路由器的鄰接路由器數(shù)量可以改善網(wǎng)絡(luò)結(jié)構(gòu)［10］。改進(jìn)的路由算法結(jié)合優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu)能進(jìn)一步提高路由計(jì)算的速度。

參 考 文 獻(xiàn)

［1］別碧勇.ISIS路由協(xié)議及其在IP網(wǎng)絡(luò)工程設(shè)計(jì)中的應(yīng)用［J］.鐵道勘測(cè)與設(shè)計(jì)，2006(1)：47-53.

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

［3］何濤.ISIS協(xié)議在IP網(wǎng)絡(luò)中的設(shè)計(jì)與應(yīng)用［D］.北京：北京郵電大學(xué)，2007.

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

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

［6］任榮錦.IP網(wǎng)絡(luò)中IGP路由快速收斂的探討與實(shí)現(xiàn)［D］.廣州：華南理工大學(xué)，2006.

［7］李園花，李健，趙凱.基于鏈路狀態(tài)路由快速收斂技術(shù)的研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2009(3)：9-11.

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

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

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