Discovering admissibleWeb services with uncertain QoS

Abstract

Open and dynamic environments lead to inherent uncertainty of Web service QoS (Quality of Service), and the QoS-aware service selection problem can be looked upon as a decision problem under uncertainty. We use an empirical distribution function to describe the uncertainty of scores obtained from historical transactions. We then propose an approach to discovering the admissible set of services including alternative services that are not dominated by any other alternatives according to the expected utility criterion. Stochastic dominance (SD) rules are used to compare two services with uncertain scores regardless of the distribution form of their uncertain scores. By using the properties of SD rules, an algorithm is developed to reduce the number of SD tests, by which the admissible services can be reported progressively. We prove that the proposed algorithm can be run on partitioned or incremental alternative services. Moreover, we achieve some useful theoretical conclusions for correct pruning of unnecessary calculations and comparisons in each SD test, by which the efficiency of the SD tests can be improved. We make a comprehensive experimental study using real datasets to evaluate the effectiveness, efficiency, and scalability of the proposed algorithm.

Keywords

Web services / uncertain QoS / partial preference / empirical distribution function / stochastic dominance / admissible set

References

[1] Papazoglou M, Traverso P, Dustdar S, Leymann F. Service-oriented computing: state of the art and research challenges. Computer, 2007, 40(11): 38-45

[2] Sanati F, Lu J. An ontology for e-government service integration. Computer Systems Science and Engineering, 2012, 27(2): 89-101

[3] Dou W, Lv C, Zhang X, Chen J. A collaborative QoS-aware service evaluation method among multi-users for a shared service. International Journal of Web Services Research, 2012, 9(1): 30-50

[4] Zheng Z, Zhang Y, Lyu M R. Investigating QoS of real-world Web services. IEEE Transactions on Services Computing, 2014, 7(1): 32-39

[5] Candan K S, Li W S, Phan T, Zhou M. Frontiers in information and software as services. In: Proceedings of the 2009 IEEE International Conference on Data Engineering. 2009, 1761-1768

[6] Alrifai M, Skoutas D, Risse T. Selecting skyline services for QoS-based Web service composition. In: Proceedings of the 19th International Conference on World Wide Web. 2010, 11-20

[7] Zeng L, Benatallah B, Ngu AHH, Dumas M, Kalagnanam J, Chang H. QoS-aware middleware for Web services composition. IEEE Transactions on Software Engineering, 2004, 30(5): 311-327

[8] Yu T, Zhang Y, Lin K J. Efficient algorithms for Web services selection with end-to-end QoS constraints. ACM Transactions on the Web, 2007, 1(1): 6

[9] Alrifai M, Risse T. Combining global optimization with local selection for efficient QoS-aware service composition. In: Proceedings of the 18th International Conference on World Wide Web. 2009, 881-890

[10] Hwang S Y, Wang H, Tang J, Srivastava J. A probabilistic approach to modeling and estimating the QoS of Web-services-based workflows. Information Sciences, 2007, 177(23): 5484-5503

[11] Rosario S, Benveniste A, Haar S, Jard C. Probabilistic QoS and soft contracts for transaction-based Web services orchestrations. IEEE Transactions on Service Computing, 2008, 1(4): 187-200

[12] Jurca R, Faltings B, Binder W. Reliable QoS monitoring based on client feedback. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 1003-1012

[13] Barbon F, Traverso P, Pistore M, Trainotti M. Run-time monitoring of instances and classes of Web service compositions. In: Proceedings of the 4th International Conference on Web Services. 2006, 63-71

[14] Porter R B, Gaumnitz J E. Stochastic dominance vs. mean-variance portfolio analysis: an empirical evaluation. American Economic Review, 1972, 62(3): 438-446

[15] Cynthia B L, Allan E S. Precise and realistic utility functions for usercentric performance analysis of schedulers. In: Proceedings of the 16th International Symposium on High Performance Distributed Computing. 2007, 107-116

[16] Arrow K J. Essays in the theory of risk-bearing. North-Holland Publishing Company, 1976

[17] Zheng H, Yang J, Zhao W. QoS probability distribution estimation for Web services and service compositions. In: Proceedings of the IEEE International Conference on Service-Oriented Computing and Applications. 2010, 1-8

