基于鏈路狀態(tài)的路由協(xié)議仿真分析

曹雪峰

（承德民族師專 數(shù)學(xué)與計(jì)算機(jī)系，河北 承德 067000）

基于鏈路狀態(tài)的路由協(xié)議仿真分析

曹雪峰

（承德民族師專 數(shù)學(xué)與計(jì)算機(jī)系，河北 承德 067000）

本文介紹了基于鏈路狀態(tài)的路由選擇協(xié)議，并對(duì)OSPF和集成IS-IS協(xié)議進(jìn)行了比較分析。利用OPNET仿真軟件對(duì)兩種協(xié)議的收斂速度、路由開(kāi)銷以及負(fù)載平衡等進(jìn)行了仿真實(shí)驗(yàn)。結(jié)果表明分析結(jié)果是正確的，同時(shí)還說(shuō)明了集成IS-IS協(xié)議也可以象OSPF協(xié)議一樣用于骨干網(wǎng)絡(luò)，并且在有些方面還優(yōu)于OSPF協(xié)議。

鏈路狀態(tài)；路由協(xié)議；收斂速度；仿真

1 引言

鏈路狀態(tài)路由協(xié)議是目前使用最廣的自治系統(tǒng)內(nèi)部路由協(xié)議。它不同于距離矢量路由協(xié)議，如果把距離矢量路由選擇協(xié)議比作是由路標(biāo)提供的信息，那么鏈路狀態(tài)路由選擇協(xié)議就是一張交通路線圖，因?yàn)樗幸粡埻暾木W(wǎng)絡(luò)圖，所以它是不容易被欺騙而作出錯(cuò)誤的路由決策的。運(yùn)行基于鏈路狀態(tài)的路由選擇協(xié)議的每臺(tái)路由器，都會(huì)產(chǎn)生一些關(guān)于自己、本地直連鏈路以及這些鏈路的狀態(tài)和所有直接相連鄰居的信息。只將它所直連的鏈路狀態(tài)與鄰居共享，這個(gè)鄰居是指一個(gè)自治系統(tǒng)或一個(gè)區(qū)域內(nèi)的所有路由器。這些信息從一臺(tái)路由器傳送到另一臺(tái)路由器，每臺(tái)路由器都做一份信息拷貝，但是決不改動(dòng)這些信息，最終通過(guò)對(duì)這些鏈路狀態(tài)進(jìn)行拼裝，生成一個(gè)全網(wǎng)的拓?fù)鋱D，然后根據(jù)自己在該圖中所處的位置，運(yùn)行E.W.Dijkstra算法計(jì)算出到達(dá)各目標(biāo)網(wǎng)絡(luò)的最佳路徑，從而構(gòu)造出完整的路由表。

2 協(xié)議分析

2.1 協(xié)議工作過(guò)程

鏈路狀態(tài)路由選擇協(xié)議的目的是映射互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，構(gòu)造路由表。它的具體工作過(guò)程如下：

①每臺(tái)路由器與它的鄰居之間建立聯(lián)系，這種聯(lián)系稱為鄰接關(guān)系；

②每臺(tái)路由器向每個(gè)鄰居發(fā)送鏈路狀態(tài)通告（LSA）或者鏈路狀態(tài)數(shù)據(jù)包（LSP）。對(duì)每臺(tái)路由器鏈路都會(huì)生成一個(gè)LSA（LSP），用于標(biāo)識(shí)這條鏈路、鏈路狀態(tài)、路由器接口到鏈路的代價(jià)度量值以及鏈路所連接的所有鄰居。每個(gè)鄰居在收到通告后將依次向它的鄰居轉(zhuǎn)發(fā)(泛洪)這些通告，它的結(jié)果是向網(wǎng)絡(luò)發(fā)送第一手信息，為網(wǎng)絡(luò)建立更新路由的準(zhǔn)確映射。鏈路狀態(tài)路由選擇協(xié)議使用稱為代價(jià)的方法，而不是使用跳。代價(jià)是自動(dòng)或人工賦值的。根據(jù)鏈路狀態(tài)協(xié)議的算法，代價(jià)可以計(jì)算數(shù)據(jù)包必須穿越的跳數(shù)目、鏈路帶寬、鏈路上的當(dāng)前負(fù)載，或者甚至其他由管理員加入的權(quán)重來(lái)評(píng)價(jià)。

③每臺(tái)路由器要在數(shù)據(jù)庫(kù)中保存一份它所收到的LSA的備份，如果所有路由器工作正常，那么它們的鏈路狀態(tài)數(shù)據(jù)庫(kù)應(yīng)該相同；

④完整的拓?fù)鋽?shù)據(jù)庫(kù)，也叫做鏈路狀態(tài)數(shù)據(jù)庫(kù)，每臺(tái)路由器使用Dijkstra算法計(jì)算出到每個(gè)目的網(wǎng)絡(luò)的最短路徑，并把這些信息保存到路由表中。

