☆ 王開遠

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

一、引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、仿真結果

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

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

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

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

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

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

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

四、總結

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

當故障轉移發(fā)生時，分歧點毒化發(fā)送過探測消息的鄰居。這樣使得一些能夠切換到備用鏈路上的節(jié)點暫時失去對目的節(jié)點的鏈接。如何在保證連通性的同時又能避免偽信息的傳播將會是進一步提高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．