# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) 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 nth-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. network measurement; top-\(k\) finding; elephant flow; MSLCFinder; data flow; traffic sampling; network security; massive traffic +
Footnote †: journal: Applied  
and heterogeneous. The nodes at different levels in the end-edge-cloud architecture on the Internet are heterogeneous regarding function, performance, and data coverage. Thus, the security of cyberspace depends more on the traffic measurement of high-speed networks and encrypted traffic analysis and classification. At this stage, the analysis, classification, and measurement of encrypted traffic rely more on the collection and analysis of massive network traffic data, and establishing more extensive and comprehensive encrypted traffic sample datasets is one of the long-term and primary goals of such work. The collection and analysis of massive network traffic data cannot happen without the support of high-speed network traffic measurement technology. Generally, the network traffic on the high-speed link is viewed as a set of flows. For traffic measurement, complete packet processing must occur in a few nanoseconds. For example, in a 100 Gbp Ethernet link, to process packets with an average size of 64 bytes and continuous arrival, the average processing time is about 4.768 ns. Thus, the measurement of network traffic has more technical challenges, such as using extremely high computing resources and storage resources, because of the continuous improvement of network link rate and the sharp increase of network data flows. The flow is composed of the packets carrying the same FlowIDs such as source IP, destination IP, or others. We can define the size of flow as the number of packets in each flow. The network traffic conforms to the heavy-tailed distribution model in the real world: 80% of the network traffic consists of 20% of the flow, and the remaining 80% of the flow only constitutes 20% of the network traffic. In other words, compared with mouse flows (e.g., the number of packets less than 200), the elephant flows (e.g., the number of packets more than 10,000) can signify the real characteristics of the network. To provide high-quality operation services (such as QoS management and QoE improvement [3]), detect anomalies in the network, control network congestion, or detect DDoS attacks, the different statistics and measurements of flows should be collected and analyzed based on high-speed network traffic measurement technology by the Internet service providers (ISPs) or the department of cyberspace security supervisions.