| 题名 | BGP路由稳定性建模与分析 |
| 作者 | 包广斌 |
| 答辩日期 | 2009 |
| 导师 | 袁占亭 |
| 关键词 | 自治系统 边界网关协议 路由抖动 路由收敛 路由策略 广义似然比检验 |
| 学位名称 | 博士 |
| 英文摘要 | BGP (Border Gateway Protocol)作为Internet路由体系结构的核心协议,其稳定性已成为人们所关心的焦点。本文以BGP路由稳定性作为研究对象,着重研究了影响BGP路由稳定性的关键问题,并提出了相应的稳定性解决方案,为Internet稳定运行提供了可靠的数据分析方法和快速的故障解决方案。通过理论研究、仿真分析、实验证实的研究方法,主要做了以下几个方面的工作：BGP路由抽象模型的研究和建立。本文以Internet路由体系结构为研究对象,深入研究了Internet路由系统的基本理论和动态行为规律,基于静态或动态数学模型,系统分析了BGP路由抖动、收敛延时、路由配置故障等影响BGP路由稳定性的关键问题。结合图论和拓扑学的已有知识给出BGP路由抽象模型,以简化对BGP路由稳定性问题的研究。BGP路由抖动的检测和消除方法研究。要从根本上解决路由抖动问题,最实际的方法就是找到路由抖动的源头并加以抑制。根据Griffin的BGP路由模型提出了改进的稳定路径问题模型,运用竞争有向图理论,用形式化方法详细描述了BGP路由抖动问题的本质,建立了抖动路由到路由策略冲突的映射关系,提出了基于消除策略冲突的路由抖动检测和消除方法,较好地解决了BGP路由策略所引发的路由抖动问题。BGP路由收敛性分析和改进。通过对BGP路由慢收敛现象的研究,发现造成BGP路由慢收敛的4个主要原因：1)链路或路由器失败造成的BGP路由探索延时;2)BGP最小路由通告时间会推迟BGP最佳路由的通告时间;3) AS(Autonomous System)间路由策略会影响BGP路由收敛时间;4)路由抖动抑制机制也会增加BGP路由收敛时间。研究发现,随着网络规模和连接密度的增加,BGP路由的收敛时间和消息开销都迅速增大,Tdown(路由失效)收敛时间上限达到O(n),其中n是AS节点数,消息开销上限达到|EN|·n,其中|EN|是AS间直连的链路数量。针对BGP路由慢收敛问题,本文提出了基于安全路径向量协议模型的路由收敛改进算法,通过检测AS间失效链路的根源节点,并在路由更新消息中携带根源节点信息,使接收更新的节点可以迅速撤销所有与根源节点相关的失效路由,从而提高收敛速度,减少路由更新消息开销。改进算法克服了BGP路由普遍采用的路由抖动抑制技术引起的网络收敛变慢问题,Tdown收敛时间上限下降为O(d),其中d是网络直径,更新消息开销下降为(?)EN(?), BGP路由收敛速度得到了显著提高。在BGP路由配置故障检测方法的研究中,本文主要针对路由源配置故障和路由输出配置故障进行分析。根据目前静态和动态检测方法中存在的问题,提出了两种路由配置故障检测方法：第一种方法,通过分析AS间关系和BGP路由通告原则,提出基于BGP路由输出规则的路由配置故障检测算法,该算法实现简单,便于实施,整个算法的时间复杂度为O(n·d),适合部署在AS间关系较为简单的BGP网络中。第二种方法,采用数理统计中随机变量的假设检验方法,通过分析一段时间内BGP对等体之间路由更新消息的统计量变化,实现基于广义似然比检验(Generalized Likelihood Ratio Test)的异常路由更新检测,进而推断BGP路由错误配置情况。该算法的结果不受AS之间的具体连接关系的影响,适合部署在AS间连接关系复杂的BGP网络中。在仿真实验过程中,本文使用美国Oregon大学Route View项目提供的在线BGP路由信息和欧洲IP资源网络协调中心RIPE NCC的RIS (Routing Information Service)项目网站上提供的路由信息作为实验数据。采用美国Michigan大学开发的MRT (Multi-threaded Routing Toolkit)来构造网络检测平台,用MRT所提供的动态注入BGP路由的功能,构造了脚本驱动的故障注入工具,将实验设定的路由故障注入到相应的仿真网络中。采用SSFNet (Scalable Simulation Framework Network)进行仿真实验,证实了本文所设计算法的仿真实验结果和理论分析结论基本吻合。 |
| 语种 | 中文 |
| 页码 | 117 |
| URL标识 | 查看原文 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.lut.edu.cn/handle/2XXMBERH/89678]  |
| 专题 | 网络与信息中心 |
| 作者单位 | 兰州理工大学 |
| 推荐引用方式 GB/T 7714 | 包广斌. BGP路由稳定性建模与分析[D]. 2009. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论