Source-linked AI summary
Packet Transactions: High-level Programming for Line-Rate Switches
Anirudh Sivaraman, Mihai Budiu, Alvin Cheung, Changhoon Kim, Steve Licking, George Varghese, Hari Balakrishnan, Mohammad Alizadeh, Nick McKeown
TL;DR
Stateful data-plane algorithms need programmable processing at hardware line rates, but fixed-function switches are difficult to change and earlier programmable systems often sacrificed performance. The paper introduces packet transactions in Domino, compiles them through a Banzai-based pipeline to line-rate targets, and reports concise programming with feasible estimated area overhead. Its scope remains bounded by the computations and state operations supported by the target hardware.
Problem
Fixed-function switches make post-deployment algorithm changes require new hardware, while existing programmable approaches do not directly capture stateful data-plane algorithms at line rate.
Method
Domino expresses algorithms as atomic, isolated packet transactions and compiles them through normalization, pipelining, and Banzai-target code generation.
Results
Domino provides a more concise and easier model for stateful algorithms than P4, while Banzai-based targets are feasible with < 15% estimated chip-area overhead.
Takeaways & Limitations
The results suggest familiar programming and line-rate performance can coexist when the algorithm can run at line rate.
Takeaways & Limitations
Banzai cannot efficiently support large payload processing, large-table periodic scans, or algorithms requiring unsupported complex operations such as CoDel’s square root.
Abstract
from arXiv · showhide
Many algorithms for congestion control, scheduling, network measurement, active queue management, security, and load balancing require custom processing of packets as they traverse the data plane of a network switch. To run at line rate, these data-plane algorithms must be in hardware. With today's switch hardware, algorithms cannot be changed, nor new algorithms installed, after a switch has been built. This paper shows how to program data-plane algorithms in a high-level language and compile those programs into low-level microcode that can run on emerging programmable line-rate switching chipsets. The key challenge is that these algorithms create and modify algorithmic state. The key idea to achieve line-rate programmability for stateful algorithms is the notion of a packet transaction : a sequential code block that is atomic and isolated from other such code blocks. We have developed this idea in Domino, a C-like imperative language to express data-plane algorithms. We show with many examples that Domino provides a convenient and natural way to express sophisticated data-plane algorithms, and show that these algorithms can be run at line rate with modest estimated die-area overhead.
1. INTRODUCTION
Modern data-plane algorithms need stateful packet processing at line rate, but fixed hardware limits deployment and existing programmable approaches often sacrifice performance. Domino addresses this gap with packet transactions, a Banzai machine model, and an all-or-nothing compiler for programmable line-rate switches.
- Motivation: Data-plane algorithms support tasks including queue management, scheduling, congestion control, measurement, security, and load balancing while creating and maintaining switch state.These algorithms typically require dedicated hardware to meet line rates of 10–100 Gbit/s on 10–100 ports.
- Motivation: Fixed-function hardware is rigid, so deploying or modifying an algorithm after switch construction requires new hardware and substantial time and expense.This constraint affects vendors, operators, and researchers.
- Motivation: Earlier programmable routers and network processors generally ran an order of magnitude or worse below hardware line rates, limiting production deployment.Emerging programmable switching chips preserve data rates but expose mainly low-level packet parsing, forwarding, and match-action controls.
- Motivation: Existing match-action programmability does not directly express algorithms that create and modify algorithmic state, leaving a gap between available abstractions and data-plane needs.Such algorithms are often expressed in pseudocode or implemented in software routers, network processors, and endpoints.
- Domino: A packet transaction is a sequential code block that is atomic and isolated, making each packet’s visible state equivalent to serial execution across packets.This abstraction lets programmers focus on per-packet operations without reasoning about concurrent packets.
- Domino: Domino is a C-like imperative DSL built around packet transactions, while Banzai models programmable line-rate switch constraints and exposes instruction-set atoms.Its compiler accepts transactions only when they can run at line rate on the target, otherwise rejecting them outright.
- Evaluation: Domino provides a more concise stateful programming model than P4, and its compiler targets are feasible with < 15% estimated chip-area overhead in a 32 nm standard-cell library.The evaluation programs varied data-plane algorithms, compares Domino with P4, and studies how target atoms determine supported algorithms.
2. A MACHINE MODEL FOR LINE-RATE SWITCHES
Banzai models programmable line-rate switch pipelines and exposes stateful processing through atoms, while imposing clock-cycle and resource constraints. Its atomic operations address the isolation required for state updates, but its scope excludes payload-heavy and multi-cycle computations.
- Machine model: Banzai abstracts programmable switch architectures into a compiler target with stateful processing units called atoms.Atoms model the operations that hardware can execute at line rate and serve as Domino’s target instruction set.
- Line-rate constraints: State-modifying operations must complete within one clock cycle because later packets cannot observe unfinished updates.This constraint motivates hardware primitives that combine state read, computation, and write in one atom.
- Pipeline model: Each Banzai stage processes one packet every clock cycle and passes it synchronously to the next stage.The model assumes a 1 GHz clock, corresponding to one packet every 1 ns per stage.
- Atoms: An atom is sequential code that executes atomically, modifies packet or persistent state, and completes before the next packet is processed.Atoms may also contain private state that persists across packets.
- Atom constraints: Atom templates constrain atom behavior to terminating programs that fit the one-cycle execution requirement.Templates let ASIC engineers expose different atom instruction sets while preserving deterministic performance.
- Scope: Banzai targets small per-packet computations, not payload processing or operations such as periodic scans that span many clock cycles.Deep packet inspection, WAN optimization, and large-table garbage collection are outside the model’s intended scope.
3. PACKET TRANSACTIONS
Domino expresses data-plane algorithms as packet transactions that process packets sequentially while accessing packet fields and persistent switch state. Its restrictions enforce deterministic execution, and the paper leaves composition of overlapping transactions for future work.
- Programming model: Domino programs data-plane algorithms as packet transactions compiled into atom pipelines for Banzai machines.The paper uses flowlet switching to illustrate this programming and compilation workflow.
- Transaction contents: A packet transaction can modify packet fields and persistent global state within a C-like imperative function.The flowlet example uses packet fields plus persistent variables such as last_time and saved_hop.
- Transaction semantics: Transactions present a sequential abstraction in which one packet completes processing before the next packet is handled.The compiler translates this abstraction into a Banzai atom pipeline.
- Language constraints: Domino forbids unbounded iteration, unstructured control flow, dynamic allocation, pointers, and varying array indices within one transaction.These restrictions support deterministic performance and constrain each array’s accesses to a constant index.
- Multiple transactions: The paper focuses on compiling a single packet transaction and leaves detailed composition semantics for overlapping transactions to future work.Concatenating transaction bodies is offered as one possible composition semantics when multiple transactions process the same packets.
4. THE DOMINO COMPILER
The Domino compiler transforms packet transactions into pipelined code and then into Banzai configurations, rejecting programs that cannot meet line-rate constraints. Its passes normalize stateful sequential code, construct an unconstrained pipeline representation, and enforce target resource and computational limits during code generation.
- Compiler passes: The compiler uses normalization, pipelining, and code generation to transform Domino transactions into Banzai configurations.Normalization simplifies sequential transactions; pipelining creates PVSM codelets; code generation maps them to a constrained Banzai target.
- Normalization: Branch removal converts nested branches into conditional operators, producing straight-line code for simpler dependency analysis and SSA conversion.The transformation proceeds from innermost branches outward.
- Normalization: State-variable rewriting moves reads and writes into flanks, replacing state variables inside transactions with temporary packet fields.Array index expressions are also moved into the read flank because each packet accesses only one array index.
- Normalization: SSA assigns each packet field exactly once, eliminating write-after-read and write-after-write dependencies so only read-after-write dependencies remain.This simplifies dependency analysis after branch removal.
- Pipelining: Pipelining builds PVSM codelets by dependency analysis, SCC condensation, and critical-path scheduling while imposing no computational or resource limits.State-variable operations are kept within one codelet or atom because state cannot be shared between atoms.
- Code generation: Code generation checks pipeline width, depth, and atom-template compatibility, inserting stages when needed and rejecting programs that exceed target constraints.Atom bodies must finish within one clock cycle, and each codelet must map to an available atom.
5. EVALUATION
Domino is evaluated as an expressive language for stateful data-plane algorithms and as a compiler target for feasible line-rate hardware. The evaluation identifies both the algorithms supported by different atom capabilities and the trade-off between programmability, area, and performance.
- 5.1 Expressiveness: Domino expresses load balancing, congestion control, active queue management, security, measurement, and scheduling algorithms using imperative packet-processing code.The translated algorithms were already available as imperative code, and converting them to Domino was described as straightforward.
- 5.1 Expressiveness: 231 lines of uncommented P4 versus 37 lines of Domino code are required for the compared flowlet-switching implementation.P4 also requires manually specifying tables, actions, chaining, and required headers, whereas Domino can generate equivalent P4 code automatically.
- 5.2 Banzai machines: 12% estimated chip-area overhead is used for the illustrated Banzai targets, including 7% for stateless atoms, 1% for stateful atoms, and 4% for crossbars.The targets assume 32 stages, 300 stateless atoms per stage, and 10 stateful atoms per stage.
- 5.3 Compiling Domino programs to Banzai machines: Single-state-variable operations suffice for several algorithms, while CONGA requires an atom that updates a pair of state variables atomically.The Pairs atom supports updates conditioned on a predicate over a pair of state variables, allowing CONGA to run at line rate.
- 5.3 Compiling Domino programs to Banzai machines: CoDel cannot run at line rate on the evaluated targets because none provides the required square-root operation.The paper identifies lookup-table approximation as one possible direction for future work.
- 5.4 Performance vs. programmability: More complex stateful atoms increase programmability but decrease achievable line rate because their deeper circuits have longer signal-propagation delays.The paper describes this as a trade-off between supporting more algorithms and maintaining performance.
6. RELATED WORK
Related work spans programmable data planes, abstract machines, packet-processing languages, and network-wide abstractions. Domino differs by targeting stateful algorithms on line-rate switches while retaining sequential, C-like programming semantics.
- Abstract machines for line-rate switches: Banzai models practical line-rate switch constraints that NetASM, a portable abstract machine, does not model.Examples include prohibiting state sharing between atoms and limiting computations with atom templates.
- Programmable data planes: Software data planes are flexible but lack large-scale deployment performance, while network processors remain approximately 10× slower than switching chips.The paper positions Domino against prior efforts that traded performance for programmability.
- Programmable data planes: Unlike work compiling P4 for stateless forwarding and routing, Domino focuses on stateful data-plane algorithms.The distinction follows the different computational requirements of state-modifying packet processing.
- Packet-processing languages: Domino’s C-like sequential semantics are inspired by packet-processing DSLs, but line-rate targeting imposes stricter constraints such as forbidding loops.The cited DSLs target software routers or network processors rather than line-rate switches.
- Network-wide abstractions: Domino compiles SNAP’s switch-local rules into atom pipelines, extending a network-wide transaction abstraction to programmable switch hardware.SNAP itself translates network transactions into rules on each switch but does not compile those rules into a switch pipeline.
7. CONCLUSION
Domino uses packet transactions to give C-like packet-processing programs atomic, isolated semantics and compiles them to Banzai, a programmable line-rate switch model. The results suggest familiar programming and line-rate performance can coexist when an algorithm fits the available hardware.
- Conclusion: Domino is a C-like imperative language in which packet transactions are sequential code blocks atomic and isolated from other packet transactions.The compiler targets Banzai, a machine model based on programmable line-rate switch architectures.
- Conclusion: The results suggest familiar programming and line-rate performance are both possible when the algorithm can run at line rate.The conclusion presents this as a supported result rather than a claim that every algorithm is supported.