低負(fù)載、可靠的鏈路狀態(tài)路由協(xié)議洪泛算法ＥＲＳＮ

摘要：為了減少冗余報(bào)文的發(fā)送，降低網(wǎng)絡(luò)負(fù)載，提出了ERSN（efficient reliable subnetwork）算法。在保證洪泛可靠性的條件下，ERSN算法采用減少鏈路數(shù)目的方法，減少了鄰居路由器的數(shù)量，從而降低了洪泛報(bào)文的數(shù)量。實(shí)驗(yàn)結(jié)果表明，在維持穩(wěn)定與可靠的條件下，ERSN算法比標(biāo)準(zhǔn)的洪泛算法有效地減少了洪泛報(bào)文的數(shù)量。

關(guān)鍵詞：路由協(xié)議；鏈路狀態(tài)；洪泛

中圖分類(lèi)號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)01－0056－03

0引言

路由算法可以分為距離矢量路由算法和鏈路狀態(tài)路由算法兩類(lèi)。在距離矢量路由算法中，每一個(gè)路由器維護(hù)一個(gè)矢量，矢量中列出了當(dāng)前已知的到每個(gè)目標(biāo)的最佳距離以及所使用的路徑。通過(guò)在每個(gè)鄰居之間相互交換信息，路由器不斷地更新它們內(nèi)部的路由表。但距離矢量路由算法收斂較慢，并且不易于擴(kuò)展。當(dāng)今網(wǎng)絡(luò)中，鏈路狀態(tài)路由算法是占主導(dǎo)地位的域內(nèi)路由算法，如OSPF、IS IS都是使用這種算法。這種算法主要有兩個(gè)階段：每個(gè)路由器收集完整的網(wǎng)絡(luò)拓?fù)湫畔ⅲ宦酚善魍ㄟ^(guò)收集到的拓?fù)湫畔⒂?jì)算路由。在第一個(gè)階段中，路由器通過(guò)與鄰居路由器交換鏈路狀態(tài)信息得到完整的網(wǎng)絡(luò)拓?fù)湫畔ⅲ辉诘诙€(gè)階段中，每一個(gè)路由器獨(dú)立使用收集到的拓?fù)湫畔?gòu)造路由表。

與距離矢量路由算法相比，鏈路狀態(tài)路由算法最突出的優(yōu)點(diǎn)是每一個(gè)路由器獨(dú)立計(jì)算路由，不依賴(lài)其他路由器的計(jì)算結(jié)果。Huitema[1]還列出了其他的一些優(yōu)點(diǎn)，如支持到目的地址的多種路徑、快速收斂等。但是當(dāng)網(wǎng)絡(luò)拓?fù)涓淖儠r(shí)，鏈路狀態(tài)路由算法需要洪泛鏈路狀態(tài)信息，以確保同一個(gè)區(qū)域中的拓?fù)鋽?shù)據(jù)庫(kù)達(dá)到一致。尤其當(dāng)鏈路變化較頻繁或是區(qū)域非常大、包含的路由器非常多時(shí)，洪泛的負(fù)載是非常大的。這種負(fù)載可能造成網(wǎng)絡(luò)的擁塞，可以使路由收斂的性能變?cè)悖瑥亩鴮?dǎo)致網(wǎng)絡(luò)的不穩(wěn)定。所以洪泛過(guò)程中發(fā)送信息的數(shù)量在鏈路狀態(tài)路由協(xié)議中起著很重要的作用。

目前，人們?cè)谶@方面已經(jīng)做了很多的工作，從劃分網(wǎng)絡(luò)區(qū)域、減少路由計(jì)算和限制報(bào)文更新頻率等多方面作了深入的研究。本文針對(duì)洪泛過(guò)程中發(fā)送大量冗余報(bào)文的特點(diǎn)，通過(guò)減少網(wǎng)絡(luò)中的鏈路數(shù)目，有效地減少了洪泛報(bào)文的發(fā)送數(shù)量。

1相關(guān)工作

鏈路狀態(tài)路由協(xié)議比較復(fù)雜，適合于較大的網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，就會(huì)產(chǎn)生大量的冗余報(bào)文，給網(wǎng)絡(luò)和路由器帶來(lái)很大的負(fù)載。為了減少報(bào)文的發(fā)送，目前人們?cè)谶@方面已經(jīng)作了大量的研究。Aho等人[2]提出了一種網(wǎng)絡(luò)結(jié)構(gòu)， 根據(jù)這種結(jié)構(gòu)劃分OSPF 的區(qū)域， 能夠使OSPF 產(chǎn)生的鏈路狀態(tài)信息(link state advertisement， LSA)的數(shù)量從O(n2) 減少到O(n1/3×n)，降低了洪泛對(duì)網(wǎng)絡(luò)帶來(lái)的負(fù)載。

