摘要： 针对最近最久未使用(LRU)算法在高速网络中大流漏判率高的缺陷，提出一种基于多粒度最近最久未使用检测算法。该算法采用分层多粒度压缩计数机制对高速网络数据抽样，提高对长流的识别精度。基于实际的互联网数据进行仿真实验，结果表明，在给定条件下，该方法的内存占用量为LRU算法的50%，测量误差仅为LRU算法的10%。

关键词: 流量测量, 多粒度压缩计数, 最近最久未使用

Abstract: Aiming at the lack of the high false negative ratio of Least Recently Used(LRU) algorithm in high-speed network traffic measurement, this paper proposes a new algorithm which is based on the Multi-Granularity Least Recently Used(MGLRU). The algorithm employs hierarchical multi-granularity compression counting mechanism for high-speed network data sampling, and improves the accuracy of the long-term flow detection. And based on the real Internet data, simulation results show that: in the given conditions, the algorithm uses about 50 percent of the memory consumption and has 10 percent of relative error compared with the LRU algorithm.

Key words: traffic measurement, multi-granularity compressed counting, Least Recently Used(LRU)

中图分类号: 

• TP393