1、作者 ：郑萌 1 张沛 2 黄小红 3 袁晟 4基于下一跳路由变化矩阵的细粒度路由事件识别方法北京 邮电 大学网络技术研究院 CONTENTS14253研究背景与意义算法思想实验结果国内外研究现状结论1 研究背景和意义研究背景1 研究背景和意义12BGP域间路由作为网络空间的基础设施，提供了自治系统间的通信机制 ， 随着互联网的飞速发展，网络拓扑变得空前复杂 。带有破坏性的路由变化事件会造成应用服务的连接中断、可用带宽变小、链路入口处的流量阻塞，严重影响网络和服务的性能 。BGP缺乏任何形式的路径或者来源的验证，使得这一协议在经历突发状况时（链路中断、攻击、错误配置等）造成域间路由在选择路径上
2、的变化 。3研究意义1 研究背景和意义路由事件之间存在复杂的因果关系以及域间路由系统本身所存在的噪声的影响，使得检测域间路由变化的表象下所潜在的路由事件变得复杂 。传统基于 BGP路由表或更新报文的路由事件识别方法由于路由更新报文噪声以及路由表采集时间间隔的限制，在路由事件识别精度和时间粒度方面存在一定局限性 。2 国内外研究现状BGP 更新报文： 更新报文的数量分析 ：仅 着重于一个或者几个监测点 ，在 多个监测点下不易确定门限 是否被检测：二进制矩阵， 仅关注某个时隙中是否存在事件却忽视了存在多个不同事件的可能BGP 路由表： 构造二进制的张量并用于识别大规模的周期性路由事件 粒度较粗糙2
3、 国内外研究现状3 算法思想3 算法思想基本定义：路由状态 三元组 (i, n, j)： i： 自治域 n： i到达目的地前缀 j路径中的下一跳 j： 目的地前缀N(i,j,k)表示在 k时 间点自治域 i到达前缀 j所经过的下一跳Xij 1： N(i,j,k) ！ N(i,j,k+1) Xij 0： N(i,j,k) = N(i,j,k+1) 3 算法思想1.重建路由表：缩短时隙步 骤 1 获 取 监测 点路由表 R及 该时间 之后，第二天 获 取路由表 时间 之前所有更新 报 文信息集合 Y步 骤 2 解析集合 Y中的更新 报 文信息 y，并根据解析后的信息 y中的每一行判断更新 报 文 类 型：若更新 报 文 类 型表示为 A， 则 更新路由表 R中 该 前 缀 Pe和自治域 As相 对应 的路径Pa；若更新 报 文 类 型 为 W， 则删 除 该 前 缀 Pe和自治域 As相对应 的路径 Pa.步 骤 4 根据 设 定的 时间间 隔 Ti，每隔一个 Ti生成 对应 的路由表 输 出 .步 骤 5 循 环 步 骤 3， 4直到 Y中所有的更新 报 文都被 处 理 .RIB 状态 update 状态
