4.6 Article

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

Journal

IEEE ACCESS
Volume 9, Issue -, Pages 85823-85838

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2021.3088500

Keywords

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

Funding

  1. Agencia Nacional de Investigacion y Desarrollo (ANID) Fondecyt Regular [1180995]
  2. Basal Funds [FB0001]
  3. Magister Nacional Scholarship
  4. Doctorado Nacional Scholarship

Ask authors/readers for more resources

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

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available