# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
###### Abstract
On the other hand, because the flow sizes are unknown a priori, almost existing methods set a large length (such as direct use of the integers in C++ or a 20-bit counter). However, if the hardware development resources and costs are limited, for example, they use only 1 Mbit to complete the top-\(k\) measurement task of millions of flows. Using a large counter such as existing methods will not only lead to the waste of counter space caused by counting most flows whose sizes are under 200 (the mouse flows) but also cause fewer counters, affecting measurement accuracy. Therefore, existing top-\(k\) finding solutions all share the same limitation: most counters will only record a mouse flow and waste significant on-chip memory, especially with resource constraints. On the whole, we aim to conquer six challenges of finding top-\(k\) in a resource-constrained environment: (1) the scheme should be completed within limited on-chip resources as far as possible; (2) the algorithm that needs to process data flows can only perform calculations on network flows once; (3) the calculation logic is simple and the storage space is small; (4) to achieve measurement of millions or more flows; (5) to restore valid top-\(k\) elephant flows information; (6) measuring top-\(k\) elephant flow on the fixed and short-length counter, with satisfactory accuracy. In this paper, we adopt a novel strategy called _count-with-uth-level-sampling_. Moreover, we propose a novel core component named Multi-Sampled Lightweight Counting Finder (MSLCFinder) to achieve a measurement scheme for finding top-\(k\) flows based on hardware resource-constrained environments. The MSLCFinder has three primary modules: a lightweight counting module, a multi-sampling module, and a flow label recording module. The lightweight counting module can work under extreme storage requirements and requests a few bits for counting. The multi-sampling module can sample flows by using multi-sampling probabilities generated by itself and the lightweight counting module. They complement and constrain each other to maximize the optimization of the MSLCFinder in the measurement task. The flow label recording module can promptly update and record top-\(k\) elephant flows information. Finally, with the MSLCFinder we propose, we can effectively find top-\(k\) elephant flows with less memory overhead and counters under resource constraints. Our main contributions can be summarized as follows:  
* We propose a novel method for finding top-\(k\) elephant flows with little memory, reducing the waste of memory space of mouse flows. It is different from the two strategies in the previous study. It compresses the count by sampling and can accurately obtain the top-\(k\) elephant flows measurement results. * We design a \(u\)th-level sampling algorithm. It can generate multiple different sampling probabilities by initial sampling threshold \(\theta\), size of MSLCFinder counter, and the sampling level \(u\). It is used to ensure that the counters of MSLCFinder can measure elephant flows more optimally before the end of the measurement task and reduce the space occupied by mouse flows. * We verify the effectiveness of the method in this paper on CAIDA public datasets and the effectiveness of the method in real network traffic. * We propose a flow recording algorithm for MSLCFinder to make up for the defect that existing top-\(k\) finding solutions generally cannot restore stream ID and other information. The rest of the paper is structured as follows. Section 2 describes the background of this research and reviews the related work. Section 3 focuses on the measurement method we proposed, including the design of MSLCFinder and the algorithm of its core components. In Section 4, the MSLCFinder is evaluated through experiments in many aspects. Finally, we summarize our research and point out future work.