基于懲罰機制的OSPF路由振蕩抑制算法

劉嵩 馬琳 劉福強 海軍裝備研究院,北京 100036

基于懲罰機制的OSPF路由振蕩抑制算法

劉嵩 馬琳 劉福強 海軍裝備研究院,北京 100036

在當今的互聯網中，路由振蕩越來越成為影響網絡服務質量的重大因素。為了解決此問題，提出了一種適用于開放式最短路徑優先協議(OSPF)的路由振蕩抑制算法。該算法借鑒邊界網關協議(BGP)中的路由振蕩抑制機制，引入懲罰值的概念，并結合OSPF的特點，將路由振蕩抑制轉化為相鄰路由器之間的鏈路振蕩抑制。仿真模擬顯示，本算法可以有效地屏蔽振蕩中的鏈路，大大減少了網絡中LSA的產生數量，增加了網絡的穩定性。

路由振蕩；鏈路振蕩；抑制

route flapping；link flapping；suppress；OSPF；BGP

路由表中的路由條目間斷性的消失和再現的現象，稱為路由振蕩。路由振蕩會導致路由器在互聯網內周期性的更新、洪泛的更新或撤銷鏈路消息，占用大量的網絡帶寬，同時不斷的鏈路狀態更新會引起頻繁的最短路徑優先路由重計算，加重CPU的負荷，嚴重時引起錯誤的路由重計算，導致大量丟包。

OSPF是一種專門為IP網絡開發且廣泛應用在單一自治系統內的路由協議，目前已成為事實上的域內路由協議標準。現有的OSPF中并無可靠的路由振蕩抑制機制，而主要依靠若干定時器來削弱路由振蕩帶來的影響。如思科公司的路由產品在RFC2328標準外額外定義了延緩路由重計算的定時器SPFDelay，以減少路由振蕩時的最短路徑重計算。但這延長了收斂過程，易引起錯誤的路由重計算，極端情況下甚至適得其反。而且無法真正屏蔽路由振蕩源，是一種消極的手段[1]。

域間路由協議BGP中基于懲罰機制的路由振蕩抑制機制，在實踐中被證明是行之有效的[2]。但OSPF是鏈路狀態協議，BGP是距離矢量協議，這個根本不同點使BGP的路由振蕩抑制算法無法直接應用在OSPF協議中。本文通過分析OSPF協議的特點，將路由振蕩避免轉化為鏈路振蕩避免[3]。對不穩定鏈路進行懲罰，從而較好的改善網絡性能。

1 OSPF原理

OSPF是一種分布式的鏈路狀態協議（link state protocol）[4]，每個路由器向外通告與本路由器相鄰的所有路由器的鏈路狀態，最終所有的路由器都建立一個全網統一的鏈路狀態數據庫（link state database），這個數據庫實際上就是全網的拓撲結構圖。每一個路由器根據收斂后的鏈路狀態數據庫，以自己為起點，采用最短路徑優先算法計算與目的節點之間的最佳路由，獨立的構造出自己的路由表。

OSPF鏈路狀態信息通過鏈路狀態廣播LSA（link state advertisement）表示，包括路由器ID、接口IP地址和相鄰接口的IP地址、鏈路代價、序列號、年齡和校驗和等內容。有多種LSA，用來描述不同的對象。其中路由器LSA最為重要，用來表示該路由器的各個端口所連接的對象和代價等信息。

路由器啟動后，通過接口向外組播Hello分組，用以探測鄰居，并開始建立鄰接關系。經過確認主從關系、交換鏈路數據庫摘要、請求新的LSA、發送和確認LSA等階段后，鏈路狀態數據庫將完全一致，即達到完全鄰接狀態（Full Adjacent）。當鏈路狀態改變或鏈路刷新時間到，路由器就更新和擴散LSA，同時接收其它節點洪泛的LSA，以保持全網的鏈路狀態數據庫是最新的。

OSPF同時定義了一些定時器來抑制過于快速的數據洪泛。如定義HelloInterval來禁止過快的Hello包發送，定義MinLsInterval來禁止過快的LSA更新，定義SPFDelay來禁止過于頻繁的最短路徑重計算。這也是目前OSPF抑制快速路由振蕩的主要方法，但效果并不是很好。

2 路由振蕩轉化為鏈路振蕩

圖1 LSA平均更新數量比較

與距離矢量路由協議不同的是，OSPF的鏈路狀態信息發送至全網，且僅發送與本路由器相鄰的路由器的鏈路狀態信息。當某條鏈路狀態發生變化，該路由器就使用鏈路狀態更新分組，用洪泛法向全網更新鏈路狀態。該分組首先發送給相鄰路由器，相鄰路由器必須將接收到的分組再轉發給除分組來源外的所有與自身相鄰的路由器，如此反復。若收到相同的LSA的多個實例，將通過比較序列號、校驗以及老化時間等參數判斷最新的LSA，并更新舊的LSA。

