Packet Transactions
Authors:
Open Access
- 22 August 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 15-28
Abstract
Many algorithms for congestion control, scheduling, network measurement, active queue management, and traffic engineering require custom processing of packets in the data plane of a network switch. To run at line rate, these data-plane algorithms must be implemented 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 chips. The key challenge is that many data-plane algorithms create and modify algorithmic state. To achieve line-rate programmability for stateful algorithms, we introduce the notion of a packet transaction: a sequential packet-processing 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 way to express sophisticated data-plane algorithms, and show that these algorithms can be run at line rate with modest estimated chip-area overhead.Keywords
Funding Information
- NSF (CNS-1563826)
This publication has 39 references indexed in Scilit:
- Enabling End-Host Network Functions2015
- Jupiter Rising2015
- The case for an intermediate representation for programmable data planes2015
- ChlorophyllACM SIGPLAN Notices, 2014
- Controlling Queue DelayQueue, 2012
- Automatically partitioning packet processing applications for pipelined architecturesACM SIGPLAN Notices, 2005
- An improved data stream summary: the count-min sketch and its applicationsJournal of Algorithms, 2005
- The click modular routerACM Transactions on Computer Systems, 2000
- Random early detection gateways for congestion avoidanceIEEE/ACM Transactions on Networking, 1993
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991