基于端到端数据的矩的网络时延估计算法

《基于端到端数据的矩的网络时延估计算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第37卷第10期计算机工程2011年5月Vol.37No.10ComputerEngineeringMay2011·博士论文·文章编号：1000—3428(2011)10—0032—03文献标识码：A中图分类号：TP301.6基于端到端数据的矩的网络时延估计算法12林俊武，张建中(1.厦门大学电子工程系，福建厦门361005；2.中国海洋大学地球探测与信息技术系，山东青岛266100)摘要：现有时延层析算法大多考虑离散时延模式，但算法效率比较低。为此，提出一种连续时延估计算法，假定链路时延为某参数的函数分布，根据多播特征并基于端到端数据的矩，利用非线性最小二乘法估计链路时延分布函数的参数，

2、并在每步迭代中用一维牛顿搜索确定最优步长，达到快速收敛。应用Matlab和NS2仿真软件得到的数据表明，该算法所需的存储量少，算法简单且效率较高。关键词：网络测量；网络层析；时延估计；多播；非线性最小二乘法AlgorithmforNetworkDelayEstimationBasedonEnd-to-EndDataMoment12LINJun-wu,ZHANGJian-zhong(1.DepartmentofElectronicEngineering,XiamenUniversity,Xiamen361005,China;2.DepartmentofGeo-explorationandIn

3、formationTechnology,OceanUniversityofChina,Qingdao266100,China)【Abstract】Theup-to-datealgorithmsondelaytomographyarebasedonthediscretedelaymode,butitislowefficiencyinthismode.Thispaperproposesacontinuousdelaymode,whosedelayisdistributedonafunctionwithsomeparameters.Accordingtotheruleofmulticastand

4、basedonend-to-endmoments,theparameterscanbeestimatedusingnonlinearleastsquaresandthebeststepischosenbytheone-dimensionNewtonsearchiniteration.ExperimentalresultsonMatlabandNS2simulationshowthatthealgorithmneedslittlestorageandissimplewithhighefficiency.【Keywords】networkmeasurement;networktomograph

5、y;delayestimation;multicast;nonlinearleastsquaremethodDOI:10.3969/j.issn.1000-3428.2011.10.0101概述到节点j的连接路径，2个节点之间的直接连接(不包含中间因特网规模的日益扩展使得对网络性能进行监控和测量节点)称为链路。拓扑结构如图1所示。越来越重要。针对传统的网络性能测量方法的局限性，一些[1]研究者提出了网络层析技术，通过端到端测量到的结果，利用统计推断技术估计网络内部性能(包括丢包率、时延和流量等)。由于无需网络内部节点的协作，确保用户的信息安全并能减少网络负载，因此网络层析已成为当前网络测量

6、领域的一个研究热点。网络性能测量中时延性能检测是网络层析技术的一个重图1拓扑结构要研究内容。目前的研究方法主要有2种模式：离散时延模当探测包经过一条链路l时，会产生一个时间延时值xl，[2-3]式和连续时延模式。离散时延模式是把链路时延离散成几每个探测包在所有链路上时间延时值表示为一个向量X=个量化当元(bins)，然后利用迭代算法推断出在各个bins上的(xl∈VS)；同样，每个探测包经过一条路径p(从源节点到叶节概率大小。离散时延模式的主要缺点在于：(1)在算法应用之点)也会产生一个时间延时值，表示为yp，每个探测包在所有前应该选好合适的bins大小，但在内部链路的统计未知情况路径上

7、的延时值表示为一个向量Y=(yp∈R)；A=(aij)是网络路下这是不可能的。(2)固定的bins大小实际上对链路间延时有由矩阵，由

8、R

9、行和(

10、V-1

11、)列构成，当从源节点0到叶节点i很大偏差的情况是不适用的。(3)当bins比较大或者网络拓扑的路径上包含链路j时，aij=1；否则，aij=0。这样，Y与X比较大时，这些方法计算复杂性比较大。为了克服bins的问满足关系式：Y=AX。由观察到的Y的数据估计出X的值，[4