Random task scheduling scheme based on reinforcement learning in cloud computing

详细信息    查看全文

• 作者：Zhiping Peng ; Delong Cui ; Jinglong Zuo ; Qirui Li ; Bo Xu ; Weiwei Lin
• 关键词：Task scheduling ; Cloud computing ; Queuing theory ; Reinforcement learning ; State aggregation
• 刊名：Cluster Computing
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：18
• 期：4
• 页码：1595-1607
• 全文大小：1,115 KB
• 参考文献：1.Vaquero, L., Rodero-Merino, L., Caceres, J., et al.: A break in the clouds: towards a cloud definition. ACM SIGCOMM Comput. Commun. Rev. 39(1), 50鈥?5 (2009)CrossRef
  2.Zhou, M., Zhang, R., Zeng, D., et al.: Services in the cloud computing era: a survey. In: Proceeding of the Fourth International Universal Communication Symposium (FIUCS2010), pp. 40鈥?6 (2010)
  3.Buyya, R., Yeo, C., Venugopal, S.: Market-oriented cloud computing: vision, hype, and reality for delivering it services as computing utilities. In: Proceeding of the 10th IEEE International Conference on High Performance Computing and Communications (HPCC2008), pp. 5鈥?3 (2008)
  4.Delimitrou, C., Kozyrakis, C.: QoS-aware scheduling in heterogeneous datacenters with paragon. IEEE Micro 34(3), 17鈥?0 (2013)CrossRef
  5.Wang, W.J., Chang, Y.S., Lo, W.T., et al.: Adaptive scheduling for parallel tasks with QoS satisfaction for hybrid cloud environments. J. Supercomput. 66(2), 783鈥?11 (2013)CrossRef
  6.Kusic, D., Kephart, J., Hanson, J., et al.: Power and performance management of virtualized computing environments via lookahead control. Clust. Comput. 12(1), 1鈥?5 (2009)CrossRef
  7.Karve, A., Kimbrel, T., Pacifici, G., et al.: Dynamic placement for clustered Web applications. In: Proceeding of the 15th International Conference on World Wide web (WWW2006), pp. 593鈥?04 (2006)
  8.Heath, T., Diniz, B., Carrera, E.V., et al.: Energy conservation in heterogeneous server clusters. In: Proceeding of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP2005), pp. 186鈥?95 (2005)
  9. http://鈥媋ws.鈥媋mazon.鈥媍om/鈥媏c2/鈥?/span>
  10. http://鈥媤ww.鈥媘icrosoft.鈥媍om/鈥媤indowsazure/鈥?/span>
  11.Yang, B., Tan, F., Dai, Y.S., et al.: Performance evaluation of cloud service considering fault recovery. In: Proceeding of the First International Conference on Cloud Computing (CloudCom 09), pp. 571鈥?76 (2009)
  12.Liu, X.D., Tong, W.Q., Zhi, X.L., et al.: Performance analysis of cloud computing services considering resources sharing among virtual machines. J. Supercomput. 69, 357鈥?74 (2014)CrossRef
  13.Khazaei, H., Misic, J., Misic, V.: Performance analysis of cloud computing centers using M/G/m/m+r.queuing systems. IEEE Trans. Parall. Distr. 23(5), 936鈥?43 (2012)CrossRef
  14.Khazaei, H., Misic, J., Misic, V.: Modeling of cloud computing centers using M/G/m queues. In: Proceeding of the 31st International Conference on Distributed Computing Systems Workshops (ICDCSW2011), pp. 87鈥?2 (2011)
  15.Khazaei, H., Misic, J., Misic, V.: Performance analysis of cloud centers under burst arrivals and total rejection policy. In: Proceeding of IEEE Global Telecommunications Conference (Globecom2011), pp. 1鈥? (2011)
  16.Rao, L., Liu, X., Xie, L., Liu, W.: Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment. In: Proceeding of IEEE INFOCOM, pp. 1鈥? (2010)
  17.Brenner, U.: A faster polynomial algorithm for the unbalanced Hitchcock transportation problem. Oper. Res. Lett. 36, 408鈥?13 (2008)
  18.Luo, J.Y., Rao, L., Liu, X.: Eco-IDC: trade delay for energy cost with service delay guarantee for internet data centers. In: Proceeding of IEEE International Conference Cluster Computing (CLUSTER2012), pp. 45鈥?3 (2012)
  19.Luo, J.Y., Rao, L., Liu, X.: Temporal load balancing with service delay guarantees for data center energy cost optimization. IEEE Trans. Parall. Distr. 25(3), 775鈥?84 (2014)CrossRef
  20.Yao, Y., Huang, L., Sharma, A. et al.: Data centers power reduction: a two time scale Approach for delay tolerant workloads. In: Proceeding of IEEE INFOCOM, pp. 1431鈥?439 (2012)
  21.Gao, Y.Q., Guan, H.B., Qi, Z.W., et al.: Service level agreement based energy-efficient resource management in cloud data centers. Comput. Electr. Eng. 40, 1621鈥?633 (2014)CrossRef
  22.Suresh, V., Ezhilchelvan, P., Watson, P.: Scalable and responsive event processing in the cloud. Phil. Trans. R. Soc. A 371(1983), 20120095 (2013)CrossRef
  23.Nan, X.M., He, Y.F., Guan, L.: Queueing model based resource optimization for multimedia cloud. J. Vis. Commun. Image Represent. 25, 928鈥?42 (2014)CrossRef
  24.Huynh, N., Tran, M., Nam, T.: Tool-driven strategies for resource provisioning of single-tier web applications in clouds. In: Proceeding of the 5th International Conference on Ubiquitous and Future Networks (ICUFN2013), pp. 795鈥?99 (2013)
  25.Tesauro, G., Jong, N., Das, R., et al.: A hybrid reinforcement learning approach to autonomic resource allocation. In: Proceedings of IEEE International Conference on Autonomic Computing (ICAC 鈥?6), pp. 65鈥?3 (2006)
  26.Xavier, D., Nicolas, R.: From data center resource allocation to control theory and back. In: Proceedings of the 3rd IEEE International Conference on Cloud Computing (CLOUD), pp. 410鈥?17 (2010)
  27.Julien, P., Cecile, G.R., Balazs, K., et al.: Multi-objective reinforcement learning for responsive grids. J. Grid Comput. 8, 473鈥?92 (2010)CrossRef
  28.Alexander, F., Matthias, H.: Improving scheduling performance using a Q-Learning-based leasing policy for clouds. In: Proceedings of 18th International Conference on Euro-par Parallel Processing (Euro-Par), pp. 337鈥?49 (2012)
  29.Bu, X.P., Rao, J., Xu, C.Z.: A reinforcement learning approach to online web systems auto-configuration. In: Proceedings of the 29th IEEE International Conference on Distributed Computing Systems (ICDCS2009), pp. 2鈥?1 (2009)
  30.Khazaei, H., Misic, J., Misic, V., et al.: A fine-grained performance model of cloud computing centers. IEEE Trans. Parall. Distr. 24(11), 2138鈥?147 (2013)CrossRef
  31.Grimmett, G., Stirzaker, D.: Probability and random processes, 3rd edn. Oxford Univ Press, Oxford (2010)
  32.Gross, D.: Fundamentals of queueing theory. Wiley-India Press, New Jersey (2008)CrossRef
  33.Sutton, R., Barto, A.: Reinforcement learning: an introduction. MIT Press, Cambridge (1998)
  34.Wiering, M., Otterlo, M.: Reinforcement learning: state-of-the-art. Springer, New York (2012)CrossRef
  35.Tang, H., Pei, R., Zhou, L., et al.: Coordinate control of multiple CSPS system based on state aggregation method. Acta Autom. Sin. 40(5), 901鈥?08 (2014). (in Chinese)MathSciNet
  36. http://鈥媤ww.鈥媘athworks.鈥媍n/鈥?/span>
  37.Calheiros, R.N., Ranjan, R., Beloglazov, A., De Rose, C.A.F., Buyya, R.: CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource pro visioning algorithms. Softw. Pract. Exp. 41(1), 23鈥?0 (2011)
  38.Isard, M., Budiu, M., Yu, Y., et al.: Distributed data-parallel programs from sequential building blocks. In: Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems(EuroSys2007), pp. 59鈥?2 (2007)
  39. http://鈥媓adoop.鈥媋pache.鈥媜rg/鈥媍ommon/鈥媎ocs/鈥媍urrent.鈥?鈥媍apacity_鈥媠heduler.鈥媓tml [EB/OL]
  40.Dong, Z.Q., Ning, L., Roberto, R.C., et al.: Greedy scheduling of tasks with time constraints for energy-efficient cloud-computing data centers. J. Cloud Comput. Adv. Syst. Appl. 4, 1鈥?4 (2015)CrossRef
  41.Kaur, S., Verma, A.: An efficient approach to genetic algorithm for job scheduling in cloud computing environment. Int. J. Info. Technol. Comput. Sci. 4(10), 74鈥?9 (2012)
  
