# 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.2 The Lightweight Counting Module  
As shown in Figure 5, the lightweight counting module has \(d\) hash functions, and each function space comprises \(w\) counters. The counter of MSLCFinder is only \(n\) bits long. The hash functions can calculate the hash value of the incoming packet as the FlowID for MSLCFinder counting. It can also help the multi-sampling module to achieve flow sampling.  
**Multi-Sampling**: 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.  
**Insertion**: At the beginning of the measurement task, all counters are zero. For each coming packet \(Pac_{\theta}\) belonging to flow \(f_{\varphi}\), MSLCFinder calculates the \(d\) hash functions. After mapping \(f_{\varphi}\) to the counter node, it should be sampled by sampling probability and the hash value. The hash value of \(Pac_{\theta}\) will be the FlowID of flow \(f_{\varphi}\). If \(Pac_{\theta}\) is sampled, the counter will addone. Otherwise, the counter will not be processed.  
**Query**: To query the counts of a flow \(f_{\varphi}\), MSLCFinder reports the minimum value of \(d\) counter nodes that \(f_{\varphi}\) mapped.  
**Analysis**: The minimum error tolerated for the measurement task is \(\delta\). The flow \(f_{\varphi}\) true size is \(n\_pac_{\varphi}\), and its estimated size is \(\overline{i\_pac_{i}}\). We want to set an error range (\(n\_pac_{\varphi}\leq\overline{n\_pac_{i}}\leq n\_pac_{\varphi}+\varepsilon N\)), in which \(N\) is the total number of packets counted by the module. In the optimal case, \(w=\lceil e/\varepsilon\rceil\), \(d=\lceil\ln(1/\delta)\rceil\) (where \(e\) is the base of the natural logarithm, i.e., \(2.71828...\), a constant chosen to optimize the space for fixed accuracy requirements). When \(\varepsilon\) is smaller (i.e., \(w\) is larger), the error of element estimation is smaller; when \(\delta\) is smaller (i.e., \(d\) is smaller), the probability of error in element estimation is smaller.  
For the insertion procedure, because computing each hash function takes \(O(1)\) (constant) time, the total time to perform an update is \(O(d)\), independent of \(w\). Since \(d\) is typically small in practice (often less than 10), updates can be processed at high speed. The space complexity is \(O(wd)\). For the query procedure, the time complexity is \(O(\ln(1/\delta))\), and the space complexity is \(O((1/\delta^{2})\log(1/\delta))\).  
Figure 5: The structure of the lightweight counting module in MSLCFinder.