一种高精度均匀取样算法及其网络应用
|
摘要
为解决按比例均匀取样问题,简要分析了一般取样方法的不足,提出了一种可实现高精度任意比例的均匀取样算法,该算法理论上可实现零误差的任意比例均匀取样。介绍了该算法的原理,并对其实现过程进行了详细阐述。针对该算法在网络中的2种典型应用,详细阐述包括速率限制、流量整形中常用的令牌桶算法的实现以及网络损伤中按比例均匀丢包的实现。最后利用网络测试仪器对该算法在FPGA上的实现进行了测试,测试结果显示,利用该算法实现的限速和均匀丢包误差均小于10~(-5)。
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 than 10~(-5).
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 than 10~(-5).
引文
[1] Heinanen J,Guerin R. IETF RFC 2697:A Single Rate Three Color Marker[R]. Philadelphia,PA,USA:University of Pennsylvania,1999.
[2] Heinanen J,Guerin R.IETF RFC 2698:A Two Rate Three Color Marker[R]. Philadelphia,PA,USA:University of Pennsylvania,1999.
[3] Volker R. Accurate Traffic Shaping Algorithms for IEEE802.16-2012 Based Wi MAX Networks[J].Wireless Communication Systems(ISWCS),2016(9):218-224.
[4] Farzaneh,Yashar,Mardi.A Qo S-aware Downlink Packet Scheduler Using Token Bucket Algorithm for LTE Systems[J]. Electrical Engineering(ICEE),2014(5):1775-1780.
[5] Faheem,Humayun,Fahd.Performance Analysis of a Token Bucket Shaper for MPEG4 Video and Real Audio Signal[J]. Smart Instrumentation, Measurement and Applications(ICSIMA),2013(11):1-4.
[6]刘治国,史二鑫,马悦.基于动态令牌桶的卫星网络带宽分配方法[J].计算机工程,2016(2):93-97.
[7]王汝言,池文祥,张鸿.WOBAN中基于令牌桶算法的自适应流量整形策略[J].电子与信息学报,2017(6):1401-1408.
[8]马徐瀚,吴龙胜,赵坤鹏.一种基于多令牌桶的数据风暴抑制单元[J].微电子学与计算机,2016(9):84-88.
[9]费嘉.浅析Qo S中的令牌桶算法[J].邮电设计技术,2014(6):54-57.
[10]杨冬,孙剑伟.基于令牌桶算法的卫星数据地面传输流量控制方法研究[J].软件,2016,37(3):99-103.
[11]吕华辉,林志达,黄宏聪.业务优先级感知的网络流量调度机制[J].电信科学,2017(7):151-158.
[12]张建立.网络损伤仿真系统设计与开发[J].数字技术与应用,2016(9):170.
[13]李晓莉,郭宇春.QoS技术中令牌桶算法实现方式比较[J].中兴通讯技术,2007(6):56-60.
[14]王勇,叶明川.基于图形分类的令牌桶流控算法[J].桂林电子科技大学学报,2015,35(5):391-394.
[15]李建东,郑杰,刘勤,等.异构协作网络中采用令牌漏桶的多接入业务分配算法[J].西安大学学报,2014,48(8):7-11.
[16]刘宇翔.基于令牌桶算法的交换网流量控制方法[D].西安:西安电子科技大学,2014.
[17]王志,田晓,彭月川.网络损伤模拟环境的设计与实现[J].计算机工程与设计,2017(10):2858-2863.
[18]孙艺桐.模拟网络损伤装置的研究与实现[D].上海:上海交通大学,2012.
[2] Heinanen J,Guerin R.IETF RFC 2698:A Two Rate Three Color Marker[R]. Philadelphia,PA,USA:University of Pennsylvania,1999.
[3] Volker R. Accurate Traffic Shaping Algorithms for IEEE802.16-2012 Based Wi MAX Networks[J].Wireless Communication Systems(ISWCS),2016(9):218-224.
[4] Farzaneh,Yashar,Mardi.A Qo S-aware Downlink Packet Scheduler Using Token Bucket Algorithm for LTE Systems[J]. Electrical Engineering(ICEE),2014(5):1775-1780.
[5] Faheem,Humayun,Fahd.Performance Analysis of a Token Bucket Shaper for MPEG4 Video and Real Audio Signal[J]. Smart Instrumentation, Measurement and Applications(ICSIMA),2013(11):1-4.
[6]刘治国,史二鑫,马悦.基于动态令牌桶的卫星网络带宽分配方法[J].计算机工程,2016(2):93-97.
[7]王汝言,池文祥,张鸿.WOBAN中基于令牌桶算法的自适应流量整形策略[J].电子与信息学报,2017(6):1401-1408.
[8]马徐瀚,吴龙胜,赵坤鹏.一种基于多令牌桶的数据风暴抑制单元[J].微电子学与计算机,2016(9):84-88.
[9]费嘉.浅析Qo S中的令牌桶算法[J].邮电设计技术,2014(6):54-57.
[10]杨冬,孙剑伟.基于令牌桶算法的卫星数据地面传输流量控制方法研究[J].软件,2016,37(3):99-103.
[11]吕华辉,林志达,黄宏聪.业务优先级感知的网络流量调度机制[J].电信科学,2017(7):151-158.
[12]张建立.网络损伤仿真系统设计与开发[J].数字技术与应用,2016(9):170.
[13]李晓莉,郭宇春.QoS技术中令牌桶算法实现方式比较[J].中兴通讯技术,2007(6):56-60.
[14]王勇,叶明川.基于图形分类的令牌桶流控算法[J].桂林电子科技大学学报,2015,35(5):391-394.
[15]李建东,郑杰,刘勤,等.异构协作网络中采用令牌漏桶的多接入业务分配算法[J].西安大学学报,2014,48(8):7-11.
[16]刘宇翔.基于令牌桶算法的交换网流量控制方法[D].西安:西安电子科技大学,2014.
[17]王志,田晓,彭月川.网络损伤模拟环境的设计与实现[J].计算机工程与设计,2017(10):2858-2863.
[18]孙艺桐.模拟网络损伤装置的研究与实现[D].上海:上海交通大学,2012.