中文

Journal of Applied Sciences >

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

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

Computer Science and Applications

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

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

Cite this article

YANG Yanan, LI Yiming, NIE Lihai, ZHANG Ning, ZHAO Laiping . Cost-Efficient Task Scheduling in Geo-distributed Datacenters[J]. Journal of Applied Sciences, 2019 , 37(6) : 859 -874 . DOI: 10.3969/j.issn.0255-8297.2019.06.011

References

[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
Outlines

/

〈 〉