CFBF: Reducing the Insertion Time of Cuckoo Filters With an Integrated Bloom Filter

Cuckoo filters (CFs) are an alternative to Bloom filters (BFs) that supports deletions and can often be configured to have a lower false positive rate. A drawback of cuckoo filters is that the insertion process is complex and requires a large number of memory accesses when the filter operates at high occupancy. Therefore, insertion complexity may limit the applicability of cuckoo filters in many networking applications that require fast updates of the filter contents. In this letter, the cuckoo filter is extended to integrate a Bloom filter that is used to improve the performance of insertions. The proposed CFBF does not require additional memory accesses for lookup operations and preserves the support for deletion of the original cuckoo filter. The CFBF targets hardware implementations where the Bloom filter can be checked with negligible cost and where the memory width can also be adjusted to the bucket size. The evaluation results show that it can be used to reduce worst case insertion time by a factor of ten and achieve an average insertion time similar to that of a lookup. The CFBF can support bursts of hundreds of insertions for large filters and moderate false positive rates. Therefore, it can enable the use of hardware implemented cuckoo filters in applications that need to support bursts of insertions or to provide a low worst case insertion time.

I. Introduction

Approximate membership checking is widely used in networking applications to simplify and speed up processing [1]. For example, the Bloom filter [2] is commonly used in packet classification [3] and security. A recently proposed approximate membership check data structure, the cuckoo filter [4] is attracting interest as an alternative to Bloom filters. The cuckoo filter supports deletion of elements and in some settings achieves a lower false positive rate than Bloom filters when using the same amount of memory. This in conjunction with the fact that, in the worst case only two memory accesses are needed to complete a check, make it attractive for some applications. In particular, the cuckoo filter has been recently proposed for example, to improve deep packet inspection [5], longest prefix matching [6], traffic monitoring for security [7] and authentication [8].