劉嵩 馬琳 劉福強(qiáng) 海軍裝備研究院,北京 100036

基于懲罰機(jī)制的OSPF路由振蕩抑制算法

劉嵩 馬琳 劉福強(qiáng) 海軍裝備研究院,北京 100036

在當(dāng)今的互聯(lián)網(wǎng)中，路由振蕩越來(lái)越成為影響網(wǎng)絡(luò)服務(wù)質(zhì)量的重大因素。為了解決此問(wèn)題，提出了一種適用于開(kāi)放式最短路徑優(yōu)先協(xié)議(OSPF)的路由振蕩抑制算法。該算法借鑒邊界網(wǎng)關(guān)協(xié)議(BGP)中的路由振蕩抑制機(jī)制，引入懲罰值的概念，并結(jié)合OSPF的特點(diǎn)，將路由振蕩抑制轉(zhuǎn)化為相鄰路由器之間的鏈路振蕩抑制。仿真模擬顯示，本算法可以有效地屏蔽振蕩中的鏈路，大大減少了網(wǎng)絡(luò)中LSA的產(chǎn)生數(shù)量，增加了網(wǎng)絡(luò)的穩(wěn)定性。

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

route flapping；link flapping；suppress；OSPF；BGP

路由表中的路由條目間斷性的消失和再現(xiàn)的現(xiàn)象，稱(chēng)為路由振蕩。路由振蕩會(huì)導(dǎo)致路由器在互聯(lián)網(wǎng)內(nèi)周期性的更新、洪泛的更新或撤銷(xiāo)鏈路消息，占用大量的網(wǎng)絡(luò)帶寬，同時(shí)不斷的鏈路狀態(tài)更新會(huì)引起頻繁的最短路徑優(yōu)先路由重計(jì)算，加重CPU的負(fù)荷，嚴(yán)重時(shí)引起錯(cuò)誤的路由重計(jì)算，導(dǎo)致大量丟包。

OSPF是一種專(zhuān)門(mén)為IP網(wǎng)絡(luò)開(kāi)發(fā)且廣泛應(yīng)用在單一自治系統(tǒng)內(nèi)的路由協(xié)議，目前已成為事實(shí)上的域內(nèi)路由協(xié)議標(biāo)準(zhǔn)?，F(xiàn)有的OSPF中并無(wú)可靠的路由振蕩抑制機(jī)制，而主要依靠若干定時(shí)器來(lái)削弱路由振蕩帶來(lái)的影響。如思科公司的路由產(chǎn)品在RFC2328標(biāo)準(zhǔn)外額外定義了延緩路由重計(jì)算的定時(shí)器SPFDelay，以減少路由振蕩時(shí)的最短路徑重計(jì)算。但這延長(zhǎng)了收斂過(guò)程，易引起錯(cuò)誤的路由重計(jì)算，極端情況下甚至適得其反。而且無(wú)法真正屏蔽路由振蕩源，是一種消極的手段[1]。

域間路由協(xié)議BGP中基于懲罰機(jī)制的路由振蕩抑制機(jī)制，在實(shí)踐中被證明是行之有效的[2]。但OSPF是鏈路狀態(tài)協(xié)議，BGP是距離矢量協(xié)議，這個(gè)根本不同點(diǎn)使BGP的路由振蕩抑制算法無(wú)法直接應(yīng)用在OSPF協(xié)議中。本文通過(guò)分析OSPF協(xié)議的特點(diǎn)，將路由振蕩避免轉(zhuǎn)化為鏈路振蕩避免[3]。對(duì)不穩(wěn)定鏈路進(jìn)行懲罰，從而較好的改善網(wǎng)絡(luò)性能。

1 OSPF原理

OSPF是一種分布式的鏈路狀態(tài)協(xié)議（link state protocol）[4]，每個(gè)路由器向外通告與本路由器相鄰的所有路由器的鏈路狀態(tài)，最終所有的路由器都建立一個(gè)全網(wǎng)統(tǒng)一的鏈路狀態(tài)數(shù)據(jù)庫(kù)（link state database），這個(gè)數(shù)據(jù)庫(kù)實(shí)際上就是全網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖。每一個(gè)路由器根據(jù)收斂后的鏈路狀態(tài)數(shù)據(jù)庫(kù)，以自己為起點(diǎn)，采用最短路徑優(yōu)先算法計(jì)算與目的節(jié)點(diǎn)之間的最佳路由，獨(dú)立的構(gòu)造出自己的路由表。