鏈路狀態(tài)路由選擇協(xié)議的主要優(yōu)點(diǎn)是收斂速度非常快，原因是一旦路由選擇拓?fù)涑霈F(xiàn)變動(dòng)，則更新在互連網(wǎng)絡(luò)上迅速泛洪。這些優(yōu)點(diǎn)釋放了路由器的資源，因?yàn)閷?duì)不好的路由信息所花費(fèi)的處理能力和帶寬消耗都很少。但是維護(hù)路由器區(qū)域的鏈路狀態(tài)數(shù)據(jù)庫(kù)將在路由器上加重RAM負(fù)擔(dān)。同樣在每次網(wǎng)絡(luò)拓?fù)涓淖兊臅r(shí)候都要運(yùn)行Dijkstra算法，這在所有的路由器上加重了CPU的負(fù)擔(dān)。另外一個(gè)優(yōu)點(diǎn)是不會(huì)形成路由環(huán)路。鏈路狀態(tài)路由協(xié)議適合大型網(wǎng)絡(luò)，但由于它的復(fù)雜性，使得路由器需要更多的CPU資源。

2.2 IS-IS與OSPF協(xié)議的比較

IS-IS最初是ISO的標(biāo)準(zhǔn)協(xié)議，是為CLNS設(shè)計(jì)的，集成化的IS-IS是擴(kuò)展版本的IS-IS協(xié)議，用于CLNS和IP混合的環(huán)境中，既可用于單純IP路由，又可用于單純CLNP路由，還可用于為兩者混合路由，后面提到的IS-IS協(xié)議都是指集成化的IS-IS協(xié)議。而OSPF是IETF為IP網(wǎng)絡(luò)設(shè)計(jì)的，只支持IP協(xié)議。它們都是基于鏈路狀態(tài)的自治系統(tǒng)內(nèi)部路由選擇協(xié)議，因此它們有許多相似之處：

①都采用E.W.Dijkstra算法進(jìn)行路由計(jì)算，并且除了非廣播多址網(wǎng)絡(luò)外，在其它網(wǎng)絡(luò)中采用組播方式傳送鏈路狀態(tài)報(bào)文。具有快速收斂、無(wú)環(huán)路等特點(diǎn)，都能很好地支持大型網(wǎng)絡(luò)。

②IS-IS和OSPF都采用分層路由的概念，都進(jìn)行區(qū)域的劃分并且都有骨干區(qū)域，為網(wǎng)絡(luò)規(guī)劃提供了比較靈活的設(shè)計(jì)方法。

③為了控制鏈路狀態(tài)數(shù)據(jù)庫(kù)的規(guī)模和復(fù)雜度，IS-IS和OSPF在廣播網(wǎng)絡(luò)上都選舉DR來(lái)?yè)?dān)任數(shù)據(jù)庫(kù)同步的主要角色。

④IS-IS和OSPF對(duì)路由開(kāi)銷的度量都采用了接口可配置的代價(jià)，能夠比較正確地反映網(wǎng)絡(luò)的實(shí)際情況。

⑤對(duì)于每個(gè)LSP(LSA)都有一個(gè)鏈路狀態(tài)計(jì)時(shí)器相關(guān)聯(lián)，在正常情況下，如果在一定時(shí)間內(nèi)LSP(LSA)被更新，就重新開(kāi)始計(jì)時(shí)。如果在規(guī)定時(shí)間內(nèi)沒(méi)有收到新的更新，鏈路狀態(tài)計(jì)時(shí)器超時(shí)，將從數(shù)據(jù)庫(kù)中清除該LSP(LSA)，不再用做路由計(jì)算用。

⑥在采用Dijkstra算法進(jìn)行路由計(jì)算時(shí)，如果在最后的路由子集中有多條等價(jià)代價(jià)的、等價(jià)路徑類型的路由存在，那么兩種協(xié)議都會(huì)把它們放入路由選擇表，并且利用它們實(shí)現(xiàn)負(fù)載平衡。

雖然兩種協(xié)議有許多共同點(diǎn)，但是因?yàn)樗鼈冊(cè)诰唧w實(shí)現(xiàn)上存在著差別，因此它們又有許多不同：

①報(bào)文格式不同

OSPF協(xié)議報(bào)文封裝在IP數(shù)據(jù)報(bào)中，通過(guò)IP協(xié)議傳送，只支持IP協(xié)議；IS-IS協(xié)議報(bào)文直接封裝在鏈路層報(bào)文中，直接在鏈路層上傳送，支持CLNS、IP等多種協(xié)議。

②度量的最大值不同

