Universal Packet Scheduling
Universal Packet Scheduling
复制标题
DOI：
10.1145/2834050.2834085
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
R. Mittal;R. Agarwal;Sylvia Ratnasamy;S. Shenker
中科院分区：
文献类型：
--
作者：
R. Mittal;R. Agarwal;Sylvia Ratnasamy;S. Shenker
在本文中，我们解决一个看似简单的问题：是否有一个通用的数据包调度算法？更确切地说，我们分析（理论和经验）是否有一个单一的数据包调度算法，在网络范围内的水平，可以匹配任何给定的调度算法的结果。我们发现，总的来说，答案是否定的。然而，我们从理论上表明，经典的最小松弛时间优先（LSTF）调度算法最接近于普遍的经验表明，LSTF可以密切，但不完美，重放广泛的调度算法在现实的网络设置。然后，我们评估LSTF是否可以在实践中使用，以满足各种网络范围内的目标，通过查看三个流行的性能指标（平均FCT，尾部数据包延迟和公平性），我们发现，LSTF执行相当于国家的最先进的每一个。
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.