1. bookVolume 44 (2019): Issue 4 (December 2019)
Journal Details
First Published
24 Oct 2012
Publication timeframe
4 times per year
access type Open Access

Cloud Brokering with Bundles: Multi-objective Optimization of Services Selection

Published Online: 25 Nov 2019
Volume & Issue: Volume 44 (2019) - Issue 4 (December 2019)
Page range: 407 - 426
Received: 28 Feb 2019
Accepted: 21 Aug 2019
Journal Details
First Published
24 Oct 2012
Publication timeframe
4 times per year

Cloud computing has become one of the major computing paradigms. Not only the number of offered cloud services has grown exponentially but also many different providers compete and propose very similar services. This situation should eventually be beneficial for the customers, but considering that these services slightly differ functionally and non-functionally -wise (e.g., performance, reliability, security), consumers may be confused and unable to make an optimal choice. The emergence of cloud service brokers addresses these issues. A broker gathers information about services from providers and about the needs and requirements of the customers, with the final goal of finding the best match.

In this paper, we formalize and study a novel problem that arises in the area of cloud brokering. In its simplest form, brokering is a trivial assignment problem, but in more complex and realistic cases this does not longer hold. The novelty of the presented problem lies in considering services which can be sold in bundles. Bundling is a common business practice, in which a set of services is sold together for the lower price than the sum of services’ prices that are included in it. This work introduces a multi-criteria optimization problem which could help customers to determine the best IT solutions according to several criteria. The Cloud Brokering with Bundles (CBB) models the different IT packages (or bundles) found on the market while minimizing (maximizing) different criteria. A proof of complexity is given for the single-objective case and experiments have been conducted with a special case of two criteria: the first one being the cost and the second is artificially generated. We also designed and developed a benchmark generator, which is based on real data gathered from 19 cloud providers. The problem is solved using an exact optimizer relying on a dichotomic search method. The results show that the dichotomic search can be successfully applied for small instances corresponding to typical cloud-brokering use cases and returns results in terms of seconds. For larger problem instances, solving times are not prohibitive, and solutions could be obtained for large, corporate clients in terms of minutes.


[1] Aazam M., Huh E., St-Hilaire M., Lung C., and Lambadaris I. Cloud Customer’s Historical Record Based Resource Pricing. IEEE Trans. Parallel Distrib. Syst., 27(7):1929–1940, 2015.10.1109/TPDS.2015.2473850Search in Google Scholar

[2] Aazam M. and Huh E.-N. Cloud broker service-oriented resource management model. Trans. Emerg. Telecommun. Technol., 28(2):e2937, 2017.10.1002/ett.2937Search in Google Scholar

[3] Armbrust M., Fox A., Griffith R., Joseph A., Katz R., Konwinski A., Lee G., Patterson D., Rabkin A., Stoica I., and Zaharia M. A view of cloud computing. Commun. ACM, 53(4):50–58, 2010.10.1145/1721654.1721672Search in Google Scholar

[4] Blazewicz J., Bouvry P., Kovalyov M. Y., and Musial J. Erratum to: Internet shopping with price-sensitive discounts. 4OR-Q J Oper Res, 12(4):403–406, 2014.Search in Google Scholar

[5] Blazewicz J., Bouvry P., Kovalyov M. Y., and Musial J. Internet shopping with price sensitive discounts. 4OR-Q J Oper Res, 12(1):35–48, 2014.10.1007/s10288-013-0230-7Search in Google Scholar

[6] Blazewicz J., Cheriere N., Dutot P.-F., Musial J., and Trystram D. Novel dual discounting functions for the Internet shopping optimization problem: new algorithms. J. Sched., 19(3):245–255, 2016.Search in Google Scholar

[7] Blazewicz J., Kovalyov M. Y., Musial J., Urbanski A. P., and Wojciechowski A. Internet shopping optimization problem. Int. J. Appl. Math. Comput. Sci., 20(2):385–390, 2010.10.2478/v10006-010-0028-0Search in Google Scholar

[8] Blazewicz J. and Musial J. E-Commerce Evaluation – Multi-Item Internet Shopping. Optimization and Heuristic Algorithms. In Hu B., Morasch K., Pickl S., and Siegle M., editors, Operations Research Proceedings 2010: Selected Papers of the Annual International Conference of the German Operations Research Society, pages 149–154. Springer, Berlin, Heidelberg, 2011.10.1007/978-3-642-20009-0_24Search in Google Scholar

[9] Calheiros R., Ranjan R., and Buyya R. Virtual Machine Provisioning Based on Analytical Performance and QoS in Cloud Computing Environments. In Parallel Processing (ICPP), 2011 International Conference on, pages 295–304, Sept 2011.10.1109/ICPP.2011.17Search in Google Scholar

