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

• US 20010039581A1
• Filed: 01/18/2001
• Published: 11/08/2001
• Est. Priority Date: 01/18/2000
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Galactic Computing Corp.
• Inventors: OʼBrien, Thomas, Engel, Stephen J., Deng, Yuefan, Giustozzi, Joseph
• Granted Patent: US 6,938,256 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• 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, said method comprising the steps of:

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

(b) analyzing each said collected client requests with respect to at least one attribute;

(c) collecting resource capability information of each server;

(d) upon completion of said time interval, distributing said collected client requests across the multiple servers in response to in response to the attributes of said collected client requests and the resource capability information of the multiple servers; and

(e) repeating steps (a) through (d) for subsequent ones of said time interval.

2. The method of

claim 1

, wherein the attributes analyzed in step (b) are selected from the set comprising:

categorical criteria and demographic criteria

3. 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.

4. The method of

claim 3

, wherein said method wherein step (a) 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.

5. The method of

claim 4

, wherein the number of said expected demand patterns can dynamically increase or decrease.

6. The method of

claim 4

, 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.

7. The method of

claim 6

, wherein the step (d) further comprises determining the metric distance between said resource requirement metrics and said resource capability metrics for at least one combination of said collected 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.

8. The method of

claim 7

, wherein an optimization paradigm is used to at least partially perform step (d).

9. A method for distributing incoming client requests across multiple servers in a networked client-server computer environment, said method comprising the steps of:

(a) collecting at least two requests incoming within a predetermined time interval;

(b) analyzing each of said collected request with respect to at least one attribute;

(c) analyzing said at least one attribute for ascertaining statistical patterns across said collected requests;

(d) identifying at least one resource parameter for said servers.

(e) collecting a resource capability metric of each server for said at least one resource parameter;

(f) assigning a resource need metric for said at least one resource parameter to each statistical pattern;

(g) correlating each of said collected requests with at least one said statistical pattern;

(h) assigning said metric for said at least one resource parameter assigned to said statistical pattern correlated to said collected request;

(i) determining a metric distance between a resource need metric and a resource capability metric for at least one combination of a pairing of said collected request and one of said servers;

(j) upon completion of said time interval, selecting a server for each of said collected request so that a sum of said metric distances for said pairings is minimized; and

(k) repeating steps (a) through (j) for consecutive ones of said time intervals.

10. The method of

claim 9

, wherein the attributes analyzed in step (b) are selected from the set comprising:

categorical criteria and demographic criteria.

11. The method of

claim 9

, wherein said at least one resource capability metric comprises metrics chosen 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.

12. The method of

claim 11

, wherein step (g) said method further comprises the step of providing a dynamic, relational database and process of statistical inference for ascertaining said statistical patterns.

13. The method of

claim 9

, wherein the number of said statistical patterns can dynamically increase or decrease.

14. The method of

claim 9

, wherein an optimization paradigm is used to select a server.

15. A system for distributing incoming client requests across multiple servers in a networked client-server computer environment, said system comprising;

a request table to collect at least two requests incoming within a predetermined time interval;

a request examiner routine to analyze each said collected request with respect to at least one attribute;

a system status monitor to collect resource capability information of each server; and

an optimization and allocation process to distribute said collected requests in said table across the multiple servers upon completion of said time interval in response to said request table and said resource capability information.

16. The system of

claim 15

, wherein there are at least two said time intervals and said time intervals are consecutive.

17. The system of

claim 15

, wherein the table is maintained as a relational database and further comprising process of statistical inference to ascertain expected demand patterns involving said at least one attribute.

18. The system of

claim 15

, wherein said resource capability information comprises a resource capability metric for each of at least a plurality of resource parameters for each serverselected 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.

19. The system of

claim 15

, wherein the database is dynamic and wherein the number of said expected demand patterns can dynamically increase or decrease.

20. The system of

claim 15

, wherein a resource requirement metric for each of said at least five resource parameters is assigned to each of said expected demand pattern, wherein each said collected request is correlated with at least one said expected demand pattern, and wherein said resource requirement metrics assigned to said correlated expected demand pattern are further assigned to said collected request.

21. The system of

claim 20

, wherein the process of distributing said collected requests further comprises determining the metric distance between said resource requirement metrics and said resource capability metrics for at least one combination of a pairing of said collected request and server and selecting a server for each said collected requests so that the sum of said metric distances for said at least one combination of said pairings is minimized.

22. The system of

claim 21

, wherein a global optimization paradigm is used to minimize a total assignment cost for said pairings of all of said servers and said requests.