互联网域间路由系统动态行为研究与机制设计

摘要

域间路由系统是Internet的核心基础设施，它不仅为全网范围内实现互联互通提供必要的路由信息，而且以其相对稳定性成为了Internet持续演进的基石。作为一个动态分布式系统，系统内节点间相互交换路由信息是域间路由系统运行的基本形式。这种动态行为决定了域间路由系统所呈现的扩展性、稳定性、收敛性和安全性等一系列特征。本文针对当前域间路由系统面临的问题，从域间路由动态行为的角度，量化路由动态行为的特征、分析路由劫持的传播机理、探索路由行为优化方法、设计实现路由优化和安全机制，对改善域间路由系统的扩展性、稳定性、收敛性和安全性有着积极意义。
　　本文的贡献主要现在以下几个方面：
　　一、基于Internet路由数据对域间路由动态行为进行测量和分析，发现了动态行为中存在的一些病态现象。具体地，路由变化成因分析发现产生路由更新的主要原因是COMMUNITY属性和AS路径属性变化，并且域间路由系统中存在大量重复的路由更新；通过分析路由更新数量在网络前缀粒度上的分布，发现路由抖动是域间路由系统中存在过量路由更新的重要原因；对路由抖动的机理进一步分析，发现路径探测(一个网络事件在远端路由器引发多个路由更新的现象)对路由更新数量具有显著的放大作用，且路径探测过程中使用的AS路径具有局部性（路径局部性原理）。上述发现不仅深化对当前域间路由动态行为特征的理解，而且为路由优化方案的设计提供了思路。
　　二、对路由劫持在域间路由系统中的传播机理进行分析和建模，揭示了域间路由系统中自治系统（Autonomous System，简称AS）对路由劫持免疫力低下的原因。将AS基于BGP路由信息自我发现路由劫持的概率定义为对路由劫持的免疫能力，通过求解AS实现自我免疫的充分条件和必要条件，给出了该免疫能力的上界。分析发现，在当前的域间路由系统中，80％以上的AS对路由劫持完全没有免疫能力，仅有不超过0.26%的AS具有大于85%的免疫能力。进一步分析AS免疫过程，揭示了造成AS免疫能力低下的“提供商栅栏”现象——提供商优先选择客户路由，阻止了劫持路由向被劫持者的传播，从而阻碍了被劫持者发现路由劫持。上述研究为理解路由劫持的危害和设计路由安全监测系统提供了理论支持。
　　三、基于路径局部性原理，设计并实现了路径探测聚合机制 PEA(Path Exploration Aggregation)，以抑制路由抖动和路径探测引发的多余路由更新。该机制对反复被探测的路径实施路由聚合并向邻居传播，以阻止路由抖动扩散和保护下游客户。同时，通过增加聚合路径的长度，降低聚合路由在下游客户路由决策中的优先级，以减少抖动路由对正常用户的影响。实验表明，该机制能够减少多达63.1%的BGP路由更新数量和高达53.3%的收敛时间，将平均每个路由事件的持续时间减少了7.39秒，三项指标均优于以RFD（Route Flap Damping）和PED（Path Exploration Damping）为代表的同类机制。
　　四、为了阻断不稳定路由在域间路由系统中的传播，提出了基于虚拟路径的路由抖动隔离方法BGP-VP(BGP-Virtual Path)。和PEA相比，BGP-VP做出了两点改进：一是基于路由事件而不是路由变化的发生频率来识别路由抖动，能有效避免误判；二是当检测到某个网络前缀的路由发生抖动时，将观察到的受路由抖动影响的AS关于此网络前缀的路由拓扑抽象成一个“单源单汇”网络，使用以“源”和“汇”为端点的虚路径表示经过此网络的所有已知路径，从而实现对AS路径频繁变换的隔离，增强数据平面的稳定性。理论证明，BGP-VP除了能阻止路由抖动的传播之外，还具有解除路由“争执环”的能力；给定任意路由“争执环”，该方法在其最小“争执环”所涉及节点上的部署能够消除路由抖动。以上工作对消除域间路由系统中的持续震荡具有重要的意义。
　　五、为解决“提供商栅栏”问题、提高AS对路由劫持的的免疫能力，设计了防范路由劫持的基于协同的路由安全监测机制。定义了AS部署协同监测能够获得的安全能力、协同监测网络的容错能力，并评估了不同的协同邻居选择策略对其产生的影响。实验结果表明，仅与25个自治系统进行协同就可以将对EA型路由劫持（Export-to-All,攻击者向所有直接邻居传播恶意路由实施攻击）的免疫能力提高到高于95%的水平。研究了协同监测中协同关系建立的条件，即在协同监测这种“直接互惠”型的协同关系中，参与协同的AS能从对方获得相近的效用。考虑两种不同的路由劫持策略，EA和EC(Export-to-Customer，只向客户AS宣告攻击路由)，实验结果表明，尽管Tier1 AS和Transit AS在防范EA类型的路由劫持具有显著的优势，但它们仍然需要Stub AS的协作以防范EC类型的路由劫持。
　　六、在AS之间开展路由安全监测的协同监测器面临两方面的问题，一是如何从海量的路由事件向关键事件聚焦，二是如何检测针对协同监测器本身的路由劫持。针对问题一，提出了多维度信息关联方法，该方法从发生时间、网络前缀和观测点等多个维度对检测到的网络变化进行聚合和过滤，产生告警的源AS变化、下一跳AS变化和网络不可达事件数量和关联前相比，分别减少了89.01%、96.02%和99.86%。针对问题二，提出了路由劫持验证方法，从BGP异常报文、BGP路由信息、特定方向数据包和主动探测四个层面验证针对于监测器的路由劫持是否发生。该方法具有很高的准确性，在六个月的实验期间未引发任何误判(False Positives)。在解决上述问题的基础上，设计并实现了协同监测器，实验评估表明该设计具有较小的网络开销。
　　七、要实现有效路由安全监测的关键在于检测知识库，但IP资源所有权和使用权的频繁变化使IP前缀—源AS映射关系难以有效获取。从知识平面(David D. Clark提出的、未来网络的一个构件，是用于指导网络发展的普适系统)的角度，对参与Internet地址资源分配和使用的组织及组织间关系进行建模，建立了通用的组织模型框架，基于地区级Internet注册机构(RIR)的注册数据得到了Internet的组织关系图，在此基础上构建了IP前缀和源AS映射关系的知识库，并用于对路由劫持的检测，取得了良好的效果。该模型和方法的应用有助于增强运营商对路由劫持的防范能力，是从知识平面向Internet提供支撑的一个典型示范，对认识Internet生态和新一代Internet可能的发展趋势有着积极意义。

