{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T10:09:33Z","timestamp":1776334173233,"version":"3.51.2"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T00:00:00Z","timestamp":1672704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T00:00:00Z","timestamp":1672704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cloud Comp"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Distributed service applications make heavy use of clouds and multi-clouds, and must (i) meet service quality goals (e.g. response time) while (ii) satisfying cloud resource constraints and (iii) conserving power. Deployment algorithms must (iv) provide a solution meeting these requirements within a short time to be useful in practice. Very few existing deployment methods address the first three requirements, and those that do take too long to find a deployment. The <jats:italic>Low-Power Multi-Cloud Application Deployment<\/jats:italic> (LPD) algorithm fills this gap with a low-complexity heuristic combination of generalized graph partitioning between clouds, bin-packing within each cloud and queueing approximations to control the response time. LPD has no known competitor that quickly finds a solution that satisfies response time bounds. A host execution time approximation for contention is fundamental to achieving sufficient solution speed. LPD is intended for use by cloud managers who must simultaneously manage hosts and application deployments and plan capacity to offer services such as Serverless Computing.<\/jats:p><jats:p>On 104 test scenarios deploying up to 200 processes with up to 240 replicas (for scaling), LPD always produced a feasible solution within 100\u2009s (within 20\u2009seconds in over three-quarters of cases). Compared to the Mixed Integer Program solution by CPLEX (which took a lot longer and was sometimes not found) LPD solutions gave power consumption equal to MIP in a third of cases and within 6% of MIP in 95% of cases. In 93% of all 104 cases the power consumption is within 20% of an (unachievable) lower bound.<\/jats:p><jats:p>LPD is intended as a stand-alone heuristic to meet solution time restrictions, but could easily be adapted for use as a repair mechanism in a Genetic Algorithm.<\/jats:p>","DOI":"10.1186\/s13677-022-00363-w","type":"journal-article","created":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T23:02:31Z","timestamp":1672786951000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Low-power multi-cloud deployment of large distributed service applications with response-time constraints"],"prefix":"10.1186","volume":"12","author":[{"given":"Babneet","family":"Singh","sequence":"first","affiliation":[]},{"given":"Ravneet","family":"Kaur","sequence":"additional","affiliation":[]},{"given":"Murray","family":"Woodside","sequence":"additional","affiliation":[]},{"given":"John W.","family":"Chinneck","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,3]]},"reference":[{"key":"363_CR1","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen HI, Khan A, Pokutta S, Tetali P (2017) Approximation and online algorithms for multidimensional bin packing: a survey. Comp Sci Rev 24:63\u201379","journal-title":"Comp Sci Rev"},{"key":"363_CR2","doi-asserted-by":"publisher","unstructured":"Arroba P, Moya J, Ayala J, Buyya R (2017) Dynamic voltage and frequency scaling-aware dynamic consolidation of virtual machines for energy efficient cloud data centers. Concur Comput Pract Exper 29 (10), https:\/\/doi.org\/10.1002\/cpe.4067","DOI":"10.1002\/cpe.4067"},{"key":"363_CR3","volume-title":"Application deployment framework for large-scale fog computing environments, PhD Thesis","author":"N Verba","year":"2019","unstructured":"Verba N (2019) Application deployment framework for large-scale fog computing environments, PhD Thesis. Coventry University, Coventry, England"},{"key":"363_CR4","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.jnca.2015.12.018","volume":"64","author":"J Zhang","year":"2016","unstructured":"Zhang J, Huang H, Wang X (2016) Resource provision algorithms in cloud computing: a survey. J Netw Comput Appl 64:23\u201342","journal-title":"J Netw Comput Appl"},{"key":"363_CR5","doi-asserted-by":"crossref","unstructured":"Helali L, Omri MN (2021) A survey of data center consolidation in cloud computing systems. Comp Sci Rev 39, 100366","DOI":"10.1016\/j.cosrev.2021.100366"},{"key":"363_CR6","volume-title":"Green cloud computing using proactive virtual machine placement: challenges and issues","author":"M Masdari","year":"2020","unstructured":"Masdari M, Zangakani M (2020) Green cloud computing using proactive virtual machine placement: challenges and issues. Springer J. Grid Computing"},{"key":"363_CR7","first-page":"488","volume-title":"A survey of task allocation techniques in MAS","author":"GM Skaltsis","year":"2021","unstructured":"Skaltsis GM, Shin H-S, Tsourdos A (2021) A survey of task allocation techniques in MAS, pp 488\u2013497 Int. Conf. on Unmanned Aircraft Systems (ICUAS)"},{"issue":"1","key":"363_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1109\/TSE.2011.3","volume":"38","author":"S Malek","year":"2012","unstructured":"Malek S, Medvidovic N, Mikic-Rakic M (2012) An extensible framework for improving a distributed software System's deployment architecture. IEEE Trans Softw Eng 38(1):73\u2013100","journal-title":"IEEE Trans Softw Eng"},{"issue":"2","key":"363_CR9","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1109\/TCC.2015.2409873","volume":"5","author":"J Li","year":"2017","unstructured":"Li J, Woodside M, Chinneck J, Litiou M (2017) Adaptive cloud deployment using persistence strategies and application awareness. IEEE Trans Cloud Comput 5(2):277\u2013290","journal-title":"IEEE Trans Cloud Comput"},{"key":"363_CR10","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.jss.2016.10.001","volume":"123","author":"M Ciavotta","year":"2017","unstructured":"Ciavotta M, Ardagna D, Gibilisco GP (2017) A mixed integer linear programming optimization approach for multi-cloud capacity allocation. J Syst Softw 123:64\u201378","journal-title":"J Syst Softw"},{"key":"363_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2021.05.012","volume-title":"Research on strong agile response task scheduling optimization enhancement with optimal resource usage in green cloud computing","author":"W Shu","year":"2021","unstructured":"Shu W, Cai K, Xiong NN (2021) Research on strong agile response task scheduling optimization enhancement with optimal resource usage in green cloud computing. Elsevier Future Generation Computer Systems"},{"key":"363_CR12","first-page":"267","volume-title":"Multi-objective meta-heuristics for scheduling applications with high availability requirements and cost constraints in multi-cloud environments","author":"ME Frincu","year":"2011","unstructured":"Frincu ME, Craciun C (2011) Multi-objective meta-heuristics for scheduling applications with high availability requirements and cost constraints in multi-cloud environments, pp 267\u2013274 4th IEEE Int Conf on Utility and Cloud Computing"},{"key":"363_CR13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10723-017-9419-x","volume":"16","author":"C Guerrero","year":"2018","unstructured":"Guerrero C, Lera I, Juiz C (2018) Genetic algorithm for multi-objective optimization of container allocation in cloud architecture. J Grid Computing 16:113\u2013135","journal-title":"J Grid Computing"},{"key":"363_CR14","first-page":"512","volume-title":"Search based genetic optimization for deployment and reconfiguration of software in the cloud","author":"S Frey","year":"2013","unstructured":"Frey S, Fittkau F, Hasselbring W (2013) Search based genetic optimization for deployment and reconfiguration of software in the cloud, pp 512\u2013521 Proc Int. Conf. on Software Engineering (ICSE '13)"},{"key":"363_CR15","doi-asserted-by":"publisher","first-page":"16006","DOI":"10.1109\/ACCESS.2017.2733723","volume":"5","author":"X Ye","year":"2017","unstructured":"Ye X, Yin Y, Lan L (2017) Energy-efficient many-objective virtual machine placement optimization in a cloud computing environment. IEEE Access 5:16006\u201316020","journal-title":"IEEE Access"},{"key":"363_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.future.2016.12.034","volume":"71","author":"T Geurout","year":"2017","unstructured":"Geurout T, Gaoua Y, Artigues C, Da Costa G (2017) Mixed integer linear programming for quality of service optimization in clouds. Futur Gener Comput Syst 71:1\u201317","journal-title":"Futur Gener Comput Syst"},{"issue":"10","key":"363_CR17","first-page":"370","volume":"32","author":"R Alizadeh","year":"2019","unstructured":"Alizadeh R, Nishi T (2019) A genetic algorithm for multi-period location problem with modular emergency facilities and backup services. Trans Inst Syst Contr Inform Eng 32(10):370\u2013377","journal-title":"Trans Inst Syst Contr Inform Eng"},{"key":"363_CR18","unstructured":"IBM, \u201cIBM CPLEX Optimizer\u201d, https:\/\/www.ibm.com\/analytics\/cplex-optimizer, (Accessed 11 May 2021)"},{"key":"363_CR19","first-page":"175","volume-title":"A linear-time heuristic for improving network partitions","author":"CM Fiduccia","year":"1982","unstructured":"Fiduccia CM, Mattheyses RM (1982) A linear-time heuristic for improving network partitions, pp 175\u2013181 19th Design Automation Conference"},{"key":"363_CR20","first-page":"963","volume-title":"Network aware resource allocation in distributed clouds","author":"M Alicherry","year":"2012","unstructured":"Alicherry M, Lakshman T (2012) Network aware resource allocation in distributed clouds, pp 963\u2013971 Proc. IEEE INFOCOM"},{"key":"363_CR21","first-page":"1","volume-title":"ACO based graph partitioning algorithm for optimistic deployment of software in MCC. Proc. Int. Conf. Innovations in information","author":"S Sachdeva","year":"2015","unstructured":"Sachdeva S, Kaur K (2015) ACO based graph partitioning algorithm for optimistic deployment of software in MCC. Proc. Int. Conf. Innovations in information, pp 1\u20135 Embedded and Communication Systems (ICIIECS 2015)"},{"key":"363_CR22","doi-asserted-by":"crossref","unstructured":"Leivadeas A, Papagianni C, Papavassiliou S (2013) Efficient resource mapping framework over networked clouds via iterated local search-based request partitioning. IEEE Trans Parallel Distrib Syst: vol. 24, no. 6, pp. 1077\u20131086.","DOI":"10.1109\/TPDS.2012.204"},{"key":"363_CR23","first-page":"32","volume-title":"Redundant virtual machine placement for fault-tolerant consolidated server clusters","author":"F Machida","year":"2010","unstructured":"Machida F, Kawato M, Maeno Y (2010) Redundant virtual machine placement for fault-tolerant consolidated server clusters, pp 32\u201339 Network Operations and Management Symposium (NOMS 2010)"},{"key":"363_CR24","first-page":"192","volume-title":"Performance prediction of cloud-based big data applications","author":"D Ardagna","year":"2018","unstructured":"Ardagna D, Barbierato E, Evangelinou A, Gianniti E, Gribaudo M, Pinto TB, Guimar\u00e3es A, Couto da Silva AP, Almeida JM (2018) Performance prediction of cloud-based big data applications, pp 192\u2013199 Proc ACM\/SPEC Int Conf on Performance Engineering"},{"key":"363_CR25","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAC.2015.16","volume-title":"Near-optimal allocation of VMs from IaaS providers by SaaS providers","author":"A Aldhalaan","year":"2015","unstructured":"Aldhalaan A, Menasc\u00e9 DA (2015) Near-optimal allocation of VMs from IaaS providers by SaaS providers. Proc. Int. Conf. on Cloud and Autonomic Computing"},{"key":"363_CR26","first-page":"19","volume-title":"Energy-efficient resource allocation and provisioning for in-memory database clusters, IFIP\/IEEE Symp on integrated network and service management (IM)","author":"K Molka","year":"2017","unstructured":"Molka K, Casale G (2017) Energy-efficient resource allocation and provisioning for in-memory database clusters, IFIP\/IEEE Symp on integrated network and service management (IM), pp 19\u201327"},{"key":"363_CR27","first-page":"661","volume-title":"Evolutionary deployment optimization with probabilistic SLAs for service oriented clouds","author":"H Wada","year":"2009","unstructured":"Wada H, Suzuki J, Oba K, Theoretic Q (2009) Evolutionary deployment optimization with probabilistic SLAs for service oriented clouds, pp 661\u2013669 Proc 2009 Congress on Services"},{"key":"363_CR28","first-page":"295","volume-title":"Virtual machine provisioning based on analytical performance and QoS in cloud computing environments","author":"RN Calheiros","year":"2011","unstructured":"Calheiros RN, Ranjan R, Buyya R (2011) Virtual machine provisioning based on analytical performance and QoS in cloud computing environments, pp 295\u2013304 Int. Conf. on Parallel processing (ICPP 2011)"},{"key":"363_CR29","first-page":"84","volume-title":"Energy optimal VM placement in the cloud","author":"Y Wang","year":"2016","unstructured":"Wang Y, Xia Y (2016) Energy optimal VM placement in the cloud, pp 84\u201391 IEEE 9th Int Conf on Cloud Computing"},{"key":"363_CR30","first-page":"1","volume-title":"Value of service based task scheduling for cloud computing systems","author":"C Tunc","year":"2016","unstructured":"Tunc C, Kumbhare N, Akoglu A, Hariri S, Machovec D, Siegel HJ (2016) Value of service based task scheduling for cloud computing systems, pp 1\u201311 Int Conf on Cloud and Autonomic Computing (ICCAC)"},{"key":"363_CR31","doi-asserted-by":"crossref","unstructured":"Chen K-Y, Xu Y, Xi K, Chao HJ (2013) Intelligent virtual machine placement for cost efficiency in geo-distributed cloud systems. IEEE Int Conf Commun:3498\u20133503","DOI":"10.1109\/ICC.2013.6655092"},{"issue":"C","key":"363_CR32","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.jss.2015.01.040","volume":"103","author":"J-P Arcangeli","year":"2015","unstructured":"Arcangeli J-P, Boujbel R, S. (2015) Leriche automatic deployment of distributed software systems. J Syst Softw 103(C):198\u2013218","journal-title":"J Syst Softw"},{"key":"363_CR33","volume-title":"Lightweight robust optimizer for distributed application deployment in multi-clouds, MASc thesis","author":"R Kaur","year":"2015","unstructured":"Kaur R (2015) Lightweight robust optimizer for distributed application deployment in multi-clouds, MASc thesis. Carleton Unversity, Ottawa, Canada"},{"key":"363_CR34","volume-title":"Multi-cloud application deployment, MASc thesis","author":"B Singh","year":"2019","unstructured":"Singh B (2019) Multi-cloud application deployment, MASc thesis. Carleton University, Ottawa, Canada"},{"key":"363_CR35","volume-title":"A study of the k-way graph partitioning problem","author":"B Menegola","year":"2012","unstructured":"Menegola B (2012) A study of the k-way graph partitioning problem. Federal University of Rio Grande do Sul, Rio Grande do Sul"},{"issue":"1","key":"363_CR36","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput 20(1):359\u2013392","journal-title":"SIAM J Sci Comput"},{"issue":"1","key":"363_CR37","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V (1998) Multilevel k-way partitioning scheme for irregular graphs. J Parallel Distributed Comput 48(1):96\u2013129","journal-title":"J Parallel Distributed Comput"},{"key":"363_CR38","unstructured":"Standard Performance Evaluation Corporation, SPECpower_ssj2008 Result File Fields, https:\/\/www.spec.org\/power\/docs\/SPECpower_ssj2008-Result_File_Fields.html. (Accessed 6 Dec 2018)"},{"issue":"2","key":"363_CR39","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TSE.2008.74","volume":"35","author":"G Franks","year":"2009","unstructured":"Franks G, Al-Omari T, Woodside M (2009) Enhanced modeling and solution of layered Queueing networks. IEEE Trans Software Eng 35(2):148\u2013161","journal-title":"IEEE Trans Software Eng"},{"key":"363_CR40","unstructured":"Woodside M, Tutorial Introduction to Layered Modeling of Software Performance, http:\/\/www.sce.carleton.ca\/rads\/lqns\/lqn-documentation\/tutorialh.pdf (Accessed Sept 2021)"},{"key":"363_CR41","volume-title":"Computer performance engineering (EPEW 2015)","author":"F Islam","year":"2015","unstructured":"Islam F, Petriu D, Woodside M (2015) Simplifying layered queuing network models. In: Beltr\u00e1n M, Knottenbelt W, Bradley J (eds) Computer performance engineering (EPEW 2015), vol 9272. Springer LNCS"},{"key":"363_CR42","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.enbuild.2013.04.015","volume":"64","author":"J Yuventi","year":"2013","unstructured":"Yuventi J, Mehdizadeh R (2013) A critical analysis of power usage effectiveness and its use in communicating data center energy consumption. Energy Buildings 64:90\u201394","journal-title":"Energy Buildings"},{"key":"363_CR43","volume-title":"Foundations of software and system performance engineering","author":"AB Bondi","year":"2014","unstructured":"Bondi AB (2014) Foundations of software and system performance engineering. Addison-Wesley"},{"key":"363_CR44","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/j.jnca.2017.07.011","volume":"103","author":"G Han","year":"2018","unstructured":"Han G, Que W, Jia G, Zhang W (2018) Resource-utilization-aware energy efficient server consolidation algorithm for green computing in IIOT. J Netw Comput Appl 103:205\u2013214","journal-title":"J Netw Comput Appl"},{"key":"363_CR45","unstructured":"Franks G, lqngen \u2212 generate layered queueing network models. https:\/\/github.com\/layeredqueuing\/V5 (Accessed 10 Feb 2022)"},{"issue":"2","key":"363_CR46","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.future.2012.07.003","volume":"29","author":"T Verbelen","year":"2013","unstructured":"Verbelen T, Stevens T, De Turck F, Dhoedt B (2013) Graph partitioning algorithms for optimizing software deployment in mobile cloud computing. Futur Gener Comput Syst 29(2):451\u2013459","journal-title":"Futur Gener Comput Syst"}],"container-title":["Journal of Cloud Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-022-00363-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13677-022-00363-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-022-00363-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T11:34:46Z","timestamp":1672832086000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofcloudcomputing.springeropen.com\/articles\/10.1186\/s13677-022-00363-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,3]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["363"],"URL":"https:\/\/doi.org\/10.1186\/s13677-022-00363-w","relation":{},"ISSN":["2192-113X"],"issn-type":[{"value":"2192-113X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,3]]},"assertion":[{"value":"18 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"1"}}