Cuckoo Filters and Bloom Filters: Comparison and Application to Packet Classification Articles uri icon

publication date

  • December 2020

start page

  • 2690

end page

  • 2701

issue

  • 4

volume

  • 17

International Standard Serial Number (ISSN)

  • 1932-4537

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.

keywords

  • data structures; software defined networking; cuckoo filters; bloom filters; packet classification; sdn