The Programmable Data Plane: Reading List

Languages and Compilers

Abstractions for Embedded State

• Verdú et al.: Workload Characterization of Stateful Networking Applications, IEEE HPC, 2008.
  

  RELEVANCE: important
  

  This paper presents the first workload characterization of stateful networking applications. The analysis emphasizes the study of data cache behavior, but discusses branch prediction, instruction distribution, etc. Another important contribution is the study of the state categories of different networking applications.

• Bianchi et al.: OpenState: Programming Platform-independent Stateful Openflow Applications Inside the Switch, ACM SIGCOMM Comput. Commun. Rev., 2014.
  

  RELEVANCE: mustread
  

  The paper tackles the challenge to devise a stateful data plane programming abstraction (versus the stateless OpenFlow match/action table abstraction) which still entails high performance and remains consistent with vendors' preference for closed platforms. The authors posit that a promising answer revolves around the usage of extended finite state machines, as an extension (super-set) of the OpenFlow match/action abstraction, turn the proposed abstraction into an actual table-based API, and show how it can be supported by (mostly) reusing core primitives already implemented in OpenFlow devices.

• Moshref et al.: Flow-level State Transition As a New Switch Primitive for SDN, ACM HotSDN, 2014.
  

  RELEVANCE: interesting
  

  The paper proposes FAST (Flow-level State Transitions) as a new switch primitive for software-defined networks. With FAST, the controller simply preinstalls a state machine and switches can automatically record flow state transitions by matching incoming packets to installed filters. FAST can support a variety of dynamic applications, and can be readily implemented with commodity switch components and software switches.

• Arashloo et al.: SNAP: Stateful Network-Wide Abstractions for Packet Processing, ACM SIGCOMM, 2016.
  

  RELEVANCE: important
  

  SNAP offers a simpler "centralized" stateful programming model on top of the simple match-action paradigm offered by OpenFlow. SNAP programs are developed on a one-big-switch abstraction and may contain reads and writes to global, persistent arrays, allowing programmers to implement a broad range of stateful applications. The SNAP compiler then distributes, places, and optimizes access to these stateful arrays, discovering read/write dependencies and translating one-big-switch programs into an efficient internal representation based on a novel variant of binary decision diagrams.

• Kim et al.: Kinetic: Verifiable Dynamic Network Control, USENIX NSDI, 2015.
  

  RELEVANCE: important
  

  Kinetic provides a formal way to program the network control plane using finite state machines. The use of a formal language allows the system to verify the correctness of the control program according to user-specified temporal properties. The paper also reports about a user survey among students of the Coursera's SDN course, which find the Finite State Machine abstraction of Kinetic to be intuitive and easier to verify compared to other high-level languages, such as Pyretic.

• Sivaraman et al.: Packet Transactions: High-Level Programming for Line-Rate Switches, ACM SIGCOMM, 2016.
  

  RELEVANCE: important
  

  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 programmable line-rate switching chips. The key challenge is that many data-plane algorithms create and modify algorithmic state. To achieve line-rate programmability for stateful algorithms, the paper introduces the notion of a packet transaction: a sequential packet-processing code block that is atomic and isolated from other such code blocks. The idea is developed in Domino, a C-like imperative language to express data-plane algorithms, and many examples are shown that can be run at line rate with modest estimated chip-area overhead.

• Giuseppe Bianchi et al.: Open Packet Processor: a programmable architecture for wire speed platform-independent stateful in-network processing, unpublished manuscript, 2016.
  

  RELEVANCE: interesting
  

  This paper aims at contributing to the debate on how to bring programmability of stateful packet processing tasks inside the network switches, while retaining platform independence. The proposed approach, named "Open Packet Processor" (OPP), shows the viability of eXtended Finite State Machines (XFSM) as low-level data plane programming abstraction. Platform independence is accomplished by decoupling the implementation of hardware primitives from their usage by an application formally described via an abstract XFSM.

• Junaid Khalid et al.: Paving the Way for NFV: Simplifying Middlebox Modifications Using StateAlyzr, USENIX NSDI, 2016.
  

  RELEVANCE: interesting
  

  Migrating/cloning internal state in elastically scalable Network Functions Virtualization (NFV) require modifications to middlebox code to identify needed state. The paper presents a framework-independent system, StateAlyzr, that embodies novel algorithms adapted from program analysis to provably and automatically identify all state that must be migrated/cloned to ensure consistent middlebox output in the face of redistribution. StateAlyzr reduces man-hours required for code modification by nearly 20x.

• Luo et al.: Swing State: Consistent Updates for Stateful and Programmable Data Planes, ACM SOSR, 2017.
  

  RELEVANCE: interesting
  

  The paper presents Swing State, a general state-management framework and runtime system supporting consistent state migration in stateful data planes. The key insight is to perform state migration entirely within the data plane by piggybacking state updates on live traffic. To minimize the overhead, Swing State only migrates the states that cannot be safely reconstructed at the destination switch. A prototype of Swing State for P4 is also described.

• Dargahi et al.: A Survey on the Security of Stateful SDN Data Planes, IEEE Communications Surveys Tutorials, 2017.
  

  RELEVANCE: important
  

  The paper provides the reader with a background on stateful SDN data plane proposals, focusing on the security implications that data plane programmability brings about, identifies potential attack scenarios, and highlights possible vulnerabilities specific to stateful in-switch processing, including denial of service and saturation attacks.

• Murad Kablan et al.: Stateless Network Functions: Breaking the Tight Coupling of State and Processing, USENIX NSDI, 2017.
  

  RELEVANCE: mustread
  

  The paper presents Stateless Network Functions, a new architecture for network functions virtualization, where the existing design of network functions is decomposed into a stateless processing component along with a data-store layer. The StatelessNF processing instances are architected around efficient pipelines utilizing DPDK for high performance network I/O, packaged as Docker containers for easy deployment, and a data store interface optimized based on the expected request patterns to efficiently access a RAMCloud-based data store. A network-wide orchestrator monitors the instances for load and failure, manages instances to scale and provide resilience, and leverages an OpenFlow-based network to direct traffic to instances.

