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

Previous Articles     Next Articles

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)

225

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

CLC Number: 

  • 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] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd