吳學(xué)會　祁建松　鄭超　呂思思

摘要：BGP協(xié)議是網(wǎng)絡(luò)中最流行的域間路由協(xié)議之一，其具有路由控制機(jī)制豐富、穩(wěn)定、安全的特點。BGP協(xié)議中路由選擇受從相鄰路由發(fā)出的UPDATE消息影響，由于AS選擇各自的路由策略，這可能會導(dǎo)致收斂時間過長，丟失AS的數(shù)據(jù)包。采用調(diào)整MRAI定時器值的方式能實現(xiàn)減少收斂時間的效果，但也會帶來如廣播風(fēng)暴這樣的危害。該文提出了一種基于壞消息傳的緩慢而好消息傳播快的BGP快速收斂機(jī)制，通過修改不同類別消息的定時器值實現(xiàn)快速收斂。通過SSFnt工具仿真驗證了該機(jī)制可以大幅減少收斂時間并在一定程度上減少冗余數(shù)據(jù)包的結(jié)論。

關(guān) 鍵 詞：BGP；路由協(xié)議；快速收斂；SSFnet工具

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）14-0047-03

Abstract： The BGP protocol is the most popular protocol in the inter-domain routing， it has plenty of routing control mechanisms， to provide a stable and secure scheme. The attribute information of BGP routing depends on UPDATE messages received from the adjacent routing contained in the AS. It allows each AS routing strategy， which may lead to the convergence time is too long， the loss of AS packets. By modifying the MRAI timer value can reduce the convergence time in a certain extent， but also may have a negative impact on the broadcast storm. In this paper， we proposed a BGP fast convergence mechanism by modifying the timer depending on the message type based on the concept that the bad news travels slowly while the good news travels quickly in the Internet. By simulating our mechanism on the SSFnt， it draw the conclusion that it can greatly reduce the convergence time， as well as reducing the redundant packets to some extent.

Key words： BGP； routing protocol； fast convergence； SSFnet

1 引言

目前BGP協(xié)議是互聯(lián)網(wǎng)上標(biāo)準(zhǔn)的域間路由協(xié)議，它在網(wǎng)絡(luò)性能上扮演著重要的角色。該協(xié)議是路徑向量協(xié)議，該協(xié)議中各個節(jié)點向它的相鄰節(jié)點廣播到目標(biāo)地址的最佳路由信息。因此路由器在網(wǎng)絡(luò)上通過該協(xié)議發(fā)送的UPDATE消息帶有目標(biāo)路徑信息。一個BGP節(jié)點存儲了發(fā)送到鄰居中節(jié)點的所有路徑，但僅使用和廣播那些對于某些標(biāo)準(zhǔn)來講最好的消息。如果這個首選的路徑失敗，那么BGP選擇下一個后備的最優(yōu)路由，這個路由會被廣播到它的鄰居節(jié)點，但不能保證這個后備的路由是有效的。為了防止這個后備的路由也是失敗的，它將在發(fā)送一個撤銷消息到它的鄰居后替換這個路由消息，然后其它的備份路由將被選擇。路由消息有效信息的缺乏導(dǎo)致 BGP在正確選擇前可能已經(jīng)選擇了大量的后備路由。BGP是網(wǎng)間路由協(xié)議的標(biāo)準(zhǔn)，使用的最普遍，因此在撤銷和公告周期中，所有BGP節(jié)點形成有效、穩(wěn)定的目標(biāo)路徑之前，這里可能有相當(dāng)大的延遲。最近的研究表明，節(jié)點發(fā)生故障后可能花費(fèi)3到15分鐘建立穩(wěn)定的路由。

2基于消息分類的BGP收斂方法

本文提出一個簡單的機(jī)制：通過對BGP的UPDATE消息分類和修改相應(yīng)的定時器值來實現(xiàn)緩解路由器的負(fù)擔(dān)和減少BGP收斂的時間。

2.1消息優(yōu)先級分類

在方案中設(shè)置MARI定時器值的前提是對BGP的UPDATE消息進(jìn)行優(yōu)先級劃分。從BGP消息接收器角度來看，如果BGP消息的目的地址是一個新地址，那么它對應(yīng)較高的優(yōu)先級。反之，它的優(yōu)先級由UPDATE消息的狀態(tài)是“on-tree”還是“off-tree”來決定。如果接收到的UPDATE消息是沿轉(zhuǎn)發(fā)樹的樹干發(fā)送的那么它是“on-tree”狀態(tài)，否則是在“off-tree”狀態(tài)。在BGP路由協(xié)議中，子樹節(jié)點知道它的父節(jié)點數(shù)據(jù)，但它的父節(jié)點不保存子節(jié)點的數(shù)據(jù)。因為處于“on-tree”狀態(tài)的UPDATE消息可以立刻做出路由決策，因此它具有更高的優(yōu)先級。

