吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (4): 1159-1164.doi: 10.13229/j.cnki.jdxbgxb201404039

• • 上一篇    下一篇

基于LRU淘汰机制的自适应大流检测算法

任高明, 夏靖波, 乔向东, 杨仝   

  1. 空军工程大学 信息与导航学院, 西安 710077
  • 收稿日期:2013-04-07 出版日期:2014-07-01 发布日期:2014-07-01
  • 作者简介:任高明(1986-), 男, 博士生研究生.研究方向:互联网测量.E-mail:gaomingren_928@126.com
  • 基金资助:
    国家自然科学基金项目(61202489); 陕西省自然科学基础研究计划项目(2012JZ8005)

Adaptive algorithm of identifying and measuring elephant flow based on least recently used replacement

REN Gao-ming, XIA Jing-bo, QIAO Xiang-dong, YANG Tong   

  1. College of Information and Navigation, Air Force Engineering University, Xi'an 710077, China
  • Received:2013-04-07 Online:2014-07-01 Published:2014-07-01

RICH HTML

0   

PDF (PC)

243

摘要： 针对现有大流检测算法自适应能力差和难以满足工程应用需求的问题, 提出一种新的基于“最近最久未用”淘汰机制的自适应大流检测算法。该算法设置流归并和LRU两级缓存, 数据分组到达时, 首先进入流归并缓存, 按照“流关键字”通过哈希算法实现数据分组到流的匹配, 并对流大小进行估计;同时根据上一时刻被LRU淘汰流的大小实时调整LRU缓存之前的过滤门限;然后比较流估计值和门限大小, 估计值大于门限的流所含数据分组进入LRU缓存进一步筛选, 否则丢弃。为保证实时性和过滤效果, 分析并提出了门限时长的设置方法。理论推导和实验结果表明:该算法既保证了准确性又提高了自适应性, 更适合工程应用。

关键词: 计算机应用, 网络流量测量, 大流检测, 自适应算法, 最近最久未用

Abstract: The adaptivity of the existing methods of elephant flow identification is poor and can not meet the needs of engineering application. In order to solve this problem, a novel algorithm based on Least Recently Used (LRU) replacement was developed. The algorithm has two caches, flow merge cache and LRU cache. First, the packet goes into flow merge cache and is matched to flow records according to flow keywords, and the length of flow is estimated. In the meantime, the threshold is changed with the previous length of the flow estimated by LRU cache in real time. Then the estimation of the flow is compared with the threshold; if the estimated length of the flow is longer than threshold, the packet belongs to the flow can go into LRU cache and be further filtered, otherwise the packet is abandoned. To guarantee the filtering effect and real-time performance, a method of setting up the threshold of time span was proposed. Theoretical analysis and experiment results illustrate that the algorithm can guarantee the accuracy, improve the adaptivity, and is more suitable for engineering application.

Key words: computer application, traffic measurement, elephant flows, adaptive algorithm, least recently used

中图分类号: 

  • TP393
[1] Estan C, Varghese G, Fisk M. Bitmap algorithms for counting active flows on high speed links[C]∥Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement, ACM, 2003: 153-166.
[2] 张震, 汪斌强, 陈庶樵, 等. 基于多维计数型布鲁姆过滤器的大流检测机制[J]. 电子与信息学报, 2010, 32(7):1608-1613. Zhang Zhen, Wang Bin-qiang, Chen Shu-qiao, et al. A mechanism of identifying heavy hitters based on multi-dimensional counting bloom filter[J]. Journal of Electronics & Information Technology, 2010, 32(7):1608-1613.
[3] 王宏, 龚正虎. Hits和Holds:识别大象流的两种算法[J]. 软件学报, 2010, 21(6):1391-1403. Wang Hong, Gong Zheng-hu. Hits and holds: two algorithms for identifying the elephant flows[J]. Journal of Software, 2010, 21(6):1391-1403.
[4] Zhang Y, Breslau L, Paxson V, et al. On the characteristics and origins of internet flow rates[C]∥ACM SIGCOMM, Pittsburgh, PA, USA, 2002:309-322.
[5] Feldmann A, Greenberg A, Lund C, et al. Deriving traffic demands for operational IP networks: methodology and experience[J]. IEEE/ACM Transactions on Networking, 2001, 9(3):265-280.
[6] Zadnik M, Canini M, Moore A W, et al. Tracking elephant flows in internet backbone traffic with an fpga-based cache[C]∥International Conference on Field Programmable Logic and Applications, IEEE, 2009: 640-644.
[7] Rong Q, Zhang G X, Xie G G. Mnemonic lossy counting: an efficient and accurate heavy-hitters identification algorithm[C]∥The 29th International Performance Computing and Communications Conference, IEEE, 2010:233-255.
[8] Cristian E, George V. New direction in traffic measurement and accounting[J]. SIGOMM Computer Communication Review, 2002, 32(4):323-336.
[9] Hong W, Zheng H G, Qing G, et al. Detection network anomalies based on packet and flow analysis[C]∥Seventh International Conference on Networking, IEEE, 2008: 497-502.
[10] 谢冬青, 周再红, 骆嘉伟. 基于LRU和SCBF的大象流提取及其在DDoS防御中的应用[J]. 计算机研究与发展, 2011(8):1517-1523. Xie Dong-qing, Zhou Zai-hong, Luo Jia-wei. An algorithm based on LRU and SCBF for elephant flows identification and its application in DDoS defense[J]. Journal of Computer Research and Development, 2011(8):1517-1523.
[11] Cisco Netflow.[DB/OL].[2006-07-19].http://www.cisco.com/en/US/products/ps6601/products_ios_protocol_group_home.html.
[12] Kim I, Reddy A L N. Identifying long-term high-bandwidth flows at a router[C]∥Proceedings of the 8th International Conference on High Performance, Berlin, Springer, 2001: 361-371.
[13] 裴育杰, 王洪波, 程时端. 基于两级LRU机制的大流检测算法[J].电子学报, 2009, 37(4):684-691. Pei Yu-jie, Wang Hong-bo, Cheng Shi-duan. A dual-LRU based algorithm for identifying and measuring large flows[J]. Acta Electronic Sinica, 2009, 37(4): 684-691.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发