Programmable Packet Scheduling at Line Rate

Anirudh Sivaraman, Suvinay Subramanian, Mohammad Alizadeh, Sharad Chole, Shang-Tse Chuang, Anurag Agrawal, Hari Balakrishnan, Tom Edsall, Sachin Katti, Nick McKeown
ACM SIGCOMM 2016, Florianópolis, Brazil, August 2016

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 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.


[PDF (532KB)]
URL: http://web.mit.edu/pifo

Bibtex Entry:

@inproceedings{sivaraman2016programmable,
   author =       "Anirudh Sivaraman and Suvinay Subramanian and Mohammad Alizadeh and Sharad Chole and Shang-Tse Chuang and Anurag Agrawal and Hari Balakrishnan and Tom Edsall and Sachin Katti and Nick McKeown",
   title =        "{Programmable Packet Scheduling at Line Rate}",
   booktitle =    {ACM SIGCOMM 2016},
   year =         {2016},
   month =        {August},
   address =      {Florianópolis, Brazil}
}