TY - GEN
T1 - Universal packet scheduling
AU - Mittal, Radhika
AU - Agarwal, Rachit
AU - Ratnasamy, Sylvia
AU - Shenker, Scott
N1 - Funding Information:
We are thankful to Satish Rao for his helpful tips regarding the theoretical aspects of this work and to Anirudh Sivaraman for liberally sharing his insights on hardware implementation of fine-grained priorities. We would also like to thank Aisha Mushtaq, Kay Ousterhout, Aurojit Panda, Justine Sherry, Ion Stoica and our anonymous HotNets and NSDI reviewers for their thoughtful feedback. Finally, we would like to thank our shepherd Srikanth Kandula for helping shape the final version of this paper. This work was supported by Intel Research and by the National Science Foundation under Grant No. 1117161, 1343947 and 1040838.
Funding Information:
We are thankful to Satish Rao for his helpful tips regarding the theoretical aspects of this work and to Anirudh Sivara-man for liberally sharing his insights on hardware implementation of fine-grained priorities. We would also like to thank Aisha Mushtaq, Kay Ousterhout, Aurojit Panda, Justine Sherry, Ion Stoica and our anonymous HotNets and NSDI reviewers for their thoughtful feedback. Finally, we would like to thank our shepherd Srikanth Kandula for helping shape the final version of this paper. This work was supported by Intel Research and by the National Science Foundation under Grant No. 1117161, 1343947 and 1040838.
PY - 2016
Y1 - 2016
N2 - In this paper we address a seemingly simple question: Is there a universal packet scheduling algorithm? More precisely, we analyze (both theoretically and empirically) whether there is a single packet scheduling algorithm that, at a network-wide level, can perfectly match the results of any given scheduling algorithm. We find that in general the answer is “no”. However, we show theoretically that the classical Least Slack Time First (LSTF) scheduling algorithm comes closest to being universal and demonstrate empirically that LSTF can closely replay a wide range of scheduling algorithms. We then evaluate whether LSTF can be used in practice to meet various network-wide objectives by looking at popular performance metrics (such as average FCT, tail packet delays, and fairness); we find that LSTF performs comparable to the state-of-the-art for each of them. We also discuss how LSTF can be used in conjunction with active queue management schemes (such as CoDel and ECN) without changing the core of the network.
AB - In this paper we address a seemingly simple question: Is there a universal packet scheduling algorithm? More precisely, we analyze (both theoretically and empirically) whether there is a single packet scheduling algorithm that, at a network-wide level, can perfectly match the results of any given scheduling algorithm. We find that in general the answer is “no”. However, we show theoretically that the classical Least Slack Time First (LSTF) scheduling algorithm comes closest to being universal and demonstrate empirically that LSTF can closely replay a wide range of scheduling algorithms. We then evaluate whether LSTF can be used in practice to meet various network-wide objectives by looking at popular performance metrics (such as average FCT, tail packet delays, and fairness); we find that LSTF performs comparable to the state-of-the-art for each of them. We also discuss how LSTF can be used in conjunction with active queue management schemes (such as CoDel and ECN) without changing the core of the network.
UR - http://www.scopus.com/inward/record.url?scp=85077060835&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077060835&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85077060835
T3 - Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
SP - 501
EP - 521
BT - Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
PB - USENIX Association
T2 - 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
Y2 - 16 March 2016 through 18 March 2016
ER -