一種加快BGP收斂的方法

☆ 王開遠(yuǎn)

（吉林師范大學(xué)，吉林四平 136000）

一、引言

現(xiàn)行Internet由分屬于不同管理部門的路由域組成，這些路由域被稱為自治系統(tǒng)（AS，Autonomous System）。AS之間通過域間路由協(xié)議交換路由信息，也就是BGP（Border Getway Protocol）協(xié)議。BGP協(xié)議是目前運(yùn)行于Internet上唯一的域間路由協(xié)議。BGP協(xié)議根據(jù)自治系統(tǒng)本身所制定的路由策略來選擇到達(dá)目的網(wǎng)絡(luò)的路徑，然而這些路徑并不穩(wěn)定，事實上Internet每天都會產(chǎn)生幾十萬條的UPDATE消息需要BGP協(xié)議處理。研究表明，路由策略不一致會導(dǎo)致BGP發(fā)散，產(chǎn)生路由震蕩。并且由于BGP協(xié)議屬于路徑向量協(xié)議，收斂慢是它的一個主要缺點(diǎn)，通常收斂時間需要數(shù)十分鐘，甚至數(shù)小時，對網(wǎng)絡(luò)的穩(wěn)定性影響巨大。BGP路由收斂性問題正逐漸引起人們的關(guān)注。隨著Internet規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的復(fù)雜化，這一問題變得日趨嚴(yán)重，同時，域間路由收斂性問題也是下一代Internet所必須研究的內(nèi)容之一。在這樣的背景下對于BGP收斂性的研究變得尤為重要。

二、無拖延反向毒化和環(huán)路檢測方法

本文提出一種提高BGP的收斂速度的方法，由無拖延反向毒化（NDPR，Non－Delay Poison Reverse）和環(huán)路檢測（ALP，Anti－Loop Probing）兩部分組成，這種方法以較少的傳輸和存儲代價通過及時地排除種種影響路徑探索速度的原因，來達(dá)到加快BGP收斂速度的目的。

1．無拖延反向毒化（NDPR）

BGP在運(yùn)行過程中，各對等體間更新信息的傳遞都要受到MRAI的限制，由于這種限制經(jīng)常會導(dǎo)致對等體相互認(rèn)為對方是到達(dá)某一目的地的下一跳，并且在一段時間內(nèi)都無法察覺，這使BGP的收斂速度受到很大影響。為了避免這一情況的產(chǎn)生提出了NDPR。

借鑒RIP的反向毒化思想，根據(jù)BGP的運(yùn)行特點(diǎn)，對BGP的更新消息以及撤銷消息的發(fā)送機(jī)制進(jìn)行如下改動：如果有關(guān)某一目的地的路由選擇發(fā)生消極變化，而由于距離上次更新公告的時間過近被MRAI限制，本次的更新公告無法馬上發(fā)送給下一跳，那么，就向下一跳發(fā)送取消去往該目的地的路由消息，由于MRAI并不限制取消路由的消息，所以，這條取消消息可以瞬時發(fā)出。這樣設(shè)置的想法是，當(dāng)路由變差時便會有路徑探索發(fā)生，在探索過程中的每一條更新消息都應(yīng)該立刻告知下一跳的節(jié)點(diǎn)，在消息正常發(fā)送的情況下，其狀況與正常的BGP沒有區(qū)別，包含在路徑中的AS號可以避免下一跳的路由器選擇自己的上一跳作為可用的路由；當(dāng)更新消息受到MRAI的限制而無法發(fā)送時，就把發(fā)送的更新路由消息改為取消本路由的消息發(fā)送給下一跳，取消路由的消息不受MRAI的影響。以這種形式，NDPR降低了路徑探索的復(fù)雜度提高了收斂速度。

對于不受限制的路由撤銷消息可能存在的消息泛濫問題，由于BGP的消息發(fā)送機(jī)制，一條撤銷消息一定會對應(yīng)之前發(fā)送的一個宣告消息，使得兩次撤銷消息發(fā)送的中間必定會有一條宣告消息，而宣告消息是受到MRAI的限制的，這就是說，撤銷消息的發(fā)送最多與宣告消息數(shù)量相同而永不會多于宣告消息。這種方式的優(yōu)點(diǎn)在于對之前所發(fā)的宣告可以隨時取消。

