# Dependency Analysis based Approach for Virtual Machine Placement in Software-Defined Data Center
## 4 Proposed VM Placement Strategy
### Satisfying Resource Constraints  
When none of the possible matches of groups and PMs can fully satisfy the resource constraints, the groups are adjusted until they satisfy the resource constraints of the matched PMs. To do this, the least dependent VMs in the group are removed until the group satisfies the resource constraints of the PM. Since less-dependent VMs are located farther from the header node, the radius of the group is reduced, thereby removing the least dependent VMs, until the group satisfies the resource constraints of the matched PM. This process is applied to all groups that do not satisfy the resource constraints of  
Figure 4: Matching groups to PMs. their PMs. As a result, some VMs are removed from their initial groups. The removed VMs must then be allocated to new groups. A removed VM is added to a new group if the circle of the group is closer than the circles of other groups. However, the group should still satisfy the resource constraints of its matched PM after adding the VM. If the resource requirements of the closest group conflict with the resource constraints of the matched PM after adding the VM, the VM is allocated to the next closest group. The radius of the circle corresponding to the group is increased until it overcomes other groups to obtain the VM. In this way, the resource constraints of all groups are satisfied. If the selected match does not satisfy the constraint in Equation (2), the radius of the group \(\mathcal{G}_{i}\) is adjusted as follows:  
\[\bar{R}_{i}= \begin{cases}R_{i}-\theta,&\text{if }\mathcal{G}_{i}\text{ does not satisfy constraints in }\text{ Equation }\eqref{eq:constraint}\\ R_{i}+\theta,&\text{otherwise},\end{cases}  \tag{8}\]  
where \(\theta\) is the minimum Euclidean distance between all pairs of nodes in the reduced dimension. A radius of a group that does not satisfy the resource constraint of its corresponding PM is iteratively reduced by \(\theta\), and a radius of a group that satisfies the resource constraint is increased by \(\theta\) until all the groups satisfy the resource constraints. Figure 3 shows the initial radius \(R\) of circle is adjusted to \(\bar{R}_{1}\), \(\bar{R}_{2}\), and \(\bar{R}_{3}\), respectively. ```
0:\(\mathbf{V},\mathbf{P},\mathbf{W}\)
0:X
1:Initialize \(g=m\)
2:\(\mathbf{W}^{\prime}=\text{PCA}(\mathbf{W})\)
3:while\(g\geq 1\)do:
4:\(R\leftarrow\text{compute\_radius}(\mathbf{W}^{\prime},g)\) by (3)
5:\(\{R_{1},\cdots,R_{g}\}\gets R_{i}=R\) for \(\forall i\in[1,g]\)
6:repeat
7:\(\{\mathcal{G}_{1},\cdots,\mathcal{G}_{g}\}\leftarrow\text{clustering}(\{R_{1}, \cdots,R_{g}\},\mathbf{W}^{\prime},\mathbf{V})\)
8:\(\mathbf{A}\leftarrow\text{Hungarian\_matching}(\{\mathcal{G}_{1},\cdots, \mathcal{G}_{g}\},\mathbf{P})\)
9:\(\mathbf{X}_{g}\leftarrow\text{compute\_}X\) using \(\{\mathcal{G}_{1},\cdots,\mathcal{G}_{g}\},\mathbf{P}\), and \(\mathbf{A}\)
10:\(\{\bar{R}_{1},\cdots,\bar{R}_{g}\}\leftarrow\text{update\_R}(\{R_{1},\cdots,R_{g}\},\mathbf{X}_{g})\)
11:if\(\bar{R}_{i}<R_{i}\)\(\forall i\in[1,g]\)then
12: Stop to find a solution
13:else
14:\(R_{i}\leftarrow\bar{R}_{i}\) for \(\forall i\in[1,g]\)
15:endif
16:until Constraint in Equation (2) is satisfied with \(\mathbf{X}_{g}\)
17:\(g\gets g-1\)
18:endwhile
19:\(\mathbf{X}\leftarrow\arg\min_{Y\in\{\mathbf{X}_{1},\cdots,\mathbf{X}_{m}\}}D_ {p}(Y)\)
```  
**Algorithm 1** Deciding location of VMs. Algorithm 1 shows the pseudocode of the proposed VM-placement scheme. The algorithm requires \(\mathbf{V}\), \(\mathbf{P}\), and \(\mathbf{W}\) as inputs, and an \(n\)-by-\(m\) VM location matrix, \(\mathbf{X}\), is returned as the output. Initially, on Line 1, the number of groups is set to \(m\). The PCA analysis described in Section 4.1 is performed on Line 2 by the PCA function. On Lines 3-18, possible solutions are derived as the number of VM groups is decreased. On Line 4, the initial radius of the dependency group is computed based on \(g\) and \(\mathbf{W}^{\prime}\). Next, the radius for each VM group is set as \(R\) on Line 5.