Abstract
QoS attributes are one of the key factors taken into account when selecting services for a composite application. While there are systems for automated service selection based on QoS constraints, most of them are very limited in the preferences the user can state. In this paper we present: a) a simple, yet versatile, language for describing composite applications, b) a rich set of notations for stating complex preferences over the QoS attributes, including checkpoints and invariants, and c) an automatic tool for optimal global QoS-aware service selection based on MiniBrass, a state-of-the-art soft-constraint solver. We provide a running example accompanying the definitions and a preliminary performance analysis showing the practical usefulness of the tools.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Available at https://www.gurobi.com.
- 2.
The interested reader might, however, have a look at the handbook https://www.minizinc.org/doc-latest/en/index.html.
- 3.
- 4.
The interested reader is pointed to [5, 28] for the results associated to the theoretical complexity of the formal framework underlying MiniBrass and to [26, section 5] for an empirical evaluation. In the case of the complexity associated to the use of MiniZinc there is not much to be said about the translation to FlatZinc (i.e., its target language) because most of the computational effort resides in the execution of the solver [20]. Regarding Gurobi; a comprehensive empirical study against the SAS solvers, available at https://www.sas.com, running over the Mittelmann’s benchmark can be found in [12].
- 5.
R squared, denoted \(R^2\), is the coefficient of determination that provides a measure of how well the model fits the data.
References
Arbab, F., Baier, C., Rutten, J., Sirjani, M.: Modeling component connectors in reo by constraint automata: (extended abstract). Electron. Notes Theor. Comput. Sci. 97, 25–46 (2004). https://doi.org/10.1016/j.entcs.2004.04.028
Arbab, F., Santini, F.: Preference and similarity-based behavioral discovery of services. In: ter Beek, M.H., Lohmann, N. (eds.) WS-FM 2012. LNCS, vol. 7843, pp. 118–133. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38230-7_8. ISBN 978-3-642-38230-7
Arbab, F., Santini, F., Bistarelli, S., Pirolandi, D.: Towards a similarity-based web service discovery through soft constraint satisfaction problems. In: Proceedings of the 2nd International Workshop on Semantic Search over the Web, ICPS Proceedings, New York, NY, USA. Association for Computing Machinery (2012). https://doi.org/10.1145/2494068.2494070. ISBN 978-1-4503-2301-7
Baryannis, G.: Service composition. In: Papazoglou, M.P., Pohl, K., Parkin, M., Metzger, A. (eds.) Service Research Challenges and Solutions for the Future Internet. LNCS, vol. 6500, pp. 55–84. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17599-2_3. ISBN 978-3-642-17599-2
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint satisfaction and optimization. J. ACM 44(2), 201–236 (1997). https://doi.org/10.1145/256303.256306. ISSN 0004–5411
Bouguettaya, A., Sheng, Q.Z., Daniel, F. (eds.): Web Services Foundations. Springer, New York (2014). https://doi.org/10.1007/978-1-4614-7518-7. ISBN 978-1-4614-7517-0
De Filippo, A., Lombardi, M., Milano, M.: Integrated offline and online decision making under uncertainty. J. Artif. Int. Res. 70, 77–117 (2021). https://doi.org/10.1613/jair.1.12333. ISSN 1076–9757
Deng, S., Huang, L., Wu, H., Wu, Z.: Constraints-driven service composition in mobile cloud computing. In: 2016 IEEE International Conference on Web Services (ICWS), pp. 228–235 (2016). https://doi.org/10.1109/ICWS.2016.37
Dokter, K., Gadducci, F., Santini, F.: Soft constraint automata with memory. In: de Boer, F., Bonsangue, M., Rutten, J. (eds.) It’s All About Coordination. LNCS, vol. 10865, pp. 70–85. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-90089-6_6. ISBN 978-3-319-90089-6
El Hadad, J., Manouvrier, M., Rukoz, M.: Tqos: transactional and qos-aware selection algorithm for automatic web service composition. IEEE Trans. Serv. Comput. 3(1), 73–85 (2010). https://doi.org/10.1109/TSC.2010.5
Freuder, E.C., Mackworth, A.K.: Constraint satisfaction: an emerging paradigm. In: Handbook of Constraint Programming, vol. 2, 1 edn. (2006). ISBN 978-008-04-6380-3
Helm, W.E., Justkowiak, J.-E.: Extension of Mittelmann’s benchmarks: comparing the solvers of SAS and Gurobi. In: Fink, A., Fügenschuh, A., Geiger, M.J. (eds.) Operations Research Proceedings 2016. ORP, pp. 607–613. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-55702-1_80
Hosobe, H.: Constraint hierarchies as semiring-based csps. In: 2009 21st IEEE International Conference on Tools with Artificial Intelligence, pp. 176–183. IEEE (2009). https://doi.org/10.1109/ICTAI.2009.43
Lecue, F., Mehandjiev, N.: Towards scalability of quality driven semantic web service composition. In: 2009 IEEE International Conference on Web Services, pp. 469–476. IEEE (2009). https://doi.org/10.1109/ICWS.2009.88. ISBN 978-0-7695-3709-2
Martello, S., Toth, P.: Algorithms for knapsack problems. In: Martello, S., Laporte, G., Minoux, M., Ribeiro, C. (eds.) Surveys in Combinatorial Optimization, number 132 in North-Holland Mathematics Studies, North-Holland, pp. 213–257 (1987). https://doi.org/10.1016/S0304-0208(08)73237-7
Menascé, D.A.: Qos issues in web services. IEEE Internet Comput. 6(6), 72–75 (2002). https://doi.org/10.1109/MIC.2002.1067740. ISSN 1941–0131
Meseguer, P., Rossi, F., Schiex, T.: Soft constraints. In: Handbook of Constraint Programming, vol. 9, 1 edn., pp. 281–328 (2006). ISBN 978-008-04-6380-3
Michlmayr, A., Rosenberg, F., Leitner, P., Dustdar, S.: End-to-end support for qos-aware service selection, invocation and mediation in vresco. Technical report, Vienna University of Technology (2009). https://dsg.tuwien.ac.at/Staff/sd/papers/TUV-1841-2009-03.pdf
Moghaddam, M., Davis, J.G.: Service selection in web service composition: a comparative review of existing approaches. In: Bouguettaya, A., Sheng, Q., Daniel, F. (eds.) Web Services Foundations, pp. 321–346. Springer, New York (2014). https://doi.org/10.1007/978-1-4614-7518-7_13
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_38. ISBN 978-3-540-74970-7
Papazoglou, M.P., Traverso, P., Dustdar, S., Leymann, F.: Service-oriented computing: state of the art and research challenges. Computer 40(11), 38–45 (2007). https://doi.org/10.1109/MC.2007.400. ISSN 1558–0814
Rosenberg, F., Celikovic, P., Michlmayr, A., Leitner, P., Dustdar, S.: An end-to-end approach for qos-aware service composition. In: 2009 IEEE International Enterprise Distributed Object Computing Conference, pp. 151–160. IEEE (2009). https://doi.org/10.1109/EDOC.2009.14. ISBN 978-0-7695-3785-6
Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming, 1 edn. Elsevier Science Inc., Amsterdam (2006). ISBN 978-008-04-6380-3
Sakellariou, R., Yarmolenko, V.: On the flexibility of ws-agreement for job submission. In: Proceedings of the 3rd International Workshop on Middleware for Grid Computing, ICPS Proceedings. Association for Computing Machinery (2005). https://doi.org/10.1145/1101499.1101511. ISBN 978-1-59593-269-3
Sargolzaei, M., Santini, F., Arbab, F., Afsarmanesh, H.: A tool for behaviour-based discovery of approximately matching web services. In: Hierons, R.M., Merayo, M.G., Bravetti, M. (eds.) SEFM 2013. LNCS, vol. 8137, pp. 152–166. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40561-7_11. ISBN 978-3-642-40561-7
Schiendorfer, A., Knapp, A., Anders, G., Reif, W.: MiniBrass: soft constraints for MiniZinc. Constraints 23(4), 403–450 (2018). https://doi.org/10.1007/s10601-018-9289-2
Schiendorfer, A., Knapp, A., Steghöfer, J.-P., Anders, G., Siefert, F., Reif, W.: Partial valuation structures for qualitative soft constraints. In: De Nicola, R., Hennicker, R. (eds.) Software, Services, and Systems. LNCS, vol. 8950, pp. 115–133. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15545-6_10. ISBN 978-3-319-15545-6
Schiex, T., Fargier, H., Verfaillie, G.: Valued constraint satisfaction problems: hard and easy problems. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 1995, Montréal, Québec, Canada, 20–25 August 1995, vol. 2, pp. 631–639. Morgan Kaufmann (1995)
Wei, L., Junzhou, L., Bo, L., Xiao, Z., Jiuxin, C.: Multi-agent based QoS-aware service composition. In: 2010 IEEE International Conference on Systems, Man and Cybernetics, pp. 3125–3132. IEEE (2010). https://doi.org/10.1109/ICSMC.2010.5641725
Tao, Yu., Zhang, Y., Lin, K.-J.: Efficient algorithms for web services selection with end-to-end qos constraints. ACM Trans. Web 1(1), 6-es (2007). https://doi.org/10.1145/1232722.1232728. ISSN 1559–1131
Zemni, M.A., Benbernou, S., Carro, M.: A soft constraint-based approach to QoS-aware service selection. In: Maglio, P.P., Weske, M., Yang, J., Fantinato, M. (eds.) ICSOC 2010. LNCS, vol. 6470, pp. 596–602. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17358-5_44. ISBN 978-3-642-17358-5
Zheng, X., Luo, J.Z., Song, A.B.: Ant colony system based algorithm for qos-aware web service selection. In: Kowalczyk, R. (ed.) Grid Service Engineering and Management “The 4th International Conference on Grid Service Engineering and Management” GSEM 2007, number 117 in Lecture Notes in Informatics, Bonn, Germany, pp. 39–50. Gesellschaft für Informatik e. V. (2007). https://dl.gi.de/server/api/core/bitstreams/4cefa9ab-94e1-4d82-b2ea-4d8ea1041838/content. ISBN 978-3-88579-211-6
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 Springer Nature Switzerland AG
About this paper
Cite this paper
Keis, E., Pombo, C.G.L., Suñé, A.E.M., Knapp, A. (2023). Automated QoS-Aware Service Selection Based on Soft Constraints. In: Madeira, A., Martins, M.A. (eds) Recent Trends in Algebraic Development Techniques. WADT 2022. Lecture Notes in Computer Science, vol 13710. Springer, Cham. https://doi.org/10.1007/978-3-031-43345-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-43345-0_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43344-3
Online ISBN: 978-3-031-43345-0
eBook Packages: Computer ScienceComputer Science (R0)