低負載、可靠的鏈路狀態路由協議洪泛算法ＥＲＳＮ

摘要：為了減少冗余報文的發送，降低網絡負載，提出了ERSN（efficient reliable subnetwork）算法。在保證洪泛可靠性的條件下，ERSN算法采用減少鏈路數目的方法，減少了鄰居路由器的數量，從而降低了洪泛報文的數量。實驗結果表明，在維持穩定與可靠的條件下，ERSN算法比標準的洪泛算法有效地減少了洪泛報文的數量。

關鍵詞：路由協議；鏈路狀態；洪泛

中圖分類號：TP301．6文獻標志碼：A

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

0引言

路由算法可以分為距離矢量路由算法和鏈路狀態路由算法兩類。在距離矢量路由算法中，每一個路由器維護一個矢量，矢量中列出了當前已知的到每個目標的最佳距離以及所使用的路徑。通過在每個鄰居之間相互交換信息，路由器不斷地更新它們內部的路由表。但距離矢量路由算法收斂較慢，并且不易于擴展。當今網絡中，鏈路狀態路由算法是占主導地位的域內路由算法，如OSPF、IS IS都是使用這種算法。這種算法主要有兩個階段：每個路由器收集完整的網絡拓撲信息；路由器通過收集到的拓撲信息計算路由。在第一個階段中，路由器通過與鄰居路由器交換鏈路狀態信息得到完整的網絡拓撲信息；在第二個階段中，每一個路由器獨立使用收集到的拓撲信息構造路由表。

與距離矢量路由算法相比，鏈路狀態路由算法最突出的優點是每一個路由器獨立計算路由，不依賴其他路由器的計算結果。Huitema[1]還列出了其他的一些優點，如支持到目的地址的多種路徑、快速收斂等。但是當網絡拓撲改變時，鏈路狀態路由算法需要洪泛鏈路狀態信息，以確保同一個區域中的拓撲數據庫達到一致。尤其當鏈路變化較頻繁或是區域非常大、包含的路由器非常多時，洪泛的負載是非常大的。這種負載可能造成網絡的擁塞，可以使路由收斂的性能變糟，從而導致網絡的不穩定。所以洪泛過程中發送信息的數量在鏈路狀態路由協議中起著很重要的作用。

目前，人們在這方面已經做了很多的工作，從劃分網絡區域、減少路由計算和限制報文更新頻率等多方面作了深入的研究。本文針對洪泛過程中發送大量冗余報文的特點，通過減少網絡中的鏈路數目，有效地減少了洪泛報文的發送數量。

1相關工作

鏈路狀態路由協議比較復雜，適合于較大的網絡結構。當網絡拓撲發生變化時，就會產生大量的冗余報文，給網絡和路由器帶來很大的負載。為了減少報文的發送，目前人們在這方面已經作了大量的研究。Aho等人[2]提出了一種網絡結構， 根據這種結構劃分OSPF 的區域， 能夠使OSPF 產生的鏈路狀態信息(link state advertisement， LSA)的數量從O(n2) 減少到O(n1/3×n)，降低了洪泛對網絡帶來的負載。

文獻[3]中提出了graceful restart 方案。該方案使得路由器在某些情況下需要重新啟動時， 不會導致重新計算路由，這樣就大大減輕了路由器和網絡的負載。文獻[4]中提出了改進的graceful restart方案， 進一步減輕了路由器的負載。文獻[5]中指出忽略鏈路度量值的改變也可以降低發送信息的數量，減輕網絡負載。當鏈路度量值改變時，路由器將忽略這個拓撲的改變，并不發送這個更新信息。只有當多個鏈路的度量改變后，路由器才會廣播這個包含了所有拓撲變化的數據包。 通過限制更新的頻率，發送信息的總數量就會減少。但是當鏈路的度量是由于鏈路斷開而改變時，就會造成路由錯誤和數據包的丟失。因此，為了修復包含斷開鏈路的路由路徑，鏈路斷開的信息必須被馬上發送到其他路由器。文獻[6]中提出了通過控制網絡拓撲中鄰居節點的數目來降低洪泛負載的RSN(reliable subnetwork)算法。在這個算法中，首先為網絡拓撲構造一棵最小生成樹MST，計算最小生成樹每一個節點的度數；其次為度數是1的葉子節點加邊。當加邊后網絡拓撲的邊連通度[7]（邊連通度是由連通圖產生非連通圖需要刪除邊的最少數目）小于1時，繼續為最小生成樹加入開銷值最小的邊，直到網絡拓撲的邊連通度大于1。這樣得到最后的拓撲圖稱為SNT(subnetwork topology)。當鏈路狀態路由協議需要洪泛路由信息時，只在屬于SNT的鏈路上進行洪泛，其他不屬于SNT的鏈路不進行信息的洪泛。因為SNT的邊連通度大于1，所以當網絡中一個節點的鏈路斷開后，可以保證網絡中的節點不會從網絡拓撲中孤立出去。但是該算法沒有考慮SNT生成過程中橋的產生。設無向圖G＝V， E 是連通的。若有邊子集E′屬于E，使得在圖G中刪除了E′后，所得到的子圖G－E′是非連通的，而在圖G中刪除E′的任何真子集所得到的子圖仍是連通圖（若無向圖中任意兩個節點都是互相可達的，則稱該無向圖為連通的；否則為非連通的），則稱E′為G的一個邊割集。若圖G的某一邊割集僅有一條邊e，則稱該邊e為橋[8]。橋是網絡拓撲中一個重要的鏈路。當這個鏈路斷開時，網絡拓撲就會分成兩個不連通的部分，并且存在橋的網絡拓撲的邊連通度為1。因此，RSN算法為了保證邊連通度大于1，就必須為拓撲圖加邊直到邊連通度大于1。RSN算法不能有效減少路由器鏈路的數目，降低洪泛信息的數量，保證路由快速有效地收斂。

