Programmable switch (e.g., Barefoot Tofino)

  • Contains programmable processing units (PUs) that execute a limited set of single-cycle primitives.
  • These primitives, organized into pipeline stages, ultimately compose into data-plane algorithms. A richer set of primitives thus supports a broader range of functions at line rate.
  • Paper’s motivation: This can replace the limited fixed-function data plane that is baked into hardware in conventional network switches.

Paper’s thesis

  • Data plane algorithms can be expressed with a high-level sequential abstraction and still run at guaranteed line rate, provided they compile into sufficiently expressive single-cycle HW atoms.

Key techniques

Banzai (switch) model

  • Models a programmable switch architecture as a multi-stage feed-forward pipeline.
  • Each stage is a vector of parallel atoms. An atom is a configrable PU itself; it operates on packet fields and atom-local persistent state within one clock cycle. It can implement seven primitives (e.g., RMW) that are expressive in the proposed atom circuitry.
  • A program that satisfies the atom constraints (e.g., no cross-atom state sharing) and fits in the pipeline thus runs at line rate.

Packet transaction

  • Programmer’s specification of processing associated with a packet—how its fields and persistent switch state are updated.
  • The programmer assumes transactions execute atomically and serially in packet-arrival order.
  • Its syntax is restricted—e.g., no loops, memory allocation, or multiple locations accessed in the same state array in a single line—to ensure deterministic execution.

Compilation (synthesis)

  • The compiler transforms a packet transaction into a dependency-preserving DAG of atomic codelets.
  • Independent codelets are scheduled in parallel within a single pipeline stage, while dependent ones are mapped across stages.
  • Each codelet maps to one atom, which is configred to implement that codelet.
  • If no feasible mapping exists, the compiler concludes that the program can’t run at line-rate on the target Banzai machine and rejects it.

Comments

  • What makes the paper stand out is the programmability coupled with performance guarantees. Programmability can be a double-edged sword, letting custom programs to be blindly run at unpredictable performance. The paper builds on a core principle for designing a high-performance programmable hardware: a strict compile-or-reject model with guaranteed performance for only accepted programs should be preferred.
  • After six years, Trio (SIGCOMM’22) advocates an opposite design: on a Juniper’s non-pipeline-based programmable switch, it proposes a multi-threaded, shared-memoy-based programming model opting for flexibility (targeting ML).