作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

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

王宜青,陈庶樵,马海龙   

  1. (国家数字交换系统工程技术研究中心,郑州 450002)
  • 收稿日期:2013-03-01 出版日期:2014-04-15 发布日期:2014-04-14
  • 作者简介:王宜青(1986-),男,硕士研究生,主研方向:宽带信息网络;陈庶樵,教授、博士;马海龙,讲师、博士。
  • 基金资助:
    国家科技重大专项基金资助项目(2009ZX03004-002)。

Network Data Flow Statistics Based on Counting Bloom Filter

WANG Yi-qing, CHEN Shu-qiao, MA Hai-long   

  1. (National Digital Switching System Engineering Technological R&D Center, Zhengzhou 450002, China)
  • Received:2013-03-01 Online:2014-04-15 Published:2014-04-14

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

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

Abstract: 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.

Key words: Counting Bloom Filter(CBF), flow measurement, network measurement, full-flow statistics, packet statistics, flow statistics

中图分类号: