A Multi-Objective Optimization Method of Initial Virtual Machine Fault-Tolerant Placement for Star Topological Data Centers of Cloud Systems

The following part describes the traditional heuristic algorithm, which can solve the VM fault-tolerant placement problem, and proposes a heuristic ACO algorithm.

(1) FFD-based algorithm of VM fault-tolerant placement

The FFD-based algorithm of VM fault-tolerant placement is described in Algorithm 1. Its input contains $C_i$ , $Q_k$ , $u$ , $P_{\min }$ , $P_{\max }$ , $w_1$ , $w_2$ , $w_3$ , and $w_4$ , and its output contains A and $F(U)$ . A is the placement matrix that describes how the VMs are placed on physical nodes. This algorithm can be divided into three steps, as follows:

Step 1. Sort the resource request of VMs in descending order, expressed as $a_1$ , $a_2$ , …, $a_{v+r}$ .

Step 2. Place $a_1$ on the physical node ${\text{hn}}_1$ . If ${\text{hn}}_1$ does not meet the requirements, then select the next physical node ${\text{hn}}_2$ , until the resource request of $a_1$ is met.

Step 3. To meet the resource request $a_k$ of the VM, if physical nodes ${\text{hn}}_1^{*}$ , ${\text{hn}}_2^{*}$ , …, ${\text{hn}}_z^{*}$ are already in use at this time, then select one or some of them to place $a_k$ in numerical order of subscript, ensuring that the resource request is met and its corresponding redundant and service-providing VMs are not on the same physical node. If one or some physical nodes that meet the requirements do exist, then select the one that has the minimum subscript to place $a_k$ . By contrast, if such a physical node does not exist, then select a new physical node to place $a_k$ .

(2) BFD-based algorithm of VM fault-tolerant placement

The BFD-based algorithm of VM fault-tolerant placement is described in Algorithm 2. Its input and output are the same as those of the FFD-based algorithm. This algorithm can be divided into three steps, as follows:

Step 1. Sort the resource requests of VMs in descending order, expressed as $a_1$ , $a_2$ , …, $a_{v+r}$ .

Step 2. Place $a_1$ on the physical node ${\text{hn}}_1$ . If ${\text{hn}}_1$ does not meet the requirements, then select the next physical node ${\text{hn}}_2$ , until the resource request of $a_1$ is met.

Step 3. To meet the resource request $a_k$ of the VM, if physical nodes ${\text{hn}}_1^{*}$ , ${\text{hn}}_2^{*}$ , …, ${\text{hn}}_z^{*}$ are already in use at this time, then select one or some of them to place $a_k$ in numerical order of the subscript, ensuring that the resource request is met and its corresponding redundant and service-providing VMs are not on the same physical node. If one or some physical nodes that meet the requirements do exist, then select the one which can minimize the resource remaining rate to place $a_k$ . By contrast, if such a physical node does not exist, then select a new physical node to place $a_k$ .

The traditional ant colony algorithm optimization depends on the positive feedback mechanism, but it often leads to local optimization or premature convergence. To avoid this situation, this study uses the Max-Min Ant System (MMAS) proposed by Stützle and Hoos^{[ 33 ]}, which can search for high-quality solutions and avoid premature convergence or falling into the local optimum.

We assume that the number of ants is $n$ in iteration $q$ , the number of ants on the $k$ -th VM is $b_k(q)$ , the pheromone of the $k$ -th VM on the physical node $i$ is ${\tau }_{ki}(q)$ , the probability that ant $h$ places the $k$ -th VM on physical node $i$ is $P_{ki}^h(q)$ , the heuristic function is ${\eta }_{ki}(q)$ , the information heuristic factor is $\partial$ , the expected heuristic factor is $\beta$ , the tabu list of ant $h$ is ${\text{tabu}}_h(q)$ (the set of VMs that has been placed), the volatile coefficient $\rho \in [0,1)$ , the pheromone increment of the $k$ -th VM on physical node $i$ is $\Delta {\tau }_{ki}^{\text{best}}$ , and the set of VMs that has not yet been placed and can be placed on physical node $i$ by ant $h$ is ${\text{allowed}}_h$ . If $k\in {\text{allowed}}_h$ , then the transition probability function $P_{ki}^h(q)$ can be expressed as Eq. ( 17 ); otherwise, its value is zero.

