基于SSFnet環(huán)境的BGP快速收斂方法研究

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

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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é)議中各個(gè)節(jié)點(diǎn)向它的相鄰節(jié)點(diǎn)廣播到目標(biāo)地址的最佳路由信息。因此路由器在網(wǎng)絡(luò)上通過該協(xié)議發(fā)送的UPDATE消息帶有目標(biāo)路徑信息。一個(gè)BGP節(jié)點(diǎn)存儲(chǔ)了發(fā)送到鄰居中節(jié)點(diǎn)的所有路徑，但僅使用和廣播那些對(duì)于某些標(biāo)準(zhǔn)來講最好的消息。如果這個(gè)首選的路徑失敗，那么BGP選擇下一個(gè)后備的最優(yōu)路由，這個(gè)路由會(huì)被廣播到它的鄰居節(jié)點(diǎn)，但不能保證這個(gè)后備的路由是有效的。為了防止這個(gè)后備的路由也是失敗的，它將在發(fā)送一個(gè)撤銷消息到它的鄰居后替換這個(gè)路由消息，然后其它的備份路由將被選擇。路由消息有效信息的缺乏導(dǎo)致 BGP在正確選擇前可能已經(jīng)選擇了大量的后備路由。BGP是網(wǎng)間路由協(xié)議的標(biāo)準(zhǔn)，使用的最普遍，因此在撤銷和公告周期中，所有BGP節(jié)點(diǎn)形成有效、穩(wěn)定的目標(biāo)路徑之前，這里可能有相當(dāng)大的延遲。最近的研究表明，節(jié)點(diǎn)發(fā)生故障后可能花費(fèi)3到15分鐘建立穩(wěn)定的路由。

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

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

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

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

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

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

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

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

2.2 BGP 快速收斂算法

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

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

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

3仿真驗(yàn)證實(shí)驗(yàn)

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

仿真結(jié)果：

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

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

（2） 鏈路故障的場景

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

4 結(jié)論

本文研究了一個(gè)基于消息分類BGP快速收斂機(jī)制，實(shí)驗(yàn)將消息在轉(zhuǎn)發(fā)過程中被按照狀態(tài)進(jìn)行分類，將處于“on-tree”狀態(tài)的消息設(shè)置較高優(yōu)先級(jí)和較小MRAI值；處于“off-tree”狀態(tài)的消息設(shè)置較低優(yōu)先級(jí)和較大的MRAI值。采用SSFNet仿真工具進(jìn)行了模擬實(shí)驗(yàn)，結(jié)果表明該機(jī)制與默認(rèn)BGP協(xié)議、Ghost flushing機(jī)制相比具有更小的BGP收斂時(shí)間。它具有與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ì)算機(jī)應(yīng)用研究，2011（9）：3481-3484.

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

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

[5] 郭輝，常晉義.邊界網(wǎng)關(guān)協(xié)議收斂問題研究綜述[J]. 計(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.