Calculating numbers of servers for tiers of a multi-tiered system

1. A method comprising:

calculating, by at least one processor, fractional, non-integer numbers of servers for respective tiers of a multi-tiered system using a server allocation algorithm; and

computing, by the at least one processor, allocated numbers of servers for respective tiers by rounding up the fractional, non-integer numbers to integer numbers,

wherein calculating the fractional, non-integer numbers of servers for respective tiers of the multi-tiered system using the server allocation algorithm comprises using a Lagrangian multiplier technique.

2. The method of claim 1 , wherein the allocated numbers of servers for respective tiers are approximate numbers, and wherein computing the allocated numbers of servers for respective tiers of the multi-tiered system provides an approximate total system cost that is less than twice an optimal total system cost associated with an optimum solution for numbers of servers for respective tiers.

3. The method of claim 2 , wherein the optimum solution is defined as

min

⁢

⁢

∑

i

=

1

k

⁢

⁢

h

i

⁢

⁢

N

i

s

.

t

.

⁢

∑

i

=

1

k

⁢

⁢

f

i

⁢

⁢

(

N

i

)

≤

T

N 1 , . . . , N k are positive integers,

where h i represents a cost of a server, k represents a number of tiers in the multi-tiered system, and ƒ i (N i ) represents a function for calculating a response time based on a number N i of servers at tier i, i=1 to k.

4. The method of claim 1 , wherein the Lagrangian multiplier technique employs a Lagrangian function,

L

⁢

⁢

(

N

1

,

N

2

,

…

⁢

,

N

k

,

λ

)

=

∑

i

=

1

k

⁢

⁢

h

i

⁢

⁢

N

i

+

λ

⁢

⁢

(

∑

i

=

1

k

⁢

⁢

a

i

N

i

-

b

i

-

T

)

,

where k represents the number of tiers in the multi-tiered system, λ is a Lagrangian multiplier, N 1 represents a number of servers at tier 1 , N 2 represents a number of servers at tier 2 , N k represents a number of servers at tier k, h i represents cost per server at tier i, and

⁢

(

∑

i

=

1

k

⁢

⁢

a

i

N

i

-

b

i

-

T

)

represents a response time constraint.

5. The method of claim 4 , further comprising:

taking the partial derivative of L with respect to N i ; and

solving for N i to compute the fractional, non-integer numbers of servers at respective tiers i, i equals 1 to k.

6. The method of claim 5 , wherein the fractional, non-integer numbers are represented as N i ƒ , i equals 1 to k, and wherein calculating the fractional, non-integer numbers of servers for respective tiers i comprises solving

N

i

f

=

b

i

+

λ

⁢

⁢

a

i

h

i

,

i

=

1

,

…

⁢

,

k

.

7. The method of claim 1 , wherein calculating the fractional, non-integer numbers of servers for respective tiers is based on a response time constraint.

8. The method of claim 1 , wherein calculating the fractional, non-integer numbers of servers for respective tiers is based on a constraint including an average response time.

9. The method of claim 1 , wherein computing the allocated numbers of servers for respective tiers provides a feasible solution that satisfies a response time constraint.

10. A machine-readable storage medium containing instructions that upon execution by at least one processor cause a system to:

calculate fractional, non-integer numbers of servers for respective tiers of a multi-tiered system using a server allocation algorithm; and

compute allocated numbers of servers for respective tiers by rounding up the fractional, non-integer numbers to integer numbers,

wherein calculating the fractional, non-integer numbers of servers for respective tiers of the multi-tiered system using the server allocation algorithm comprises using a Lagrangian multiplier technique.

11. The machine-readable storage medium of claim 10 , wherein the allocated numbers of servers for respective tiers are approximate numbers, and wherein computing the allocated numbers of servers for respective tiers of the multi-tiered system provides an approximate total system cost that is less than twice an optimal total system cost associated with an optimum solution.

12. The machine-readable storage medium of claim 10 , wherein calculating the fractional, non-integer numbers of servers for respective tiers is based on an average response time constraint.

13. The machine-readable storage medium of claim 12 , wherein computing the allocated numbers of servers for respective tiers provides an approximate total system cost that is greater than an optimal system cost associated with an optimal solution.

14. A method comprising:

computing, by at least one processor, numbers of servers for respective tiers of a multi-tiered system using a server allocation algorithm, wherein the computed numbers of servers are part of an approximate solution in which the server allocation algorithm calculates fractional, non-integer numbers of servers for the respective tiers, wherein the computed numbers of servers are rounded up from the fractional, non-integer numbers;

