[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

A green policy to schedule tasks in a distributed cloud

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In the last years, demand and availability of computational capabilities experienced radical changes. Desktops and laptops increased their processing resources, exceeding users’ demand for large part of the day. On the other hand, computational methods are more and more frequently adopted by scientific communities, which often experience difficulties in obtaining access to the required resources. Consequently, data centers for outsourcing use, relying on the cloud computing paradigm, are proliferating. Notwithstanding the effort to build energy-efficient data centers, their energy footprint is still considerable, since cooling a large number of machines situated in the same room or container requires a significant amount of power. The volunteer cloud, exploiting the users’ willingness to share a quote of their underused machine resources, can constitute an effective solution to have the required computational resources when needed. In this paper, we foster the adoption of the volunteer cloud computing as a green (i.e., energy efficient) solution even able to outperform existing data centers in specific tasks. To manage the complexity of such a large scale heterogeneous system, we propose a distributed optimization policy to task scheduling with the aim of reducing the overall energy consumption executing a given workload. To this end, we consider an integer programming problem relying on the Alternating Direction Method of Multipliers (ADMM) for its solution. Our approach is compared with a centralized one and other non-green targeting solutions. Results show that the distributed solution found by the ADMM constitutes a good suboptimal solution, worth to be applied in a real environment.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. https://github.com/distributedResearch/taskSchedulingADMM.

References

  1. The Service Level Agreement. http://www.sla-zone.co.uk (2015)

  2. Amoretti, M., Lafuente, A., Sebastio, S.: A cooperative approach for distributed task execution in autonomic clouds. In: PDP’13 (2013). https://doi.org/10.1109/PDP.2013.47

  3. Anderson, D.P.: BOINC: A system for public-resource computing and storage. In: GRID ’04 (2004). https://doi.org/10.1109/GRID.2004.14

  4. Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@Home: an experiment in public-resource computing. Commun. ACM 45(11), 56–61 (2002). https://doi.org/10.1145/581571.581573

    Article  Google Scholar 

  5. Babaoglu, O., Marzolla, M., Tamburini, M.: Design and Implementation of a P2P Cloud System. In: SAC ’12 (2012). https://doi.org/10.1145/2245276.2245357

  6. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)

    Article  Google Scholar 

  7. Brasileiro, F., Araujo, E., Voorsluys, W., Oliveira, M., Figueiredo, F.: Bridging the high performance computing gap: the ourgrid experience. In: CCGrid’07 (2007). https://doi.org/10.1109/CCGRID.2007.28

  8. Cappos, J., Beschastnikh, I., Krishnamurthy, A., Anderson, T.: Seattle: a platform for educational cloud computing. SIGCSE Bull. 41(1), 111–115 (2009). https://doi.org/10.1145/1539024.1508905

    Article  Google Scholar 

  9. Carrabs, F., Cerulli, R., D’Ambrosio, C., Gentili, M., Raiconi, A.: Maximizing lifetime in wireless sensor networks with multiple sensor families. Comput. Oper. Res. 60, 121–137 (2015). https://doi.org/10.1016/j.cor.2015.02.013

    Article  MathSciNet  MATH  Google Scholar 

  10. Caton, S., Rana, O.: Towards autonomic management for Cloud services based upon volunteered resources. Concurr. Comput. Pract. Exp. 24(9), 992–1014 (2012). https://doi.org/10.1002/cpe.1715

    Article  Google Scholar 

  11. Celestini, A., Lluch Lafuente, A., Mayer, P., Sebastio, S., Tiezzi, F.: Reputation-based cooperation in the clouds. In: IFIPTM’14 (2014). https://doi.org/10.1007/978-3-662-43813-8_15

    Google Scholar 

  12. Costa, F., Silva, L., Dahlin, M.: Volunteer cloud computing: mapreduce over the internet. In: IEEE IPDPSW’11 (2011). https://doi.org/10.1109/IPDPS.2011.345

  13. Cunsolo, V.D., Distefano, S., Puliafito, A., Scarpa, M.: Cloud@Home: bridging the gap between volunteer and cloud computing. In: ICIC’09 (2009). https://doi.org/10.1007/978-3-642-04070-2_48

    Chapter  Google Scholar 

  14. Di Nitto, E., Dubois, D.J., Mirandola, R.: On exploiting decentralized bio-inspired self-organization algorithms to develop real systems. In: SEAMS ’09 (2009). https://doi.org/10.1109/SEAMS.2009.5069075

  15. Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)

    Article  Google Scholar 

  16. Feizollahi, M.J., Costley, M., Ahmed, S., Grijalva, S.: Large-scale decentralized unit commitment. Int. J. Elect. Power Energy Syst. 73(0), 97–106 (2015). https://doi.org/10.1016/j.ijepes.2015.04.009

    Article  Google Scholar 

  17. Ghadimi, E., Teixeira, A., Shames, I., Johansson, M.: Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems. IEEE Trans. Autom. Control 60(3), 644–658 (2015). https://doi.org/10.1109/TAC.2014.2354892

    Article  MathSciNet  MATH  Google Scholar 

  18. Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Recent advances in learning and control, pp. 95–110 (2008). http://stanford.edu/~boyd/graph_dcp.html

  19. Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. (2014). http://cvxr.com/cvx

  20. Gurobi Optimization Inc.: Gurobi optimizer reference manual (2015).http://www.gurobi.com

  21. Haridas, H., Kailasam, S., Dharanipragada, J.: Cloudy knapsack problems: an optimization model for distributed cloud-assisted systems. In: P2P’14 (2014). https://doi.org/10.1109/P2P.2014.6934313

  22. Hellerstein, J.L.: Google cluster data. Google research blog (2010). http://googleresearch.blogspot.com/2010/01/google-cluster-data.html

  23. Hill, M.D., Marty, M.R.: Amdahl’s Law in the Multicore Era. Computer 41(7), 33–38 (2008). https://doi.org/10.1109/MC.2008.209

    Article  Google Scholar 

  24. Kavalionak, H., Montresor, A.: P2P and cloud: a marriage of convenience for replica management. In: Self-organizing systems, LNCS (2012). https://doi.org/10.1007/978-3-642-28583-7_6

    Chapter  Google Scholar 

  25. Kavalionak, H., Carlini, E., Ricci, L., Montresor, A., Coppola, M.: Integrating peer-to-peer and cloud computing for massively multiuser online games. Peer-to-Peer Netw. Appl. (2013). https://doi.org/10.1007/s12083-013-0232-4

    Article  Google Scholar 

  26. Li, B., Song, S., Bezakova, I., Cameron, K.: EDR: an energy-aware runtime load distribution system for data-intensive applications in the cloud. In: CLUSTER’2013 (2013). https://doi.org/10.1109/CLUSTER.2013.6702674

  27. Malawski, M., Figiela, K., Nabrzyski, J.: Cost minimization for computational applications on hybrid cloud infrastructures. Fut. Gen. Comput. Syst. 29(7), 1786–1794 (2013). https://doi.org/10.1016/j.future.2013.01.004

    Article  Google Scholar 

  28. Malawski, M., Figiela, K., Bubak, M., Deelman, E., Nabrzyski, J.: Scheduling multilevel deadline-constrained scientific workflows on clouds based on cost optimization. Sci. Prog. 2015, 680,271:1–680,271:13 (2015). https://doi.org/10.1155/2015/680271

    Article  Google Scholar 

  29. Miksik, O., Vineet, V., Pérez, P., Torr, P.: Distributed non-convex ADMM-based inference in large-scale random fields. In: BMVC’14 (2014)

  30. Milojicic, D.S., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., Rollins, S., Xu, Z.: Peer-to-Peer computing. Tech. Rep. HPL-2002-57, HP Laboratories Palo Alto (2002). http://www.hpl.hp.com/techreports/2002/HPL-2002-57R1.pdf

  31. Mishra, A.K., Hellerstein, J.L., Cirne, W., Das, C.R.: Towards characterizing cloud backend workloads: insights from google compute clusters. ACM SIGMETRICS Perform. Eval. Rev. 37(4), 34–41 (2010). https://doi.org/10.1145/1773394.1773400

    Article  Google Scholar 

  32. Montresor, A., Abeni, L.: Cloudy weather for P2P, with a chance of gossip. In: IEEE P2C Computing’11 (2011). https://doi.org/10.1109/P2P.2011.6038743

  33. Nir, M., Matrawy, A., St-Hilaire, M.: An energy optimizing scheduler for mobile cloud computing environments. In: INFOCOM WKSHPS’14 (2014). https://doi.org/10.1109/INFCOMW.2014.6849266

  34. Saino, L., Cocora, C., Pavlou, G.: A toolchain for simplifying network simulation setup. In: SIMUTOOLS (2013)

  35. Satyanarayanan, M., Bahl, P., Caceres, R., Davies, N.: The case for VM-based cloudlets in mobile computing. IEEE Pervasive Comput. 8(4), 14–23 (2009). https://doi.org/10.1109/MPRV.2009.82

    Article  Google Scholar 

  36. Sebastio, S., Scala, A.: A workload-based approach to partition the volunteer cloud. In: CIC’15 (2015). https://doi.org/10.1109/CIC.2015.27

  37. Sebastio, S., Amoretti, M., Lluch Lafuente, A.: A computational field framework for collaborative task execution in volunteer clouds. In: SEAMS’14 (2014). https://doi.org/10.1145/2593929.2593943

  38. Sebastio, S., Amoretti, M., Lluch Lafuente, A.: AVOCLOUDY: a simulator of volunteer clouds. Softw.: Pract. Exp. 46(1), 3–30 (2016). https://doi.org/10.1002/spe.2345

    Article  Google Scholar 

  39. Sebastio, S., Amoretti, M., Lluch Lafuente, A., Scala, A.: A holistic approach for collaborative workload execution in volunteer clouds. ACM TOMACS (2017a)

  40. Sebastio, S., Gnecco, G., Bemporad, A.: Optimal and distributed task scheduling in volunteer clouds. Comput. Oper. Res. (2017b). https://doi.org/10.1016/j.cor.2016.11.004

    Article  MathSciNet  Google Scholar 

  41. Sun, X.H., Chen, Y.: Reevaluating Amdahl’s law in the multicore era. J. Parallel Distrib. Comput. 70(2), 183–188 (2010). https://doi.org/10.1016/j.jpdc.2009.05.002

    Article  MATH  Google Scholar 

  42. Talia, D.: Cloud computing and software agents: towards cloud intelligent services. In: WOA’11 (2011)

  43. Thain, D., Tannenbaum, T., Livny, M.: Distributed computing in practice: the Condor experience. Concurr.: Pract. Exp. 17(2–4), 323–356 (2005)

    Article  Google Scholar 

  44. Tsai, J.T., Fang, J.C., Chou, J.H.: Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm. Comput. Oper. Res. 40(12), 3045–3055 (2013). https://doi.org/10.1016/j.cor.2013.06.012

    Article  MATH  Google Scholar 

  45. Wendell, P., Jiang, J.W., Freedman, M.J., Rexford, J.: DONAR: decentralized server selection for cloud services. SIGCOMM Comput. Commun. Rev. 40(4), 231–242 (2010)

    Article  Google Scholar 

  46. Woo, D.H., Lee, H.H.: Extending Amdahl’s law for energy-efficient computing in the many-core era. Computer 41(12), 24–31 (2008). https://doi.org/10.1109/MC.2008.494

    Article  Google Scholar 

  47. Xu, H., Li, B.: Joint request mapping and response routing for geo-distributed cloud services. In: INFOCOM’13 (2013). https://doi.org/10.1109/INFCOM.2013.6566873

  48. Zambonelli, F., Mamei, M.: Spatial computing: an emerging paradigm for autonomic computing and communication. In: WAC’04 (2004). https://doi.org/10.1007/11520184_4

    Google Scholar 

  49. Zhu, C., Li, X., Leung, V.C.M., Hu, X., Yang, L.T.: Job scheduling for cloud computing integrated with wireless sensor network. In: CloudCom’14 (2014). https://doi.org/10.1109/CloudCom.2014.106

Download references

Acknowledgements

This research was partially supported by the EU through the HOME/2013/CIPS/AG/4000005013 project CI2C. The contents of the paper do not necessarily reflect the position or the policy of funding parties.

Author information

Authors and Affiliations

  1. LIMS London Institute of Mathematical Sciences, London, W1K 2XF, UK

    Stefano Sebastio

  2. IMT School for Advanced Studies, 55100, Lucca, Italy

    Giorgio Gnecco

Authors
  1. Stefano Sebastio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giorgio Gnecco
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stefano Sebastio.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sebastio, S., Gnecco, G. A green policy to schedule tasks in a distributed cloud. Optim Lett 12, 1535–1551 (2018). https://doi.org/10.1007/s11590-017-1208-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-017-1208-8

Keywords

Search

Navigation