## 4 DRPS: Fault-Tolerant Approach for Dynamic Redundant Path Selection
### Path Selection  
In this paper, the service migration whose execution time does not exceed a certain threshold is called a service migration success. Mobile users will not feel the change of QoS obviously at this time. If the service migration time exceeds a certain threshold, the service migration is considered a failure because mobile users can feel the decrease of QoS obviously at this time. The traditional service migration [43] mainly studies the migration of task data and does not consider the calculation of tasks during the migration process. However, with the increase in the complexity of mobile applications, simple data migration is gradually difficult to meet user needs. Therefore, this paper considers the case where services are migrated and calculated simultaneously.  
As shown in Algorithm 1, this paper uses the Dijkstra algorithm to find the migration path between the source ES and the target ES. When looking for the migration path of task \(r_{i}\), the weight of the ESs node in graph \(G\) is the failure rate of \(r_{i}\) when it is executed on \(e_{j}^{b}\), i. e., \(P_{i}^{j}(F\mid t_{i}^{x^{\prime}})\). First, initialize the migration path set \(M^{r_{i}}\) and weight graph \(G\) (lines 1-2), then find the path \(m^{r_{i}}\) with the lowest failure rate according to the Dijkstra algorithm,add \(m^{\prime_{i}}\) to the set \(M^{\prime_{i}}\), delete the data link in the path \(m^{\prime_{i}}\), and cyclically query the all paths (lines 3-9), and finally determine whether the service is successfully migrated (lines 10-21). The task migration time \(MT_{i}\) is the shortest migration time of task \(r_{i}\) in all feasible paths, which will be described in detail later. Algorithm 1 is based on Dijkstra, so the time complexity is \(O(kn^{2})\), where \(k\) is the number of all feasible migration paths and \(n\) is the number of all nodes in \(G\).  
```
0: Task \(r_{i}\); source edge server \(B_{s}\); target edge server \(B_{t}\).
0:\(T\) or \(F\), where \(T\) indicates that the task migration succeeded, and \(F\) indicates that the task migration fail.
1: Initialize the set of migration paths \(M^{\prime_{i}}\leftarrow\{\}\).
2: Abstracts the transmission link between \(B_{s}\) and \(B_{t}\) as a weighted graph \(G\), and the failure rate is the weight.
3:while True do
4: apply Dijkstra algorithm to the weighted graph \(G\) to find the shortest path \(m^{\prime_{i}}\) from \(B_{s}\) to \(B_{t}\)
5:if\(m^{\prime_{i}}\) not exists then
6: break
7:else
8:\(M^{\prime_{i}}\gets M^{\prime_{i}}\cup\{m^{\prime_{i}}\}\)
9: delete all nodes in path \(m^{\prime_{i}}\)
10:endif
11:endwhile
12:if\(M^{\prime_{i}}==\varnothing\)then
13: return \(F\)
14:else
15: compute the task migration time \(MT_{i}\)
16:if\(MT_{i}>td_{i}^{\prime}\)then
17: return \(F\)
18:else
19: return \(T\)
20:endif
21:endif
```  
**Algorithm 1** Path Selection Algorithm  
It should be noted that to ensure the success rate of service migration, the path selection algorithm finds all feasible paths in \(G\) for migration, which is not suitable for all cases. If all paths are found for migration in a dense network, the cost of migration will be immeasurable. Still, with a slight modification of the path selection algorithm, it can be applied to a broader range of situations; e.g., limiting the number of migration paths or limiting the number of nodes in the migration path, etc., can be a good trade-off for the problem of excessive migration costs.