文獻(xiàn)[3]中提出了graceful restart 方案。該方案使得路由器在某些情況下需要重新啟動(dòng)時(shí)， 不會(huì)導(dǎo)致重新計(jì)算路由，這樣就大大減輕了路由器和網(wǎng)絡(luò)的負(fù)載。文獻(xiàn)[4]中提出了改進(jìn)的graceful restart方案， 進(jìn)一步減輕了路由器的負(fù)載。文獻(xiàn)[5]中指出忽略鏈路度量值的改變也可以降低發(fā)送信息的數(shù)量，減輕網(wǎng)絡(luò)負(fù)載。當(dāng)鏈路度量值改變時(shí)，路由器將忽略這個(gè)拓?fù)涞母淖儯⒉话l(fā)送這個(gè)更新信息。只有當(dāng)多個(gè)鏈路的度量改變后，路由器才會(huì)廣播這個(gè)包含了所有拓?fù)渥兓臄?shù)據(jù)包。 通過(guò)限制更新的頻率，發(fā)送信息的總數(shù)量就會(huì)減少。但是當(dāng)鏈路的度量是由于鏈路斷開(kāi)而改變時(shí)，就會(huì)造成路由錯(cuò)誤和數(shù)據(jù)包的丟失。因此，為了修復(fù)包含斷開(kāi)鏈路的路由路徑，鏈路斷開(kāi)的信息必須被馬上發(fā)送到其他路由器。文獻(xiàn)[6]中提出了通過(guò)控制網(wǎng)絡(luò)拓?fù)渲朽従庸?jié)點(diǎn)的數(shù)目來(lái)降低洪泛負(fù)載的RSN(reliable subnetwork)算法。在這個(gè)算法中，首先為網(wǎng)絡(luò)拓?fù)錁?gòu)造一棵最小生成樹(shù)MST，計(jì)算最小生成樹(shù)每一個(gè)節(jié)點(diǎn)的度數(shù)；其次為度數(shù)是1的葉子節(jié)點(diǎn)加邊。當(dāng)加邊后網(wǎng)絡(luò)拓?fù)涞倪呥B通度[7]（邊連通度是由連通圖產(chǎn)生非連通圖需要?jiǎng)h除邊的最少數(shù)目）小于1時(shí)，繼續(xù)為最小生成樹(shù)加入開(kāi)銷(xiāo)值最小的邊，直到網(wǎng)絡(luò)拓?fù)涞倪呥B通度大于1。這樣得到最后的拓?fù)鋱D稱(chēng)為SNT(subnetwork topology)。當(dāng)鏈路狀態(tài)路由協(xié)議需要洪泛路由信息時(shí)，只在屬于SNT的鏈路上進(jìn)行洪泛，其他不屬于SNT的鏈路不進(jìn)行信息的洪泛。因?yàn)镾NT的邊連通度大于1，所以當(dāng)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的鏈路斷開(kāi)后，可以保證網(wǎng)絡(luò)中的節(jié)點(diǎn)不會(huì)從網(wǎng)絡(luò)拓?fù)渲泄铝⒊鋈ァ５窃撍惴](méi)有考慮SNT生成過(guò)程中橋的產(chǎn)生。設(shè)無(wú)向圖G＝V， E 是連通的。若有邊子集E′屬于E，使得在圖G中刪除了E′后，所得到的子圖G－E′是非連通的，而在圖G中刪除E′的任何真子集所得到的子圖仍是連通圖（若無(wú)向圖中任意兩個(gè)節(jié)點(diǎn)都是互相可達(dá)的，則稱(chēng)該無(wú)向圖為連通的；否則為非連通的），則稱(chēng)E′為G的一個(gè)邊割集。若圖G的某一邊割集僅有一條邊e，則稱(chēng)該邊e為橋[8]。橋是網(wǎng)絡(luò)拓?fù)渲幸粋€(gè)重要的鏈路。當(dāng)這個(gè)鏈路斷開(kāi)時(shí)，網(wǎng)絡(luò)拓?fù)渚蜁?huì)分成兩個(gè)不連通的部分，并且存在橋的網(wǎng)絡(luò)拓?fù)涞倪呥B通度為1。因此，RSN算法為了保證邊連通度大于1，就必須為拓?fù)鋱D加邊直到邊連通度大于1。RSN算法不能有效減少路由器鏈路的數(shù)目，降低洪泛信息的數(shù)量，保證路由快速有效地收斂。