兩種協(xié)議都是基于路由度量值來(lái)決定最短路徑，一條路由的度量值是指沿著到達(dá)目的網(wǎng)絡(luò)的路由路徑上所有出站接口的代價(jià)之和。OSPF協(xié)議支持無(wú)大小限制、任意的度量值；IS-IS協(xié)議支持最大的度量值為1023，此值雖然在大型互聯(lián)網(wǎng)絡(luò)中有點(diǎn)小，但它卻提高了Dijkstra算法的效率。

③區(qū)域劃分方式不同

IS-IS協(xié)議中整個(gè)路由器只能全部屬于一個(gè)區(qū)域，區(qū)域邊界位于兩個(gè)路由器之間，路由器的LSDB按Level1來(lái)維護(hù)；而OSPF按接口來(lái)劃分，一個(gè)路由器可以屬于多個(gè)區(qū)域，為每個(gè)區(qū)域維護(hù)一個(gè)LSDB數(shù)據(jù)庫(kù)。另外，OSPF通過(guò)特殊的區(qū)域ID Area0來(lái)定義骨干區(qū)域，而IS-IS是通過(guò)連續(xù)的Level2路由器來(lái)組成骨干區(qū)域，這樣就使IS-IS比OSPF有更好的可擴(kuò)展性，需要擴(kuò)展骨干區(qū)域時(shí)，只需加入更多的Level2路由器就可以。

④DR選舉方式不同

在廣播多址網(wǎng)絡(luò)中，兩種協(xié)議都要選舉DR，但是IS-IS協(xié)議的DR選舉比較簡(jiǎn)單，而且是搶占式可預(yù)見(jiàn)的，優(yōu)先級(jí)最高的是DR，優(yōu)先級(jí)為0的也可能成為DR。IS-IS協(xié)議沒(méi)有BDR，DR失敗，重新選舉DR。OSPF協(xié)議DR選舉機(jī)制比較復(fù)雜并不可預(yù)見(jiàn)，優(yōu)先級(jí)最高的不一定是DR，優(yōu)先級(jí)為0的不可能成為DR，并且有BDR的概念，當(dāng)DR出故障時(shí)，BDR升級(jí)為DR。

⑤區(qū)域間路由選擇算法不同

IS-IS在區(qū)域內(nèi)運(yùn)行Level1 SPF計(jì)算路由，在區(qū)域間運(yùn)行Level2 SPF計(jì)算路由；OSPF在區(qū)域內(nèi)運(yùn)行SPF計(jì)算路由，在區(qū)域間運(yùn)行距離向量算法來(lái)計(jì)算路由。比較兩種協(xié)議，IS-IS使用更少的鏈路狀態(tài)數(shù)據(jù)包，因此開(kāi)銷更小，效率更高一些。

⑥支持的網(wǎng)絡(luò)類型不同

OSPF協(xié)議支持4種網(wǎng)絡(luò)類型：廣播型網(wǎng)絡(luò)、非廣播多址網(wǎng)絡(luò)、點(diǎn)到點(diǎn)網(wǎng)絡(luò)點(diǎn)到多點(diǎn)網(wǎng)絡(luò)。在前兩種網(wǎng)絡(luò)中要選舉DR和BDR。而IS-IS不支持點(diǎn)到多點(diǎn)網(wǎng)絡(luò)類型，并且非廣播多址網(wǎng)絡(luò)也只能模擬成點(diǎn)到點(diǎn)網(wǎng)絡(luò)來(lái)運(yùn)行。

從以上分析可以看到，在CPU的利用方面和路由更新的處理方面，IS-IS協(xié)議更有效些，不僅需要處理的鏈路狀態(tài)數(shù)據(jù)包要少一些，而且創(chuàng)建維護(hù)路由的機(jī)制可以占用更少的資源。下面通過(guò)OPNET仿真軟件對(duì)它們進(jìn)行建模分析。

3 仿真分析

3.1 仿真建模

在OPNET中建立仿真模型如圖1所示，模型中創(chuàng)建兩個(gè)場(chǎng)景，它們使用相同的拓?fù)浣Y(jié)構(gòu)。

OSPF場(chǎng)景：

在此場(chǎng)景中，所有路由器端口上都啟用OSPF協(xié)議，創(chuàng)建骨干區(qū)域0，包含與北京和武漢結(jié)點(diǎn)相連的所有鏈路，并設(shè)置開(kāi)銷值為20；創(chuàng)建普通區(qū)域1，包含與西安、成都和廣州結(jié)點(diǎn)相連的三條鏈路，并設(shè)置開(kāi)銷值為40；創(chuàng)建普通區(qū)域2，包含與沈陽(yáng)、南京和上海結(jié)點(diǎn)相連的三條鏈路，并設(shè)置開(kāi)銷值為60。在成都和上海結(jié)點(diǎn)之間創(chuàng)建IP通信流。

IS_IS場(chǎng)景：

