BGP路由的动态性研究

摘 要 BGP路由的不断变化使得对协议策略的维护、定位路由故障、控制协议流量十分困难。本文从优化BGP路由策略配置、解释产生路由更新的根本来源、预测BGP的路由行为等角度对BGP路由的动态特征的相关研究进行介绍，进而对不同研究进行比较分类，剖析其的优劣。

关键词 BGP；路由动态性；路由策略

中图法分类号 TP393 文献标识码：A 文章编号：2095-2163（2016）02-

A survey on BGP routing dynamics

Su Shen， Fang Binxing

（Network and Information Security Research Center， Harbin Institute of Technology ， Harbin 150001）

Abstract BGP’s routing table changes constantly， which makes routing policy decision， locating route instabilities， and engineering traffic very hard. This paper investigates the researches of BGP route dynamics from the point of route convergence， locating route instabilities， and predicting AS level paths. And the paper also explores their advantages and disadvantages.

Key words Border Gateway Protocol （BGP）； routing dynamics； routing policy

0 引言

Internet的BGP路由系统存在大量的更新报文，这导致BGP的路由表频繁发生变化，从而增大了路由系统的开销、并降低了网络的可控性和稳定性。因此，如下研究营运而生：需要对BGP路由的动态特征进行描述、分析和解释，而在此基础上对BGP路由行为展开预测，进而为工业界提出改善BGP协议配置的指导方法。

1997年，Labovitz等人[1]系统地描述了BGP路由动态特征，指出BGP路由系统中大量的更新报文并不是由路由配置或者网络拓扑的变化引起的，而是冗余的、病态的路由更新报文。同时，BGP路由的变化具有明显的周期性，这与网络的使用方式（network usage）相关。在后续研究中[2]，Labovitz等人发现通过对单一供应商的路由配置的优化，可以显著减少冗余的BGP路由更新。2007年，文献[3]对文献[1]描述的BGP路由动态性重新进行了评价，指出BGP路由系统的冗余路由转发已经大大减少了。另外，文献[4]指出BGP更新报文的规模与Internet拓扑规模呈线性关系。文献[5]指出Internet主体流量的路由很稳定，相比之下流量比较小的路由将会更加容易发生改变。

基于对BGP路由动态性的认识，相关研究大体可以分为：讨论如何优化BGP路由策略配置，以减少冗余的路由更新[6-10]；从BGP路由行为出发，解释产生路由更新的根本来源[11-18]；模型、预测BGP的路由行为[19-23]。鉴于目前BGP路由系统的冗余更新大大减少，第一类研究效果颇为可观。由于BGP协议本身对路由的描述粒度限于AS级，后两类研究的精度仅限于AS级。接下来，本文依次介绍上述3类研究工作。

1 BGP路由收敛问题

冗余的BGP路由更新导致BGP路由表频繁发生变化，一条BGP路由的AS路径的变化通常都符合如下模式：一个长时间存在的AS路径在短时间内频繁地发生变化，最后变成某一个其它的AS路径并继续长时间存在，这种现象称为“路径探索”（path exploration）。究其本质就是在某一个网络事件的影响下，某个AS改变其BGP路由表，由此而使得一定范围内与之连接的AS的路由表页随即发生震荡。文献[6]通过声明和撤销“种子前缀”（beacons）来观察相应的路由行为来研究“路径探索”现象，进一步发现“路径探索”多会持续几分钟，而且这一现象在Internet核心网络并不明显，在边缘网络则表现更为突出。

“路径探索”表明BGP路由表会在特定情况下反复变化，即BGP对应特定的路由变化的收敛时间可能会很长，极端情况下，会出现持续的路由震荡。文献[7]从理论的角度对BGP的路由收敛问题进行了形式化论证，由此推得：BGP路由系统是否收敛等价于这个网络的BGP路由配置是否存在一个“争执轮”。

虽然路由抖动抑制可以加速BGP收敛，但是该方法并不能从根本上解决BGP协议的收敛问题，目前BGP收敛问题的研究实现方法大体分为3类。在此，对这3类方法给出如下应用解析：

第一类方法采用实时的路由策略冲突检查。通过累计收集历史路由[9-10]，检查哪些路由更新会导致循环的路由更新转发，进而调整路由策略以屏蔽这些病态的路由更新。这类方法的缺点在于通信开销比较大；而且其解决方案也并非检查是否存在“争执轮”，因而本可以收敛的路由策略也会发生一定修改。

第二类方法强调在BGP基础上增加全局的调度[11]。通过收集每个AS的路由配置策略，并从整体上检查AS间是否存在相互冲突的路由策略。这类方法的缺点是BGP路由配置策略本身通常关乎商业运作内情，很多AS是难于主动提供这样的数据，因而整个Internet的协作基本是不可能实现的。

