Patent Publication Number: US-7594016-B1

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

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This is a continuation-in-part of U.S. Ser. No. 10/706,401, filed Nov. 12, 2003, which is incorporated by reference herein. 
   This is a continuation-in-part of U.S. Ser. No. 11/116,728, entitled “Allocation of Resources for Tiers of a Multi-Tiered System Based On Selecting Items From Respective Sets,” and of U.S. Ser. No. 11/117,197, entitled “Allocating Resources in a System Having Multiple Tiers,” both filed on Apr. 28, 2005, and both hereby incorporated by reference. 

   BACKGROUND 
   Web-based resources, such as online information, online retail sites, and other web resources, are widely available to users over networks such as the Internet and intranets. Access to a web resource is provided by a website, which is typically implemented with a server system having one or more servers. Traffic at a popular website can be relatively heavy. If an insufficient number of servers are allocated to a website, then response times experienced by users when visiting the website can be long. 
   Typically, a server system that provides a website has a multi-tiered architecture that includes multiple tiers of servers. A user request submitted to the server system is typically processed by all the tiers. Thus, the total response time for a user request is the sum of the response times at respective tiers. The expected response time at each tier depends upon the number of servers allocated to the tier. 
   A web-based, multi-tiered architecture typically includes three tiers of servers: web servers, application servers, and database servers. Web servers communicate with the user (at a client system) and serve as the interface between the application servers and the user. Application servers parse user requests and perform predefined computations. Application servers in turn communicate with database servers to access requested information. 
   Conventional techniques have been proposed to allocate an adequate number of servers to each tier of a multi-tiered architecture to meet a desired response time constraint. However, conventional techniques for allocating the number of servers in each tier of a multi-tiered architecture employ algorithms that have processing times related exponentially to the input problem size. In other words, as the number of tiers of the multi-tiered server system increases, the processing time for computing the allocation of servers in each tier increases exponentially. Consequently, the amount of processing time involved in performing server allocation using conventional techniques for a multi-tiered server system can be relatively large. Also, conventional techniques are inflexible in that, in a particular system, users typically are limited to using one server allocation algorithm to address the server allocation issue. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram of server systems and a server management system according to an embodiment of the invention. 
       FIG. 2  is a flow diagram of a process performed by a server allocation module executable in the server management system, in accordance with an embodiment. 
   

   DETAILED DESCRIPTION 
     FIG. 1  illustrates components of an example multi-tiered server system  100 A, which includes multiple tiers of servers. The server system  100 A includes a first tier of web servers  102 , a second tier of application servers  104 , and a third tier of database server(s)  106 . In one example, the server system  100 A is used for web-based applications (e.g., e-commerce, search engine, web service, and so forth). However, in other embodiments, the multi-tiered server system can include other types of servers for other applications, such as storage applications, utility computing shared environment applications, and so forth. Also, even though three tiers are depicted for the server system  100 A in  FIG. 1 , it is contemplated that other multi-tiered server systems can include other numbers of tiers, such as two or greater than three. 
     FIG. 1  also shows another multi-tiered server system  10 B, which can be configured in similar manner as server system  100 A, or can be configured differently with different types of servers and different numbers of tiers. The example arrangement of  FIG. 1  also shows a server pool  108 , which includes a number of spare servers that are dynamically allocated to either server system  100 A or server system  100 B to expand the capacity of the server system  100 A or  100 B based on demands experienced by either server system  100 A or  100 B. In the embodiment of  FIG. 1 , the server pool  108  includes spare web servers  110 , spare application servers  112 , and spare database servers  114 . One or more of each of the spare web servers  110 , spare application servers  112 , and spare database servers  114  are dynamically added to corresponding tiers of either the server system  100 A or server system  100 B to dynamically expand capacity at each respective tier. 
   For example, as user traffic at a server system increases, servers from the server pool  108  are added to one or more tiers of the server system to assure that average user response time is below some predefined threshold. In some cases, the predefined threshold is specified by a service level agreement (SLA) entered between the provider of the server system and another party, such as the party providing the e-commerce service, search engine service, or web service, as examples. 
   A “server” refers to a computer, a collection of computers, or any part of a computer (whether software or hardware or a combination of both). 
   As depicted in  FIG. 1 , client systems  116  are able to access the web servers  102  to issue requests (e.g., user requests) to the server system  100 A. The same client systems  116 , or other client systems, can issue requests to the server system  100 B. 
   A server management system  118  (implemented as a computer in some embodiments) is coupled to the server systems  100 A,  100 B, and server pool  108 . The server management system  118  includes a server allocation module  120 , which in one example implementation is a software module (or plural software modules) executable on one or plural central processing units (CPUs)  122  in the server management system. The CPU(s)  122  is (are) coupled to storage  124 . 
   The server management system  118  also includes a server monitor  126  that is executable on the CPU(s)  122 . The server monitor  126  is used to monitor the status of each server system  100 A,  100 B. The server monitor  126  receives data (e.g., amount of user traffic, etc.) from each server system  100 A,  100 B and stores the data in the storage  124  for use by the server allocation module  120 . Note that the tasks performed by the server monitor  126  and by the server allocation module  120  can be combined such that a single software module performs the tasks. Alternatively, the tasks can be performed by a larger number of software modules. 
   Also, although described in the context of software modules, it is contemplated that the server allocation and server monitoring tasks can be performed by hardware, or by a combination of hardware or firmware, in other embodiments. 
   The server allocation module  120  is able to dynamically allocate a number of servers to each tier of a multi-tiered server system ( 100 A or  100 B) depending upon the incoming workload (requests from client systems). The server allocation module  120  computes a number of servers allocated to each tier such that the total server system cost is reduced while a desired average response time is achieved for requests from the client systems  116 . Average response time is one example of a response time constraint. Another example of a response time constraint includes maximum response time. Based on information collected by the server monitor  126 , additional resources (in the form of servers) are dynamically allocated by the server allocation module  120  from the server pool  108  to the server system  100 A or  100 B to add resources to each tier to achieve the desired average response time. In another embodiment, the server allocation module  120  is able to allocate numbers of servers to respective tiers of a multi-tiered server system without using data from the server monitor  126 . 
   Although reference is made to allocating servers to tiers of a server system, it is contemplated that other types of resources (e.g., CPUs, memory, etc.) can be allocated to plural tiers of any multi-tiered computer, according to alternative embodiments. 
   In accordance with some embodiments of the invention, for enhanced flexibility, the server allocation module  120  selects one of multiple server allocation algorithms to use for determining a system configuration (that includes a number of servers in each tier of the multi-tiered server system) such that total system cost is minimized while a response time constraint is satisfied. 
   In one embodiment, the server allocation module  120  is able to selectively use one of three algorithms, including a first server allocation algorithm  128 , a second server allocation algorithm  130 , and a third server allocation algorithm  132 . In other embodiments, a smaller number or larger number of server allocation algorithms can be selectively used. 
   The first server allocation algorithm  128  (referred to as the “two-approximation algorithm”) is relatively fast since the first server allocation algorithm  128  computes an approximate solution with a total system cost that is at most twice the optimal cost. More generally, the first server allocation algorithm  128  computes an approximate solution with a total system cost that is at most m times the optimal cost, where m is greater than one. The term “optimal cost” refers to the minimum cost that can be achieved by an optimum configuration of the multi-tiered server system while still satisfying the response time constraint. 
   The second server allocation algorithm  130  (referred to as the “pseudo-polynomial-time exact algorithm”) computes an optimal (or exact) solution, rather than an approximate solution, in pseudo-polynomial running time (as contrasted with the exponential running time associated with some conventional techniques for server allocation). The term “pseudo-polynomial running time” refers to the polynomial running time of an algorithm if all input numbers have bounded sizes, where the algorithm typically runs in exponential or other longer running time otherwise. 
   The third server allocation algorithm  132  (referred to as the “fully-polynomial-time approximation algorithm”) computes an approximate solution with the total cost at most (1+ε) times the optimal cost, where the running time is a polynomial in both 1/ε and k, where k is the number of tiers. 
   Note that the first and third algorithms produce feasible solutions regarding the numbers of servers for respective tiers that satisfy the response time constraint, but the solutions are not optimal (but rather are approximate) in the sense that the solutions do not achieve optimal (e.g., minimum) cost. However, the second algorithm produces a solution that achieves optimal (e.g., minimum) cost. Note also that the first algorithm is usually faster than the third algorithm, since the value of ε is a constant between 0 and 1. 
   A property of a multi-tiered server system architecture is that the delay experienced by a request in each tier depends upon the number of servers in that tier and is not affected by the number of servers in any other tier. Thus, according to some embodiments, the response time for a request can be computed by summing the delays in individual tiers to obtain the total response time. 
   In one embodiment, the server allocation module  120  of the server management system  118  uses a response time model that assumes that all servers in the same tier are identical, and that the workload is shared approximately equally among all the servers in the same tier. The server allocation module  120  performs server resource allocation modeled as an integer optimization problem, with one linear objective function and an arbitrary decomposable additive constraint, as follows: 
   
     
       
         
           
             
               
                 
                   min 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       k 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         h 
                         i 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         N 
                         i 
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     s 
                     . 
                     t 
                     . 
                     
                         
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           f 
                           i 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           
                             N 
                             i 
                           
                           ) 
                         
                       
                     
                   
                   ≤ 
                   T 
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   1 
                 
                 ) 
               
             
           
         
       
     
   
   N 1 , . . . , N k  are positive integers. 
   In the equation, h i  represents a cost of a server, and ƒ i (N i ) represents a function for calculating a response time based on a number N i  of servers at tier i. Conventionally, allocating servers to different tiers of a multi-tiered computing system with the objective of minimizing system cost while meeting a response time constraint across all the tiers typically is NP-hard in general (where computation time is exponential). However, according to some embodiments of the invention, polynomial-time approximation algorithms (first and third server allocation algorithms  128  and  132 ) and a pseudo-polynomial-time exact algorithm ( 130 ) are selectively used to allocate server resources. The approximation algorithms run in polynomial time and offer the flexibility to control the tradeoff between solution quality and running time. In other words, approximate server allocation solutions can be computed to quickly obtain results in certain situations. If more accurate results are desired, then the exact algorithm  130  is used. The ability to select one of plural server allocation algorithms provides enhanced flexibility for changing system environments. 
   Use of the approximation algorithms (e.g., first and third server allocation algorithms  128  and  132 ) provide smaller computation times than exponential-time based server allocation algorithms. Also, as described further below, the pseudo-polynomial-time algorithm  130  is transformed into a multi-choice knapsack problem that simplifies the computation of numbers of servers in a multi-tiered server system. 
   Using server allocation techniques according to some embodiments, user control of running time and solution quality is provided. Selection (either by user or the server management system  118 ) of the approximation algorithms (first or third algorithms) results in reduced computation time and reduced solution quality, but selection of the optimal algorithm (second algorithm) results in increased computation time, but increased solution quality. As discussed further below, control of usage of storage space can also be accomplished by selecting a server allocation algorithm with reduced storage usage. 
   In the response time model according to an example implementation, if the request arrival rate is λ i  (incoming workload) for the i-th tier, and this tier has N i  servers, then each server has a request arrival rate of λ i /N i . In one implementation, each server is modeled as a processor-sharing queue. The expected response time is given by the expected time in a system with an M/G/1 queuing model (Poisson distribution for request interarrival density, arbitrary distribution for service processing time, and one single queue with unbounded buffer length): 
                       R   i     ⁢           ⁢     (     N   i     )       =       E   ⁡     [     S   i     ]         1   -       (       λ   i       N   i       )     ⁢           ⁢     E   ⁡     [     S   i     ]               ,           (     Eq   .           ⁢   2     )               
