Charting the Complexity Landscape of Compiling Packet Programs to Reconfigurable Switches

Vass, Balázs and Bérczi-Kovács, Erika R. and Fraknói, Ádám and Raiciu, Costin and Rétvári, Gábor (2024) Charting the Complexity Landscape of Compiling Packet Programs to Reconfigurable Switches. IEEE/ACM Transactions on Networking. pp. 1-16. ISSN 1063-6692

Text Pipeline_Embedding_Journal_version.pdf - Published Version Restricted to Repository staff only Download (4MB)

Abstract

P4 is a widely used Domain-specific Language for Programmable Data Planes. A critical step in P4 compilation is finding a feasible and efficient mapping of the high-level P4 source code constructs to the physical resources exposed by the underlying hardware, while meeting data and control flow dependencies in the program. In this paper, we take a new look at the algorithmic aspects of this problem, with the motivation to understand the fundamental theoretical limits and obtain better P4 pipeline embeddings, and to speed up practical P4 compilation times for RMT and dRMT target architectures. We report mixed results: we find that P4 compilation is computationally hard even in a severely relaxed formulation, and there is no polynomial-time approximation of arbitrary precision (unless P=NP), while the good news is that, despite its inherent complexity, P4 compilation is approximable in linear time with a small constant bound even for the most complex, nearly real-life models.

Actions (login required)

Edit Item