Programmable Packet Scheduling at Line Rate

By Anirudh Sivaraman, Suvinay Subramanian, Mohammad Alizadeh, S. Chole, Shang-Tse Chuang, Anurag Agrawal, Hari Balakrishnan, Tom Edsall, Sachin Rajsekhar Katti, Nick McKeown. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2016

317 citations recorded by the source corpus.

Switches today provide a small menu of scheduling algorithms. While we can tweak scheduling parameters, we cannot modify algorithmic logic, or add a completely new algorithm, after the switch has been designed. This paper presents a design for a {\em programmable} packet scheduler, which allows scheduling algorithms---potentially algorithms that are unknown today---to be programmed into a switch without requiring hardware redesign. Our design uses the property that scheduling algorithms make two decisions: in what order to schedule packets and when to schedule them. Further, we observe that in many scheduling algorithms, definitive decisions on these two questions can be made when packets are enqueued. We use these observations to build a programmable scheduler using a single abstraction: the push-in first-out queue (PIFO), a priority queue that maintains the scheduling order or time. We show that a PIFO-based scheduler lets us program a wide variety of scheduling algorithms. We present a hardware design for this scheduler for a 64-port 10 Gbit/s shared-memory (output-queued) switch. Our design costs an additional 4% in chip area. In return, it lets us program many sophisticated algorithms, such as a 5-level hierarchical scheduler with programmable decisions at each level.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/6caa2eb7212cb5e53721592ec9ac7d9c10d83d2d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Heavy-Hitter Detection Entirely in the Data Plane (2016, background): “Further, maintaining data structures like sorted linked lists [28] or priority queues [41] requires multiple memory accesses within the per-packet time budget.”
Language-Directed Hardware Design for Network Performance Monitoring (2017, background): “Programmable switches [3, 13, 25] now support flexible parsing [39], header processing [33, 56], and scheduling [57].”
DRILL: Micro Load Balancing for Low-latency Data Center Networks (2017, unknown): “Using the minimum chip area estimate of 200 mm2 in [38], similar to [66], we estimate this to be less than 1% of the area of a typical switch chip.”
Packet Transactions: High-Level Programming for Line-Rate Switches (2015, background): “Examples include active queue management [53, 52, 67, 74, 76], scheduling [88], congestion control with switch feedback [64, 93, 60, 28], network measurement [98, 51, 50], security [34], and trafﬁc load balancing [27].”
Routing or Computing? The Paradigm Shift Towards Intelligent Computer Network Packet Transmission Based on Deep Learning (2017, background): “…the packet processing logic into hardware continues to improve the routers’ line rates up to 100 Gbps, applying new network trafﬁc control algorithms remains a challenging issue because of the shortcoming of the purpose-designed hardware in terms of feasibility and extensibility [6], [20].”