论文部分内容阅读
随着互联网技术的不断发展与广泛应用,网络的规模和复杂性日益提高,网络管理和维护的难度也随之提高,实时准确地掌握网络内部链路的性能参数及其动态变化成为网络测量的重要研究目标。出于安全等方面的考虑,要求网络内部节点协作的传统网络测量方法受到越来越多的限制,为此人们将医学、地球科学等领域中比较成熟的层析成像技术引入到网络测量中,通过在网络边缘进行端到端测量得到路径级性能参数,进行网络内部链路性能参数的推断。网络层析成像方法不需要内部节点协作即可获得网络内部性能参数,与互联网的非协作、异构化、基于边缘控制等特点十分契合,因此自提出以来受到人们的持续关注,是目前网络测量领域的研究热点之一。根据估计目标的不同,基于网络层析成像的链路性能参数估计问题可以分为两类:定量参数估计问题和定性参数估计问题。前者以链路性能参数的准确值为估计目标,对测量及估计方法的要求比较苛刻,而后者只需要识别网络链路的状态(如是否拥塞、是否中立等),无需估计链路性能参数的准确值,因此可以采用更为简便的方法实现。本文对这两类问题展开研究,取得以下创新成果:1.针对链路时延估计问题,结合网络链路的时延多样性特征,提出一种基于可变量化间隔的离散时延模型。该模型首先由端到端测量数据估计出各条链路时延的上界,然后据此计算各条链路的离散时延分布对应的量化间隔。同时,本文提出一种基于二层二叉树结构的链路时延估计算法,通过显式计算获得各条链路的时延分布,有效地解决了现有算法计算复杂度高的问题。仿真结果表明该算法能比现有方法更快地估计出链路时延的分布;与基于可变量化间隔的时延模型相结合,能更准确地估计链路的平均时延。2.针对拥塞链路识别问题,本文在单时隙测量场景下,提出两种利用路径拥塞程度提高识别精度的方法:(1)基于多状态模型的拥塞链路识别方法:首先根据多个路径门限将拥塞程度不同的路径映射为不同的拥塞状态,建立链路状态和路径状态在多状态模型下的关系。然后以所有链路的状态和为最小化目标,将链路状态的求解问题转换为一个多约束最优化问题,并提出一个自顶向下的方法对该问题进行求解。(2)基于拥塞子树拆分的拥塞链路识别方法:为克服多状态模型中,因路径门限选择不恰当引入的误差问题,提出一种基于拥塞子树拆分的拥塞链路识别方法。该方法根据拥塞子树中路径性能参数的相对大小对拥塞子树进行拆分,然后分别在各子树中识别拥塞链路。仿真结果表明,该方法相比已有算法,能够显著提高识别结果的准确性。3.基于单时隙测量的拥塞链路识别方法假设所有链路的拥塞概率相同。当该假设与实际情况相差较大时,这些方法的准确度较低。为此,本文对基于多时隙测量的拥塞链路识别问题展开研究,提出一个新的链路拥塞概率估计算法。该算法以最大似然方法为出发点,将针对整个网络的全局最大似然问题拆分为多个子树的子问题,然后通过显式计算分别对其求解。最大化子树似然函数的策略保证了该算法的准确度,同时由于该算法仅涉及测量数据的显式计算,计算复杂度很低。然后,将估计得到的链路拥塞概率和后续的路径状态结合,求得链路在后续时隙中的最大后验状态。相较于基于单时隙测量的方法,该方法能够进一步提高识别结果的准确性。4.当前的大多数网络层析成像方法都建立在中立网络的基础上,而对于网络是否遵守中立性原则缺少关注。但随着非中立网络在当今互联网中日趋常见,网络链路的中立性检测也逐渐成为一个受到人们关注的网络测量问题。本文首次对网络及其内部链路中立性估计的层析成像方法展开了研究。首先,采用一个线性方程组描述多时隙测量场景下链路及路径拥塞概率之间的关系,提出并证明了网络中立性可以根据该方程组解的存在性进行判断的充分条件。然后,将该条件应用于网络的局部区域,通过判断局部网络对应的线性方程组是否有解,识别其中的非中立链路序列。基于此,提出一个定位非中立链路的基本算法及其优化算法,并通过仿真实验验证了算法的有效性。