Content area
As network traffic grows in volume and diversity, operators increasingly require real-time, in-network control over packets. Tasks such as rate-limiting large flows, identifying heavy downloaders, and dropping unsolicited packets demand stateful processing at line rate—capabilities absent in traditional fixed-function switches. The advent of programmable data planes has made such control feasible, allowing custom stateful logic to run directly in the network.
However, programming traffic control remains challenging. Data planes impose strict memory constraints, making conventional data structures impractical. Instead, operators rely on approximate data structures like Bloom filters and hash tables, trading accuracy for efficiency. Selecting and configuring these structures requires expertise, as poor choices can lead to excessive errors or wasted resources.
To address this, we developed Network Approximate Programming (NAP), a high-level language centered on a versatile approximate dictionary abstraction. This abstraction captures a broad range of compact data structures while allowing programmers to specify the types of errors an application can tolerate. The NAP compiler automatically selects and configures the appropriate structure to optimize hardware utilization and compiles to P4, the native programming language for data planes—significantly simplifying development.
Ensuring correctness of approximate data structures in P4 poses additional challenges. While research has advanced new streaming algorithms, little attention has been paid to adapting them systematically to data-plane constraints and refreshing them at runtime. Moreover, these practical concerns may introduce subtle bugs. To address these concerns, we developed general synthesis and verification frameworks. We deployed an approximate sliding-window Bloom filter on Intel Tofino and verified its correctness, demonstrating how to build P4 data structures with correctness guarantees.
Finally, P4 itself presents foundational challenges: its low-level design, ambiguous specification, and lack of formal semantics make stateful programming error-prone. To provide a rigorous foundation, we developed a formal semantics for P4 based on its two-phase evaluation model. Our mechanized formalization precisely defines language constructs, including stateful externs on Intel Tofino. By adhering to P4’s intended behavior, our work uncovered previously undocumented ambiguities and contributed improvements to the specification.
Together, these efforts form a cohesive framework for enabling robust network control in programmable data planes.
