论文部分内容阅读
随着信息技术的飞速发展,网络的普及率越来越高,计算机网络已经深入到生活的各个领域,成为人们生活密不可分、极其重要的一部分。由于各种原因,网络内部的拓扑结构信息通常是不可见的,但是准确的网络拓扑对网络管理、网络的故障诊断、错误定位、流量分析等有着重要作用。因此,对网络拓扑推断的研究具有重要的学术意义和广泛的实用价值,故本文的主要研究内容是主动测量下的基于traceroute的网络拓扑推断。在非合作网络环境下,通过traceroute技术进行网络拓扑推断的过程中,不得不面对两个问题:匿名路由器问题和路由器别名问题。尽管目前国内外学者对于这两个问题已经进行了一些研究,提出了一些解决方法,但这些方法仍存在不足之处。例如,在匿名路由器方面,现有算法在推断过程中出现环、非匿名节点的错误合并等问题,导致推断出的网络拓扑图不够准确;在路由器别名方面,现有算法的计算复杂度较高,存在大量不必要的计算,不适用于大规模网络等等。本文对主动测量下的基于traceroute的网络拓扑推断进行研究,主要工作包括以下两个方面:1.在匿名路由器方面,本文首先对现有的算法进行了深入研究,分析并指出了iTop算法中存在的环、非匿名节点的错误合并等五个方面问题。其次,针对上述问题给出了具体的解决方案,提出了GAAR算法。最后,对本文提出的GAAR算法和现有算法,在公开数据集CADIA上从多个维度进行实验分析,指明GAAR算法在保证时间复杂度的同时,提高算法准确率。2.在路由器别名方面,现有的别名解析的方法主要有两类:基于探测的别名解析技术、基于分析的别名解析技术。本文通过对现有算法的分析,指出Kapar算法所存在的计算量大、对traceroute过于依赖的问题,并针对这些问题对现有算法进行优化。通过对基于分析的别名解析技术和基于探测的别名解析技术的结合、以及加入filter机制,提出ICAR算法。通过理论分析的方法,指明ICAR算法在减少计算量的同时,提高了路由器别名识别的完整度。