论文部分内容阅读
网络拓扑推断在计算机网络领域是十分重要的一个问题。无论对于普通的网络使用者还是网络管理者而言,精确了解网络内部结构对于监控网络运行状态,设计网络应用都具有重要的意义。由于实际网络内部可能存在大量不能提供测量协作的节点,传统推断方法会面临失效的风险,而基于层析成像的网络拓扑推断方法通过在网络边缘节点上收集网络端到端性能参数(如时延、丢包率等),然后利用收集到参数进行数据分析及统计特征提取,便可以推断网络拓扑结构。现有网络层析成像研究大都是在网络拓扑是树状拓扑的假设下进行的。然而随着负载均衡技术的应用,互联网中出现了越来越多的多径路由网络,此时网络端节点对间会存在多条可达路径,拓扑不再是传统的树形拓扑结构,并且传统层析成像方法不再适用,因此本文主要对多径路由下拓扑估计的网络层析成像问题进行研究。另外为使网络层析成像的研究更加方便高效,设计并搭建了一套基于PlanetLab与NS-3的层析成像测量平台。本文的主要工作与创新点概括如下:(1)提出了基于报文到达顺序的端到端路径数目识别算法。明确网络中多径路由数目对拓扑估计问题至关重要。本方法首先根据包组中报文到达顺序得到探测流约束集合,在不同的K值下对探测流使用有约束K均值算法进行聚类,得到不违反约束的最小的K值,最后使用传统K均值算法的对探测流进行聚类,对从最小K值开始的不同聚类结果利用相关标准进行评判,推断出可能的多径路由数目。通过实验证明了该算法在不同负载的网络中都能准确地推断出端到端路径数目。(2)提出了多径路由下基于节点插入的网络拓扑估计方法。通过将多径路由拓扑的分解为一个单源树状拓扑和若干多源树状拓扑证明了多径路由拓扑结构的可辨识性。方法首先对网络中单径路由节点利用传统方法进行拓扑恢复得到树状拓扑,然后利用端到端测量得到的多径路由路径与其它单径路由的相关性对其分支节点在树状拓扑上进行定位,从而最终恢复出多径路由网络拓扑结构。实验结果也证明了该方法可以准确估计多径路由网络拓扑。(3)设计并搭建了基于PlanetLab与NS-3的层析成像测量平台。该平台将实际网络测量与网络仿真相结合,可以完成实际网络多径路由发现及端到端参数测量等工作,并且可以对本文所提相关算法进行实验,结果也证明了算法的有效性。