由此可見，OSPF雖然將鏈路狀態信息洪泛至全網，但鏈路信息首先被發送給相鄰的路由器，再通過相鄰路由器轉發出去。盡管域內每個路由器都有全網的鏈路狀態數據庫，并能獲知網內任意一條鏈路的變化，但它們互相之間傳遞信息卻是基于本地的鄰接關系。鏈路的更新信息只傳遞給鄰居，再由鄰居繼續轉發，而不會直接傳遞給域內的其它路由器。基于OSPF的這一特點，我們可以將路由振蕩由目前的基于定時器的全網抑制轉化為對本地鏈路振蕩的抑制。對于處于振蕩中的鏈路，相鄰路由器將接收到的鏈路狀態信息屏蔽，不再繼續轉發，該鏈路狀態變化將只局限于與該路由器相鄰的路由器范圍內，而不會波及全網。即每一個路由器都只處理與自己相鄰的路由器的鏈路變化。

3 基于懲罰機制的路由振蕩抑制算法

算法的核心思想是：鏈路的每一次振蕩都會被記錄為不良記錄，并增加一定的懲罰值，若懲罰值超過某個門限，該鏈路將會被抑制。被抑制的鏈路信息不會得到轉發，不會參加最短路徑重計算。鏈路穩定下來以后，鏈路的懲罰值會隨時間慢慢減少，當懲罰值減少到重用門限以下時，解除鏈路抑制。

對振蕩鏈路的抑制可能會影響網絡可達性和代價最小原則，因此應設置一個最大鏈路抑制數。若被抑制的鏈路數量達到最大鏈路抑制數，則應提前解除對當前懲罰值最小的鏈路的抑制。下面描述詳細的算法。

算法設置參數如下：

T：鏈路當前懲罰值的累計總額，初始值為0。

P：鏈路每振蕩一次增加的懲罰值。

H：鏈路當前的狀態，0表示未被抑制，1表示已經被抑制。

Ls：抑制門限，鏈路懲罰值超過抑制門限時將被抑制。

Lr：重用門限，處于被抑制狀態的鏈路的懲罰值降到重用門限或以下時，將被解除抑制。

Ts：鏈路處于被抑制狀態且已經穩定時，懲罰值的衰減速率。每過一個Ts周期，鏈路的懲罰值減半。這里的穩定是指一個Ts周期內，鏈路沒有再次振蕩。

Tr：鏈路處于未被抑制狀態且已經穩定時，懲罰值的衰減速率。每過一個Tr周期，鏈路的懲罰值減少P。這里的穩定是指一個Tr周期內，鏈路沒有再次振蕩。

Tc：上次懲罰值進行衰減的時間點。懲罰值的衰減并不是連續性的衰減，而是在一個衰減周期后直接減去一定值，因此需要記錄上一次衰減時的時間點。初始值為路由器剛啟動的時間。

Md：最大抑制門限，每條鏈路的懲罰值T所能累積到的最大值。這是為了避免鏈路在短時間內的急劇振蕩累積過高的懲罰值，導致鏈路在很長時間內都無法解除抑制。該值必須大于抑制門限，否則鏈路將永遠不會被懲罰。

Cl：當前被抑制的鏈路數量，初始為0。

Ml：最大鏈路抑制數，每個路由器同時可抑制的最大鏈路數。為了避免鏈路被抑制過多而影響網絡可達性，需限制路由器抑制鏈路數不大于Ml。

以上參數中除了說明初始值的外，其它都可以自行設置。Ls和P的比值越大，表示可容忍的振蕩程度越高。Lr和Ls的比值越大，表示鏈路被抑制后的恢復時間越短。最大抑制門限Md應該由重用門限Lr、鏈路在懲罰狀態時的衰減周期Ts和鏈路的最長抑制時間計算出來。假設衰減周期Ts為30分鐘，鏈路的最長抑制時間為1小時，重用門限Lr為1000，則最大抑制門限Md=4000，這樣才能保證在一個小時內經過兩個半衰期，懲罰值衰減到重用門限Lr以便鏈路解除抑制。

最重要的兩個參數是鏈路處于抑制狀態時的懲罰值衰減周期Ts和鏈路處于未抑制狀態時的懲罰值衰減周期Tr。Ts的值設置過小會導致鏈路可以迅速從被抑制狀態恢復到正常狀態，若這個恢復周期比鏈路振蕩周期小，則算法起不到抑制振蕩的作用。Ts的值也不能過大，因為過大就意味著鏈路長時間得不到恢復，即使鏈路已經穩定。對于Tr，它的值不應該過小，過小就意味著懲罰值衰減得太快，在對鏈路進行下一次懲罰時，可能前一次的懲罰值已經被清除了，起不到懲罰的作用。

算法的具體實施步驟如下所示：

1）路由器進行初始化，保存所有與自己相鄰的路由器的所有鏈路，并對鏈路進行參數初始化。T=0，H=0，Cl=0，Tc為當前時間。

