Flexible provisioning of web service workflows

ABSTRACT

Web services promise to revolutionize the way computational resources and business processes are offered and invoked in open, distributed systems, such as the Internet. These services are described using machine-readable metadata, which enables consumer applications to automatically discover and provision suitable services for their workflows at run-time. However, current approaches have typically assumed service descriptions are accurate and deterministic, and so have neglected to account for the fact that services in these open systems are inherently unreliable and uncertain. Specifically, network failures, software bugs and competition for services may regularly lead to execution delays or even service failures. To address this problem, the process of provisioning services needs to be performed in a more flexible manner than has so far been considered, in order to proactively deal with failures and to recover workflows that have partially failed. To this end, we devise and present a heuristic strategy that varies the provisioning of services according to their predicted performance. Using simulation, we then benchmark our algorithm and show that it leads to a 700% improvement in average utility, while successfully completing up to eight times as many workflows as approaches that do not consider service failures.

REFERENCES

• 1: Rohit Aggarwal , Kunal Verma , John Miller , William Milnor, Constraint Driven Web Service Composition in METEOR-S, Proceedings of the 2004 IEEE International Conference on Services Computing, p.23-30, September 15-18, 2004
• 2: Aghdaie, N. and Tamir, Y. 2003. Fast transparent failover for reliable web service. In Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS). 757--762.
• 3: Akkiraju, R., Verma, K., Goodwin, R., Doshi, P., and Lee, J. 2004. Executing abstract web process flows. In Proceedings of the ICAPS Workshop on Planning and Scheduling for Web and Grid Services. 9--15.
• 4: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 5: Raghu Arunachalam , Norman Sadeh, The 2003 Supply Chain Management Trading Agent Competition, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands [doi>10.1145/1052220.1052235]
• 6: Baccelli, F., Jean-Marie, A., and Liu, Z. 1993. A survey on solution methods for task graph models. In Arbeitsberichte der IMMD, N. Götz, U. Herzog, and M. Rettelbach, Eds. Vol. 26 (14). Universität Erlangen-Nürnberg, Erlangen, Chapter Second QMIPS Workshop, 163--183.
• 7: Boualem Benatallah , Mohand-Said Hacid , Alain Leger , Christophe Rey , Farouk Toumani, On automating Web services discovery, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.1, p.84-96, March 2005 [doi>10.1007/s00778-003-0117-x]
• 8: Jean-Chrysotome Bolot, End-to-end packet delay and loss behavior in the internet, Conference proceedings on Communications architectures, protocols and applications, p.289-298, September 13-17, 1993, San Francisco, California, United States
• 9: Buyya, R., Abramson, D., and Venugopal, S. 2005. The grid economy. Proc. IEEE 93, 3, 698--714.
• 10: Tom Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence, v.69 n.1-2, p.165-204, Sept. 1994 [doi>10.1016/0004-3702(94)90081-7]
• 11: Gerardo Canfora , Massimiliano Di Penta , Raffaele Esposito , Maria Luisa Villani, QoS-Aware Replanning of Composite Web Services, Proceedings of the IEEE International Conference on Web Services, p.121-129, July 11-15, 2005 [doi>10.1109/ICWS.2005.96]
• 12: Fabio Casati , Stefano Ceri , Stefano Paraboschi , Guiseppe Pozzi, Specification and implementation of exceptions in workflow management systems, ACM Transactions on Database Systems (TODS), v.24 n.3, p.405-451, Sept. 1999 [doi>10.1145/328939.328996]
• 13: Paul R. Cohen, Empirical methods for artificial intelligence, MIT Press, Cambridge, MA, 1995
• 14: John Collins , Corey Bilot , Maria Gini , Bamshad Mobasher, Decision Processes in Agent-Based Automated Contracting, IEEE Internet Computing, v.5 n.2, p.61-72, March 2001 [doi>10.1109/4236.914649]
• 15: Flavin Cristian, Understanding fault-tolerant distributed systems, Communications of the ACM, v.34 n.2, p.56-78, Feb. 1991 [doi>10.1145/102792.102801]
• 16: Francisco Curbera , Matthew Duftler , Rania Khalaf , William Nagy , Nirmal Mukhi , Sanjiva Weerawarana, Unraveling the Web Services Web: An Introduction to SOAP, WSDL, and UDDI, IEEE Internet Computing, v.6 n.2, p.86-93, March 2002 [doi>10.1109/4236.991449]
• 17: Francisco Curbera , Rania Khalaf , Nirmal Mukhi , Stefan Tai , Sanjiva Weerawarana, The next step in Web services, Communications of the ACM, v.46 n.10, October 2003 [doi>10.1145/944217.944234]
• 18: A. Dan , D. Davis , R. Kearney , A. Keller , R. King , D. Kuebler , H. Ludwig , M. Polan , M. Spreitzer , A. Youssef, Web services on demand: WSLA-driven automated management, IBM Systems Journal, v.43 n.1, p.136-158, January 2004
• 19: Deelman, E., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., Vahi, K., Blackburn, K., Lazzarini, A., Arbree, A., Cavanaugh, R., and Koranda, S. 2003. Mapping abstract complex workflows onto grid environments. J. Grid Comput. 1, 1, 25--39.
• 20: DeGroot, M. H. and Shervish, M. J. 2002. Probability and Statistics, 3rd ed. Addison-Wesley, Reading, MA.
• 21: Dodin, B. 1985. Bounding the project completion time distribution in PERT networks. Oper. Res. 33, 4, 862--881.
• 22: Eder, J. and Liebhart, W. 1995. The workflow activity model WAMO. In Proceedings of the 3rd International Conference on Cooperative Information Systems. 87--98.
• 23: Abdelkarim Erradi , Piyush Maheshwari , Vladimir Tosic, Recovery Policies for Enhancing Web Services Reliability, Proceedings of the IEEE International Conference on Web Services, p.189-196, September 18-22, 2006 [doi>10.1109/ICWS.2006.110]
• 24: Ewing, B., Hillier, L., Wendl, M. C., and Green, P. 1998. Base-calling of automated sequencer traces using phred. I. Accuracy assessment. Genome Res. 8, 3, 175--185.
• 25: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 26: Friese, T., Müller, J. P., and Freisleben, B. 2005. Self-healing execution of business processes based on a peer-to-peer service architecture. In Proceedings of the 18th International Conference on Architecture of Computing Systems (ARCS '05), System Aspects in Organic and Pervasive Computing. Lecture Notes in Computer Science, vol. 3432. Springer-Verlag, Berlin, Germany. 108--123.
• 27: Hector Garcia-Molina , Kenneth Salem, Sagas, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.249-259, May 27-29, 1987, San Francisco, California, United States
• 28: Felix C. Gärtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999 [doi>10.1145/311531.311532]
• 29: Dimitrios Georgakopoulos , Mark Hornick , Amit Sheth, An overview of workflow management: from process modeling to workflow automation infrastructure, Distributed and Parallel Databases, v.3 n.2, p.119-153, April 1995 [doi>10.1007/BF01277643]
• 30: David B. Ingham , Fabio Panzieri , Santosh K. Shrivastava, Constructing Dependable Web Services, Advances in Distributed Systems, Advanced Distributed Computing: From Algorithms to Systems, p.277-294, January 1999
• 31: David E. Irwin , Laura E. Grit , Jeffrey S. Chase, Balancing Risk and Reward in a Market-Based Task Service, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing, p.160-169, June 04-06, 2004 [doi>10.1109/HPDC.2004.5]
• 32: Michael C. Jaeger , Hendrik Ladner, Improving the QoS of WS Compositions Based on Redundant Services, Proceedings of the International Conference on Next Generation Web Services Practices, p.189, August 22-26, 2005 [doi>10.1109/NWESP.2005.47]
• 33: Jaeger, M. C. and Mühl, G. 2007. QoS-based selection of services: The implementation of a genetic algorithm. In Proceedings of the KiVS 2007 Workshop: Service-Oriented Architectures und Service-Oriented Computing (SOA/SOC). 359--370.
• 34: Nicholas R. Jennings, An agent-based approach for building complex software systems, Communications of the ACM, v.44 n.4, p.35-41, April 2001 [doi>10.1145/367211.367250]
• 35: Jennings, N. R., Faratin, P., Lomuscio, A. R., Parsons, S., Sierra, C., and Wooldridge, M. 2001. Automated negotiation: Prospects, methods and challenges. Group Decis. Negot. 10, 2, 199--215.
• 36: Jennings, N. R., Faratin, P., Norman, T. J., O'Brien, P., and Odgers, B. 2000. Autonomous agents for business process management. Appl. Artif. Intell. 14, 2, 145--189.
• 37: Klusch, M., Gerber, A., and Schmidt, M. 2005. Semantic web service composition planning with OWLS-XPlan. In Proceedings of the 1st Int. AAAI Fall Symposium on Agents and the Semantic Web. 55--62.
• 38: Krys Kochut , Jonathan Arnold , Amit Sheth , John Miller , Eileen Kraemer , Budak Arpinar , Jorge Cardoso, IntelliGEN: A Distributed Workflow System for Discovering Protein-Protein Interactions, Distributed and Parallel Databases, v.13 n.1, p.43-72, January 2003 [doi>10.1023/A:1021565722755]
• 39: Wei Li , Jiang He , Qingkai Ma , I-Ling Yen , Farokh Bastani , Raymond Paul, A Framework to Support Survivable Web Services, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.93.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.27]
• 40: D. Long , A. Muir , R. Golding, A longitudinal survey of Internet host reliability, Proceedings of the 14TH Symposium on Reliable Distributed Systems, p.2, September 13-15, 1995
• 41: Malcolm, D. G., Roseboom, J. H., Clark, C. E., and Fazar, W. 1959. Application of a technique for research and development program evaluation. Oper. Res. 7, 5, 646--669.
• 42: Mandell, D. and McIlraith, S. 2003. Adapting BPEL4WS for the semantic web: The bottom-up approach to web service interoperation. In Proceedings of the 2nd International Semantic Web Conference. Lecture Notes in Computer Science, vol. 2870, Springer-Verlag, Berlin, Germany. 227--241.
• 43: Martin, D., Paolucci, M., McIlraith, S., Burstein, M., McDermott, D., McGuinness, D., Parsia, B., Payne, T., Sabou, M., Solanki, M., Srinivasan, N., and Sycara, K. 2004. Bringing semantics to web services: The OWL-S approach. In Proceedings of the 1st International Workshop on Semantic Web Services and Web Process Composition (SWSWPC 2004). Lecture Notes in Computer Science, vol. 3387, Springer-Verlag, Berlin, Germany. 26--42.
• 44: E. Michael Maximilien , Munindar P. Singh, A Framework and Ontology for Dynamic Web Services Selection, IEEE Internet Computing, v.8 n.5, p.84-93, September 2004 [doi>10.1109/MIC.2004.27]
• 45: E. Michael Maximilien , Munindar P. Singh, Toward autonomic web services trust and selection, Proceedings of the 2nd international conference on Service oriented computing, November 15-19, 2004, New York, NY, USA [doi>10.1145/1035167.1035198]
• 46: McDermott, D. 2002. Estimated-regression planning for interactions with web services. In Proceedings of the 6th International Conference on AI Planning and Scheduling (AIPS'02). 204--211.
• 47: McGuinness, D. and van Harmelen, F. 2004. OWL web ontology language overview. Recommendation, W3C. February. (http://www.w3.org/TR/2004/REC-owl-features-20040210/).
• 48: McIlraith, S. A. and Son, T. C. 2002. Adapting golog for composition of semantic web services. In Proceedings of the 8th International Conference on Knowledge Representation and Reasoning (KR2002). 482--493.
• 49: Sheila A. McIlraith , Tran Cao Son , Honglei Zeng, Semantic Web Services, IEEE Intelligent Systems, v.16 n.2, p.46-53, March 2001 [doi>10.1109/5254.920599]
• 50: B. Medjahed , B. Benatallah , A. Bouguettaya , A. H. H. Ngu , A. K. Elmagarmid, Business-to-business interactions: issues and enabling technologies, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.1, p.59-85, May 2003 [doi>10.1007/s00778-003-0087-z]
• 51: Daniel A. Menascé, QoS Issues in Web Services, IEEE Internet Computing, v.6 n.6, p.72-75, November 2002 [doi>10.1109/MIC.2002.1067740]
• 52: Michael G. Merideth , Arun Iyengar , Thomas Mikalsen , Stefan Tai , Isabelle Rouvellou , Priya Narasimhan, Thema: Byzantine-Fault-Tolerant Middleware forWeb-Service Applications, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.131-142, October 26-28, 2005 [doi>10.1109/RELDIS.2005.28]
• 53: Zbigniew Michalewicz , David B. Fogel, How to Solve It: Modern Heuristics, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 54: Nikola Milanovic , Miroslaw Malek, Current Solutions for Web Service Composition, IEEE Internet Computing, v.8 n.6, p.51-59, November 2004 [doi>10.1109/MIC.2004.58]
• 55: Keung-Chi Ng , Bruce Abramson, Uncertainty Management in Expert Systems, IEEE Expert: Intelligent Systems and Their Applications, v.5 n.2, p.29-48, April 1990 [doi>10.1109/64.53180]
• 56: Victor F. Nicola , Ambuj Goyal, Modeling of Correlated Failures and Community Error Recovery in Multiversion Software, IEEE Transactions on Software Engineering, v.16 n.3, p.350-359, March 1990 [doi>10.1109/32.48942]
• 57: Norman, T. J., Preece, A., Chalmers, S., Jennings, N. R., Luck, M., Dang, V. D., Nguyen, T. D., Deora, V., Shao, J., Gray, A. W., and Fiddian, N. J. 2004. Agent-based formation of virtual organisations. Knowl.-Based Syst. 17, 2--4, 103--111.
• 58: O'Brien, A., Newhouse, S., and Darlington, J. 2004. Mapping of scientific workflow within the e-protein project to distributed resources. In Proceedings of the UK E-Science All Hands Meeting (AHM 2004). 404--409.
• 59: Tom Oinn , Mark Greenwood , Matthew Addis , M. Nedim Alpdemir , Justin Ferris , Kevin Glover , Carole Goble , Antoon Goderis , Duncan Hull , Darren Marvin , Peter Li , Phillip Lord , Matthew R. Pocock , Martin Senger , Robert Stevens , Anil Wipat , Chris Wroe, Taverna: lessons in creating a workflow environment for the life sciences: Research Articles, Concurrency and Computation: Practice & Experience, v.18 n.10, p.1067-1100, August 2006 [doi>10.1002/cpe.v18:10]
• 60: Massimo Paolucci , Takahiro Kawamura , Terry R. Payne , Katia P. Sycara, Semantic Matching of Web Services Capabilities, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.333-347, June 09-12, 2002
• 61: Massimo Paolucci , Katia Sycara, Autonomous Semantic Web Services, IEEE Internet Computing, v.7 n.5, p.34-41, September 2003 [doi>10.1109/MIC.2003.1232516]
• 62: Raiffa, H. 1968. Decision Analysis: Introductory Lectures on Choices Under Uncertainty. McGraw-Hill, Englewood Cliffs, NJ.
• 63: Shuping Ran, A model for web services discovery with QoS, ACM SIGecom Exchanges, v.4 n.1, p.1-10, Spring, 2003 [doi>10.1145/844357.844360]
• 64: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 65: Bianca Schroeder , Garth A. Gibson, A large-scale study of failures in high-performance computing systems, Proceedings of the International Conference on Dependable Systems and Networks, p.249-258, June 25-28, 2006 [doi>10.1109/DSN.2006.5]
• 66: Singh, M. P. and Huhns, M. N. 2005. Service-Oriented Computing: Semantics, Processes, Agents. Wiley, New York.
• 67: Sirin, E., Parsia, B., and Hendler, J. 2005. Template-based composition of semantic web services. In Proceedings of the AAAI Fall Symposium on Agents and the Semantic Web. 85--92.
• 68: Smith, T. M., Abajian, C., and Hood, L. 1997. Hopper: Software for automating data tracking and flow in DNA sequencing. Comput. Appl. Biosci. 13, 2, 175--182.
• 69: Stein, S., Jennings, N. R., and Payne, T. R. 2007a. Provisioning heterogeneous and unreliable providers for service workflows. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. 1452--1458.
• 70: Stein, S., Payne, T. R., and Jennings, N. R. 2006. Flexible provisioning of semantic web service workflows using a QoS ontology. In Proceedings of the 5th International Semantic Web Conference (ISWC 2006), Online supplement. (available at http://eprints.ecs.soton.ac.uk/12992/).
• 71: Stein, S., Payne, T. R., and Jennings, N. R. 2007b. An effective strategy for the flexible provisioning of service workflows. In Proceedings of the Workshop on Service-Oriented Computing: Agents, Semantics, and Engineering (SOCASE 2007). Lecture Notes in Computer Science, vol. 4504. Springer-Verlag, Berlin, Germany, 16--30.
• 72: M. Szomszor , T. R. Payne , L. Moreau, Using semantic Web technology to automate data integration in grid and Web service architectures, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 1, p.189-195, May 09-12, 2005
• 73: W. T. Teacy , Jigar Patel , Nicholas R. Jennings , Michael Luck, TRAVOS: Trust and Reputation in the Context of Inaccurate Information Sources, Autonomous Agents and Multi-Agent Systems, v.12 n.2, p.183-198, March 2006 [doi>10.1007/s10458-006-5952-x]
• 74: Tillman, F. A., and Liittschwager, J. M. 1967. Integer programming formulation of constrained reliability problems. Manage. Sci. 13, 11, 887--899.
• 75: Paul Townend , Paul Groth , Jie Xu, A Provenance-Aware Weighted Fault Tolerance Scheme for Service-Based Applications, Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.258-266, May 18-20, 2005 [doi>10.1109/ISORC.2005.3]
• 76: Kishor S. Trivedi, Probability and statistics with reliability, queuing and computer science applications, John Wiley and Sons Ltd., Chichester, UK, 2001
• 77: Hakim Weatherspoon , Tal Moscovitz , John Kubiatowicz, Introspective Failure Analysis: Avoiding Correlated Failures in Peer-to-Peer Systems, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems, p.362, October 13-16, 2002
• 78: Sanjiva Weerawarana , Francisco Curbera , Frank Leymann , Tony Storey , Donald F. Ferguson, Web Services Platform Architecture: SOAP, WSDL, WS-Policy, WS-Addressing, WS-BPEL, WS-Reliable Messaging and More, Prentice Hall PTR, Upper Saddle River, NJ, 2005
• 79: Gerhard Weiss, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 80: Zhonghua Yang , Keith Duddy, CORBA: a platform for distributed object computing, ACM SIGOPS Operating Systems Review, v.30 n.2, p.4-31, April 1996 [doi>10.1145/232302.232303]
• 81: Yu, T. and Lin, K.-J. 2005. Adaptive algorithms for finding replacement services in autonomic distributed business processes. In Proceedings of Autonomous Decentralized Systems (ISADS 2005). 427--434.
• 82: Tao Yu , Yue Zhang , Kwei-Jay Lin, Efficient algorithms for Web services selection with end-to-end QoS constraints, ACM Transactions on the Web (TWEB), v.1 n.1, p.6-es, May 2007 [doi>10.1145/1232722.1232728]
• 83: Liangzhao Zeng , Boualem Benatallah , Marlon Dumas , Jayant Kalagnanam , Quan Z. Sheng, Quality driven web services composition, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775211]
• 84: Chen Zhou , Liang-Tien Chia , Bu-Sung Lee, DAML-QoS Ontology for Web Services, Proceedings of the IEEE International Conference on Web Services, p.472, June 06-09, 2004 [doi>10.1109/ICWS.2004.44]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
Web services, semantic Web services, service composition, service provisioning, service-oriented computing, workflows