PeriodicPipe

Mining flows with special patterns can provide insightful knowledge for fine-grained network monitoring and management in cyber-physical-social systems (CPSSs). However, existing work fails to pay full attention to periodic flows, which have great importance in many real-world applications. We observe that the prior algorithms are significantly constrained by limited memory resources, which hinders their ability to achieve high accuracy, and suffer from circular dependencies, making them impractical to be implemented on hardware platforms and achieve line-rate processing of high-speed network flows. Thus, we propose a hardware-friendly algorithm called PeriodicPipe, aiming to find top- $k$ periodic flows more accurately. PeriodicPipe utilizes periodic calculation mechanism to calculate the interarrival times of flows, eliminating the need for storing flow labels and out-dated timestamps. To comply with hardware programming constraints, we designed the pipelining insertion mechanism to store the interarrival time frequencies of all flows, thereby identifying the top- $k$ periodic flows. In addition, we introduce a recirculation filter to filter low-frequency replacements that may otherwise degrade throughput. While it consumes a small amount of memory, this design ensures high throughput with only a negligible impact on accuracy. We construct a hardware prototype of PeriodicPipe and compare the performance of PeriodicPipe with two contrast algorithms (the baseline algorithm and PeriodicSketch algorithm). Our experiments demonstrate that: PeriodicPipe reduces the average relative error (ARE) by 95.52% and 98.79% compared to the two compared algorithms, while improving throughput by up to 5.5 $\times$ and 8.4 $\times$ , respectively

Algorithm design · Data stream mining · Data structure · Execution time · Throughput · Data Mining Algorithms and Applications · Internet Traffic Analysis and Secure E-voting · Software System Performance and Reliability