How to Execute Any Computable Function on Programmable Data Plane

Abstract

The current programming and execution models of programmable switches are overly specialized, requiring ad hoc design choices to overcome rigid hardware constraints when implementing particular computations. We attribute this limitation to the absence of Turing completeness, which decouples computation from its execution mechanism. To address this, we propose Turing-complete virtual machines on programmable switches. Our design enables programs written in high-level general-purpose languages, such as C, to run on the switch data plane with execution dynamically determined at runtime. To this end, we first demonstrate the feasibility of universal computation by implementing a Turing machine and then extend it to a register machine with a C compiler targeting it. We further enhance this design into the Anomalocaris machine, optimized for performance through parallel instruction execution and efficient memory access, tailored to a state-of-the-art programmable switch architecture. Our evaluation demonstrates the performance and applicability of Anomalocaris across synthetic workloads and real-world network functions.