互联网域间路由大规模不稳定事件测量研究

《互联网域间路由大规模不稳定事件测量研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、互联网域间路由大规模不稳定事件测量研究（申请清华大学工学博士学位论文）培养单位：计算机科学与技术系学科：计算机科学与技术研究生：陈蒙指导教师：徐明伟教授二〇一七年五月Ｍｅａｓｕ－ｒｅｍｅｎｔＲｅｓｅａｒｃｈｏｎＬａｒｅｓｃａｌｅｇ－ＩｎｔｅｒｄｏｍａｉｎＩｎｓｔａｂｉｌｉｔｙＥｖｅｎｔｓｉｎｔｈｅＩｎｔｅｒｎｅｔＤｉｓｓｅｒｔａｔｉｏｎＳｕｂｍｉｔｔｅｄｔｏＴｓｉｎｈｕａＵｎｉｖｅｒｓｉｔｇｙｉｎａｒｔｉａｌｆｕｌｆｉｌｌｍｅｎｔｏｆｔｈｅｒｅｕｉｒｅｍｅｎｔ

2、ｐｑｆｏｒｔｈｅｄｅｒｅｅｏｆｇＤｏｃｔｏｒｏｆＰｈｉｌｏｓｏｈｐｙｉｎＣｏｍｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｐｇｙｂｙＣｈｅｎＭｅｎｇＤｉｓｓｅｒｔａｔｉｏｎＳｕｅｒｖｉｓｏｒ：ＰｒｏｆｅｓｓｏｒＸｕＭｉｎｗｅｉｐｇＭａ１７ｙ，２０摘要摘要测量和检测ＢＧＰ动态中的异常事件是网络测量的热门话题。此类研究工作对于域间路由故障避免、预测、检测和恢复，网络管理和配置优化，协议设计、评估和改进等方面具有重要作用。绝大部分现有ＢＧＰ异常测量工作基于所有观测点路

3、由动态数据的聚合，例如总路由更新数量、总被更新ＩＰ前缀数量等；忽略了不同观测点数据的差别。然而根据ＢＧＰ协议的特性，单个观测点处看到的ＢＧＰ动态可能是高度本地化的。因此基于聚合后的数据来设计方法和算法可能导致对ＢＧＰ动态的误理解。基于以上分析，本文提出基于观测点区分的域间路由大规模不稳定事件检测方法。研究内容和贡献包括：（１）定量研究ＢＧＰ动态数据，以及活跃ＩＰ前缀的更新在互联网的分布情况。测量发现，ＢＧＰ动态的分布是高度不均的；反映病态行为的动态更是高度本地化一的。此外，相当部分基于总更新数定义的活跃前缀，其更新分布

4、是高度局部化的。本文提出更新可见性的概念，结合更新数量定义了五类活跃前缀，并分析了各类活跃前缀的数量趋势、相互关系等特征。总的测量结果显示了基于观测点区分测量ＢＧＰ的重要性。（２）提出大规模ＢＧＰ事件（ＬＢＥ）的概念。ＬＢＥ满足两个条件：在互联网中的较大范围可见，并影响大量前缀。本文提出更新可见性矩阵的概念来描述ＬＢＥ，并形式化地定义了ＬＢＥ检测问题。在证明该问题是ＮＰ难之后，本文提出了ＧＤＡ算法来解决它。然后，该方法被应用于大量ＢＧＰ更新报文数据。测量结果显示，知名的互联网大规模破坏性事件与检测到的ＬＢＥ存在较

5、强的相关性。此外，该方法还在２０１３年１０个月的数据中检测到１０１个未被报告过的ＬＢＥ。（３）基于ＢＧＰ更新的类型和内容，以及路由表数据、ＢＧＰＣｏｍｍｕｎｉｔｙ属性一—语义数据等，提出了系列的方法包括主要元素分析，ＡＳ路径变化分析，—Ｃｏｍｍｕｎｉｔｙ属性变化分析等来分析ＬＢＥ的成因和对ＢＧＰ系统的具体影响。本文用这些方法深入分析２０１３年检测结果中的２３个ＬＢＥ。（４）开发域间路由动态性测量系统，以完成上述测量工作。该系统能够处理ＴＢ量级的数据，考虑到了各类异常情况，并且多方面的优化使得该系统适用于内存和计算

6、等资源比较有限的实验环境。关键词：域间路由；ＢＧＰ；活跃前缀；网络测量；异常检测ＩＡｂｓｔｒａｃｔＡｂｓｔｒａｃｔＭｅａｓｕｒｉｎｇｔｈｅｄｅｔｅｃｔｉｎａｎｏｍａｌｏｕｓｅｖｅｎｔｓｉｎｔｈｅＢＧＰｓｓｔｅｍｈａｖｅｒｅｍａｉｎｅｄａｎａｃｔｉｖｅｇｙｈｔｏｉ？ｒｅｓｅａｒｃｐｃ．Ｔｈｅｒｅｓｅａｒｃｈｗｏｒｋｓｉｎｔｈｉｓｄｏｍａｉｎａｒｅｉｍｐｏｒｔａｎｔｉｎｔｈｅｆｉｅｌｄｓｏｆｉｎｔｅｒｄｏｍａｉｎｒｏｕｔｉｎｇｆａｕｌｔａｖｏｉｄａｎｃｅ，ｐｒｅ

7、ｄｉｃｔｉｏｎ，ｄｅｔｅｃｔｉｏｎ，ａｎｄｒｅｃｏｖｅｒｙ，ａｓｗｅｌｌａｓｎｅｔｗｏｒｋｍａｎａｅｍｅｎｔａｎｄｏｔｉｍｉｚａｔｉｏｎａｎｄｒｏｕｔｉｎｒｏｔｏｃｏｌｄｅｓｉｎｅｖａｌｕａｔｉｏｎａｎｄｉｍｒｏｖｅｍｅｎｔ．ｇｐ，ｇ，，ｐｇｐＷｅｆｉｎｄｔｈａｔｍｏｓｔｐｒｅｖｉｏｕｓｍｅａｓｕｒｅｍｅｎｔｗｏｒｋｓａｒｅｂａｓｅｄｏｎａｇｇｒｅｇａｔｅｄｄａｔａ（ｅ．ｇ．，ｔｏｔａｌｕｐｄａｔｅｑｕａｎｔｉｔｔｏｔａｌａｎｔｉｔｏｆｕｄａｔｅｄＩＰｒｅｆｉｘｆｒｏｍ

8、ａｌｌｕｓｅｄｍｏｎｉｔｏｒｓ．Ｉｎｔｈｉｓｗａｙ，ｑｕｙｐｐ）ｙ，ｔｈｅｄｉｆｆｅｒｅｎｃｅｂｅｔｗｅｅｎ