Profitable services in an uncertain world

ABSTRACT

In a service-oriented, utility-computing, Grid-like world, service providers will execute jobs on behalf of their clients on systems rented from resource providers. This poses many challenges to the service provider, such as choosing which jobs to admit, when to run them, whether to execute them on one system or many, and how many resources to rent. To complicate matters, the service provider may experience resource uncertainty an inability to get the resources it needs or expects. The result will be sub-optimal choices of which jobs to accept and when to run them, and the service provider may have to pay penalties to its clients. Using an economics-based approach, we have developed scheduling policies that systematically address these problems. We show that the new policies deliver significantly more profit (or added value) than ones oblivious to such concerns.

REFERENCES

• 1: [Amdahl1967] Gene Amdahl. Validity of the single processor approach to achieving large-scale computing capabilities. Proceedings of AFIPS, volume 30, pages 483-5, 1967.
• 2: [Beckett2004] Jamie Beckett. HP Labs goes Hollywood: researchers help bring "Shrek 2" to life. HP Laboratories, Palo Alto, CA, April 2004. Web page.
• 3: Ken Chen , Paul Muhlethaler, A scheduling algorithm for tasks described by time value function, Real-Time Systems, v.10 n.3, p.293-312, May 1996 [doi>10.1007/BF00383389]
• 4: Su-Hui Chiang , Mary K. Vernon, Characteristics of a Large Shared Memory Production Workload, Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, p.159-187, June 16, 2001
• 5: Brent N. Chun , David E. Culler, User-Centric Performance Analysis of Market-Based Cluster Batch Schedulers, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.30, May 21-24, 2002
• 6: Franklin Reynolds, An Architectural Overview of Alpha: A Real-Time, Distributed Kernel, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.127-146, April 27-28, 1992
• 7: [He2004] L. He, S. A. Jarvis, D. P. Spooner, X. Chen, and G. R. Nudd. Dynamic, hybrid performance-oriented scheduling of moldable jobs with QoS demands in multiclusters and grids. 3rd International Conference on Grid and Cooperative Computing (GCC 2004) (Wuhan, China), October 2004.
• 8: David E. Irwin , Laura E. Grit , Jeffrey S. Chase, Balancing Risk and Reward in a Market-Based Task Service, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing, p.160-169, June 04-06, 2004 [doi>10.1109/HPDC.2004.5]
• 9: Leonard Kleinrock , Jau-Hsiung Huang, On Parallel Processing Systems: Amdahl's Law Generalized and Some Results on Optimal Design, IEEE Transactions on Software Engineering, v.18 n.5, p.434-447, May 1992 [doi>10.1109/32.135776]
• 10: Chen Lee , John Lehoczky , Dan Siewiorek , Ragunathan Rajkumar , Jeff Hansen, A Scalable Solution to the Multi-Resource QoS Problem, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.315, December 01-03, 1999
• 11: David Petrou , Gregory R. Ganger , Garth A. Gibson, Cluster scheduling for explicitly-speculative tasks, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006256]
• 12: Jerry Rolia , Xiaoyun Zhu , Martin Arlitt , Artur Andrzejak, Statistical service assurances for applications in utility grid environments, Performance Evaluation, v.58 n.2+3, p.319-339, November 2004 [doi>10.1016/j.peva.2004.07.015]
• 13: [Segall2002] M. D. Segall, Philip J. D. Lindan, M. J. Probert, C. J. Pickard, P. J. Hasnip, S. J. Clark, and M. C. Payne. First-principles simulation:ideas, illustrations and the CASTEP code. Journal Physics: Condensed Matter 14(11):2717-44, 2002.
• 14: Jahanzeb Sherwani , Nosheen Ali , Nausheen Lotia , Zahra Hayat , Rajkumar Buyya, Libra: a computational economy-based job scheduling system for clusters, Software—Practice & Experience, v.34 n.6, p.573-590, May 2004 [doi>10.1002/spe.581]
• 15: [Squillante1999] M. S. Squillante, D. D. Yao, and L. Zhang. Analysis of job arrival patterns and parallel scheduling performance. Performance Evaluation, 36-7:137-63, August 1999.
• 16: [Sun2004] Jiong Sun and Norman M. Sadeh. Coordinating multi-attribute procurement auctions subject to finite capacity considerations. Technical report CMU-CS-03-184 and CMU-ISRI-03-105. Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA, April 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

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

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Design, Experimentation, Measurement, Performance