Identifying the largest K flows in network traffic is an important task for applications such as flow scheduling and anomaly detection, which aim to improve network efficiency and security. However, accurately estimating flow frequencies is challenging due to the large number of flows and increasing network speeds. Hardware accelerators are often used in this endeavor due to their high computational power, but their limited amount of on-chip memory constrains their performance. Various sketch-based algorithms have been proposed to estimate properties of traffic such as frequency, with lower memory usage and theoretical bounds, but they often under perform with the skewed distribution of network traffic. In this work, we propose an algorithm for top- K identification using a modified TowerSketch and a priority queue array. Tested on real traffic traces, we identify the top- K flows, with K up to 32,768, with a precision of more than 0.94, and estimate their frequency with an average relative error under $1.96 \%$. We designed and implemented an accelerator for this algorithm on an AMD Virtex U280 UltraScale+ FPGA, which processes one packet per cycle at 392 MHz, reaching a minimum line rate of more than 200 Gbps.

Measuring statistical properties of network traffic can improve our understanding of traffic distribution and help us detect short and long-term anomalies. However, computing the exact value of these properties requires significant storage and computation, which limits their application in high-speed networks. Hardware accelerators provide the computational power to process a large sequence of network packets with high throughput and low latency, but their performance is ultimately limited by the amount of on-chip memory available on the device. Consequently, researchers have proposed sketch-based algorithms to estimate properties of a data stream with sub linear memory and theoretical estimation error bounds. In this paper, we present a streaming algorithm and hardware accelerator for quantile estimation, which is based on the architecture of the KLL sketch. Implemented on an AMD Virtex XCU55 UltraScale+ FPGA, the accelerator operates at a clock frequency of 356 MHz, thereby achieving a minimum line rate of 182 Gbps and a maximum estimation latency of 4.33 µs. When processing a set of 10 real traffic traces of up to 123 million packets, the accelerator estimates 1000 packet-size quantiles per trace with a median error of 0.39% or less, and a maximum error of 1.3% or less across all traces.

The empirical Shannon entropy is a popular metric for anomaly detection in network traffic. However, computing its exact value in real time requires fast access to a large number of counters, which is unfeasible in high-speed networks. Approximate approaches using sketches can estimate the entropy with low memory usage. However, achieving good estimation accuracy still requires large data structures, making their implementation difficult in dedicated hardware and programable switches. In this paper, we present an entropy-estimation algorithm and its implementation in a programmable switch, which achieves good accuracy for large traffic traces with low memory usage. The algorithm uses sketches to track the packet count of only the most-frequent flows and models the rest of the traffic with a uniform distribution. The implementation operates within the restrictions imposed by the P4 switch programming language, achieving a 1.72% average estimation error on 12 real-world large traces from public repositories.