MVX-CF: A Multi-Value eXpandable Cuckoo Filter for Pending Interest Tables in Named Data Networking

Abstract

Efficient data structures that support dynamic insertion, lookup, deletion, and multi-value key storage are increasingly important in network environments. In particular, applications such as the Pending Interest Table (PIT) in Named Data Networking (NDN) require storing multiple values for a single key, while handling frequent updates under highly dynamic traffic conditions. Existing Bloom filter-based approaches offer space efficiency and fast membership queries, but often lack sufficient flexibility to support dynamic resizing and efficient multi-value mappings. In this paper, we propose the Multi-Value eXpandable Cuckoo Filter (MVX-CF), a probabilistic data structure designed for dynamic multi-value key storage. MVX-CF combines a Bloom filter, a fingerprint array, and a value bucket array, and employs cuckoo hashing to achieve high space utilization. To adapt to varying workloads, MVX-CF introduces structure and value expansion mechanisms to accommodate hash collisions and bucket overflows, as well as corresponding compression mechanisms to reclaim unused memory after deletions. These mechanisms enable MVX-CF to dynamically adjust its structure while maintaining low memory overhead and stable processing performance. Experimental results demonstrate that MVX-CF achieves significantly better lookup performance than existing PIT designs across various datasets. Furthermore, when expanding each structure to eliminate overflows, MVX-CF reduces memory consumption by 76%–78% compared with FBF-PIT, underscoring its superior efficiency and robustness for dynamic multi-value key management.