computing, by the at least one processor, a first cost for the computed numbers of servers for respective tiers of the multi-tiered system, wherein the first cost is less than m times a cost associated with an optimal solution for the numbers of servers in the respective tiers of the multi-tiered system, wherein m is greater than 1; and

computing, by the at least one processor, a second cost based on the fractional, non-integer numbers of servers for the respective tiers.

15. The method of claim 14 , wherein computing the numbers of servers for respective tiers of the multi-tiered system uses the server allocation algorithm in which a constraint that the numbers of servers for the respective tiers are integers is relaxed.

16. The method of claim 14 , wherein computing the numbers of servers for the respective tiers of the multi-tiered system uses the server allocation algorithm that includes a Lagrangian multiplier technique.

17. The method of claim 16 , wherein computing the numbers of servers for the respective tiers is performed by using the Lagrangian multiplier technique to compute a closed-form solution for a relaxed optimization problem in which a constraint that the numbers of servers for the respective tiers are integers is relaxed.

18. The method of claim 14 , wherein computing the first cost comprises computing the first cost that is less than twice the cost associated with the optimal solution.

19. The method of claim 14 , wherein the multi-tiered system has k tiers, and wherein the numbers of servers for respective tiers comprise N i r , i=1 to k, the method further comprising:

calculating N i ƒ , i=1 to k, for the respective k tiers, wherein N i ƒ , i=1 to k, comprise the fractional, non-integer numbers,

wherein computing N i r , i=1 to k, is based on rounding up N i ƒ , i=1 to k, to respective integer values.

20. A system comprising:

a processor; and

a server allocation module executable on the processor to perform a server allocation algorithm to allocate numbers of servers in respective plural tiers of a multi-tiered server system,

wherein the server allocation module computes the allocated numbers of servers in the respective plural tiers based on calculating fractional, non-integer numbers of servers for respective tiers,

wherein the server allocation module calculates the fractional, non-integer numbers of servers for respective tiers by using a Lagrangian multiplier technique.

21. The system of claim 20 , wherein the server allocation module is executable to compute a total system cost associated with the allocated numbers of servers for the respective tiers, wherein the total system cost associated with the allocated numbers of servers is greater than a total system cost associated with an optimal solution for numbers of servers for the respective tiers.

22. The system of claim 20 , wherein the allocated numbers of servers is an approximate but feasible solution that satisfies a response time constraint.

23. A system comprising:

means for calculating fractional, non-integer numbers of servers for respective tiers of a multi-tiered system using a server allocation algorithm; and

means for rounding up the fractional, non-integer numbers of servers for the respective tiers to derive integer numbers of servers for the respective tiers of the multi-tiered system, the integer numbers of servers representing an approximate, feasible solution that satisfies an average response time constraint, wherein the server allocation algorithm uses a Lagrangian multiplier technique.

24. A system comprising:

a processor; and

a server allocation module executable on the processor to calculate fractional, non-integer numbers of servers for respective tiers of a multi-tiered system using a server allocation algorithm that includes a Lagrangian multiplier technique, wherein the Lagrangian multiplier technique employs a Lagrangian function,

L

⁢

⁢

(

N

1

,

N

2

,

…

⁢

,

N

k

,

λ

)

=

∑

i

=

1

k

⁢

⁢

h

i

⁢

⁢

N

i

+

λ

⁢

⁢

(

∑

i

=

1

k

⁢

⁢

a

i

N

i

-

b

i

-

T

)

,

where k represents the number of tiers in the multi-tiered system, k is a Lagrangian multiplier, N 1 represents a number of servers at tier 1 , N 2 represents a number of servers at tier 2 , N k represents a number of servers at tier k, h i represents cost per server at tier i, and

(

∑

i

=

1

k

⁢

⁢

a

i

N

i

-

b

i

-

T

)

represents a response time constraint,

the server allocation module to further take the partial derivative of L with respect to N i , and to solve for N i to compute the fractional, non-integer numbers (N i ƒ ) of servers at respective tiers i, i equals 1 to k,

the server allocation module to further round up the fractional, non-integer numbers N i ƒ of servers for the respective tiers to derive integer numbers of servers for the respective tiers of the multi-tiered system, the integer numbers of servers representing an approximate, feasible solution that satisfies the response time constraint.