# A Novel Self-Adaptive VM Consolidation Strategy Using Dynamic Multi-Thresholds in IaaS Clouds
## 3 Novel Self-Adaptive VM Consolidation Strategy
### VM Placement Using Modified MW-BF Algorithm  
The VM placement is similar to a bin packing problem on variable bin sizes and prices, where bins represent the physical nodes; items are the VMs that had to be allocated; bin sizes are the available resource capacities (CPU, RAM, Bandwidth, etc.) of the nodes; and prices correspond to the power consumption by the nodes. As the bin packing problem is NP-hard, to solve it we apply a modification of the Best Fit (BF) algorithm by considering the multi-weight of the VM that needs to be allocated. In our modification (MW-BF), we sort all the PMs in the ascending of its resource utilization ratio, multiplied by the weights of the allocating VM. This allocates each VM to a host that provides the least increase of the power consumption and chooses the most power-efficient one by leveraging the heterogeneity of each node.  
Use matrix \(P^{*}\) to represent each resource utilization ratio of all PMs, defined as:  
\[P^{*}=\left[\begin{array}{c}P^{*}_{1}\\ P^{*}_{2}\\ \vdots\\ P^{*}_{m}\end{array}\right]=\left[\begin{array}{ccc}P^{c}_{1}&P^{b}_{1}&P^ {r}_{1}\\ P^{c}_{2}&P^{b}_{2}&P^{r}_{2}\\ \vdots&\vdots&\vdots\\ P^{c}_{m}&P^{b}_{m}&P^{r}_{m}\end{array}\right] \tag{9}\]  
The product of multi-weights and resource utilization of each PM for allocating VM selected from \(PM(j)\) can be calculated as:  
\[W_{PM}=P^{*}\cdot Q_{j}^{T}=\left[\begin{array}{ccc}P^{c}_{1}&P^{b}_{1}&P^ {r}_{1}\\ P^{c}_{2}&P^{b}_{2}&P^{r}_{2}\\ \vdots&\vdots&\vdots\\ P^{c}_{m}&P^{b}_{m}&P^{r}_{m}\end{array}\right]\cdot\left[\begin{array}{c}Q^ {c}_{j}\\ Q^{c}_{j}\\ Q^{b}_{j}\end{array}\right] \tag{10}\]The pseudo-code for the algorithm is presented in Algorithm 4. The complexity of the algorithm is \(n\cdot m\), where \(n\) is the number of nodes and m is the number of VMs that have to be allocated. After these steps, the waiting list \(Target_{PM}\) then contains PMs that need to be migrated in.  
```
1 Input:\(PM_{List}\), \(Select_{VM}\)
2 Output: placement of VMs
3\(Select_{VM}\). sortDescendingUtilization()
4 foreach VMin\(Select_{VM}\) do
5 calculate each \(W_{PM}\) using Formula (10)
6\(W_{PM}\). sortAscendingUtilization()
7 if PM has enough resource for VM then
8\(Target_{PM}\leftarrow\) PM
9\(\min\)Energy \(\leftarrow\) MAX
10 allocatedPM \(\leftarrow\) NULL
11 foreach PMin\(Target_{PM}\) do
12 energy \(\leftarrow\) estimateEnergy (PM, VM) in (13)
13 ifenergy < minEnergythen
14 allocatedPM \(\leftarrow\) PM
15 minEnergyr \(\leftarrow\) energy
16 ifallocatedPM \(\
eq\) NULLthen
17 allocate VM to allocatedPM
18 return placement of VMs
```  
**Algorithm 4** Modified Multi-weights Best fit (MW-BF)  
The VM first selects the PM with least \(W_{PM}\) and adds it to the waiting list (\(Target_{PM}\)), then it will be checked for being overload. To maximize the utilization of the remaining resource on these destination PMs, all product \(W_{PM}\) are sorted in descending order. In general, the least the product of resource utilization and weights is, the more the corresponding resource it will leave, which means that the VM would have enough remaining resources to use and thus it could efficiently decrease the cost of the frequent migration of VMs.