# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
## 2 Background and Related Work
### Review of Related Research  
#### 2.2.1 Network Measurement Technology Based on Sketch  
Count-min sketch (CM sketch) [13] has the advantages of simple, efficient operation and small memory usage with a high accuracy guarantee. CM sketch has linear space-time complexity and can perform frequency statistics of data streams, frequent item mining, and other tasks. It can overestimate but only requires one memory access per counter. Currently, CM sketch is one of the most popular sketch-based algorithms for network measurement.  
Although many sketch structures have high accuracy, they can only perform specific detection tasks. For example, FMSketch [29] can perform the measurement task of cardinality estimation. OpenSketch [30] is a universal and efficient measurement framework that can measure a variety of tasks in real-time elephant flow detection, DDoS/SuperSpreadernetwork anomaly detection, flow size statistics, etc. It is also deployed in SDN. SketchVisor [31] uses fast path technology and compressive sensing technology to reduce the number of packets to be processed, improve the processing speed of packets, and realize the statistics of multiple traffic characteristics. To solve the problem of complex resource configuration in the measurement process, SketchLearn[32] designed a multi-level sketch structure. According to the feature that small data streams obey the Gaussian distribution in multi-level sketches, the algorithm automatically infers and extracts large data streams by using the statistical characteristics of data streams, effectively reducing system overhead. NitroSketch [33] uses adaptive sampling to update only the values of some counters, reducing the number of data packets to be processed, fundamentally improving the robustness of the measurement framework, and significantly speeding up the processing of data packets.  
Relevant research [34] shows that the combination of sketch structure and machine learning algorithm can dynamically adapt to changes in the network environment, automatically extract network features, and achieve high-precision network measurement. In [PERSON] et al. [34], measurement accuracy was dramatically improved. [PERSON] et al. [35] combined the skeleton structure with reinforcement learning and proposed the RL sketch method to detect abnormal data streams in the network. RL sketch uses DQN (Deep Q-Network) to predict the size of data streams, filter out mouse flows, and only count elephant flows in the skeleton. High-accuracy network measurement is achieved with small memory. [PERSON] et al. [36] used the K-means algorithm to map similar data streams to the same bucket for clustering, replacing individual values with average category values, and used random mappers to correct statistical values, which improved processing speed while ensuring accuracy.  
In a word, the research of the sketch method can be roughly divided into two directions: (1) the transformation from poor scalability of the single task to strong versatility of multi-task; (2) it combines machine learning and artificial intelligence algorithms to adapt to the diversity of a network environment.