基于AS划分的全球互联网别名解析技术

发布时间：2018-06-25 10:40

本文选题：别名解析 + IP-to-AS划分　；参考：《电子科技大学》2017年硕士论文

【摘要】：随着互联网在各行各业中正起着越来越重要的作用,互联网拓扑识别有助于科研人员保证互联网的良好运行,提升网络性能。路由器级的网络拓扑,反映了网络中路由器间的连接关系,是互联网拓扑结构的重要组成部分,然而其中存在的路由器别名问题给拓扑识别带来了很大的困难,因此针对该问题开展的别名解析研究必不可少。基于分析的技术是目前别名解析处理方法的一大分支,其主要思想为针对一些现有的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划分降低来对其进行修正,此外还对基于相似性的别名解析处理方法中的参数进行了讨论,在提升算法准确率的同时降低算法运行时间,并在不同大小的数据集中对上述方法进行了验证。
[Abstract]:As the Internet is playing a more and more important role in all walks of life, the Internet topology recognition helps the researchers to ensure the good operation of the Internet and improve the network performance. The router level network topology reflects the connection between the routers in the network, which is an important part of the Internet topology. However, it exists in the network topology. The problem of router alias has brought great difficulties to topology recognition, so the study of alias parsing for this problem is essential. Analysis based technology is a major branch of the present alias resolution processing method. Its main idea is to conclude the alias by inferring some existing traceroute data. But the existing analysis based alias resolution techniques are mostly carried out against symmetric traceroute data. When the symmetric traceroute paths are few in the processed data, the results obtained by using these methods are not very ideal. In addition, the existing analysis based alias resolution technology also has a high algorithm complexity. In view of the above problems, the main work of this paper is as follows: (1) in view of the defects in the existing analysis based alias resolution technology, the IP-to-AS partition is introduced in the alias resolution, and an alias resolution technique based on AS partition is proposed in this paper. The idea is to combine the IP-to-AS partition with the alias resolution, and use the result of IP-to-AS's processing, to divide it into different IP address blocks according to the AS attribution of the destination IP, and carry out the alias resolution processing within each block. This method reduces the complexity of the existing analysis based alias analysis method and improves the efficiency of the algorithm. It also destroys the topology structure that brings misjudgement on the AS boundary and improves the accuracy of the algorithm. In addition, in view of the high complexity of the existing IP-to-AS partitioning method, it is not conducive to the improvement of the operation efficiency of the whole algorithm. In addition, a relatively simple IP-to-AS partition method for extending the ground truth is proposed. (2) the existing based on the division of the partition method. The analysis of alias parsing technology is mostly carried out on symmetric traceroute data. In this paper, two kinds of alias resolution processing methods, which are based on graph structure and alias parsing based on similarity, are proposed, which are not dependent on the features of traceroute data, and the alias analysis based on graph structure is analyzed. The processing method uses two groups of decision topologies to determine the alias, and the similarity based alias resolution processing method constructs the feature set for each IP address, uses the feature set to calculate the similarity between the IP addresses, and carries out the alias determination according to the similarity degree. In order to reduce the complexity of the above methods, this paper also introduces the IP-to-AS delimit. In addition, the parameters of the alias resolution processing method based on similarity are discussed, and the algorithm running time is reduced while improving the accuracy of the algorithm, and the above methods are verified in different size data sets.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.0

【参考文献】