Scheduling in practice

ABSTRACT

In queueing theory, it has been known for a long time that the scheduling policy used in a system greatly impacts user-perceived performance. For example, it has been proven in the 1960's that size-based scheduling policies that give priority to short jobs are optimal with respect to mean response time. Yet, virtually no systems today implement these policies. One reason is that real systems are significantly more complex than a theoretical M/M/1 or M/G/1 queue and it is not obvious how to implement some of these policies in practice. Another reason is that there is a fear that the big jobs will "starve", or be treated unfairly as compared to Processor-Sharing (PS). In this article we show, using two important real world applications, that size-based scheduling can be used in practice to greatly improve mean response times in real systems, without causing unfairness or starvation. The two applications we consider are connection scheduling in web servers and packet scheduling in network routers.

REFERENCES

• 1: S. Aalto and U. Ayesta. On the non-optimality of the fb discipline for imrl service times. Journal of Applied Probability, pages 523--534, 2006.
• 2: K. Avrachenkov, U. Ayesta, P. Brown, and N. Nyberg. Differentiation between short and long tcp flows: Predictability of the response time. In Proc. IEEE INFOCOM, March 2004.
• 3: Gaurav Banga , Peter Druschel, Measuring the capacity of a Web server under realistic loads, World Wide Web, v.2 n.1-2, p.69-83, 1999 [doi>10.1023/A:1019292504731]
• 4: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 5: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 6: Patrick Brown, Comparing FB and PS scheduling policies, ACM SIGMETRICS Performance Evaluation Review, v.34 n.3, December 2006 [doi>10.1145/1215956.1215965]
• 7: K. Claffy, G. Miller, and K. Thompson. The nature of the beast: Recent traffic measurements from an internet backbone. In Proceedings of INET, July 1998.
• 8: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 9: Supratim Deb , Ayalvadi Ganesh , Peter Key, Resource allocation between persistent and transient flows, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.302-315, April 2005 [doi>10.1109/TNET.2005.845544]
• 10: H. Feng and M. Misra. Mixed scheduling disciplines for network flows. In The Fifth Workshop of Mathematical Performance Modeling and Analysis (MAMA 2003), San Diego, California, USA, June 2000.
• 11: D. Ferrero and G. Urvoy-Keller. Size-based scheduling to improve fairness and performance in 802.11 networks. Technical Report RR 2125, Institut Eurecom, France, Dec, 2006.
• 12: M. Franceschinis, M. Mellia, M. Meo, and M. Munaf. Measuring TCP over wifi: A real case. In 1st workshop on Wireless Network Measurements (Winmee), Riva Del Garda, Italy, 2005.
• 13: Zhenghua Fu , Haiyun Luo , Petros Zerfos , Songwu Lu , Lixia Zhang , Mario Gerla, The Impact of Multihop Wireless Channel on TCP Performance, IEEE Transactions on Mobile Computing, v.4 n.2, p.209-221, March 2005 [doi>10.1109/TMC.2005.30]
• 14: Mingwei Gong , Carey Williamson, Simulation Evaluation of Hybrid SRPT Scheduling Policies, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04), p.355-363, October 04-08, 2004
• 15: L. Guo and I. Matta. Differentiated control of web traffic: A numerical analysis. In SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks, August 2002.
• 16: P. Gupta and P. R. Kumar. The capacity of wireless networks. Information Theory, IEEE Transactions on, 46(2):388--404, 2000.
• 17: Mor Harchol-Balter , Bianca Schroeder , Nikhil Bansal , Mukesh Agrawal, Size-based scheduling to improve web performance, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.207-233, May 2003 [doi>10.1145/762483.762486]
• 18: Vikas Kawadia , P. R. Kumar, Experimental investigations into TCP performance over wireless multihop networks, Proceeding of the 2005 ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080148.1080155]
• 19: L. Kleinrock. Queuing Systems, Volume II: Computer Applications. Wiley, New York, 1976.
• 20: Zhen Liu , Nicolas Niclausse , César Jalpa-Villanueva, Traffic model and performance evaluation of Web servers, Performance Evaluation, v.46 n.2-3, p.77-100, October 2001 [doi>10.1016/S0166-5316(01)00046-3]
• 21: Dong Lu , Huanyuan Sheng , Peter Dinda, Size-Based Scheduling Policies with Inaccurate Scheduling Information, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'04), p.31-38, October 04-08, 2004
• 22: David T. McWherter , Bianca Schroeder , Anastassia Ailamaki , Mor Harchol-Balter, Priority Mechanisms for OLTP and Transactional Web Applications, Proceedings of the 20th International Conference on Data Engineering, p.535, March 30-April 02, 2004
• 23: David T. McWherter , Bianca Schroeder , Anastassia Ailamaki , Mor Harchol-Balter, Improving Preemptive Prioritization via Statistical Characterization of OLTP Locking, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.446-457, April 05-08, 2005 [doi>10.1109/ICDE.2005.78]
• 24: C. D. Murta and T. P. Corlassoli. Fastest connection first: A new scheduling policy for web servers. In Proc. of the 18th International Teletraffic Congress (ITC-18), 2003.
• 25: M. Nuyens and A. Wierman. The foreground-background queue: a survey. Technical report, under submission, 2006.
• 26: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 27: I. Rai. QOS Support in Edge Routers. PhD thesis, Télécom Paris, Institut Eurecom, France, Sept. 2004.
• 28: I. Rai, E. W. Biersack, and G. Urvoy-Keller. Size-based scheduling to improve the performance of short TCP flows. IEEE Network Magazine, 19(1):12--17, January-February 2005.
• 29: Idris A. Rai , Guillaume Urvoy-Keller , Ernst W. Biersack, Analysis of LAS scheduling for job size distributions with high variance, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 30: Idris A. Rai , Guillaume Urvoy-Keller , Mary K. Vernon , Ernst W. Biersack, Performance analysis of LAS-based scheduling disciplines in a packet switched network, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 31: Mayank Rawat , Ajay Kshemkalyani, SWIFT: Scheduling in Web Servers for Fast Response Time, Proceedings of the Second IEEE International Symposium on Network Computing and Applications, p.51, April 16-18, 2003
• 32: David Raz , Hanoch Levy , Benjamin Avi-Itzhak, A resource-allocation queueing fairness measure, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 33: A. Salvatori. LAS scheduler implementation and performance analysis, institut eurecom, Feb. 2005.
• 34: L. E. Schrage. The queue m/g/1 with feedback to lower priority queues. Management Science, 13(7):466--474, 1967.
• 35: Bianca Schroeder , Mor Harchol-Balter, Web servers under overload: How scheduling can help, ACM Transactions on Internet Technology (TOIT), v.6 n.1, p.20-52, February 2006 [doi>10.1145/1125274.1125276]
• 36: Bianca Schroeder , Mor Harchol-Balter , Arun Iyengar , Erich Nahum, Achieving Class-Based QoS for Transactional Workloads, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.153, April 03-07, 2006 [doi>10.1109/ICDE.2006.11]
• 37: Bianca Schroeder , Mor Harchol-Balter , Arun Iyengar , Erich Nahum , Adam Wierman, How to Determine a Good Multi-Programming Level for External Scheduling, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.60, April 03-07, 2006 [doi>10.1109/ICDE.2006.78]
• 38: Bianca Schroeder , Adam Wierman , Mor Harchol-Balter, Open versus closed: a cautionary tale, Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, p.18-18, May 08-10, 2006, San Jose, CA
• 39: Standard Performance Evaluation Corporation. SPECweb99. http://www.specbench.org/osg/web99/.
• 40: Transaction Processing Performance Council. TPC benchmark W (web commerce). Number Revision 1.8, February 2002.
• 41: G. Trent and M. Sake. WebStone: The first generation in HTTP server benchmarking, http: - //www.mindcraft.com/webstone/paper.html.
• 42: A. Wierman, N. Bansal, and M. Harchol-Balter. A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues. Operations Research Letters, 32(1):73--76, Jan. 2004.
• 43: Adam Wierman , Mor Harchol-Balter, Classifying scheduling policies with respect to unfairness in an M/GI/1, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 44: Adam Wierman , Mor Harchol-Balter, Classifying scheduling policies with respect to higher moments of conditional response time, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 45: Adam Wierman , Mor Harchol-Balter , Takayuki Osogami, Nearly insensitive bounds on SMART scheduling, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 46: Shanchieh Jay Yang , Gustavo de Veciana, Enhancing both network and user performance for networks supporting best effort traffic, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.349-360, April 2004 [doi>10.1109/TNET.2004.826280]
• 47: Jingyu Zhou , Tao Yang, Selective early request termination for busy internet services, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135866]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems
      D.4.8 Performance
          Subjects: Operational analysis

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance