Combined Filtering and Frequency Estimation with the Integrated Xor Filter and Count-Min Sketch

Aguilar R.M.; Reviriego P.; Larrabeiti D. · IEEE International Conference on High Performance Switching and Routing, HPSR (2024) · DOI: 10.1109/hpsr62440.2024.10635957

Resumen

Monitoring and analysis of network traffic with proper accuracy and efficiency are paramount in computer networks management and security. An example of function required for this type of applications is per-flow packet accounting. Having an efficient data structure that provides such functionality while maintaining good performance can become challenging. In this paper, we propose an integrated data structure that combines the ability of the xor filter to detect packets from selected flows and the Count-Min sketch (CMS) to efficiently estimate the frequencies. The results show that the integrated filter improves performance compared to keeping both structures separate, achieving a reduction of up to 23% in the probability of false positives, fewer memory access per operation, and a reduction of the Average Relative Error in the CMS as more packets are analyzed.

Instituciones: Universidad Católica San Pablo