BGP路由的动态性研究.docVIP

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路由配置是否存在一个“争