• Shinae Woo et al.: Elastic Scaling of Stateful Network Functions, USENIX NSDI, 2018.
  

  RELEVANCE: mustread
  

  Elastic scaling is a central promise of NFV but has been hard to realize in practice, because most Network Functions (NFs) are stateful and this state need to be shared across NF instances. The paper presents S6, building on the insight that a distributed shared state abstraction is well-suited to the NFV context. State is organized as a distributed shared object (DSO) space, extended with techniques designed to meet the need for elasticity and high-performance in NFV workloads.

• Salvatore Pontarelli et al.: FlowBlaze: Stateful Packet Processing in Hardware, USENIX NSDI, 2019.
  

  RELEVANCE: mustread
  

  FlowBlaze is an open abstraction for building stateful packet processing functions in hardware. The abstraction is based on Extended Finite State Machines and introduces the explicit definition of flow state, allowing FlowBlaze to leverage flow-level parallelism. The paper presents an implementation of FlowBlaze on a NetFPGA SmartNIC that achieves latency on the order of a few microseconds, consumes relatively little power, can hold per-flow state for hundreds of thousands of flows, and yields speeds of 40 Gbps.

Programmable Parsing and Scheduling

• Gibb et al.: Design principles for packet parsers, IEEE/ACM ANCS, 2013.
  

  RELEVANCE: important
  

  The paper presents an interesting view on parser design and the trade-offs between different designs, asking whether it is better to design one fast parser or several slow parsers, what are the costs of making the parser reconfigurable in the field, and what design decisions most impact power and area. The paper describes trade-offs in parser design, identifies design principles for switch and router architects, and describes a parser generator that outputs synthesizable Verilog that is available for download.

• Sivaraman et al.: No Silver Bullet: Extending SDN to the Data Plane, ACM HotNets, 2013.
  

  RELEVANCE: interesting
  

  The authors argue that, instead of going with a universal scheduler that would handle all queuing strategies that may arise in a programmable switch, Software-Defined Networking must be extended to control the fast-path scheduling and queuing behavior of a switch. To this end, they propose adding a small FPGA to switches, and synthesize, place, and route hardware implementations for CoDel and RED.

• Radhika Mittal et al.: Universal Packet Scheduling, USENIX NSDI, 2016.
  

  RELEVANCE: interesting
  

  The addresses a seemingly simple question: Is there a universal packet scheduling algorithm? It turns out that in general the answer is "no"; however, the authors manage to show that the classical Least Slack Time First (LSTF) scheduling algorithm comes closest to being universal and it can closely replay a wide range of scheduling algorithms. LSTF is evaluated as to whether in practice it can meet various network-wide objectives; the authors find that LSTF performs comparable to the state-of-the-art for each of performance metric.

• Sivaraman et al.: Programmable Packet Scheduling at Line Rate, ACM SIGCOMM, 2016.
  

  RELEVANCE: important
  

  Similarly to the "Universal Packet Scheduling" paper, this paper presents another design for a programmable packet scheduler, which allows scheduling algorithms, potentially algorithms that are unknown today, to be programmed into a switch without requiring hardware redesign. The design uses the property that scheduling algorithms make two decisions, in what order to schedule packets and when to schedule them, and exploits that in many scheduling algorithms definitive decisions on these two questions can be made when packets are enqueued. The resultant design uses a single abstraction: the push-in first-out queue (PIFO), a priority queue that maintains the scheduling order or time.

• Naveen Sharma et al.: Approximating Fair Queueing on Reconfigurable Switches, USENIX NSDI, 2018.
  

  RELEVANCE: interesting
  

  The paper discusses how to leverage configurable per-packet processing and the ability to maintain mutable state inside switches to achieve fair bandwidth allocation across all traversing flows. The problem is that implementing fair queuing mechanisms in high-speed switches is expensive, since they require complex flow classification, buffer allocation, and scheduling on a per-packet basis. The proposed dequeuing scheduler, called Rotating Strict Priority scheduler, simulates an ideal round-robin scheme where each active flow transmits a single bit of data in every round, which allows to transmit packets from multiple queues in approximately sorted order.

• Vishal Shrivastav: Fast, Scalable, and Programmable Packet Scheduler in Hardware, ACM SIGCOMM, 2019.
  

  RELEVANCE: mustread
  

  The trend toward increasing link speeds and slowdown in the scaling of CPU speeds, leads to a situation where packet scheduling in software results in lower precision and higher CPU utilization. While by offloading packet scheduling to the hardware (e.g., the NIC), this drawback can be overcome, one still would like to retain the flexibility benefits of software packet schedulers: packet scheduling in hardware should hence be programmable. Shrivastav proposes a generalization of the Push-In-First-Out (PIFO) primitive used by state-of-the-art hardware packet schedulers: Push-In-Extract-Out (PIEO) maintains an ordered list of elements, but allows dequeue from arbitrary positions in the list by supporting a programmable predicate-based filtering at dequeue. PIEO supports most scheduling (work-conserving and non-work conserving) algorithms and can be implemented scalably in hardware.

Software Switch Architectures

Hardware Switch Architectures

• De Carli et al.: PLUG: Flexible Lookup Modules for Rapid Deployment of New Protocols in High-speed Routers, ACM SIGCOMM, 2009.
  

  RELEVANCE: mustread
  

  The first incarnation of the "programmable switch". PLUG (Pipelined Lookup Grid) is a flexible lookup module that can achieve generality without loosing efficiency, because various custom lookup modules have the same fundamental features that PLUG retains: area dominated by memories, simple processing, and strict access patterns defined by the data structure. The authors IPv4, Ethernet, Ethane, and SEATTLE in a dataflow-based programming model for the PLUG and mapped them to the PLUG hardware, showing that throughput, area, power, and latency of PLUGs are close to those of specialized lookup modules.

