# A Novel Hybrid-Copy Algorithm for Live Migration of Virtual Machine
## 3 Novel Hybrid-Copy Algorithm
### Switched Decision Factor(SDF)  
Before we introduce the SDF, let us discuss the flaw of the current hybrid-copy algorithm. It is the key thought of the hybrid-copy algorithm to combine the pre-copy algorithm and the post-copy algorithm to remedy the defects of the pre-copy and post-copy algorithms. In the current hybrid-copy  
Figure 2: The Markov model representing the previous dirty pages via transition probabilities. algorithm, all memory pages are transmitted to the destination only once. Then, the post-copy algorithm starts working. All memory pages are copied once so that the number of page faults are notably reduced, compared with the pure post-copy algorithm. However, if the iterative process of the pre-copy algorithm increases, the number of page faults and the downtime caused by the page faults will be reduced as well. Thus, the best time to switch the pre-copy algorithm to the post-copy algorithm is a key issue in hybrid-copy algorithm. Here, we propose SDF to determine when to switch the pre-copy phase to the post-copy phase. Some definitions and symbols are first introduced in Table 1 to facilitate discussion. **Definition 2 (Invalid Transfer). **_An Invalid transfer means a memory page at the source is dirtied again, after this page has been transferred to the destination at least once._  
If a transmitted memory page at source is dirtied again, it should be retransmitted. This means that all transmissions of this memory page before this copy round did nothing but waste resources and time. Therefore, the number of the invalid transfers should be as small as possible. At the beginning, there is no any transfer between source and destination, so the value of n in Table 1 is 0 at first. We therefore arrive at the following conclusion:  
\[S(0)=0,\ T(0)=0,\ V_{1}(0)=0,\ V_{2}(0)=N \tag{1}\]  
As shown in Table 1, \(V_{1}(n)\) represents the total number of invalid transfers after \(n^{\text{th}}\) transfer, while \(V_{2}(n)\) represents the number of the dirty pages after \(n^{\text{th}}\) transfer. It is obvious that \(V_{1}(n)\) is related to the wasted bandwidth resources in the pre-copy phase, and \(V_{2}(n)\) has ties with the number of page faults and the downtime caused by page faults. Therefore, we introduce the following function to evaluate the state of migration process:  
\[F(n)=\alpha\times V_{1}(n)+(1-\alpha)\times V_{2}(n) \tag{2}\]  
Here, the \(0\leq\alpha\leq 1\). If \(\alpha=0\), only the number of dirty pages needs to be considered, and the pure pre-copy algorithm should be adopted. In this situation, we get the smallest downtime. However, lots of bandwidth resources may be wasted and the migration process may last a long time. Otherwise, if \(\alpha=1\), then \((1-\ \alpha)=0\). This means that we should ensure that the number of invalid transfers is as small as possible. In this case, the pure post-copy algorithm is a good choice. We can guarantee that all memory pages are transferred only once and that there is no any invalid transfer. Numerous page faults always caused network traffic and seriously affect the user experience. According to the definition of the symbols in the Table 1, Equations (3) and (4) can be derived as,  
\[T(n)=S(n)-(V_{2}(n-1)-V_{2}(n)) \tag{3}\]  
\[V_{1}(n)=\ \sum_{i=1}^{n}T(i),\ n>0 \tag{4}\] \begin{table}
\begin{tabular}{c c} \hline
**Symbol** & **Definition** \\ \hline \(N\) & The total number of the VM’s memory pages \\ \(S(n)\) & The number of the transmitted memory pages in \(n^{\text{th}}\) round \\ \(R(n)\) & The total number of the transmitted memory pages after \(n^{\text{th}}\) round \\ \(T(n)\) & The number of invalid transfers in \(n^{\text{th}}\) round \\ \(V_{1}(n)\) & The total number of invalid transfers after \(n^{\text{th}}\) transfer \\ \(V_{2}(n)\) & The number of the dirty pages after \(n^{\text{th}}\) transfer \\ \hline \end{tabular}
\end{table} 
Table 1: Symbols and definitions.