System for balance distribution of requests across multiple servers using dynamic metrics

• US 6,938,256 B2
• Filed: 01/18/2001
• Issued: 08/30/2005
• Est. Priority Date: 01/18/2000
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Galactic Computing Corp.
• Inventors: O'Brien, Thomas O., Giustozzi, Joseph, Engel, Stephen J., Deng, Yuefan
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Truong, Camquy
• Application Number:
  US09/765,766
• Publication Number:
  US 20010039581A1
• Time in Patent Office: 1,685 Days
• Field of Search: 718/104, 718/101
• US Class Current: 718/104
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/3442 for planning or managing the needed capacity
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1021 based on client or server locations

Abstract

A system for distributing incoming client requests across multiple servers in a networked client-server computer environment processes all requests as a set that occur within a given time interval and collects information on both the attributes of the requests and the resource capability of the servers to dynamically allocate the requests in a set to the appropriate servers upon the completion of the time interval. Preferably, the system includes a request table to collect at least two requests incoming within a predetermined time interval. A request examiner routine analyzes each collected request with respect to at least one attribute. A system status monitor collects resource capability information of each server in a resource table. An optimization and allocation process distributes collected requests in the request table across the multiple servers upon completion of said time interval based on an optimization of potential pairings of the requests in the request table with the servers in the resource table. The optimization and allocation process preferably analyzes metrics maintained in the request table and resource table as part of a relational database to allocate requests to servers based on a minimization of the metric distance between pairings of requests and servers. Preferably, the request table is part of a dynamic, relational database and a process of statistical inference for ascertaining expected demand patterns involving said the attributes adds predictive information about client requests as part of the request examiner routine.

Claims

1. A method for distributing incoming client requests across multiple servers in a networked client-server computer environment comprising:

(a) collecting client requests incoming within a predetermined time interval;

(b) upon receipt of the at least two incoming client requests within the predetermined time interval, analyzing each of the client requests using categorical criteria and demographic criteria to extract attributes of the request;

(c) classifying the client requests based on the extracted attributes by comparing each request with a pattern selected from a set of patterns in an adaptive request table to find a match-pattern that best matches the request;

(d) using the match-pattern to associate a requirements vector with each request, the requirements vector being populated with at least five resource parameters that prescribe the expected resource requirements of the request;

(e) capturing resource capability information for each server at least once during the predetermined time interval, each server being associated with a capability vector refreshed with the resource capability information;

(f) following steps (d) and (e), for each client request and server pair, computing a vector space distance between the requirement vectors and capability vectors corresponding to the client request and the server respectively, the vector space distance being an update to an element in a cost matrix initialized at the start of the predetermined time interval;

(g) at the completion of the time interval, distributing the client requests across multiple servers to minimize a cost metric associated with the cost matrix for all combinations of client requests and server resource capabilities; and

(h) repeating steps (a) through (g) for subsequent ones of said time interval after initializing the cost matrix.

2. The method of claim 1, wherein said resource capability information comprises a resource capability metric for each of at least five resource parameters for each server, regarding the server'"'"'s CPU availability, memory availability, connectivity to storage, connectivity to a proxy server, and connectivity to peer servers.

3. The method of claim 2, wherein said method further comprises the step of providing a dynamic, relational database and process of statistical inference for ascertaining expected demand patterns involving said at least one attribute.

4. The method of claim 3, wherein the number of said expected demand patterns can dynamically increase or decrease.

5. The method of claim 3, wherein a resource requirement metric for each of said at least five resource parameters is assigned to each said expected demand pattern, wherein each said collected request is identified with at least one said expected demand pattern, and wherein said resource requirement metrics assigned to said identifying expected demand pattern are further assigned to said collected request.

6. The method of claim 5, further comprising the steps of determining the metric distance between said resource requirement metrics and said resource capability metrics for at least one combination of said collected client request and server pairings and selecting a server for each said collected request so that the sum of said metric distances for said at least one combination of said pairings is minimized.

7. The method of claim 6, wherein an optimization paradigm is used to at least partially perform the step of selecting a server for each said collected request so that the sum of said metric distances for said at least one combination of said pairings is minimized.

8. A system for servicing multiple requests to be distributed across multiple servers in a networked client-server computer environment, the system comprising:

a request examiner routine for analyzing each of the client requests incoming within a predefined time interval, using categorical criteria and demographic criteria to extract attributes of the request;

a request table for collecting attribute information associated with each client request incoming within the predetermined time interval;

an adaptive request table populated with a set of patterns, each pattern associated with a generic request type that is most likely to be received by a proxy server, the adaptive request table suited for classifying client requests by comparing each request with a pattern selected from the set of patterns in the adaptive request table to find a match-pattern that best matches the client request resulting in a successful match, so that an expected demand on resources by the client request can be predicted using the match-pattern in the adaptive request table to associate a requirements vector with each request, the requirements vector being populated with at least five resource parameters that prescribe the expected demand on resources imposed by the request;

a relational database coupled with a process of statistical inference to facilitate the construction of an adaptive request table, the adaptive request table being updated by the process of statistical inference for each match-pattern resulting from a successful match of the client request with the set of patterns;

a resource table for collecting resource capability information about each server at least once during the predetermined time interval wherein each server is associated with a capability vector refreshed with the resource capability information;

a cost matrix initialized at the start of the time interval, the cost matrix characterized by a row index associated with a request identifier and a column index associated with a resource identifier, each element in the cost matrix representing a vector space distance between the requirements vector corresponding to the client reguest and the capability vector corresponding to the server resource;

a distance vector computing process for computing the vector space distance between the requirements vector and the capability vector for each pairing of the client request and the server resource; and

an optimization and allocation process for selecting a server resource for receiving each client request so that a sum of all costs in the cost matrix is minimized for all combinations of client requests and server resources.

9. The system of claim 8, wherein said resource capability information comprises a resource capability metric for each of at least a plurality of resource parameters for each server selected from the set comprising:

the server'"'"'s CPU availability, memory availability, connectivity to storage, connectivity to a proxy server, connectivity to peer servers, and connectivity to the Internet.

10. The system of claim 8, wherein the relational database is dynamic and wherein the number of said patterns can dynamically increase or decrease.

11. The system of claim 8, wherein the requirements vector associated with one request among the client requests incoming within the predefined time interval is further assigned to all said client requests incoming within the predefined time interval.

12. The system of claim 8, wherein the optimization and allocation process for selecting a server resource for receiving each client request is configured so that the sum of all costs in the cost matrix is minimized for at least one combination of client requests and server resources.

13. The system of claim 8, wherein a global optimization paradigm is used to minimize a total assignment cost for the said all combinations of client requests and server resources.