A method for transparent admission control and request scheduling in e-commerce web sites

ABSTRACT

This paper presents a method for admission control and request scheduling for multiply-tiered e-commerce Web sites, achieving both stable behavior during overload and improved response times. Our method externally observes execution costs of requests online, distinguishing different request types, and performs overload protection and preferential scheduling using relatively simple measurements and a straight forward control mechanism. Unlike previous proposals, which require extensive changes to the server or operating system, our method requires no modifications to the host O.S., Web server, application server or database. Since our method is external, it can be implemented in a proxy. We present such an implementation, called Gatekeeper, using it with standard software components on the Linux operating system. We evaluate the proxy using the industry standard TPC-W workload generator in a typical three-tiered e-commerce environment. We show consistent performance during overload and throughput increases of up to 10 percent. Response time improves by up to a factor of 14, with only a 15 percent penalty to large jobs.

REFERENCES

• 1: Tarek F. Abdelzaher , Nina Bhatti, Web content adaptation to improve server overload behavior, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1563-1577, May 17, 1999
• 2: 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]
• 3: J. Almeida, M. Dabu, A. Manikutty, and P. Cao. Providing differentiated levels of service in Web content hosting. In Workshop on Internet Server Performance, Madison, WI, June 1998.
• 4: AMD Corporation. AMD Athlon processor x86 code optimization guide. http://www.amd.com.
• 5: C. Amza, E. Cecchet, A. Chanda, A. L. Cox, S.Elnikety, R. Gil, J. Marguerite, K. Rajamani, and W. Zwaenepoel. Specification and implementation of dynamic Web site benchmarks. In Proceedings of the 5th Workshop on Workload Characterization, Austin, Texas, November 2002.
• 6: M. Arlitt, D. Krishnamurthy, and J. Rolia. Characterizing the scalability of a large Web -based shopping system. Technical Report HPL-2001-XX, HP Labs, April 2001.
• 7: Mohit Aron , Peter Druschel , Willy Zwaenepoel, Cluster reserves: a mechanism for resource management in cluster-based network servers, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.90-101, June 18-21, 2000, Santa Clara, California, United States
• 8: Mohit Aron , Peter Druschel, Differentiated and predictable quality of service in web server systems, 2001
• 9: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 10: N. Bhatti, A. Bouch, and A. Kuchinsky. Integrating user-perceived quality into Web server design. Technical Report HPL-2000-3, HP Labs, January 2000.
• 11: N. Bhatti and R. Friedrich. Web server support for tiered services. IEEE Network, 13(5):64--71, September 1999.
• 12: P. Bhoj, S. Rmanathan, and S. Singhal. Web2K: Bringing QoS to Web servers. Technical Report HPL-2000-61, HP Labs, May 2000.
• 13: E. Cecchet, A. Chanda, S. Elnikety, J. Marguerite, and W. Zwaenepoel. Performance comparison of middleware architectures for generating dynamic Web content. In Proceedings of the ACM/IFIP/USENIX International Middleware Conference (Middleware 2003), Rio de Janeiro, Brazil, June 2003.
• 14: S. Chandra, C. Ellis, and A. Vahdat. Differentiated multimedia Web services using quality aware transcoding. In IEEE Infocom, Tel-Aviv, Israel, March 2000.
• 15: Xiangping Chen , Prasant Mohapatra , Huamin Chen, An admission control scheme for predictable server response time for web accesses, Proceedings of the 10th international conference on World Wide Web, p.545-554, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372156]
• 16: Ludmila Cherkasova, Scheduling Strategy to improve Response Time for Web Applications, Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking, p.305-314, April 21-23, 1998
• 17: 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]
• 18: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 19: M. Crovella, R. Frangioso, and M. Harchol-Balter. Connection scheduling in Web servers. In Proceedings of the 1999 USENIX Symposium on Internet Technologies and Systems (USITS '99), Boulder, Colorado, October 1999.
• 20: Peter J. Denning, A Short Theory of Multiprogramming, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.2-7, January 10-18, 1995
• 21: Y. Diao, N. Gandhi, J. L. Hellerstein, S. Parekh, and D. M. Tilbury. Using MIMO feedback control to enforce policies for interrelated metrics with application to the Apache Web server. In Proceedings of the Network Operations and Management Symposium, Florence, Italy, April 2002.
• 22: Peter Druschel , Gaurav Banga, Lazy receiver processing (LRP): a network subsystem architecture for server systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.261-275, October 29-November 01, 1996, Seattle, Washington, United States
• 23: Lars Eggert , John Heidemann, Application-level differentiated services for Web servers, World Wide Web, v.2 n.3, p.133-142, 1999 [doi>10.1023/A:1019200806549]
• 24: Hans-Ulrich Heiss , Roger Wagner, Adaptive Load Control in Transaction Processing Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.47-54, September 03-06, 1991
• 25: D. Heller. Rabbit performance counters library. http://www.scl.ameslab.gov/Projects/Rabbit/.
• 26: R. Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
• 27: Vikram Kanodia , Edward W. Knightly, Ensuring Latency Targets in Multiclass Web Servers, IEEE Transactions on Parallel and Distributed Systems, v.14 n.1, p.84-93, January 2003 [doi>10.1109/TPDS.2003.1167373]
• 28: K. Li and S. Jamin. A measurement-based admission-controlled Web server. In IEEE Infocom, Tel-Aviv, Israel, March 2000.
• 29: Chenyang Lu , Tarek F. Abdelzaher , John A. Stankovic , Sang H. Son, A Feedback Control Approach for Guaranteeing Relative Delays in Web Servers, Proceedings of the Seventh Real-Time Technology and Applications Symposium (RTAS '01), p.51, May 30-June 01, 2001
• 30: David T. McWherter , Bianca Schroeder , Anastassia Ailamaki , Mor Harchol-Balter, Priority Mechanisms for OLTP and Transactional Web Applications, Proceedings of the 20th International Conference on Data Engineering, p.535, March 30-April 02, 2004
• 31: Daniel A. Menascé, TPC-W: A Benchmark for E-Commerce, IEEE Internet Computing, v.6 n.3, p.83-87, May 2002 [doi>10.1109/MIC.2002.1003136]
• 32: Jeffrey C. Mogul , K. K. Ramakrishnan, Eliminating receive livelock in an interrupt-driven kernel, ACM Transactions on Computer Systems (TOCS), v.15 n.3, p.217-252, Aug. 1997 [doi>10.1145/263326.263335]
• 33: News.Com. E-commerce strong in third quarter. http://news.com.com/2100-1017-971123.html, November 2002.
• 34: V. Pai, P. Druschel, and W. Zwaenepoel. Flash: An efficient and portable Web server. In USENIX Annual Technical Conference , Monterey, CA, June 1999.
• 35: P. Pradhan, R. Tewari, S. Sahu, A. Chandra, and P. Shenoy. An observation-based approach towards self-managing Web servers. In International Workshop on Quality of Service, Miami Beach, FL, May 2002.
• 36: Rice University Computer Science Department. The Dynaserver project. http://www.cs.rice.edu/CS/Systems/DynaServer.
• 37: B. Schroeder and M. Harchol-Balter. Web servers under overload: How scheduling can help. Technical Report CMU-CS-02-143, Carnegie-Mellon University C.S. Department, Pittsburgh, PA, July 2002.
• 38: S. Seshan, M. Stemm, and R. H. Katz. Benefits of transparent content negotiation in HTTP. In Proceedings of the IEEE Globcom 98 Internet Mini-Conference, Sydney, Australia, November 1998.
• 39: Kai Shen , Hong Tang , Tao Yang , Lingkun Chu, Integrated resource management for cluster-based internet services, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060311]
• 40: Sysstat Project. Systat home page. http://freshmeat.net/projects/sysstat.
• 41: Y. C. Tay , Nathan Goodman , R. Suri, Locking performance in centralized databases, ACM Transactions on Database Systems (TODS), v.10 n.4, p.415-462, Dec. 1985 [doi>10.1145/4879.4880]
• 42: The Apache Project. The Apache WWW server. http://httpd.apache.org.
• 43: The Transaction Processing Council (TPC). TPC-W.http://www.tpc.org/tpcw.
• 44: Thiemo Voigt , Renu Tewari , Douglas Freimuth , Ashish Mehra, Kernel Mechanisms for Service Differentiation in Overloaded Web Servers, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.189-202, June 25-30, 2001
• 45: M. Welsh and D. Culler. Adaptive overload control for busy Internet servers. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS), San Francisco, CA, March 2003.
• 46: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Measurement, Performance

Keywords:
admission control, dynamic web content, load control, request scheduling, web servers