[18] Wiesemann W, Hochreiter R, Kuhn D. A stochastic programming approach for QoS-aware service composition. In: Proceedings of the 8th IEEE International Symposium on Cluster Computing and the Grid. 2008, 226-233

[19] Fu X D, Yue K, Zou P, Wang F. Risk-driven Web services selection based on stochastic QoS. ICIC Express Letters, 2011, 5(7): 2269-2274

[20] Klein A, Ishikawa F, Bauer B. A probabilistic approach to service selection with conditional contracts and usage patterns. In: Proceedings of the 7th International Conference on Service Oriented Computing. 2009, 253-268

[21] Schuller D, Lampe U, Eckert J, Steinmetz R, Schulte S. Cost-driven optimization of complex service-based workflows for stochastic QoS parameters. In: Proceedings of the 10th IEEE International Conference on Web Services. 2012, 66-73

[22] Zheng Z, Zhang Y, Lyu M. Distributed QoS evaluation for real-world Web services. In: Proceedi<?Pub Caret?>ngs of the 8th IEEE International Conference on Web Services. 2010, 83-90

[23] Yu Q, Bouguettaya A. Computing service skyline from uncertain QoWS. IEEE Transactions on Services Computing, 2010, 3(1): 16-29

[24] Levy H. Stochastic dominance and expected utility: survey and analysis. Management Science, 1992, 38(4): 555-593

[25] Chakraborty S, Yeh C H. A simulation based comparative study of normalization procedures in multiattribute decision making. In: Proceedings of the 6th Conference on Artificial Intelligence, Knowledge Engineering and Databases. 2007, 102-109

[26] van der Vaart A W. Asymptotic statistics. London: Cambridge University Press, 2000.

[27] Kroll Y, Levy H. Stochastic dominance: areview and some new evidence. Research in Finance, 1980, 2: 163-227

[28] Kuosmanen T. Efficient diversification according to stochastic dominance criteria. Management Science, 2004, 50(10): 1390-1406

[29] Hadar J, Russell W R. Rules for ordering uncertain prospects. American Economic Review, 1969, 59(1): 25-34

[30] Hanoch G, Levy H. The efficiency analysis of choices involving risk. The Review of Economic Studies, 1969, 36(3): 335-346

[31] Whitmore G A. Third-degree stochastic dominance. American Economic Review, 1970, 60(3): 457-459

[32] Bawa V S. Optimal rules for ordering uncertain prospects. Journal of Financial Economics, 1975, 2(1): 95-121

[33] Hu F, Wang G, Feng L. Fast knowledge reduction algorithms based on quick sort, In: Proceedings of the 3rd International Conference on Rough Sets and Knowledge Technology. 2008, 72-79

[34] Haddad J E, Manouvrier M, Rukoz M. TQoS: transactional and QoSaware selection algorithm for automatic Web service composition. IEEE Transactions on Services Computing, 2010, 3(1): 73-85

[35] Lecue F. Optimizing QoS-aware semantic Web service composition. In: Proceedings of the 8th International Semantic Web Conference. 2009, 375-391

[36] Borzsonyi S, Kossmann D, Stocker K. The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering, 2001, 421-430

[37] Yu Q, Bouguettaya A. Efficient service skyline computation for composite service selection. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4): 776-789

[38] Skoutas D, Sacharidis D, Simitsis A, Sellis T. Serving the sky: discovering and selecting semantic Web services through dynamic skyline queries. In: Proceedings of the 2008 IEEE International Conference on Semantic Computing. 2008, 222-229

[39] Skoutas D, Sacharidis D, Simitsis A, Sellis T. Ranking and clustering Web services using multicriteria dominance relationships. IEEE Transactions on Services Computing, 2010, 3(3): 163-177

[40] Rosario S, Benveniste A, Jard C. Flexible probabilistic QoS management of orchestrations. International Journal of Web Services Research, 2010, 7(2): 21-42

[41] Fourneau J M, Mokdad L, Pekergin N. Stochastic bounds for performance evaluation of Web services. Concurrency and Computation: Practice and Experience, 2010, 22(10): 1286-1307

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg