Molly Pan will present her FPO "Verifiable Traffic Control with Compact Data Structures in the Data Plane" on Friday, Aug 8, 2025 at 10am in Friend 125.
Advisers: Jennifer Rexford and Andrew Appel
Examiners: Jennifer Rexford (Adviser), David Walker, and Maria Apostolaki
Readers: Hyojoon Kim (University of Virginia) and Andrew Appel
Abstract:
As network tra!c 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 tra!c 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 verif ied 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 e”orts form a cohesive framework for enabling robust network control in programmable data planes.