2ERSN算法

在鏈路狀態(tài)路由算法中，當(dāng)網(wǎng)絡(luò)拓?fù)涓淖儠r(shí)，路由器就會(huì)洪泛LSA，以確保同一個(gè)區(qū)域內(nèi)的拓?fù)鋽?shù)據(jù)庫(kù)達(dá)到一致。收到更新的LSA后，為確保其他節(jié)點(diǎn)數(shù)據(jù)庫(kù)的一致性，接收節(jié)點(diǎn)需要將更新的LSA洪泛到它的所有鄰居路由器（除了發(fā)送此信息的鄰居）。這樣就會(huì)造成大量冗余信息的產(chǎn)生。如圖1所示，假設(shè)包含12個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都運(yùn)行OSPF協(xié)議，當(dāng)連接節(jié)點(diǎn)A的某個(gè)鏈路斷開(kāi)后，節(jié)點(diǎn)A就會(huì)向它連接的所有鄰居節(jié)點(diǎn)B、C、D、E發(fā)送LSA。這樣節(jié)點(diǎn)F就會(huì)收到A、C、E發(fā)送的包含同樣信息的LSA；其他節(jié)點(diǎn)也同樣要收到大量包含相同信息的冗余LSAs，從而造成帶寬的浪費(fèi)并加重網(wǎng)絡(luò)負(fù)載。

根據(jù)RSN算法，首先構(gòu)造網(wǎng)絡(luò)拓?fù)涞淖钚∩蓸?shù)MST，計(jì)算最小生成樹(shù)每一個(gè)節(jié)點(diǎn)的度數(shù)，并為最小生成樹(shù)的葉子節(jié)點(diǎn)加邊。當(dāng)拓?fù)鋱D的邊連通度小于1時(shí)，隨機(jī)加邊直到拓?fù)鋱D的邊連通度大于1。最后得到的拓?fù)鋱DSNT如圖2所示。

由于RSN算法沒(méi)有考慮加邊過(guò)程中橋的產(chǎn)生，最后生成的拓?fù)鋱D并不能有效減少需要洪泛的鏈路。例如圖2中，為了防止橋的出現(xiàn)，為MST的葉子節(jié)點(diǎn)加邊后必須為子圖再添加邊AC、AI、EG、EH。

通過(guò)深入分析，本文提出了ERSN算法。其核心思想是通過(guò)減少網(wǎng)絡(luò)拓?fù)渲墟溌返臄?shù)目來(lái)控制需要洪泛的信息數(shù)量。在構(gòu)造網(wǎng)絡(luò)拓?fù)鋱D最小生成樹(shù)的基礎(chǔ)上，為拓?fù)鋱D的最小生成樹(shù)的葉子節(jié)點(diǎn)加邊；同時(shí)要保證加邊后構(gòu)成的回路中包含最多的節(jié)點(diǎn)，以盡可能避免橋的產(chǎn)生。這樣就會(huì)保證在拓?fù)鋱D的連通度大于1的情況下，盡可能地減少拓?fù)鋱D中鏈路的數(shù)量，最大程度地降低需要洪泛的信息數(shù)量，減少網(wǎng)絡(luò)帶寬的占用。

根據(jù)ERSN算法最終得到如圖3所示的網(wǎng)絡(luò)拓?fù)洹Ｊ紫鹊玫阶钚∩蓸?shù)，節(jié)點(diǎn)C、D、I、J、K、L是最小生成樹(shù)中的葉子節(jié)點(diǎn)，它們的度數(shù)為1，不能保證洪泛的可靠性。當(dāng)這些節(jié)點(diǎn)連接的鏈路斷開(kāi)后，整個(gè)拓?fù)鋱D就會(huì)被分成孤立的幾個(gè)連通分支(設(shè)M′是無(wú)向圖M的連通子圖。若M′不包含在任何更大的連通子圖中，則稱(chēng)M′是圖M的連通分支)，每個(gè)分支都不能得到整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔ⅲ瑥亩荒苓M(jìn)行正確的路由計(jì)算。步驟d)為這些葉子節(jié)點(diǎn)加邊DI、EF、JK、KL，最后得到圖3。

3模擬實(shí)驗(yàn)