第三类方法放弃全局协作，而对每个AS的BGP配置提出限制规则。文献[24]指出，只要每个AS的BGP输出过滤规则满足：“对供应商和对等AS只转发本地或者来自客户AS的路由”， Internet的全局BGP路由就可以保证收敛。然而，某些AS之间的商业关系定性复杂，不能用简单的“客户、供应商、对等AS”来进行确切描述。同时，对于大规模ISP，其内部客户AS的路由数量趋多，且变化非常频繁，想要让BGP配置满足上述规即已成为一项颇具难度的研究工作。

2 定位BGP路由变化来源

除了冗余的路由更新，BGP路由系统中的路由更新主要是由拓扑变化、软硬件故障或者路由策略的变化引起的[12]。定位这些路由更新的实际来源可以帮助AS管理员定位路由故障、提高网络性能并避免路由震荡，因此学术界对此开展了大量研究工作[13-19]，并将这类研究统称为定位路由变化（Locating route instabilities）。其基本思路为：将路由更新按着前缀、时间、观测点三个维度划分成不同的路由事件，并根据同一个路由事件中的路由更新的特征推测路由事件的类型，进而定位路由更新的来源。当一条稳定的路由经过“路径探索”过程变为另外一条稳定的路由，要么是旧的路由被撤销，要么是新的优先级更高的路由被声明[13]。文献[16]证明了该研究可以将70%的路由更新的来源精确定位到某一条AS边上。虽然进一步细化定位精度存在实施困难，文献[17]则转而讨论了如何在定位路由故障以后，再通过修改路由配置以避免受到路由故障的影响。

3 AS路径预测

为了控制网络流量、优化网络配置，AS管理员往往需要主动修改网络配置。因此预测BGP路由（预测AS路径），也是一个重要且热门的研究课题。

traceroute可以探测流量在AS间的实际传播路径，因此这类研究中最为常见的讨论方法就是利用traceroute主动探测IP级路径，而后将IP地址转化为AS号。这种方法存在不可小视的现实缺陷。首先，与拓扑测量的问题一样，将IP地址映射为AS号的过程会带来无法忽略的误差。其次，流量经过的实际路径与BGP路由页并不是完全一致。最后，这种方法需要从预测起点发起traceroute探测，而实际情况下却往往难以满足，并且Internet的骨干网络中很多路由器并不响应traceroute探测。

基于所有AS的路由转发都符合AS商业关系的路由策略这一基础假设，文献[22- 23]将预测AS间路径转化为计算一对AS间的符合“无谷底”模型的最短路径。后续工作验证了这一方法的正确性[25]，然而该方法却无法体现BGP路由的多样性（即同一个AS的不同路由器到达特定目标前缀的AS路径可能会存在着不一致），而且最短的符合“无谷底”模型的AS路径页可能不止一条，因此这种方法的精确性还有待改善。

文献[26]采用类似神经网络的方法从BGP数据中抽取路由策略，通过迭代地调整网络路由策略使得其路由输出与训练数据能够达成现实一致，而后再用训练获得的路由策略进行AS路径预测。文献中将一个AS划分成若干个“准路由器”，不同“准路由器”采取的路由策略页随即有所不同，因此该方法可以体现BGP路由的多样性。但这种方法的缺点缺课分析表现在其中用于训练的数据仅只考虑一副快照，而实际的网络环境却是变化补丁的，因而这种预测后得到的结果也是片面的。

4 结束语

对于BGP行为的理解，本质上是对经济的行为的理解，更是对人的行为的理解。如果Internet的经济结构发生改变，或者能够从一个新的角度去观察BGP行为，往往就会获得某种全新的、甚至更进一步的理解。因此对BGP路由动态性的研究只能解说哪个更符合目前的Internet特征，而不能评说基础事实是什么，因为基础事实会随着经济规律变化。

本文从优化BGP路由策略配置，解释产生路由更新的根本来源；模拟、预测BGP的路由行为3个角度对动态BGP路由的相关研究进行了详细的探讨与介绍。期待相关研究机构、运营商能够提供更充分的数据来源，为BGP动态性的相关研究提供有利、且重要的研究环境和基础。

参 考 文 献：

[1] LABOVITZ C， MALAN G， JAHANIAN F. Internet routing instability [J]. IEEE/ACM Transactions on Networking （TON）， 1998， 6（5）： 515- 528.

[2] LABOVITZ C， MALAN G， JAHANIAN F. Origins of Internet routing instability [C]// //Proceeding of IEEE INFOCOM， [S. l.]： IEEE 1999： 218-226.

[3] LI J， GUIDERO M， WU Z， et al. BGP Routing Dynamics Revisited [J]. ACM SIGCOMM Computer Communication Review， 2007， 37（2）： 5-16.

