Approximate Membership Query (AMQ) filter is a group of probabilistic data structures, such as Bloom filter and cuckoo filter, which supports approximate set membership queries under constant memory budget and time cost. It has numerous applications in real-world scenarios, such as connection tracking and IP blacklisting for network management and security. However, dynamic datasets are pervasive in practice, with the number of elements fluctuating significantly over time. This requires an AMQ structure to support the run-time memory reallocation for dynamic set representation. Although previous works exist that enhance the cuckoo filter to be memory elastic, most of them only support coarse-grained memory expansion at the filter level or the mini-filter level. We propose a new AMQ filter named BECF (Bucket-level Elastic Cuckoo Filter) that allows fine-grained expansion and shrinkage at the bucket level. BECF combines cuckoo filter with consistent hashing technique, which one-to-one maps the buckets of a cuckoo filter to the segments of a hashring. To allow the number of segments to increase dynamically, BECF splits an arbitrary segment into two child segments, and adopts a segment re-addressing technique that borrows extra bits from element fingerprint to identify the child segment prefix. We also minimize the data movement between the parent and the child segments (or buckets), and preserve all the good properties of cuckoo filter after the expansion. Our experiments show that BECF attains 37% lower memory cost (while holding the same number of elements), 12% higher insertion speed and 20% faster query speed than other designs.

In high-speed networks, flow-level traffic measurement is an essential tool to understand how network bandwidth is being utilized. It can be used to detect anomalous traffic behaviors due to operational or security issues. Perhaps the most important measurement task is to track the heavy hitters (HHs), i.e., the flows occupying the greatest shares of bandwidth. But most existing solutions have no concept of time window: Whenever a measurement period ends, the data sketch, which is deployed in the data plane for monitoring HHs, must be transferred to the control plane and then reset to zeros. It is better to capture network conditions of the continuous recent past by designing a HHs measurement solution that can support time-decaying window. As a result, recently several related works are devoted to tracking the time-decaying heavy hitters, including time-decaying CountMin and time-decaying Space-Saving. However, their memory-accuracy tradeoff is still suboptimal. In this paper, we attain higher performance by proposing a new algorithm named DecayAware Cuckoo Filter along Kicking Path (DAKP-CF). It can be regarded as a variant of cuckoo filter (an improved version of hash table with better memory efficiency), which transforms each bucket into a bucket-level min-heap. Its key advantage is that, when we update the table as a packet arrive, it can discover and replace the most time-decayed flow along the kicking path of a cuckoo filter. We deliberately avoid scanning the entire table to keep the high time efficiency. The experiment results show that our DAKP-CF can reach the same identification accuracy as existing methods with roughly 25% memory cost. In addition, we build a prototype of our DAKP-CF by P4-programmable BMv2 software switch.