A Two-layer Sketch for Entropy Estimation in Data Plane
Jie Lu, Zhen Zhang, Hongchang Chen · 2022
Entropy-based approaches have been shown to aid a wide variety of network measurement applications such as load balancing, anomaly detection, traffic classification. Existing entropy estimation methods require frequent interaction between forwarding and control planes which increases the burden on the network and causes unnecessary delay. In this paper, we present Filter-Sketch, a two-layer sketch that supports frequency estimation with small and static memory allocation. Based on Filter-Sketch, we propose a new generation of mechanisms to calculate entropy at a line rate which completely executes in programmable data plane. The trace-driven evaluation shows that Filter-Sketch achieves higher accuracy than the existing data plane algorithm in entropy estimation where the relative error decreases 0.65 in average.