基于隶属度的自治系统级拓扑发现-江苏计算机网络技术重点试验室.PDF

基于隶属度的自治系统级拓扑发现 史海涛，程光 （东南大学 计算机科学与工程学院，南京 210096；江苏省计算机网络重点实验室， 南京 210096； 东南大学计算机网络和信息集成教育部重点实验室） 摘 要： 基于BGP 路由表进行AS 级拓扑发现是当前使用的主 方法之一，结合BGP updates 可以 获得更加完整的拓扑信息。但是BGP updates 时间长度的选取是一个难题，另外，该方法也很难保 证结果的准确性。本文提出一种基于隶属度的AS 级拓扑发现方法，将边和节点分为存在和不存在 两个状态，从BGP 路由表和BGP updates 中得到边和节点并计算其存在性的隶属度，然后将隶属度 带入拓扑中进行分析研究。这是第一次将隶属度引入到拓扑发现中。 关键词： 自治系统; 边界网关协议; 网络拓扑; 隶属度 1．引言 Internet 由几万个自治系统构成。如果把这些自治系统看作一个个节点，把自治系统间的互联看作相应节 点间的边，则由这些节点和边构成的图就是自治系统级拓扑图。建立自治系统级的拓扑图在研究 Internet 的结构模型，网络协议的改进，网络行为预测以及网络仿真等方面都有重 意义。 自治系统(AS)是由于技术、网络管理、行政和商业上的原因被划分到一个组的网关的集合。每一个自治 系统都有一个 16 位的编号做其标识。在每个自治系统内部运行的路由协议被称为内部网关协议(IGP) ，而 在各自治系统之间的路由协议被称为外部网关协议(EGP) ，外部网关协议中最常使用的就是边界网关协议 (BGP) 。 基于BGP 路由表构建拓扑图是一种常用的方法。从Internet 中设置的观测点中获得BGP 路由表快照， 提取其中as_path 信息，在as_path 中相邻的自治系统之间存在着一条边，而在as_path 中出现的自治系统 就是拓扑中存在的节点。该方法的局限性在于通过几个观测点的路由表所得的拓扑图是不完全的。首先观 测点所得路由表只是从该点所能到达的路由信息，并不是整个互联网的信息；其次路由表中只存放最优的 路由，其他的路由都被丢弃，所以丢失了很多的互联信息。 使用BGP updates 和路由表结合的方法在一定程度上可以提高获取的连接信息量，但是BGP updates 的 选取有一个重 的问题需 解决：究竟应该选取多长时间的数据量。随着时间的增长，拓扑图中的边和节 点的数量会增加，但是时间越长，现实中已经消失的边和节点出现的可能性又会增大。另外这种判断方法 本身还存在着另一个问题：根据时间来判断在拓扑图中边和节点是否存在，在选定的时间段内出现的边和 节点就认为存在，而在选定的时间段之外出现的边和节点就认为不存在，这种判断方法不够精确。假设选 取时间段为60 天,60 天内出现的边或者节点可能已经消失，而60 天之前的边或节点可能仍然存在。而且， 该方法认为在第60 天出现的边在当前拓扑中肯定存在，而第61 天出现的边一定不存在，这显然是不合理 的。 基金项目：下一代网络热点异常自适应抽样测量方法研究，BK2008288，江苏省自然科学基金 基于自治治理模型的网络管理与安全研究，2009CB320505，国家973 计划 作者简介：史海涛，1985 年，男，硕士研究生,研究方向：网络测量，htshi@; 程光，1973 年，男，副教授， gcheng@nj 本文提出一种基于隶属度的 AS 级拓扑发现方法。该方法将边和节点分为存在和不存在两个状态，从 BGP 路由表和BGP updates 得到边和节点并计算其存在性的隶属度，然后将隶属度带入拓扑中进行分析研 究。 2.相关工作 Govindan 等人的研究[1]通过收集21 天的路由更新数据得到自治系统级拓扑，这是在该领域最早的研究 工作之一。后来有一系 的自治系统拓扑研究，基本方法都是读取BGP 路由表进行拓扑发现。Chang 等人 [3] 在[2] 中检验了RouteView 项目 收集的路由表快照，研究其中包含的拓扑完整性。他们发现该路由表快照 比较完整的覆盖了Tier-1 型自治系统的互联信息，但是更低级的自治系统互联信息覆盖率不高。文章研究 结果表明，路由表快照丢失了很大一部分的自治系统拓扑数据。文章[4] 中CAIDA 使用另一种方法进行AS 级拓扑发现。他们用从25