若UPDATE消息是撤回消息且為“on-tree”的狀態(tài)，這說明前期刪除的路徑被使用，也表明這個路徑是非常重要，應(yīng)該具有更高的優(yōu)先級。相反，表明刪除的路徑是一個可替代的路徑，先前沒有被使用過，所以應(yīng)該對應(yīng)到一個較低的優(yōu)先級。如果UPDATE消息是一個“on-tree”狀態(tài)的消息，這意味著有一個新的路徑，可以替代先前通告的路徑，這是一個好消息，它應(yīng)該具有更高的優(yōu)先級。如果UPDATE消息是一個“off-tree”狀態(tài)，但比路徑通告路徑更好，即它是一個更短的路徑，應(yīng)該有更高的優(yōu)先權(quán)，否則，它應(yīng)該有低優(yōu)先級。

對于通告消息的特別處理：對于相同目標(biāo)，如果通告路徑比前一個長，那么它是在收斂時間內(nèi)產(chǎn)生的無效信息。為了刪除網(wǎng)絡(luò)中的該信息從而實現(xiàn)加快BGP收斂的目的，需要通知其它BGP路由先前通告的路徑不再有效。即對于通告的消息，不管是 “on-tree”或“off-tree”狀態(tài)，只要存在同一目的地址的路徑較長的情況，就說明在網(wǎng)絡(luò)中存在無效信息。在這種情況下，消息應(yīng)該具有更高的優(yōu)先級，節(jié)點需要向目標(biāo)地址發(fā)送撤銷消息，聲明到達(dá)目標(biāo)的先前路徑是有效的。消息分類后，還需要通過以下兩種方法進(jìn)一步處理：

1）從接收端設(shè)置隊列優(yōu)先級：實現(xiàn)接收端對UPDATE消息的分類，最簡單的方法是對消息設(shè)置不同的優(yōu)先級。優(yōu)點在于是通過轉(zhuǎn)發(fā)表的檢查容易判斷消息的優(yōu)先級。然而，接收機(jī)需要事先做大量的處理工作，從而提高接收機(jī)的負(fù)擔(dān)。

2）從發(fā)送端設(shè)置隊列優(yōu)先級：發(fā)送端為帶有不同優(yōu)先級的消息設(shè)置不同的延時時間。使用BGP協(xié)議作為默認(rèn)定時器值的消息設(shè)置較低優(yōu)先級。定時器值較小的消息，則為它設(shè)置較高的優(yōu)先級。該方式的優(yōu)勢在于可以減少BGP的收斂時間，只需要修改MRAL值就可以實現(xiàn)UPDATE消息在每一跳的時間較短。同時，利用該方法可以在相同時間內(nèi)加快BGP收斂。

2.2 BGP 快速收斂算法

通過BGP的 UPDATE消息分類而進(jìn)一步設(shè)置消息的優(yōu)先級，實現(xiàn)快速收斂。如圖2所示，該算法在BGP消息的發(fā)送端實現(xiàn)，高優(yōu)先級的消息被直接發(fā)送，而低優(yōu)先級的消息將被延遲發(fā)送。為加快使BGP收斂，低優(yōu)先級消息的MRAI值設(shè)置為BGP協(xié)議的默認(rèn)值，高優(yōu)先級的MRAI設(shè)置為標(biāo)準(zhǔn)值的一半。

一個UPDATE消息發(fā)送時，需要檢查消息類型，若是一個處于“on-tree”狀態(tài)的撤回消息，則表明被刪除的路徑是轉(zhuǎn)發(fā)樹的一個分支，為達(dá)到加快BGP收斂目的，因此使用較小的MRAI定時器值發(fā)送；若是“off-tree”的狀態(tài)，說明該路徑從沒有被使用過，推遲它不會影響目前路徑的使用，因此這個撤銷消息會被更晚發(fā)送從而實現(xiàn)降低BGP收斂處理過程中產(chǎn)生的消耗。

