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

Fingerprint

Scheduling algorithms
Scheduling

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

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.

Universal packet scheduling. / Mittal, Radhika; Agarwal, Rachit; Ratnasamy, Sylvia; Shenker, Scott.

Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016. USENIX Association, 2016. p. 501-521 (Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016).

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

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. Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016, USENIX Association, pp. 501-521, 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara, United States, 3/16/16.
Mittal R, Agarwal R, Ratnasamy S, Shenker S. Universal packet scheduling. In Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016. USENIX Association. 2016. p. 501-521. (Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016).
Mittal, Radhika ; Agarwal, Rachit ; Ratnasamy, Sylvia ; Shenker, Scott. / Universal packet scheduling. Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016. USENIX Association, 2016. pp. 501-521 (Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016).
@inproceedings{0483af43bddc473198e4bd3cdfb71ad9,
title = "Universal packet scheduling",
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.",
author = "Radhika Mittal and Rachit Agarwal and Sylvia Ratnasamy and Scott Shenker",
year = "2016",
month = "1",
day = "1",
language = "English (US)",
series = "Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016",
publisher = "USENIX Association",
pages = "501--521",
booktitle = "Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016",

}

TY - GEN

T1 - Universal packet scheduling

AU - Mittal, Radhika

AU - Agarwal, Rachit

AU - Ratnasamy, Sylvia

AU - Shenker, Scott

PY - 2016/1/1

Y1 - 2016/1/1

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

ER -