• Anwer et al.: SwitchBlade: A Platform for Rapid Deployment of Network Protocols on Programmable Hardware, ACM SIGCOMM, 2010.
  

  RELEVANCE: important
  

  SwitchBlade is a platform for rapidly deploying custom protocols on programmable hardware. SwitchBlade uses a pipeline-based design that allows individual hardware modules to be enabled or disabled on the fly, integrates common packet-processing functions as hardware modules enabling different protocols to use these functions without having to resynthesize hardware, and uses a customizable forwarding engine that supports both longest-prefix matching in the packet header and exact matching on a hash value. SwitchBlade also allows multiple custom data planes to operate in parallel on the same physical hardware, while providing complete isolation for protocols running in parallel.

• Bosshart et al.: Forwarding Metamorphosis: Fast Programmable Match-action Processing in Hardware for SDN, ACM SIGCOMM, 2013.
  

  RELEVANCE: mustread
  

  This seminal paper presents RMT to overcome two limitations in current switching chips and OpenFlow: (1) conventional hardware switches are rigid, allowing "Match-Action" processing on only a fixed set of fields, and (2) the OpenFlow specification only defines a limited repertoire of packet processing actions. The RMT (Reconfigurable Match Tables) model is a RISC-inspired pipelined architecture for switching chips, including an essential minimal set of action primitives to specify how headers are processed in hardware. RMT allows the forwarding plane to be changed in the field without modifying hardware.

• Brebner et al.: High-Speed Packet Processing using Reconfigurable Computing, IEEE Micro, 2014.
  

  RELEVANCE: interesting
  

  The paper presents a tool chain that maps a domain-specific declarative packet-processing language with object-oriented semantics, called PX, to high-performance reconfigurable-computing architectures based on field-programmable gate array (FPGA) technology, including components for packet parsing, editing, and table lookups.

• Kuzniar et al.: What You Need to Know About SDN Control and Data Planes, EPFL Technical Report 199497, 2014.
  

  RELEVANCE: mustread
  

  The definite source on OpenFlow switches and the differences between them. The authors measure, report, and explain the performance characteristics of the control- and data-planes in three hardware OpenFlow switches. The results highlight differences between the OpenFlow specification and its implementations that, if ignored, pose a serious threat to network security and correctness.

• Han et al.: BlueSwitch: Enabling Provably Consistent Configuration of Network Switches, ACM/IEEE ANCS, 2015.
  

  RELEVANCE: important
  

  The paper is motivated by the challenges involved in consistent updates of distributed network configurations, given the complexity of modern switch datapaths and the exposed opaque configuration mechanisms. The authors demonstrate that even simple rule updates result in inconsistent packet switching in multi-table datapaths. The main contribution of the paper is a hardware design that supports a transactional configuration mechanism, providing strong switch-level atomicity: all packets traversing the datapath will encounter either the old configuration or the new one, and never an inconsistent mix of the two. The approach is prototyped using the NetFPGA hardware platform.

• Li et al.: ClickNP: Highly Flexible and High Performance Network Processing with Reconfigurable Hardware, ACM SIGCOMM, 2016.
  

  RELEVANCE: interesting
  

  This paper focuses on accelerating NFs with FPGAs. However, FPGA is predominately programmed using low-level hardware description languages (HDLs), which are hard to code and difficult to debug. More importantly, HDLs are almost inaccessible for most software programmers. This paper presents ClickNP, a FPGA-accelerated platform, which is highly flexible as it is completely programmable using high-level C-like languages and exposes a modular programming abstraction that resembles Click Modular Router, and also high performance.

• Chole et al.: dRMT: Disaggregated Programmable Switching, ACM SIGCOMM, 2017.
  

  RELEVANCE: important
  

  A follow-up to the RMT paper. dRMT (disaggregated Reconfigurable Match-Action Table) is a new architecture for programmable switches, which overcomes two important restrictions of RMT: (1) table memory is local to an RMT pipeline stage, implying that memory not used by one stage cannot be reclaimed by another, and (2) RMT is hardwired to always sequentially execute matches followed by actions as packets traverse pipeline stages. dRMT resolves both issues by disaggregating the memory and compute resources of a programmable switch, moving table memories out of pipeline stages and into a centralized pool that is accessible through a crossbar. In addition, dRMT replaces RMT's pipeline stages with a cluster of processors that can execute match and action operations in any order.

• Narayana et al.: Language-Directed Hardware Design for Network Performance Monitoring, ACM SIGCOMM, 2017.
  

  RELEVANCE: interesting
  

  The authors ask what switch hardware primitives are required to support an expressive language of network performance questions. They present a performance query language, Marple, modeled on familiar functional constructs, backed by a new programmable key-value store primitive on switch hardware that performs flexible aggregations at line rate and scales to millions of keys. Marple can express switch queries that could previously run only on end hosts, while Marple queries only occupy a modest fraction of a switch's hardware resources.

• Daniel Firestone et al.: Azure Accelerated Networking: SmartNICs in the Public Cloud, USENIX NSDI, 2018.
  

  RELEVANCE: mustread
  

  Modern public cloud architectures rely on complex networking policies and running the necessary network stacks on CPU cores takes away processing power from VMs, increasing the cost of running cloud services, and adding latency and variability to network performance. The paper presents the design of AccelNet, the Azure Accelerated Networking scheme for offloading host networking to hardware, using custom Azure SmartNICs based on FPGAs, including the hardware/software co-design model, performance results on key workloads, and experiences and lessons learned from developing and deploying AccelNet.

Hybrid Hardware/Software Architectures

