NAP: Programming Data Planes with Approximate Data Structures

Mengying Pan, Hyojoon Kim, Jennifer Rexford, David Walker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationEuroP4 2023 - Proceedings of the 6th International Workshop on P4 in Europe
PublisherAssociation for Computing Machinery, Inc
Pages33-39
Number of pages7
ISBN (Electronic)9798400704468
DOIs
StatePublished - Dec 8 2023
Event6th International Workshop on P4 in Europe, EuroP4 2023, co-located with ACM CoNEXT 2023 - Paris, France
Duration: Dec 8 2023 → …

Publication series

NameEuroP4 2023 - Proceedings of the 6th International Workshop on P4 in Europe

Conference

Conference6th International Workshop on P4 in Europe, EuroP4 2023, co-located with ACM CoNEXT 2023
Country/TerritoryFrance
CityParis
Period12/8/23 → …

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Keywords

  • abstraction
  • data structure
  • programmable data plane
  • programming language

Fingerprint

Dive into the research topics of 'NAP: Programming Data Planes with Approximate Data Structures'. Together they form a unique fingerprint.

Cite this