Scheduling Problems For Cloud Computing

Abstract. Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. From the theoretical aspect, we mainly accomplish three research issues. Firstly, we solve the resource allocation problem in the user-level of cloud scheduling. We propose game theoretical algorithms for user bidding and auctioneer pricing.With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we address the task scheduling problem in the system-level of cloud scheduling. We prove a new utilization bound to settle on-line schedulability test considering the sequential feature of MapReduce. We deduce the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classical bound which is most used in industry.

Keywords:

Cloud computing, Scheduling problems, Cloud evolution Cloud service, Cloud characteristics,

PDF

___

M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia. A view of cloud computing. Communications of the ACM, 53(4):50–58, 2010.
Foster, Y. Zhao, I. Raicu, and S. Lu. Cloud computing and grid computing 360-degree compared. In Proceedings of Grid Computing Environments Workshop, pages 1–10, 2008.
D. M. S. Daryl C. Plummer, David W. Cearley. Cloud computing confusion leads to opportunity. Technical report, Gartner Research, 2008.
P. Mell and T. Grance. The NIST Definition of Cloud Computing (Draft). National Institute of Standards and Technology, 53:7, 2010.
M. Armbrust, A. Fox, and R. Griffith. Above the clouds: A berkeley view of cloud computing. Technical Report UCB/EECS-2009-28, EECS Department, University of California, Berkeley, Feb 2009.
J. Blazewicz. Scheduling in Computer and Manufacturing Systems. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1996.
M. Sipser. Introduction to the Theory of Computation. International Thomson Publishing, 1st edition, 1996.
R. Buyya, D. Abramson, J. Giddy, and H. Stockinger. Economic models for resource management and scheduling in grid computing. Concurrency and Computation: Practice and Experience, 14:1507–1542, 2002.
Y. Sun, S. Tilak, R. K. Thulasiram, and K. Chiu. Markets, Mechanisms, Games, and Their Implications in Grids, chapter 2, pages 29–48. John Wiley & Sons, Inc., 2009.
Y. kwong Kwok, S. Song, and K. Hwang. Selfish grid computing: Game-theoretic modeling and nash performance results. In Proceedings of International Symposium on Cluster Computing and the Grid, pages 9-12, 2005.
R. Buyya, C. Yeoa, S. Venugopala, J. Broberg, and I. Brandic. Cloud computing and emerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility. Future Generation Computer Systems, 25(6):599-616, 2009.
Cluster-on-demand. http://www.cs.duke.edu/nicl/cod/.
Mosix. http://www.mosix.cs.huji.ac.il/.
Stanford peers. http://infolab.stanford.edu/peers/.
D’agents. http://agent.cs.dartmouth.edu/.
D. Abramson, R. Buyya, and J. Giddy. A computational economy for grid computing and its implementation in the nimrod-g resource broker. Future Generation Computer Systems, 18(8):1061–1074, 2002.
L. V. Kale, S. Kumar, M. Potnuru, J. DeSouza, and S. Bandhakavi. Faucets: Efficient resource allocation on the computational grid. In Proceedings of the 2004 International Conference on Parallel Processing, pages 396–405. IEEE Computer Society, 2004.
Dailianas, Y. Yemini, D. Florissi, and H. Huang. Marketnet: Market-based protection of network systems and services - an application to snmp protection. In Proceedings of 19th IEEE International Conference on Computer Communications, pages 1391–1400, 2000.
R. Buyya, S. Pandey, and C. Vecchiola. Cloudbus toolkit for market-oriented cloud computing. In Proceedings of the 1st International Conference on Cloud Computing, pages 24-44. Springer- Verlag, 2009.
S. Venugopal, J. Broberg, and R. Buyya. Openpex: An open provisioning and execution system for virtual machines. Technical Report CLOUDS-TR-2009-8, CLOUDS Laboratory, The University of Melbourne, Australia,, 2009.
E. Elmroth and J. Tordsson. A grid resource broker supporting advance reservations and benchmark-based resource selection. In Lecture Notes in Computer Science, pages 1061– 1070. Springer-Verlag, 2005.
M. M. Shoukat, M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing, 59:107–131, 1999.
D. Borthakur. The Hadoop Distributed File System: Architecture and Design. The Apache Software Foundation, 2007.
M. Zaharia, A. Konwinski, A. D. Joseph, R. H. Katz, and I. Stoica. Improving mapreduce performance in heterogeneous environments. In R. Draves and R. van Renesse, editors, Proceedings of Symposium on Operating Systems Design and Implementation, pages 29– 42. USENIX Association, 2008.
M. Zaharia, D. Borthakur, J. Sen Sarma, K. Elmeleegy, S. Shenker, and I. Stoica. Job scheduling for multi-user mapreduce clusters. Technical Report UCB/EECS-2009-55, EECS Department, University of California, Berkeley, Apr 2009.
M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, and I. Stoica. Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling. In Proceedings of International Conference on EuroSys, pages 265–278, 2010.
Dryad. http://research.microsoft.com/en-us/projects/dryad/.
M. Isard, V. Prabhakaran, J. Currey, U.Wieder, K. Talwar, and A. Goldberg. Quincy: fair scheduling for distributed computing clusters. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles, pages 261–276. ACM, 2009.
Oracle grid engine. http://www.sun.com/software/sge/.
Maui cluster scheduler. http://www.cluster.com/maui-cluster-scheduler.php.
D. Thain, T. Tannenbaum, and M. Livny. Distributed computing in practice: the condor experience: Research articles. Journal of Concurrency: Practice and Experience, 17:323-356, February 2005.
C. Ragusa, F. Longo, and A. Puliafito. Experiencing with the cloud over glite. In Proceedings of ICSE Workshop on Software Engineering Challenges of Cloud Computing, pages 53–60. IEEE Computer Society, 2009.
C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real- time environment. Journal of the Association for Computing Machinery, 20(1):46–61, 1973.
L. Sha, T. Abdelzaher, K.-E. Arzen, A. Cervin, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, J. Lehoczky, and A. K. Mok. Real time scheduling theory: A historical perspective. Real-Time Systems, 28:101-155, November 2004.
J. P. Lehoczky, L. Sha, and Y. Ding. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of IEEE Real-Time Systems Symposium, pages 166–171, 1989.
P. K. Harter, Jr. Response times in level-structured systems. ACM Transaction on Computer Systems, 5:232–248, August 1987.
M. Joseph and P. K. Pandya. Finding response times in a real-time system. The Computer Journal, 29:390–395, 1986.
N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8:284-292, 1993.
J. Y. T. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2:237–250, 1982.
J. P. Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the 11th Real-Time Systems Symposium, pages 201–209, 1990.
S. R. Thuel and J. P. Lehoczky. Algorithms for scheduling hard aperiodic tasks in fixed- priority systems using slack stealing. In Proceedings of IEEE Real-Time Systems Symposium, pages 22–33, 1994.
N. C. Audsley, A. Burns, R. I. Davis, K. Tindell, and A. J. Wellings. Fixed priority pre- emptive scheduling: An historical perspective. Real-Time Systems, 8(2-3):173–198, 1995.
C. L. L. S. K. Dhall. On a real-time scheduling problem. Operations Research, 26(1):127– 140, 1978.
D.-I. Oh and T. P. Bakker. Utilization bounds for n-processor rate monotonescheduling with static processor assignment. Real-Time Systems, 15(2):183–192, 1998.
J. M. L´opez, J. L. D´ıaz, and D. F. Garc´ıa. Minimum and maximum utilization bounds for multiprocessor rate monotonic scheduling. IEEE Transactions Parallel Distributed Systems, 15(7):642–653, 2004.
B. Andersson, S. Baruah, and J. Jonsson. Static-priority scheduling on multiprocessors. In Proceedings of the 22nd IEEE Real-Time Systems Symposium, page 93. IEEE Computer Society, 2001.
S. K. Baruah and J. Goossens. Rate-monotonic scheduling on uniform multiprocessors. IEEE Transaction on Computers, 52:966–970, July 2003.
T. P. Baker. An analysis of edf schedulability on a multiprocessor. IEEE Transactions on Parallel and Distributed Systems, 16:760–768, 2005.
P. Uthaisombut. Generalization of edf and llf: Identifying all optimal online algorithms for minimizing maximum lateness. Algorithmica, 50:312–328, 2008.
T. D. Braun, H. J. Siegel, N. Beck, L. L. B¨ol¨oni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen, and R. F. Freund. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61:810–837, June 2001.
J. M. Hyman, J. M. Hyman, A. A. Lazar, A. A. Lazar, G. Pacifici, and G. Pacifici. Real-time scheduling with quality of service constraints. IEEE Journal on Selected Areas in Communications, 9:1052–1063, 1991.
H. Tokuda and C. W. Mercer. Arts: a distributed real-time kernel. SIGOPS Operating Systems Review, 23:29–53, July 1989.
S. Kato, R. Rajkumar, and Y. Ishikawa. A loadable real-time scheduler suite for multicore platform. Technical Report 12, Carnegie Mellon University, Department of Electrical and Computer Engineering, December, 2009.
R. Buyya, S. Pandey, and C. Vecchiola. Cloudbus toolkit for market-oriented cloud computing. In Proceedings of the 1st International Conference on Cloud Computing, pages 24–44. Springer- Verlag, 2009.