[4] ELMOKASHFI A， DHAMDHERE A. Revisiting BGP churn growth [J]. ACM SIGCOMM Computer Communication Review， 2014， 44（1）： 5- 12.

[5] REXFORDJ， WANG J， XIAO Z， et al. BGP routing stability of popular destinations [C] //ACM SIGCOMM Internet Measurement Workshop （IMW）， Pittsburgh： ACM， ， 2003：197-202.

[6] OLIVEIRA R， ZHANG B， PEI D， et al. Quantifying path exploration in the Internet [J]. IEEE/ACM Transaction on Networking， 2009， 17（2）： 445- 458.

[7] GRIFFIN T， SHEPHERD F， WILFONG G. The stable paths problem and inter domain routing [J]. IEEE/ACM Transaction on Networking， 2002， 10（2）： 232-243.

[8] Labovitz C， Ahuja A， Bose A， Jahanian F. An experimental study of Internet routing convergence [R]. Tech. Rep. MSR-TR-2000-08， Microsoft Research， 2000.

[9] Yilmaz S， Matta I. An Adaptive Policy Management Approach to BGP Convergence [D]. Boston， MA， USA： Boston University ， 2006.

1 [10] GRIFFIN T， WILFONG G. A safe path vector protocol [C]// Proceeding of IEEE INFOCOM， Tel Aviv， Israel

： ACM， 2000： 490-499.

[11] GOVINDAN R， ALAETTINOGLU C， EDDY G， et al. An architecture for stable， analyzable Internet routing [J]. IEEE Network： The Magazine of Global Internetworking， 1999， 13（1）： 29-35.

[12] MAHAJAN R， WETHERALL D， ANDERSON T. Understanding BGP misconfiguration [C]// SIGCOMM 2002： Proceedings of the 2002 conference on Applications， technologies， architectures， and protocols for computer communications， Pittsburgh： ACM，2002： 3-16.

[13] FELDMANN A， MAENNEL O， MAO Z. Locating internet routing instabilities [C]// proceeding of ACM SIGCOMM. Portland： ACM， 2004， 34（4）：205-218.

[14] LAD M， ZHANG L， MASSEY D. Link-Rank： A graphical tool for capturing BGP routing dynamics [J]. Network Operations and Management Symposium， 2004， 1： 617- 640.

[15] MAENNEL O， FELDMANN A. Realistic BGP traffic for test labs [C] // proceeding of ACM SIGCOMM. Pittsburgh： ACM， 2002， 32（4）：31-44.

[16] Caesar M， Subramanian L， Katz R. Towards Localizing Root Causes of BGP Dynamics [EB/OL]. （2003-11） http：//web.engr.illinois.edu/～caesar/papers/rootcause.pdf.

[17] JAVED U， CUNHA I， CHOFFINES D， et al. PoiRoot： Investigating the Root Cause of Interdomain Path Changes [C]//proceeding of ACM SIGCOMM， HongKong： ACM， 2013， 43（4）：183-194.

[18] Caesar M， Subramanian L， Katz R. Route cause analysis of Internet routing dynamics [R]. Tech. rep.， UC Berkeley UCB/CSD-04-1302， 2003.

[19] LAD M， NANAVATI A， MASSEY D， et al. An algorithmic approach to identifying link failures [C]// Proceeding of PRDC， Papeete， Tahiti：IEEE， 2004：：25 - 34.

[20] Quoitin B. C-BGP， an effcient BGP simulator [EB/OL][2003]. http：//cbgp.info.ucl.ac.be/

[21] QUOTIN B， UHLIG S. Modeling the routing of an autonomous system with C-BGP [J]. IEEE Network： The Magazine of Global Internetworking， 2005， 19（6）： 12- 19.

[22] WENPING D， MUHLBAUER W， YUEXIANG Y， et al. Shedding light on the use of AS relationships for path inference [J]. Communications and Networks， 2012， 14（3）： 336- 345.

[23] YANG G， DOU W. An efficient algorithm for AS path inferring [C]// ICHIT. Daejeon： ACM， 2009：151-154.

[24] GAO L， REXFORD J. Stable Internet routing without global coordination [J]. IEEE/ACM Transactions on Networking （TON）， 2001， 9（6）： 681- 692.

[25] MüHLBAUER W， UHLIG S， FU B， et al. In search for an appropriate granularity to model routing policies [C]// SIGCOMM 2007： Proceedings of the 2007 conference on Applications， technologies， architectures， and protocols for computer communications. Kyoto： ACM， 2007：145- 156.

[26] HLBAUER W， FELDMANN A， MAENNEL O， et al. Building an AS-topology model that captures route diversity [C]// SIGCOMM. Pisa： ACM， 2006：36（4）：195-206.