OSPF鏈路狀態(tài)信息通過(guò)鏈路狀態(tài)廣播LSA（link state advertisement）表示，包括路由器ID、接口IP地址和相鄰接口的IP地址、鏈路代價(jià)、序列號(hào)、年齡和校驗(yàn)和等內(nèi)容。有多種LSA，用來(lái)描述不同的對(duì)象。其中路由器LSA最為重要，用來(lái)表示該路由器的各個(gè)端口所連接的對(duì)象和代價(jià)等信息。

路由器啟動(dòng)后，通過(guò)接口向外組播Hello分組，用以探測(cè)鄰居，并開(kāi)始建立鄰接關(guān)系。經(jīng)過(guò)確認(rèn)主從關(guān)系、交換鏈路數(shù)據(jù)庫(kù)摘要、請(qǐng)求新的LSA、發(fā)送和確認(rèn)LSA等階段后，鏈路狀態(tài)數(shù)據(jù)庫(kù)將完全一致，即達(dá)到完全鄰接狀態(tài)（Full Adjacent）。當(dāng)鏈路狀態(tài)改變或鏈路刷新時(shí)間到，路由器就更新和擴(kuò)散LSA，同時(shí)接收其它節(jié)點(diǎn)洪泛的LSA，以保持全網(wǎng)的鏈路狀態(tài)數(shù)據(jù)庫(kù)是最新的。

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

2 路由振蕩轉(zhuǎn)化為鏈路振蕩

圖1 LSA平均更新數(shù)量比較

與距離矢量路由協(xié)議不同的是，OSPF的鏈路狀態(tài)信息發(fā)送至全網(wǎng)，且僅發(fā)送與本路由器相鄰的路由器的鏈路狀態(tài)信息。當(dāng)某條鏈路狀態(tài)發(fā)生變化，該路由器就使用鏈路狀態(tài)更新分組，用洪泛法向全網(wǎng)更新鏈路狀態(tài)。該分組首先發(fā)送給相鄰路由器，相鄰路由器必須將接收到的分組再轉(zhuǎn)發(fā)給除分組來(lái)源外的所有與自身相鄰的路由器，如此反復(fù)。若收到相同的LSA的多個(gè)實(shí)例，將通過(guò)比較序列號(hào)、校驗(yàn)以及老化時(shí)間等參數(shù)判斷最新的LSA，并更新舊的LSA。

由此可見(jiàn)，OSPF雖然將鏈路狀態(tài)信息洪泛至全網(wǎng)，但鏈路信息首先被發(fā)送給相鄰的路由器，再通過(guò)相鄰路由器轉(zhuǎn)發(fā)出去。盡管域內(nèi)每個(gè)路由器都有全網(wǎng)的鏈路狀態(tài)數(shù)據(jù)庫(kù)，并能獲知網(wǎng)內(nèi)任意一條鏈路的變化，但它們互相之間傳遞信息卻是基于本地的鄰接關(guān)系。鏈路的更新信息只傳遞給鄰居，再由鄰居繼續(xù)轉(zhuǎn)發(fā)，而不會(huì)直接傳遞給域內(nèi)的其它路由器?；贠SPF的這一特點(diǎn)，我們可以將路由振蕩由目前的基于定時(shí)器的全網(wǎng)抑制轉(zhuǎn)化為對(duì)本地鏈路振蕩的抑制。對(duì)于處于振蕩中的鏈路，相鄰路由器將接收到的鏈路狀態(tài)信息屏蔽，不再繼續(xù)轉(zhuǎn)發(fā)，該鏈路狀態(tài)變化將只局限于與該路由器相鄰的路由器范圍內(nèi)，而不會(huì)波及全網(wǎng)。即每一個(gè)路由器都只處理與自己相鄰的路由器的鏈路變化。

3 基于懲罰機(jī)制的路由振蕩抑制算法

算法的核心思想是：鏈路的每一次振蕩都會(huì)被記錄為不良記錄，并增加一定的懲罰值，若懲罰值超過(guò)某個(gè)門(mén)限，該鏈路將會(huì)被抑制。被抑制的鏈路信息不會(huì)得到轉(zhuǎn)發(fā)，不會(huì)參加最短路徑重計(jì)算。鏈路穩(wěn)定下來(lái)以后，鏈路的懲罰值會(huì)隨時(shí)間慢慢減少，當(dāng)懲罰值減少到重用門(mén)限以下時(shí)，解除鏈路抑制。

