Abstract

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 sublinear 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 mu 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.