[10] Columbus L. Roundup Of Cloud Computing Forecasts And Market Estimates, 2016. www.forbes.com/sites/louiscolumbus/2016/03/13/roundup-of-cloud-computing-forecasts-and-market-estimates-2016, 2016. Accessed: 2016-06-16.Search in Google Scholar

[11] Ehrgott M. Multicriteria Optimization. Springer-Verlag, Berlin Heidelberg, 2005.Search in Google Scholar

[12] Garey M. R. and Johnson D. S. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.Search in Google Scholar

[13] Guan Z. and Melodia T. The Value of Cooperation: Minimizing User Costs in Multi-broker Mobile Cloud Computing Networks. IEEE Trans. Cloud Comput., PP(99):1–1, 2015.Search in Google Scholar

[14] Gutierrez-Garcia J. O. and Sim K. M. Agent-based Cloud service composition. Appl. Intell., 38(3):436–464, 2012.10.1007/s10489-012-0380-xSearch in Google Scholar

[15] Guzek M., Bouvry P., and Talbi E.-G. A Survey of Evolutionary Computation for Resource Management of Processing in Cloud Computing [Review Article]. IEEE Comput. Intell. Mag., 10(2):53–67, May 2015.10.1109/MCI.2015.2405351Search in Google Scholar

[16] Guzek M., Gniewek A., Bouvry P., Musial J., and Blazewicz J. Cloud Brokering: Current Practices and Upcoming Challenges. IEEE Cloud Comput., 2(2):40–47, Mar 2015.10.1109/MCC.2015.32Search in Google Scholar

[17] International Telecommunication Union. Information technology — Cloud computing — Overview and vocabulary. Technical Report ITU-T Y.3500, International Organization for Standardization, 2014.Search in Google Scholar

[18] Karp R. M. Reducibility among Combinatorial Problems. In Miller R. E., Thatcher J. W., and Bohlinger J. D., editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103. Springer US, 1972.10.1007/978-1-4684-2001-2_9Search in Google Scholar

[19] Kim S.-H., Kang D.-K., Kim W.-J., Chen M., and Youn C.-H. A Science Gateway Cloud With Cost-Adaptive VM Management for Computational Science and Applications. IEEE Syst. J., 11(1):173–185, 2016.10.1109/JSYST.2015.2501750Search in Google Scholar

[20] Lopez-Loces M. C., Musial J., Pecero J. E., Fraire-Huacuja H. J., Blazewicz J., and Bouvry P. Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs. Int. J. Appl. Math. Comput. Sci., 26(2):391–406, 2016.10.1515/amcs-2016-0028Search in Google Scholar

[21] Lucas-Simarro J. L., Moreno-Vozmediano R., Montero R. S., and Llorente I. M. Scheduling strategies for optimal service deployment across multiple clouds. Future Gener. Comput. Syst., 29(6):1431–1441, 2013.10.1016/j.future.2012.01.007Search in Google Scholar

[22] Lucas-Simarro J. L., Moreno-Vozmediano R., Montero R. S., and Llorente I. M. Cost optimization of virtual infrastructures in dynamic multi-cloud scenarios. Concurr. Comput.: Pract. Exp., 27(9):2260–2277, 2015.Search in Google Scholar

[23] Ludwig A. and Schmid S. Distributed Cloud Market: Who Benefits from Specification Flexibilities? SIGMETRICS Perform. Eval. Rev., 43(3):38–41, Nov. 2015.10.1145/2847220.2847230Search in Google Scholar

[24] Lund C. and Yannakakis M. On the hardness of approximating minimization problems. J ACM, 41(5):960–981, Sept. 1994.10.1145/185675.306789Search in Google Scholar

[25] Mell P. and Grance T. The NIST definition of cloud computing. Natl. Inst. Stand. Technol., 53(6):50, 2009.Search in Google Scholar

[26] Moens H., Truyen E., Walraven S., Joosen W., Dhoedt B., and De Turck F. Cost-Effective Feature Placement of Customizable Multi-Tenant Applications in the Cloud. J. Netw. Syst. Manag., 22(4):517–558, 2013.10.1007/s10922-013-9265-5Search in Google Scholar

[27] Moreno-Vozmediano R., Montero R. S., and Llorente I. M. IaaS Cloud Architecture: From Virtualized Datacenters to Federated Cloud Infrastructures. IEEE Comput., 45(12):65–72, 2012.Search in Google Scholar

[28] Musial J. and Lopez-Loces M. C. Trustworthy Online Shopping with Price Impact. Found. Comput. Decis. Sci., 42(2):121–136, 2017.10.1515/fcds-2017-0005Search in Google Scholar

[29] Musial J., Pecero J. E., Lopez-Loces M. C., Fraire-Huacuja H. J., Bouvry P., and Blazewicz J. Algorithms solving the Internet shopping optimization problem with price discounts. Bull. Pol. Ac. Sci.: Tech. Sci., 64(3):505–516, 2016.Search in Google Scholar