2）每當路由器檢測到相鄰路由器的某條鏈路產生振蕩，就給這條鏈路增加一個單位懲罰值即T=T+P，若T>Md，則T=Md，同時Tc置為當前時間。若T>Ls，則令鏈路狀態H=1，表示鏈路已經被抑制，路由器不再對外廣播該鏈路信息，Cl=Cl+1。

3）若Cl>Ml，查找一條當前被抑制鏈路里最穩定的鏈路，即T最小的鏈路，提前解除對這條鏈路的抑制，Cl=Cl-1，重復執行該步驟直到不滿足Cl>Ml。

4）若鏈路處于未被抑制狀態下，檢查從Tc到現在是否已經過了Tr時間。若是，懲罰值減去P即T=T-P。

5）若鏈路處于被抑制狀態下，檢查從Tc到現在是否已經過了Ts時間。若是，將當前懲罰值減半，即T=T/2。若T

4 仿真與性能分析

為了驗證路由振蕩抑制算法的可行性和有效性，我們將采用相關的仿真軟件進行仿真。仿真包括對原OSPF算法的仿真和改進后算法的仿真，并對兩種算法進行比較。路由振蕩最顯著的危害是頻繁的向外更新LSA，占用網絡帶寬，同時引起路由器的最短路徑重計算。因此將每個路由器的LSA更新數量作為本次仿真的對比指標。

我們使用BRite[5]拓撲生成器根據Waxman算法生成一個具有128個節點260條鏈路的隨機網絡拓撲，然后利用基于SSFNet[6]仿真實現的OSPF協議進行網絡仿真。算法的各參數選取如下：P=1000，Ls=2000，Lr=750，Ts=15分鐘，Tr=15分鐘，Md=6000，Ml=2。仿真持續時間為120分鐘，其中每隔10分鐘，隨機選取3對鏈路，在其間產生抖動（通過通斷其間的鏈路來實現）。為避開MinLsInterval定時器，以便模擬OSPF里最壞情況下的路由振蕩抑制，通斷間隔定為7秒，2秒正常5秒斷開，持續35秒。

圖1給出了原OSPF路由振蕩抑制算法和加入懲罰機制后的路由振蕩抑制算法的仿真場景下，LSA的平均更新數量。從圖中可以看出，在該參數下的仿真里，改進后的算法比原OSPF算法減少了約34%的LSA更新數量。

5 結語

本文針對OSPF的域內穩定性問題，提出一種基于懲罰機制的路由振蕩抑制算法。通過記錄歷史振蕩行為并進行懲罰來抑制不穩定鏈路，屏蔽振蕩源。仿真實驗表明，算法簡單可行，能大大降低振蕩時網絡中LSA的洪泛數量，提高網絡穩定性。

[1]Ohara Y, Bhatia M, Osamu N, et al. Route flapping effects on OSPF [A]. Proceedings of2003 Symposium on Applications and the Internet Workshops [C]. Orlando,USA: IEEE Computer Society,2003.232～237.

[2]IETF RFC2439. BGP Route Flap Damping [S].

[3]Wang F, Chen S. Z, Li X, et al. A Route Flap Suppression Mechanism Based on Dynamic Timers in OSPF Network.

[4]IETF RFC2328, OSPF version2[S].

[5]Medina A., Lakhina A, Mattal, et al. Brite: boston university representative internet topology generator [EB/OL]. (2004～03)[2008-10-26]. http:∥www.cs.bu.edu/brite.

[6]SSFNet. Scalable simulation framework for networkmodels [EB/OL]. (2003～05) [2008-10-26]. http:∥www.ssfnet.org.

OSPF，BGP OSPF Route Flapping Suppressed Algorithm Based on Punishment Mechanism

Liu Song Ma Lin Liu Fuqiang Naval Academy of Armament, Beijing,100036

Rout Flapping has become more and more serious as a factor on influencing the quality of service in toady’s internet. Aimed at solving the problem, this paper comes up with a Route Flapping Suppression Arithmetic which is fit for the Open Shortest Path First (OSPF). Absorbing the Rout Flapping Suppression mechanism from BGP, introducing the concept of punishment, plus combing the characteristics of the OSPF, the arithmetic method makes the rout flapping suppression shift to link flapping suppression of the neighboring routers. Analogue simulation has demonstrated that the arithmetic helps to improve the stability of the internet by shielding the oscillating link to reduce the number of the LSA appeared in the internet.

10.3969/j.issn.1001-8972.2012.07.019

劉嵩，男，（1974-），遼寧沈陽人，海軍裝備研究院，高級工程師，碩士，主要研究方向為網絡及網絡安全。

馬琳，女，（1974-），河北唐山人，海軍裝備研究院，高級工程師，碩士，主要研究方向為網絡及網絡安全。

劉福強，男，（1976-），遼寧鞍山人，海軍裝備研究院，工程師，碩士，主要研究方向為網絡及網絡安全。