Please use this identifier to cite or link to this item:
標題: 雲端系統任務調度機制與資源配置之研究
Task Scheduling Mechanism and Resources Provisioning Management in Cloud Computing Systems
作者: 江依儒
Yi-Ju Chiang
關鍵字: 排隊理論;系統阻擋率;省電策略;任務調度;Queuing theory;system blocking probability;power-saving policies;task scheduling
引用: [1] P. Mell, and T. Grance, 'The NIST definition of cloud computing,' Communications of the ACM, vol. 53, no. 6, pp. 50, 2010. [2] S. Marston, Z. Li, S. Bandyopadhyay, J. Zhang, and A. Ghalsasi, 'Cloud computing—The business perspective,' Decision support systems, vol. 51, no. 1, pp. 176-189, 2011. [3] L. Xu, and A. B. Cremers, “A Decentralized Pseudonym Scheme for Cloud-based eHealth Systems”, Proc. International Conference on Health Informatics, pp. 230-237, 2014. [4] M. Xu, L. Cui, H. Wang and Y. Bi, 'A multiple QoS constrained scheduling strategy of multiple workflows for cloud computing,' In 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications, pp. 629-634, 2009. [5] K. Wang, N. Li, and Z. Jiang, “Queueing system with impatient customers: A review,” in Proc. IEEE Int. Conf. Serv. Operations Logistics Inform., pp. 82–87, 2010. [6] J. Li, T. Dai, J. Huo, and Q. Su, “A method of service quality monitoring in contact centers with impatient customers,” in Proc. 9th Int. Conf. Service Syst. Service Manage., pp. 114–117, 2012. [7] C. J. Ancker Jr, and A. V. Gafarian. 'Some queuing problems with balking and reneging. I.' Operations Research, vol. 11, no. 1, pp. 88-100, 1963. [8] K. H. Wang, and Y. C. Chang, 'Cost analysis of a finite M/M/R queueing system with balking, reneging, and server breakdowns, ' Mathematical Methods of Operations Research, vol. 56, no. 2, pp. 169-180, 2002. [9] M. E. Crovella, M. S. Taqqu, and A. Bestavros, 'Heavy-tailed probability distributions in the World Wide Web,' A practical guide to heavy tails, 1, pp. 3-26, 1998. [10] I. Taboada, J. O. Fajardo, F. Liberal, and B. Blanco, 'Size-based and channel-aware scheduling algorithm proposal for mean delay optimization in wireless networks,' In Communications (ICC), 2012 IEEE International Conference on, pp. 6596-6600, 2012. [11] D. G. Feitelson, 'Workload modeling for performance evaluation,' In Performance Evaluation of Complex Systems: Techniques and Tool. Springer Berlin Heidelberg, pp. 114-141 2002. [12] B. Fu, J. Broberg, and Z. Tari, 'Task assignment strategy for overloaded systems,' IEEE International Symposium on Computers and Communication, pp. 1119-1125, 2003. [13] A. Nahir, A. Orda,and D. Raz, 'Distributed oblivious load balancing using prioritized job replication,' Proceedings of the 8th International Conference on Network and Service Management, pp. 55-63, 2012. [14] H. Khazaei, J. Mišić, and V. B. Mišić, 'Performance analysis of cloud centers under burst arrivals and total rejection policy,' IEEE Global Telecommunications Conference (GLOBECOM 2011), pp. 1-6, 2011. [15] R. Hwang, C. Lee, Y. Chen, and D. Zhang-Jian, 'Cost Optimization of Elasticity Cloud Resource Subscription Policy,' IEEE Trans. on service computing, vol. 7, no. 4, pp. 561-574, 2013. [16] D. Bruneo, 'A stochastic model to investigate data center performance and qos in iaas cloud computing systems,' IEEE Trans. on Parallel and Distributed Systems, vol. 25, pp. 560-569, 2014. [17] N. Samaan, 'A Novel Economic Sharing Model in a Federation of Selfish Cloud Providers,' IEEE Trans. on Parallel and Distributed Systems, vol. 25, pp. 12- 21, 2014. [18] D. Doran, L. Lipsky and S. Thompson, “Cost-based Optimization of Buffer Size in M/G/1/N Systems Under Different Service-time Distributions,” Proceedings of 9th IEEE Network Computing and Applications (NCA), pp. 28-35, 2010. [19] H. Khazaei, J. Misic, and V. B. Misic, “Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems,” IEEE Transactions on Parallel and Distributed Systems, vol 23, no.5 pp. 936-943, 2012. [20] Y. C. Lee, C. Wang, A. Y. Zomaya, and B. B. Zhou, “Profit-driven scheduling for cloud services with data access awareness,” Journal of Parallel and Distributed Computing, vol. 72, no. 4, pp.591-601, 2012. [21] B. Yang, F. Tan, Y. Dai, and S. Guo, “Performance Evaluation of Cloud Service Considering Fault Recovery,” Proc. First Int’l Conf. Cloud Computing (CloudCom ’09), pp.571-576, 2009. [22] H. Khazaei, J. Mišić, and V. B. Mišić, 'Performance analysis of cloud centers under burst arrivals and total rejection policy,' In Global Telecommunications Conference (GLOBECOM 2011), IEEE, pp. 1-6, 2011. [23] R. Ghosh, F. Longo,V. K. Naik, and K. S. Trivedi, 'Quantifying resiliency of iaas cloud,' 29th IEEE Symposium on Reliable Distributed Systems, pp. 343-347, 2010. [24] R. N. Calheiros, R. Ranjan, and R. Buyya, 'Virtual machine provisioning based on analytical performance and QoS in cloud computing environments,' 2011 International Conference on Parallel Processing (ICPP), pp. 295-304, 2011. [25] B. Song, M. M. Hassan, and E. N. Huh, ' A novel heuristic-based task selection and allocation framework in dynamic collaborative cloud service platform,' In Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference on, pp. 360-367, 2010. [26] T. R. V. Anandharajan, and M. A. Bhagyaveni, 'Co-operative scheduled energy aware load-balancing technique for an efficient computational cloud,' International Journal of Computer Science, (8), pp. 571-576, 2011. [27] S. Shen, K. Deng, A. Iosup, and D. Epema, 'Scheduling jobs in the cloud using on-demand and reserved instances,' In Euro-Par 2013 Parallel Processing, Springer Berlin Heidelberg, pp. 242-254, 2013. [28] D. Gross, J. F. Shortle, J. M. Thompson, and C. M. Harris, “Fundamentals of Queuing Theory, 4th Edition,” New York, USA: Wiley, 2008. [29] J. Cao, L. Yang, X. Zheng, B. Liu, L. Zhao, X. Ni, F. Dong, and B. Mao, “Social attribute based web service information publication mechanism in delay tolerant network,” IEEE 14th International Conference on Computational Science and Engineering (CSE), pp. 435–442, 2011. [30] M. Armony and C. Maglaras, “Contact centers with a call-back option and real-time delay information,” Operations Research, vol. 52, no. 4, pp. 527–545, 2004. [31] R. L. Grossman, “The case for cloud computing,” IT professional, vol. 11, no. 2, pp. 23-27, 2009. [32] Q. Zhang, L. Cheng, and R. Boutaba, 'Cloud computing: state-of-the-art and research challenges,' Journal of internet services and applications, vol. 1, no. 1, pp. 7-18, 2010. [33] J. Shao and Q. Wang, “A performance guarantee approach for cloud applications based on monitoring,” In Computer Software and Applications Conference Workshops (COMPSACW), IEEE 35th Annual, pp. 25–30, 2011. [34] R. Nathuji, A. Kansal, and A. Ghaffarkhah, “Q-clouds: Managing performance interference effects for qos-aware clouds,” In Proceedings of the 5th European conference on Computer systems, pp. 237–250, 2010. [35] R. N. Calheiros, R. Ranjan, and, R. Buyya, “Virtual machine provisioning based on analytical performance and QoS in cloud computing environments,” 2011 international conference on Parallel processing (ICPP), pp. 295–304, 2011. [36] M. Yadin, and P. Naor, “Queueing systems with a removable service station,” Operations research, pp. 393-405, 1963. [37] W. Huang, X. Li and Z. Qian, “An Energy Efficient Virtual Machine Placement Algorithm with Balanced Resource Utilization,” Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS), pp. 313-319, 2013. [38] R. Nathuji, K. Schwan, A. Somani, and Y. Joshi, “VPM tokens: virtual machine-aware power budgeting in datacenters,” Cluster computing, vol. 12, no. 2, pp.189-203, 2009. [39] J. S. Yang, P. Liu, and J. J. Wu, “Workload characteristics-aware virtual machine consolidation algorithms,” IEEE 4th International Conference on Cloud Computing Technology and Science (CloudCom), pp. 42-49, 2012. [40] K. Ye, D. Huang, X. Jiang, H. Chen, and S. Wu, “Virtual machine based energy-efficient data center architecture for cloud computing: a performance perspective,” IEEE/ACM Int''l Conference on Green Computing and Communications & Int''l Conference on Cyber, Physical and Social Computing, pp.171-178, 2010. [41] G. P. Duggan and P. M. Young, “A Resource Allocation Model for Energy Management Systems,” IEEE International Systems Conference (SysCon), pp. 1-3, 2012. [42] M. Mazzucco, D. Dyachuky, and R. Detersy, “Maximizing Cloud Providers Revenues via Energy Aware Allocation Policies,” IEEE 3rd International Conference on Cloud Computing (CLOUD), pp. 131-138, 2010. [43] Q. Zhang, M. Zhani, R. Boutaba, and J. Hellerstein, “Dynamic Heterogeneity-Aware Resource Provisioning in the Cloud,” IEEE Transactions on Cloud Computing, vol. 2, no.1, pp.14-28, 2014. [44] M. Guazzone, C. Anglano and M. Canonico, “Energy-Efficient Resource Management for Cloud Computing Infrastructures,” IEEE International Conference on Cloud Computing Technology and Science (CloudCom), pp. 424-431, 2011. [45] A. Amokrane, M. Zhani, R. Langar, R. Boutaba, and G. Pujolle, “Greenhead: Virtual Data Center Embedding across Distributed Infrastructures,” IEEE Transactions on Cloud Computing, vol. 1, no.1, pp. 36-49, 2013. [46] F. Larumbe, and B. Sanso, “A Tabu Search Algorithm for the Location of Data Centers and Software Components in Green Cloud Computing Networks,” IEEE Transactions on Cloud Computing, vol. 1, no. 1, pp. 22-35, 2013. [47] Y. Deng, W. J. Braun, and Y. Q. Zhao, “M/M/1 queueing system with delayed controlled vacation,” OR Transactions, vol. 3, pp. 17-30, 1999. [48] K. H. Wang and H. M. Huang, “Optimal control of an M/Ek/1 queueing system with a removable service station,” Journal of the operational research society,” vol. 46, pp.1014 -1022, 1995. [49] Y. Levy and U. Yechiali, “Utilization of Idle Time in an M/G/1 Queueing System,” Management Science, vol. 22, no2, pp. 202-211, 1975. [50] T. Naishuo, Z. Daqing, C. Chengxuan, “M/G/1 queue with controllable vacations and optimization of vacation policy,” Acta Mathematicae Applicatae Sinica, vol. 7, no. 4, pp. 363-373, 1991. [51] D. A. Wu, and H. Takagi, “M/G/1 queue with multiple working vacations,” Performance Evaluation, vol. 63, no. 7, pp. 654-681, 2006. [52] M. Zhang, and Z. Hou, “M/G/1 queue with single working vacation,” Journal of Applied Mathematics and Computing, vol. 39, no. 1-2, pp. 221-234, 2012. [53] D. Meisner, B. T. Gold and T. F. Wenisch, “PowerNap: Eliminating Server Idle Power,” In proceedings of the 14th international conference on Architectural support for programming languages and operating systems, pp. 205-216, 2009. [54] H. Mi, H. Wang, G. Yin, Y. Zhou, D. Shi, and L. Yuan, “Online Self-reconfiguration with Performance Guarantee for Energy-efficient Large-scale Cloud Computing Data Centers,” IEEE International Conference on Services Computing, pp. 514-521, 2010. [55] H. Abdelsalam, K. Maly, R. Mukkamala, M. Zubair, and D. Kaminsky, “Towards Energy Efficient Change Management in a Cloud Computing Environment,” Springer Berlin Heidelberg Scalability of Networks and Services, pp. 161-166, 2009. [56] J. Song, T. Li, Z. Wang, and Z. Zhu, “Study on energy-consumption regularities of cloud computing systems by a novel evaluation model,” Computing, vol. 95, no. 4, pp. 269-287, 2013. [57] R. Van den Bossche, K. Vanmechelen, and J. Broeckhove, “Cost-optimal scheduling in hybrid iaas clouds for deadline constrained workloads,” In 2010 IEEE 3rd International Conference on Cloud Computing, pp. 228-235, 2010. [58] M. Miyama, and S. Kumano, 'Numerical solution of Q 2 evolution equations in a brute-force method,' Computer Physics Communications, vol. 94, no. 2, pp. 185-215, 1996. [59] R. M. Haralick, and G. L. Elliott, 'Increasing tree search efficiency for constraint satisfaction problems,' Artificial intelligence, vol. 14, no. 3, pp. 263-313, 1980. [60] P. Somol, P. Pudil, and J. Kittler, “Fast branch & bound algorithms for optimal feature selection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 7, pp. 900-912, 2004. [61] D. P. Bertsekas, and D. P. Bertsekas, 'Dynamic programming and optimal control,' Belmont, MA: Athena Scientific, 1995. [62] D. El Baz, and M. Elkihel, 'Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0–1 knapsack problem,' Journal of Parallel and Distributed Computing, vol. 65, no. 1, pp. 74-84, 2005. [63] B. Doytchinov, J. Lehoczky, and S. Shreve, 'Real-time queues in heavy traffic with earliest-deadline-first queue discipline, ' Annals of Applied Probability, pp. 332-378, 2001. [64] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, ' CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,' Software: Practice and Experience, vol. 41, no. 1, pp. 23-50, 2011.

