A High-Throughput Hardware Accelerator for Network Entropy Estimation Using Sketches

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.

Automated summary

The paper introduces a method and hardware accelerator to approximate the empirical entropy of a large data set with high throughput and sublinear memory requirements. It uses streaming algorithms and sketches to compute the cardinality of the stream and the frequencies of the top-K elements, estimating the contribution to entropy of the rest of the stream assuming a simple uniform distribution. Implemented on a Xilinx UltraScale+ ZCU102 FPGA, the accelerator achieves less than 1.5% mean relative error in estimating empirical entropy with a latency of 21 microseconds and a minimum throughput of 204 gigabits per second.