一种加快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．