where R i (N i ) represents the average response time of the i-th tier, S i  is a random variable denoting the processing time (or service demand) of a request on a resource (such as a CPU) at the i-th tier, and E[S i ] is the expected processing time of a request on a resource. In other implementations, other queuing models can be employed.
 
   The parameter E[S i ] can be estimated from the measured utilization rate, u i , of the resource as follows: E[S i ]=u i /(λ i /N i ). The average response time, R(N), for a k-tier server system is the sum of the delays in all the tiers. Therefore, 
                     R   ⁢           ⁢     (   N   )       =         ∑     i   =   1     k     ⁢           ⁢       R   i     ⁢           ⁢     (     N   i     )         =       ∑     i   =   1     k     ⁢       E   ⁡     [     S   i     ]         1   -         λ   i     ⁢           ⁢     E   ⁡     [     S   i     ]           N   i                 ,           (     Eq   .           ⁢   3     )               
where N=(N 1 , N 2 , . . . , N k ). The parameter N is referred to as a configuration, and represents the numbers of servers in respective tiers.
 
   From Eq. 3, it follows that there exist multiple server configurations satisfying a given response time constraint. Among these multiple feasible allocations, it is desired to find the one configuration that has the minimum cost. Finding the configuration with the minimum cost can be formulated as the following optimization problem: 
   
     
       
         
           
             
               
                 
                   min 
                   
                     N 
                     i 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     k 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       h 
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       N 
                       i 
                     
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   4 
                 
                 ) 
               
             
           
           
             
               
                 
                   
                     
                       s 
                       . 
                       t 
                       . 
                       
                           
                       
                       ⁢ 
                       R 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       N 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           E 
                           ⁡ 
                           
                             [ 
                             
                               S 
                               i 
                             
                             ] 
                           
                         
                         
                           1 
                           - 
                           
                             
                               
                                 λ 
                                 i 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 E 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     S 
                                     i 
                                   
                                   ] 
                                 
                               
                             
                             
                               N 
                               1 
                             
                           
                         
                       
                     
                     ≤ 
                     
                       T 
                       0 
                     
                   
                 
                 ; 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   5 
                 
                 ) 
               
             
           
         
       
     
   
   N i  integer with N i &gt;λ i E[S i ], for i=1, . . . , k, 
   where T 0  is the response time threshold value and the weights h i  (all assumed to be positive) are the costs of each server in the different tiers. In other words, h i  represents the cost of a server in the i-th tier. In the case where costs are difficult to ascertain, a convenient simplification involves minimizing the total number of servers Σ i=1   k N i ; that is, to set h i =1 for all i. Because: 
                 E   ⁡     [     S   i     ]         1   -         λ   i     ⁢           ⁢     E   ⁡     [     S   i     ]           N   i           =           N   i     ⁢           ⁢     E   ⁡     [     S   i     ]             N   i     -       λ   i     ⁢           ⁢     E   ⁡     [     S   i     ]             =       E   ⁡     [     S   i     ]       +         λ   i     ⁢           ⁢       E   ⁡     [     S   i     ]       2           N   i     -       λ   i     ⁢           ⁢     E   ⁡     [     S   i     ]                   ,         
