More Web Proxy on the site http://driver.im/

article

Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds

Authors:

Ruben Van Den Bossche,

Kurt Vanmechelen,

Jan BroeckhoveAuthors Info & Claims

Future Generation Computer Systems, Volume 29, Issue 4

Pages 973 - 985

https://doi.org/10.1016/j.future.2012.12.012

Published: 01 June 2013 Publication History

Abstract

Cloud computing has found broad acceptance in both industry and research, with public cloud offerings now often used in conjunction with privately owned infrastructure. Technical aspects such as the impact of network latency, bandwidth constraints, data confidentiality and security, as well as economic aspects such as sunk costs and price uncertainty are key drivers towards the adoption of such a hybrid cloud model. The use of hybrid clouds introduces the need to determine which workloads are to be outsourced, and to what cloud provider. These decisions should minimize the cost of running a partition of the total workload on one or multiple public cloud providers while taking into account the application requirements such as deadline constraints and data requirements. The variety of cost factors, pricing models and cloud provider offerings to consider, further calls for an automated scheduling approach in hybrid clouds. In this work, we tackle this problem by proposing a set of algorithms to cost-efficiently schedule the deadline-constrained bag-of-tasks applications on both public cloud providers and private infrastructure. Our algorithms take into account both computational and data transfer costs as well as network bandwidth constraints. We evaluate their performance in a realistic setting with respect to cost savings, deadlines met and computational efficiency, and investigate the impact of errors in runtime estimates on these performance metrics.

References

[1]

Keahey, K., Tsugawa, M., Matsunaga, A. and Fortes, J., Sky computing. IEEE Internet Computing. v13. 43-51.

[2]

Buyya, R., Yeo, C.S., Venugopal, S., Broberg, J. and Brandic, I., Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility. Future Generation Computer Systems. v25. 599-616.

[3]

P. Mell, T. Grace, The NIST definition of cloud computing, Technical Report 800-145, National Institute of Standards and Technology (NIST), Information Technology Laboratory, Computer Security Division, 2011.

Digital Library

[4]

"Amazon Web Services", Amazon EC2 reserved instance marketplace - beta, 2012. http://aws.amazon.com/ec2/reserved-instances/marketplace/ (accessed 19.11.12).

[5]

Sotomayor, B., Montero, R.S., Llorente, I.M. and Foster, I., Virtual infrastructure management in private and hybrid clouds. IEEE Internet Computing. v13. 14-22.

[6]

Assunção, M.D., Costanzo, A. and Buyya, R., A cost-benefit analysis of using cloud computing to extend the capacity of clusters. Cluster Computing. v13. 335-347.

[7]

Petcu, D., Macariu, G., Panica, S. and Crciun, C., Portable cloud applications - from theory to practice. Future Generation Computer Systems.

[8]

Edmonds, A., Metsch, T., Papaspyrou, A. and Richardson, A., Toward an open cloud standard. IEEE Internet Computing. v16. 15-25.

[9]

The Apache Software Foundation, libcloud, a unified interface to the cloud, 2012. http://libcloud.apache.org/.

[10]

Apache Software Foundation, Deltacloud API, 2012. http://deltacloud.apache.org/.

[11]

Rightscale Inc., Rightscale multi-cloud engine, 2012. http://www.rightscale.com.

[12]

Tordsson, J., Montero, R.S., Moreno-Vozmediano, R. and Llorente, I.M., Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers. Future Generation Computer Systems. v28. 358-367.

[13]

W. Li, J. Tordsson, E. Elmroth, Modeling for dynamic cloud scheduling via migration of virtual machines, in: IEEE Third International Conference on Cloud Computing Technology and Science, CloudCom 2011, pp. 163-171.

Digital Library

[14]

Lucas-Simarro, J.L., Moreno-Vozmediano, R., Montero, R.S. and Llorente, I.M., Scheduling strategies for optimal service deployment across multiple clouds. Future Generation Computer Systems.

[15]

D. Breitgand, A. Maraschini, J. Tordsson, Policy-driven service placement optimization in federated clouds, Technical Report, IBM Research Division, 2011.

[16]

