NewKeeper: An Efficient and Fast Algorithm for Finding Top-k Elephant Flow

Finding top-k elephant flows in high-speed networks has been a critical task in recent years. Previous works focus on flow sizes, where they only keep elephant flows and expel mouse flows based on sizes. However, due to the non-uniform network traffic distribution and limited hardware resources, real elephant flows tend to be overwhelmed by numerous mouse flows, making it difficult for its size to be accurately recorded and thus misjudged. To address this issue, we introduce a new strategy called count-new-expel-old and propose an algorithm called NewKeeper based on it, separating elephant flows from mouse flows by expelling the oldest flow instead of the smallest one. Besides, we optimize the tracking process of top-k flows improves the throughput of the algorithm. Experimental results show that NewKeeper outperforms the state-of-the-art by achieving higher precision and higher throughput with small memory size.