# Delay-Sensitive Service Provisioning in Software-Defined Low-Earth-Orbit Satellite Networks
## 4 Approximation Algorithm Design
Therefore, a line is added between \(\mathcal{T}_{1}\) and \(\mathcal{T}_{2}\) in the diagram to represent the availability of \(path_{1}\) in both time slots. The process continues to check the availability of \(path_{1}\  
routing path, and a similar process is followed to determine the availability of \(path_{2}\) in \(\mathcal{T}_{3}\) and \(\mathcal{T}_{4}\). All of the routing paths in \(P\) for all time slots are evaluated at line 2 in Algorithm 2, and the auxiliary graph \(G^{\prime}\) for the traffic flow is obtained. In line 8, we set each of the link costs to 1 in the auxiliary graph to signify that a path handover between two time slots incurs a cost of 1. We hope that the shortest number of hops is the number of path handovers of the target flow throughout the entire satellite topology cycle, meaning that every edge passed except for the first hop represents a path handover. Therefore, finding the shortest path in the auxiliary graph enables the selection of a routing solution that minimizes the number of path handovers across time slots. ```
Data: Set of routing path \(P=\{path_{1},path_{2},\ldots,path_{|\mathcal{T}|}\}\) Result: Auxiliary graph
1 Add \(|\mathcal{T}|\) nodes in an empty graph;
2 for\(j\) in \(1,\ldots,|\mathcal{T}|\)do
3 for\(t\) in \(j+1,\ldots,|\mathcal{T}|\)do
4 if\(path_{j}\) is valid in \(\mathcal{T}_{t}\)then
5 Add a link between \(\mathcal{T}_{j}\) and \(\mathcal{T}_{t}\);
6
7 else
8 Break;
9
10 Set each of link costs to 1. ```  
**Algorithm 2**Construct auxiliary graph  
At line 8 of Algorithm 1, the auxiliary graph is built for the traffic flow by running Algorithm 2, and at line 9, the shortest path that aims to reduce the number of path handovers is derived as the final routing path of the traffic flow. It is noted that the final routing path has already met the delay requirement and considered the load balance; moreover, it reduces the number of path handovers. Finally, I will discuss the computational complexity of the proposed LCP algorithm. The LCP algorithm has two main steps: (1) Finding candidate paths in each time slot (lines 5-6 in Algorithm 1); this step uses the K-DSP algorithm to find at most K candidate paths in each time slot satisfying the delay constraint. The computational complexity of the K-DSP algorithm is \(O(KV(E+VlogV))\) for a graph with V nodes and E edges. (2) Constructing the auxiliary graph and finding the final path sequence (lines 7-9 in Algorithm 1); this step constructs an auxiliary graph with V nodes (number of time slots). Then, it runs the [PERSON]'s shortest path algorithm on the auxiliary graph, which has a computational complexity of \(O(V^{2})\). Therefore, the overall computational complexity of the LCP algorithm is \(O(T[KV(E+VlogV)+V^{2}])\), where T is the number of time slots. Since T, K, V, and E are all bounded in a given network, the LCP algorithm has a polynomial computational complexity. Figure 4: Routing auxiliary graph. In contrast, directly solving the ILP formulation of the problem has exponential complexity. Therefore, the proposed LCP approximation algorithm is much more efficient at finding solutions than directly solving the ILP model for large problem sizes. In summary, the LCP algorithm has a polynomial time complexity, making it suitable for real-time path computation in large dynamic LEO satellite networks. However, the lower complexity comes at the cost of approximate solutions instead of optimal ones. But LCP achieves excellent performance in terms of path handovers and load balancing compared to the other algorithms considered in this paper.