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

• 网络、通信、安全 • 上一篇    下一篇

基于DCBF的流抽样测量算法

孟金凤,高仲合   

  1. 曲阜师范大学 计算机科学学院,山东 日照 276826
  • 出版日期:2015-09-01 发布日期:2015-09-14

Flow sampling measurement algorithm based on dynamic counting bloom filter

MENG Jinfeng, GAO Zhonghe   

  1. School of Computer Science College, Qufu Normal University, Rizhao, Shandong 276826, China
  • Online:2015-09-01 Published:2015-09-14

摘要: 为了提高系统的处理效率,减少系统的测量误差,提出了一种基于动态计数型布鲁姆过滤器(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