English

应用科学学报 >

2019 , Vol. 37 >Issue 6: 859 - 874

DOI: https://doi.org/10.3969/j.issn.0255-8297.2019.06.011

计算机科学与应用

跨地域分布数据中心高成本效益的任务调度

展开
  • 天津大学 智能与计算学部, 天津 300350

收稿日期: 2019-06-13

  修回日期: 2019-06-20

  网络出版日期: 2019-12-06

收起

Cost-Efficient Task Scheduling in Geo-distributed Datacenters

Expand
  • College of Intelligence and Computing, Tianjin University, Tianjin 300350, China

Received date: 2019-06-13

  Revised date: 2019-06-20

  Online published: 2019-12-06

Fold

摘要

研究了跨地域分布数据中心云计算成本最小化问题，首先将其建模为一般分配问题，利用增广拉格朗日乘子法（augmented Lagrangian multiplier method，ALMM）得到最优的调度方案，然后设计了Adjusting算法以调整ALMM产生的结果，使之成为可行解.进一步设计了一种降序价值密度算法（decreased value density scheduling algorithm，DVDS），以解决ALMM的收敛速度相对较慢的问题.在线性定价和阶梯定价两种模型下的实验结果表明，当任务数量较少时，DVDS算法可以在拥有极小的时间开销下达到和ALMM同样小的调度成本；当任务数量增加时，DVDS产生的调度结果成本相比ALMM仅增加10%左右.

关键词： 任务调度; 成本效益; 云计算

本文引用格式

杨亚南, 李一鸣, 聂力海, 张宁, 赵来平 . 跨地域分布数据中心高成本效益的任务调度[J]. 应用科学学报, 2019 , 37(6) : 859 -874 . DOI: 10.3969/j.issn.0255-8297.2019.06.011

Abstract

In this paper, we study the cost minimization for cloud users in geo-distributed cloud systems. By modeling it as a general assignment problem (GAP), we use the augmented Lagrangian multiplier method (ALMM) to obtain the optimal schedule solution. We additionally apply an Adjusting algorithm that adjusts the solution produced by ALMM to make it more feasible. We further use a decreased value density scheduling algorithm (DVDS) to speed up the convergence of ALMM. Experimental results show that DVDS algorithm can work out solutions in a much shorter period than ALMM does with costs similar to ALMM's in the case of small task, and only 10% more in the case of large task.

Key words： task scheduling; cost-efficiency; cloud computing

参考文献

