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

• US 8,302,100 B2
• Filed: 08/12/2005
• Issued: 10/30/2012
• Est. Priority Date: 01/18/2000
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Galactic Computing Corporation Bvi/Bc
• Inventors: O'Brien, Thomas, Giustozzi, Joseph, Engel, Stephen J., Deng, Yuefan
• Primary Examiner(s): Truong, Camquy
• Application Number:
  US11/202,644
• Publication Number:
  US 20060036743A1
• Time in Patent Office: 2,636 Days
• Field of Search: 718/104
• 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 the attributes of the requests and the resource capability of the servers to dynamically allocate requests in a set to the appropriate servers upon completion of the time interval. Preferably, a request table collects 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 and 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 servers in the resource table.

Claims

1. A method for allocating a server, selected from a plurality of servers, to client requests originating over a predefined time interval at a plurality of user accounts, the method comprising:

collecting a plurality of client requests that arrive within the predefined time interval wherein at least two of said client requests are serviceable by the server and wherein a first of said at least two of said client requests originates at a first user account and a second of said at least two of said client requests originates at a second user account;

determining a first value of a cost metric for a first set of client request-server pairings wherein said first set includes at least one client request-server pair with said server being paired with either said first or said second of said at least two client requests;

determining a second value of a cost metric for a second set of client request-server pairings wherein said second set includes at least one client request-server pair with said server being paired with both said first and said second of said at least two client requests; and

at the end of said predefined time interval distributing said client requests according to one of said first and said second set of client request-server pairings based on said first and second values of said cost metric;

wherein the step of determining the first or the second value of a cost metric for the first or the second set of client request-server pairings further comprises the steps of;

initializing the first or second set of client request-server pairings at a commencement of the predefined time interval;

a) selecting a client request-server pair to satisfy a selection criteria;

b) creating a requirement vector corresponding to said client request;

c) creating a capability vector corresponding to said server;

d) calculating a distance between the requirement vector and the capability vector and adding said distance to a cumulative value when said distance exceeds a match threshold value and repeating steps a), b), c) and d); and

e) adding said client request-server pair to said set of client request-server pairings when said distance exceeds the match threshold value, said cumulative value is less than a cost threshold and said client request has arrived within said predefined time interval.

2. The method of claim 1 wherein the step of determining the value of the first or the second cost metric for the first or the second set of client request-server pairings comprises the steps of:

at the commencement of said predefined time interval, initializing a cumulative value to zero;

for each client request-server pair in the first or the second set of client request-server pairings,

a) creating a requirement vector corresponding to said client request;

b) creating a capability vector corresponding to said server;

c) calculating an inner product of said requirement vector and said capability vector and adding said inner product to the cumulative value and repeating steps a), b) and c) for all client request-server pairs in the first or second set of client request-server pairings whereupon said cumulative value represents the value of the cost metric.

3. The method of claim 1 wherein the step of distributing said client requests further comprises distributing said client requests according to said first set of client requests-server pairings if said first value of the cost metric is lower than the second value of the cost metric otherwise distributing said client requests according to said second set of client requests-server pairings.

4. The method of claim 1 wherein said selection criteria comprises matching a client request with a server to generate at least one client request-server pairing belonging to one of said first set and said second set.

5. A system for distributing load within a client-server computer network, comprising:

a plurality of interconnected computer servers, each server having at least one processor, wherein each computer server is associated with a capability vector having at least one element associated with a resource expected to be requested by at least one of a plurality of incoming client requests;

a dynamic capability vector determining module configured to generate a dynamic capability vector for each server of said plurality of interconnected servers, said dynamic capability vector representing an update to said capability vector such that the at least one element of the capability vector corresponds to an unused portion of the resource associated with the at least one element and measured at the commencement of one of a sequence of predefined time intervals;

a requirement vector determining module configured to generate a requirement vector for each incoming client request during the one of the sequence of predefined time intervals; and

a load balancing module for selectively pairing said plurality of interconnected computer servers with one or more of said plurality of incoming client requests so as to minimize a cost metric computed during the one predefined time interval in said sequence of predefined time intervals wherein said cost metric is a function of vector distances between said dynamic capability vectors and said requirement vectors associated with said computer servers and said client request pairs in said computer server-client request pairing;

wherein said load balancing module further comprises a plurality of instances of load balancing modules resident on an appropriate plurality of servers disposed at intermediate nodes forming a connectivity hierarchy of layers throughout said computer client-server network such that said cost metric is computed and minimized for at least one layer of server nodes corresponding to the same connectivity hierarchy whereby each incoming client request is satisfied by a plurality of computer servers and transmission paths.