Towards programmable packet scheduling

Anirudh Sivaraman, Suvinay Subramanian, Anurag Agrawal, Sharad Chole, Shang Tse Chuang, Tom Edsall, Mohammad Alizadeh, Sachin Katti, Nick McKeown, Hari Balakrishnan

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

Abstract

Packet scheduling in switches is not programmable; operators only choose among a handful of scheduling algorithms implemented by the manufacturer. In contrast, other switch functions such as packet parsing and header processing are becoming programmable [10, 3, 6]. This paper presents a programmable packet scheduler that allows operators to program a variety of scheduling algorithms. Our design exploits the insight that any scheduling algorithm can be deconstructed into two decisions: in what order packets depart and when they depart. The algorithms only differ in how the order and departure times are computed. We show how these decisions map to two well-understood abstractions: priority and calendar queues [11]. Priority and calendar queues can then be composed together to realize a broad range of sophisticated scheduling algorithms. Further, both abstractions can be realized using the same mechanism: a programmable push-in first-out queue (PIFO) that allows a packet to push itself into an arbitrary location in a queue by programming a packet field. A PIFO is feasible in hardware. Preliminary synthesis indicates that an unoptimized hardware design meets timing at 1 GHz on a 16 nm technology node and occupies only 5% additional die area relative to existing merchant-silicon switching chips.

Original languageEnglish (US)
Title of host publicationProceedings of the 14th ACM Workshop on Hot Topics in Networks, HotNets-XIV 2015
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450340472
DOIs
StatePublished - Nov 16 2015
Event14th ACM Workshop on Hot Topics in Networks, HotNets-XIV 2015 - Philadelphia, United States
Duration: Nov 16 2015Nov 17 2015

Publication series

NameProceedings of the 14th ACM Workshop on Hot Topics in Networks, HotNets-XIV 2015

Other

Other14th ACM Workshop on Hot Topics in Networks, HotNets-XIV 2015
CountryUnited States
CityPhiladelphia
Period11/16/1511/17/15

Keywords

  • Programmable scheduling
  • Switch hardware

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Towards programmable packet scheduling'. Together they form a unique fingerprint.

Cite this