• Han et al.: PacketShader: A GPU-accelerated Software Router, ACM SIGCOMM, 2010.
  

  RELEVANCE: important
  

  PacketShader is a high-performance software router framework for general packet processing with Graphics Processing Unit (GPU) acceleration, exploiting the massively-parallel processing power of GPU to address the CPU bottleneck in software routers, combined with a high-performance packet I/O engine. The paper presents implementations for IPv4 and IPv6 forwarding, OpenFlow switching, and IPsec tunneling to demonstrate the flexibility and performance advantage of PacketShader.

• Pongrácz et al.: Cheap Silicon: A Myth or Reality Picking the Right Data Plane Hardware for Software Defined Networking, ACM HotSDN, 2013.
  

  RELEVANCE: interesting
  

  Industry insight holds that programmable network processors are of lower performance than their hard-coded counterparts, such as Ethernet chips. The paper argues that, contrast to the common view, the overhead of programmability is relatively low, and that the apparent difference between programmable and hard-coded chips is not primarily due to programmability itself, but because the internal balance of programmable network processors is tuned to more complex use cases.

• Kalia et al.: Raising the Bar for Using GPUs in Software Packet Processing, USENIX NSDI, 2015.
  

  RELEVANCE: interesting
  

  The paper opens the debate as to whether Graphics Processing Units (GPUs) are useful for accelerating software-based routing and packet handling applications. The authors argue that for many such applications the benefits arise less from the GPU hardware itself than from the expression of the problem in a language such as CUDA or OpenCL that facilitates memory latency hiding and vectorization through massive concurrency. They then demonstrate that applying a similar style of optimization to algorithm implementations, a CPU-only implementation is more resource efficient than the version running on the GPU.

• Katta et al.: CacheFlow: Dependency-Aware Rule-Caching for Software-Defined Networks, ACM SOSR, 2016.
  

  RELEVANCE: interesting
  

  The paper presents an architecture to allow high-speed forwarding even with large rule tables and fast updates, by combining the best of hardware and software processing. The CacheFlow system caches the most popular rules in the small TCAM and relies on software to handle the small amount of cache-miss traffic. The authors observe that one cannot blindly apply existing cache-replacement algorithms, because of dependencies between rules with overlapping patterns. Rather long dependency chains must be broken to cache smaller groups of rules while preserving the semantics of the policy.

• Younghwan Go et al.: APUNet: Revitalizing GPU as Packet Processing Accelerator, USENIX NSDI, 2017.
  

  RELEVANCE: interesting
  

  This is the answer to the question raised by the "Raising the Bar for Using GPUs" paper. Kalia et al. argue that the key enabler for high packet-processing performance is the inherent feature of GPU that automatically hides memory access latency rather than its parallel computation power and claim that CPU can outperform or achieve a similar performance as GPU if its code is re-arranged to run concurrently with memory access. This paper revists these claims and find, with eight popular algorithms widely used in network applications, that (a) there are many compute-bound algorithms that do benefit from the parallel computation capacity of GPU while CPU-based optimizations fail to help, and (b) the relative performance advantage of CPU over GPU in most applications is due to data transfer bottleneck in PCIe communication of discrete GPU rather than lack of capacity of GPU itself.

Programmable NICs

• Pravin Shinde et al.: We Need to Talk About NICs, USENIX HotOS, 2013.
  

  RELEVANCE: mustread
  

  The paper's aim is to reinvigorate the discussion on the design of network interface cards (NICs) in the network and OS community. The authors argue that currently operating systems fail to efficiently exploit and manage the considerable hardware resources provided by modern network interface controllers. They then describe Dragonet, a network stack that represents both the physical capabilities of the network hardware and the current protocol state of the machine as dataflow graphs.

• Zilberman et al.: NetFPGA SUME: Toward 100 Gbps as Research Commodity, IEEE Micro, 2014.
  

  RELEVANCE: mustread
  

  The paper presents a reference design and implementation for a programmable NIC that is in wide-scale use today as an accessible development environment that both reuses existing codebases and enables new designs. NetFPGA SUME is an FPGA-based PCI Express board with I/O capabilities for 100 Gbps operation as a network interface card, multiport switch, firewall, or test and measurement environment.

• Sangjin Han et al.: SoftNIC: A Software NIC to Augment Hardware, unpublished manuscript, 2015.
  

  RELEVANCE: interesting
  

  SoftNIC is a hybrid software-hardware architecture to bridge the gap between limited hardware capabilities and ever changing user demands. SoftNIC provides a programmable platform that allows applications to leverage NIC features implemented in software and hardware, without sacrificing performance. This paper serves the foundation for the BESS software switch.

• Kaufmann et al.: High Performance Packet Processing with FlexNIC, ACM SIGPLAN Not., 2016.
  

  RELEVANCE: interesting
  

  The authors argue that the primary reason for high memory and processing overheads inherent to packet processing applications is the inefficient use of the memory and I/O resources by commodity NICs. They propose FlexNIC, a flexible network DMA interface that can be used to reduce packet processing overheads; FlexNIC allows services to install packet processing rules into the NIC, which then executes simple operations on packets while exchanging them with host memory. This moves some of the packet processing traditionally done in software to the NIC, where it can be done flexibly and at high speed.

• Phitchaya Mangpo Phothilimthana et al.: Floem: A Programming System for NIC-Accelerated Network Applications, USENIX OSDI, 2018.
  

  RELEVANCE: interesting
  

  The paper presents Floem, a set of programming abstractions for NIC-accelerated applications to ease developing server applications that offload computation and data to a NIC accelerator. Floem simplifies typical offloading issues, like data placement and caching, partitioning of code and its parallelism, and communication strategies between program components across devices, by providing language-level abstractions for logical and physical queues, global per-packet state, remote caching; and interfacing with external application code. The paper also presents evaluations to demonstrate how these abstractions help explore a space of NIC-offloading designs for real-world applications, including a key-value store and a distributed real-time data analytics system.

