作者：翟金凤¹, 孙立博¹, 鲁凯², 林学勇², 秦文虎¹

作者单位：1. 东南大学仪器科学与工程学院, 江苏 南京 210096;
2. 南京市计量监督检测院, 江苏 南京 210049

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

摘要：

为满足高速网络流量测量需求，结合网络流显著的重尾分布特征，提出一种基于抽样和两级CBF的长流识别算法，先对观测时间内链路上通过的报文进行系统抽样，继而利用两级CBF对被抽样报文分别进行长流过滤和流长计数处理，最后再利用第二级CBF继续对所有未被抽样的报文进行查询，统计出长流所含的总报文数。实验验证该算法能在有效节约空间和时间资源的基础上，既实现对长流的准确识别，又实现对原始流长度的高精度测量，识别出的长流信息与真实信息完全相同。同时，该算法还具有可扩展性，一定误差范围内可以选用相对简单的哈希算法，或者使用硬件实现，进一步提高算法的处理效率。

Algorithm based on sample and two CBF for elephant flows identification

ZHAI Jinfeng¹, SUN Libo¹, LU Kai², LIN Xueyong², QIN Wenhu¹

1. School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China;
2. Nanjing Metrology Supervision and Inspection Institute, Nanjing 210049, China

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

Keywords: network traffic measurement; elephant flows identification; sample; counting bloom filter; threshold

2018, 44(7): 105-109  收稿日期: 2017-09-23;收到修改稿日期: 2017-11-28

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

作者简介: 翟金凤(1995-),女,江苏泰州市人,硕士研究生,专业方向为虚拟现实。

参考文献

[1] HAWA M, RAHHAL J S, ABU-AL-NADI D I. File size models for shared content over the BitTorrent Peer-to-Peer network[J]. Peer-to-peer Networking and Applications, 2012, 5(3):279-291.
[2] 张淋淋, 高仲合. 基于LRU_CBF的大流识别算法[J]. 电子技术, 2015, 44(3):39-42.
[3] 刘晓陆, 刘渊, 王春龙. 一种基于FEFS与CBF的网络大流识别算法[J]. 计算机工程, 2015, 41(9):68-73.
[4] HU C, LIU B, WANG S, et al. ANLS:Adaptive non-linear sampling method for accurate flow size measurement[J]. IEEE Transactions on Communications, 2012, 60(3):789-798.
[5] MORI T, UCHIDA M, KAWAHARA R, et al. Identifying elephant flows through periodically sampled packets[C]//The Institute of Electronics, Information and Communication Engineers, 2004:115-120.
[6] 景泉, 白磊, 刘卫江. 基于抽样技术与哈希技术结合的长流识别算法的研究[J]. 辽宁工学院学报, 2006(6):376-378.
[7] 景泉. 网络中IP长流识别方法的研究[J]. 信息技术与信息化, 2015(7):199-200, 202.
[8] 吴桦, 龚俭, 杨望. 一种基于双重Counter Bloom Filter的长流识别算法[J]. 软件学报, 2010, 21(5):1115-1126.
[9] 刘元珍. 基于多级CBF的长流识别[J]. 微型电脑应用, 2014, 30(9):60-61, 64.
[10] 张淋淋. 网络流量测量中的抽样算法研究[D]. 曲阜:曲阜师范大学, 2015.
[11] 周爱平, 程光, 郭晓军. 高速网络流量测量方法[J]. 软件学报, 2014(1):135-153.
[12] 林明方. 高速网络流量测量中抽样技术的研究[J]. 硅谷, 2010(10):86, 169.
[13] 李雪梅, 王洪源. 网络流量抽样测量技术综述[J]. 科技信息, 2011(9):61, 117.
[14] 张震, 汪斌强, 张风雨, 等. 基于LRU-BF策略的网络流量测量算法[J]. 通信学报, 2013(1):111-120.
[15] BLOOM B H. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970, 13(7):422-426.
[16] 夏靖波, 任高明. 大流识别方法综述[J]. 控制与决策, 2013, 28(6):801-807.
[17] 白磊, 田立勤, 陈超. 基于流抽样和LRU的高速网络大流检测算法[J]. 计算机应用与软件, 2016, 33(4):111-115.
[18] STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4):341-359.
[19] FAN L,CAO P,ALMEIDA J,et al. Summary cache:a scalable wide-area web cache sharing protocol[J]. IEEE/ACM Transactions on Networking, 2000, 8(3):281-293.