(17) $$P_{ki}^h(q)=\frac{{\tau }_{ki}{(q)}^{\partial }\times {\eta }_{ki}{(q)}^{\beta }}{{\displaystyle \underset{k\in {\text{allowed}}_h}{\sum }}({\tau }_{ki}{(q)}^{\partial }\times {\eta }_{ki}{(q)}^{\beta })}$$

where $\partial$ is a parameter used to control the influence of the information accumulated by ants during its movement process and $\beta$ is a parameter used to control the influence of the heuristic information in path selection. In iteration $q$ , the pheromone function of the $k$ -th VM on physical node $i$ is expressed as Eq. ( 18 ):

(18) $${\tau }_{ki}(q+1)=(1-\rho )\times {\tau }_{ki}(q)+\Delta {\tau }_{ki}^{\text{best}}$$

In the first iteration, ${\tau }_{ki}(0)=\alpha$ , $\alpha$ is a constant value and $1-\rho$ is the pheromone evaporation coefficient. In MMAS, we need to set the upper and lower bounds for pheromone. We assume that ${\tau }_{ki}(q)\in [{\tau }_{\min },{\tau }_{\max }]$ , where the initial value of ${\tau }_{\max }$ is ${\tau }_{ki}(0)$ , ${\tau }_{\min }={\displaystyle \frac{{\tau }_{\max }}{g}}$ , and $g$ is the lower bound factor (i.e., $g>1$ ). The pheromone increment $\Delta {\tau }_{ki}^{\text{best}}$ of the $k$ -th VM on the physical node $i$ is expressed as Eq. ( 19 ):

