论文部分内容阅读
随着互联网在各行各业中正起着越来越重要的作用,互联网拓扑识别有助于科研人员保证互联网的良好运行,提升网络性能。路由器级的网络拓扑,反映了网络中路由器间的连接关系,是互联网拓扑结构的重要组成部分,然而其中存在的路由器别名问题给拓扑识别带来了很大的困难,因此针对该问题开展的别名解析研究必不可少。基于分析的技术是目前别名解析处理方法的一大分支,其主要思想为针对一些现有的traceroute数据,通过对其进行推断来完成别名的判定。但是现有的基于分析的别名解析技术大多是针对对称的traceroute数据开展的,当处理的数据中对称的traceroute路径较少时,使用这些方法所得到的结果并不十分理想,此外,现有的基于分析的别名解析技术还存在着算法复杂度较高,判定拓扑遗漏等缺陷。针对上述问题,本文的主要工作如下:(1)针对现有的基于分析的别名解析技术中存在的判定拓扑遗漏,算法复杂度较高等缺陷,本文在别名解析中引入了IP-to-AS划分,提出了一种基于AS划分的别名解析技术。该方法的主要思想是将IP-to-AS划分与别名解析相结合,利用IP-to-AS的处理结果,根据目的IP的AS归属情况,将其划分到不同的IP地址块中,并在各块内部进行别名解析处理。该方法减小了现有的基于分析的别名解析方法的复杂度,提升了算法的运行效率,还破坏了AS边界上会带来误判的拓扑结构,提升了算法准确率。此外,鉴于现有的IP-to-AS划分方法复杂度较高,不利于提升整体算法的运行效率,本文还提出了一种较为简单的对ground truth进行扩展的IP-to-AS划分方法。(2)针对现有的基于分析的别名解析技术大多是在对称的traceroute数据上开展的这一问题,本文提出了两种不依赖于traceroute数据特征的别名解析处理方法——基于图结构的别名解析处理方法和基于相似性的别名解析处理方法,其中基于图结构的别名解析处理方法利用两组判定拓扑来进行别名的判定,而基于相似性的别名解析处理方法则为每个IP地址构建特征集合,利用特征集合来计算IP地址间的相似度,并根据相似度来进行别名判定,为降低上述方法的复杂度,本文还引入了IP-to-AS划分降低来对其进行修正,此外还对基于相似性的别名解析处理方法中的参数进行了讨论,在提升算法准确率的同时降低算法运行时间,并在不同大小的数据集中对上述方法进行了验证。