• Liu et al.: Offloading Distributed Applications Onto SmartNICs Using iPipe, ACM SIGCOMM, 2019.
  

  RELEVANCE: important
  

  The paper presents iPipe, a generic actor-based offloading framework to run distributed applications on commodity SmartNICs. The paper details the iPipe design, built around a hybrid scheduler that combines first-come-first-served with deficit round-robin policies to schedule offloading tasks at microsecond-scale precision on SmartNICs, and presents 3 custom-built use cases, a real-time data analytics engine, a distributed transaction system, and a replicated key-value store, to show that SmartNIC offloading brings about significant performance benefits in terms of traffic control, computing capability, onboard memory, and host communication.

• Kumar et al.: PicNIC: Predictable Virtualized NIC, ACM SIGCOMM, 2019.
  

  RELEVANCE: important
  

  The paper addresses the noisy neighbor problem in the context of NICs. Using data from a major public cloud provider, the paper systematically characterizes how performance isolation can break in virtualization stacks and finds a fundamental tradeoff between isolation and efficiency. The paper then proposes PicNIC, the Predictable Virtualized NIC, a new NIC design that shares resources efficiently in the common case while rapidly reacting to ensure isolation in order to provide predictable performance for isolated workloads. PicNIC builds on three constructs to quickly detect isolation breakdown and to enforce it when necessary: CPU-fair weighted fair queues at receivers, receiver-driven congestion control for backpressure, and sender-side admission control with shaping. Evaluations show that this combination ensures isolation for VMs at sub-millisecond timescales with negligible overhead.

Resilient, Robust, and Efficient Forwarding

• Al-Fares et al.: Hedera: Dynamic Flow Scheduling for Data Center Networks, USENIX NSDI, 2010.
  

  RELEVANCE: important
  

  This paper is motivated by the limitations of existing IP multipath protocols relying on per-flow static hashing, which can result in suboptimal throughput and bandwidth losses due to long-term collisions. Hedera is a dynamic flow scheduling system for multi-stage switch topologies as they often appear in data centers. Hedera uses flow information from constituent switches and reroutes traffic to non-conflicting routes accordingly. The authors show that the more global view of routing and traffic demands allows Hedera to see bottlenecks that switch-local schedulers cannot, and to adaptively schedule the switching fabric in a way which significantly improves aggregate network utilization with minimal overheads.

• Liu et al.: Ensuring Connectivity via Data Plane Mechanisms, USENIX NSDI, 2013.
  

  RELEVANCE: important
  

  The authors propose to move the responsibility for maintaining basic network connectivity (as opposed to the computation of optimal paths which require global control plane knowledge) to the data plane, which operates orders of magnitude faster than the control plane. Their Data-Driven Connectivity (DDC) approach, which can handle arbitrary delays and losses, relies on simple state changes which can done at packet rates. In particular, DCC relies on link reversal routing, adapted to suit the data plane, e.g., to handle message loss.

• Borokhovich et al.: The show must go on: Fundamental data plane connectivity services for dependable SDNs, Elsevier ComCom, 2018.
  

  RELEVANCE: interesting
  

  The paper argues that in order to provide a high availability, connectivity, and robustness, dependable SDNs must implement functionality for inband network traversals, e.g., to find failover paths in the presence link failures. Three fundamentally different mechanisms are described: simple stateless mechanisms, efficient mechanisms based on packet tagging, and mechanisms based on dynamic state at the switches.

• Thomas Holterbach et al.: Blink: Fast Connectivity Recovery Entirely in the Data Plane, USENIX NSDI, 2019.
  

  RELEVANCE: important
  

  The paper explores new possibilities, created by programmable switches, for fast dataplane-driven rerouting upon signals triggered by traffic disruptions. The proposed method, Blink, uses exploits TCP-induced signals to detect failures; when compounded over multiple flows, TCP behavior creates a strong and characteristic failure signal. Blink analyzes TCP flows, at line rate, to reliably and quickly detect major traffic disruptions and recover data-plane connectivity. Evaluation results on a P4 implementation of Blink running on real Tofino switch indicate that it can achieve sub-second rerouting for realistic Internet traffic and scales to protect large fractions of realistic traffic.

In-network Computation

• Paolo Costa et al.: Camdoop: Exploiting In-network Aggregation for Big Data Applications, USENIX NSDI, 2012.
  

  RELEVANCE: important
  

  This paper makes the case that many massive-scale information processing and real-time applications may benefit from pushing data-aggregation load from the network edge into the network. This is because in many of these applications data is aggregated during the computation process and the output size is a fraction of the input size. The authors explore a different point in the design space, whereby instead of increasing the network bandwidth they rather implement a MapReduce-like system on a cluster design that uses a direct-connect network topology, with servers directly linked to other servers, and letting servers to perform in-network aggregation of data during the shuffle phase. Camdoop was shown to significantly reduce network traffic and provide high performance increase.

• Mai et al.: Netagg: Using middleboxes for application-specific on-path aggregation in data centres, ACM CoNEXT, 2014.
  

  RELEVANCE: mustread
  

  This paper is motivated by the performance challenges faced by data-center applications, such as Hadoop batch processing, during the data aggregation phase: if the network struggles to support many-to-few, high-bandwidth communication between servers then it can become a bottleneck. Mai et al. propose to depart from performing data aggregation at edge servers, but rather, do it more efficiently along network paths. The presented software platform, NETAGG, supports on-path aggregation for network-bound partition/aggregation applications. It is based on a middlebox-like design, in which dedicated servers that can execute aggregation functions provided by applications. The authors demonstrate that NETAGG can improve throughput substantially.

• Graham et al.: Scalable hierarchical aggregation protocol (SHArP): a hardware architecture for efficient data reduction, IEEE COMHPC, 2016.
  

  RELEVANCE: important
  

  SHArP is designed to offload computational load to the network, by relying on intelligent network devices manipulating data traversing the datacenter. SHArP is implemented in Mellanox’s SwitchIB-2 ASIC, using in-network trees to reduce data from a group of sources, and to distribute the result. Multiple parallel jobs with several partially overlapping groups are supported, and pipelining is used for improving latency further.

