# Towards Rack Utilization in Internet Datacenters: An Approach Based on Dynamic Programming
## 4 Our Approach
### Dynamic Programming Based Algorithm  
To reduce computational complexity, we propose another algorithm according to the following idea: servers should be assigned to each rack as much as possible, so as to minimize the power fragment of each rack. How to install more servers into each rack can be abstracted as a 0-1 Knapsack problem. That is, each rack is regarded as a knapsack with the capacity of \(C\), and \(C\) is equal to \(BR\) of the rack. Each server is regarded as an object with the value of \(V\) and weight of \(M\), which are equal to the power threshold of server \(P_{cap}\). Then, the problem is how to maximize \(V\) in each knapsack while ensuring the sum of objects' \(M\) will not exceed \(C\). Notably, although multiple racks can be regarded as multiple knapsacks, it is different from the Multidimensional Knapsack (MKP) problem [16]. Specifically, the MKP problem is to find a path to maximize the value of objects in all knapsacks. In addition, it does not apply to the case that not all knapsacks are needed for the optimal strategy.  
The knapsack problem with gradually filling up each rack in this paper is more like a Stochastic Knapsack Problem (SKP). The number of knapsacks can be reduced if there are limited number of objects. The knapsack problem is a nondeterministic polynomial (NP) problem with overlapping sub-problems and optimal sub-structures. Thus, we can solve the problem by constructing a state transition equation and using the dynamic programming method. The state transition equation is constructed as follows:  
\[\texttt{dp}(i,V_{r})=max(\texttt{dp}(i+1,V_{r}),\texttt{dp}(i+1,V_{r}-V_{i})+V_{ i}). \tag{8}\]  
Specifically, \(\texttt{dp}(i,V_{r})\) represents the largest power available for the \(i^{th}\) to \((m_{r}-1)^{th}\) servers when the remaining rack power is \(V_{r}\). \(V_{i}\) represents the power threshold of the \(i^{th}\) server. In addition, \(m_{r}\) represents the number of servers to be racked. The largest power available for the servers to be installed into a rack can be obtained by calling \(\texttt{dp}(0,V_{r})\).  
The variables and functions used in Algorithm 2 are described in Table 2.  
In this section, we take the server placement problem as a knapsack problem. The pseudo-code of the algorithm is shown in Algorithm 2. The core function of this algorithm, named as dp(0), is the state transition equation based on dynamic programming, which represents the maximum power of all servers starting from the \(i^{th}\) one when the remaining power of a rack is _remainPower_. In the algorithm, the searching result of the substructure is stored in set \(d\), thus avoiding the repeated computing of overlapping sub-problems. In line 5, the algorithm judges whether \(d\) has a computing result; if so, it returns the result (line 6). In lines 8 and 9, recursive computations are performed, respectively, to judge whether stacking the \(i^{th}\) server can maximize the rack's utilized power and to determine the server arrangement. In lines 10-13, two strategies are compared to return the better one. In lines 17-20, the server arrangement with the optimal leasing cost is obtained through multiple callings of dp(0).  
The algorithm can provide the optimal server placement strategy for one rack in each computation. It belongs to the greedy algorithm achieving a local optimization for rack, so the final solution is an approximate optimal solution. Compared with the branch and bound algorithm, the solution of the algorithm proposed in this section is probably inferior to the global optimal solution, but it is much time-saving.