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

• Autorzy: Musial Jędrzej , Kieffer Emmanuel , Guzek Mateusz , Danoy Gregoire , Wagle Shyam S. , Bouvry Pascal , Blazewicz Jacek

Identyfikatory

DOI

10.2478/fcds-2019-0020

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

applied operations research; cloud computing; cloud brokering; optimization; algorithms; computational complexity

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2019
• Tom: Vol. 44, No. 4
• Strony: 407--426
• Opis fizyczny: Bibliogr. 46 poz., rys., tab.

Twórcy

autor

Musial Jędrzej

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

autor

Kieffer Emmanuel

• Computer Science and Communications Research Unit (CSC), University of Luxembourg, 6 avenue de la Fonte, L-4364 Esch-surAlzette, Luxembourg

autor

Guzek Mateusz

• Computer Science and Communications Research Unit (CSC), University of Luxembourg, 6 avenue de la Fonte, L-4364 Esch-surAlzette, Luxembourg

autor

Danoy Gregoire

• Computer Science and Communications Research Unit (CSC), University of Luxembourg, 6 avenue de la Fonte, L-4364 Esch-surAlzette, Luxembourg

autor

Wagle Shyam S.

• Computer Science and Communications Research Unit (CSC), University of Luxembourg, 6 avenue de la Fonte, L-4364 Esch-surAlzette, Luxembourg

autor

Bouvry Pascal

• Computer Science and Communications Research Unit (CSC), University of Luxembourg, 6 avenue de la Fonte, L-4364 Esch-surAlzette, Luxembourg

autor

Blazewicz Jacek

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

Bibliografia

• [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.
• [2] Aazam M. and Huh E.-N. Cloud broker service-oriented resource management model. Trans. Emerg. Telecommun. Technol., 28(2):e2937, 2017.
• [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.
• [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.
• [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.
• [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.
• [7] Blazewicz J., Kovalyov M. ., Musial J., Urbanski A.P., and Wojciechowski A. Internet shopping optimization problem. Int. J. Appl. Math. Comput. Sci., 20(2):385-390, 2010.
• [8] Blazewicz J. and Musial J. E-Commerce Evaluation - Multi-Item Internet Shop¬ping. 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.
• [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] 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.
• [11] Ehrgott M. Multicriteria Optimization. Springer-Verlag, Berlin Heidelberg, 2005.
• [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.
• [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.
• [14] Gutierrez-Garcia J.O. and Sim K.M. Agent-based Cloud service composition. Appl. Intell., 38(3):436-464, 2012.
• [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.
• [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.
• [17] International Telecommunication Union. Information technology — Cloud computing — Overview and vocabulary. Technical Report ITU-T Y.3500, International Organization for Standardization, 2014.
• [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.
• [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.
• [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.
• [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.
• [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.
• [23] Ludwig A. and Schmid S. Distributed Cloud Market: Who Benefits from Specification Flexibilities? SIGMETRICS Perform. Eval. Rev., 43(3):38-41, Nov. 2015.
• [24] Lund C. and Yannakakis M. On the hardness of approximating minimization problems. J ACM, 41(5):960-981, Sept. 1994.
• [25] Mell P. and Grance T. The NIST definition of cloud computing. Natl. Inst. Stand. Technol., 53(6):50, 2009.
• [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.
• [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.
• [28] Musial J. and Lopez-Loces M.C. Trustworthy Online Shopping with Price Impact. Found. Comput. Decis. Sci., 42(2):121-136, 2017.
• [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.
• [30] Nesmachnow S., Iturriaga S., and Dorronsoro B. Efficient Heuristics for Profit Optimization of Virtual Cloud Brokers. IEEE Comput. Intell. Mag., 10(1):33-43, Feb 2015.
• [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.
• [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.
• [33] Rajavel R. and Thangarathanam M. Adaptive Probabilistic Behavioural Learning System for the effective behavioural decision in cloud trading negotiation market. Future Gener. Comput. Syst., 58:29-41, 2016.
• [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.
• [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.
• [36] Shawish A. and Salama M. Cloud Computing: Paradigms and Technologies, pages 39-67. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014.
• [37] Sim K.M. Agent-Based Cloud Computing. IEEE Trans. Serv. Comput., 5(4):564-577, Fourth 2012.
• [38] Somasundaram T.S. and Govindarajan K. CLOUDRB: A framework for schedul- ing and managing High-Performance Computing (HPC) applications in science cloud. Future Gener. Comput. Syst., 34:47-65, 2014.
• [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.
• [40] Varrette S., Bouvry P., Cartiaux H., and Georgatos F. Management of an aca- demic 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.
• [41] Visee 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.
• [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.
• [43] Wojciechowski A. and Musial J. A customer assistance system: Optimizing basket cost. Found. Comput. Decis. Sci., 34(1):59-69, 2009.
• [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.
• [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.
• [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.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).