for all i,
 
the non-linear constraint (Eq. 5) can be further simplified as follows:
 
               ∑     i   =   1     k     ⁢           ⁢         λ   i     ⁢           ⁢       E   ⁡     [     S   i     ]       2           N   i     -       λ   i     ⁢           ⁢     E   ⁡     [     S   i     ]               ≤       T   0     -       ∑     i   =   1     k     ⁢           ⁢       E   ⁡     [     S   i     ]       .               
Let a i =λ i E[S i ] 2 , b i =λ i E[S i ] and T=T 0 −Σ i=1   k E[S i ], then the response time constraint (in this example the average response time constraint) becomes:
 
   
     
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     k 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       a 
                       i 
                     
                     
                       
                         N 
                         i 
                       
                       - 
                       
                         b 
                         i 
                       
                     
                   
                 
                 ≤ 
                 
                   T 
                   . 
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   6 
                 
                 ) 
               
             
           
         
       
     
   
   Note that the response time constraint takes into account the incoming workload, λ i , from each tier i. Even though server allocation is generally NP-hard for a variable number of tiers, real-world systems are usually composed of a relatively small number of tiers. For example, a typical e-commerce application has three tiers. Where the number of tiers is constant, it is possible to solve the server allocation problem in polynomial time or pseudo-polynomial time, using algorithms according to some embodiments. 
     FIG. 2  shows a server allocation process performed by the server allocation module  120  ( FIG. 1 ), according to an embodiment. In response to receiving (at  202 ) a request (such as through the user interface  134 , through the network interface  136 , or from elsewhere) to perform server allocation, the server allocation module  120  determines (at  204 ) which algorithm to select to perform the server allocation. The received request includes a request from a user, or a request automatically initiated in the server management system  118  or from another source. 
   Selection of the algorithm (at  204 ) is based on various factors, including user input, as well as factors relating to how accurate the results should be. For example, a user may expressly indicate which of the three algorithms to use for performing the server allocation process. Alternatively, the server allocation module  120  can determine, from the context of the request, whether the desired server allocation determination is to be highly accurate or just a rough approximation. In one example context, a user may be accessing the server management system  118  ( FIG. 1 ) “on-line” (such as the user interactively using the server management system  118  to obtain answers regarding server allocation in the server system  100 A or  100 B ( FIG. 1 ) to meet incoming workloads). In such a context, use of either the first or third approximation algorithms would likely provide a quicker answer (approximate answer) than the second algorithm. Note that the first algorithm (the two-approximation algorithm) usually also has a faster running time than the third approximation algorithm (depending on the value set for ε in the third approximation algorithm). 
   Thus, in the context where a relatively quick answer is desirable, the server management system  118  ( FIG. 1 ) selects one of the approximation algorithms. In a different context, where computation time is not an issue and a more accurate solution is desirable, the server management system selects the second server allocation algorithm. More generally, the server management system determines, based on one or more conditions, which of the server allocation algorithms to select. The one or more conditions include a specific indication in the request issued by the user (user selection), or other conditions relating to the context in which a request for server allocation was submitted (e.g., user is on-line and would like an answer quickly) which provides some indication of the desired computation time and solution quality. 
   In response to determining that the first algorithm  128  ( FIG. 1 ), which is the two-approximation algorithm, is to be used, the server allocation module  120  relaxes (at  206 ) the constraint that each N i  (the number of servers at the i-th tier) should be an integer. According to the two-approximation algorithm, the Lagrangian multiplier method is used to compute a closed-form solution for the relaxed optimization problem (where the value of each N i  does not have to be integer). The relaxed optimization problem is also referred to as a continuous-relaxation model. According to this algorithm, the output value obtained for each N i  is a fractional (or continuous) value. To be meaningful, the fractional value is rounded up to the nearest integer. Therefore, according to this method, the approximate solution provides a solution with a cost that is less than twice the minimum cost, and at most one extra server per tier. 
   The Lagrangian multiplier method uses a Lagrangian function where λ is the Lagrangian multiplier: 
   
     
       
         
           
             
               
                 
                   L 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     ( 
                     
                       
                         N 
                         1 
                       
                       , 
                       
                         N 
                         2 
                       
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         N 
                         k 
                       
                       , 
                       λ 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       k 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         h 
                         i 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         N 
                         i 
                       
                     
                   
                   + 
                   
                     λ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               1 
                             
                             k 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               a 
                               i 
                             
                             
                               
                                 N 
                                 i 
                               
                               - 
                               
                                 b 
                                 i 
                               
                             
                           
                         
                         - 
                         T 
                       
                       ) 
                     
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   7 
                 
                 ) 
               
             
           
         
       
     
   
   Note that N 1  represents the number of servers at tier  1 , N 2  represents the number of servers at tier  2 , and N k  represents the number of servers at tier k. As discussed above, the expression 
             ∑     i   =   1     k     ⁢           ⁢       h   i     ⁢           ⁢     N   i             
