REFI: Extracting out heavy-hitter flows accurately and rapidly

Along with the improvement of network bandwidth, identifying heavy-hitter flows on-line is more significant for some network application, such as congestion controlling, anomaly detecting and so on. In this paper, we propose a novel algorithm REFI (Replacement-based Flow Identifying) to extract heavy-hitter flows online. On the basis of LRU replacement, REFI introduces flow size factor σ and modulating factor M. Using the two factors, REFI can avoid discarding heavy-hitter flows with very low processing cost. We evaluate the performance of REFI through mathematical analysis and through experiments. Exploiting the distribution characteristics of network traffic, REFI can identify heavy-hitter flows accurately with low memory space and memory accessing. In simulated experiments, REFI shows superior processing speed and acceptable measurement accuracy.