A streaming algorithm and hardware accelerator to estimate the empirical entropy of network flows

• Published in: Computer networks (Amsterdam, Netherlands : 1999) Netherlands : 1999), 2023-12, Vol.237, p.110035, Article 110035
• Main Authors: Fernández, Yaime, Soto, Javier E., Vera, Sofía, Prieto, Yasmany, Hernández, Cecilia, Figueroa, Miguel
• Format: Article
• Language: English
• Subjects: Hardware acceleration; Shannon empirical entropy; Sketch-based streaming algorithms
• ISSN: 1389-1286; 1872-7069
• DOI: 10.1016/j.comnet.2023.110035

The empirical entropy is used in network traffic monitoring and classification to detect anomalous events and manage network resources. Computing the entropy of high-speed traffic in real time requires dedicated hardware, such as programmable switches and FPGA-based accelerators. While these devices can achieve high performance by exploiting the parallelism of the algorithm, they possess limited on-chip storage. Thus, designing algorithms that estimate the entropy of network traffic with low error and memory usage is challenging. In this paper, we present an entropy-estimation streaming algorithm that operates on large datasets with sublinear memory usage. We use sketches to estimate the frequency and cardinality of network flows during an observation interval. We only store the frequencies of the most frequent flows and use them to estimate the rest of the frequencies by assuming a power-law distribution. Our results show that, using real network traces with observation intervals of up to 50 million flows, we can estimate their empirical entropy with 0.69% mean relative error, using more than three orders of magnitude less memory than an exact entropy-computation method. We also present an FPGA-based hardware accelerator for the algorithm that can operate at a line rate of more than 200 Gbps and an estimation latency of 16μs. Using fixed-point arithmetic and function approximations in the accelerator increases the mean estimation error of our algorithm by only 0.07%. •An algorithm that measures and models traffic to estimate its empirical entropy.•Algorithm achieves 0.69% error on large traces using sketches and a power-law fit.•Accelerator architecture exploits parallelism and optimizes on-chip memory usage.•FPGA implementation operates at line rate of 200 Gbps with 16 us estimation latency.