• 作者单位：Zhiping Peng (1)
  Delong Cui (1)
  Jinglong Zuo (1)
  Qirui Li (1)
  Bo Xu (1)
  Weiwei Lin (2)
  
  1. College of Computer and Electronic Information, Guangdong University of Petrochemical Technology, Maoming, China
  2. School of Computer Science and Engineering, South China University of Technology, Guangzhou, China
  
• 刊物类别：Computer Science
• 刊物主题：Processor Architectures
  Operating Systems
  Computer Communication Networks
  
• 出版者：Springer Netherlands
• ISSN：1573-7543

文摘

Task scheduling is a necessary prerequisite for performance optimization and resource management in the cloud computing system. Focusing on accurate scaled cloud computing environment and efficient task scheduling under resource constraints problems, we introduce fine-grained cloud computing system model and optimization task scheduling scheme in this paper. The system model is comprised of clearly defined separate submodels including task schedule submodel, task execute submodel and task transmission submodel, so that they can be accurately analyzed in the order of processing of user requests. Moreover the submodels are scalable enough to capture the flexibility of the cloud computing paradigm. By analyzing the submodels, where results are repeated to obtain sufficient accuracy, we design a novel task scheduling scheme based on reinforcement learning and queuing theory to optimize task scheduling under the resource constraints, and the state aggregation technologies is employed to accelerate the learning progress. Our results, on the one hand, demonstrate the efficiency of the task scheduling scheme and, on the other hand, reveal the relationship between the arrival rate, server rate, number of VMs and the number of buffer size. Keywords Task scheduling Cloud computing Queuing theory Reinforcement learning State aggregation