• Sapio et al.: In-Network Computation is a Dumb Idea Whose Time Has Come, ACM HotNets, 2017.
  

  RELEVANCE: important
  

  The authors ask the question, given that programmable data plane hardware creates new opportunities for infusing intelligence into the network, what kinds of computation should be delegated to the data plane? The paper discusses the opportunities and challenges for co-designing data center distributed systems with their network layer, under the constraints imposed by the limitations of the network machine architecture of programmable devices. They find that, in particular, aggregation functions raise opportunities to exploit the limited computation power of networking hardware to lessen network congestion and improve the overall application performance.

• Liu et al.: IncBricks: Toward In-Network Computation with an In-Network Cache, SIGOPS Oper. Syst. Rev., 2017.
  

  RELEVANCE: interesting
  

  This paper presents IncBricks, an in-network caching fabric with basic computing primitives. IncBricks is a hardware-software co-designed system that supports caching in the network using a programmable network middlebox. As a key-value store accelerator, our prototype lowers request latency by over 30% and doubles throughput for 1024 byte values in a common cluster configuration. The results demonstrate the effectiveness of in-network computing and that efficient datacenter network request processing is possible if we carefully split the computation across programmable switches, network accelerators, and end hosts.

• Naveen Sharma et al.: Evaluating the Power of Flexible Packet Processing for Network Resource Allocation, USENIX NSDI, 2017.
  

  RELEVANCE: important
  

  The main contribution of this work is providing a set of general building blocks that mask the limitations of programmable switches (limited state, support limited types of operations, limited per-packet computation) using approximation techniques and thereby enabling the implementation of realistic network protocols. These building blocks are then used to tackle the network resource allocation problem within datacenters and realize approximate variants of congestion control and load balancing protocols, such as XCP, RCP, and CONGA, that require explicit support from the network. The evaluations show that the proposed approximations are accurate and that they do not exceed the hardware resource limits associated with flexible switches.

• Sanvito et al.: Can the Network Be the AI Accelerator, SIGCOMM NetCompute, 2018.
  

  RELEVANCE: mustread
  

  This paper analyzes the feasibility and opportunities from using programmable network devices (e.g., network cards and switches), as accelerators for Artificial Neural Networks (NNs). In particular, the authors investigate the properties of NN processing on CPUs, and find that programmable network devices may indeed be a suitable engine, for implementing a CPU’s NN co-processor.

• Giuseppe Siracusano et al.: In-network Neural Networks, unpublished manuscript, 2018.
  

  RELEVANCE: important
  

  The paper presents N2Net, a system that implements binary neural networks using commodity switching chips deployed in network switches and routers. N2Net shows that these devices can run simple neural network models, whose input is encoded in the network packets' header, at packet processing speeds (billions of packets per second). Furthermore, the authors' experience highlights that switching chips could support even more complex models, provided that some minor and cheap modifications to the chip's design are applied.

Distributed Consensus

• Dang et al.: NetPaxos: Consensus at Network Speed, ACM SOSR, 2015.
  

  RELEVANCE: important
  

  This paper explores the possibility of implementing the widely deployed Paxos consensus protocol in network devices. Two different approaches are presented: (1) a detailed design description for implementing the full Paxos logic in SDN switches, which identifies a sufficient set of required OpenFlow extensions, and (2) an alternative, optimistic protocol which can be implemented without changes to the OpenFlow API, but relies on assumptions about how the network orders messages. Although neither of these protocols can be fully implemented without changes to the underlying switch firmware, the authors argue that such changes are feasible in existing hardware.

• Dang et al.: Paxos Made Switch-y, ACM SIGCOMM Comput. Commun. Rev., 2016.
  

  RELEVANCE: interesting
  

  This paper posits that there are significant performance benefits to be gained by implementing the Paxos protocol, the foundation for building many fault-tolerant distributed systems and services, in network devices. The paper describes an implementation of Paxos in P4.

• Li et al.: Be Fast, Cheap and in Control with SwitchKV, USENIX NSDI, 2016.
  

  RELEVANCE: interesting
  

  SwitchKV implements a key-value store system leveraging SDN network switches to balance the cache servers workload routing the traffic based on the content of the network packets. To identify the content of a packet, the key of a key-value entry is encoded in the packet header. A hybrid cache strategy keeps the cache and switch forwarding rules updated, finally achieving significant improvements in both system's throughput and latency.

• Schiff et al.: In-band synchronization for distributed SDN control planes, SIGCOMM CCR, 2016.
  

  RELEVANCE: important
  

  The paper considers the design of consistent distributed control planes in which the actions performed on the data plane by different controllers need to be synchronized. The authors propose a synchronization framework for based on atomic transactions implemented in the data plane switches and show that their approach allows to realize fundamental consensus primitives in the presence of controller failures. They also discuss applications for consistent policy composition. With a proof-of-concept implementation, it is demonstrated that the framework can be implemented using the standard OpenFlow protocol.

• Xin et al.: NetCache: Balancing Key-Value Stores with Fast In-Network Caching, ACM SOSP, 2017.
  

  RELEVANCE: interesting
  

  NetCache implements a small cache in for key-velue stores in a programmable hardware switch data plane. The switch works as a cache at the datacenter's rack level, handling requests directed to the rack's server. The implementation deals with consistency problems and shows how to overcome the constraints of hardware to provide throughput and latency improvements.

• Li et al.: KV-Direct: High-Performance In-Memory Key-Value Store with Programmable NIC, ACM SOSP, 2017.
  

  RELEVANCE: interesting
  

  The paper presents an interesting alternative of NetCache: instead of using in-network programmable switches to cache key-value pairs it leverages programmable NIC to accelerate key-value stores in an "end-to-end" fashion. In particular, KV-Direct extends RDMA using programmable NICs to enable remote direct key-value access to the main host memory, yielding more than 1.2 billion operations per second using 10 parallel NICs.

