基于抽样和两级CBF的长流识别算法  

Algorithm based on sample and two CBF for elephant flows identification

作　　者：翟金凤 孙立博[1] 鲁凯 林学勇 秦文虎[1] ZHAI Jinfeng;SUN Libo;LU Kai;LIN Xueyong;QIN Wenhu(School of Instrument Science and Engineering,Southeast University,Nanjing 210096,China;Nanjing Metrology Supervision and Inspection Institute,Nanjing 210049,China)

机构地区：[1]东南大学仪器科学与工程学院,江苏南京210096 [2]南京市计量监督检测院,江苏南京210049

出　　处：《中国测试》2018年第7期105-109,共5页China Measurement & Test

基　　金：国家质量监督检验检疫总局科技计划项目(2015QK059);江苏省重点研发计划项目(BE2017035);中央高校基本科研业务费专项(2242018K40062)

摘　　要：为满足高速网络流量测量需求,结合网络流显著的重尾分布特征,提出一种基于抽样和两级CBF的长流识别算法,先对观测时间内链路上通过的报文进行系统抽样,继而利用两级CBF对被抽样报文分别进行长流过滤和流长计数处理,最后再利用第二级CBF继续对所有未被抽样的报文进行查询,统计出长流所含的总报文数。实验验证该算法能在有效节约空间和时间资源的基础上,既实现对长流的准确识别,又实现对原始流长度的高精度测量,识别出的长流信息与真实信息完全相同。同时,该算法还具有可扩展性,一定误差范围内可以选用相对简单的哈希算法,或者使用硬件实现,进一步提高算法的处理效率。In order to meet the demand of high-speed network traffic measurement,an algorithm based on sample and two CBF for elephant flows identification is proposed,combined with the prominent heavy-tail distribution characteristics of network flow.Carry out system sampling of packets over the link during the observation time,and then conduct processes of elephant flows filtration and flow length statistics for sampled packets by two CBF.Finally,use the second counting bloom filter to continuously query all the remaining packets,and count the total number of packets contained in the elephant flows.Experiment results show that the algorithm can realize accurate identification of elephant flows and high precision measurement of the original flow length,saving space and time effectively,with the elephant flow information identified exactly the same as the real information.Meanwhile,it is also scalable,using relatively simple hash algorithms within a certain error range or hardware to further improve the processing efficiency.

关 键 词：网络流量测量 长流识别 抽样 计数型布隆过滤器 阈值 

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