Models and framework for supporting runtime decisions in Web-based systems

ABSTRACT

Efficient management of distributed Web-based systems requires several mechanisms that decide on request dispatching, load balance, admission control, request redirection. The algorithms behind these mechanisms typically make fast decisions on the basis of the load conditions of the system resources. The architecture complexity and workloads characterizing most Web-based services make it extremely difficult to deduce a representative view of a resource load from collected measures that show extreme variability even at different time scales. Hence, any decision based on instantaneous or average views of the system load may lead to useless or even wrong actions. As an alternative, we propose a two-phase strategy that first aims to obtain a representative view of the load trend from measured system values and then applies this representation to support runtime decision systems. We consider two classical problems behind decisions: how to detect significant and nontransient load changes of a system resource and how to predict its future load behavior. The two-phase strategy is based on stochastic functions that are characterized by a computational complexity that is compatible with runtime decisions. We describe, test, and tune the two-phase strategy by considering as a first example a multitier Web-based system that is subject to different classes of realistic and synthetic workloads. Also, we integrate the proposed strategy into a framework that we validate by applying it to support runtime decisions in a cluster Web system and in a locally distributed Network Intrusion Detection System.

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: Mauro Andreolini , Sara Casolari, Load prediction models in web-based systems, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy [doi>10.1145/1190095.1190129]
• 3: Andreolini, M., Colajanni, M., and Nuccio, M. 2003. Scalability of content-aware server switches for cluster-based Web information systems. In Proceedings of 12th International World Wide Web Conf. (WWW'03). Budapest, Hungary.
• 4: Apache. 1999. Apache HTTP server project. http://www.apache.org.
• 5: Characterizing the scalability of a large web-based shopping system, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.44-69, Aug. 2001 [doi>10.1145/383034.383036]
• 6: Jacques M. Bahi , Sylvain Contassot-Vivier , Raphael Couturier, Dynamic Load Balancing and Efficient Load Estimators for Asynchronous Iterative Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.16 n.4, p.289-299, April 2005 [doi>10.1109/TPDS.2005.45]
• 7: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 8: Yuliy Baryshnikov , Ed Coffman , Guillaume Pierre , Dan Rubenstein , Mark Squillante , Teddy Yimwadsana, Predictability of Web-Server Traffic Congestion, Proceedings of the 10th International Workshop on Web Content Caching and Distribution, p.97-103, September 12-13, 2005 [doi>10.1109/WCW.2005.17]
• 9: Bonett, D. 2006. Approximate confidence interval for standard deviation of nonnormal distributions. Comput. Statis. Data Anal. 50, 3, 775--882.
• 10: George Edward Pelham Box , Gwilym M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 11: Peter J Brockwell , Richard A Davis, Time series: theory and methods, Springer-Verlag New York, Inc., New York, NY, 1986
• 12: Bryhni, H. 2000. A comparison of load balancing techniques for scalable web servers. IEEE Netw. 14, 4, 58--64.
• 13: Morris Marden, An Architectural Evaluation of Java TPC-W, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.229, January 20-24, 2001
• 14: Canali, C., Xiao, Z., and Rabinovich, M. 2004. Utility computing for Internet applications. In Web Content Delivery, X. Tang, J. Xu, and S. Chanson, Eds. Vol. 2. Springer Verlag, 131--151.
• 15: Valeria Cardellini , Emiliano Casalicchio , Michele Colajanni , Philip S. Yu, The state of the art in locally distributed Web-server systems, ACM Computing Surveys (CSUR), v.34 n.2, p.263-311, June 2002 [doi>10.1145/508352.508355]
• 16: Valeria Cardellini , Michele Colajanni , Philip S. Yu, Request Redirection Algorithms for Distributed Web Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.355-368, April 2003 [doi>10.1109/TPDS.2003.1195408]
• 17: Valeria Cardellini , Michele Colajanni , Philip S. Yu, Geographic Load Balancing for Scalable Distributed Web Systems, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.20, August 29-September 01, 2000
• 18: Castro, M., Dwyer, M., and Rumsewicz, M. 1999. Load balancing and control for distributed World Wide Web servers. In Proceedings of the International Conference on Control Applications (CCA'99). Kohala Coast, HI.
• 19: Cecchet, E., Chanda, A., Elnikety, S., Marguerite, J., and Zwaenepoel, W. 2003. Performance comparison of middleware architectures for generating dynamic Web content. In Proceedings of the 4th Middleware Conference. Rio de Janeiro, Brazil.
• 20: James R. Challenger , Paul Dantzig , Arun Iyengar , Mark S. Squillante , Li Zhang, Efficiently serving dynamic data at highly accessed web sites, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.233-246, April 2004 [doi>10.1109/TNET.2004.826289]
• 21: Chen, H. and Mohapatra, P. 2002. Session-based overload control in QoS-aware Web server. In Proceedings of the 21th IEEE International Conference on Computer Communications (INFOCOM'02).
• 22: Huamin Chen , Prasant Mohapatra, Overload control in QoS-aware web servers, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.1, p.119-133, 15 May 2003 [doi>10.1016/S1389-1286(03)00178-6]
• 23: Xuan Chen , John Heidemann, Flash crowd mitigation via adaptive admission control based on application-level observations, ACM Transactions on Internet Technology (TOIT), v.5 n.3, p.532-569, August 2005 [doi>10.1145/1084772.1084776]
• 24: Cherkasova, L. and Phaal, P. 1999. Session based admission control: A mechanism for improving performance of commercial Web sites. In Proceedings of the 7th International Workshop on Quality of Service (IWQoS'99). London, UK, 226--235.
• 25: Ludmila Cherkasova , Peter Phaal, Session-Based Admission Control: A Mechanism for Peak Load Management of Commercial Web Sites, IEEE Transactions on Computers, v.51 n.6, p.669-685, June 2002 [doi>10.1109/TC.2002.1009151]
• 26: Choi, B., Park, J., and Zhang, Z. 2003. Adaptive random sampling for traffic load measurement. In Proceedings of the 16th IEEE International Conference on Communications (ICC'03). Anchorage, AL.
• 27: Colajanni, M. and Marchetti, M. 2006. A parallel architecture for stateful intrusion detection in high traffic networks. In Proceedings of the IEEE/IST Workshop on Monitoring, Attack Detection and Mitigation (MonAM'06). Tuebingen, Germany.
• 28: Mark E. Crovella , Murad S. Taqqu , Azer Bestavros, Heavy-tailed probability distributions in the World Wide Web, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 29: Michael Dahlin, Interpreting Stale Load Information, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1033-1047, October 2000 [doi>10.1109/71.888643]
• 30: Peter A. Dinda , David R. O'Hallaron, Host load prediction using linear models, Cluster Computing, v.3 n.4, p.265-280, 2000 [doi>10.1023/A:1019048724544]
• 31: Dodge, R. C., Menascé, D. A., and Barbará, D. 2001. Testing e-commerce site scalability with TPC-W. In Proceedings of the 27th International Computer Measurement Group Conference. Orlando, FL.
• 32: Duffield, N. G. and Lo Presti, F. 2000. Multicast inference of packet delay variance at interior network links. In Proceedings of the 19th IEEE International Conference on Computer Communications (INFOCOM'00). Tel Aviv, Israel.
• 33: Sameh Elnikety , Erich Nahum , John Tracey , Willy Zwaenepoel, A method for transparent admission control and request scheduling in e-commerce web sites, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988710]
• 34: Eubank, R. L. and Eubank, E. 1999. Non parametric regression and spline smoothing. CRC Press.
• 35: Domenico Ferrari , Songnian Zhou, An Empirical Investigation of Load Indices for Load Balancing Applications, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.515-528, December 07-09, 1987
• 36: George S. Fishman , Ivo J. B. F. Adan, How heavy-tailed distributions affect simulation-generated time averages, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.2, p.152-173, April 2006 [doi>10.1145/1138464.1138467]
• 37: Sally Floyd , Vern Paxson, Difficulties in simulating the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.4, p.392-403, August 2001 [doi>10.1109/90.944338]
• 38: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 39: A. G. Ganek , T. A. Corbi, The dawning of the autonomic computing era, IBM Systems Journal, v.42 n.1, p.5-18, January 2003
• 40: Hasyim Gautama , Arjan J. C. van Gemund, Low-Cost Static Performance Prediction of Parallel Stochastic Task Compositions, IEEE Transactions on Parallel and Distributed Systems, v.17 n.1, p.78-91, January 2006 [doi>10.1109/TPDS.2006.13]
• 41: Ravi R. Iyer, Exploring the Cache Design Space for Web Servers, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.67, April 23-27, 2001
• 42: Jaeyeon Jung , Balachander Krishnamurthy , Michael Rabinovich, Flash crowds and denial of service attacks: characterization and implications for CDNs and web sites, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511485]
• 43: Kamra, A., Misra, V., and Nahum, E. M. 2004. Yaksha: A self-tuning controller for managing the performance of 3-tiered sites. In Proceedings of the 12th International Workshop on Quality of Service (IWQOS'04). Montreal, Canada.
• 44: Pradnya Karbhari , Michael Rabinovich , Zhen Xiao , Fred Douglis, ACDN: a content delivery network for applications, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564773]
• 45: Terence Kelly, Detecting performance anomalies in global applications, Proceedings of the 2nd conference on Real, Large Distributed Systems, p.42-47, December 13, 2005, San Francisco, CA
• 46: Kendall, M. and Ord, J. 1990. Time Series. Oxford University Press.
• 47: Jeffrey O. Kephart , David M. Chess, The Vision of Autonomic Computing, Computer, v.36 n.1, p.41-50, January 2003 [doi>10.1109/MC.2003.1160055]
• 48: Measuring computer performance: a practitioner's guide, Cambridge University Press, New York, NY, 2000
• 49: Lingyun Yang , Ian Foster , Jennifer M. Schopf, Homeostatic and Tendency-Based CPU Load Predictions, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.42.2, April 22-26, 2003
• 50: Richard Lippmann , Joshua W. Haines , David J. Fried , Jonathan Korba , Kumar Das, Analysis and Results of the 1999 DARPA Off-Line Intrusion Detection Evaluation, Proceedings of the Third International Workshop on Recent Advances in Intrusion Detection, p.162-182, October 02-04, 2000
• 51: Song Luo , Gerald A. Marin, Realistic internet traffic simulation through mixture modeling and a case study, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
• 52: Daniel A. Menasce , Jeffrey O. Kephart, Guest Editors' Introduction: Autonomic Computing, IEEE Internet Computing, v.11 n.1, p.18-21, January 2007 [doi>10.1109/MIC.2007.11]
• 53: Michael Mitzenmacher, How Useful Is Old Information?, IEEE Transactions on Parallel and Distributed Systems, v.11 n.1, p.6-20, January 2000 [doi>10.1109/71.824633]
• 54: MySQL 2005. MySQL Database server. http://www.mysql.com/.
• 55: Vivek S. Pai , Mohit Aron , Gaurov Banga , Michael Svendsen , Peter Druschel , Willy Zwaenepoel , Erich Nahum, Locality-aware request distribution in cluster-based network servers, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.205-216, October 02-07, 1998, San Jose, California, United States
• 56: Raju Pandey , J. Fritz Barnes , Ronald Olsson, Supporting quality of service in HTTP servers, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.247-256, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277742]
• 57: Guillaume Pierre , Maarten van Steen, Globule: A Platform for Self-Replicating Web Documents, Proceedings of the 6th International Conference on Protocols for Multimedia Systems, p.1-11, October 17-19, 2001
• 58: Poirier, D. J. 1973. Piecewise regression using cubic spline. J. Amer. Statist. Ass. 68, 343, 515--524.
• 59: Pradhan, P., Tewari, R., Sahu, S., Chandra, A., and Shenoy, P. 2002. An observation-based approach towards self-managing Web servers. In Proceedings of the 10th International Workshop on Quality of Service (IWQOS'02). Monterey, CA.
• 60: Rabinovich, M., Triukose, S., Wen, Z., and Wang, L. 2006. DipZoom: The Internet measurement marketplace. In Proceedings of the 9th IEEE Global Internet Symposium. Barcelona, Spain.
• 61: Rabinovich, M., Zhen, X., and Aggarwal, A. 2003. Computing on the edge: A platform for replicating Internet applications. In Proceedings of the 8th International Workshop of Web Content Caching and Distribution (WCW'03). Hawthorne, NY.
• 62: Parameswaran Ramanathan, Overload Management in Real-Time Control Applications Using m,k $(m,k)$-Firm Guarantee, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.549-559, June 1999 [doi>10.1109/71.774906]
• 63: Sang, A. and Li, S. 2000. A predictability analysis of network traffic. In Proceedings of the 19th IEEE International Conference on Computer Communications (INFOCOM'00). Tel Aviv, Israel.
• 64: Brian D. Noble , M. Satyanarayanan , Dushyanth Narayanan , James Eric Tilton , Jason Flinn , Kevin R. Walker, Agile application-aware adaptation for mobility, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.276-287, October 05-08, 1997, Saint Malo, France
• 65: Swaminathan Sivasubramanian , Michal Szymaniak , Guillaume Pierre , Maarten van Steen, Replication for web hosting systems, ACM Computing Surveys (CSUR), v.36 n.3, p.291-334, September 2004 [doi>10.1145/1035570.1035573]
• 66: SpecWEB05 2005. The SPECWeb05 benchmark. http://www.spec.org/osg/web2005/.
• 67: SpecWEB96 1996. The SPECWeb96 benchmark. http://www.spec.org/osg/web96/.
• 68: John A. Stankovic, Simulations of three adaptive, decentralized controlled, job scheduling algorithms, Computer Networks and ISDN Systems, v.8 n.3, p.199-217, June 1984
• 69: Tomcat 2005. The Tomcat Servlet Engine. http://jakarta.apache.org/tomcat/.
• 70: TPC-W 2004. TPC-W transactional Web e-commerce benchmark. http://www.tpc.org/tpcw/.
• 71: Nancy Tran , Daniel A. Reed, Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.362-377, April 2004 [doi>10.1109/TPDS.2004.1271185]
• 72: Utts, J. M. 2004. Seeing Through Statistics. Thomson Brooks/Cole.
• 73: Jonathan Wildstrom , Emmett Witchel , Raymond J. Mooney, Towards Self-Configuring Hardware for Distributed Computer Systems, Proceedings of the Second International Conference on Automatic Computing, p.241-249, June 13-16, 2005 [doi>10.1109/ICAC.2005.63]
• 74: George Wolberg , Itzik Alfy, Monotonic Cubic Spline Interpolation, Proceedings of the International Conference on Computer Graphics, p.188, June 07-11, 1999
• 75: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Measurement techniques; Modeling techniques; Design studies

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
World Wide Web, distributed systems, load change detection, load prediction, load representation