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

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

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