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
HotNets 2015: Fourteenth ACM Workshop on Hot Topics in Networks, Philadelphia, Pennsylvania, November 2015

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

[PDF (250KB)]

Bibtex Entry:

   author =       "Anirudh Sivaraman and Suvinay Subramanian and Anurag Agrawal and Sharad Chole and Shang-Tse Chuang and Tom Edsall and Mohammad Alizadeh and Sachin Katti and Nick McKeown and Hari Balakrishnan",
   title =        "{Towards Programmable Packet Scheduling}",
   booktitle =    {HotNets 2015: Fourteenth ACM Workshop on Hot Topics in Networks},
   year =         {2015},
   month =        {November},
   address =      {Philadelphia,  Pennsylvania}