Programmable Packet Scheduling at Line Rate
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 sche...
| Main Authors: | , , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110763 https://orcid.org/0000-0003-4034-0918 https://orcid.org/0000-0001-7701-8303 https://orcid.org/0000-0002-0014-6742 https://orcid.org/0000-0002-1455-9652 |
| _version_ | 1826202704362340352 |
|---|---|
| author | McKeown, Nick Chole, Sharad Chuang, Shang-Tse Agrawal, Anurag Edsall, Tom Sivaraman Kaushalram, Anirudh Subramanian, Suvinay Alizadeh Attar, Mohammadreza Balakrishnan, Hari Katti, Sachin Rajsekhar |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science McKeown, Nick Chole, Sharad Chuang, Shang-Tse Agrawal, Anurag Edsall, Tom Sivaraman Kaushalram, Anirudh Subramanian, Suvinay Alizadeh Attar, Mohammadreza Balakrishnan, Hari Katti, Sachin Rajsekhar |
| author_sort | McKeown, Nick |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:14:15Z |
| format | Article |
| id | mit-1721.1/110763 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:14:15Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1107632022-09-28T00:49:47Z Programmable Packet Scheduling at Line Rate McKeown, Nick Chole, Sharad Chuang, Shang-Tse Agrawal, Anurag Edsall, Tom Sivaraman Kaushalram, Anirudh Subramanian, Suvinay Alizadeh Attar, Mohammadreza Balakrishnan, Hari Katti, Sachin Rajsekhar Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Sivaraman Kaushalram, Anirudh Subramanian, Suvinay Alizadeh Attar, Mohammadreza Balakrishnan, Hari Katti, Sachin Rajsekhar 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. National Science Foundation (U.S.) (Grant CNS-1563826) Cisco Research Center 2017-07-18T16:17:54Z 2017-07-18T16:17:54Z 2016-08 Article http://purl.org/eprint/type/JournalArticle 9781450341936 http://hdl.handle.net/1721.1/110763 Sivaraman, Anirudh, Nick McKeown, Suvinay Subramanian, Mohammad Alizadeh, Sharad Chole, Shang-Tse Chuang, Anurag Agrawal, Hari Balakrishnan, Tom Edsall, and Sachin Katti. “Programmable Packet Scheduling at Line Rate.” Proceedings of the 2016 Conference on ACM SIGCOMM 2016 Conference - SIGCOMM ’16 (2016). https://orcid.org/0000-0003-4034-0918 https://orcid.org/0000-0001-7701-8303 https://orcid.org/0000-0002-0014-6742 https://orcid.org/0000-0002-1455-9652 en_US http://dx.doi.org/10.1145/2934872.2934899 Proceedings of the 2016 conference on ACM SIGCOMM 2016 Conference - SIGCOMM '16 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT Web Domain |
| spellingShingle | McKeown, Nick Chole, Sharad Chuang, Shang-Tse Agrawal, Anurag Edsall, Tom Sivaraman Kaushalram, Anirudh Subramanian, Suvinay Alizadeh Attar, Mohammadreza Balakrishnan, Hari Katti, Sachin Rajsekhar Programmable Packet Scheduling at Line Rate |
| title | Programmable Packet Scheduling at Line Rate |
| title_full | Programmable Packet Scheduling at Line Rate |
| title_fullStr | Programmable Packet Scheduling at Line Rate |
| title_full_unstemmed | Programmable Packet Scheduling at Line Rate |
| title_short | Programmable Packet Scheduling at Line Rate |
| title_sort | programmable packet scheduling at line rate |
| url | http://hdl.handle.net/1721.1/110763 https://orcid.org/0000-0003-4034-0918 https://orcid.org/0000-0001-7701-8303 https://orcid.org/0000-0002-0014-6742 https://orcid.org/0000-0002-1455-9652 |
| work_keys_str_mv | AT mckeownnick programmablepacketschedulingatlinerate AT cholesharad programmablepacketschedulingatlinerate AT chuangshangtse programmablepacketschedulingatlinerate AT agrawalanurag programmablepacketschedulingatlinerate AT edsalltom programmablepacketschedulingatlinerate AT sivaramankaushalramanirudh programmablepacketschedulingatlinerate AT subramaniansuvinay programmablepacketschedulingatlinerate AT alizadehattarmohammadreza programmablepacketschedulingatlinerate AT balakrishnanhari programmablepacketschedulingatlinerate AT kattisachinrajsekhar programmablepacketschedulingatlinerate |