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:
@inproceedings{sivaraman2015towards,
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}
}