Cuckoo Filters and Bloom Filters: Comparison and Application to Packet Classification

Bloom filters are used to perform approximate membership checking in a wide range of applications in both computing and networking, but the recently introduced cuckoo filter is also gaining popularity. Therefore, it is of interest to compare both filters and provide insights into their features so that designers can make an informed decision when implementing approximate membership checking in a given application. This article first compares Bloom and cuckoo filters focusing on a packet classification application. The analysis identifies a shortcoming of cuckoo filters in terms of false positive rate when they do not operate close to full occupancy. Based on that observation, this article also proposes the use of a configurable bucket to improve the scaling of the false positive rate of the cuckoo filter with occupancy.Pedro Reviriego and David Larrabeiti would like to acknowledge the support of the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and Innovation and of the Madrid Community research project TAPIRCM grant no. P2018/TCS-4496. David Larrabeiti acknowledges the support of EU project PASSION, Grant Agreement 780326. Salvatore Pontarelli has been partly funded by the EU commission in the context of the 5G-PICTURE project, Grant Agreement 762057