MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-<i>k</i> Elephant Flows

Abstract

Encrypted traffic accounts for 95% of the total traffic in the backbone network environment with Tbps bandwidth. As network traffic becomes more and more encrypted and link rates increase in modern networks, the measurement of encrypted traffic relies more on collecting and analyzing massive network traffic data that can be separated from the support of high-speed network traffic measurement technology. Finding top-k elephant flows is a critical task with many applications in congestion control, anomaly detection, and traffic engineering. Owing to this, designing accurate and fast algorithms for online identification of elephant flows becomes more and more challenging. Existing methods either use large-size counters, i.e., 20 bit, to prevent overflows when recording flow sizes or require significant space overhead to measure the sizes of all flows. Thus, we adopt a novel strategy, called count-with-uth-level-sampling, in this paper, to find top-k elephant flows in limited resource environments. Moreover, the proposed algorithm, called MSLCFinder, incurs lightweight counter and uth-level multi-sampling with small, constant processing for millions of flows. Experimental results show that MSLCFinder can achieve more than 97% precision with an extremely limited hardware resource. Compared to the state-of-the-art, our method realizes the statistics and filtering of millions of data streams with less memory.

Keywords

• network measurement
• top-<i>k</i> finding
• elephant flow
• MSLCFinder
• data flow
• traffic sampling