當(dāng)一個通告消息發(fā)送，需要對通告的目標(biāo)地址的新舊進(jìn)行檢驗：若是新的地址，說明存在一個新的路徑消息，這是好消息，需要設(shè)置較高的優(yōu)先級；若是舊目標(biāo)地址，并通告的路徑比前一個更好，也就是說比前一個更短，那么這個通告消息應(yīng)該具有更高的優(yōu)先級。但若通告的路徑比以前的更長，說明有無效路徑信息存在，為了快速刪除這些消息，無論定時器是否超時該消息都需要立即發(fā)送，并且發(fā)送者需要將目的地的路徑設(shè)置為空。當(dāng)接收到一個新的目標(biāo)路徑，因為不存在比空路徑更短的路徑，所以可以立即發(fā)布通告。該方式降低了網(wǎng)絡(luò)中無效的消息和BGP收斂時間。

3仿真驗證實驗

通過SSFnet工具完成仿真，對生成一個新的路由和鏈路失效的路由兩種情況進(jìn)行測試。在每一個場景中，對ENCT、AENCT和 NEUM三個參數(shù)進(jìn)行分析。

仿真結(jié)果：

（1）產(chǎn)生新路由的場景

在這種場景下測試了ENCT， AENCT， NEUM三個參數(shù)。測試節(jié)點的各個參數(shù)如表1所示。

（2） 鏈路故障的場景

在這種情況下，除了比較默認(rèn)BGP和默認(rèn)BGP MRAI 15算法的三參數(shù)，也與目前的BGP路由收斂算法ghost flushing和Root-Cause進(jìn)行了比較。在比較中將默認(rèn)BGP的MRAI定時器分別為30和15，Root-Cause的MRAI定時器為15。在每種拓?fù)浣Y(jié)構(gòu)，選擇一個隨機(jī)的節(jié)點與鄰居節(jié)點的路由，并且這個節(jié)點廣播到達(dá)鄰居的目標(biāo)地址，該地址帶有網(wǎng)絡(luò)前綴信息。實驗將測試網(wǎng)絡(luò)收斂達(dá)到穩(wěn)定狀態(tài)時切斷與某個相鄰節(jié)點間鏈路，觀察該算法與其他算法的性能變化情況。

4 結(jié)論

本文研究了一個基于消息分類BGP快速收斂機(jī)制，實驗將消息在轉(zhuǎn)發(fā)過程中被按照狀態(tài)進(jìn)行分類，將處于“on-tree”狀態(tài)的消息設(shè)置較高優(yōu)先級和較小MRAI值；處于“off-tree”狀態(tài)的消息設(shè)置較低優(yōu)先級和較大的MRAI值。采用SSFNet仿真工具進(jìn)行了模擬實驗，結(jié)果表明該機(jī)制與默認(rèn)BGP協(xié)議、Ghost flushing機(jī)制相比具有更小的BGP收斂時間。它具有與RNC機(jī)制類似的性能，且與其它機(jī)制相比較產(chǎn)生較少的UPDATE消息。

參考文獻(xiàn)：

[1] 汪小滟.芻議BGP/VPN快速收斂技術(shù)[J]. 中國新技術(shù)新產(chǎn)品，2011（2）：40.

[2] 胡字瀅，張濤. 基于路由更新鏈的BGP收斂性改進(jìn)機(jī)制[J]. 計算機(jī)應(yīng)用研究，2011（9）：3481-3484.

[3] 趙金晶，朱培棟，盧錫城. BGP收斂性及其對網(wǎng)絡(luò)性能影響的定量分析[J]. 通信學(xué)報，2007（8）：24-33.

[4] 趙金晶，朱培棟，周麗濤. 域間路由協(xié)議BGP收斂時間的定量分析及預(yù)測[J]. 計算機(jī)工程與科學(xué)，2007（9）：56-57+63.

[5] 郭輝，常晉義.邊界網(wǎng)關(guān)協(xié)議收斂問題研究綜述[J]. 計算機(jī)應(yīng)用，2010（10）：2628-2631.

[6] Dan Pei， Zhang B.An analysis of convergence delay in path vector routing protocols[J]. Computer Networks， 2006，30（3）：398–421.

[7] Villamizar C， Chandra R， Govindan R. BGP route flap damping[S].RFC 2439，November 1998.

[8] Griffin T G， Premore B J.An experimental analysis of BGP convergence time[J]. Proc. ICNP 2001， Riverside， California， 2001，11–14：53–61.

[9] Gao L. and Rexford J. Stable Internet routing without global coordination[J].IEE E /A CM Transactions on Networking，2001，9（6）：681-692.