As cloud computing become more and more popular, how to manage resource provisioning and schedule tasks are several critical challenges for cloud providers. To analyze these issues, resources provisioning, power-saving policies and task scheduling in cloud computing are studied and analyzed in this research.
First of all, we try to design an effectively resources provisioning mechanism and power-saving policies according to system blocking probability and response time constraints, so as to meet performance guarantees and reduce power consumption. Different models are designed according to various system capacities, resources provisioning and user behaviors. The relationship between system capacity and task loss rates is analyzed based on different queuing models and system performance. According to incurred cost, power consumption and system performance, different objective functions with performance guarantees are proposed. The effect of energy-efficiency controls on response times, operating modes and incurred cost are demonstrated. Three power-saving policies are proposed to reduce idle power consumption, manage resources provisioning and solve the optimal solutions under a performance constraint.
Furthermore, how to develop an optimal task scheduling approach when the system is under heavy load is studied. The main purpose is to reduce response time, so as to make tasks complete within their deadline constraints. Simulation results show that the proposed approach outperforms other approaches in terms of system performance and profit.
Rights: 不同意授權瀏覽/列印電子全文服務
Appears in Collections:電機工程學系所

Files in This Item:
File SizeFormat Existing users please Login
nchu-106-8102064001-1.pdf1.86 MBAdobe PDFThis file is only available in the university internal network    Request a copy
Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.