论文部分内容阅读
二十世纪九十年代以来,工业界基本没有对边界网关协议(Border Gateway Protocol,BGP)进行改良,然而BGP协议服务的对象—Internet在人类社会生活中却扮演着越来越重要的角色。随着Internet的网络规模、通信体量以及应用种类的快速增长,那些在BGP设计之初并不重要的缺陷逐渐成为限制Internet发展的关键因素。因为BGP协议可扩展性差、控制语义模糊,所以理解和预测BGP的路由行为十分困难,这导致网络性能难以优化、路由故障难以定位、网络应用服务质量难以保障。因为BGP协议不检验路由的可信性和有效性,所以无效的、甚至恶意篡改的路由内容极易在BGP路由系统中扩散,这导致网络流量易被劫持,进而给网络用户造成经济损失。此外,Internet和BGP协议都采用分布式控制,并以经济利益为驱动。无论Internet是否以地址为核心,这个运作模式不会改变。因此,对于BGP协议的研究不但有助于改善目前BGP协议的性能,还对未来域间路由协议的开发具有指导意义。基于上述原因,本文对BGP路由系统的拓扑结构、路由的决策过程、传播过程和安全问题进行研究,并在深化已有认识和理解的基础上,对现有研究的不足之处提出改进。具体的,本文的主要工作和贡献包括:第一,评价AS(Autonomous System,自治域)级拓扑的测量覆盖范围。被动测量是目前测量AS级拓扑的主要方法,其测量结果受限于每个测量点的位置。本文从理论角度分析并描述了测量点的在理论上的测量覆盖结果上限,并比较实际测量结果与理论测量上限的差距。发现实际测量结果覆盖理论上限中大部分的C-P(Customer-Provider,客户-供应商)边,但只覆盖理论上限的大约30%的P-P(Peer-Peer,对等)边。本文进一步讨论了测量点的测量覆盖范围与哪些因素有关,发现测量点对被测AS的拓扑覆盖率随着被测AS与测量点间距离、测量点和被测AS邻居数量的增大而降低,而且测量覆盖率与测量点的路由策略没有明显关系。基于评价结论,本文进一步提出了优化测量点部署算法,相比于目前最优的测量点部署算法,该算法测得P-P边多11%,相比于随机选点,该算法测得P-P边多30%。第二,量化BGP路由策略的变化。BGP路由策略的变化导致路由行为规律发生变化,这会导致相关研究的结论出现偏差。本文提出邻居优先级模型以对BGP路由策略进行细粒度建模,并讨论了该模型的正确性。基于邻居优先级模型,本文提出量化BGP路由策略动态性的算法,并将该算法应用于2012年的Routeviews数据。进一步的分析发现:至少20%的前缀的选路策略在6个月内至少发生了一次变化;一个AS的路由策略以恒定的速率变化,但是非顶级AS可能会经历大规模的路由策略突变;拓扑结构和AS商业关系的变化不是路由策略变化的主因。第三,AS级路径预测。预测一对AS间的路径有助于网络诊断、流量工程和协议行为分析,然而目前存在的解决方案只能预测最佳路径,无法在网络配置发生动态变化时预测相应的路径变化。为了预测在动态的网络环境中的AS级路径,本文基于邻居优先级模型提出从累积的BGP路由数据中抽取网络拓扑和选路配置,并讨论了如何模拟动态网络环境以进行AS路径预测。本文从理论上证明了本文构建的模型网络的路由是收敛的。进一步的实验评价表明,本文提出的方法能够更准确且更充分的预测AS路径。第四,BGP异常路由检测。BGP路由系统在配置不当时或者受到恶意攻击时十分脆弱,因此需要实时检测BGP路由系统的异常路由行为。如果异常路由检测的误报率很高,系统的使用者就需要通过其它方式进一步验证,这降低了异常路由的检测的实效性。基于长时间存活的路由和事件并发度,本文提出路由泄漏的在线检测方法;基于误报事件特征分析,本文提出前缀劫持的在线检测的改进方法。进一步的实验评价表明本文的方法不包含误报的前缀劫持和路由泄漏事件。