基于流抽样和LRU的高速网络大流检测算法  

ELEPHANT FLOW DETECTION ALGORITHM FOR HIGH SPEED NETWORKS BASED ON FLOW SAMPLING AND LRU

作　　者：白磊[1] 田立勤[1] 陈超[1,2] 

机构地区：[1]华北科技学院计算机学院,北京101601 [2]浙江大学机械工程学院,浙江杭州310058

出　　处：《计算机应用与软件》2016年第4期111-115,共5页Computer Applications and Software

基　　金：国家重点基础研究发展计划专项(2011CB311809);国家自然科学基金项目(61472137);中央高校基本科研业务费项目(3142014085)

摘　　要：在高速主干网络中,随着网络链路速率的不断提高和网络流数量的增加,如何及时、准确地检测出网络中的大流信息,成为目前网络流测量的热点问题。根据传统LRU算法由于突发性大量小流导致淘汰大流的测量缺陷和网络重尾分布的特点,提出一种新的识别大流的算法——基于流抽样和LRU的大流检测算法。算法通过流抽样技术过滤大部分的小流,并通过LRU算法识别大流信息,将过滤和识别过程分离,减少小流错误淘汰大流的可能性,提高算法测量准确性。分析算法的复杂度和漏检率,并通过实际试验数据分析了算法参数配置对于大流测量的准确性的影响。理论分析和仿真结果表明,与标准LRU算法和LRU_BF算法相比,在使用相同的存储空间下,新算法具有更高的测量准确性和实用性。In high-speed backbone network,with the increasing speed of network link and the augment in network flow numbers,it becomes a hot issue in current network flow measurement that how to detect the elephant flow information in networks timely and accurately.According to the measurement defect of traditional LRU algorithm that the elephant flows be discarded due to bursting large numbers of mice flows and the feature of heavy tail distribution of network,we proposed a new algorithm for identifying elephant flows—an elephant flow detection algorithm based on flow sampling and LRU. The algorithm filtrates most of the mice flows by flow sampling technology,and identifies elephant flows by LRU algorithm. It separates the filtration and recognition processes,reduces the possibility of mice flows phasing out elephant flows incorrectly,and improves measurement accuracy. We analysed the complexity and missing rate of the algorithm,and analysed the influence of algorithm ＇s parameter configuration on accuracy of elephant flows measurement through practical test data.Theoretical analysis and simulation result indicated that compare with standard LRU algorithm and LRU_ BF algorithm,when the memory spaces used were the same,our algorithm had higher measurement accuracy and practicality.

关 键 词：网络测量 大流 抽样 哈希 近期最少使用算法(LRU) 

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