Tuesday, August 23, 2016

Programmable Packet Scheduling at Line Rate

Anirudh Sivaraman (MIT CSAIL)
Suvinay Subramanian (MIT CSAIL)
Mohammad Alizadeh (MIT CSAIL)
Sharad Chole (Cisco Systems)
Shang-Tse Chuang (Cisco Systems)
Anurag Agrawal (Barefoot Networks)
Hari Balakrishnan (MIT CSAIL)
Tom Edsall (Cisco Systems)
Sachin Katti (Stanford University)
Nick McKeown (Stanford University)

Existing switches come with a small set of built in scheduling algorithms. These can be tuned with parameters, but network operators and researchers cannot implement completely new algorithms. Schedulers have resisted the push to more programmability, because there exist no abstractions for schedulers that would allow programming them at line rate.

This paper presents an abstraction for schedulers that is programmable, and for which evidence suggests that it can be implemented to run at line rate. In this abstraction, the scheduler maintains multiple priority queues, from which the scheduler periodically dequeues and forwards the packet with the highest rank (priority). The scheduler waits to send the dequeued packet until its rank is equal to the wall clock time. The scheduler is programmed by setting a packet's rank during the enqueue operation. This enables programmability, as the rank can be computed with arbitrary programs in the ingress pipeline.

The authors evaluate this new scheduling abstraction by implementing various scheduling algorithms
against the abstraction. The authors also present a hardware design of their scheduler abstraction that works at line rate for up to 1024 flows. The authors estimate that the design requires about 4% in additional chip area.

This work is exciting, as it shows a way to provide programmability for yet another aspect of routing.

Q1: How can a network operator influence when a packet is forwarded?
A1: A packet's rank represents the wall clock time at which the packet should be forwarded.
Q2: How is your approach different from a calendar queue?
A2: When applied to traffic shaping, it is exactly like a calendar queue.

Q: How can you scale up to routers that forward over 6 TBit/s?
A: We don't have a concrete design, but we believe this to be possible because people know how to scale FIFOs, and because our scheduler is implemented in flip flops.

Link to paper.