在此場(chǎng)景中，所有路由器端口上都啟用IS-IS協(xié)議。創(chuàng)建區(qū)域49.0001，包含北京和武漢兩個(gè)結(jié)點(diǎn)；創(chuàng)建區(qū)域49.0002，包含西安、成都和廣州三個(gè)結(jié)點(diǎn)；創(chuàng)建區(qū)域49.0003，包含沈陽(yáng)、南京和上海三個(gè)結(jié)點(diǎn)。其中普通區(qū)域包括成都和上海兩個(gè)結(jié)點(diǎn)，其它結(jié)點(diǎn)屬于骨干區(qū)域。其它與OSPF場(chǎng)景相同。

3.2 結(jié)果分析

3.2.1 收斂速度

兩種算法收斂速度比較如圖2所示。OSPF協(xié)議收斂周期約為13秒，而IS-IS協(xié)議收斂周期約為15秒，收斂速度相近，這是因?yàn)樗鼈兪褂孟嗤乃惴ㄟM(jìn)行路由計(jì)算。

3.2.2 協(xié)議產(chǎn)生的開(kāi)銷

①CPU、緩存開(kāi)銷

圖3 CPU開(kāi)銷和緩存隊(duì)列長(zhǎng)度比較

兩種算法CPU、緩存開(kāi)銷比較如圖3所示。OSPF協(xié)議在達(dá)到收斂狀態(tài)前CPU、緩存開(kāi)銷要高于IS-IS協(xié)議，這是因?yàn)樵贑PU的利用方面和路由更新的處理方面IS-IS協(xié)議更有效些。

②鏈路開(kāi)銷

兩種算法鏈路開(kāi)銷比較如圖4所示。OSPF協(xié)議在達(dá)到收斂狀態(tài)前發(fā)送和接收的組播報(bào)文數(shù)要高于IS-IS協(xié)議，這是因?yàn)镺SPF協(xié)議中發(fā)送的LSA報(bào)文數(shù)多于IS-IS協(xié)議發(fā)送的LSP報(bào)文數(shù)。

圖4 發(fā)送和接收組播報(bào)文數(shù)比較

3.2.3 負(fù)載平衡

兩種算法負(fù)載平衡比較如圖5所示。OSPF和IS-IS協(xié)議都能實(shí)現(xiàn)負(fù)載平衡。

4 結(jié)論

通過(guò)以上分析可以看出，IS-IS和OSPF協(xié)議收斂速度都比較快，都能實(shí)現(xiàn)負(fù)載平衡，而在開(kāi)銷方面前者要小于后者。IS-IS協(xié)議不但可以和OSPF協(xié)議一樣被用在骨干網(wǎng)上，實(shí)現(xiàn)骨干網(wǎng)內(nèi)部路徑選擇、負(fù)載平衡等，而且在有些方面還優(yōu)于OSPF協(xié)議。IS-IS協(xié)議還有一些缺點(diǎn)，如只定義了兩種網(wǎng)絡(luò)拓?fù)漕愋?；提出了virtual-link來(lái)修復(fù)分開(kāi)的骨干區(qū)域，但目前沒(méi)有具體的實(shí)現(xiàn)等。

[1]Jeff D oyle CCIE#1919著.葛建立，吳建章譯.TCP/IP路由技術(shù)（第一卷）[M].北京：人民郵電出版社，2003.

[2]謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)（第5版）[M].北京：電子工業(yè)出版社，2008.

[3]陳敏.O PN ET網(wǎng)絡(luò)仿真[M].北京：清華大學(xué)出版社，2004.

[4]王文博，張金文.O PN ET M odeler與網(wǎng)絡(luò)仿真[M].北京：人民郵電出版社，2003.

[5]楊子江，張興明，張建輝.利用區(qū)域劃分算法降低O SPF路由表計(jì)算開(kāi)銷[J].微計(jì)算機(jī)信息，2005，9x：92-94.

[6]柴晟，羅傳軍，羅惠瓊.自治系統(tǒng)內(nèi)部路由的仿真實(shí)驗(yàn)分析[J].微計(jì)算機(jī)信息，2007，18：235-236.

[7]尤瀾濤，朱巧明，李培峰.基于O SPF的網(wǎng)絡(luò)拓?fù)淇焖侔l(fā)現(xiàn)系統(tǒng)的設(shè)計(jì)[J].計(jì)算機(jī)工程，2006，32（24）：115-117.

[8]Ross Callon.U se of O SI IS-IS for Routing in TCP/IP and D ual Environments[S].IETF RFC 1195，1990.

[9]J.M oy.O SPF V ersion 2[S].IETF RFC 2328，1998.

TP393

A

1005-1554（2010）02-0021-03

2009-11-16

曹雪峰（1967-），男，滿族，河北隆化人，承德民族師專數(shù)學(xué)與計(jì)算機(jī)系副教授，主要從事計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用技術(shù)研究。