一种快速精确的网络链路丢包率算法研究

马宏艳

摘 要：针对多源多播网络链路丢包率的算法的研究，提出在多源多播网络中，将修正后的PMLE算法和加权平均算法相结合的新算法，可以快速精确地计算网络链路的丢包率，通过NS 2仿真实验，验证了新算法推测链路丢包率速度快，更接近真实值。

关键词：多播；网络链路；丢包率；网络仿真软件

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2015）04-00-04

0 引 言

随着网络的迅速发展，各种类型网络业务也不断的增长，高质量的网络服务也迫在眉睫，对现有网络结构的了解是高效管理的前提，因此网络拓扑结构推测算法的研究成了重点。研究结果表明多源网络结构更接近实际的网络，端到端的主动测量技术中，探测包之间具有很强的相关性，通过研究探测包的丢包率可以推断网络的拓扑结构。

1 多源测量技术

多源测量[1-3]，也称多点测量，多源测量技术是采用多个源节点对多个目的节点的端到端测量，是单源测量方法的扩展。在实际网络测量的过程中，许多网络需要通过多源测量技术才能覆盖到所有的链路。在图1所示的网络拓扑中，有两个发送源节点分别是0和1，节点2和3是网络的内部节点，节点4和5作为网络的接收节点。如果采用单点测量技术，产生的测量子树1并不能覆盖网络中的所有链路。同理，如果把节点1作为探测包的发送源时产生的测量子树2也不能覆盖所有的链路。这时，就需要用到多点测量技术，即从节点0和1同时发送数据包，才能得到完全的网络性能参数。

2 多源多播丢包率的算法

多播丢包率推断算法是利用探测包之间的相关性进行估计。在一个深度大于1的网络拓扑中，从源节点发出的探测包到达每个分支节点后被复制，然后传输到达下一个节点，直至目的节点。对于每一个探测包来说，如果这个包到达了目的节点，那么它一定先经过内部分支节点。接收端的每个探测包，在共享链路上一定具有完全相同的性能，即这些探测包之间是完全相关的，利用这种相关性就可以推导出给定节点的成功传输概率。常见算法包括DE（Direct Estimation）算法，EM（Expectation Maximum）算法和PMLE（Pseudo Maximum Likelihood Estimate）算法。DE和EM计算量大，计算效率低。PMLE算法，又称为快速算法，它是极大似然估计算法的一种近似[4]。

重复以上过程计算出所有的网络链路的探测包。但是当多个子节点同时未收到探测包时，PMLE算法将默认这些子节点的父节点也没有收到探测包。多个子节点同时发生丢包的可能性很小； PMLE算法的计算过程是自底向上的，当对父节点的估计出现误差后，这种误差随着拓扑结构中层级递增而递增，也会层间叠加。如果一个网络拓扑结构的层级越多，使用PMLE算法推断出的链路丢包率误差越大。

2.2 u-PMLE算法

5 结 语

本文结合PMLE算法和加权平均算法二者的优势，将基于u-PMLE算法的加权平均算法应用于多源网络中，推测出整个网络的丢包性能。比较得出基于PMLE的加权平均算法和基于u-PMLE的加权平均算法，证明提出的算法是更精确的网络链路丢包率的算法。

参考文献

[1] Rabbat M， Coates M， Nowak R. Multiple Source Internet Tomography[J]. IEEE Journal on Selected Areas in Communications，2006（12）：2221-2234.

[2] Yongjun Li， Wangdong Cai. A Fast Multicast-based Approach to Inferring Loss Performance[J]. Communication and Computer， 2006， 3（3）：19-24.

[3] 吴文佳，张建中，张元鹏.基于丢包率的多播网络拓扑推断算法[J].计算机工程，2010（1）：124-126.

[4] 何仁清.基于网络透视技术的丢包率推理算法研究[D].哈尔滨：哈尔滨工业大学，2006.

[5] 林文.基于网络层析的丢包率推断算法研究[D].厦门：厦门大学，2009.

[6] Liao Hailiang， Hu Guangmin， Qian Feng， et al. Network Topology Inference Based on Traceroute and Tomography[J]. Journal of Software， 2010，21（1）： 133-146.

[7] 费高雷.基于单播端到端测量的网络性能参数估计方法研究[D].成都：电子科技大学，2012.

[8] 吴光伟，刘双艳，宋进.基于网络断层扫描的传感器网络链路丢包研究[J]. 计算机技术与发展，2012，22（3）：64-66，70.