2020年 05期

Universal and Gradual-optimization Strategies for Resource Allocation in Infrastructure as a Service


摘要(Abstract):

为了提高各类资源利用率,在分析基础设施服务层计算、存储、网络资源共性的基础上,提出以高效解决0-1背包问题为靶向的通用逐步优化策略;设计时间复杂度分别为多项式级别的基于贪婪算法、进化算法、线性规划算法的通用逐步优化策略;通过理论分析及实验验证,得出基于3类优化算法的通用逐步优化策略的优缺点及适用范围。结果表明:贪婪算法能够满足时间方面的要求,进化算法能够满足时间、单个资源利用率和整体资源利用率3个方面的要求,线性规划算法能够满足单个资源利用率和整体资源利用率2个方面的要求。

关键词(KeyWords): 基础设施服务层;通用逐步优化策略;0-1背包问题;资源利用率

基金项目(Foundation): 国家自然科学基金项目(61563038);; 内蒙古自治区高等学校创新团队发展计划项目(NMGIRT-A1609);; 内蒙古自治区高等学校科学研究项目(NJZZ18117)

作者(Author): 邢海峰,高宽云,张增平

DOI: 10.13349/j.cnki.jdxbn.20200526.001

参考文献(References):

[1] MAHESWARAN M,ALI S,SIEGEL H J,et al.Dynamic mapping of a class of independent tasks onto heterogeneous computing systems[J].Journal of Parallel and Distributed Computing,1999,59(2):107-131.

[2] VENUGOPAL S,BUYYA R.A set coverage-based mapping heuristic for scheduling distributed data-intensive applications on global grids[C]//Proceedings of the 7th IEEE/ACM International Conference on Grid Computing,September 28-29,2006,Barcelona,Spain.Washington,D.C.:IEEE CS Press,2006:238-245.

[3] BUYYA R,YEO C S,VENUGOPAL S,et al.Cloud computing and emerging IT platforms:vision,hype,and reality for delivering computing as the 5th utility[J].Future Generation Computer Systems,2009,25(6):599-616.

[4] ASSUN??O M D,CALHEIROS R N,BIANCHI S,et al.Big data computing and clouds:trends and future directions[J].Journal of Parallel and Distributed Computing,2015,79/80:3-15.

[5] BUYYA R,SRIRAMA S N,CASALE G,et al.A manifesto for future generation cloud computing:research directions for the next decade[J].ACM Computing Surveys,2018,51(5):1-38.

[6] MADNI S H H,LATIFF M S A,COULIBALY Y,et al.Resource scheduling for infrastructure as a service (IaaS) in cloud computing[J].Journal of Network and Computer Applications,2016,68(6):173-200.

[7] MEI J,LI K L,LI K Q.Energy-aware task scheduling in heterogeneous computing environments[J].Cluster Computing,2014,17(2):537-550.

[8] TARPLEE K M,MACIEJEWSKI A A,SIEGEL H J.Energy-aware profit maximizing scheduling algorithm for heterogeneous computing systems[C]//14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing,May 26-29,2014,Chicago,USA.New York:IEEE,2014:595-603.

[9] DHARANE N S,KULKARNI A S,BHAWTHANKAR A U,et al.Load balancing method for infrastructure as a service (IaaS) in cloud computing:survey[J].International Journal of Computer Applications,2015,117(16):26-30.

[10] KESHVADI S,FAGHIH B.A multi-agent based load balancing system in IaaS cloud environment[J].International Robotics & Automation Journal,2016,1(1):3-8.

[11] LUO P,LYU K,SHI Z Z.A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems[J].Journal of Parallel and Distributed Computing,2007,67(6):695-714

[12] KUNE R,KONUGURTHI P K,AGARWAL A,et al.Genetic algorithm based data-aware group scheduling for big data clouds[C]//2014 IEEE/ACM International Symposium on Big Data Computing,December 8-11,2014,London,UK.New York:IEEE,2014:96-104.

[13] AL-AZZONI I,DOWN D G.Linear programming-based affinity scheduling of independent tasks on heterogeneous computing systems[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(12):1671-1682.

[14] PEI Y Y,LI X Y,YU L,et al.A cloud-based stream processing platform for traffic monitoring using large-scale probe vehicle data[C]//IEEE Wireless Communications and Networking Conference,March 19-22,2017,San Francisco,USA.New York:IEEE,2017:1-6.

[15] 孙建朋.基于多VM迁移调度的云数据中心网络流量优化技术研究[D].济南:山东大学,2016.

[16] 邓罡.数据中心网络资源管理与性能优化关键技术研究[D].长沙:国防科学技术大学,2015.

[17] AHO A V,HOPCROFT J E,ULLMAN J D.The design and analysis of computer algorithms[M].Massachusetts:Addison-Wesley,1974.

[18] DU D,DAN S,ERGEZER M.Biogeography-based optimization combined with evolutionary strategy and immigration refusal[C]//Proceedings of the IEEE International Conference on Systems,Man and Cybernetics,October 11-14,2009,San Antonio,USA.New York:IEEE,2009:997-1002.

[19] PAN P Q.Linear programming computation[M].Berlin:Springer,2014.

[20] NEMHAUSER G L,WOLSEY L A.Integer and combinatorial optimization[M].New York:John Wiley,1988.

[21] WILLIAMS H P.Model building in mathematical programming[M].New York:John Wiley,1999.

[22] IBM.CPLEX user’s manual-v12.4[Z/OL].[2018-12-05].https://www.ibm.com/products/ilog-cplex-optimization-studio.