Universal packet scheduling

Radhika Mittal, Rachit Agarwal, Sylvia Ratnasamy, Scott Shenker

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

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
PublisherUSENIX Association
Pages501-521
Number of pages21
ISBN (Electronic)9781931971294
StatePublished - Jan 1 2016
Externally publishedYes
Event13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016 - Santa Clara, United States
Duration: Mar 16 2016Mar 18 2016

Publication series

NameProceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016

Conference

Conference13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016
CountryUnited States
CitySanta Clara
Period3/16/163/18/16

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

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

  • Cite this

    Mittal, R., Agarwal, R., Ratnasamy, S., & Shenker, S. (2016). Universal packet scheduling. In Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016 (pp. 501-521). (Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016). USENIX Association.