# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
## 3 Top-\(k\) Measurement Scheme Based on MSLCFinder
### Description of Top-k Measurement Algorithm Based on MSLCFinder  
Figure 7 shows the overall algorithm process, divided into two stages: measurement and FlowID recording. Low-proportion sampling reduces the probability of mouse flows being counted by MSLCFinder. It reduces operations, saves the MSLCFinder space, and reduces the probability of hash collisions. The overall algorithm can only access the memory in four cases: no access, one read zero write, one read one write, and two read one write, which meets the requirement of this problem that one read one write is the average. **Initialization**: Let MSLCFinder be \(MF[m,n]\), where \(m\) is the total number of counters in the MSLCFinder structure, and \(n\) is the number of bits in each counter. In addition, set the count in each counter in MSLCFinder as \(C\), and the initial value of \(C\) is 0. Let the initial threshold of the top-\(k\) flow measurement task be \(\theta\). Choose a \(u\)th-level sampling method for flow sampling. The minimum error that can be tolerated for the measurement task is \(\delta\). Calculate the number \(d\) of hash functions in MSLCFinder according to Formula (11). \[d=\lceil\ln(1/\delta)\rceil \tag{11}\]  
Then, calculate the initial sampling probability \(p_{1}\) with Formulas (1) and (2). Figure 7: The structure of the flow label recording module in MSLCFinder. To more simply describe the process of this algorithm, we choose the 3 rd-level sampling methods. That is, \(\mathfrak{u}=3\). For each incoming packet \(Pac_{\theta}\) belonging to flow \(f_{\varphi}\), these are the following two steps for each insertion:  
Step 1: The \(f_{\varphi}\) will be inserted in the MSLCFinder, shown in lines 3-24 in Algorithm 2. Hash the identity of the stream corresponding to each arriving packet \(Pac_{\theta}\), and the FlowID of \(f_{\varphi}\) is the hash results \(h_{1}(f_{\varphi}),h_{2}(f_{\varphi}),...,h_{d}(f_{\varphi})\). If the count \(C\) is already equal to \(2^{n}\), do not insert anything into the counter and forward the packet. Otherwise, determine the size of \(C\) and the three thresholds, and use the sampling probability corresponding to the threshold interval to perform the flow sampling. If the \(Pac_{\theta}\) has been sampled, the counter will be plus one, and the flag is true, which means that the count of \(f_{\varphi}\) is updated. Step 2: We use the MSLCFinder flow label recording module to record the FlowID of \(f_{\varphi}\), which is shown in lines 25-27 in Algorithm 2. We use the minimal \(MF[hash_{d}(f_{\varphi})].C\) to record into the module. The record in the module is timely updated by the function \(Record\). ```
Input: A packet \(Pac_{\theta}\) belong to flow \(f_{\varphi}\), Sampling threshold \(\theta\), Counter length \(n\)\(new\_cnt\gets 0\); \(u\gets 3\); \(p_{1}\leftarrow\frac{1}{\theta-[2^{n-2}-2]}\); for\(j\in 1\to d\)do \(C\leftarrow MF[hash_{j}(f_{i})].C\); \(Flow.ID\gets MF[hash_{j}(f_{i})].ID\); if\(C==2^{n}\)then  pass;  end if \(C<2^{n-2}\)then  Flow Sampling as \(p_{1}\);  end if \(2^{n-2}\leq C<2^{n-1}\)then  Flow Sampling as \(p_{2}\);  end if \(2^{n-1}\leq C<2^{n}\)then  Flow Sampling as \(p_{3}\);  end if \(Pac_{\theta}\)Be Sampledthen \(MF[hash_{j}(f_{i})].C++\); \(Flag\gets True\); else  pass;  end if  end for if Flag == Truethen  new_cnt \(\leftarrow\) min(\(MF[hash_{1}(f_{i})].C,MF[hash_{2}(f_{i})].C,...,MF[hash_{d}(f_{\varphi})].C\));  cnt \(\leftarrow\) Record(\(Flow.ID,new\_cnt\));  end if
```  
**Algorithm 2**Top-\(k\) measurement algorithm based on MSLCFinder. **Query top-\(k\) flows**: After the measurement task, the MSLCFinder will report the information of \(k\) flows recorded in the flow label recording module, such as network quintuple. **Analysis**: Our method's time complexity and space complexity are as follows: (1) The time complexity is \(O(n\log k)\). When a new element comes, it needs \(O(1)\) time to query in the lightweight counting module of MSLCFinder.