跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.87) 您好!臺灣時間:2025/02/17 13:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:江依儒
研究生(外文):Yi-Ju Chiang
論文名稱:雲端系統任務調度機制與資源配置之研究
論文名稱(外文):Task Scheduling Mechanism and Resources Provisioning Management in Cloud Computing Systems
指導教授:歐陽彥杰許慶賢
指導教授(外文):Yen-Chieh OuyangChing-Hsien Hsu
口試委員:張建禕溫志煜楊晴雯馬代駿歐陽彥杰許慶賢
口試委員(外文):Chein-I ChangChih-Yu WenChing Wen YangDye-Jyun MaYen-Chieh OuyangChing-Hsien Hsu
口試日期:2017-06-29
學位類別:博士
校院名稱:國立中興大學
系所名稱:電機工程學系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:90
中文關鍵詞:排隊理論系統阻擋率省電策略任務調度
外文關鍵詞:Queuing theorysystem blocking probabilitypower-saving policiestask scheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:361
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著雲端服務平台的日益普及,在服務系統中如何進行資源配置與任務調度來維持服務水平是服務供應商面臨的主要挑戰之一。在論文中針對雲端系統資源配置、省電運作模式與任務調度機制進行了探討與分析。首先在系統阻擋率與任務響應時間的性能約束下,研究與設計有效地資源配置與省電機制來穩定服務水平與降低系統耗能。在論文中,我們根據不同的系統容量、資源配置與使用者行為來建立不同的分析模型,並利用排隊理論,分析系統容量對任務丟失率與系統性能的影響。在不同系統根據所需考慮的運作成本、系統耗能與性能要求,分別設置不同的目標函數與性能約束條件。在不同的省電機制下研究對於響應時間、運作狀態與運作成本的影響。我們所提出的演算法與三種省電運作模式能有效地進行資源配置、降低伺服器在閒置狀態下的耗能成本,並能在性能約束條件下求最佳解。
接著進一步探討當系統處在高負載的狀態時,如何在負載的限制下進行最佳的任務調度。在雲端服務系統中,開發任務調度機制的主要目標是降低任務的響應時間,讓任務能在處理期限內完成,同時進行壅塞控制,避免系統過載。最後我們所設計的方法和其他方法進行模擬比較,證明能夠改善系統性能與利潤。
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.
Abstract.........ii
Contents.........iii
List of Figures........v
List of Tables.........vii
Chapter 1 Introduction.....1
1.1 Background and Motivation.....1
1.2 Literature Review...5
1.2.1 Analysis of Capacity Provisioning.5.
1.2.2 Workload Control ........................7
Chapter 2 Cloud Service Models.........10
2.1 Service System with Different Buffer Sizes....10
2.1.1 A Multi-Servers System with Blocking Control..10
2.1.2 Performance Evaluation......13
2.1.3 Resources Provisioning Scheme....16
2.2 Performance Analysis............21
2.2.1 Experimental Results..........21
2.2.2 Comparison of Results.........25
2.3 Energy-Efficiency Controls......29
2.3.1 Related Works.....29
2.3.2 ISN Policy.....33
2.3.3 SN and SI Policies.....35
2.3.4 Queuing Models....38
Chapter 3 Optimization Problem Formulation.....43
3.1 Operational Cost................43
3.2 Performance Comparisons and the ECG Algorithm..........................................46
Chapter 4 Numerical Validation.....54
4.1 Experiments Results......54
4.2 Comparison of Results.....58
Chapter 5 Task Scheduling.....62
5.1 Scheduling Approaches.....62
5.2 Load-Based Scheduling Approach.....69
5.3 Experimental Environment......72
Chapter 6 Conclusion.....80
6.1 Conclusion.....80
Reference......82
Publication List.....90
[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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top