對(duì)振蕩鏈路的抑制可能會(huì)影響網(wǎng)絡(luò)可達(dá)性和代價(jià)最小原則，因此應(yīng)設(shè)置一個(gè)最大鏈路抑制數(shù)。若被抑制的鏈路數(shù)量達(dá)到最大鏈路抑制數(shù)，則應(yīng)提前解除對(duì)當(dāng)前懲罰值最小的鏈路的抑制。下面描述詳細(xì)的算法。

算法設(shè)置參數(shù)如下：

T：鏈路當(dāng)前懲罰值的累計(jì)總額，初始值為0。

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

H：鏈路當(dāng)前的狀態(tài)，0表示未被抑制，1表示已經(jīng)被抑制。

Ls：抑制門(mén)限，鏈路懲罰值超過(guò)抑制門(mén)限時(shí)將被抑制。

Lr：重用門(mén)限，處于被抑制狀態(tài)的鏈路的懲罰值降到重用門(mén)限或以下時(shí)，將被解除抑制。

Ts：鏈路處于被抑制狀態(tài)且已經(jīng)穩(wěn)定時(shí)，懲罰值的衰減速率。每過(guò)一個(gè)Ts周期，鏈路的懲罰值減半。這里的穩(wěn)定是指一個(gè)Ts周期內(nèi)，鏈路沒(méi)有再次振蕩。

Tr：鏈路處于未被抑制狀態(tài)且已經(jīng)穩(wěn)定時(shí)，懲罰值的衰減速率。每過(guò)一個(gè)Tr周期，鏈路的懲罰值減少P。這里的穩(wěn)定是指一個(gè)Tr周期內(nèi)，鏈路沒(méi)有再次振蕩。

Tc：上次懲罰值進(jìn)行衰減的時(shí)間點(diǎn)。懲罰值的衰減并不是連續(xù)性的衰減，而是在一個(gè)衰減周期后直接減去一定值，因此需要記錄上一次衰減時(shí)的時(shí)間點(diǎn)。初始值為路由器剛啟動(dòng)的時(shí)間。

Md：最大抑制門(mén)限，每條鏈路的懲罰值T所能累積到的最大值。這是為了避免鏈路在短時(shí)間內(nèi)的急劇振蕩累積過(guò)高的懲罰值，導(dǎo)致鏈路在很長(zhǎng)時(shí)間內(nèi)都無(wú)法解除抑制。該值必須大于抑制門(mén)限，否則鏈路將永遠(yuǎn)不會(huì)被懲罰。

Cl：當(dāng)前被抑制的鏈路數(shù)量，初始為0。

Ml：最大鏈路抑制數(shù)，每個(gè)路由器同時(shí)可抑制的最大鏈路數(shù)。為了避免鏈路被抑制過(guò)多而影響網(wǎng)絡(luò)可達(dá)性，需限制路由器抑制鏈路數(shù)不大于Ml。

以上參數(shù)中除了說(shuō)明初始值的外，其它都可以自行設(shè)置。Ls和P的比值越大，表示可容忍的振蕩程度越高。Lr和Ls的比值越大，表示鏈路被抑制后的恢復(fù)時(shí)間越短。最大抑制門(mén)限Md應(yīng)該由重用門(mén)限Lr、鏈路在懲罰狀態(tài)時(shí)的衰減周期Ts和鏈路的最長(zhǎng)抑制時(shí)間計(jì)算出來(lái)。假設(shè)衰減周期Ts為30分鐘，鏈路的最長(zhǎng)抑制時(shí)間為1小時(shí)，重用門(mén)限Lr為1000，則最大抑制門(mén)限Md=4000，這樣才能保證在一個(gè)小時(shí)內(nèi)經(jīng)過(guò)兩個(gè)半衰期，懲罰值衰減到重用門(mén)限Lr以便鏈路解除抑制。

最重要的兩個(gè)參數(shù)是鏈路處于抑制狀態(tài)時(shí)的懲罰值衰減周期Ts和鏈路處于未抑制狀態(tài)時(shí)的懲罰值衰減周期Tr。Ts的值設(shè)置過(guò)小會(huì)導(dǎo)致鏈路可以迅速?gòu)谋灰种茽顟B(tài)恢復(fù)到正常狀態(tài)，若這個(gè)恢復(fù)周期比鏈路振蕩周期小，則算法起不到抑制振蕩的作用。Ts的值也不能過(guò)大，因?yàn)檫^(guò)大就意味著鏈路長(zhǎng)時(shí)間得不到恢復(fù)，即使鏈路已經(jīng)穩(wěn)定。對(duì)于Tr，它的值不應(yīng)該過(guò)小，過(guò)小就意味著懲罰值衰減得太快，在對(duì)鏈路進(jìn)行下一次懲罰時(shí)，可能前一次的懲罰值已經(jīng)被清除了，起不到懲罰的作用。