J. Strebel, A. Stage, An economic decision model for business software application deployment on hybrid cloud environments, M. Schumann, L.M. Kolbe, M.H. Breitner, A. Frerichs, Multikonferenz Wirtschaftsinformatik 2010, Universitätsverlag Göttingen, Göttingen, 2010, pp. 195-206.

[17]

A. Andrzejak, D. Kondo, S. Yi, Decision model for cloud computing under sla constraints, in: 2010 IEEE International Symposium on Modeling, Analysis Simulation of Computer and Telecommunication Systems, MASCOTS, pp. 257-266.

Digital Library

[18]

Kailasam, S., Gnanasambandam, N., Dharanipragada, J. and Sharma, N., Optimizing service level agreements for autonomic cloud bursting schedulers. In: International Conference on Parallel Processing Workshops, IEEE Computer Society, Los Alamitos, CA, USA. pp. 285-294.

Digital Library

[19]

U. Lampe, M. Siebenhaar, D. Schuller, R. Steinmetz, A cloud-oriented broker for cost-minimal software service distribution, in: W.Z. Rosa M. Badia (Eds.), Proceedings of the Second Optimising Cloud Services Workshop, OCS 2011.

[20]

Javadi, B., Abawajy, J. and Buyya, R., Failure-aware resource provisioning for hybrid cloud infrastructure. Journal of Parallel and Distributed Computing. v72. 1318-1331.

[21]

R. Van¿den Bossche, K. Vanmechelen, J. Broeckhove, Cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads, in: IEEE 3rd International Conference on Cloud Computing, CLOUD, 2010, pp. 228-235.

Digital Library

[22]

Van den Bossche, R., Vanmechelen, K. and Broeckhove, J., Cost-efficient scheduling heuristics for deadline constrained workloads on hybrid clouds. In: Proceedings of the 3rd IEEE International Conference on Cloud Computing Technology and Science, IEEE Computer Society. pp. 320-327.

Digital Library

[23]

Brucker, P., Scheduling Algorithms. 2004. Springer-Verlag, Berlin Heidelberg.

[24]

Verboven, S., Hellinckx, P., Arickx, F. and Broeckhove, J., Runtime prediction based grid scheduling of parameter sweep jobs. Journal of Internet and Technology. v11. 47-54.

[25]

Iverson, M.A., Özgüner, F. and Follen, G.J., Run-time statistical estimation of task execution times for heterogeneous distributed computing. In: Proceedings of 5th IEEE International Symposium on High Performance Distributed Computing, IEEE Computer Society. pp. 263-270.

[26]

Iverson, M.A., Özgüner, F. and Potter, L.C., Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment. IEEE Transactions on Computers. v48. 1374-1379.

[27]

Nadeem, F., Yousaf, M.M., Prodan, R. and Fahringer, T., Soft benchmarks-based application performance prediction using a minimum training set. In: Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, IEEE Computer Society, Washington, DC, USA. pp. 71

[28]

Nguyen, T.D., Vaswani, R. and Zahorjan, J., Parallel application characterization for multiprocessor scheduling policy design. In: Feitelson, D.G., Rudolph, L. (Eds.), Lecture Notes in Computer Science, vol. 1162. Springer-Verlag. pp. 105-118.

[29]

A.B. Downey, A model for speedup of parallel programs, Technical Report UCB/CSD-97-933, EECS Department, University of California, Berkeley, 1997.

Digital Library

[30]

Chiang, S.-H., Mansharamani, R.K. and Vernon, M.K., Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies. ACM SIGMETRICS Performance Evaluation Review. v22 i1. 33-44.

[31]

L.W. Dowdy, On the partitioning of multi-processor systems, Technical Report 88-06, Vanderbilt University, 1988.

[32]

Mualem, A.W. and Feitelson, D.G., Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling. IEEE Transactions on Parallel and Distributed Systems. v12. 529-543.

[33]

Tsafrir, D., Etsion, Y. and Feitelson, D.G., Backfilling using system-generated predictions rather than user runtime estimates. IEEE Transactions on Parallel and Distributed Systems. v18. 789-803.

[34]

Prasad, R., Dovrolis, C., Murray, M. and Claffy, K., Bandwidth estimation: metrics, measurement techniques, and tools. IEEE Network. v17. 27-35.

[35]