目录

声明

第一章 绪论

1.1 域间路由系统动态行为面临的问题

1.2 改善域间路由动态行为面临的挑战

1.3 论文工作和结构

第二章 相关研究

2.1 新一代互联网路由体系结构

2.2 抑制路由抖动增强域间路由稳定性

2.3 加速路由收敛提高域间路由性能

2.4 扩展、监测BGP提高域间路由安全性

2.5 本章小结

第三章 互联网域间路由系统及其行为分析

3.1 边界网关协议BGP

3.2 Internet域间路由系统

3.3 路由变化成因分析

3.4 域间路由系统中存在过量路由更新

3.5 AS对路由劫持的免疫力评估

3.6 本章小结

第四章 PEA：抑制过量路由更新的路径探测聚合机制

4.1 前言

4.2 路径探测聚合原理

4.3 PEA机制优化

4.4 实验评估与横向比较

4.5 本章小结

第五章 BGP-VP：基于虚拟路径的路由抖动隔离机制

5.1 前言

5.2 路由抖动的识别

5.3 路由抖动的隔离

5.4 BGP-VP的三种功能

5.5 BGP-VP稳定性分析

5.6 本章小结

第六章 防范路由劫持的协同监测方法设计与系统实现

6.1 前言

6.2 协同监测的必要性

6.3 协同监测原理和体系结构设计

6.4 安全能力评估

6.5 协同关系的持续性评估

6.6 协同监测器的设计与实现

6.7 根据CMS状态检测路由劫持的可靠性评估

6.8 多维度信息关联的有效性评估

6.9 资源消耗评估

6.10 本章小结

第七章 Internet组织关系模型及其结构化建模方法

7.1 背景介绍

7.2 Internet组织关系建模框架

7.3 模型检验

7.4 组织关系模型的应用

7.5 本章小结

第八章 总结与展望

8.1 工作总结

8.2 工作展望

致谢

作者在学期间取得的学术成果

参考文献