Analysis of LAS scheduling for job size distributions with high variance

ABSTRACT

Recent studies of Internet traffic have shown that flow size distributions often exhibit a high variability property in the sense that most of the flows are short and more than half of the total load is constituted by a small percentage of the largest flows. In the light of this observation, it is interesting to revisit scheduling policies that are known to favor small jobs in order to quantify the benefit for small and the penalty for large jobs. Among all scheduling policies that do not require knowledge of job size, the least attained service (LAS) scheduling policy is known to favor small jobs the most. We investigate the M/G/1/LAS queue for both, load ? < 1 and ? = 1. Our analysis shows that for job size distributions with a high variability property, LAS favors short jobs with a negligible penalty to the few largest jobs, and that LAS achieves a mean response time over all jobs that is close to the mean response time achieved by SRPT.Finally, we implement LAS in the ns-2 network simulator to study its performance benefits for TCP flows. When LAS is used to schedule packets over the bottleneck link, more than 99% of the shortest flows experience smaller mean response times under LAS than under FIFO and only the largest jobs observe a negligible increase in response time. The benefit of using LAS as compared to FIFO is most pronounced at high load.

REFERENCES

• 1: Virgílio Almeida , Azer Bestavros , Mark Crovella , Adriana de Oliveira, Characterizing reference locality in the WWW, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.92-107, December 18-20, 1996, Miami Beach, Florida, United States
• 2: 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
• 3: Xuan Chen , John Heidemann, Preferential treatment for short flows to reduce web latency, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.6, p.779-794, 22 April 2003 [doi>10.1016/S1389-1286(02)00439-5]
• 4: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 5: R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of Scheduling, Addison-Wesley Publishing Company, 1967.
• 6: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 7: M. Crovella, R. Frangioso, and M. Harchol-Balter, "Connection Scheduling in Web Servers", In USENIX Symposium on Internet Technologies and Systems (USITS '99), pp. 243--254, Boulder, Colorodo, October 1999.
• 8: Mark Crovella, Performance Evaluation with Heavy Tailed Distributions, Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, p.1-10, June 16, 2001
• 9: Anja Feldmann , Anna C. Gilbert , Polly Huang , Walter Willinger, Dynamics of IP traffic: a study of the role of variability and the impact of control, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.301-313, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 10: M. J. Fischer, D. Gross, D. M. B. Masi, and J. F. Shortle, "Analyzing the Waiting Time Process in Internet Queueing Systems With the Transform Approximation Method", The Telecommunications Review, pp. 21--32, 2001.
• 11: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 12: W. Gong, Y. Liu, V. Misra, and D. Towsley, "On the Tails of Web File Size Distributions", In Proc. of 39-th Allerton Conference on Communication, Control, and Computing, October 2001.
• 13: 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.
• 14: 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]
• 15: Mor Harchol-Balter , Karl Sigman , Adam Wierman, Asymptotic convergence of scheduling policies with respect to slowdown, Performance Evaluation, v.49 n.1-4, p.241-256, September 2002 [doi>10.1016/S0166-5316(02)00132-3]
• 16: http://www.isi.edu/nsnam/ns/, "The Network Simulator ns2",
• 17: L. Kleinrock, Queuing Systems, Volume II: Computer Applications, Wiley, New York, 1976.
• 18: H. Krayl, E. J. Neuhold, and C. Unger, Grundlagen der Betriebssysteme, Walter de Gruyter, Berlin, New York, 1975.
• 19: D. S. Mitrinovic, Analytic Inequalities, Springer-Verlag, 1970.
• 20: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 21: 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]
• 22: R. Schassberger, "A Detailed Steady State Analysis of the M/G/1 Queue under various Time Sharing Disciplines", In P. J. C. In O.J. Boxma G. Iazeolla, editor, Computer Performance and Reliability, pp. 431--442, North Holland, 1987.
• 23: R. Schassberger, "The Steady State Distribution of Spent Service Times Present in the M/G/1 Foreground-Background Processor-sharing Queue", Journal of Applied Probability, 25(7):194--203, 1988.
• 24: L. E. Schrage, "The queue M/G/1 with feedback to lower priority queues", Management Science, 13(7):466--474, 1967.
• 25: L. E. Schrage, "A Proof of the Optimality of the Shortest Remaining Service Time Discipline", Operations Research, 16:670--690, 1968.
• 26: L. E. Schrage and L. W. Miller, "The queue M/G/1 with the shortest processing remaining time discipline", Operations Research, 14:670--684, 1966.
• 27: F. Donelson Smith , Félix Hernández Campos , Kevin Jeffay , David Ott, What TCP/IP protocol headers can tell us about the web, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.245-256, June 2001, Cambridge, Massachusetts, United States
• 28: R. W. Wolff, "Time Sharing with Priorities", SIAM Journal of Applied Mathematics, 19(3):566--574, 1970.
• 29: S. Yang and G. Veciana, "Size-based Adaptive bandwidth Allocation: Optimizing the Average QoS for Elastic Flows", In Infocom 2002, 2002.

INDEX TERMS

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

General Terms:
Experimentation, Performance

Keywords:
high variability property, least attained service, size-based scheduling, web objects response time