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

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 \text{s}$ latency, and supports a minimum throughput of 204 gigabits per second.

Keywords

• Empirical entropy
• network monitoring
• hardware acceleration
• field-programmable gate arrays
• streaming algorithms
• sketches