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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication
PublisherAssociation for Computing Machinery, Inc
Pages44-57
Number of pages14
ISBN (Electronic)9781450341936
DOIs
StatePublished - Aug 22 2016
Event2016 ACM Conference on Special Interest Group on Data Communication, SIGCOMM 2016 - Florianopolis, Brazil
Duration: Aug 22 2016Aug 26 2016

Publication series

NameSIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication

Other

Other2016 ACM Conference on Special Interest Group on Data Communication, SIGCOMM 2016
CountryBrazil
CityFlorianopolis
Period8/22/168/26/16

Keywords

  • Programmable scheduling
  • Switch hardware

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Communication
  • Computer Networks and Communications
  • Signal Processing

Fingerprint Dive into the research topics of 'Programmable packet scheduling at line rate'. Together they form a unique fingerprint.

  • Cite this

    Sivaraman, A., Subramanian, S., Alizadeh, M., Chole, S., Chuang, S. T., Agrawal, A., Balakrishnan, H., Edsall, T., Katti, S., & McKeown, N. (2016). Programmable packet scheduling at line rate. In SIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication (pp. 44-57). [2934899] (SIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication). Association for Computing Machinery, Inc. https://doi.org/10.1145/2934872.2934899