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 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, though not perfectly, replay a wide range of scheduling algorithms in realistic network settings. We then evaluate whether LSTF can be used in practice to meet various network-wide objectives by looking at three popular performance metrics (mean FCT, tail packet delays, and fairness); we find that LSTF performs comparable to the state-of-the-art for each of them.

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
Externally publishedYes
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
Country/TerritoryUnited States
CityPhiladelphia
Period11/16/1511/17/15

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

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

Cite this