一种高精度均匀取样算法及其网络应用

为解决按比例均匀取样问题,简要分析了一般取样方法的不足,提出了一种可实现高精度任意比例的均匀取样算法,该算法理论上可实现零误差的任意比例均匀取样。介绍了该算法的原理,并对其实现过程进行了详细阐述。针对该算法在网络中的2种典型应用,详细阐述包括速率限制、流量整形中常用的令牌桶算法的实现以及网络损伤中按比例均匀丢包的实现。最后利用网络测试仪器对该算法在FPGA上的实现进行了测试,测试结果显示,利用该算法实现的限速和均匀丢包误差均小于10^-5。

A High-precision Uniform Sampling Algorithm and Its Network Applications

To resolve the problem of proportionally uniform sampling,this paper analyzes briefly the shortcomings of the general sampling method,and proposes a high-precision uniform sampling algorithm with arbitrary proportions.The algorithm can theoretically achieve zero error sampling at arbitrary proportions.Firstly,the principle of the algorithm is introduced,and the implementation process is elaborated.Then,the two typical applications of the algorithm in the network are elaborated,including the implementation of the token bucket algorithm commonly used in rate limiting and traffic shaping,and the implementation of proportionally uniform packet loss in network impairment.Finally,the implementation of the algorithm on FPGA is tested by using network testing instrument.The test results show that the error range of speed limit and uniform packet loss rate achieved by this algorithm are less than10^-5.