Internet域间路由稳定性研究

摘要

Internet从诞生到现在已经发生了巨大的变化。整个Internet被划分为不同的管理域，这些管理域称为自治系统。自治系统内部通过内部网关协议交换路由信息，自治系统间通过外部网关协议交换路由信息。目前，边界网关协议(BGP)是运行于Internet上的事实上的外部网关协议。随着网络规模的扩大，BGP路由的稳定性受到了业界的广泛关注，如何解决BGP路由不稳定问题已经成为Internet路由研究的焦点。 BGP路由不稳定是指存在于路由表中的路由间断性的消失和再现的现象，也叫路由振荡。导致BGP路由不稳定的因素很多，包括IGP不稳定、硬件故障、软件故障、路由器CPU能力不足和存储能力不足、网络拓扑改变、BGP路由策略冲突和配置错误等。本文以国家自然科学基金项目“Internet域间路由稳定性和可管理性”为背景，作为研究项目的一部分，对域间路由稳定性进行了深入的研究，针对导致BGP路由不稳定的部分原因，给出提高BGP路由稳定性的方法，取得了一些重要的研究成果。 路由策略冲突可导致BGP路由振荡。本文对路由策略冲突引发的路由振荡进行了深入研究，并通过仿真实验再现了路由振荡现象，给出了一种路由策略冲突检测和策略冲突引发的路由振荡抑制方法。首先根据BGP路由模型稳定路径问题，对BGP路由振荡进行研究，从理论上深入地分析了BGP路由振荡的动态行为特征和振荡条件。给出路由相对优先级的概念，用路由相对优先级来描述到同一目的的两条路由的优选关系。相邻自治系统通过所选路由的相对优先级比较来发现路由策略冲突。定义本地路径历史记录参与振荡的路由，并对本地路径历史中的重复路由加以抑制，消除BGP路由振荡。该方法能够准确地检测到BGP路由策略冲突引发的路由振荡和参与振荡的路由，并能区分策略冲突引发的路由振荡和其它原因引发的路由振荡。 BGP路由不稳定源可以通过追踪路由变化事件来确定，为此给出另外一种BGP路由不稳定解决方法。每个路由器都对路由变化事件及原因进行记载，AS间通过构建路由变化事件链发现路由振荡源。通过仿真实验证实了该方法的有效性。BGP路由器对路由表进行管理要消耗大量的CPU时间和存储空间，BGP路由表过大可能造成路由器处理能力和存储能力不足，导致路由器失效和BGP连接中断，影响BGP路由的稳定性。对BGP路由表的构成进行了定量分析，发现路由表内包含大量前缀长度大于区域Internet注册处所允许的最大前缀长度的路由。提出了基于过滤机制的减缓路由表增长的方法，与一般过滤方法不同的是，该方法对地址前缀长度大于区域Internet注册处规定的最大长度的路由进行过滤。考虑到客户对负载均衡和可靠连接的需求，允许前缀长度过长的路由在指定范围内传播，一旦传播距离超过所规定的范围就对路由加以过滤。利用实际的BGP路由表进行实验，发现该方法可以大大减少BGP路由表内的路由数，对抑制路由表增长效果明显，同时几乎不对网络的可达性产生影响。 路由配置错误也是导致BGP路由不稳定的一个原因，路由配置错误会增加路由器负载，甚至导致网络中断。本文主要研究路由源配置错误和路由输出配置错误。路由源配置错误主要是指导致通告了无效的地址前缀、无效的AS号的路由配置，路由输出配置错误是指违反BGP路由输出策略的路由配置。提出了一种路由配置错误检测方法，该方法对输入和输出路由的前缀进行从属关系检测，发现非授权的地址前缀。自治系统之间根据商业合同形成了客户-提供者关系和对等者关系，自治系统的路由输出策略由AS关系决定，本文利用AS关系对路由进行有效性检测，发现违反输出原则的路由。 针对BGP路由的收敛问题，分析了BGP路由收敛慢的原因。BGP收敛慢主要是由于收敛过程中大量的路由探测和自治系统间BGP路由策略冲突所导致，同时BGP路由收敛慢与网络拓扑和最小路由通告时间间隔相关。基于竞争有向图对BGP收敛时间进行研究，给出了BGP收敛时间范围，并从理论上加以证明，最后通过仿真实验证实了所得结论的正确性。

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

第一章 绪论

第二章 BGP协议及其模型

第三章 BGP路由振荡解决方案研究

第四章 抑制BGP路由表增长方法研究

第五章 BGP路由错误配置检测方法研究

第六章 BGP收敛时间研究

第七章 结束语

参考文献

附录

致谢