NAP: Programming Data Planes with Approximate Data Structures
Open Access
- 6 December 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 33-39
Abstract
Many applications that run on programmable data planes rely on approximate data structures, due to insufficient in-network memory. However, programming with approximate data structures is challenging because it requires (1) expertise in streaming algorithms to select the data structures that best match an application's requirements, (2) meticulous configuration to minimize approximation error while fitting within the hardware constraints, and (3) proficiency in the low-level P4 language. To address these issues, we propose NAP, a high-level network programming language. The core of NAP is the versatile approximate dictionary abstraction that captures a wide range of compact data structures, while allowing programmers to simply specify the kinds of error an application can tolerate. We demonstrate the language's expressiveness, conciseness, and efficiency through a variety of network applications, each compiling to P4 for the Intel Tofino in less than a second and featuring 25X--50X fewer lines of code compared to the P4 output. We evaluate an approximate stateful firewall written in NAP with real campus traffic, achieving performance consistent with the predicted accuracy.Keywords
Funding Information
- Defense Advanced Research Projects Agency (HR0011-20-C-0160)
This publication has 15 references indexed in Scilit:
- Fine-grained queue measurement in the data plane2019
- Nitrosketch2019
- Sonata2018
- NetCache2017
- Language-Directed Hardware Design for Network Performance Monitoring2017
- SilkRoad2017
- SNAP2016
- Forwarding metamorphosis2013
- An improved data stream summary: the count-min sketch and its applicationsJournal of Algorithms, 2005
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004