Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
1999-08-16
2002-04-16
Lim, Krisna (Department: 2757)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S235000, C709S201000, C709S229000, C707S793000
Reexamination Certificate
active
06374297
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer cluster load balancing systems and methods and, particularly, to a novel system and method for load balancing a farm of servers hosting clusters of web sites that enables maximal web site customer throughput.
2. Discussion of the Prior Art
In modern world-wide web-based (“web”) computer systems, there currently exists the concept of a farm containing multiple web servers containing facilities for hosting multiple web sites. Sharing common resources such as web servers is very effective, because it is statistically unlikely that busy periods for one web site will correspond to those of another. However, the challenge remains to balance the load on the existing servers effectively, so that maximum customer throughput of the system may be achieved.
Overutilization of servers may cause either web site service interruptions to current customers or rejection of new customer demands, neither of which is desirable. On the other hand, underutilization is wasteful. Consequently, there is presented a real-time scheduling problem which is non-trivial and must be solved satisfactorily if one is to achieve the supposed advantages of a web farm. The server scheduling problem is made more complicated by the fact that some web sites are significantly more popular than others at any given time. Furthermore, this skewed distribution is not stationary: it varies significantly on a weekly, daily, hourly or even a more frequent basis, due to changing web site popularity and customer mix.
It is very likely that the popularity of the hottest web sites will be so great that it takes multiple servers to host them satisfactorily. Thus, it would be highly advantageous to exploit a requirement that multiple servers be available for hosting the highly popular web sites, particularly, by taking advantage of resulting multiple web site copies in order to solve the server load balancing problem very effectively.
SUMMARY OF THE INVENTION
The present invention pertains to an improved method for web site server load balancing by servers available for hosting the highly popular web sites, particularly, by taking advantage of multiple web site copies in order to solve the server load balancing problem very effectively.
According to the principles of the present invention, the load balancing method consists of two components: 1) a static component that functions to create the logical assignment of web sites to servers; and, 2) a dynamic component that performs real-time web site customer scheduling. The static component consists of two stages. First, based on web site demand forecasts, an optimization technique is employed for solving the “apportionment problem” to determine the optimal number of copies per web site. This technique is borrowed from the theory of resource allocation problems, such as described in T. Ibaraki and N. Katoh, “Resource Allocation Problems—Algorithmic Approaches,” The MIT Press, 1988. Second, a method is implemented which makes good quality logical assignments of these optimal number of web site copies to servers. The set of all servers to which a particular web site is assigned is called its ‘cluster’. Note that these clusters may overlap, i.e., the set of web servers is not partitioned. This logical assignment method may be run either in initial or incremental mode. The initial mode is appropriate when configuring a new web cluster farm. Those web sites with multiple copies are assigned first, using a graph-theoretic scheme based on a construct called “clique trees”. Then single copy web sites are assigned, using a Least Loaded First (“LLF”) scheme. The incremental mode allows for constraints which limit the number of copy and logical assignment changes, and is thus practical and appropriate for maintaining high quality web site-to-server assignments. A k-interchange heuristic such as described in the reference to G. Nemhauser and L. Wolsey entitled “Integer and Combinatorial Optimization”, John Wiley and Sons, 1988, the contents and disclosure of which is incorporated by reference as if fully set forth herein, may be employed. The incremental mode is preferably run periodically, e.g., once per week or once per month, etc. However, one could also run this mode when the cluster farm configuration changes, for example when new servers are added to the system. In any case, the exact frequency will depend on the volatility of the web site demand forecasts and the growth in customer activity.
The dynamic component handles the real-time scheduling of web sites customers to servers, based on the output of the static component and on fluctuating web site customer demands. These fluctuations occur because customers arrive and depart, and they do so in a fashion which is not entirely predictable. Thus, according to the invention, a probabilistic approach is aimed at assigning servers to newly arriving customers. A customer who is assigned initially to a particular server will be allowed to complete his activity at that server. However, it is possible that the server will allow existing activity for a particular web site to quiesce naturally, future activity for that web site being assigned to a new server. The actual output of the dynamic component is a set of probabilistic routing choices, one for each web site. Thus, associated with the web site is a set of optimal routing probabilities, one for each server in the cluster, summing to one. A routing probability of 0 indicates that the relevant server is not hosting the web site at the time, i.e., customer activity for that web site is being handled by other servers in the cluster.
Once these routing probabilities have been established the actual assignments of new customers to web sites may be handled in a greedy fashion. If the routing probabilities happen to be equal, for example, this amounts to round-robin scheduling. For a given web site, the active hosts consist of those servers whose routing probabilities are positive. The other servers are not active for this web site-thus, limiting the increase of the spread of active hosts more than necessary. In particular it will never happen that two servers are both simultaneously active for two distinct web sites.
As with the static component there are two stages to the dynamic component: a first stage implementing an optimization technique for solving the “discrete class constrained resource allocation problem” ; and, a second stage that attempts to achieve these load balancing goals by basing the scheduling decision on which server should handle a new customer web site request on the pre-existing probalistic basis.
For the first stage, optimization techniques for solving the discrete class constrained resource allocation problem may be implemented in accordance with techniques described in the references 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 and, A. Tantawi, D. Towsley and J. Wolf, “Optimal Allocation of Multiple Class Resources in Computer Systems”, ACM Sigmetrics Conference, Santa Fe NM, 1988, the contents and disclosure of each of which are incorporated by reference as if fully set forth herein. Particularly, these references describe techniques that may be used for determining optimal load balancing goals at any given moment, given the logical assignments of web sites to servers. Specifically, the output of this stage is the optimal number of web site customers on each server. This problem is repeatedly solved whenever the overall load on the servers changes significantly. Fortunately, the method is fast and incremental in nature.
According to the second stage for achieving load balancing goals, the scheduling decision on which server should handle a new customer web site request is performed on the pre-existing probabilistic basis: Specifically, those servers to which the web site is logically assigned and which already have current act
Wolf Joel L.
Yu Philip Shi-lung
Lim Krisna
Scully Scott Murphy & Presser
Zarick, Esq. Gail H.
LandOfFree
Method and apparatus for load balancing of web cluster farms does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for load balancing of web cluster farms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for load balancing of web cluster farms will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2924539