TY - GEN
T1 - Programmable packet scheduling at line rate
AU - Sivaraman, Anirudh
AU - Subramanian, Suvinay
AU - Alizadeh, Mohammad
AU - Chole, Sharad
AU - Chuang, Shang Tse
AU - Agrawal, Anurag
AU - Balakrishnan, Hari
AU - Edsall, Tom
AU - Katti, Sachin
AU - McKeown, Nick
N1 - Funding Information:
We are grateful to our shepherd, Jeff Mogul, the anonymous SIGCOMM reviewers, and Amy Ousterhout for many suggestions that greatly improved the clarity of the paper. We thank Ion Stoica for helpful discussions, Robert Hunt for help with the design of the compiler, and Radhika Mittal for helping us understand LSTF. This work was partly supported by NSF grant CNS-1563826 and a gift from the Cisco Research Center. We thank the industrial partners of the MIT Center for Wireless Networks and Mobile Computing (Wireless@MIT) for their support.
Publisher Copyright:
© 2016 Copyright held by the owner/author(s).
PY - 2016/8/22
Y1 - 2016/8/22
N2 - 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.
AB - 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.
KW - Programmable scheduling
KW - Switch hardware
UR - http://www.scopus.com/inward/record.url?scp=84986559262&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84986559262&partnerID=8YFLogxK
U2 - 10.1145/2934872.2934899
DO - 10.1145/2934872.2934899
M3 - Conference contribution
AN - SCOPUS:84986559262
T3 - SIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication
SP - 44
EP - 57
BT - SIGCOMM 2016 - Proceedings of the 2016 ACM Conference on Special Interest Group on Data Communication
PB - Association for Computing Machinery, Inc
T2 - 2016 ACM Conference on Special Interest Group on Data Communication, SIGCOMM 2016
Y2 - 22 August 2016 through 26 August 2016
ER -