A control theoretical approach to self-optimizing block transfer in Web service grids

ABSTRACT

Nowadays, Web Services (WS) play an important role in the dissemination and distributed processing of large amounts of data that become available on the Web. In many cases, it is essential to retrieve and process such data in blocks, in order to benefit from pipelined parallelism and reduced communication costs. This article deals with the problem of minimizing at runtime, in a self-managing way, the total response time of a call to a database exposed to a volatile environment, like the Grid, as a WS. Typically, in this scenario, response time exhibits a concave, nonlinear behavior depending on the client-controlled size of the individual requests comprising a fixed size task. In addition, no accurate profiling or internal state information is available, and the optimum point is volatile. This situation is encountered in several systems, such as WS Management Systems (WSMS) for DBMS-like data management over wide area service-based networks, and the widely spread OGSA-DAI WS for accessing and integrating traditional DBMS. The main challenges in this problem apart from the unavailability of a model, include the presence of noise, which incurs local minima, the volatility of the environment, which results in moving optimum operating point, and the requirements for fast convergence to the optimal size of the request from the side of the client rather than of the server, and for low overshooting. Two solutions are presented in this work, which fall into the broader areas of runtime optimization and switching extremum control. They incorporate heuristics to avoid local optimal points, and address all the aforementioned challenges. The effectiveness of the solutions is verified via both empirical evaluation in real cases and simulations, which show that significant performance benefits can be provided rendering obsolete the need for detailed profiling of the WS.

REFERENCES

