Publication: Cuckoo Filters and Bloom Filters: Comparison and Application to Packet Classification
Loading...
Identifiers
Publication date
2020-12
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Impact
Export
Abstract
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.
Description
Keywords
Data structures, Software defined networking, Cuckoo filters, Bloom filters, Packet classification, SDN
Bibliographic citation
Reviriego, P., Martinez, J., Larrabeiti, D., Pontarelli, S.(2020). Cuckoo Filters and Bloom Filters: Comparison and Application to Packet Classification. IEEE Transactions on Network and Service Management, 17(4), 2690–2701.