一种新的基于LRU的大流检测算法

New Algorithm Based on LRU for Identify and Measuring Large Flows

针对LRU(Least Recently Used)算法大流漏检率过高的问题,提出了一种采用CBF(Counting Bloom Filter)和LRU两级结构的大流检测算法。该算法根据大流占用带宽较大、持续时间较长的特点在CBF中引入时间窗口机制来滤出可能的大流,然后将流信息记录在LRU中作进一步筛选。从理论上分析了影响该算法性能的因素,考虑了在存储资源一定的条件下,如何设置参数以发挥该算法最大效能的问题。最后基于实际的互联网数据进行了对比验证。结果表明,与同类算法相比,该算法在有效降低大流漏检率的同时,提高了大流流量的测量精度。

Aiming at the LRU（Least Recently Used） algorithmt problem of high false negative probability, a two-stage structure algorithm based on CBF（ Counting Bloom Filter）and LRU is presented. According to the characteristics of the large bandwidth and long d^ation, the algorithm introduces time window mechanism to filter the probable large flow and saves the flow message in LRU for further screening. Analyzing the effect factors of the algo- rithm in theory and considering the question that how to set parameters with limited storage resources to wake the algorithm maximum efficiency, Experi- ments are also conducted based on real network traces. The results indicate that the algorithm can reduce the false negative probability. Meanwhile, the accuracy of large flow measuring is improved.