[1] Mohamed H. Security of cloud computing providers study[R]//Ponemon Institute:Research Report, 2011:1-25.
[2] Tang X. Green-aware workload scheduling in geographically distributed data centers[C]//Cloud Computing Technology and Science, 2012 IEEE 4th International Conference. Taipei, China. 2012:82-89.
[3] Beloglazov A, Buyya R. Energy efficient allocation of virtual machines in cloud data centers[C]//2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing. IEEE, 2010:577-578.
[4] Michele M, Dmytro D, Ralph D. Maximizing cloud providers' revenues via energy aware allocation policies[C]//Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing (CLOUD'10). IEEE Computer Society, 2010:131-138.
[5] Zhao L P, Lu L F, Zhou J, et al. Online virtual machine placement for increasing cloud provider's revenue[J]. IEEE Transactions on Services Computing, 2015, 10(2):273-285.
[6] He X, Prashant S, Ramesh S, et al. Cutting the cost of hosting online services using cloud spot markets[C]//International Symposium on High-Performance Parallel and Distributed Computing (HPDC). Oregon, USA:2015:207-218.
[7] Guo W C, Chen K, Wu Y W, et al. Bidding for highly available services with low price in spot instance market[C]//High-Performance Parallel and Distributed Computing (HPDC). Oregon, USA, 2015:191-202.
[8] Koomey J, Brill K, Turner P, et al. A simple model for determining true total cost of ownership for data centers[J]. Earthquake Spectra, 1988, 4(2):277-317.
[9] Greenberg A G, Hamilton J R, Maltz D A, et al. The cost of a cloud:research problems in data center networks[J]. ACM Sigcomm Computer Communication Review, 2009, 39(1):68-73.
[10] Yin L, Sun J, Zhao L P, et al. Joint scheduling of data and computation in geo-distributed cloud systems[C]//15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid). IEEE, 2015:657-666.
[11] Li Y, Zhao L P, Cui C Z. Fast big data analysis in GEO-distributed cloud[C]//2016 IEEE International Conference on Cluster Computing (CLUSTER). IEEE, 2016:388-391.
[12] Marshall P, Kaeahey K, Freeman T. Elastic site:using clouds to elastically extend site resources[C]//Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing. IEEE Computer Society, 2010:43-52.
[13] Beloglazov A, Buyya R. Energy efficient allocation of virtual machines in cloud data centers[C]//2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing. IEEE, 2010:577-578.
[14] Michele M, Dmytro D, Ralph D. Maximizing cloud providers' revenues via energy aware allocation policies[C]//2010 IEEE 3rd International Conference on Cloud Computing. IEEE, 2010:131-138.
[15] Song W J, Xiao Z, Chen Q. Dynamic resource allocation using virtual machines for cloud computing environment[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 24(6):1107-1117.
[16] Krihnaveni N, Sivakumar G. Survey on dynamic resource allocation strategy in cloud computing environment[J]. International Journal of Computer Applications Technology and Research, 2013, 2(6):731-737.
[17] Qureshi A, Rick W, Hari B, et al. Cutting the electric bill for internet-scale systems[J]. Computer Communication Review, 2009, 39(4):123-134.
[18] Amokrane A, Zhani M F, Langar R, et al. Greenhead:virtual data center embedding across distributed infrastructures[J]. IEEE Transactions on Cloud Computing, 2013, 1(1):36-49.
[19] Vinod K V, Murthy A, Chris D. Apache hadoop yarn:yet another resource negotiator[C]//Proceedings of the 4th annual Symposium on Cloud Computing. ACM, New York, 2013:5.
[20] Zeng F S. Large-scale cluster management at Google with Borg[C]//6th EEM International Conference on Education Science and Social Science (EEM-ESSS 2017), Singapore, 2017, 104:76-80.
[21] Malte S, Andy K, Michael A, et al. Omega:flexible, scalable schedulers for large compute clusters[C]//Scalable Schedulers for Large Compute Clusters, 2013:351-364.
[22] Benjamin H, Andy K, Matei Z, et al. Mesos:a platform for fine-grained resource sharing in the data center[C]//Symposium on Network System Design and Implementation, NSDI 2011.
[23] Cai B L, Zhang R Q, Zhao L P, et al. Less provisioning:A fine-grained resource scaling engine for long-running services with tail latency guarantees[C]//Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018, 30.
[24] Yang Y N, Zhao L P, Li Z G, et al. ElaX:provisioning resource elastically for containerized online cloud services[C]//21th IEEE International Conference on High Performance Computing and Communication, HPCC 2019, Changsha, China, 2019:1987-1994.
[25] Znao L P, Yang Y N, Munir A, et al. Optimizing geo-distributed data analytics with coordinated task scheduling and routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2019:371-385.
[26] Dantzig G B. Discrete-variable extremum problems[J]. Operations Research, 1957, 5(2):266-288.
[27] Gong D J, Mitsuo G, Yamazaki G, et al. Neural network approach for general assignment problem[C]//Proceedings of ICNN'95-International Conference on Neural Networks. IEEE, 1995(4):1861-1866.
[28] Zhang Q, Zhu Q Y, Raouf B. Dynamic resource allocation for spot markets in cloud computing environments[C]//2011 Fourth IEEE International Conference on Utility and Cloud Computing. IEEE, 2011:178-185.
[29] Jalaparti V, Bliznets I, Kandula S, et al. Dynamic pricing and traffic engineering for timely inter-datacenter transfers[C]//Proceedings of the 2016 ACM SIGCOMM Conference. ACM, 2016:73-86.
[30] Chen J L, Wang C, Zhou B B, et al. Tradeoffs between profit and customer satisfaction for service provisioning in the cloud[C]//Proceedings of the 20th International Symposium on High Performance Distributed Computing. ACM, 2011:229-238.
[31] Cao J, Hwang K, Li K, et al. Optimal multi-server configuration for profit maximization in cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 24(6):1087-1096.
[32] Su S, Li J, Huang Q J, et al. Cost-efficient task scheduling for executing large programs in the cloud[J]. Parallel Computing, 2013, 39(4/5):177-188.
[33] Stephane G, Julien G. Cost-wait trade-offs in client-side resource provisioning with elastic clouds[C]//2011 IEEE 4th International Conference on Cloud Computing. IEEE, 2011:1-8.
[34] Zhan J F, Wang L, Li X N, et al. Cost-aware cooperative resource provisioning for heterogeneous workloads in data centers[J]. IEEE Transactions on Computers, 2012, 62(11):2155-2168.
Options
文章导航

/

〈 〉