# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
## 2 Background and Related Work
### Related Backgrounds
#### 2.1.3 Network Data Flow Methods  
With the rapid development of hardware, it is possible to measure the real-time performance of high-speed networks. The data flow methods are real-time measurement methods that use limited computing and memory resources to perform a calculation on the network flow. Sampling technology is widely used in network traffic measurement and analysis. Although the sampling method produces a representative subset of the original data, the statistical information of network traffic inferred from the sampling data has some errors and cannot accurately reflect the characteristics of the original traffic. The data stream method has the characteristics of single-pass scanning, limited computing, and memory resources. It is a powerful method for high-speed network traffic measurement.  
A practical and available data structure is a crucial prerequisite of the data flow method in network traffic measurement. The optimized data structure helps to improve the execution efficiency and estimation accuracy of the algorithm and reduces the computational and storage costs. The most representative and universal data structures are bitmap [27], bloom filter [28], and sketch [13].  
Bitmap [27] is a simple data structure. Its essence is a bit group. It maps a field to a bit group to count the number of duplicate elements. The direct bitmap is a stream number estimation algorithm that uses the hash function to map the stream ID to a bit in the bitmap. The bitmap is initialized to 0. When a packet arrives, its ID will be mapped a bit in bitmap, and the bit will be set to 1. All packets belonging to the same class are mapped to the exact location in bitmap. Therefore, no matter how many packets are sent in each stream, each stream corresponds to at most one bit in bitmap.  
Bloom filter [28] can be seen as an extension of bitmap. It is a simple, efficient, probability-based random data structure, and its primary data structure is a bit vector. Bloom filter can allow for processing more data under inevitable error and then judging whether the mapping is repeated. Bloom filter can generally judge whether an element is in the collection. It is characterized by fast operation and small memory consumption, but it can only tell us whether an element is \"definitely not in the collection\" or \"probably in the collection\". Bloom filter is a widely used tool based on multi-hash. It combines multiple hash functions to perform the hash process and verification and uses multiple hash functions to replace a single hash function to improve the accuracy of hash verification. Various network systems have used bloom filter algorithms, such as Web proxy and cache, database servers, and routers.  
Sketch [13] is a type of sublinear space and probabilistic data structure widely used in network measurement. Sketch algorithms often use probabilistic methods such as hash functions to map elements to continuous memory space and achieve small space consumption and swift constant-level processing time by sacrificing sure accuracy. Among them, the count-min sketch [13] is a classic sketch algorithm. Count-min sketch allows basic queries in the data flow summary, such as point queries, range queries, and inner product queries. It can also be used to solve significant problems in the data flow, such as finding quantiles and identifying elephant flows. The essence of sketch is also a data structure based on multiple hashes. It maintains an independent hash storage space for each hash function and finds data meeting special requirements through a series of complex and unique mapping rules and several additional rules. The most significant difference from bloom filter is that sketch is based on the time series model, and the counters in the hash space can be reduced.