為了測(cè)試該算法的性能，利用網(wǎng)絡(luò)模擬器OPNET搭建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)它進(jìn)行模擬，并與標(biāo)準(zhǔn)洪泛算法和RSN算法的性能進(jìn)行比較。算法性能比較包括兩個(gè)指標(biāo)：網(wǎng)絡(luò)洪泛LSAs的總數(shù)量和失效節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)拓?fù)涞挠绊憽ＤM器隨機(jī)產(chǎn)生的網(wǎng)絡(luò)拓?fù)浒?5個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)、25條鏈路。在限定30 s內(nèi)，任何一個(gè)節(jié)點(diǎn)隨機(jī)地發(fā)生改變而洪泛LSAs，統(tǒng)計(jì)網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)送的LSAs的總數(shù)量。

由圖4的模擬結(jié)果可以看出，ERSN算法發(fā)送的報(bào)文數(shù)量比標(biāo)準(zhǔn)的洪泛算法減少了45％，比RSN算法減少了30％，大大減少了報(bào)文的發(fā)送數(shù)量，減輕了網(wǎng)絡(luò)負(fù)載。

假設(shè)模擬器產(chǎn)生的網(wǎng)絡(luò)拓?fù)涞拿總€(gè)節(jié)點(diǎn)都隨機(jī)失效。當(dāng)任意一個(gè)節(jié)點(diǎn)失效時(shí)，網(wǎng)絡(luò)拓?fù)浔环指畛瑟?dú)立的兩個(gè)部分，統(tǒng)計(jì)網(wǎng)絡(luò)中存在多少個(gè)這樣的節(jié)點(diǎn)。由表1可以看出，標(biāo)準(zhǔn)洪泛算法和ERSN算法中不存在這樣的節(jié)點(diǎn)：當(dāng)這個(gè)節(jié)點(diǎn)失效時(shí)，網(wǎng)絡(luò)被分割成獨(dú)立的兩個(gè)部分，從而使節(jié)點(diǎn)的鏈路狀態(tài)數(shù)據(jù)庫(kù)不能統(tǒng)一。RSN算法中存在兩個(gè)這樣的節(jié)點(diǎn)：當(dāng)這兩個(gè)節(jié)點(diǎn)失效時(shí)，RSN算法不能使節(jié)點(diǎn)統(tǒng)一它們的鏈路狀態(tài)數(shù)據(jù)庫(kù)，從而保證洪泛的可靠性。

4結(jié)束語(yǔ)

本文通過(guò)深入的分析，結(jié)合計(jì)算機(jī)圖論的知識(shí)提出了ERSN算法。其基本思想就是在保證網(wǎng)絡(luò)拓?fù)涞倪呥B通度大于1的情況下，盡可能地減少每個(gè)路由器的鏈路數(shù)目，從而減少需要洪泛的LSAs。因?yàn)樗惴p少的只是每個(gè)路由器發(fā)送的冗余LSAs的數(shù)量，所以不會(huì)降低洪泛的可靠性，但可以有效降低發(fā)送的LSAs數(shù)量。它大大降低了鏈路狀態(tài)路由協(xié)議給網(wǎng)絡(luò)帶來(lái)的負(fù)載。

參考文獻(xiàn)：

［1］HUITEMA C.Rouing in the Internet[M].N J:Prentice Hall，1995:127 149.

[2]AHO A，LEE D.Hierarchical networks and the LSA Nsquared problem in OSPF routing[C]//Proc of IEEE Conference on GLOBECOM.New York: IEEE Press，2000:397－403.

[3]RFC 3623， Graceful OSPF restart[S].

[4]SHAIKH A，DUBE R，VARMA A.A voiding instability during graceful shutdown of OSPF[C]//Proc of IEEE Conference on INFOCOM.New York: IEEE Press，2002:397－403.

[5]NARVAEZ P，SIU K Y，HONG Y T.Local restoration algorithm for link state routing protocols[C]//Proc of the 8th IEEE Conference on Computer Communications and Networks. Boston: IEEE Press，1999:352－357.

[6]MIYAMURA T，KURIMOTO T，AOKI M.Enhancing the network scalability of link state routing protocols by reducing their flooding overhead[C]//Proc ofIEEE Conference on HPSR.Torino:IEEE Press，2003:263－271.

[7]殷劍宏，吳開(kāi)亞.圖論及其算法[M].北京:中國(guó)科學(xué)技術(shù)大學(xué)出版社，2003:56－82.

[8]謝政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué)出版社，2003:139 157.

[9]MOY J.OSPF:anatomy of an Internet routing protocol[M].Boston:Addison Wesley，1998:72－83.

[10]RFC 1195，Use of OS1 IS IS for routing in TCP/IP and dual environments[S].

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”