# A Novel Hybrid-Copy Algorithm for Live Migration of Virtual Machine
## 3 Novel Hybrid-Copy Algorithm
### Markov Model of Memory Write  
Assume that the set \(\mathrm{M}=\{m_{1},\ m_{2},\ \dots,\ m_{n}\}\) represents all memory pages in the source VM. The set \(\mathrm{M}^{\prime}=\{m^{\prime}_{1},\ m^{\prime}_{2},\ \dots,\ m^{\prime}_{n}\}\) is a set of memory pages in the destination VM. We need to ensure that \(\mathrm{M}=\mathrm{M}^{\prime}\) after the live migration of the VM.  
**Definition 1** (Dirty Page): _A dirty page at the source is a memory page whose state is different from the destination. These pages should be copied to the destination._  
All memory pages in the set \(\mathrm{M}\) are marked as dirty pages in the beginning. Assume that \(m_{1}\) would be modified in \(i^{th}\) round of the iteration phase. If the \(m_{1}\) page was synchronized before the \(i^{th}\) round of the iteration phase, this page should be synchronized again after \(i^{th}\) iterative copy round. If it can be forecasted when the memory page would be modified, lots of time and bandwidth resources will be saved. The Markov model is a classical forecasting model: [PERSON] et al. (2019) have proven that the Markov model achieves a good result in memory prefetching. Therefore, we chose the Markov model as the forecasting model in our novel hybrid-copy algorithm.  
In the observation period, let all memory pages in the source be the input. We need to build a forecasting model based on the analysis of the input data to forecast which pages are going to be dirtied in the next round. Assume a VM possessing 1 GB memory with a 4-KB page size. Such a VM will contain 262,144 pages. In a real case, there may be even larger memory in a VM. It is a heavy burden to analysis such a large data set for the live migration task.  
In the pre-copy algorithm implemented by [PERSON] et al. (2017), a concept of the \"writable working set\" (WWS) is proposed. It is a set of the global frequently modified pages in the iteration phase. We can use the WWS as the input instead of all the memory pages. Assume \(W=\{w_{1},\ w_{2},\ \ldots,\ w_{t}\}\) represents the memory pages that belong to the WWS.  
To simplify the question, we use a dirty memory page to describe a memory write state. For example, if \(w_{1}\) is modified, then \(w_{1}\) is used to describe present state. There will arise to kinds of states during the observation period. The VM is configured with 1-GB RAM and two VCPUs. Various workloads are running in different times. We track dirty pages through the shadow page every 50 ms. Assume that the \(w_{1}\) and \(w_{2}\) were modified during the first 50 ms, the \(w_{2}\), \(w_{3}\), and \(w_{4}\) are modified in the next 50 ms, and the \(w_{1}\), \(w_{4}\) and \(w_{5}\) are changed during the third 50 ms. We believe that every state that occurred during the second 50 ms are associated with the states appeared during the first 50 ms. Similarly, the states happped in the third 50 ms are related to the states that arise during the second 50 ms. If there are only three observation periods, we can calculate the state transition probabilities. The conversion relations between all states are shown in Figure 2. In this example, different states are described by the dirtied memory pages. Each transition from node X to node Y in the diagram is assigned a weight representing the transition probability from X to Y. For example, if the \(w_{1}\) is modified, there is a 50% possibility that the \(w_{2}\) will be changed in the next 50 ms, and both \(w_{3}\) and \(w_{4}\) have a 25% probability to be changed in the next 50 ms. More concretely, we can use a state transition matrix to represent the Markov transition diagram. The observation period lasts 8 s at least, and we can get more than 160 groups of states transitions like these. We can then calculate the state transition matrix \(P_{tt}\) based on these state transitions ([PERSON] et al., 2017).