一種加快BGP收斂的方法

☆ 王開遠

（吉林師范大學，吉林四平 136000）

一、引言

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

二、無拖延反向毒化和環路檢測方法

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

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

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

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

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

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

圖 1 BGP,NDPR,BGP－GF區別

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

2．環路檢測方法

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

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

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

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

圖2 環路檢測舉例

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

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

三、仿真結果

仿真結果顯示，NDPR和環路檢測方法在收斂時間和消息復雜度上比較標準的BGP都要更加優越，由于BGP冗長的計數過程，在網絡尺寸不斷增加時，其收斂時間隨之線性變化。再加之每個MRAI都會伴隨一次偽信息的散播。使得消息復雜度也隨之增加。這當中NDPR和環路檢測方法及時去除掉了系統中的偽信息，對收斂性能的提高起到了很大作用，但仍然遜于BGP－GF。

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

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

圖3和圖4為BA拓撲中故障中斷和故障轉移情況下時間復雜度和收斂時間統計。

圖3 BA拓撲故障中斷情況下的收斂時間和消息復雜度

圖4 BA拓撲故障轉移情況下的收斂時間和消息復雜度

BA拓撲情況下的收斂時間和消息復雜度與全連通拓撲情況下的結果相似。NDPR和環路檢測方法對比標準的BGP在收斂性能上有著較大的優勢。但在機制上的差異使得在故障中斷下NDPR和環路檢測方法無法做到像BGP－GF那樣的收斂效果，可就用戶體驗而言，故障中斷時的表現更為重要。故障轉移時兩種機制的表現依然基本一致。NDPR和環路檢測方法在末端AS連通性的保護上仍然具有BGP－GF所不具備的優勢。表中可以看出為此所帶來的消息開銷依然被控制在了較低的水平上。總體上看，兩種方法在BA拓撲上的表現都要略差于全連通拓撲。這是由于在仿真過程中所使用的BA拓撲的規模要大于全連通拓撲，使得路由重建的時間略長。

四、總結

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

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

[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．