• Xin Jin et al.: NetChain: Scale-Free Sub-RTT Coordination, USENIX NSDI, 2018.
  

  RELEVANCE: important
  

  This paper presents NetChain, a new approach that provides scale-free sub-RTT coordination in data centers. NetChain exploits programmable switches to store data and process queries entirely in the network data plane. This eliminates the query processing at coordination servers and cuts the end-to-end latency to as little as half of an RTT. New protocols and algorithms are designed for NetChain guarantees strong consistency and handles switch failures efficiently.

Monitoring, Telemetry, and Measurement

• Jeyakumar et al.: Millions of little minions: Using packets for low latency network programming and visibility, SIGCOMM CCR, 2014.
  

  RELEVANCE: important
  

  Jeyakumar et al. present an approach to give end-hosts visibility into network behavior and to quickly introduce new data plane functionality, via a new Tiny Packet Program (TTP) interface. TTPs are embedded into packets by endhosts and can actively query and manipulate internal network state. The idea is motivated by a clear work division: switches forward and execute TTPs in-band at line rate, and endhosts perform arbitrary (and easily updated) computation on network state. The paper presents a number of use case descriptions motivating In‐band Network Telemetry (INT).

• Kim et al.: In-band Network Telemetry via Programmable Dataplanes, ACM SIGCOMM, 2015.
  

  RELEVANCE: important
  

  In-band Network Telemetry (INT) is a powerful new network-diagnostics and debug mechanism, which allows, e.g., to diagnose performance problems related to latency spikes. The INT abstraction allows data packets to query switch-internal state (e.g., queue size, link utilization, and queuing latency). The paper reports on a prototype implemented in the P4 language, hence supporting various different programmable network devices.

• Gong et al.: Towards Accurate Online Traffic Matrix Estimation in Software-defined Networks, ACM SOSR, 2015.
  

  RELEVANCE: interesting
  

  The paper seeks for accurate, feasible and scalable traffic matrix estimation approaches, by designing feasible traffic measurement rules that can be installed in TCAM entries of SDN switches. The statistics of the measurement rules are collected by the controller to estimate fine-grained traffic matrix. Two strategies are proposes, called Maximum Load Rule First (MLRF) and Large Flow First (LFF), both of which LFF satisfy the flow aggregation constraints (determined by associated routing policies) and have low-complexity.

• Kim et al.: In-band Network Telemetry (INT), P4 Consortium, 2015.
  

  RELEVANCE: mustread
  

  A specification of In-band Network Telemetry (INT) using P4.

• Sivaraman et al.: Heavy-Hitter Detection Entirely in the Data Plane, ACM SOSR, 2017.
  

  RELEVANCE: interesting
  

  The paper describes HashPipe, a heavy hitter detection algorithm using programmable data planes. HashPipe implements a pipeline of hash tables which retain counters for heavy flows while evicting lighter flows over time. HashPipe is prototyped in P4 and evaluated with packet traces from an ISP backbone link and a data center.

• Ghasemi et al.: Dapper: Data plane performance diagnosis of TCP, ACM SOSR, 2017.
  

  RELEVANCE: important
  

  Dapper is a system which leverages emerging edge devices offering flexible and high-speed packet processing on commodity hardware, to diagnose cloud performance problems in a timely manner. In particular, Dapper analyzes TCP performance in real time near the end-hosts, i.e., at the hypervisor, NIC, or top-of-rack switch, by determining whether a connection is limited by the sender, the network, or the receiver. Dapper was prototyped in P4.

• Huang et al.: SketchVisor: Robust Network Measurement for Software Packet Processing, ACM SIGCOMM, 2017.
  

  RELEVANCE: interesting
  

  The paper presents SketchVisor, a robust network measurement framework, which augments sketch-based measurement in the data plane with a fast path that is activated under high traffic load to provide high-performance local measurement with slight accuracy degradation. It further recovers accurate network-wide measurement results via compressive sensing. A SketchVisor prototype is build on top of Open vSwitch; testbed experiments show that SketchVisor achieves high throughput and high accuracy for a wide range of network measurement tasks.

Load balancing

• Katta et al.: Hula: Scalable load balancing using programmable data planes, ACM SOSR, 2016.
  

  RELEVANCE: mustread
  

  HULA is motivated by the shortcomings of ECMP as well as of existing congestion-aware load-balancing techniques such as CONGA, which, due to limited switch memory, can only maintain a limited amount of congestion-tracking state at the edge switches, and hence do not scale. HULA is a more flexible and scalable data-plane load-balancing algorithm in which each switch tracks congestion only for the best path to a destination through a neighboring switch. HULA is designed for programmable switches and is programmed in P4.

• Miao et al.: SilkRoad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching ASICs, ACM SIGCOMM, 2017.
  

  RELEVANCE: interesting
  

  The paper explores how to use programmable switching ASICs to build much faster load balancers than have been built before. The proposed system, called SilkRoad, is defined in a 400 lines of P4 and, when compiled to a state-of-the-art switching ASIC, it can load-balance ten million connections simultaneously at line rate.

• Bremler-Barr et al.: Load Balancing Memcached Traffic Using Software Defined Networking, IFIP Networking, 2017.
  

  RELEVANCE: interesting
  

  Memcached is an in-memory key-value distributed caching solution, commonly used by web servers for fast content delivery. In order to deal with skewed distributions of key popularity in key-value stores, the authors propose and implement MBalancer, a switch-based L7 load balancing scheme, which offloads requests from bottleneck Memcached servers. MBalancer runs as an SDN application, identifies the (typically small number of) hot keys, duplicates these hot keys to many (or all) Memcached servers, and adjusts the switches' forwarding tables accordingly. Experiences with an implementation of MBalancer on a hardware-based OpenFlow switch indicate significant throughput boost and latency reduction.

