Identifying heavy-hitter flows fast and accurately

摘要

In many applications, such as network congestion monitoring, accounting and network anomaly detection, identifying heavy-hitter flows is very important and imperative. Recent research work on extracting heavy-hitter flows in high-speed network attracts quite a few researchers because of the importance of finding out heavy-hitter flows. However, due to the high speed of network and the ever-growing of flow amount, it's of great significance to identify heavy-hitter flows in high-speed network with much less memory and computational overhead apart from high measurement accuracy. Moreover, it's infeasible to track per-flow statistics to achieve high accuracy because of the limits of both the computational and memory requirements. Consequently, finding a rational way to solve this problem is of great significance. In this paper, a novel scheme named CHHFR (Caching Heavy-hitter Flows with Replacement) is proposed. CHHFR algorithm is based on LRU (Least Recently Used) replacement mechanism but different from it because CHHFR does not only care about the update time of traffic flows when it find a flow to replace. Another parameter named Ctr is added to LRU replacement mechanism to avoid its shortcomings. Through both theoretical analysis and experimental validation of different Internet traces, CHHFR algorithm can achieve a good measurement performance with a higher accuracy at a faster speed compared with the existing methods.