System and method for allocating server resources

• US 7,581,008 B2
• Filed: 11/12/2003
• Issued: 08/25/2009
• Est. Priority Date: 11/12/2003
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhang, Alex, Tang, Hsiu-Khuem, Santos, Cipriano A., Beyer, Dirk M.
• Primary Examiner(s): Osman; Ramy M
• Application Number:
  US10/706,401
• Publication Number:
  US 20050102398A1
• Time in Patent Office: 2,113 Days
• Field of Search: 709/223, 709/224, 709/226, 709/229, 709/201, 709/203, 703/2, 703/23
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A system and method employing an allocation process for determining the number of server machines at each tier of a multiple tiered server system. The allocation process evaluates the number of server machines at each tier sufficient to achieve an average response time of a transaction request to be processed by the server system in response to changes in the average number of transaction requests. The allocation process also identifies shadow pricing enabling analysis of the cost associated with incremental changes in the average response time or other critical system resources.

Claims

1. A server system comprising:

at least two scaleable tiers of server machines;

a server pool including plural spare server machines;

means for computing an average response time for the server system to respond to transaction requests at the two scaleable tiers of server machines; and

means for increasing a number of server machines processing transactions for each of the two scaleable tiers of server machines by allocating the spare server machines to process a portion of the transactions, wherein the spare server machines are allocated to process a portion of the transactions when the average response time for the server system to respond to the transaction requests is greater than or equal to a specified average response time, wherein said means for computing further comprises a non-iterative queuing model for predicting the average response time for the server system in response to measured arrival rates of transaction requests into each of the two scaleable tiers of server machines, an average service demand at each of the two scaleable tiers of server machines, and a number of servers allocated to each of the two scaleable tiers of server machines.

2. The server system of claim 1 further comprising means for determining costs associated with allocating the number of server machines at each of the two scaleable tiers of server machines.

3. The server system of claim 2 wherein said means for determining further comprises means for minimizing costs associated with allocating an optimized number of server machines at each of the two scaleable tiers of server machines.

4. The server system of claim 3 wherein said means for minimizing comprises:

means operatively coupled to said server system for receiving input parameters and for solving;

$\sqrt{\mathrm{\gamma <br><br>}}=\frac{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>\sqrt{h_i<br><br>s_i<br><br>u_i}}{T-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>s_i};<br><br>$

where;

γ

is a shadow price of the average response time;

h₁, h₂, . . . h_n are weights reflecting a cost of different types of servers located at each of the two scaleable tiers of server machines;

s is an average service time;

u is a measured average utilization rate expressed in a single-machine percentage; and

T is the average response time.

5. The server system of claim 1, wherein the average response time is determined by examining a time that the transaction requests are pending at each of the two scaleable tiers of server machines.

6. The server system of claim 1 further comprising:

a contractual relationship between a system operator and at least one contracting party; and

means for adjusting prices charged by said system operator to at least one third party in response to a change in an allocation of server machines in each of the two scaleable tiers of server machines.

7. A method for allocating a server machine to at least two tiers of a server system, said method comprising:

computing, by a computer, an expected average response time as a function of transaction requests and an amount of resources allocated to each of the two tiers of the server system;

determining whether an optimization problem is feasible;

computing a lower bound and an upper bound on a number of server machines at each of the two tiers of said server system required to meet the average response time;

computing a solution specifying a number of server machines allocated to each of the two tiers of said server system;

computing an average time that transaction requests are pending at each of the two tiers;

automatically increasing the number of server machines, from a pool of server machines, allocated to one of the two tiers at a point in time when the average time the transaction requests are pending at the one of the two tiers is greater than or equal to a pre-determined limit; and

predicting, with a non-iterative queuing model, an average server system response time in response to measured arrival rates of transaction requests into said two tiers of server machines, an average service demand at said two tiers of server machines; and

a number of servers allocated to said two tiers of server machines.

8. The method of claim 7 wherein said computing an expected average response time further comprises:

obtaining at least one input value for an average arrival rate of transaction requests into each of the two tiers of said server system;

obtaining at least one input value for an average service demand at each of the two tiers of said server system; and

obtaining at least one input value for the number of server machines allocated at each of the two tiers of said server system.

9. An assembly for allocating server machines in a server system comprising:

at least two tiers of server machines;

a pool of spare server machines that process transactions for the two tiers of server machines;

means for computing an average response time for said two tiers of server machines to respond to a plurality of transaction requests; and

means for increasing and decreasing a number of server machines from said pool that process transactions for said two tiers of server machines when average response times for processing transactions at the two tiers of server machines exceed a specified average response time, wherein said means for computing further comprises a non-iterative queuing model for predicting an average server system response time in response to measured arrival rates of transaction requests into said two tiers of server machines, an average service demand at said two tiers of server machines, and a number of servers allocated to said two tiers of server machines.

10. The assembly of claim 9, wherein the average response time is determined by examining a time that the transaction requests are pending at the two tiers of server machines.

11. The assembly of claim 9 further comprising:

a contractual relationship between a system operator and at least one contracting party; and

means for adjusting prices charged by said system operator to said at least one contracting party in response to a change in an allocation of server machines in said two tiers of server machines.

12. A server system comprising:

an open queuing network of multiple server machines with each server machine having a processor-sharing queue with a single critical resource;

at least two tiers of server machines; and

a computer-readable medium comprising instructions for;

(i) predicting an average system response time of said multiple server machines based on an arrival rate of transaction requests into each of the two tiers of server machines averaged over all transaction request types and a number of server machines allocated at each of the two tiers of server machines;

(ii) solving a mathematical representation of an optimization objective and constraints of said server system;

(iii) determining a number of server machines for each of the two tiers of server machines in response to said predicted the average system response time;

(iv) automatically increasing the number of server machines, from a pool of server machines, processing transactions for each of the two tiers of server machines at a point in time when an average time that transactions requests are pending at the two tiers of server machines exceeds a threshold; and

(v) predicting, with a non-iterative queuing model, an average server system response time in response to measured arrival rates of transaction requests into said two tiers of server machines, an average service demand at said two tiers of server machines, and a number of servers allocated to said two tiers of server machines.

13. The server system of claim 12 wherein said mathematical representation comprises:

a continuous-relaxation model of a mathematical optimization system; and

an iterative bounding procedure.

14. The server system of claim 12 wherein said instructions for determining the number of server machines for each of the two tiers of server machines is in response to a predicted average system response time and at least one service level agreement (SLA) requirement.