Decentralizing execution of composite web services

ABSTRACT

Distributed enterprise applications today are increasingly being built from services available over the web. A unit of functionality in this framework is a web service, a software application that exposes a set of "typed'' connections that can be accessed over the web using standard protocols. These units can then be composed into a <i>composite</i> web service. BPEL (Business Process Execution Language) is a high-level distributed programming language for creating composite web services.

Although a BPEL program invokes services distributed over several servers, the <i>orchestration</i> of these services is typically under centralized control. Because performance and throughput are major concerns in enterprise applications, it is important to remove the inefficiencies introduced by the centralized control. In a distributed, or decentralized orchestration, the BPEL program is partitioned into independent sub-programs that interact with each other without any centralized control. Decentralization can increase parallelism and reduce the amount of network traffic required for an application.

This paper presents a technique to partition a composite web service written as a single BPEL program into an equivalent set of decentralized processes. It gives a new code partitioning algorithm to partition a BPEL program represented as a program dependence graph, with the goal of minimizing communication costs and maximizing the <i>throughput</i> of multiple concurrent instances of the input program. In contrast, much of the past work on dependence-based partitioning and scheduling seeks to minimize the <i>completion time</i> of a single instance of a program running in isolation. The paper also gives a cost model to estimate the throughput of a given code partition.

REFERENCES

• 1: WebSphere Application Server. http://www-3.ibm.com/software/info1/websphere/index.jsp?tab=products/appserv.
• 2: W. Baxter , H. R. Bauer, III, The program dependence graph and vectorization, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75278]
• 3: S. H. Bokhari, Partitioning Problems in Parallel, Pipeline, and Distributed Computing, IEEE Transactions on Computers, v.37 n.1, p.48-57, January 1988 [doi>10.1109/12.75137]
• 4: Business Process Execution Language for Web Services Version 1.1. http://www.ibm.com/developerworks/library/ws-bpel/.
• 5: BPWS4J: Java Run Time for BPEL4WS. http://www.alphaworks.ibm.com/tech/bpws4j.
• 6: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 7: Apostolos Gerasoulis , Sesh Venugopal , Tao Yang, Clustering task graphs for message passing architectures, Proceedings of the 4th international conference on Supercomputing, p.447-456, June 11-15, 1990, Amsterdam, The Netherlands
• 8: R. L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17(2):416--429, March 1969.
• 9: Steve Graham , Doug Davis , Simeon Simeonov , Toufic Boubez , Ryo Neyama , Yuichi Nakamura, Building Web Services with Java: Making Sense of Xml, Soap, Wsdl, and Uddi, Sams, Indianapolis, IN, 2001
• 10: S. Horwitz , J. Prins , T. Reps, Integrating non-intering versions of programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-145, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73572]
• 11: R. Khalaf, N. Mukhi, and S. Weerawarana. Service-Oriented Composition in BPEL4WS. In Proceedings of the Twelfth International World Wide Web Conference, 2003.
• 12: Jens Krinke, Static slicing of threaded programs, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.35-42, June 16-16, 1998, Montreal, Quebec, Canada
• 13: Peter Muth , Dirk Wodtke , Jeanine Weissenfels , Angelika Kotz Dittrich , Gerhard Weikum, From Centralized Workflow Specification to Distributed WorkflowExecution, Journal of Intelligent Information Systems, v.10 n.2, p.159-184, March/April 1998 [doi>10.1023/A:1008608810770]
• 14: Raymond Reiter, Scheduling Parallel Computations, Journal of the ACM (JACM), v.15 n.4, p.590-599, Oct. 1968 [doi>10.1145/321479.321485]
• 15: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 16: V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991
• 17: Vivek Sarkar, A Concurrent Execution Semantics for Parallel Program Graphs and Program Dependence Graphs, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.16-30, August 03-05, 1992
• 18: Abhishek Singh , Santosh Pande, Compiler optimizations for Java aglets in distributed data intensive applications, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508809]
• 19: S. Singhai and K. McKinley. Loop fusion for data locality and parallelism. In Proceedings of the Mid-Atlantic Student Workshop on Programming Languages and Systems, 1996.
• 20: Jaspal Subhlok , David R. O'Hallaron , Thomas Gross , Peter A. Dinda , Jon Webb, Communication and memory requirements as the basis for mapping task and data parallel programs, Proceedings of the 1994 conference on Supercomputing, p.330-339, December 1994, Washington, D.C., United States
• 21: Jaspar Subhlok , Gary Vondran, Optimal latency-throughput tradeoffs for data parallel pipelines, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.62-71, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237508]
• 22: Eli Tilevich , Yannis Smaragdakis, J-Orchestra: Automatic Java Application Partitioning, Proceedings of the 16th European Conference on Object-Oriented Programming, p.178-204, June 10-14, 2002
• 23: T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994 [doi>10.1109/71.308533]
• 24: Dong Zhou , Santosh Pande , Karsten Schwan, Method Partitioning - Runtime Customization of Pervasive Programs without Design-time Application Knowledge, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.610, May 19-22, 2003

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages, Performance

Keywords:
business process, program dependence graph, work flow