2ERSN算法

在鏈路狀態路由算法中，當網絡拓撲改變時，路由器就會洪泛LSA，以確保同一個區域內的拓撲數據庫達到一致。收到更新的LSA后，為確保其他節點數據庫的一致性，接收節點需要將更新的LSA洪泛到它的所有鄰居路由器（除了發送此信息的鄰居）。這樣就會造成大量冗余信息的產生。如圖1所示，假設包含12個節點的網絡，每一個網絡節點都運行OSPF協議，當連接節點A的某個鏈路斷開后，節點A就會向它連接的所有鄰居節點B、C、D、E發送LSA。這樣節點F就會收到A、C、E發送的包含同樣信息的LSA；其他節點也同樣要收到大量包含相同信息的冗余LSAs，從而造成帶寬的浪費并加重網絡負載。

根據RSN算法，首先構造網絡拓撲的最小生成樹MST，計算最小生成樹每一個節點的度數，并為最小生成樹的葉子節點加邊。當拓撲圖的邊連通度小于1時，隨機加邊直到拓撲圖的邊連通度大于1。最后得到的拓撲圖SNT如圖2所示。

由于RSN算法沒有考慮加邊過程中橋的產生，最后生成的拓撲圖并不能有效減少需要洪泛的鏈路。例如圖2中，為了防止橋的出現，為MST的葉子節點加邊后必須為子圖再添加邊AC、AI、EG、EH。

通過深入分析，本文提出了ERSN算法。其核心思想是通過減少網絡拓撲中鏈路的數目來控制需要洪泛的信息數量。在構造網絡拓撲圖最小生成樹的基礎上，為拓撲圖的最小生成樹的葉子節點加邊；同時要保證加邊后構成的回路中包含最多的節點，以盡可能避免橋的產生。這樣就會保證在拓撲圖的連通度大于1的情況下，盡可能地減少拓撲圖中鏈路的數量，最大程度地降低需要洪泛的信息數量，減少網絡帶寬的占用。

根據ERSN算法最終得到如圖3所示的網絡拓撲。首先得到最小生成樹，節點C、D、I、J、K、L是最小生成樹中的葉子節點，它們的度數為1，不能保證洪泛的可靠性。當這些節點連接的鏈路斷開后，整個拓撲圖就會被分成孤立的幾個連通分支(設M′是無向圖M的連通子圖。若M′不包含在任何更大的連通子圖中，則稱M′是圖M的連通分支)，每個分支都不能得到整個網絡的拓撲信息，從而不能進行正確的路由計算。步驟d)為這些葉子節點加邊DI、EF、JK、KL，最后得到圖3。

3模擬實驗

為了測試該算法的性能，利用網絡模擬器OPNET搭建網絡拓撲結構對它進行模擬，并與標準洪泛算法和RSN算法的性能進行比較。算法性能比較包括兩個指標：網絡洪泛LSAs的總數量和失效節點對網絡拓撲的影響。模擬器隨機產生的網絡拓撲包含15個網絡節點、25條鏈路。在限定30 s內，任何一個節點隨機地發生改變而洪泛LSAs，統計網絡節點發送的LSAs的總數量。

由圖4的模擬結果可以看出，ERSN算法發送的報文數量比標準的洪泛算法減少了45％，比RSN算法減少了30％，大大減少了報文的發送數量，減輕了網絡負載。

假設模擬器產生的網絡拓撲的每個節點都隨機失效。當任意一個節點失效時，網絡拓撲被分割成獨立的兩個部分，統計網絡中存在多少個這樣的節點。由表1可以看出，標準洪泛算法和ERSN算法中不存在這樣的節點：當這個節點失效時，網絡被分割成獨立的兩個部分，從而使節點的鏈路狀態數據庫不能統一。RSN算法中存在兩個這樣的節點：當這兩個節點失效時，RSN算法不能使節點統一它們的鏈路狀態數據庫，從而保證洪泛的可靠性。

4結束語

本文通過深入的分析，結合計算機圖論的知識提出了ERSN算法。其基本思想就是在保證網絡拓撲的邊連通度大于1的情況下，盡可能地減少每個路由器的鏈路數目，從而減少需要洪泛的LSAs。因為算法減少的只是每個路由器發送的冗余LSAs的數量，所以不會降低洪泛的可靠性，但可以有效降低發送的LSAs數量。它大大降低了鏈路狀態路由協議給網絡帶來的負載。

參考文獻：

［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]殷劍宏，吳開亞.圖論及其算法[M].北京:中國科學技術大學出版社，2003:56－82.

[8]謝政.網絡算法與復雜性理論[M].長沙:國防科學技術大學出版社，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].

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”