原本的BGP中，撤銷消息的發(fā)送只有在節(jié)點(diǎn)無法重新找到到達(dá)某一目的地的最優(yōu)路由即rib（n，p）＝null時才會被發(fā)送。與BGP－GF相比，兩者都對撤銷消息的發(fā)送機(jī)制作了改變，改變了兩個連續(xù)消息的發(fā)送機(jī)制，其不同點(diǎn)在于反向毒化（Poison Reverse）和路由毒化（Route Poisoning）之間的區(qū)別。如圖1所示，當(dāng)A處有兩條連續(xù)的消息發(fā)送給B處時，NDPR會將第二條消息以撤銷消息的形式發(fā)出，也就是說，只有當(dāng)B是新路由的下一跳時這種情況才會發(fā)生，相當(dāng)于通知B，他所宣告的路由已被A所采納。BGP－GF則是在這兩條消息中插進(jìn)一條撤銷消息，其第二條消息宣告依然在發(fā)送消息隊列中等待MRAI到期然后發(fā)送出去，這種方式可以對任何鄰居使用，就是告知鄰居本地的路由已經(jīng)發(fā)生變化，之前所通告的路由宣布作廢，當(dāng)MRAI到期后會告知新的路由選擇。相比之下NDPR的方式更加溫和，根據(jù)下一跳的改變逐一發(fā)送撤銷消息，并且撤銷消息由宣告消息變換得到不需額外添加。

圖 1 BGP,NDPR,BGP－GF區(qū)別

在開源軟件Zebra中，在發(fā)生路由變化時就向新的下一跳發(fā)送撤銷路由的消息。實際上反向毒化的使用如果不受限制是有其缺陷的。由于BGP的抖動阻尼機(jī)制，當(dāng)節(jié)點(diǎn)收到取消路由的消息時會對其發(fā)送方的懲罰值增加，當(dāng)罰值增加到一定程度時會忽略發(fā)送端所發(fā)送的路由消息一段時間。這樣考慮當(dāng)路由改善MRAI未發(fā)生作用的情況下，標(biāo)準(zhǔn)的BGP機(jī)制是具有積極意義的。

2．環(huán)路檢測方法

NDPR解決了AS間選路錯誤的問題，可針對路由環(huán)路NDPR沒有起到作用。針對這一問題這里提出一種解決方法。網(wǎng)絡(luò)故障可分為兩種:一種為某一節(jié)點(diǎn)失去某一目的地的可達(dá)性，即故障中斷（fail－down）；另一種是該節(jié)點(diǎn)存在另一條通路并最終向路由選擇為此條通路的過程，即故障轉(zhuǎn)移（fail－over）。文章篇幅限制，這里只針對故障中斷下的環(huán)路檢測方法作詳細(xì)描述。

此種情況比較簡單，在受到影響的節(jié)點(diǎn)集合V＇中的任意節(jié)點(diǎn)n，網(wǎng)絡(luò)前綴p的所有者n0 path（n，p），在這里只有當(dāng)他處于一個環(huán)中的時候才會使路徑探索停滯。環(huán)路檢測思想是加入一種新的BGP消息，以盡快探測和破除瞬時環(huán)來加快路徑探索過程，這條消息格式十分簡單，其內(nèi)容包括目的網(wǎng)絡(luò)的網(wǎng)絡(luò)前綴p和一條曾經(jīng)到達(dá)過網(wǎng)絡(luò)p的AS路徑。在消息處理上也十分簡單，因為他不是一條路由宣告，只是一條測試消息，不會觸發(fā)決策過程。

其檢測過程為：由某一節(jié)點(diǎn)開始發(fā)送檢測消息，在AS路徑字段中添加自己的AS號，并將添加有自己AS號的消息再傳遞給下一跳，當(dāng)下一跳接到這條檢測信息就會查看信息中是否有自己的AS號，若沒有就在這條信息中添加進(jìn)自己的AS號并傳遞給他的下一跳。如果有就說明此時有環(huán)路存在，檢測到有自己AS號的節(jié)點(diǎn)就會將檢測信息的發(fā)送方的路由毒化，保留待發(fā)消息隊列里的信息，立即回復(fù)一個撤銷路由的信息使環(huán)路被破壞，路徑探索過程繼續(xù)，最終達(dá)到網(wǎng)絡(luò)收斂。