[30] Nesmachnow S., Iturriaga S., and Dorronsoro B. Effcient Heuristics for Profit Optimization of Virtual Cloud Brokers. IEEE Comput. Intell. Mag., 10(1):33–43, Feb 2015.10.1109/MCI.2014.2369893Search in Google Scholar

[31] Nir M., Matrawy A., and St-Hilaire M. Economic and Energy Considerations for Resource Augmentation in Mobile Cloud Computing. IEEE Trans. Cloud Comput., PP(99):1–1, 2015.10.1109/TCC.2015.2469665Search in Google Scholar

[32] Prasad G. V., Prasad A. S., and Rao S. A combinatorial auction mechanism for multiple resource procurement in cloud computing. IEEE Transactions on Cloud Computing, 6(4):904–914, 2018.10.1109/TCC.2016.2541150Search in Google Scholar

[33] Rajavel R. and Thangarathanam M. Adaptive Probabilistic Behavioural Learning System for the e ective behavioural decision in cloud trading negotiation market. Future Gener. Comput. Syst., 58:29–41, 2016.10.1016/j.future.2015.12.007Search in Google Scholar

[34] Samaan N. A Novel Economic Sharing Model in a Federation of Selfish Cloud Providers. IEEE Trans. Parallel Distrib. Syst., 25(1):12–21, Jan 2014.10.1109/TPDS.2013.23Search in Google Scholar

[35] Sawik B. Selected Multiobjective Methods for Multiperiod Portfolio Optimization by Mixed Integer Programming. In Lawrence K. D. and Kleinman G., editors, Applications in Multicriteria Decision Making, Data Envelopment Analysis, and Finance, volume 14 of Applications of Management Science, pages 3–34, Bingley, UK, 2010. Emerald Group Publishing Limited.10.1108/S0276-8976(2010)0000014004Search in Google Scholar

[36] Shawish A. and Salama M. Cloud Computing: Paradigms and Technologies, pages 39–67. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014.10.1007/978-3-642-35016-0_2Search in Google Scholar

[37] Sim K. M. Agent-Based Cloud Computing. IEEE Trans. Serv. Comput., 5(4):564–577, Fourth 2012.10.1109/TSC.2011.52Search in Google Scholar

[38] Somasundaram T. S. and Govindarajan K. CLOUDRB: A framework for scheduling and managing High-Performance Computing (HPC) applications in science cloud. Future Gener. Comput. Syst., 34:47–65, 2014.Search in Google Scholar

[39] 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 Gener. Comput. Syst., 28(2):358–367, 2012.10.1016/j.future.2011.07.003Search in Google Scholar

[40] Varrette S., Bouvry P., Cartiaux H., and Georgatos F. Management of an academic HPC cluster: The UL experience. In Proc. of the 2014 Intl. Conf. on High Performance Computing & Simulation (HPCS 2014), pages 959–967, Bologna, Italy, July 2014.10.1109/HPCSim.2014.6903792Search in Google Scholar

[41] Visée M., Teghem J., Pirlot M., and Ulungu E. Two-phases Method and Branch and Bound Procedures to Solve the Bi–objective Knapsack Problem. J. Glob. Optim., 12(2):139–155, 1998.10.1023/A:1008258310679Search in Google Scholar

[42] Wang W., Niu D., Liang B., and Li B. Dynamic Cloud Instance Acquisition via IaaS Cloud Brokerage. IEEE Trans. Parallel Distrib. Syst., 26(6):1580–1593, June 2015.10.1109/TPDS.2014.2326409Search in Google Scholar

[43] Wojciechowski A. and Musial J. A customer assistance system: Optimizing basket cost. Found. Comput. Decis. Sci., 34(1):59–69, 2009.Search in Google Scholar

[44] Wojciechowski A. and Musial J. Towards Optimal Multi-item Shopping Basket Management: Heuristic Approach. In Meersman R., Dillon T., and Herrero P., editors, On the Move to Meaningful Internet Systems: OTM 2010 Workshops, volume 6428 of Lecture Notes in Computer Science, pages 349–357, Berlin, 2010. Springer-Verlag.Search in Google Scholar

[45] Zhang R., Wu K., Li M., and Wang J. Online Resource Scheduling Under Concave Pricing for Cloud Computing. IEEE Trans. Parallel Distrib. Syst., 27(4):1131–1145, 2016.10.1109/TPDS.2015.2432799Search in Google Scholar

[46] Zhou A., Sun Q., Sun L., Li J., and Yang F. Maximizing the profits of cloud service providers via dynamic virtual resource renting approach. EURASIP J. Wirel. Commun. Netw., 2015(1):1–12, 2015.10.1186/s13638-015-0256-ySearch in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo