基于TCBF_LRU的高速网络大流检测算法

A TCBF_LRU Algorithm for Identifying and Measuring Elephant Flows in High Speed Network Flows

在高速主干网络中,随着网络链路速率的不断提高和网络流数量的急速增加,同时受到硬件计算和存储资源的限制,如何及时、准确地在海量数据中,有效地检测出其中的大流信息,成为目前大规模高速网络流测量的热点问题.根据传统的LRU算法容易淘汰大流和频繁更新给系统带来巨大压力的缺陷,提出一种新的大流检测算法——TCBF_LRU算法,用于高速网络大流信息识别.算法通过时间超时和大流报文预保护策略,过滤大部分的小流报文,极大减少LRU算法小流置换大流的概率,提高算法的准确性.分析了算法的误判率和复杂度,并通过实际主干网trace数据,实验分析了算法参数配置对于大流检测准确性的影响.理论分析和仿真结果表明,与标准LRU算法和BF_LRU算法相比,在使用相同的缓存空间下,TCBF_LRU算法具有更高的测量准确性和实用性.

In the high-speed backbone network,with the increasing speed of network link,the number of network flows increase rapidly.Meanwhile,with restrictions on hardware computing and storage resources,so,how to identify and measure elephant flows timely and accurately in massive data become a hot issue in high speed network flow measurement area.In this paper,we propose a new algorithm based on TCBF_LRU to realize elephant flow identification,according to the defect of traditional LRU algorithm which discards elephant flows easily and update system frequently when large numbers of mice flows arrive.By using time out and pre-protection method,the algorithm can filtrate most of the mice flows,reduce the probability of mice flows displacement elephant flows in LRU algorithm,and improve the accuracy of the algorithm.The complexity and error rate of the algorithm was analyzed. The influence of elephant flow measurement accuracy for parameter configuration was analyzed through the actual backbone trace data.The theoretical analysis and the simulation result indicate that compare to the standard LRU algorithm and BF_LRU algorithm,with the same cache space,our algorithm can identify elephant flow more accurately and practicality.