represents the total cost of having N i  servers at tier i for i=1, . . . k (in a k-tier system). The expression
 
           (         ∑     i   =   1     k     ⁢           ⁢       a   i         N   i     -     b   i           -   T     )         
represents the response time constraint. The following equation represents the partial derivative of the expression of Eq. 7 with respect to N i , which is set to zero:
 
   
     
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       L 
                     
                     
                       ∂ 
                       
                         N 
                         i 
                       
                     
                   
                   = 
                   
                     
                       
                         h 
                         i 
                       
                       - 
                       
                         λ 
                         · 
                         
                           
                             a 
                             i 
                           
                           
                             
                               ( 
                               
                                 
                                   N 
                                   i 
                                 
                                 - 
                                 
                                   b 
                                   i 
                                 
                               
                               ) 
                             
                             2 
                           
                         
                       
                     
                     = 
                     0 
                   
                 
                 , 
                 
                   i 
                   = 
                   1 
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   k 
                   . 
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   8 
                 
                 ) 
               
             
           
         
       
     
   
   Solving for N i  in Eq. 8, an optimal fractional value N i   ƒ  is obtained (at  208 ) as follows: 
   
     
       
         
           
             
               
                 
                   
                     N 
                     i 
                     f 
                   
                   = 
                   
                     
                       b 
                       i 
                     
                     + 
                     
                       
                         
                           λ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             a 
                             i 
                           
                         
                         
                           h 
                           i 
                         
                       
                     
                   
                 
                 , 
                 
                   i 
                   = 
                   1 
                 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   k 
                   . 
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   9 
                 
                 ) 
               
             
           
         
       
     
   
   The fractional value N i   ƒ  represents the optimal number (a fractional value) of servers at tier i. Since the N i   ƒ  values are continuous, the non-linear constraint is binding: 
   
     
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     k 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       a 
                       i 
                     
                     
                       
                         N 
                         i 
                         f 
                       
                       - 
                       
                         b 
                         i 
                       
                     
                   
                 
                 = 
                 
                   T 
                   . 
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   10 
                 
                 ) 
               
             
           
         
       
     
   
   Substituting the expression set equal to N i   ƒ  in Eq. 9 into the equality of Eq. 10 and simplifying algebraically, the server allocation module  120  solves (at  210 ) for the Lagrangian function multiplier λ as follows: 
   
     
       
         
           
             
               
                 
                   λ 
                 
                 = 
                 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           
                             h 
                             i 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             a 
                             i 
                           
                         
                       
                     
                     T 
                   
                   . 
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   11 
                 
                 ) 
               
             
           
         
       
     
   
   Then the cost of the relaxed Lagrangian solution is calculated (at  212 ) as follows: 
   
     
       
         
           
             
               
                 
                   cost 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     ( 
                     
                       N 
                       f 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       k 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         h 
                         i 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         N 
                         i 
                         f 
                       
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           h 
                           i 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           b 
                           i 
                         
                       
                     
                     + 
                     
                       
                         
                           
                             ( 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 k 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   
                                     h 
                                     i 
                                   
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     a 
                                     i 
                                   
                                 
                               
                             
                             ) 
                           
                           2 
                         
                         T 
                       
                       . 
                     
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   12 
                 
                 ) 
               
             
           
         
       
     
   
   The optimal fractional solution N i   ƒ  is converted into a feasible two-approximation solution directly by rounding up (at  214 ) the optimal fractional solution N i   ƒ  to an approximate integer solution N i   r . Specifically, N i   r =|N i   ƒ |, for all i. Because N i   r ≧N i   ƒ  for all i, Σ i=1   k a i /(N i   r −b i )≦Σ i=1   k a i (N i   ƒ −b i )=T. Therefore, the rounded up integer values N i   r  for i=1, . . . , k, satisfy the response time constraint and N i   r  is a feasible, approximate solution to the server allocation problem. Furthermore, N i   r  gives a two-approximation to the server allocation problem, in other words, cost (N r )≦2·cost(N*), where N* is an optimal solution. The value cost (N r ) is the cost associated with N i   r  servers in the k tiers (i=1, . . . , k). Usually, the value of cost(N r ) is greater than cost(N*). 
   An output of the two-approximation server allocation algorithm ( 128  in  FIG. 1 ) includes the values N i   r , i=1, . . . , k, which are approximate numbers of servers at respective tiers i. The cost, cost (N r ), associated with implementing these numbers of servers at the tiers i is at most twice the optimal cost, or 2·cost(N*). The computation time for computing the two-approximation server allocation algorithm is linear time (related linearly to the number of tiers). 
   Note that the two-approximation algorithm is applicable to other response time functions as well. 
   If the server allocation module  120  determines (at  204 ) that the algorithm to select is the pseudo-polynomial-time exact algorithm (second server allocation algorithm  130  in  FIG. 1 ), then the server allocation module defines (at  216 ) k sets of items S 1 , . . . , S k  for k tiers. The sets S 1 , . . . , S k  are sets used for a multi-choice knapsack problem. The server allocation problem according to the second server allocation algorithm  130  becomes an algorithm that solves for the multi-choice knapsack problem optimally. The second server allocation algorithm  130  is a pseudo-polynomial-time algorithm that runs in polynomial time if all input numbers are bounded above by a constant. Such algorithms are technically exponential but display polynomial-time behavior in many practical applications. The NP-hard multi-choice knapsack problem is pseudo-polynomial-time solvable using the second algorithm  130  according to some embodiments. 
   The multi-choice knapsack problem is a generalization of the ordinary knapsack problem, in which there are m sets of items S 1 , . . . , S m  with |S i |=n i  for all i and Σ i=1   m n i =n. Each item jεS i  includes a weight w ij  and a profit p ij , and the knapsack has capacity W. The objective is to pick exactly one item from each set, such that the profit sum is maximized and the weight sum is bounded by W. 
   When applied to the server allocation problem with k tiers, the multi-choice knapsack problem includes k sets of items S 1 , . . . , S k . For an item jεS i , parameters weight(j) and cost(j) are calculated (at  218 ) as follows: 
   
     
       
         
           
             
               
                 
                   
                     weight 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       j 
                       ) 
                     
                   
                   = 
                   
                     
                       a 
                       i 
                     
                     
                       j 
                       - 
                       
                         b 
                         i 
                       
                     
                   
                 
                 , 
                 
                   
                     cost 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       j 
                       ) 
                     
                   
                   = 
                   
                     j 
                     · 
                     
                       
                         h 
                         i 
                       
                       . 
                     
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   13 
                 
                 ) 
               
             
           
         
       
     
   
   The parameter weights) represents the response time for j servers in tier i, and the parameter cost(j) represents the cost of j servers at tier i. For the server allocation optimization problem, there is no cost constraint; thus any j&gt;b i  is a feasible item in S i . Thus, each set S i  has plural items j, representing numbers of servers, with each item j associated with parameters weight(j) (response time for j servers) and cost(j) (cost of j servers). 
   To reduce the size of input sets S i , and thus achieve polynomial-time computation time, the number of servers allocated at each tier is bounded within a lower bound n i   l  and an upper bound n i   u , calculated at ( 220 ). Based on the response time constraint, the lower bound n i   l  is defined as follows: 
   
     
       
         
           
             
               
                 
                   
                     
                       a 
                       i 
                     
                     
                       
                         N 
                         i 
                       
                       - 
                       
                         b 
                         i 
                       
                     
                   
                   ≤ 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       k 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         a 
                         i 
                       
                       
                         
                           N 
                           i 
                         
                         - 
                         
                           b 
                           i 
                         
                       
                     
                   
                   ≤ 
                   T 
                 
                 ⇒ 
                 
                   
                     N 
                     i 
                   
                   ≥ 
                   
                     
                       b 
                       i 
                     
                     + 
                     
                       
                         a 
                         i 
                       
                       T 
                     
                   
                   ≡ 
                   
                     
                       n 
                       i 
                       t 
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   14 
                 
                 ) 
               
             
           
         
       
     
   
   Thus, n i   l  is a lower bound on the number of servers to be allocated at the i-th tier, where the lower bound n i   l  is calculated based on the response time constraint (see Eq. 6 above). Next, to calculate the upper bound, the two-approximation solution N i   r  is considered (according to the first server allocation algorithm). Let C r =cost(N r ). Since C r  is an upper bound on the total cost of the optimal solution, n i   u  is defined as follows: 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         h 
                         i 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         N 
                         i 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           j 
                           | 
                           
                             j 
                             ≠ 
                             i 
                           
                         
                         
                             
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           h 
                           j 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           n 
                           j 
                           l 
                         
                       
                     
                   
                   ≤ 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         1 
                       
                       k 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         h 
                         j 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         n 
                         j 
                       
                     
                   
                   ≤ 
                   
                     C 
                     r 
                   
                 
                 ⇒ 
                 
                   
                     N 
                     i 
                   
                   ≤ 
                   
                     
                       
                         C 
                         r 
                       
                       - 
                       
                         
                           ∑ 
                           
                             j 
                             | 
                             
                               j 
                               ≠ 
                               i 
                             
                           
                           
                               
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             h 
                             j 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             n 
                             j 
                             l 
                           
                         
                       
                     
                     
                       h 
                       i 
                     
                   
                   ≡ 
                   
                     
                       n 
                       i 
                       u 
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   15 
                 
                 ) 
               
             
           
         
       
     
   
   Thus, n i   u  is an upper bound on the number of servers to be allocated at the i-th tier, where n i   u  is calculated based on the cost associated with the two-approximation algorithm. 
   Given n i   l  and n i   u , the server allocation module  120  ( FIG. 1 ) has to just consider items jεS i  satisfying ┌n i   l ┐≦j≦└n i   u ┘. Without loss of generality, it is assumed that n i   l  and n i   u  are both integers. Otherwise n i   l  can be replaced by ┌n i   l ┐ and n i   u  can be replaced by └n i   u ┘. Then set S i  has n i   u −n i   l +1 items, which reduces the number of items involved in the calculation to solve for N=(N 1 , N 2 , . . . , N k ), the optimal configuration. 
   Solving the multi-choice knapsack problem causes selection of items from respective sets S 1 , . . . , S k  that satisfy the response time constraint and a target cost (e.g., an optimal cost). In one example, the optimal cost is the minimum cost. The multi-choice knapsack problem can be solved in pseudo-polynomial time by building (at  222 ) a dynamic programming (DP) table. There are two ways to build the dynamic programming table, using either the cost or the weight. As the weights of items are not integers, and the costs are integers, the DP table is efficiently built using the cost dimension. The DP table is a two-dimensional table having k rows (corresponding to the k tiers) and C r  columns (where C r  is the cost associated with the two-approximation algorithm described above). Each cell of the DP table (which contains k×C r  cells) has a value F(i,c), which represents the minimum weight (or response time) of items selected from the first i item sets with total cost bounded by c, for i=1, . . . , k, and c=1, . . . , C r . The i-th row of the DP table represents the optimal solution, minimum response time F(i,c), for the first i tiers. The first row of the DP table, F(l,c) is relatively easy to compute: F(l,c)=min {weight(j)|j·h 1 ≦c}, c=1, . . . , C r . Each field (representing the response time) of the first row F(l,c) is the minimum response time weight(j), such that j·h 1 ≦c. 
   Once the first row is computed, the subsequent rows (2, 3, . . . , k) of the DP table F(,) are built using the following recursion function: 
   
     
       
         
           
             
               
                 
                   F 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     ( 
                     
                       i 
                       , 
                       c 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     min 
                     
                       j 
                       ∈ 
                       
                         S 
                         i 
                       
                     
                   
                   ⁢ 
                   
                     
                       { 
                       
                         
                           F 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             ( 
                             
                               
                                 i 
                                 - 
                                 1 
                               
                               , 
                               
                                 c 
                                 - 
                                 
                                   cost 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ( 
                                     j 
                                     ) 
                                   
                                 
                               
                             
                             ) 
                           
                         
                         + 
                         
                           weight 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             ( 
                             j 
                             ) 
                           
                         
                       
                       } 
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   16 
                 
                 ) 
               
             
           
         
       
     
   
   According to Eq. 16, F(i,c) is an aggregate value derived by summing the F(,) value from a previous row F(i−1, c−cost(j)) and the weight value, weight(j) (response time), of the current row, based on a selected j (number of servers) from set S i . Set S i  has multiple j values (representing different numbers of servers), in the range n i   l ≦j≦n i   u . 
   F(i,c) represents the minimum response time given a fixed cost c (derived based on cost(j)) for the first i tiers. From the two-approximation algorithm, C r  (the cost of N r ) is within a factor of two of cost(N*), the optimum cost. The size of the cost dimension (number of columns) in the DP table is C r . As a result, the total time involved in building the table is O(C r ··Σ i=1   k (n i   u −n i   l ))=O(cost(N ƒ )·Σ i=1   k (n i   u −n i   l )). 
   Once the DP table has been built, an optimal solution is found (at  224 ) by going through the last row, F(k,c), of the DP table and choosing the minimum cost c, such that F(k,c) is bounded by T (which is the response time constraint). 
   In other words, in step  224 , the server allocation module  120  walks through the last row F(k) and chooses the minimum c value (c 0 ) such that F(k, c 0 )≦T. The value c 0  is the minimum cost of the server allocation problem (aggregated for all k tiers) with the total response time, F(k,c 0 ), bounded by T. 
   Let A be an output array to hold the optimal solution, where each entry of the output array A is equal to the optimal number of servers for a respective tier. In other words, A[i], i=1, . . . , k, represents the optimal number of servers in the i-th tier. To calculate the values for A, the server allocation module  120  performs (at  226 ) a backtrack algorithm to find the optimal number of servers at each tier i. 
   The backtrack algorithm starts with i=k, c=c 0 , and continues through a loop until i=0 (i=k, . . . , 0). The backtrack algorithm walks through the i-th row and finds a value jεS i , such that F(i,c)=F(i−1, c−cost(j))+weight(j). Effectively, in the i-th row, the algorithm identifies the entry with the minimum response time. That entry of the i-th row corresponds with a j value (that represents the number of servers at the i-th tier). Then the value A[i] is set as A[i]=j, and the values of i and c are updated as i←i−l, c←c−cost(j). Effectively, for row k of the DP table, A[k]=j, where j is the value where F(k,c 0 )=F(k−1, c 0 −cost(j))+weight(j). 
   In terms of performance, the above algorithm runs in time O(C r ·Σ i=1   k (n i   u −n i   l ))=O(cost(N ƒ )·Σ i=1   k (n i   u −n i   l )). The second server allocation algorithm thus runs in pseudo-polynomial time, which is less than an exponential time. 
   As explained above, the two-approximation algorithm (the first server allocation algorithm  128  in  FIG. 1 ) provides an approximated solution with a cost that is less than twice the minimum cost. On the other hand, the pseudo-polynomial-time exact algorithm (the second server allocation algorithm  130  in  FIG. 1 ) provides an exact solution that runs in pseudo-polynomial time. In accordance with some embodiments of the invention, an intermediate solution also can be achieved by using the third server allocation algorithm  132  ( FIG. 1 ), which is a fully-polynomial-time approximation scheme. The approximate solution provided by the third server allocation algorithm  132  has better accuracy than the two-approximation algorithm. 
   The pseudo-polynomial-time algorithm described above can be converted into a fully-polynomial-time approximation scheme using cost scaling. The approximation scheme is almost identical to the pseudo-polynomial time algorithm, with the difference that a scaled down cost for each item is used and calculated (at  228 ) as follows: 
   
     
       
         
           
             
               
                 
                   
                     scost 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ( 
                       j 
                       ) 
                     
                   
                   = 
                   
                     ⌈ 
                     
                       
                         
                           k 
                           · 
                           cost 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           j 
                           ) 
                         
                       
                       
                         ɛ 
                         · 
                         
                           C 
                           r 
                         
                       
                     
                     ⌉ 
                   
                 
                 , 
                 
                   ∀ 
                   
                     j 
                     ∈ 
                     
                       
                         S 
                         i 
                       
                       . 
                     
                   
                 
               
             
             
               
                 ( 
                 
                   Eq 
                   . 
                   
                       
                   
                   ⁢ 
                   17 
                 
                 ) 
               
             
           
         
       
     
   
   The scaled down cost scost(j) replaces the cost(j) value associated with the second server allocation algorithm that is associated with items j in each set of the multi-choice knapsack problem. The value ε is selected based on the level of accuracy desired—a low ε value provides greater accuracy but involves greater processing time. Let S i ′ denote the i-th set with items associated with scaled costs. In other words, each set S i ′ includes items j that are each associated with scaled costs rather than the actual costs. If two items in the set have the same scaled cost, then the one with less weight (response time) is kept while the other item is discarded. The scost values are integer values calculated by rounding down the computed value according to Eq. 17. By using the scaled down cost values, the number of items in each set S i ′ of the multi-choice knapsack problem is further reduced for greater computational efficiency. However, the solution provided is an approximate solution, whose accuracy is based on the value of ε. 
   The set S i ′ is computed (at  230 ), where S i ′ contains k·1/ε different scost values. Each set S i ′ thus contains at most k/ε different items. S i ′ is computed efficiently according to the following algorithm. For each fixed t from 1 to k/ε, consider all the items jεS i  such that scost(j)=t. The maximum value of j, denoted j t , can be calculated in O(1) time (or constant time). The weight (response time) of the maximum j t  value becomes weight(j t )=a i /j t −b i ). The item with scost=t and weight=weight(j t ) is placed into set S i ′. The procedure to compute S i ′ takes both time and space O(k·1/ε). 
   To save storage space, not all the S i ′ have to be computed in advance. Based on the generated sets S i ′, a DP table is built (at  232 ), using a technique similar to that used for the pseudo-polynomial-time exact algorithm, described above. For improved efficiency, when computing the DP table, the whole DP table does not have to be stored. Instead, the entries F(i,c) of the DP table can be computed row by row. For i=1, . . . , k, F(i,c) is computed for all possible values of c. At the time of computing the i-th row F(i), first S i ′ is computed, then the row F(i) is computed using the values of the previous row F(i−1) and S i ′. After the i-th row F(i) is finished, S i ′ and F(i−1) are discarded, and the server allocation module  120  continues by processing the (i+1)-th row. As a result, the total storage usage for this algorithm is O(k·1/ε). Note that a similar storage savings technique can be applied to the second server allocation algorithm described above. 
   With costs scaled, the cost of the optimal solution is bounded by k·1/ε. There are k rows of the DP table, with each row of the DP table having length k/ε (that is, B=k/ε, where B represents the number of columns in the DP table), and each cell takes time O(k/ε) to compute. Thus, the total processing time becomes O(k 3 ·1/ε 2 ) In summary, this third server allocation algorithm involves a processing time O(k 3 ·1/ε 2 ) and storage space O(k·1/ε). 
   Each item of a set S i ′ with scaled cost induces an error bounded by (ε·C r /k). There are a total of k items in the solution; thus, the total error in the cost is bounded by ε·C r . Since C r  is a two-approximation of the optimal cost, it follows that the total error is bounded by ε·C r ≦2ε·cost(N*). By replacing ε by ε/2, the time and space complexities of the above algorithm will change only by a constant factor, thus asymptotically the same bounds hold. This gives a (1+ε)-approximation to the server allocation problem. Using the third server allocation algorithm, the number of servers N i ′ computed for each tier i is a feasible allocation of the number of servers for that tier-however, this feasible allocation of the number of servers does not achieve an optimal cost, but rather, a (1+ε)-approximation of the optimal cost. In other words, the cost of the approximate solution N i ′ for i=1, . . . , k satisfies cost(N′)≦(1+ε)·cost(N*). 
   Instructions of such software routines described above are loaded for execution on processors (such as CPU(s)  122  in  FIG. 1 ). The processors include microprocessors, microcontrollers, processor modules or subsystems (including one or more microprocessors or microcontrollers), or other control or computing devices. As used here, a “controller” refers to hardware, software, or a combination thereof. A “controller” can refer to a single component or to plural components (whether software or hardware). 
   Data and instructions (of the software) are stored in respective storage devices, which are implemented as one or more machine-readable storage media. The storage media include different forms of memory including semiconductor memory devices such as dynamic or static random access memories (DRAMs or SRAMs), erasable and programmable read-only memories (EPROMs), electrically erasable and programmable read-only memories (EEPROMs) and flash memories; magnetic disks such as fixed, floppy and removable disks; other magnetic media including tape; and optical media such as compact disks (CDs) or digital video disks (DVDs). 
   In the foregoing description, numerous details are set forth to provide an understanding of the present invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these details. While the invention has been disclosed with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover such modifications and variations as fall within the true spirit and scope of the invention.