以下舉例說明：如圖2，由三個節(jié)點(diǎn)1、2、3構(gòu)成的瞬時環(huán)，箭頭方向代表各節(jié)點(diǎn)的路由選擇，此時，破環(huán)探測由節(jié)點(diǎn)1發(fā)出，節(jié)點(diǎn)2收到此條探測消息并檢測其中并不含有自己的AS號，就在該消息中添加自己的AS號并將該消息傳遞給節(jié)點(diǎn)3，在節(jié)點(diǎn)3處與節(jié)點(diǎn)2處類似將自己的AS號加入消息后節(jié)點(diǎn)3將此條探測信息又發(fā)給了節(jié)點(diǎn)1，節(jié)點(diǎn)1在檢測消息時發(fā)現(xiàn)其中包含自己的AS號，就立刻發(fā)送取消路由的消息給節(jié)點(diǎn)3,此時環(huán)路被破壞。

圖2 環(huán)路檢測舉例

理想情況下，這樣的環(huán)路探測由環(huán)路當(dāng)中的一個節(jié)點(diǎn)發(fā)起即可，但在實際使用中探測的發(fā)起應(yīng)該由什么樣的節(jié)點(diǎn)來承擔(dān)就成了節(jié)省網(wǎng)絡(luò)資源的重要問題。在不可預(yù)測的網(wǎng)絡(luò)拓?fù)渲?，無可避免的會產(chǎn)生冗余檢測，采取一定措施來減少這種網(wǎng)絡(luò)資源的浪費(fèi)是必要的。當(dāng)某一節(jié)點(diǎn)到達(dá)某一目的地的路由變差而需要改變其下一跳時，就有可能產(chǎn)生瞬時環(huán)。這樣的臨時結(jié)構(gòu)只有在非末端節(jié)點(diǎn)中檢測才是有意義的，因為，只有一個入度的末端節(jié)點(diǎn)是不可能被包含在一個環(huán)中的。所以，只有在發(fā)生路由變差的中繼節(jié)點(diǎn)才有資格發(fā)起探測信息，并且只有其所選路由持續(xù)變差，下一跳地址持續(xù)改變時，才發(fā)起環(huán)路檢測。

由于在收斂過程中，鏈路上的各個節(jié)點(diǎn)的路由選擇都在不停地變化，當(dāng)一次檢測進(jìn)行時，不能保證進(jìn)行的過程中，由于某些節(jié)點(diǎn)不改變路由而使得所探測的路徑并不是探測開始時所期望的那條。這樣就會產(chǎn)生錯誤的環(huán)路信息，并引起一次不必要的路由毒化。雖然這種情況并不影響網(wǎng)絡(luò)的收斂，但會影響網(wǎng)絡(luò)資源的利用率。考慮到這一點(diǎn)，發(fā)起探測的時機(jī)不應(yīng)該是當(dāng)條件滿足時立刻發(fā)起，而應(yīng)該稍等一段時間，給系統(tǒng)穩(wěn)定留下余地，再發(fā)起探測。但是，這種方式對于破環(huán)的效率就會產(chǎn)生不利影響。針對這種矛盾的狀況，環(huán)路檢測方法所采取的方式是一種折中的辦法，設(shè)置一個定時機(jī)制，當(dāng)條件滿足后等待一個時間T，超過時間T后才開始發(fā)起探測。在收斂過程的前T時間不發(fā)生破環(huán)探測，依靠NDPR盡量多地減少無效路由信息，來降低破環(huán)檢測時的復(fù)雜度。當(dāng)定時到期前有探測消息到達(dá)就將計時清除，這樣來避免重復(fù)探測。而從鄰居處傳來的探測消息則必須轉(zhuǎn)發(fā)下去不能放棄。探測發(fā)起后，包括發(fā)起探測的節(jié)點(diǎn)都將進(jìn)入強(qiáng)制探測狀態(tài)，處于強(qiáng)制探測狀態(tài)下的節(jié)點(diǎn)在下一條發(fā)生變化時就會發(fā)起一個新探測，這樣提高了效率也保證了每個瞬時環(huán)能夠被及時破壞。如圖2當(dāng)節(jié)點(diǎn)1收到撤銷路由的信息，并撤銷掉路由以后，新的路由環(huán)仍可能產(chǎn)生，而在節(jié)點(diǎn)3處，由于收到節(jié)點(diǎn)1的撤銷消息改變了下一跳，使得節(jié)點(diǎn)3處的環(huán)路探測被觸發(fā)，這樣保證了新的環(huán)路也能夠被及時地發(fā)現(xiàn)并排除。強(qiáng)制探測的狀態(tài)將在MRAI到期后被取消。

