# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
## 3 Top-\(k\) Measurement Scheme Based on MSLCFinder
### Multi-Sampling Lightweight Counting Finder
#### 3.3.3 The Multi-Sampling Module  
Multi-sampling is a core component module in MSLCFinder, which is responsible for sampling the arrived packets, thus telling MSLCFinder whether to add the current packet to the counter at the corresponding location. Unlike the count-min sketch, the count-min sketch uses a more extended counter to record the information of all streams and count each stream. Because our method needs to complete the top-\(k\) measurement task under resource constraints, sampling and judging the traffic before updating the counter can significantly reduce the counting pressure of the counter. The multi-sampling module has two functions: (1) to conduct flow-based sampling for consecutive arriving packets to guide MSLCFinder on whether to count this packet; (2) to calculate the flow sampling probability corresponding to the FlowID based on the current number of packets in the MSLCFinder. The multi-sampling module can calculate the sampling probability \(p\) according to the current value in the counter and guide the MSLCFinder on whether to process or directly forward the currently arrived packets. The sampling probability \(p\) needs to obtain the count in counter and the initial threshold \(\theta\). Let \(a\) be the counts of the single counter. We choose \(u\)th-level sampling. The calculation method of sampling probability \(p\) is as follows:  
* Initial sampling probability: \[q_{1}=\theta-[(2^{n-u+1}-1)-1]=\theta-[2^{n-u+1}-2]\] (1) \[p_{1}=1/q_{1}\] (2)
* When \(a\) exceedsthe \(2^{n-u+1}-1\), calculate 1 st-level sampling probability: \[q_{2}=[(2^{n-u+2}-2)-(2^{n-u+1}-2)]+q_{1}=q_{1}+2^{n-u+1}\] (3) \[p_{2}=1/q_{2}\] (4)
* When \(a\) exceedsthe \(2^{n-u+i}-1(i=0\sim u-1)\), calculate \(i+1\)-level sampling probability: \[q_{i+1}=[(2^{n-u+i+1}-2)-(2^{n-u+i}-2)]+q_{i}=q_{i}+2^{n-u+i}\] (5) \[p_{i+1}=1/q_{i+1}\] (6)  
The \(u\)th-level (\(u<n-1\)) sampling method can generate \(u\) probabilities for sampling. When the measurement task is over, the computational function \(Esti(a,q_{1},q_{2},...,q_{u})\) with count \(a\) of counter can obtain estimates. * When \(1\leq a<2^{n-u+1}\): \[Esti(a,q_{1},q_{2},...,q_{u})=(a-1)\cdot q_{1}\] (7)
* When \(2^{n-u+1}\leq a<2^{n-u+2}\): \[Esti(a,q_{1},q_{2},...,q_{u})=(2^{n-u+1}-1)\cdot q_{1}+(a-2^{n-u+1})\cdot q_{2}\] (8)
* When \(2^{n-u+i}\leq a<2^{n-u+i+1}\) (\(2\leq i\leq u-1\)): \[Esti(a,q_{1},q_{2},...,q_{u})=(2^{n-u+1}-1)\cdot q_{1}+\sum_{j=1}^{i-1}(q_{j+ 1}\cdot 2^{n-u+j})+(a-2^{n-u+i})\cdot q_{i+1}\] (9)
* We can use the \(a\) to calculate the \(i\) by using the following method: \[i=\lfloor\log_{2}a\rfloor+u-n\] (10)  
For example, when we use the 3 rd-level sampling method to count the array named \(B\), which has 2 million elements, let the threshold \(\theta\) be 10,000, and the counter \(C0\) has 8-bitlength. According to the above formula, \(u=3,q_{1}=9938,q_{2}=10,002\), and \(q_{3}=10,130\). When the subscript of the element in array B is sampled, the value of counter \(Co\) is plus 1. When the array traversal is over and the \(Co=200\), the actual estimated value is 1,995,582 according to the 3 rd-level sampling method, which proves that our sampling plan is highly deterministic. When the measurement task starts, the probability \(p_{1}\) is directly used to sample each flow. If it is selected, it will be mapped to the corresponding position of the ID in the lightweight counting module, and its count will be increased by 1; if the packet is not sampled, it will be forwarded directly, and MSLCFinder will not process it. Here, we take the flow \(f_{\varphi}\) as an example. When the packet's counts in \(f_{\varphi}\) exceed the threshold value of the second level, we start to calculate the sampling probability \(p_{2}\) of the second level and continue to process the arrived packets according to \(p_{2}\), and so on until the threshold value of the \(u\)-level is exceeded.