Adaptive and scalable comparison scheduling

ABSTRACT

The Shortest Remaining Processing Time (SRPT) scheduling disciplineis optimal and its superior performance, compared with the policies that do not use the knowledge of job sizes, can be quantified using mean-value analysis as well as our new a symptotic distribution allimits for the relatively smaller heavy-tailed jobs. However, the main difficulty in implementing SRPT in large practical systems, e.g., Web servers, is that its complexity grows with the number of jobs in the queue. Hence, in order to lower the complexity, it is natural to approximate SRPT by grouping the arrivals into a fixed (small) number of classes containing jobs of approximately equal size and then serve the classes of smaller jobs with higher priorities.

In this paper, we design a novel adaptive grouping mechanism based on relative size comparison of a newly arriving job to the preceding m arrivals. Specifically, if the newly arriving job is smallerthan k and larger than m-k of the previous m jobs, it isrouted into class k. The excellent performance of this mechanism,even for a small number of classes m+1, is demonstrated using both the asymptotic queueing analysis under heavy tails and extensive simulations. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.

REFERENCES

• 1: Venkat Anantharam, Scheduling strategies and long-range dependence, Queueing Systems: Theory and Applications, v.33 n.1-3, p.73-89, 1999
• 2: S. Asmussen, H. Schmidli, and V. Schmidt. Tail probabilities for non-standard risk and queueing processes with subexponential jumps. Adv. in Appl. Probab., 31(2):422--447, 1999.
• 3: F. Baccelli and P. Bremaud. Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurence. Springer Verlag, 1994.
• 4: N. Bansal. On the average sojourn time under M/M/1/SRPT. Operations Research Letters, 33(2):195--200, 2005.
• 5: Nikhil Bansal , David Gamarnik, Handling load with less stress, Queueing Systems: Theory and Applications, v.54 n.1, p.45-54, September 2006 [doi>10.1007/s11134-006-8218-z]
• 6: 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
• 7: Sem Borst , Rudesindo Núñez-Queija , Bert Zwart, Sojourn time asymptotics in processor-sharing queues, Queueing Systems: Theory and Applications, v.53 n.1-2, p.31-51, June 2006 [doi>10.1007/s11134-006-7585-9]
• 8: S. C. Borst , O. J. Boxma , R. Núñez-Queija , A. P. Zwart, The impact of the service discipline on delay asymptotics, Performance Evaluation, v.54 n.2, p.175-206, 1 October 2003 [doi>10.1016/S0166-5316(03)00071-3]
• 9: Bogdan Caprita , Jason Nieh , Clifford Stein, Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146396]
• 10: H. Feng, V. Misra, and D. Rubenstein. PBS: A unified priority-based CPU scheduler. Technical Report, Computer Science Department, Columbia University, 2006.
• 11: 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]
• 12: P. R. Jelenkovíc, X. Kang, and J. Tan. Adaptive and scalable comparison scheduling. Extended version. Technical Report, Department of Electrical Engineering, Columbia University, March 2007. http://www.ee.columbia.edu/~predrag/pub list.html.
• 13: P. R. Jelenkovíc, X. Kang, and J. Tan. Heavy-tailed limits for medium size jobs and comparison scheduling. Technical Report, No. EE2007-01-24, Department of Electrical Engineering, Columbia University, January 2007, submitted for publication.
• 14: P. R. Jelenkovíc and A. A. Lazar. Subexponential asymptotics of a Markov-modulated random walk with queueing applications. J. Appl. Probab., 35(2):325--347, June 1998.
• 15: P. R. Jelenkovíc and P. Momčilovíc. Capacity regions for network multiplexers with heavy-tailed fluid on-off sources. In Proc. IEEE Infocom, Anchorage, AK, April 2001.
• 16: P. Jelenkovic , P. Momcilovic, Large Deviation Analysis of Subexponential Waiting Times in a Processor-Sharing Queue, Mathematics of Operations Research, v.28 n.3, p.587-608, July 2003 [doi>10.1287/moor.28.3.587.16396]
• 17: L. Kleinrock. Queueing Systems, vol. II. John Wiley and Sons, 1976.
• 18: R. M. Loynes. The stability of a queue with non-independent inter-arrival and service times. Proc. Cambridge Philos. Soc., 58:497--520, 1962.
• 19: M. Nuyens and A. Wierman. The foreground-background queue: a survey. Oct 2006, preprint.
• 20: Misja Nuyens , Bert Zwart, A large-deviations analysis of the GI/GI/1 SRPT queue, Queueing Systems: Theory and Applications, v.54 n.2, p.85-97, October 2006 [doi>10.1007/s11134-006-8767-1]
• 21: A. Pakes. On the tails of waiting-time distributions. J. Appl. Probab., 12:555--564, 1975.
• 22: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 23: I. A. Rai, E. W. Biersack, and G. Urvoy-Keller. Size-based scheduling to improve the performance of short TCP flows. IEEE Network, pages 12--17, January/February 2005.
• 24: 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
• 25: K. Ramanan and A. L. Stolyar. Largest weighted delay first scheduling: Large deviations and optimality. Annals of Applied Probability, 11(1):1--48, Feb 2001.
• 26: 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
• 27: L. E. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16(3):687--690, 1968.
• 28: L. E. Schrage and L. W. Miller. The queue M/G/1 with the shortest remaining processing time discipline. Operations Research, 14:670--684, 1966.
• 29: M. Squillante, D. Yao, and L. Zhang. Web traffic modeling and web server performance analysis. In Proc. IEEE 38th Conf., Decision and Control, pages 4432--4437, Phoenix, AZ, 1999.
• 30: 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
• 31: 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
• 32: R. W. Wolff. Stochastic Modeling and Theory of Queues. Prentice Hall, 1989.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Performance, Theory

Keywords:
M/G/1, adaptive thresholds, comparison scheduling, scalability