三、仿真結(jié)果

仿真結(jié)果顯示，NDPR和環(huán)路檢測方法在收斂時間和消息復(fù)雜度上比較標(biāo)準(zhǔn)的BGP都要更加優(yōu)越，由于BGP冗長的計數(shù)過程，在網(wǎng)絡(luò)尺寸不斷增加時，其收斂時間隨之線性變化。再加之每個MRAI都會伴隨一次偽信息的散播。使得消息復(fù)雜度也隨之增加。這當(dāng)中NDPR和環(huán)路檢測方法及時去除掉了系統(tǒng)中的偽信息，對收斂性能的提高起到了很大作用，但仍然遜于BGP－GF。

采用廣播撤銷消息的BGP－GF在故障中斷情況下沒有受到網(wǎng)絡(luò)尺寸的影響，得到了很好的收斂效果。而采用溫和散播撤銷消息的NDPR和環(huán)路檢測方法相比之下收斂時間就要稍長了。特別在網(wǎng)絡(luò)尺寸大于7之后。瞬時環(huán)的出現(xiàn)使得每次破環(huán)檢測都要4－5秒的延遲，拖后了收斂進(jìn)程。但由于在故障轉(zhuǎn)移情況下兩者都要受到MRAI的限制，到期后再進(jìn)行路由重建，所以，對收斂時間的影響不大。

消息復(fù)雜度方面，NDPR和環(huán)路檢測方法會在兩個方面影響消息復(fù)雜度，一方面是路由的更新消息，另一方面是探環(huán)檢測所產(chǎn)生的消息。NDPR和環(huán)路檢測方法與BGP－GF他們使用撤銷消息的方法雖然不同但其達(dá)到的目的是一致的。但NDPR和環(huán)路檢測方法引入了探測和回復(fù)的機(jī)制，產(chǎn)生了額外的消息開銷。盡管如此，探測的代價仍然在一個較低的水平，也是可以接受的。

圖3和圖4為BA拓?fù)渲泄收现袛嗪凸收限D(zhuǎn)移情況下時間復(fù)雜度和收斂時間統(tǒng)計。

圖3 BA拓?fù)涔收现袛嗲闆r下的收斂時間和消息復(fù)雜度

圖4 BA拓?fù)涔收限D(zhuǎn)移情況下的收斂時間和消息復(fù)雜度

BA拓?fù)淝闆r下的收斂時間和消息復(fù)雜度與全連通拓?fù)淝闆r下的結(jié)果相似。NDPR和環(huán)路檢測方法對比標(biāo)準(zhǔn)的BGP在收斂性能上有著較大的優(yōu)勢。但在機(jī)制上的差異使得在故障中斷下NDPR和環(huán)路檢測方法無法做到像BGP－GF那樣的收斂效果，可就用戶體驗而言，故障中斷時的表現(xiàn)更為重要。故障轉(zhuǎn)移時兩種機(jī)制的表現(xiàn)依然基本一致。NDPR和環(huán)路檢測方法在末端AS連通性的保護(hù)上仍然具有BGP－GF所不具備的優(yōu)勢。表中可以看出為此所帶來的消息開銷依然被控制在了較低的水平上?？傮w上看，兩種方法在BA拓?fù)渖系谋憩F(xiàn)都要略差于全連通拓?fù)?。這是由于在仿真過程中所使用的BA拓?fù)涞囊?guī)模要大于全連通拓?fù)?，使得路由重建的時間略長。

四、總結(jié)

本文提出了無拖延反向毒化和環(huán)路檢測方法。這種方法改進(jìn)了廣播向鄰居發(fā)送撤銷消息的機(jī)制，在引入適當(dāng)代價的情況下進(jìn)行探測，保證路徑探測的快速進(jìn)行，避免發(fā)送不必要的撤銷消息。實現(xiàn)了在花費(fèi)極少代價的情況下加快BGP收斂的目的，從仿真結(jié)果上看方法是可行的。

當(dāng)故障轉(zhuǎn)移發(fā)生時，分歧點(diǎn)毒化發(fā)送過探測消息的鄰居。這樣使得一些能夠切換到備用鏈路上的節(jié)點(diǎn)暫時失去對目的節(jié)點(diǎn)的鏈接。如何在保證連通性的同時又能避免偽信息的傳播將會是進(jìn)一步提高BGP收斂速度的關(guān)鍵。

[1]Bremler－Barr A,Afek Y,Schwarz S．Improved BGP Convergence via Ghost Flushing[C]．Proc．of IEEE INFOCOM,San Francisco,US,APril2003．

[2]LabovitzC，Wattenhofer R，VenkataeharyS,AhujaA．The impact of internet policy and topology on delayed routing convergence[C]．Proc．of IEEE INFOCOM,APril2001．

[3]Zaumen W T,Aceves J J G．Dynamics of distributed shortest一Pathroutingalgorithms[J]．ACM SIGCOMM Computer Communication Review,August 1991,V21(4)．

[4]Aceves J J G．LooP 一 free routing using diffusing computations[J]．IEEE／ACM Tran．on Networking,February 1993,VI(1)．

[5]Musuvathi M,Venkatachary S,Wattenhofer R,Labovitz C,Ahuja A．BgP －CT:afirststep towardsfastinternetfail 一 over[R]．Microsoft Research，Tech．Rep．，2000．

[6]Luo J,Xie J,Hao R Li X．An approach to accelerate convergence for Path vector protocol[C]．Proc．of IEEE Globecom,November2002．

[7]Pei D,AzumaM，Massey D,Zhang L．BGP 一 RCN:improving BGP convergence through root cause notification[J]．Computer Networks，2005，V48(2):175－194．

[8]Chandrashekar J,Duan Z,Zhang Z．Limmiting path exploration in BGP[C]．Proc．of IEEE INFOCOM,2005．

[9]CAIDAAS Relationships Data Set[EB ／OL]．[2007－05－01]．httP:／／www．eaida·org／data／active／as一 relationships／index．xml．

[10]riffin T G,Shepherd F B，Wilfong G The stable paths Problem and interdomain routing[J]．IEEE ／ACM Trans．on Networking,April 2002,VI0(2):232一 243．

[11]GNU Zebra[EB ／OL]．[2007－05－01]．httP:／／www．zebra．org／．

[12]Villamizar C,Chandra R,Govindan R．BGP route flap damping[S]．IETFRFC2439,November 1998．

[13]Barabasi A L,Albert R．Emergence of sealing in random networks[J]．Science,1999,V286:509 一 512．

[14]Li Q,Xu M,Pan L．A Study of Path Protection in Selfhealing Routing[A]．In:Proceedings of IFIP Networking 2008:554－561．

[15]L Subramanian,M Caesar,C T Ee,et al．HLP:A Next Generation Interdomain Routing Protocol[A]．In:Proceedings of SIGCOMM,2005:13－24．

[16]Bates T,Chen E,Chandra R．BGP Route Reflection:An Alternative to Full Mesh Internal BGP(iBGP)[S]．IETF RFC 4456,2006．

[17]Xue Jian－sheng,Wang Guang－xing．Analysis and Study of BGP4 Route Refection Technology[J]．Mini－Micro Systems,2005,26(9):1898－1903．

[18]Basu A,Ong C L,Rasala A,et al．Router Oscillations in IBGP with Route Reflection[A]．In:Proceedings of SIGCOMM,2002:235－247．

[19]Y．Rekhter and T．Li．Border Gateway Protocol 4．RFC1771,SRI Network Information Center,July 1995．

[20]S．R．Sangli,Y．Rekhter,R．Fernando,J．Scudder,and E．Chen．Graceful Restart Mechanism for BGP． http:／／www．ietf．org／internet－drafts／draft－ietf－idrrestart－05．txt,October 2002．

[21]A．Shaikh,D．Dube,and A．Varma．Avoiding Istabilityduring Shutdown of OSPF．In Proceedings of the IEEEINFOCOM,June 2002．

[22]A．U．Shankar,C．Alaettinoglu,K．Dussa－Zieger,andI．Matta．Transient and steady－state performance of routingprotocols:Distance－vector versus link－state．Journal ofInternetworking:Research and Experience,1995:59－87．