Shriram, A., Murray, M., Hyun, Y., Brownlee, N., Broido, A., Fomenkov, M. and claffy, k., Comparison of public end-to-end bandwidth estimation tools on high-speed links. In: Dovrolis, C. (Ed.), Lecture Notes in Computer Science, vol. 3431. Springer, Berlin, Heidelberg. pp. 306-320.

[36]

Lee, S.-J., Sharma, P., Banerjee, S., Basu, S. and Fonseca, R., Measuring bandwidth between planetlab nodes. In: Dovrolis, C. (Ed.), Lecture Notes in Computer Science, vol. 3431. Springer, Berlin, Heidelberg. pp. 292-305.

[37]

Evaluation and characterization of available bandwidth probing techniques. IEEE Journal on Selected Areas in Communications. v21 i6. 879-894.

[38]

England, D. and Weissman, J.B., Costs and benefits of load sharing in the computational grid. In: Proceedings of the 10th International Conference on Job Scheduling Strategies for Parallel Processing, Springer-Verlag, Berlin, Heidelberg. pp. 160-175.

[39]

Ranganathan, K. and Foster, I., Decoupling computation and data scheduling in distributed data-intensive applications. In: Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, IEEE Computer Society, Washington, DC, USA. pp. 352-358.

[40]

Tang, M., Lee, B.-S., Tang, X. and Yeo, C.-K., The impact of data replication on job scheduling performance in the data grid. Future Generation Computer Systems. v22. 254-268.

[41]

Chervenak, A., Foster, I., Kesselman, C., Salisbury, C. and Tuecke, S., The data grid: towards an architecture for the distributed management and analysis of large scientific datasets. Journal of Network and Computer Applications. v23. 187-200.

[42]

Feitelson, D., Rudolph, L., Schwiegelshohn, U., Sevcik, K. and Wong, P., Theory and practice in parallel job scheduling. In: Feitelson, D., Rudolph, L. (Eds.), Lecture Notes in Computer Science, vol. 1291. Springer, Berlin, Heidelberg. pp. 1-34.

[43]

Feitelson, D., Rudolph, L. and Schwiegelshohn, U., Parallel job scheduling a status report. In: Feitelson, D., Rudolph, L., Schwiegelshohn, U. (Eds.), Lecture Notes in Computer Science, vol. 3277. Springer, Berlin Heidelberg. pp. 1-16.

[44]

Iosup, A., Sonmez, O., Anoep, S. and Epema, D., The performance of bags-of-tasks in large-scale distributed systems. In: Proceedings of the 17th International Symposium on High Performance Distributed Computing, ACM, New York, NY, USA. pp. 97-108.

[45]

AuYoung, A., Vahdat, A. and Snoeren, A., Evaluating the impact of inaccurate information in utility-based scheduling. In: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, ACM, New York, NY, USA. pp. 38:1-38:12.

[46]

Bailey Lee, C., Schwartzman, Y., Hardy, J. and Snavely, A., Are user runtime estimates inherently inaccurate?. In: Feitelson, D., Rudolph, L., Schwiegelshohn, U. (Eds.), Lecture Notes in Computer Science, vol. 3277. Springer, Berlin, Heidelberg. pp. 253-263.

[47]

Chiang, S.-H., Arpaci-Dusseau, A. and Vernon, M., The impact of more accurate requested runtimes on production job scheduling performance. In: Feitelson, D., Rudolph, L., Schwiegelshohn, U. (Eds.), Lecture Notes in Computer Science, vol. 2537. Springer, Berlin, Heidelberg. pp. 103-127.

Cited By

Aron RAbraham A(2022)Resource scheduling methods for cloud computing environmentEngineering Applications of Artificial Intelligence10.1016/j.engappai.2022.105345116:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.engappai.2022.105345
Hariri MNouri-Baygi MAbrishami S(2022)A hybrid algorithm for scheduling scientific workflows in IaaS cloud with deadline constraintThe Journal of Supercomputing10.1007/s11227-022-04563-878:15(16975-16996)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11227-022-04563-8
Abbes WKechaou ZHussain AQahtani AAlmutiry ODhahri HAlimi A(2022)An Enhanced Binary Particle Swarm Optimization (E-BPSO) algorithm for service placement in hybrid cloud platformsNeural Computing and Applications10.1007/s00521-022-07839-535:2(1343-1361)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/s00521-022-07839-5
Show More Cited By

Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds

Recommendations

A cost model for hybrid clouds
GECON'11: Proceedings of the 8th international conference on Economics of Grids, Clouds, Systems, and Services

Cloud computing aims at allowing customers to utilize computational resources and software hosted by service providers. Thus, it shifts the complex and tedious resource and software management tasks typically done by customers to the service providers. ...
Cost-Efficient Scheduling Heuristics for Deadline Constrained Workloads on Hybrid Clouds
CLOUDCOM '11: Proceedings of the 2011 IEEE Third International Conference on Cloud Computing Technology and Science

Cloud computing offerings are maturing steadily, and their use has found acceptance in both industry and research. Cloud servers are used more and more instead of, or in addition to, local compute and storage infrastructure. Deciding which workloads to ...
Cost-Optimal Scheduling in Hybrid IaaS Clouds for Deadline Constrained Workloads
CLOUD '10: Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing

With the recent emergence of public cloud offerings, surge computing –outsourcing tasks from an internal data center to a cloud provider in times of heavy load– has become more accessible to a wide range of consumers. Deciding which workloads to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Future Generation Computer Systems

Future Generation Computer Systems Volume 29, Issue 4

June, 2013

186 pages

ISSN:0167-739X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2012.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 June 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aron RAbraham A(2022)Resource scheduling methods for cloud computing environmentEngineering Applications of Artificial Intelligence10.1016/j.engappai.2022.105345116:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.engappai.2022.105345
Hariri MNouri-Baygi MAbrishami S(2022)A hybrid algorithm for scheduling scientific workflows in IaaS cloud with deadline constraintThe Journal of Supercomputing10.1007/s11227-022-04563-878:15(16975-16996)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11227-022-04563-8
Abbes WKechaou ZHussain AQahtani AAlmutiry ODhahri HAlimi A(2022)An Enhanced Binary Particle Swarm Optimization (E-BPSO) algorithm for service placement in hybrid cloud platformsNeural Computing and Applications10.1007/s00521-022-07839-535:2(1343-1361)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/s00521-022-07839-5
Stavrinides GKaratza H(2021)Dynamic scheduling of bags-of-tasks with sensitive input data and end-to-end deadlines in a hybrid cloudMultimedia Tools and Applications10.1007/s11042-020-08974-880:11(16781-16803)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s11042-020-08974-8
Hepsiba PGrace Mary Kanaga E. (2020)An Osmosis-Based Intelligent Agent Scheduling Framework for Cloud Bursting in a Hybrid CloudInternational Journal of Distributed Systems and Technologies10.4018/IJDST.202007010411:3(68-88)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.4018/IJDST.2020070104
Liang YCui QGan LXie ZZhai SCrabbe MLi RDong RManta OComite U(2020)A Cloud Computing Task Scheduling Strategy Based on Improved Particle Swarm OptimizationProceedings of the 2020 2nd International Conference on Big Data and Artificial Intelligence10.1145/3436286.3436500(543-549)Online publication date: 28-Apr-2020
https://dl.acm.org/doi/10.1145/3436286.3436500
Tuli SSandhu RBuyya R(2020)Shared data-aware dynamic resource provisioning and task scheduling for data intensive applications on hybrid clouds using AnekaFuture Generation Computer Systems10.1016/j.future.2020.01.038106:C(595-606)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1016/j.future.2020.01.038
Masdari MZangakani M(2020)Efficient task and workflow scheduling in inter-cloud environments: challenges and opportunitiesThe Journal of Supercomputing10.1007/s11227-019-03038-776:1(499-535)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1007/s11227-019-03038-7
Elhabbash ASamreen FHadley JElkhatib Y(2019)Cloud BrokerageACM Computing Surveys10.1145/327465751:6(1-28)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3274657
Calzarossa MDella Vedova MTessera D(2019)A methodological framework for cloud resource provisioning and scheduling of data parallel applications under uncertaintyFuture Generation Computer Systems10.1016/j.future.2018.10.03793:C(212-223)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1016/j.future.2018.10.037
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents