Load balancing for clustered web farms

Abstract

We propose a scheme which attempts to optimally balance the load on the servers of a clustered web farm. Solving this performance problem is crucial to achieving minimal average response time for customer requests, and thus ultimately to achieving maximal customer throughput. This short paper gives an overview of three new mathematical contributions. First, we describe a goal setting algorithm to determine the load on each server which minimizes the average customer request response time given the possibly overlapping cluster assignments of sites to servers and the current customer request load for each site. The cluster assignments, which of necessity can only be changed relatively infrequently, have a major effect on the optimal response time in the goal setting component. So, second, we describe a static algorithm which determines good assignments of sites to servers. Third, and finally, we describe a dynamic algorithm which handles the real-time server load balancing, reacting to the fluctuating customer request load in order to come as close as possible to achieving the idealized optimal average response time. We examine the performance of the overall load balancing scheme via simulation experiments.

References

1. V. Cardellini, M. Colajanni and P. Yu, "Dynamic Load Balancing on Web-Server Systems", IEEE Internet Computing, pp. 28-39, May-June, 1999.
2. A. Federgruen and H. Groenevelt, "The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality", Operations Research, vol. 34, pp. 909-918, 1986.
3. R. Garfinkel and G. Nemhauser, Integer Programming, John Wiley and Sons, 1972.
4. T. Ibaraki and N. Katoh, Resource Allocation Problems - Algorithmic Approaches, The MIT Press, 1988.
5. A. Iyengar, M. Squillante and L. Zhang, "Analysis and Characterization of Large-Scale Web Server Access Patterns and Performance", World Wide Web, vol. 2, pp. 88-100, 1999.
6. G. Schmunek, D. Dupuche, T. Fung, E. Myhra and H. Stein, "Slicing the AS/400 with LPARS", IBM Redbook SG24-5439-00, Armonk, NY, 1999.
7. A. Tantawi, D. Towsley and J. Wolf, "Optimal Allocation of Multiple Class Resources in Computer Systems", ACM Sigmetrics Conference, Santa Fe NM, 1988.
8. J. Wolf and P. Yu, "On Balancing the Load in a Clustered Web Farm", IBM Research Report, 2001.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making