Control plane acceleration

• Molero et al.: Hardware-Accelerated Network Control Planes, ACM HotNets, 2018.
  

  RELEVANCE: mustread
  

  This seminal paper challenges a fundamental design principle of modern network architecture that the control plane software-based. With the advent of programmable switch ASICs, which can run complex logic at line rate, the paper revisits this principle, by accelerating the control plane offloading some of its tasks directly to the network hardware. Some simple control plane functionality can already be successfully offloaded to P4 hardware, including failure detection and notification, connectivity retrieval, and even policy-based routing protocols, but complex cases involve several tradeoffs and limitations; the paper outlines these and sketches interesting future research directions towards hardware-software co-design of network control planes.

• Kannan et al.: Precise Time-synchronization in the Data-Plane Using Programmable Switching ASICs, ACM SOSR, 2019.
  

  RELEVANCE: interesting
  

  Current implementations of time synchronization protocols, like PTP, handle the protocol stack in the control-plane. The paper explores the possibility of using programmable switching ASICs to design and implement a time synchronization protocol, DPTP, with the core logic running in the data-plane. Comprehensive measurement studies running a a dataplane-accelerated DPTP implemented in P4 running on a Barefoot Tofino switch shows that DPTP can achieve median and 99th percentile synchronization error of 19 ns and 47 ns, even under heavy network load.

History

• Schwartz et al.: Smart packets: Applying active networks to network management, ACM TOCS, 2000.
  

  RELEVANCE: interesting
  

  One intellectual precursor to programmable networks is the Active Networks concept. This paper surveys the application of active networks technology to network management and monitoring. The main idea of Smart Packets, which contain programs written in a safe language, is to move management decision points closer to the nodes being managed, as well as to target specific aspects of the node for information.

• Feamster et al.: The Road to SDN, ACM Queue, 2013.
  

  RELEVANCE: mustread
  

  An intellectual history of programmable networks. A mustread.

• Zilberman et al.: Reconfigurable Network Systems and Software-Defined Networking, Proceedings of the IEEE, 2015.
  

  RELEVANCE: interesting
  

  The paper reviews the state of the art in reconfigurable network systems, covering hardware reconfiguration, SDN, and the interplay between them. It starts with a tutorial on software-defined networks, then continues to discuss programming languages as the linking element between different levels of software and hardware in the network, reviews electronic switching systems, highlighting programmability and reconfiguration aspects, and describes the trends in reconfigurable network elements.

• Nick McKeown et al.: Programmable Forwarding Planes are Here to Stay, ACM SIGCOMM NetPL, 2017.
  

  RELEVANCE: mustread
  

  A keynote from Nick McKeown at NetPL'17 on the many great research ideas and new languages that have emerged for programmable forwarding. The talk considers how we got here, why programmable forwarding planes are inevitable, why now is the right time, why they are a final frontier for SDN, and why they are here to stay.

Deployments

• Casado et al.: Ethane: Taking Control of the Enterprise, ACM SIGCOMM, 2007.
  

  RELEVANCE: mustread
  

  A seminal paper for deploying SDN in enterprise networks, this paper presents Ethane, a network architecture allowing managers to define a single network-wide fine-grain policy and then enforcing it directly. Ethane couples extremely simple flow-based Ethernet switches with a centralized controller that manages the admittance and routing of flows. While radical, this design is backwards-compatible with existing hosts and switches. Ethane was implemented in both hardware and software, supporting both wired and wireless hosts.

• Jin et al.: Softcell: Scalable and flexible cellular core network architecture, ACM CoNEXT, 2013.
  

  RELEVANCE: important
  

  SoftCell aims to overcome today's expensive, inflexible and complex cellular core networks by supporting fine-grained policies for mobile devices, using commodity switches and servers. In particular, SoftCell allows to flexibly route traffic through sequences of middleboxes based on subscriber attributes and applications. Scalability is achieved by minimizing the size of the forwarding tables, using aggregation, and by performing packet classification at the access switches, next to the base stations.

• Jain et al.: B4: Experience with a Globally-deployed Software Defined Wan, ACM SIGCOMM, 2013.
  

  RELEVANCE: important
  

  The paper presents the design, implementation, and evaluation of B4, a private WAN connecting Google's data centers across the planet. B4 has a number of unique characteristics: (1) massive bandwidth requirements deployed to a modest number of sites, (2) elastic traffic demand that seeks to maximize average bandwidth, and (3) full control over the edge servers and network, which enables rate limiting and demand measurement at the edge. These characteristics led to a Software Defined Networking architecture using OpenFlow to control relatively simple switches built from merchant silicon.

• Qazi et al.: A High Performance Packet Core for Next Generation Cellular Networks, ACM SIGCOMM, 2017.
  

  RELEVANCE: important
  

  To support deploying SDNs into the Evolved Packet Core (EPC), the paper presents the design and evaluation of a system architecture for a software EPC that achieves high and scalable performance. The authors postulate that the poor scaling of existing EPC systems stems from the manner in which the system is decomposed, which leads to device state being duplicated across multiple components, which in turn results in frequent interactions between the different components. An alternate approach is proposed in which state for a single device is consolidated in one location and EPC functions are reorganized for efficient access to this consolidated state. A prototype for PEPC is also presented, as a software EPC that implements the key components of the design.

Simulators and evaluation platforms

• Bai et al.: NS4: Enabling Programmable Data Plane Simulation, ACM SOSR, 2018.
  

  RELEVANCE: interesting
  

  The paper presents a new simulator platform on top of ns-3 specifically tailored to programmable dataplanes and P4 in particular. Evaluations show tht NS4 can effectively simulate representative P4 programs and scales to large-scale P4-enabled networks at a low cost.