基于计数型Bloom过滤器的网络数据流统计

现有的流统计信息主要侧重于流抽样而忽视全流统计。为此,提出一种使用优化设计的计数型Bloom过滤器流统计方法。针对计数型Bloom过滤器数据增长带来的计数器溢出和假阳性错误率增高的问题,分别设计动态统计和多个计数器协同统计的方案。概要化的存储结构可方便查询,而且其计数型Bloom过滤器简单的数据结构也易于硬件实现。实验结果表明,与传统哈希方法相比,计数型Bloom过滤器流统计方法的时间复杂度更低,可用于网络应用中的快速全流统计。

Network Data Flow Statistics Based on Counting Bloom Filter

The current research on flow statistics information focuses primarily on flow sampling, which ignores full-flow statistics. A method of optimized designed Counting Bloom Filter（CBF） used for flow statistics is proposed. According to counter overflow and growth of positive error as a result of data increasing, scheme of dynamic statistics and multiple counter statistics in coordination are separately proposed. Its summary storage structure is easy to be inquired, and data structure of CBF can be easily implemented in hardware. Experimental results show that the time complexity of CBF used for flow statistics is lower than the traditional Hash method, which can be used in fast full flow statistics in network applications.