Abstract

Network traffic monitoring uses empirical entropy to detect anomalous events such as various types of attacks. However, the exact computation of the entropy in high-speed networks is a difficult process due to the limited memory resources available in the data plane hardware. In this paper, we present a method and hardware accelerator to approximate the empirical entropy of a large data set with high throughput and sublinear memory requirements. Our method uses streaming algorithms that exploit the fine-grained parallelism of existing hardware platforms for data plane processing, such as field-programmable gate arrays (FPGAs). The method uses sketches to compute the cardinality of the stream and the frequencies of the top-K elements on line, and then it estimates the contribution to the entropy of the rest of the stream assuming a simple uniform distribution for these elements. Implemented on a Xilinx UltraScale+ ZCU102 FPGA, the accelerator implements the method using only on-chip memory, with less than 50% resource usage. Tested on real network traces of up to 120 million packets and more than 5 million flows, the accelerator estimates the empirical entropy with less than 1.5% mean relative error and 21 mu s latency, and supports a minimum throughput of 204 gigabits per second.