# Towards Rack Utilization in Internet Datacenters: An Approach Based on Dynamic Programming
## 4 Our Approach
### Branch and Bound Based Algorithm  
In order to address the problem discussed above, in this section, we propose a branch and bound based server placement algorithm. The algorithm proposed in this section is to search all possible server placement strategies. Since there exist \(m_{z}\) servers, and each server can be stacked inside any of the \(n_{z}\) racks, so the total number of possible strategies is \({n_{z}}^{m_{z}}\). Among them, strategies with the lowest leasing cost \(C_{deploy}\) are needed. In order to reduce the number of searches, the branch and bound approach is adopted in this algorithm to cut branches whose power exceeds the total rack power, as well as the current cost has exceeded the minimum cost. The variables and functions used in Algorithm 1 are described in Table 1.  
As shown in Algorithm 1, the input contains all servers in \(serverList\) and all racks in \(rackList\), the output is a set of optimal leasing cost strategies of mapping from servers to racks. Specifically,  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Variables and Functions** & **Description** \\ \hline \(serverList\) & A list containing all servers needed to be handled \\ \(rackList\) & A list containing all racks \\ \(decisionList\) & A list containing all mapping from servers to racks obtained by running algorithm \\ visit(\(i\)) & A function determining which rack is used to host server \(i\) \\ \(minCost\) & The minimum cost \\ \hline \hline \end{tabular}
\end{table}
Table 1: Variables and functions in Algorithm 1.  
Figure 4: The percentages of businesses using different number of racks.  
the core function is visit(), which is used to process servers one-by-one in _serverList_. In lines 2-6, it iterates over all feasible strategies of current server in each rack, and if the server is allowed to be added to one rack, then turn to the next server. In line 7, it determines whether the arrangement of all servers is completed. In addition, in lines 8-11, it calculates the leasing cost and determines whether the arrangement of servers and racks is the optimal solution. In line 16, it accesses the result of optimal arrangement by calling the visit(0).  
```
1:The servers in _serverList_ and racks in _rackList_;
2:decisionList /* The placement decision of servers to racks */
3:functionvisit() /* it is used to decide which rack is used to host \(i^{th}\) server */
4:for each rack in _rackList_do
5:if rack has space for the \(i^{th}\) server in _serverList_ and current cost is less than _minCost_then
6: call visit(\(i\)+1);
7:endif
8:endfor
9:if the \(i^{th}\) server is the last server in _serverList_then /* check if the strategy is optimal when going to the last server in a strategy */
10: compute current cost \(currentCost\)
11:if\(currentCost\) is less than _minCost_then
12:\(minCost=currentCost\);
13: store mapping from server to rack in _decisionList_
14:endif
15:endif
16:endfunction
17:decisionList={};
18:call visit(0) /* achieve the optimal server placement decision*/
19:return decisionList;
```  
**Algorithm 1** The Branch and Bound Based Server Placement  
The proposed algorithm traverses all available arrangements, and it can get the optimal solution. Although it reduces the number of computations by using the branch and bound method, the computing cost rises exponentially. Specifically, the time complexity and the space complexity are both \(O(n2^{n})\), where \(n\) is the number of servers.