• 1: Tarek F. Abdelzaher , Kang G. Shin , Nina Bhatti, Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.80-96, January 2002 [doi>10.1109/71.980028]
• 2: Abdelzaher, T. F., Stankovic, A., Lu, C., Zhang, R., and Lu, Y. 2003. Feedback performance control in software services. IEEE Cont. Sys. Mag. 23, 3.
• 3: Alpdemir, M. N., Mukherjee, A., Paton, N. W., Watson, P., Fernandes, A. A. A., Gounaris, A., and Smith, J. 2003. Service-based distributed querying on the grid. In Proceedings of the 1st International Conference on Service Oriented Computing (ICSOC). Springer, 467--482.
• 4: Alpdemir, N., Gounaris, A., Mukherjee, A., Fitzgerald, D., Paton, N. W., Watson, P., Sakellariou, R., Fernandes, A. A., and Smith, J. 2005. Experience on performance evaluation with OGSA-DQP. In Proceedings of the UK e-Science All Hands Meeting.
• 5: Mario Antonioletti , Malcolm Atkinson , Rob Baxter , Andrew Borley , Neil P. Chue Hong , Brian Collins , Neil Hardman , Alastair C. Hume , Alan Knox , Mike Jackson , Amy Krause , Simon Laws , James Magowan , Norman W. Paton , Dave Pearson , Tom Sugden , Paul Watson , Martin Westhead, The design and implementation of Grid database services in OGSA-DAI: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.2-4, p.357-376, February 2005 [doi>10.1002/cpe.v17:2/4]
• 6: Kartik B. Ariyur , Miroslav Krstic, Real Time Optimization by Extremum Seeking Control, John Wiley & Sons, Inc., New York, NY, 2003
• 7: Blackman, P. 1962. Extremum-Seeking Regulators: An Exposition of Adaptive Control. Pergamon Press.
• 8: Choi, J., Krstic, M., Ariyur, K., and Lee, J. 2002. Extremum seeking control for discrete-time systems. IEEE Trans. Auto. Cont. 47, 2, 318--323.
• 9: Diao, Y., Eskesen, F., Forehlich, S., Hellerstein, J., Spainhower, L., and Surendra, M. 2003. Generic online optimization of multiple configuration parameters with application to a database server. DSOM, 3--15. LNCS 2867.
• 10: Yixin Diao , Joseph L. Hellerstein , Sujay Parekh , Rean Griffith , Gail Kaiser , Dan Phung, Self-Managing Systems: A Control Theory Foundation, Proceedings of the 12th IEEE International Conference and Workshops on Engineering of Computer-Based Systems, p.441-448, April 04-07, 2005 [doi>10.1109/ECBS.2005.60]
• 11: Dobrzelecki, B., Antonioletti, M., Schopf, J., Hume, A., Atkinson, M., Hong, N. C., Jackson, M., Karasavvas, K., Krause, A., Parsons, M., Sugden, T., and Theocharopoulos, E. 2006. Profiling OGSA-DAI Performance for Common Use Patterns. In Proceedings of the UK e-Science All Hands Meeting.
• 12: Draper, C. and Li, Y. T. 1954. Principles of Optimizing Control Systems. ASME Publications.
• 13: Flardh, O., Johansson, K. J., and Johansson, M. 2005. A new feedback control mechanism for error correction in packet-switched networks. In Proceedings of the 44th IEEE Conference on Decision and Control (CDC-ECC'05), 488--493.
• 14: S. Parekh , N. Gandhi , J. Hellerstein , D. Tilbury , T. Jayram , J. Bigus, Using Control Theory to Achieve Service Level Objectives In Performance Management, Real-Time Systems, v.23 n.1-2, p.127-141, July-September 2002 [doi>10.1023/A:1015350520175]
• 15: Anastasios Gounaris , Rizos Sakellariou , Norman W. Paton , Alvaro A. Fernandes, A novel approach to resource scheduling for parallel query processing on computational grids, Distributed and Parallel Databases, v.19 n.2-3, p.87-106, May 2006 [doi>10.1007/s10619-006-8490-2]
• 16: Gounaris, A., Smith, J., Paton, N. W., Sakellariou, R., Fernandes, A. A. A., and Watson, P. 2005. Adapting to changing resource performance in grid query processing. In Data Management in Grids, First VLDB Workshop (DMG 2005). 30--44.
• 17: Anastasios Gounaris , Christos Yfoulis , Rizos Sakellariou , Marios D. Dikaiakos, Self-optimizing block transfer in web service grids, Proceedings of the 9th annual ACM international workshop on Web information and data management, November 09-09, 2007, Lisbon, Portugal [doi>10.1145/1316902.1316911]
• 18: Hellerstein, J., Diao, Y., Parekh, S., and Tilbury, D. 2005. Control engineering for computing systems. IEEE Cont. Syst. Mag. 25, 6, 56--68.
• 19: Killingsworth, N. and Krstic, M. 2006. PID tuning using extremum seeking. IEEE Cont. Syst. Mag., (Feb.), 70--79.
• 20: Tevfik Kosar , Miron Livny, Stork: Making Data Placement a First Class Citizen in the Grid, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.342-349, March 24-26, 2004
• 21: Krstic, M. and Wang, H. 2000. Stability of extremum seeking feedback for general nonlinear dynamic systems. Automatica 36, 595--601.
• 22: Larsson, S. 2001. Literature study on extremum control. Tech. rep., Chalmers University of Technology.
• 23: David T. Liu , Michael J. Franklin , Devesh Parekh, GridDB: a relational interface for the grid, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872846]
• 24: Liu, X., Sha, L., Diao, Y., Froehlich, S., Hellerstein, J. L., and Parekh, S. S. 2003b. Online response time optimization of Apache Web server. In Proceedings of the 11th International Workshop on Quality of Service (IWQoS). 461--478.
• 25: Chenyang Lu , Xiaorui Wang , Xenofon Koutsoukos, Feedback Utilization Control in Distributed Real-Time Systems with End-to-End Tasks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.550-561, June 2005 [doi>10.1109/TPDS.2005.73]
• 26: Sivaramakrishnan Narayanan , Umit Catalyurek , Tahsin Kurc , Xi Zhang , Joel Saltz, Applying Database Support for Large Scale Data Driven Science in Distributed Environments, Proceedings of the 4th International Workshop on Grid Computing, p.141, November 17-17, 2003
• 27: A. L. Peressini , Francis E. Sullivan , J. J. Uhl, Jr., The mathematics of nonlinear programming, Springer-Verlag New York, Inc., New York, NY, 1988
• 28: Mukund Raghavachari , Darrell Reimer , Robert D. Johnson, The deployer's problem: configuring application servers for performance and reliability, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 29: Balasubramanian Seshasayee , Karsten Schwan , Patrick Widener, SOAP-binQ: High-Performance SOAP with Continuous Quality Management, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.158-165, March 24-26, 2004
• 30: Utkarsh Srivastava , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Query optimization over web services, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 31: Stanojevic, R., Kellet, C., and Shorten, R. N. 2006. Adaptive tuning of drop-tail buffers for reducing queueing delays. IEEE Comm. Letters 10, 7.
• 32: Stanojevic, R. and Shorten, R. 2007. How expensive is link utilization. Tech. Rep., available at http://www.hamilton.ie./person/rade/QP.pdf.
• 33: P.E. E. Wellstead , M. B. Zarrop, Self-Tuning Systems: Control and Signal Processing, John Wiley & Sons, Inc., New York, NY, 1991

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Performance

Keywords:
Autonomic computing, OGSA-DAI, Web Services, control theory, data grids, extremum control