(19) $$\Delta {\tau }_{ki}^{\text{best}}=\{\begin{array}{cc}\frac{F(A^{\text{best}})}{{\tau }_{ki}(q)},\hfill & \text{if}{\alpha }_{ki}=1;\hfill \\ 0,\hfill & \text{else}\hfill \end{array}$$

where $A^{\text{best}}$ represents the optimal solution set of this model. According to Eq. ( 19 ), the value of $F(A^{\text{best}})$ can be calculated. In MMAS, the pheromone increment is equal to the value of the fitness function in the optimal solution. However, in this algorithm, the pheromone increment is equal to the value of the fitness function in the optimal solution divided by the pheromone, which can avoid falling into the local optimum prematurely and obtain the global optimal approximate solution set eventually. In Eq. ( 17 ), ${\eta }_{ki}(q)$ is the heuristic function when the $k$ -th VM is placed on physical node $i$ and represents the desirability of the $k$ -th VM placed on physical node $i$ . Its function can be expressed as Eq. ( 20 ):

(20) $${\eta }_{ki}(q)=\frac{1}{1-Q_k^{{\text{cpu}}^{\prime }}}\times \frac{1}{1-Q_k^{{\text{mem}}^{\prime }}}\times \frac{1}{1-Q_k^{{\text{band}}^{\prime }}}$$

where $Q_k^{{\text{cpu}}^{\prime }}$ , $Q_k^{{\text{mem}}^{\prime }}$ , and $Q_k^{{\text{band}}^{\prime }}$ represent the ratios of the request of the $k$ -th VM for CPU, memory, and network bandwidth resources to the remaining resources of physical node $i$ , respectively. As shown in Eq. ( 20 ), the ant preferentially places VMs with large requests for CPU, memory, and network bandwidth resources.

The following part describes the traditional heuristic algorithm, which can solve the VM fault-tolerant placement problem, and proposes a heuristic ACO algorithm.

(1) FFD-based algorithm of VM fault-tolerant placement

The FFD-based algorithm of VM fault-tolerant placement is described in Algorithm 1. Its input contains $C_i$ , $Q_k$ , $u$ , $P_{\min }$ , $P_{\max }$ , $w_1$ , $w_2$ , $w_3$ , and $w_4$ , and its output contains A and $F(U)$ . A is the placement matrix that describes how the VMs are placed on physical nodes. This algorithm can be divided into three steps, as follows:

Step 1. Sort the resource request of VMs in descending order, expressed as $a_1$ , $a_2$ , …, $a_{v+r}$ .

Step 2. Place $a_1$ on the physical node ${\text{hn}}_1$ . If ${\text{hn}}_1$ does not meet the requirements, then select the next physical node ${\text{hn}}_2$ , until the resource request of $a_1$ is met.

Step 3. To meet the resource request $a_k$ of the VM, if physical nodes ${\text{hn}}_1^{*}$ , ${\text{hn}}_2^{*}$ , …, ${\text{hn}}_z^{*}$ are already in use at this time, then select one or some of them to place $a_k$ in numerical order of subscript, ensuring that the resource request is met and its corresponding redundant and service-providing VMs are not on the same physical node. If one or some physical nodes that meet the requirements do exist, then select the one that has the minimum subscript to place $a_k$ . By contrast, if such a physical node does not exist, then select a new physical node to place $a_k$ .

(2) BFD-based algorithm of VM fault-tolerant placement

The BFD-based algorithm of VM fault-tolerant placement is described in Algorithm 2. Its input and output are the same as those of the FFD-based algorithm. This algorithm can be divided into three steps, as follows:

Step 1. Sort the resource requests of VMs in descending order, expressed as $a_1$ , $a_2$ , …, $a_{v+r}$ .

Step 2. Place $a_1$ on the physical node ${\text{hn}}_1$ . If ${\text{hn}}_1$ does not meet the requirements, then select the next physical node ${\text{hn}}_2$ , until the resource request of $a_1$ is met.

Step 3. To meet the resource request $a_k$ of the VM, if physical nodes ${\text{hn}}_1^{*}$ , ${\text{hn}}_2^{*}$ , …, ${\text{hn}}_z^{*}$ are already in use at this time, then select one or some of them to place $a_k$ in numerical order of the subscript, ensuring that the resource request is met and its corresponding redundant and service-providing VMs are not on the same physical node. If one or some physical nodes that meet the requirements do exist, then select the one which can minimize the resource remaining rate to place $a_k$ . By contrast, if such a physical node does not exist, then select a new physical node to place $a_k$ .

The traditional ant colony algorithm optimization depends on the positive feedback mechanism, but it often leads to local optimization or premature convergence. To avoid this situation, this study uses the Max-Min Ant System (MMAS) proposed by Stützle and Hoos^{[ 33 ]}, which can search for high-quality solutions and avoid premature convergence or falling into the local optimum.

We assume that the number of ants is $n$ in iteration $q$ , the number of ants on the $k$ -th VM is $b_k(q)$ , the pheromone of the $k$ -th VM on the physical node $i$ is ${\tau }_{ki}(q)$ , the probability that ant $h$ places the $k$ -th VM on physical node $i$ is $P_{ki}^h(q)$ , the heuristic function is ${\eta }_{ki}(q)$ , the information heuristic factor is $\partial$ , the expected heuristic factor is $\beta$ , the tabu list of ant $h$ is ${\text{tabu}}_h(q)$ (the set of VMs that has been placed), the volatile coefficient $\rho \in [0,1)$ , the pheromone increment of the $k$ -th VM on physical node $i$ is $\Delta {\tau }_{ki}^{\text{best}}$ , and the set of VMs that has not yet been placed and can be placed on physical node $i$ by ant $h$ is ${\text{allowed}}_h$ . If $k\in {\text{allowed}}_h$ , then the transition probability function $P_{ki}^h(q)$ can be expressed as Eq. ( 17 ); otherwise, its value is zero.

(17) $$P_{ki}^h(q)=\frac{{\tau }_{ki}{(q)}^{\partial }\times {\eta }_{ki}{(q)}^{\beta }}{{\displaystyle \underset{k\in {\text{allowed}}_h}{\sum }}({\tau }_{ki}{(q)}^{\partial }\times {\eta }_{ki}{(q)}^{\beta })}$$

where $\partial$ is a parameter used to control the influence of the information accumulated by ants during its movement process and $\beta$ is a parameter used to control the influence of the heuristic information in path selection. In iteration $q$ , the pheromone function of the $k$ -th VM on physical node $i$ is expressed as Eq. ( 18 ):

(18) $${\tau }_{ki}(q+1)=(1-\rho )\times {\tau }_{ki}(q)+\Delta {\tau }_{ki}^{\text{best}}$$

In the first iteration, ${\tau }_{ki}(0)=\alpha$ , $\alpha$ is a constant value and $1-\rho$ is the pheromone evaporation coefficient. In MMAS, we need to set the upper and lower bounds for pheromone. We assume that ${\tau }_{ki}(q)\in [{\tau }_{\min },{\tau }_{\max }]$ , where the initial value of ${\tau }_{\max }$ is ${\tau }_{ki}(0)$ , ${\tau }_{\min }={\displaystyle \frac{{\tau }_{\max }}{g}}$ , and $g$ is the lower bound factor (i.e., $g>1$ ). The pheromone increment $\Delta {\tau }_{ki}^{\text{best}}$ of the $k$ -th VM on the physical node $i$ is expressed as Eq. ( 19 ):

(19) $$\Delta {\tau }_{ki}^{\text{best}}=\{\begin{array}{cc}\frac{F(A^{\text{best}})}{{\tau }_{ki}(q)},\hfill & \text{if}{\alpha }_{ki}=1;\hfill \\ 0,\hfill & \text{else}\hfill \end{array}$$

where $A^{\text{best}}$ represents the optimal solution set of this model. According to Eq. ( 19 ), the value of $F(A^{\text{best}})$ can be calculated. In MMAS, the pheromone increment is equal to the value of the fitness function in the optimal solution. However, in this algorithm, the pheromone increment is equal to the value of the fitness function in the optimal solution divided by the pheromone, which can avoid falling into the local optimum prematurely and obtain the global optimal approximate solution set eventually. In Eq. ( 17 ), ${\eta }_{ki}(q)$ is the heuristic function when the $k$ -th VM is placed on physical node $i$ and represents the desirability of the $k$ -th VM placed on physical node $i$ . Its function can be expressed as Eq. ( 20 ):

(20) $${\eta }_{ki}(q)=\frac{1}{1-Q_k^{{\text{cpu}}^{\prime }}}\times \frac{1}{1-Q_k^{{\text{mem}}^{\prime }}}\times \frac{1}{1-Q_k^{{\text{band}}^{\prime }}}$$

where $Q_k^{{\text{cpu}}^{\prime }}$ , $Q_k^{{\text{mem}}^{\prime }}$ , and $Q_k^{{\text{band}}^{\prime }}$ represent the ratios of the request of the $k$ -th VM for CPU, memory, and network bandwidth resources to the remaining resources of physical node $i$ , respectively. As shown in Eq. ( 20 ), the ant preferentially places VMs with large requests for CPU, memory, and network bandwidth resources.

The heuristic ant colony algorithm includes the FFDACO and BFDACO algorithms. The difference is that, when an ant has placed all of the service-providing VMs, the redundant VMs can be placed by the FFD or BFD algorithm.

The FFDACO-based algorithm of VM fault-tolerant placement is described in Algorithm 3. Its input and output are similar to those of Algorithms 1 and 2. The difference is that the FFDACO-based algorithm has several additional parameters to MMAS that we have discussed in Section 3.2. This algorithm can be divided into the following steps:

Step 1. Initialize the parameters, i.e., the number of ants is $N_{\text{ant}}$ and the number of iterations is $N_{\text{run}}$ .

Step 2. Select the physical node $i$ randomly and place ant $h$ on it. Then, the ant starts to search VMs.

Step 3. If set C (set of service-providing VMs) is not empty, then proceed to Step 4; otherwise, proceed to Step 6.

Step 4. The ant $h$ searches the VMs from ${\text{allowed}}_h$ , which contains the VMs that have not been placed and can be placed on physical node $i$ . If set ${\text{allowed}}_h$ is empty, then select the next physical node randomly and proceed to Step 3.

Step 5. The ant $h$ updates ${\eta }_{ki}(q)$ (it represents the desirability of the $k$ -th VM placed on physical node $i$ ) according to Eq. ( 20 ), selects the $k$ -th VM from set ${\text{allowed}}_h$ , places it on the physical node $i$ using the roulette wheel selection algorithm (which selects randomly by probability) according to Eq. ( 17 ), updates the placement matrix A, deletes the $k$ -th VM from set C, and updates $C_i$ (useable resources on the physical node $i$ ). Then, proceed to Step 3.

Step 6. Place the redundant VMs. Sort the VMs in set $C_{\text{red}}$ on the basis of the resource requests in descending order. Then, new VM sequence can be expressed as VM ${}_1$ , VM ${}_2$ , …, VM ${}_r$ .

Step 7. If set $C_{\text{red}}$ is not empty, then proceed to Step 8; otherwise, proceed to Step 9.

Step 8. To meet the resource request of VM ${}_k$ in set $C_{\text{red}}$ , if physical nodes ${\text{hn}}_1^{*}$ , ${\text{hn}}_2^{*}$ , …, ${\text{hn}}_z^{*}$ are already in use at this time, then select one or some of them to place the VM ${}_k$ in numerical order of subscript, ensuring that the resource request is met and its corresponding redundant and service-providing VMs are not on the same physical node. Then, if one or some physical nodes that meet the requirements do exist, then select the one that has the minimum subscript to place the VM ${}_k$ . If such physical node does not exist, then select a new physical node to place the VM ${}_k$ . Finally, delete the VM ${}_k$ from $C_{\text{red}}$ , update the placement matrix A, and proceed to Step 7.

Step 9. If $h=0$ , then $A^{\text{best}}$ = A; otherwise, compare $F(A)$ with $F(A^{\text{best}})$ , if ( $F(A)<F(A^{\text{best}})$ , then $A^{\text{best}}$ = A. Reset $C_i$ , $A=0$ , C, and ${\eta }_{ki}(q)$ . Then set $h=h+1$ , if $h<N_{\text{ant}}$ , proceed to Step 2.

Step 10. Update ${\tau }_{ki}(q)$ according to Eqs. ( 18 ) and ( 19 ), if ${\tau }_{ki}(q)<{\tau }_{\min }$ , set ${\tau }_{ki}(q)={\tau }_{\min }$ ; if ${\tau }_{ki}(q)>{\tau }_{\max }$ , set ${\tau }_{ki}(q)={\tau }_{\max }$ . Then set $q=q+1$ , if $q<N_{\text{run}}$ , reset $h=0$ , and proceed to Step 2.

Step 11. Calculate U according to $A^{\mathrm{best}}$ and $F(U)$ by Eq. ( 16 ). Then, output $A^{\text{best}}$ and $F(U)$ .

The difference between BFDACO and FFDACO algorithms is determined in Steps 6 - 8. In the BFDACO algorithm, these steps adopt the BFD method described in Algorithm 2.

According to Ref. [ 33 ], the time complexity of the proposed heuristic ant colony algorithm is $T(n)=$ $O(q\times$ ${(v+r)}^2\times n)$ , which increases with the increment of the number of VMs $(v+r)$ , the number of ants $(n)$ , and the number of iterations $(q)$ , respectively. Its space complexity is $S(n)$ = $O({(v+r)}^2)+$ $O((v+r)\times n)$ ; therefore, it increases with the increment of the number of VMs and the number of ants.

The four algorithms (i.e., FFD, BFD, FFDACO, and BFDACO) are all implemented using the Java programming language. Section 4 describes the three experiments, i.e., simulation, real cluster, and fault injection experiments, conducted in this study and explains all of the related algorithmic languages and environments.