基于DCBF的流抽样测量算法

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (17): 92-95.

基于DCBF的流抽样测量算法

孟金凤，高仲合

曲阜师范大学计算机科学学院，山东日照 276826

出版日期:2015-09-01 发布日期:2015-09-14

Flow sampling measurement algorithm based on dynamic counting bloom filter

MENG Jinfeng, GAO Zhonghe

School of Computer Science College, Qufu Normal University, Rizhao, Shandong 276826, China

Online:2015-09-01 Published:2015-09-14

摘要/Abstract

摘要： 为了提高系统的处理效率，减少系统的测量误差，提出了一种基于动态计数型布鲁姆过滤器（Dynamic Counting Bloom Filter，DCBF）的流抽样测量算法。该算法使用基于报文级别的抽样，并通过DCBF进行流查找和统计，且在CBF计数器溢出时动态增加新的CBF。经理论分析和实验表明，该算法不仅提高了系统的运行效率，减少了存储空间的消耗，同时具有准确性和可扩展性，能很好地适用于高速链路的流量测量中。

关键词: 动态计数型布鲁姆过滤器（DCBF）, 流抽样, 哈希函数, 误称率

Abstract: In order to improve the processing efficiency of the system and reduce the error rate of the measurement, the paper puts forward a flow sampling measurement algorithm based on Dynamic Counting Bloom Filter （DCBF）. The method samples on message level, then searches and counts the flow with the DCBF. It can add a new CBF dynamically when the CBF overflows. The theoretical analysis and experiments show that it can not only improve the operation efficiency of the system and reduce the consumption of the storage space, but also have a good result on the accuracy and scalability. It can be very suitable for high speed link.

Key words: Dynamic Counting Bloom Filter（DCBF）, flow sampling, Hash function, false positive rate

孟金凤，高仲合. 基于DCBF的流抽样测量算法[J]. 计算机工程与应用, 2015, 51(17): 92-95.

MENG Jinfeng, GAO Zhonghe. Flow sampling measurement algorithm based on dynamic counting bloom filter[J]. Computer Engineering and Applications, 2015, 51(17): 92-95.

[1]	邓清文，林志贤，郭太良. 一种基于主成分的多表图像哈希检索方法[J]. 计算机工程与应用, 2018, 54(3): 192-199.
[2]	李娟娟1，龚向阳2. 快速检测RFID复制标签的算法研究[J]. 计算机工程与应用, 2017, 53(8): 106-112.
[3]	罗俊，李劲华. LSHBMRPK-means算法及其应用[J]. 计算机工程与应用, 2017, 53(21): 62-67.
[4]	黄萍，杨小东，王彩芬. 强不可伪造的在线/离线签名方案[J]. 计算机工程与应用, 2016, 52(3): 81-84.
[5]	余纯武，郭龙飞，张健. 轻量哈希函数HBL[J]. 计算机工程与应用, 2016, 52(20): 1-4.
[6]	温雅敏1，黎凤霞2，龚征3，唐韶华2. 低功耗AVR微处理器上Quark哈希算法优化实现[J]. 计算机工程与应用, 2014, 50(23): 104-107.
[7]	于志轩，王彩芬，罗海，冯帆. 一种可确认身份的网络编码签名方案[J]. 计算机工程与应用, 2011, 47(28): 73-76.
[8]	张恒山，管会生，韩海强. RFID系统中基于公钥加密的相互认证协议[J]. 计算机工程与应用, 2010, 46(5): 69-72.
[9]	董斌¹，张敏情¹，杨晓元^1，2，周宣武¹. 一种离线半可信第三方的公平交换协议[J]. 计算机工程与应用, 2009, 45(35): 88-90.
[10]	侯爱琴¹，杨世勇²，葛建华². 具有消息自恢复的ECC认证加密方案[J]. 计算机工程与应用, 2009, 45(30): 118-120.
[11]	徐伟¹,赵嵩正¹,刘洪宇². 融合多特征算法的电子印鉴系统研究[J]. 计算机工程与应用, 2009, 45(10): 238-241.
[12]	刘元珍,刘渊,李小航. 基于DCF的资源可控流抽样[J]. 计算机工程与应用, 2008, 44(19): 127-128.
[13]	马靖善¹,陈世亮²,赵雪露²,刘卫江³. 一种新的估计流长度分布的方法[J]. 计算机工程与应用, 2008, 44(18): 119-120.