# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
## 2 Background and Related Work
### Related Backgrounds
#### 2.1.2 Network Traffic Sampling Methods  
With the improvement of link rate and the diversification of applications, the vast network traffic has brought tremendous pressure to traffic collection, transmission, storage,and analysis. In order to solve the problem of passive measurement in high-speed networks, sampling technology is applied to high-speed network traffic measurement, which can reduce the amount of data used for measurement, storage, and processing under the condition of meeting the statistical accuracy of the problem. The main idea of traffic sampling technology is to select a representative packet subset from the original traffic data and then infer the characteristics of the original traffic data through the packet subset. In high-speed network traffic measurement, the implementation of sampling methods is limited by technology and resources, and it is often necessary to compromise between sampling rate and estimation accuracy. The sampling collection dramatically reduces the processing load of the system and has good scalability. It can also reflect the original flow characteristic parameters from the sample characteristic parameters and has a specific measurement accuracy. For the traffic on the Internet, from the level of packets and flows, the sampling methods are mainly divided into packet sampling and flow sampling. * Packet Sampling  
Packet sampling refers to sampling the packets that make up the network traffic. Each packet is independent and does not consider the correlation between the packets. Standard packet sampling methods include systematic, simple, and stratified random sampling. Systematic sampling refers to extracting objects at fixed intervals. After selecting the first object, select the next for every N object, as shown in Figure 2(a). Systematic sampling is a widely used sampling method, but systematic sampling has a certain periodicity. Simple random sampling refers to sampling objects with a certain probability, as shown in Figure 2(b). The sampling probability of each object can be the same or different, and this probability generally follows a certain probability distribution function. In flow measurement, simple random sampling and random incremental sampling are commonly used in random sampling methods. These two random incremental sampling methods can avoid the synchronization problem of systematic sampling. Stratified random sampling refers to dividing the population into several levels or type groups and then sampling from each level according to a certain proportion. This layering can be divided according to the arrangement order of elements, as shown in Figure 2(c), or it can be layered according to some characteristics of elements (such as packet length, protocol type), and then sampled separately. The commonly used stratified sampling in network traffic measurement is uniform stratified random sampling. This method can ensure that the sampling is unbiased relative to the element's attribute, reduce the error of grouping statistics, and make the estimation result closer to the original data. Figure 3: Three packet sampling methods. (**a**) Description of what is systematic sampling. (**b**) Description of what is simple random sampling. (**c**) Description of what is stratified random sampling. Due to the self-similarity of network traffic, [PERSON] et al. [21] proposed an improved systematic sampling BSS (systematic biased sampling). Compared with systematic static and simple random sampling, it improves the estimation accuracy of the mean value and reduces the sampling cost. However, most packet sampling methods uniformly select packets without considering the size of the packets, which makes the network measurement obtain some uncertainties. [PERSON] [22] proposed EBS (efficient byte sampling) to improve measurement quality, make measurement accuracy less dependent on the traffic characteristics, and reduce measurement overhead. * Flow Sampling  
Flow sampling refers to the sampling of network flows within the measurement time.