Abstract: In high-speed network, finding out the heavy flows is becoming a more important, precise and extendible way to measure the network. As a structure used in network measurement, Counting Bloom Filter（CBF） is easy to overflow, pointing to this shortcomings, it is extend to do better in net flow measurement. Besides, LRU is combined with extended CBF, through verification of theory, this flow measurement module LRU_MCBF uses little memory, has low time complexity. The emulational experiments also prove that LRU_MCBF has lower missing rate and error rate, and heavy flows can be find out preciously in high-speed network.

Key words: Count Bloom Filter（CBF）, flow measurement, heavy flow, Least Recently Used（LRU）

摘要： 高速网络流量检测中的大流检测已成为当前一种重要的、高效准确的可扩展流量测量机制，针对CBF（Count Bloom Filter）容易溢出的问题，将扩展的CBF应用于流量测量，防止过滤器溢出，并且结合LRU链表存储机制，共同应用于网络大流检测之中。经理论分析，所研究的流量测量算法LRU_MCBF（Least Recently Used_Multiple Count Bloom Filter）占用空间小，时间复杂度低；通过仿真实验验证了LRU_MCBF在大流测量中漏报率和错报率较低，能实现高速网络环境下大流对象的准确提取。

关键词: 计数型布鲁姆过滤器, 流量测量, 大流, 最近最少使用（LRU）