一种自底向上的推测链路延迟分布的快速算法  

Fast bottom up algorithm to infer link delay distributions

作　　者：苏海波[1] 金德鹏[1] 曾烈光[1] 

机构地区：[1]清华大学电子工程系微波与数字通信国家重点实验室,北京100084

出　　处：《计算机应用研究》2011年第9期3455-3458,共4页Application Research of Computers

基　　金：国家"973"计划资助项目(2007CB310701);国家"863"计划资助项目(2008AA01A331;2008AA01Z107)

摘　　要：网络层析技术用端到端的测量结果来推测网络中的链路延迟分布。这方面已有的大部分工作都基于最大似然估计式(MLE)和期望最大化(EM)算法,它们在求解过程中需要不断迭代,对于大规模网络需要消耗很长的时间。为了克服这方面的不足,提出了一种快速算法FBA,该算法自底向上估计出每层链路的延迟分布。定性的分析和实验仿真结果表明FBA大大减小了计算的复杂度,而且在发包数目足够多的情况下,它的估计结果的精确度接近EM算法。Network tomography uses end-to-end measurements to estimate the link delay distribution.The existing work based on maximum likelihood estimator（MLE） and expectation maximization（EM） algorithm uses iterative approximation to make the estimation,which consumes a long time for large scale network.To overcome this limitation,this paper proposed a fast algorithm named FBA.The FBA estimated the link delay distributions level by level from bottom to up.The analytical and simulation results show that the FBA greatly reduces the computational complexity.In addition,the estimation accuracy of the FBA is close to that of the EM algorithm with enough probing packets.

关 键 词：网络层析 链路延迟分布 网络测量 组播树 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]