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

Network Data Flow Statistics Based on Counting Bloom Filter

作　　者：王宜青[1] 陈庶樵[1] 马海龙[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机工程》2014年第4期277-280,286,共5页Computer Engineering

基　　金：国家科技重大专项基金资助项目(2009ZX03004 002)

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

关 键 词：计数型Bloom过滤器 流量测量 网络测量 全流统计 分组统计 流统计 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]