Sketch-based entropy estimation
Yu‐Kuen Lai, Se-young Yu, Iek-Seng Chan, Bo-Hsun Huang, Che-Hao Chang, Jim Hao Chen, Joe Mambretti · 2022
This work presents the implementation of a tabular interpolation approach to estimate empirical Shannon entropy on programmable data plane ASICs using P4. The technique transforms the complex computations of the random projection into fast lookup over pre-computed tables in the match-action pipeline. Likewise, the interpolation heuristic further reduces the table size substantially. Thus, more tables can be accommodated, achieving higher estimation accuracy. Simulations based on real-world network traffic traces are performed to evaluate the estimation accuracy. The scheme is deployed in a Barefoot Tofino2 switch connected to the International Center for Advanced Internet Research (iCAIR) national testbed. The system can estimate the entropy of network traffic accurately at 400 Gbps throughput.