算法的具體實(shí)施步驟如下所示：

1）路由器進(jìn)行初始化，保存所有與自己相鄰的路由器的所有鏈路，并對(duì)鏈路進(jìn)行參數(shù)初始化。T=0，H=0，Cl=0，Tc為當(dāng)前時(shí)間。

2）每當(dāng)路由器檢測(cè)到相鄰路由器的某條鏈路產(chǎn)生振蕩，就給這條鏈路增加一個(gè)單位懲罰值即T=T+P，若T>Md，則T=Md，同時(shí)Tc置為當(dāng)前時(shí)間。若T>Ls，則令鏈路狀態(tài)H=1，表示鏈路已經(jīng)被抑制，路由器不再對(duì)外廣播該鏈路信息，Cl=Cl+1。

3）若Cl>Ml，查找一條當(dāng)前被抑制鏈路里最穩(wěn)定的鏈路，即T最小的鏈路，提前解除對(duì)這條鏈路的抑制，Cl=Cl-1，重復(fù)執(zhí)行該步驟直到不滿足Cl>Ml。

4）若鏈路處于未被抑制狀態(tài)下，檢查從Tc到現(xiàn)在是否已經(jīng)過(guò)了Tr時(shí)間。若是，懲罰值減去P即T=T-P。

5）若鏈路處于被抑制狀態(tài)下，檢查從Tc到現(xiàn)在是否已經(jīng)過(guò)了Ts時(shí)間。若是，將當(dāng)前懲罰值減半，即T=T/2。若T

4 仿真與性能分析

為了驗(yàn)證路由振蕩抑制算法的可行性和有效性，我們將采用相關(guān)的仿真軟件進(jìn)行仿真。仿真包括對(duì)原OSPF算法的仿真和改進(jìn)后算法的仿真，并對(duì)兩種算法進(jìn)行比較。路由振蕩最顯著的危害是頻繁的向外更新LSA，占用網(wǎng)絡(luò)帶寬，同時(shí)引起路由器的最短路徑重計(jì)算。因此將每個(gè)路由器的LSA更新數(shù)量作為本次仿真的對(duì)比指標(biāo)。

我們使用BRite[5]拓?fù)渖善鞲鶕?jù)Waxman算法生成一個(gè)具有128個(gè)節(jié)點(diǎn)260條鏈路的隨機(jī)網(wǎng)絡(luò)拓?fù)?，然后利用基于SSFNet[6]仿真實(shí)現(xiàn)的OSPF協(xié)議進(jìn)行網(wǎng)絡(luò)仿真。算法的各參數(shù)選取如下：P=1000，Ls=2000，Lr=750，Ts=15分鐘，Tr=15分鐘，Md=6000，Ml=2。仿真持續(xù)時(shí)間為120分鐘，其中每隔10分鐘，隨機(jī)選取3對(duì)鏈路，在其間產(chǎn)生抖動(dòng)（通過(guò)通斷其間的鏈路來(lái)實(shí)現(xiàn)）。為避開(kāi)MinLsInterval定時(shí)器，以便模擬OSPF里最壞情況下的路由振蕩抑制，通斷間隔定為7秒，2秒正常5秒斷開(kāi)，持續(xù)35秒。

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

5 結(jié)語(yǔ)

本文針對(duì)OSPF的域內(nèi)穩(wěn)定性問(wèn)題，提出一種基于懲罰機(jī)制的路由振蕩抑制算法。通過(guò)記錄歷史振蕩行為并進(jìn)行懲罰來(lái)抑制不穩(wěn)定鏈路，屏蔽振蕩源。仿真實(shí)驗(yàn)表明，算法簡(jiǎn)單可行，能大大降低振蕩時(shí)網(wǎng)絡(luò)中LSA的洪泛數(shù)量，提高網(wǎng)絡(luò)穩(wěn)定性。

[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-），遼寧沈陽(yáng)人，海軍裝備研究院，高級(jí)工程師，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)及網(wǎng)絡(luò)安全。

馬琳，女，（1974-），河北唐山人，海軍裝備研究院，高級(jí)工程師，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)及網(wǎng)絡(luò)安全。

劉福強(qiáng)，男，（1976-），遼寧鞍山人，海軍裝備研究院，工程師，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)及網(wǎng)絡(luò)安全。