Tutorials & Workshops - ACM SIGMETRICS 2000

Scalable Web Server Systems: Architectures, Models, and Load Balancing Algorithms

Philip S. Yu
IBM T.J. Watson Research Center, NY

Valeria Cardellini
University of Roma Tor Vergata, Italy
 

The overall increase in traffic on the World Wide Web causes a disproportionate increase in client requests to popular Web sites, especially in conjunction with special events. For these Web applications, single node platforms that do not replicate information content can not provide the needed scalability to handle large traffic volumes. Mirroring and caching were a standard solution to attack the problems of insufficient bandwidth and high latency. Several advanced approaches of replication and application level naming were introduced to further attack the problem. In other contexts, parallel and distributed technologies are becoming an important paradigm that potentially provides scalability, availability and performance. On the other hand, the Web re-engineering through parallel and distributed technologies is extremely difficult challenge, because any Web sites will be required to respond to millions of requests per day with a guaranteed quality of service level, and scale to match rapid and dramatic changes in the number of clients. Indeed, cooperative methods, parallel architectures and distributed systems could easily exacerbate the situation if the system is not well designed for some specific Web service and the results are not evaluated carefully. The need to optimize the performance of Web-based services is producing a variety of novel architectures for high performance networks and servers.

This tutorial will focus on parallel and distributed architectures and load balancing algorithms, assuming that network issues are examined elsewhere. The tutorial is organized in four sections. The first section looks at the role that parallel and distributed architectures play in the support of high performance and dependable Web services. The main target architectures are tightly coupled clusters, and geographically distributed systems with some cooperation mechanisms among the nodes. Various academic and commercial products will be examined and classified according to the load balancing mechanism that distributes the incoming requests among the servers. The second section reviews the current state-of-the-art in workload characterization and performance metrics applied to the evaluation of these Web systems. The third section is devoted to consideration of options in load balancing algorithms for each class of replicated Web server systems. We will present a taxonomy of the policies that have been developed in recent years focusing on the issues that each algorithm has to address because of the limited control of the router mechanism(s) on the requests, local and geographical distribution of the servers. The fourth section discusses the performance tradeoffs of various options in the design and operation of scalable Web systems. We analyze the results of event- and trace-driven simulation studies which consider various load management options. Performance models of locally and geographically distributed Web systems to evaluate design alternatives will be examined. We will conclude the tutorial with some remarks on some open research issues for the industry and the Sigmetrics community.
 

This is an introductory tutorial. No mathematical sophistication is assumed. Little background knowledge is assumed on networking and distributed systems. Familiarity in using Internet and general scientific background is required. Basic concepts of networking and simulation tools will be helpful but not critical.
 

Philip S. Yu, IBM T.J. Watson Research Center, NY (psyu@us.ibm.com)
Philip S. Yu received the B.S. Degree in E.E. from National Taiwan University, Taipei, Taiwan, the M.S. and Ph.D. degrees in E.E. from Stanford University, and the M.B.A. degree from New York University. He is with the IBM T.J. Watson Research Center and currently manager of the Software Tools and Techniques group. His research interests include data mining, Internet applications and technologies, database systems, multimedia systems, parallel and distributed processing, disk arrays, computer architecture, performance modeling and workload analysis. Dr. Yu has published more than 260 papers in refereed journals and conferences. He holds or has applied for 84 US patents. Dr. Yu is a Fellow of the ACM and a Fellow of the IEEE. He is a member of the IEEE Data Engineering steering committee. He is on the advisory board of IEEE Transactions on Knowledge and Data Engineering. He was an editor of IEEE Transactions on Knowledge and Data Engineering and also a guest co-editor of the special issue on mining of databases. In addition to serving as program committee member on various conferences, he was the program co-chair of the 11th Intl. Conference on Data Engineering and the program chair of the 2nd Intl. Workshop on Research issues on Data Engineering: Transaction and Query Processing. He served as the general chair of the 14th Intl. Conference on Data Engineering. He has received several IBM and external honors including Best Paper Award, 2 IBM Outstanding Innovation Awards, an Outstanding Technical achievement Award, 2 Research Division Awards and 29th plateau of Invention Achievement Awards. He also received an IEEE Region 1 Award for contributions of "New Concepts in Electrical Engineering". Dr. Yu is an IBM Master Inventor and was recognized as one of the IBM's ten top leading inventors in 1999.

Valeria Cardellini, University of Roma Tor Vergata, Italy (cardellini@uniroma2.it)
Valeria Cardellini is currently pursuing a Ph.D. in computer engineering at University of Roma Tor Vergata. She received the Laurea degree in computer engineering from the University of Roma Tor Vergata in 1997. Her research interests focus on the areas of performance analysis, modeling and simulation with particular emphasis on the World Wide Web and distributed servers.