小 型 微 型 计 算 机 系 统 200年 月 第 期 Journal of Chinese Computer Systems Vol. No. 200
BGP收敛问题研究综述
郭辉
E-mail ：guohui@cslg.cn
（常熟理工学院计算机科学与工程学院 ，江苏 常熟 215500）
摘 要：边界网关协议（BGP, Border Gateway Protocol）是目前唯一运行在Internet上的外部网关协议，是现行Internet的实施标准。但目前BGP协议的收敛性能远不能令人满意，存在收敛慢等问题。本文详细分析了引起BGP收敛问题产生的根源和原因，重点阐述了目前针对BGP收敛问题，国内外学者的一些重要工作。最后，在对这些重要工作分析比较的基础上，总结了BGP收敛问题研究方面的几大趋势，以期对日后的BGP收敛问题深入研究起到启示作用。 关键词：BGP；路由收敛
中图分类号：TP393 文献标识码：A 文章编号：
A Survey on BGP Convergence Problem Research
GUOHUI
(Department of Computer Science and Engineering, ChangShu Institute of Technology, ChangShu 215500 ,China)
Abstract: Border Gateway Protocol, BGP, is the single exterior gateway protocol running in current Internet. It is an actual standard. However, the convergence performance of current BGP protocol cannot be satisfied, because of its slow convergence problem et al. This paper analyzes the root reasons of these problems which lead to the bad convergence performance of BGP, and then a survey on the most important work which focuses on the BGP bad convergence problems is given. Based on the analysis and comparison of the important work, several important trends on BGP convergence research are proposed. Key words: BGP; routing convergence
15分钟以上[3]，远远不能满足Internet用户对域间路由协议在收敛性能上的需求。
本文将对导致BGP收敛问题的根源和原因进行分析，并重点阐述目前针对BGP收敛问题国内外学者的一些重要工作。最后，我们在对这些重要工作分析比较的基础上，总结了BGP收敛问题研究方面的几大趋势，以期对日后的BGP收敛问题深入研究起到启示作用。
1 引 言
边界网关协议（BGP, Border Gateway Protocol）[1]是一种自治系统（AS, Autonomous System）间的动态路由发现协议，基本功能是在AS之间自动交换无环的路由信息。与OSPF和RIP等内部网关协议（IGP, Interior Gateway Protocol）相对应，BGP是一种外部网关协议（EGP, Exterior Gateway Protocol），并且是目前唯一运行在Internet上的外部网关协议，是现行Internet的实施标准，目前使用的是版本4。在以IPv6为主的下一代互联网体系结构中，BGP仍然有着不可取代的地位[2]。
BGP是一种基于策略的路径向量协议，利用UPDATE消息实现增量、触发式的路由更新，而不是一般距离向量协议中的整个路由表的周期性更新。当新增加或删除一条路由时，相关UPDATE消息在各AS间传播，并可能引起路由表的改变。整个Internet上所有BGP路由器的路由不断变化最终达到一个一致状态的过程，称为BGP的路由收敛过程。在BGP收敛过程中，分组可能无法到达目的地，进而对用户端到端通信造成影响，因此如何让BGP快速收敛是学术界研究的热点问题。目前的研究表明，BGP协议在收到UPDATE消息后的在收敛时间方面的表现比人们的期望相差甚远[3][4]。Labovitz等人在互联网上做的实验表明，BGP协议在路由取消或路由切换事件发生时的平均收敛时间长达3分钟；在最坏的情况下，这个收敛时间甚至可以达到
2 BGP收敛问题分析
Internet是由两万多个相互连通的、处于各种不同机构管理下的AS组成的，它们之间具有复杂的连通结构，并且这种连通结构随时在发生着改变，这给BGP收敛性能带来很大挑战。如图1所示，Internet每天都会产生几十万条的UPDATE消息需要BGP协议处理。
收稿日期： 作者简介：郭辉，男，1969年生，学士，双学位，工程师讲师，研究方向为；计算机网络，计算机仿真等
1 期 BGP收敛问题研究综述 2
图1 BGP的UPDATE消息数量统计
导致路由变化的原因是故障，由系统或线路维护、硬软件问题、外界干扰或破坏等原因所导致的故障在互联网中大量存在着[5]
，其中链路故障占了主导地位，并且很大比例的链路故障具有瞬时、抖动的特点，即很多故障持续的时间都较短（小于10秒），并且很多故障会反复发生。这些特性会影响BGP的收敛性能，例如在BGP收敛过程未完成之前反复发生的故障可能导致BGP不收敛。然而，BGP机制自身存在的缺陷才是导致BGP收敛问题的根源。
与域内路由协议类似，BGP收敛过程可以分为三个阶段：故障检测、路由计算和路由传播。然而与域内路由协议不同的是，BGP还是一个基于策略的协议，这也导致了BGP收敛问题的特殊性。从以上这些方面我们可以分析出造成BGP收敛问题的主要原因有以下四点。
第一，BGP建立在TCP协议的基础上可能导致错误的故障检测。与直接发送IP分组的域内路由协议不同，BGP使用TCP协议在路由器之间建立对等体关系，并通过周期性的KeepAlive消息来保活。然而，TCP会话的异常可能造成KeepAlive消息的延迟甚至丢弃，导致BGP路由器不必要的路由重计算[6]
，并可能影响多个AS。
第二，BGP在路由被取消或路由发生切换时会经历较长的路径搜索过程，延长了路由收敛时间。这种搜索过程不仅仅包括路由计算本身，也涉及到BGP路由在AS之间逐跳传递的特性，这是由BGP作为一个路径向量协议的特点决定的。每条BGP路由都包含了目的网络的IP地址前缀和到达目的网络所要经过的AS路径（AS_PATH属性）。BGP路由器存储邻居路由器发送来的路由表，根据自己所在AS的策略从中选择一条作为自己的转发路由，并发送给其BGP对等体。当该转发路由不再可用时，BGP路由器需要在它的邻居发送来的路由中重新搜索新的转发路由；或者当该BGP路由器又收到一条到达该目的IP地址前缀的新路由时，则需要重新计算最优路由。在这个过程中，BGP路由器所搜索到的一些路由在收敛过程结束后已经不再可用，这样延长的搜索过程将导致整个Internet上BGP路由收敛时间被增大。
第三，BGP协议的某些设计和实现机制会导致路由消息传播时间大大增加。BGP协议中规定，BGP路由器向其对等体发送到达同一目的网络路由的最小时间间隔值限定为一确定值MRAI（Minimum Route Advertisement Interval）。BGP的这种设计虽然可以在一定程度上减小通信开销，但同时也增大了路由收敛过程所花费的时间。
第四，BGP策略设臵的灵活性和隐蔽性可能导致不收敛。不同的AS分别由不同的机构管理，它们根据自己的需要设臵不同的BGP路由策略，具有很大的灵活性。另外，出于安全性等方面的考虑，各AS的BGP路由策略通常是不对外公开的，具有很强的隐蔽性。这种特性使得各个AS都无法获得全部路由策略信息，不能判断策略冲突，有的时候可能最终导致路由的不收敛。此外，计算路由的收敛特性具有相当高的复杂性。即使各个AS都将自己本地BGP路
由策略全部公布出来，判断路由能否全局收敛仍然是一个NP-Complete问题或者NP-Hard问题[7]。
3 BGP收敛问题解决方案
现有的解决BGP收敛问题的方案可以分为调整协议参数、增加新机制、设计新协议三类。我们将分别对它们进行阐述。因为每一类中具体的方案可能针对的是导致BGP收敛问题的一个或多个原因，所以在我们介绍每一种方案时都将给出该方案改进的是哪些方面，并从收敛性能的提高、代价、可行性等方面对各方案进行评价。 3.1 调整协议内部机制
这类方案对BGP的内在机制进行优化，它们并不改变BGP协议对外表现的特征，更不需要底层基础设施的配合，因此具有实现简单、兼容性好的优点。典型的方案有Ghost Flushing、路由抖动抑制和一致性断言。 3.1.1 Ghost Flushing
Afek等人提出的Ghost Flushing方案[8]是一种重要的BGP改进方案。RFC 1771[1]中规定，只对BGP声明新路由的UPDATE消息应用MRAI。也就是说，BGP路由器向其对等体通告到达某一目的IP地址前缀的路由的最小时间间隔值至少为MRAI，而发送取消路由的UPDATE消息的时间间隔没有收到限制。Ghost Flushing机制正是利用了这种对不同类型UPDATE消息发送时间间隔规定上的差异，提出：在BGP路由发生变化时，立即发送一个UPDATE消息取消之前发布的但现已不可用的旧路由，之后再发送另一个UPDATE消息通告新选择的替代路由。因为第一个取消路由的UPDATE消息为发现路由变化后立即发送的，未受到MRAI的限制，所以它可以通知各BGP路由器删除路由表中已经失效的路由，从而使得无效路由不会BGP路径搜索过程中被错误选择。
Ghost Flushing通过坏消息快速传播缩短了路由消息传播时间，通过在声明新路由前撤销旧路由缩短了路由计算时间，从而有效缩短了BGP收敛时间。然而反复发生的故障会影响协议的稳定性。此外，新的BGP协议规范RFC 4271[9]中并未明确规定MRAI是否适用于BGP取消路由的UPDATE消息，因此具体路由器协议实现上可能会有差别，而这种差别将会限制应用Ghost Flushing机制的效果。 3.1.2 路由抖动抑制
路由抖动抑制RFD（Route Flap Damping）[10]是一种已经被广泛使用的用来降低BGP路由抖动对Internet路由稳定性带来的影响的有效机制。RFD对持续不稳定的路由和偶尔发生变化的路由进行区分，并抑制抖动的路由以加快路由收敛。具体来说，对每条路由都被设臵了一定的阈值，当某条路由的抖动值超过该阈值后，这条路由将受到惩罚：在一段时间这条路由将不会被采用。当这条路由的抖动值回落到阈值以下时才能使用它。
RFD机制可以减少不必要的路由计算次数，从而缩短BGP收敛的时间。但有研究表明，RFD机制在有效抑制路由抖动的同时，也有可能会使路由被错误抑制，甚至有可能导致有效路由长达十几分钟不可用[11]。此外，不同路由器上所应用的RFD机制之间的相互作用，也可能会使一条刚刚
1 期 BGP收敛问题研究综述 3
图2 BGP收敛问题示例 被一台BGP路由器解除抑制的路由又被其它BGP路由器再次抑制[12]。 3.1.3 一致性断言
一致性断言（Consistency assertion）
[13]
Fig.2 An example of BGP convergence problem 在RCN中，首先检测到故障的BGP路由器将路由发生
采用了特殊的算
改变的位臵和原因等信息加入了UPDATE消息，这样在一定程度上可以避免在路由收敛过程中的路由黑洞问题。例如图2中当A中的BGP路由器收到了第一个撤销消息时，它便可以知道和
这类方案在旧的BGP的基础上进行修改，典型的做法是增加新的属性，因此它们的部署需要许多BGP路由器的共同支持，然而这并不会影响旧的BGP的运行。典型的方案为根源原因通知、几种多路径方案和BGP快速重路由。 3.2.1 根源原因通知
Pei等人提出一种称作根源原因通知RCN（Root Cause Notification）的方法
[14]
。该方法试图通过在BGP的UPDATE
消息中携带一些新的路由属性，用以指示发生路由更新的原因，即产生此条UPDATE消息的原因。这些属性包括：引起路由变化的链路，链路当前状态和一个序号。RCN可以有效的缓解路由黑洞带来的影响，加快BGP收敛速度。
举例来说，如图2所示，A、B、C、D为四个AS，P为一个通过B可达的IP地址前缀。B向外发布该路由，BGP收敛后最终A的BGP路由器中会有两条到达P的路径和
PBA's route to PADRoute via B = Route via C =
序号相同的BGP消息，RFD惩罚值只增加一次，这样便能够有效避免RFD中的重复抑制问题。
然而，RCN机制对部署的规模要求较高，如果只有一台BGP路由器支持RCN则没有任何作用，这使它难以实现灵活的增量部署。并且在RCN方案中BGP收敛性能直接依赖于BGP路由器在网络拓扑中的连接关系，对端自治系统中BGP的收敛性改进比较明显。此外，UPDATE消息中新引入的属性会增加一定的通讯开销。 3.2.2 多路径方案
Kushman等人提出了一种称为R-BGP的BGP协议改进方案[15]。R-BGP方案中为每条路由都预先根据各AS的策略计算出几条备用路由，一旦某处发生故障造成某条路由不可用，在等待控制层面搜索新的最优路由的同时，在数据层面立即启用该路由的一条备用路由作为转发数据的路径，不中断数据传输。R-BGP方案试图保证：只要在路由全部收敛之后源节点和目的节点之间存在符合各AS策略的可达路由，那么在收敛过程中源和目的节点之间的通信就始终保持不中断。
R-BGP方法可以在一定程度上减少受到短暂不连接情形影响的AS的数量，减少暂时的断连对整个网络的影响，同时，由于该方法在UPDATE消息中也采用了类似RCN的根源原因通知的方法，因而既保证了持续的数据转发，也有效避免了路由黑洞。但R-BGP方法在备用路由的选择上考虑不够充分，没有充分考虑备用路径和原路径的关系。例如，如果备用路径与原路径的公共节点过多，可能在某节点失效时，两条路径同时不可用，在这种情况下保护将失效。
类似的多路径方案包括Gao等人提出的备用域间路由方案[16]，它通过给出不同的BGP多路径的策略配臵准则确保BGP在任何结点故障和链路故障的情况下收敛。该方案有效的前提是本地AS和邻居AS的策略在商业关系上能够保持一致。Xu等也提出了一个多路径的域间路由方案MIRO(Multi-path Inter-domain ROuting)[17]，该方案设计了一种AS间的动态备用路径协商机制，当协商完成后，可以使用隧道在备用路径转发数据包。
3.2.2 BGP快速重路由
Bonaventure等提出了BGP快速重路由方案[18]。该方案为不同类型的客户AS预先部署连接到提供者AS的隧道，并利用BFD技术[19]检测故障，检测到以后立即启用预先设臵的隧道，并抑制UPDATE消息的通告。该方案能针对不同隧道技术的特点采用不同的保护方法。此外，该方案还利用BGP的Local Preference属性进行路由的动态调整，避免
1 期 BGP收敛问题研究综述 4
了隧道启用引起的路由回路，并且，还提出了FIB加速更新方法。
BGP快速重路由方案消除了由于短期故障引起的不必要路由搜索，与多路径方案相比收敛性能更好。但是该方案在多个并发链路故障的情况下仍然会失效[20]。此外，它仅适用于短期故障，对于长期故障的隧道保护会给BGP边界路由器增加额外的处理代价，尤其当需要对隧道包分片的时候。所以，BGP快速重路由方案只有在一定条件下才能提高BGP收敛的性能。 3.3 设计新协议
最后一类方案致力于设计全新的协议以取代BGP。最典型的方案是HLP。
Subramanian等人提出的混合链路状态和路径向量协议HLP（Hybrid Link-state and path-vector protocol）[20]是一种全新的域间路由协议。HLP利用AS间的“提供者-客户”关系形成的层次结构，限制不同层次路由信息的可见性，以解决BGP路由的扁平结构所引起的路由收敛慢和路由变化全局传播等问题。具体来讲，BGP以目的网络的IP地址前缀为路由粒度，而HLP路由的粒度变为一个AS，从而减少了Internet中域间路由的数量。HLP的信息隐藏特点隔离了局部路由变化，大大提高了协议的可扩展性和路由收敛性。基于目前Internet上的AS连接拓扑的实验结果表明，HLP能把传递路由消息的通信开销降低400倍[20]。通过限制路径搜索过程，HLP的路由收敛延时为线性。然而作为一种全新的域间路由协议，HLP不支持在Internet的逐步部署，这使它在实际网络中的应用受到了相当大的限制。 3.4 方案总结
表1显示了现有方案对造成BGP收敛问题的各项原因进行了不同程度的改进。表2对多种BGP收敛问题解决方案在路由可用性（例如路由黑洞会降低可用性）、路由稳定性、计算或通讯开销、以及部署难度等方面的性能进行了比较。从表中可以看出：其中，对故障检测方面的改进不多，多数方案都维持了现有的机制；提高路由计算性能、缩短路径搜索过程是人们较为关注的热点问题，有较多研究成果；路由消息的传播方面的改进较为困难，这是由路径向量协议的特点决定的，对它的改进关系到路由稳定性问题，或需要设计新的协议；防止不收敛的问题也有一定的研究，但还没有从根本上找到避免策略冲突的方法。此外对路由可用性和稳定性都有所提高的方案需要一定的计算或通讯开销，或者在部署方面有一定难度。
表1 BGP收敛问题解决方案性能比较1
类别 方案 故障路由路由消防止不检测 计算 息传播 收敛 调整协Ghost 维持 改进 改进 维持 议内部Flushing 机制 路由抖动维持 改进 降低 维持 抑制 一致性断言 维持 改进 维持 维持 增加新根源原因维持 改进 维持 维持 机制 通知 多路径 维持 维持 维持 改进
BGP快速重路由 改进 维持 维持 改进 新协议 HLP 维持 改进 改进 维持
表2 BGP收敛问题解决方案性能比较2 类别 方案 路由可路由稳计算、通用性 定性 讯开销 部署 调整协Ghost 提高 降低 维持 支持增量 议内部Flushing 机制 路由抖动降低 提高 维持 支持增量 抑制 一致性断言 提高 维持 增大 支持增量 根源原因较难增量 增加新通知 提高 维持 增大 机制 多路径 提高 提高 增大 一定条件 BGP快速重路由 提高 提高 增大 一定条件 新协议 HLP 提高 提高 减小 不可增量
4 BGP收敛问题研究的发展趋势
从Internet发展的特点和对路由的需求，以及目前对BGP收敛问题的国内外研究成果来看，BGP收敛问题的研究和域间路由协议的发展具有以下的特征。
1、不仅仅关注路由收敛问题，应当同时考虑到路由可用性和稳定性，这两个性能与端用户直接相关，是最终要解决的问题。特别是当前BGP路由表前缀数量巨大且增长迅速，一些路由器扩展技术例如Route Reflector[21]虽然能够通过减少路由的计算提高路由的收敛性能[22]，但是也不能忽视BGP中采用Route Reflector可能会引起的路由震荡[23]。
2、新的方案或域间路由协议必须支持在现有互联网中逐步部署，并能与BGP交互，传递网络层可达性信息。因为任何时候Internet都不可能完全停下来以在所有路由器上部署某个协议，否则再好的研究也只能停留在实验阶段，无法得到广泛应用。
3、路径向量协议受到自身内在特点的限制，不能使路由在规模不断增大的互联网中快速收敛，新的BGP机制或域间路由协议要想提高路由收敛速度，必须在一定程度上突破路径向量协议的限制。
4、AS间连接变得越来越复杂是Internet的重要发展趋势，利用丰富的连接，AS可以灵活的选择路由，同时，使用多条转发路由能够迅速完成路由切换。新的BGP机制或域间路由协议如果能充分利用Internet丰富的连接资源，可能在提供路由收敛性能方面会产生更好的效果。 References:
[ 1 ] Y Rekhter, T Li. A Border Gateway Protocol 4 (BGP-4) [S]. IETF RFC 1771, 1995.
[ 2 ] Xu Ke, Xu Ming-wei, Wu Jian-ping, et al. Design and Implementation of Border Gateway Protocol Oriented to IPv6 (BGP4+) [J]. Mini-Micro Systems, 2003, 24(11): 1898-1903. [ 3 ] C Labovitz, G R Malan, F Jahanian. Internet Routing
1 期 BGP收敛问题研究综述 5
Instability [J]. IEEE/ACM Transactions on Networking, 1998, 6(5): 515-527.
[ 4 ] C Labovitz, A Ahuja, A Bose, et al. Delayed Internet Routing Convergence [J]. IEEE/ACM Transactions on Networking, 2001, 9(3): 293-306.
[ 5 ] A Markopoulou, G Iannaccone, S Bhattacharyya, et al. Characterization of failures in an IP backbone [A]. In:
Proceedings of INFOCOM 2004, 4(2004): 2307-2317.
[ 6 ] Wang F, Gao L, Wang J, Qiu J. On Understanding of Transient Interdomain Routing Failures [A]. In: Proceedings of ICNP 2005: 30-39.
[ 7 ] T G Griffin, G Wilfong. An Analysis of BGP Convergence Properties [J]. Computer Communication Review, 1999, 29(4): 277-288.
[ 8 ] Y Afek, A Bremler-Barr, S Schwarz. Improved BGP Convergence via Ghost Flushing [J]. IEEE Journal on Selected Areas in Communications, 2004, 22(10): 1933-1948.
[ 9 ] Y Rekhter, T Li, S Hares. A Border Gateway Protocol 4 (BGP-4) [S]. IETF RFC 4271, 2006.
[ 10 ] C Villamizar, R Chandra, R Govindan. BGP Route Flap Dampening [S]. IETF RFC 2439, 1998.
[ 11 ] Z M Mao, R Govindan, G Varghese, et al. Route Flap Damping Exacerbates Internet Routing Convergence [A]. In: Proceedings of ACM SIGCOMM, 2002, 32: 221-233. [ 12 ] B Zhang, D Pei, D Massey, et al. Timer Interaction in Route Flap Damping [A]. In: Proceedings of 25th International Conference on Distributed Computing Systems (ICDCS), 2005: 393-403.
[ 13 ] Pei D, Zhao X L, Wang L, et al. Improving BGP Convergence Through Consistency Assertions [A]. In: Proceedings of INFOCOM, 2002: 902-911.
[ 14 ] D Pei, M Azuma, D Massey, et al. BGP-RCN: Improving BGP Convergence through Root Cause Notification [J]. Computer Networks, 2005, 48(2): 175-194.
[ 15 ] N Kushman, S Kandula, D Katabi, et al. R-BGP: Staying Connected in a Connected World [A]. In: Proceedings of 4th USENIX Symposium on Networked Systems Design & Implementation (NSDI), 2007: 341-354.
[ 16 ] Gao L, Griffin T G, Rexford J. Inherently safe backup routing with BGP [A]. In: Proceeding of INFOCOM, 2001: 547-556.
[ 17 ] Xu W, Rexford J. MIRO: Multi-path Interdomain Routing [A]. In: Proceedings of SIGCOMM, 2006, 36(4): 171-182.
[ 18 ] Bonaventure O, Filsfils C, Francois P. Achieving Sub50 Milliseconds Recovery Upon BGP Peering Link Failures [J].
IEEE/ACM Transactions on Networking, 2007, 15(5): 1123-1135.
[ 19 ] D Katz, D Ward. Bidirectional Forwarding Detection [EB/OL]. Internet Draft, 2009,
http://www.ietf.org/internet-drafts/draft-ietf-bfd-base-09.txt. [ 20 ] Li Q, Xu M, Pan L. A Study of Path Protection in Self-healing Routing [A]. In: Proceedings of IFIP Networking 2008: 554-561.
[ 20 ] L Subramanian, M Caesar, C T Ee, et al. HLP: A Next Generation Interdomain Routing Protocol [A]. In: Proceedings of SIGCOMM, 2005: 13-24.
[ 21 ] Bates T, Chen E, Chandra R. BGP Route Reflection: An Alternative to Full Mesh Internal BGP (iBGP) [S]. IETF RFC 4456, 2006.
[ 22 ] Xue Jian-sheng，Wang Guang-xing. Analysis and Study of BGP4 Route Refection Technology [J]. Mini-Micro Systems, 2005, 26(9): 1898-1903.
[ 23 ] Basu A, Ong C L, Rasala A, et al. Router Oscillations in I-BGP with Route Reflection [A]. In: Proceedings of SIGCOMM, 2002: 235-247. 附中文参考文献：
[ 2 ] 徐 恪，徐明伟，吴建平 等。面向IPv6的边界网关路由协议BGP4+的设计与实现[J]。小型微型计算机系统，2003，24（11）：1898-1903。
[ 22 ] 薛建生，王光兴。BGP4路由反射技术的分析与研究[J]。小型微型计算机系统，2005，26（9）：1480-1482。