SetD4: Sets With Deletions and Decay in the Data Plane

Sets are a fundamental data type in Computer Science. Data structures used to maintain sets need to enable the insertion and deletion of keys from the set and support a lookup operation to check if a key belongs to the set. Recent advances in programmable networks allow performing fine-grained network telemetry and other network functions right in the data plane, many of which utilize sets. One of the most common data structure in use for maintaining sets in the data plane is the Bloom Filter (BF). Existing implementations of BFs in the data plane support key insertion and lookup, yet due to the harsh processing restrictions of the data plane, they do not support deletions. We present SetD4, the first data structure for maintaining sets in the data plane that supports insertion, lookup and deletion. SetD4 maintains a modified BF, which holds the set, as well as two auxiliary structures that allow the safe removal of keys from the set. In addition, we present a variant of SetD4 that also supports decay, which allows the automatic removal of keys from the structure after a predefined time interval. We analyze SetD4 and show precise error rates for both the decaying and non-decaying structures. We have implemented SetD4 on the Tofino programmable switch and show that it can achieve high accuracy with limited overhead when compared to the current state-of-the-art set-membership data structures in the data plane with better false-positive and false-negative error rates.