Radhika Mittal
Sylvia Ratnasamy
Scott Shenker
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.
Supplemental Material
- Internet2. http://www.internet2.edu/.Google Scholar
- The Network Simulator NS-2. http://www.isi.edu/nsnam/ns/.Google Scholar
- M. Alizadeh, S. Yang, M. Sharif, S. Katti, N. McKeown, B. Prabhakar, and S. Shenker. pFabric: Minimal Near-optimal Datacenter Transport. In Proc. ACM SIGCOMM, 2013. Google ScholarDigital Library
- M. Allman. Comments on bufferbloat. ACM SIGCOMM Computer Communication Review, 2013. Google ScholarDigital Library
- T. Benson, A. Akella, and D. Maltz. Network Traffic Characteristics of Data Centers in the Wild. In Proc. ACM IMC, 2012. Google ScholarDigital Library
- R. Bhagwan and B. Lin. Fast and Scalable Priority Queue Architecture for High-Speed Network Switches. In Proc. IEEE Infocom, 2000.Google ScholarCross Ref
- P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker. P4: Programming Protocol-independent Packet Processors. ACM SIGCOMM Computer Communication Review, 2014. Google ScholarDigital Library
- P. Bosshart, G. Gibb, H.-S. Kim, G. Varghese, N. McKeown, M. Izzard, F. Mujica, and M. Horowitz. Forwarding Metamorphosis: Fast Programmable Match-action Processing in Hardware for SDN. In Proc. ACM SIGCOMM, 2013. Google ScholarDigital Library
- M. Casado, T. Koponen, S. Shenker, and A. Tootoonchian. Fabric: A Retrospective on Evolving SDN. In Proc. ACM HotSDN, 2012. Google ScholarDigital Library
- S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhakar. Matching output queueing with a combined input/output-queued switch. IEEE Journal on Selected Areas in Communications, 1999. Google ScholarDigital Library
- D. D. Clark, S. Shenker, and L. Zhang. Supporting Real-time Applications in an Integrated Services Packet Network: Architecture and Mechanism. ACM SIGCOMM Computer Communication Review, 1992. Google ScholarDigital Library
- A. Demers, S. Keshav, and S. Shenker. Analysis and Simulation of a Fair Queueing Algorithm. ACM SIGCOMM Computer Communication Review, 1989. Google ScholarDigital Library
- N. Dukkipati and N. McKeown. Why Flow-Completion Time is the Right Metric for Congestion Control. ACM SIGCOMM Computer Communication Review, 2006. Google ScholarDigital Library
- S. Floyd and V. Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Trans. Netw., 1993. Google ScholarDigital Library
- A. Gupta, M. T. Hajiaghayi, and H. Räcke. Oblivious Network Design. In Proc. ACM-SIAM Symposium on Discrete Algorithm (SODA), 2006. Google ScholarDigital Library
- A. Ioannou and M. G. H. Katevenis. Pipelined Heap (Priority Queue) Management for Advanced Scheduling in High-speed Networks. IEEE/ACM Trans. Netw., 2007. Google ScholarDigital Library
- R. Jain, D.-M. Chiu, and W. Hawe. A Quantitative Measure Of Fairness and Discrimination For Resource Allocation In Shared Computer Systems. CoRR, arXiv:cs/9809099, 1998.Google Scholar
- D. Katabi, M. Handley, and C. Rohrs. Congestion Control for High Bandwidth-Delay Product Networks. In Proc. ACM SIGCOMM, 2002. Google ScholarDigital Library
- J. Y.-T. Leung. A new algorithm for scheduling periodic, real-time tasks. Algorithmica, Springer-Verlag New York Inc., 1989.Google Scholar
- C. L. Liu and J. W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM (JACM), 1973. Google ScholarDigital Library
- R. Mittal, R. Agarwal, S. Ratnasamy, and S. Shenker. Universal Packet Scheduling. CoRR, arXiv:1510.03551, 2015. Google ScholarDigital Library
- R. Mittal, J. Sherry, S. Ratnasamy, and S. Shenker. Recursively Cautious Congestion Control. In Proc. USENIX NSDI, 2014. Google ScholarDigital Library
- K. Nichols and V. Jacobson. Controlling Queue Delay. ACM Queue, 2012. Google ScholarDigital Library
- A. K. Parekh and R. G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-node Case. IEEE/ACM Trans. Netw., 1993. Google ScholarDigital Library
- B. Raghavan, M. Casado, T. Koponen, S. Ratnasamy, A. Ghodsi, and S. Shenker. Software-defined Internet Architecture: Decoupling Architecture from Infrastructure. In Proc. ACM HotNets, 2012. Google ScholarDigital Library
- K. Ramakrishnan, S. Floyd, and D. Black. The Addition of Explicit Congestion Notification (ECN) to IP. RFC 3168, 2001. Google ScholarDigital Library
- S. Blake and D. Black and M. Carlson and E. Davies and Z. Wang and W. Weiss. An Architecture for Differentiated Services. RFC 2475, 1998. Google ScholarDigital Library
- M. Shreedhar and G. Varghese. Efficient Fair Queueing Using Deficit Round Robin. ACM SIGCOMM Computer Communication Review, 1995. Google ScholarDigital Library
- A. Sivaraman, K. Winstein, S. Subramanian, and H. Balakrishnan. No Silver Bullet: Extending SDN to the Data Plane. In Proc. ACM HotNets, 2013. Google ScholarDigital Library
- N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP Topologies with Rocketfuel. In Proc. ACM SIGCOMM, 2002. Google ScholarDigital Library
- I. Stoica, S. Shenker, and H. Zhang. Core-stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks. In Proc. ACM SIGCOMM, 1998. Google ScholarDigital Library
- I. Stoica and H. Zhang. Providing Guaranteed Services Without Per Flow Management. In Proc. ACM SIGCOMM, 1999. Google ScholarDigital Library
- L. Zhang. Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks. ACM SIGCOMM Computer Communication Review, 1990. Google ScholarDigital Library
Index Terms
- Universal Packet Scheduling
Recommendations
Universal packet scheduling
NSDI'16: Proceedings of the 13th Usenix Conference on Networked Systems Design and ImplementationIn 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, ...
Mixed Criteria Packet Scheduling
AAIM '07: Proceedings of the 3rd international conference on Algorithmic Aspects in Information and ManagementPacket scheduling in networks with quality of service constraints has been extensively studied as a single criterion scheduling problem. The assumption underlying single criterion packet scheduling is that the value of all packets can be normalized to a ...
Frame-Based Packet-Mode Scheduling for Input-Queued Switches
Most packet scheduling algorithms for input-queued switches operate on fixed-sized packets known as cells. In reality, communication traffic in many systems such as Internet runs on variable-sized packets. Motivated by potential savings of segmentation ...
Comments