{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T09:59:19Z","timestamp":1770890359290,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"CoNEXT4","license":[{"start":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T00:00:00Z","timestamp":1732492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["980\/21"],"award-info":[{"award-number":["980\/21"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Netw."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p>\n            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\n            <jats:italic toggle=\"yes\">not<\/jats:italic>\n            support deletions. We present SetD4, the first data structure for maintaining sets in the data plane that supports insertion, lookup\n            <jats:italic toggle=\"yes\">and deletion.<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3696391","type":"journal-article","created":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T11:15:47Z","timestamp":1732533347000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["SetD4: Sets With Deletions and Decay in the Data Plane"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4198-7986","authenticated-orcid":false,"given":"Jonathan","family":"Diamant","sequence":"first","affiliation":[{"name":"The Open University of Israel, Raanana, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3998-8645","authenticated-orcid":false,"given":"Shir","family":"Landau Feibish","sequence":"additional","affiliation":[{"name":"The Open University of Israel, Raanana, Israel"}]}],"member":"320","published-online":{"date-parts":[[2024,11,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2019. The CAIDA Anonymized Internet Traces 2019 Dataset. https:\/\/www.caida.org\/catalog\/datasets\/passive_dataset\/."},{"key":"e_1_2_1_2_1","unstructured":"6666. Barefoot Tofino. https:\/\/www.intel.com\/content\/www\/us\/en\/products\/network-io\/programmable-ethernetswitch.html\/."},{"key":"e_1_2_1_3_1","volume-title":"A bloom filter survey: Variants for different domain applications. arXiv preprint arXiv:2106.12189","author":"Abdennebi Anes","year":"2021","unstructured":"Anes Abdennebi and Kamer Kaya. 2021. A bloom filter survey: Variants for different domain applications. arXiv preprint arXiv:2106.12189 (2021)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.2982739"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings 14","author":"Bonomi Flavio","year":"2006","unstructured":"Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese. 2006. An improved construction for counting bloom filters. In Algorithms--ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006. Proceedings 14. Springer, 684--695."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486011"},{"key":"e_1_2_1_9_1","volume-title":"Network applications of bloom filters: A survey. Internet mathematics 1, 4","author":"Broder Andrei","year":"2004","unstructured":"Andrei Broder and Michael Mitzenmacher. 2004. Network applications of bloom filters: A survey. Internet mathematics 1, 4 (2004), 485--509."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3629144"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3359989.3365408"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405865"},{"key":"e_1_2_1_13_1","unstructured":"P4 Language Consortium et al. 2019. P416 Portable Switch Architecture (PSA)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.3048265"},{"key":"e_1_2_1_15_1","volume-title":"Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515","author":"Dillinger Peter C","year":"2021","unstructured":"Peter C Dillinger and Stefan Walzer. 2021. Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515 (2021)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_17_1","volume-title":"Summary cache: a scalable wide-area web cache sharing protocol","author":"Fan Li","year":"2000","unstructured":"Li Fan, Pei Cao, Jussara Almeida, and Andrei Z Broder. 2000. Summary cache: a scalable wide-area web cache sharing protocol. IEEE\/ACM transactions on networking 8, 3 (2000), 281--293."},{"key":"e_1_2_1_18_1","volume-title":"Tracking network flows with P4. In 2018 IEEE\/ACM Innovating the Network for Data-Intensive Science (INDIS)","author":"Hill Joseph","unstructured":"Joseph Hill, Mitchel Aloserij, and Paola Grosso. 2018. Tracking network flows with P4. In 2018 IEEE\/ACM Innovating the Network for Data-Intensive Science (INDIS). IEEE, 23--32."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132764"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560606"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373360.3380830"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuCNC.2019.8801958"},{"key":"e_1_2_1_23_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Liu Zaoxing","year":"2021","unstructured":"Zaoxing Liu, Hun Namkung, Georgios Nikolaidis, Jeongkeun Lee, Changhoon Kim, Xin Jin, Vladimir Braverman, Minlan Yu, and Vyas Sekar. 2021. Jaqen: A {High-Performance} {Switch-Native} approach for detecting and mitigating volumetric {DDoS} attacks with programmable switches. In 30th USENIX Security Symposium (USENIX Security 21). 3829--3846."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2010.06.100344"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544216.3544222"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.23919\/APNOMS52696.2021.9562660"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3545008.3545009"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3067713"},{"key":"e_1_2_1_31_1","unstructured":"Sophia Yoo Xiaoqi Chen and Jennifer Rexford. 2024. SmartCookie: Blocking Large-Scale SYN Floods with a Split-Proxy Defense on Programmable Data Planes. In USENIX Security."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3406214"}],"container-title":["Proceedings of the ACM on Networking"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696391","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T01:25:44Z","timestamp":1755912344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,25]]},"references-count":32,"journal-issue":{"issue":"CoNEXT4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.1145\/3696391"],"URL":"https:\/\/doi.org\/10.1145\/3696391","relation":{},"ISSN":["2834-5509"],"issn-type":[{"value":"2834-5509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,25]]},"assertion":[{"value":"2024-11-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}