论文部分内容阅读
网络拓扑结构识别对于网络的监测、管理、控制以及内部链路参数的估计都有重要意义。通常有两种方法进行网络拓扑识别:利用内部节点协作的传统方法和网络层析成像方法。网络层析成像方法由于不需要内部节点的协作,引起了学术界和工业界的高度重视。现今的网络拓扑结构层析成像识别算法有很多种,基于最大似然的拓扑估计算法和邻居节点加入树拓扑估计算法是其中的两种算法。这两种算法都有很高的拓扑估计准确率,但是,前者在对大规模网络拓扑进行识别时会产生很大的计算量,后者对门限值的选取有很大的依赖性,好的门限值不仅能够减少探测包的数量而且能够提高拓扑估计准确率。针对上述两种算法存在的问题,本文提出了三种改进的网络拓扑结构层析成像识别方法,具体工作如下:1、首先针对基于最大似然的拓扑估计方法计算量大的问题(对大规模网络拓扑结构进行估计时),提出了改进的基于最大似然的快速拓扑估计方法,降低了计算复杂度。主要工作包括:1)证明了拓扑估计似然函数是单峰的且峰值为最大值。2)利用拓扑估计似然函数的单峰性,用MCMC算法搜索拓扑空间时只需一直沿着似然函数上界值增大的方向进行即可,找到的似然函数最大值是全局最大值。改进算法搜索到的中间拓扑数目减少了,由于计算量主要集中在对搜索到的拓扑树的似然函数上界值的计算上,因此计算量也减小了。3)模型仿真和网络仿真验证了改进算法的性能。2、现有网络拓扑结构层析成像识别方法假设所有的内部节点都不协作,然而在网络中可能存在一些内部节点是可协作的,利用这些协作信息可以提高网络拓扑结构层析成像的工作效率,为此本文提出了一种基于端到端测量的快速网络拓扑估计方法,主要工作包括:1)提取协作节点的协作信息。在内部协作节点上对数据流进行采样,获取从源节点经过该中间节点能够到达的目的节点的集合,以此作为该节点的协作信息。2)利用协作信息构建约束条件,在拓扑搜索过程中,不满足约束条件的拓扑树直接被抛弃。由于需要计算似然函数上界值的拓扑树减少了,计算量减少了。3)将拓扑估计似然函数的单峰特性和协作信息的约束结合起来,进一步减小计算量。4)模型仿真和网络仿真验证了算法的性能。3、为了减少探测包的发送数量,在一般的叶子节点加入树拓扑估计算法基础上,提出了门限分等级的叶子节点加入树拓扑估计算法,主要工作包括:1)根据经验确定经验门限值。2)将经验门限值分为n个等级。对于门限的每一个等级,分别利用一般叶子节点加入树拓扑估计算法估计出相应的拓扑,利用最大似然方法计算出该拓扑的似然函数上界值。3)比较得到的n个拓扑的似然函数上界值,似然函数上界值最大的拓扑即最佳拓扑,相应的门限值即最佳门限。4)模型仿真和网络仿真结果表明,门限分等级的叶子节点加入树拓扑估计算法在相同的拓扑估计正确率下,需要发送的探测包数目大大减少。