# Dependency Analysis based Approach for Virtual Machine Placement in Software-Defined Data Center
## 4 Proposed VM Placement Strategy
### Matching Groups to PMs  
After grouping the VMs, the next step is to decide which group of VMs should be placed in which PM. The groups are matched to PMs by building a graph of the VM groups and PMs, as illustrated in Figure 4. Matching is then conducted based on the weight of each VM group and PM pair, which is referred to as their closeness value. To find the closeness value, the resource ratios between each group, \(\mathcal{G}_{i}\), and each PM, \(p_{j}\), are computed as follows:  
\[\begin{split}\alpha_{i,j}&=\frac{\sum_{v\in \mathcal{G}_{i}}v.c}{p_{j}.c},\\ \beta_{i,j}&=\frac{\sum_{v\in\mathcal{G}_{i}}v.m}{p _{j}.m},\\ \gamma_{i,j}&=\frac{\sum_{v\in\mathcal{G}_{i}}v.s}{p _{j}.s}.\end{split} \tag{4}\]  
In Equation (4), \(\alpha\), \(\beta\), and \(\gamma\) are the resource ratios for the CPU, memory, and storage, respectively. If a PM has exactly the same amount of resources as those that are required by \(\mathcal{G}_{i}\), the resource ratio of the PM and \(\mathcal{G}_{i}\) is equal to 1. Thus, the closeness between \(\mathcal{G}_{i}\) and \(p_{j}\) can be computed by  
\[q_{i,j}=\sqrt{(1-\alpha_{i,j})^{2}+(1-\beta_{i,j})^{2}+(1-\gamma_{i,j})^{2}}. \tag{5}\]While Equation (5) is used to compute the closeness values, a match that does not fully satisfy the resource requirements of a group may occur if \(\alpha>1\), \(\beta>1\), or \(\gamma>1\). In such cases, the matching should be avoided even though the closeness is small because the resource is not sufficient. If \(\mathcal{G}_{i}\) does not satisfy the resource constraints of \(p_{j}\), a constant penalty \(\lambda\) is added to \(q_{i,j}\) as follows:  
\[\tilde{q}_{i,j}=\begin{cases}q_{i,j}+\lambda,&\text{if }\alpha_{i,j}>1\text{ or } \beta_{i,j}>1\text{ or }\gamma_{i,j}>1\\ q_{i,j},&\text{otherwise},\end{cases} \tag{6}\]  
where \(\lambda\) is a constant number that is large enough to increase the closeness value \(q_{i,j}\).  
The number of VM groups is initially set to \(m\). However, if \(g\) PMs can satisfy the constraint for \(g<m\), the number of VM groups is reduced to \(g\). With \(g\) VM groups, there are \({}_{m}P_{g}\) possible matches between VM groups and PMs. The matching that minimizes the sum of the closeness values should be identified from the \({}_{m}P_{g}\) possible matches. Let \(A\) be a \(g\)-by-\(m\) groups-to-PMs matching matrix; an element, \(a_{i,j}\), is \(1\) when \(\mathcal{G}_{i}\) is matched to \(p_{j}\) and is \(0\) otherwise. The optimization to find \(A\) is formulated as follows:  
\[A^{*}=\arg\min_{A}\sum_{i=1}^{g}\sum_{j=1}^{m}a_{i,j}\cdot\tilde{ q}_{i,j}\] (7) subject to \[\sum_{k=1}^{m}a_{i,k}=1\text{ for }\forall i\in[1,g]\] \[\sum_{k=1}^{g}a_{k,j}\leq 1\text{ for }\forall j\in[1,m].\]  
The Hungarian matching algorithm, which is a well-known algorithm for solving matching problems [47; 48], is used to solve the above optimization problem. First, a graph is built from the VM groups, the PMs, and their closeness values, and it is used as the input to the Hungarian matching algorithm. Using this algorithm, the independent-edge set of matches on the graph that minimizes the sum of the edge weights is identified. The output is a set of matches between groups and PMs.