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

计算机工程 ›› 2018, Vol. 44 ›› Issue (8): 273-278. doi: 10.19678/j.issn.1000-3428.0048088

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

基于Counting Bloom Filter的流抽样算法研究

翟金凤 1,孙立博 1,鲁凯 2,林学勇 2,秦文虎 1   

  1. 1.东南大学 仪器科学与工程学院,南京 210096; 2.南京市计量监督检测院,南京 210049
  • 收稿日期:2017-07-24 出版日期:2018-08-15 发布日期:2018-08-15
  • 作者简介:翟金凤(1995—),女,硕士研究生,主研方向为无线传感网络、网络安全、虚拟现实;孙立博,副教授、博士;鲁凯,工程师;林学勇,高级工程师;秦文虎,教授、博士。
  • 基金资助:

    国家质量监督检验检疫总局科技计划项目“网络公正性检测方法研究”(2015QK059);中央高校基本科研业务费专项(2242017K40114);江苏省重点研发计划项目“智能网联汽车车载网络架构设计及其信息安全防护关键技术研发”(BE2017035)。

Research on Flow Sampling Algorithm Based on Counting Bloom Filter

ZHAI Jinfeng 1,SUN Libo 1,LU Kai 2,LIN Xueyong 2,QIN Wenhu 1   

  1. 1.School of Instrument Science and Engineering,Southeast University,Nanjing 210096,China; 2.Nanjing Metrology Supervision and Inspection Institute,Nanjing 210049,China
  • Received:2017-07-24 Online:2018-08-15 Published:2018-08-15

摘要:

为适应高速网络环境并实现对网络流量的准确测量,提出一种将计数型布隆过滤器结构与基于报文的流抽样技术相结合的网络流等概率抽样算法。利用4 bit的Counter向量识别是否有新流出现,通过实时调整抽样频率弥补新流判定中的错误率,从而对网络流进行等概率抽样 并获取较真实的网络流分布情况。实验结果表明,该算法的测量结果与网络流真实值较接近,且具有可扩展性,可以满足当前复杂多变的高速网络环境下的流量测量需求。

关键词: 高速网络, 流抽样, 计数型布隆过滤器, 等概率抽样, 哈希函数, Counter向量

Abstract:

In order to adapt to the high-speed network environment and realize the accurate measurement of network traffic,a network algorithm of flow equal probability sampling based on the combination of Counting Bloom Filter and packet-based flow sampling technique is proposed.It identifies whether there is a new flow by the 4 bit Counter vector,and realizes the equal probability sampling of the network flow by adjusting the sampling frequency constantly to compensate for the error rate of the new flow judgement.Then,it makes an equal probability sampling of network flow and obtains a more realistic distribution of network traffic.Experimental results show that the algorithm’s measurement results are close to the real value of network flow,and it has scalability,which can meet the current demand of traffic measurement in the complex and changeable high-speed network environment.

Key words: high-speed network, flow sampling, Counting Bloom Filter, equal probability sampling, hash function, Counter vector

中图分类号: