# MSLCFinder: An Algorithm in Limited Resources Environment for Finding Top-\(k\) Elephant Flows
###### Abstract
Thus, finding top-\(k\) elephant flows and aggregating information about flow distributions can help us to achieve the above requirements. The significance of finding top-\(k\) flows is shown in Figure 1. In addition, the data flow has the characteristics of real time, continuity, and boundedness, which requires that the algorithm for processing the data flow can only perform calculations on the network flow once and can only use limited computing resources and memory resources. It also needs to ensure accuracy and timely awareness of large-scale data flows. Thus, finding top-\(k\) flows is challenging, especially with limited resources. High-speed network traffic measurement technology can mainly solve this problem, a challenging research field. For traffic measurement in the high-speed network environment, there are generally three solutions [4]: (1) based on high-performance dedicated hardware (such as TCAM, ASIC), but high-performance hardware equipment is costly; (2) based on sampling technology; (3) based on data flow technology and method. The advantages and disadvantages of different solutions are shown in Figure 2.  
The top-\(k\) elephant flow identification method based on sampling extracts some representative packets and then uses the probability theory to calculate the characteristics of the overall network traffic. The most typical method is the Sampled NetFlow [5] proposed and used by Cisco. In high-speed network links, the processing speed of hardware cannot match the enormous data flow, so the \(1/N\) sampling method is used to relieve the pressure of elephant flow identification caused by high-speed network links. In the router, the flow memory will create a new flow record based on the five-tuples of each arriving packet. Whenever a new flow is drawn into the router, a new flow record will be created in the flow memory, and a quintuple will be extracted as the unique identification of the flow. Different from NetFlow, the sample and hold [6] method first queries whether the currently arrived packet exists in the flow memory and, if so, updates the flow record; otherwise, the data packet is sampled with probability p, and a piece of new flow information is created  
Based on data flow technology, the top-\(k\) elephant flow identification method has two basic strategies: _count-all_ and _admit-all-count-some_[7]. The similarity between the two strategies is that they handle all traffic in the network rather than sampling. Therefore, the error of these two methods is smaller than the sampling technique; however, the two strategies are different in the process of handling traffic. The _admit-all-count-some_ strategy handles all traffic but does not store all traffic. The main idea is to recognize all new flows and, at the same time, remove the smallest flow from the cache. Examples are frequent [8], efficient counting [9], lossy counting [10], space-saving [11], and CSS [12]. They can effectively eliminate the flow by introducing some constraint rules and controlling the error of top-\(k\) flow measurement within a certain range. The _count-all_ strategy is based on sketches such as count-min sketch [13] and count sketch [14] to measure the size of all flows. It stores and counts all traffic. It is necessary to use sketches to summarize and count data flows to reduce the demand for memory space and resources on the premise of storing all traffic. Furthermore, the _admit-all-count-some_ strategy assumes that every new incoming flow is an elephant flow and expels the smallest one, in summary, to make room for the new one. Nevertheless, most flows are mouse flows. Such an assumption causes a significant error, especially under tight memory. The _count-all_ strategy needs a large sketch to count all flows. These solutions could not be more memory-efficient. Additionally, it needs more memory to scan the entire counter and sort elements to answer the top-\(k\) query.