NT技术中延迟分布估计算法的研究.doc

NT技术中延迟分布估计算法的研究.docNT技术中延迟分布估计算法的研究摘要:网络断层扫描(NT)是一种新的网络外部测量方法,它是网络测量技术与统计学理论相结合的产物。在简要介绍网络断层扫描的基础上,该文提出了一种基于重要性抽样(IS)和期望最大化算法(EMAlgorithm)网络断层扫描的时延估计方法,最后基于NS2仿真试验验证了该方法的有效性和准确性。关键词:网络断层扫描,端到端测量,期望最大化算法,重要性抽样,NS2 中图分类号:TP301文献标识码:A文章编号:1009-3044(2011)09-1997-02 workLinkDelayDistributionsinNTTechnology WULi-peng,WUChen-wen,SONGJin (SchollofElectronicandInformationEngineering,LanzhouJiaotongUniversity,Lanzhou730070,China) workexternalmeasuringmethod,,basedonimportancesampling(IS)andexpectationmaximizationalgorithm(EMAlgorithm),workLinkDelayDistributionsinNTTechnology,uracyistestifiedbysimulationbasedonNS2. worktomography;end-to-endmeasurements;EMalgorithm;importancesampling;NS2 1概述 workMeasurement,NM)是获取网络的拓扑结构和性能参数的方法,也是有效的设计、实现和管理网络的必要工具。但是,当今网络的大规模、分布化、不协作、异质等特点,使得传统的基于网络内部设备的网络测量方法的缺陷越来越明显: 1)测量依赖于自治系统内部节点的协作,基于网络安全和商业利益等原因,有些自治系统并不对外开放,难以实现内部节点的协作和信息交流,无法保证测量的准确性。 2)网络测量依赖于特定的网络协议[1](如TCP/IP协议、SNMP协议),无法实现与网络结构和协议无关的测量; 3)测量信息的传输可能影响到网络的运行,在网络高负载是无法进行测量。为此,workTomography,NT)。它是根据网络外部(即网络边界)的测量信息来分析和推断网络的内部性能,是一种在没有网络节点协作条件下,通过主动发包探测或被动收集网络内部有用信息的新技术,结合统计学方法能够很好地推理出网络所有链路上的QoS参数,如延迟分布、丢包率、网络拓扑结构和OD(origin―destination)流量等。而EM算法作为一种统计学上的参数估计算法,常被用于推测网络所有链路上的QoS参数,但是EM算法并非万能,其最大的缺点是收敛速度较慢,因此本文把蒙特卡洛方法重要性抽样(ImportanceSampling,简称IS)与EM算法相结合,提出一种基于重要性抽样的期望最大化算法(IS-EM)。和期望最大化算法相比,新方法不仅十分显著地减少了计算量,而且保持了EM方法的优越性能。 2链路时延估计EM算法图1的二叉树模型描述了网路的逻辑结构,节