# Delay-Sensitive Service Provisioning in Software-Defined Low-Earth-Orbit Satellite Networks
## 4 Approximation Algorithm Design  
The heuristic algorithm LCP sorts traffic flows in descending order of the priority of the traffic flows; then, these flows are sequentially routed one by one at each time slot. We consider that there are six priorities of traffic flows, which can be justified by the fact that there are usually eight priorities in a switch and that two priorities are reserved for other traffic flows. We note that with this sorting, flows with higher priority are routedfirst, and if flows have the same priority, the flows with larger bandwidth requirements are routed first. After the sorting, the routing paths of a traffic flow have to be derived at all time slots, where each of the paths is the routing detail of the traffic flow at the time slot. Then, the traffic flow can be carried throughout the sequence of all the time slots. Algorithm 1 shows the details of the LCP algorithm, where the majority of the commandlines are to derive routing path for a traffic flow. In Algorithm 1, from line 2 to the end, the routing paths of each traffic flow are derived at all time slots of the satellite network. At line 5 and line 6, a routing path satisfying the latency requirement and considering load balance is selected at each time slot. Specifically, in a time slot \(\mathcal{T}_{i}\), the K Dijkstra shortest paths (K-DSP) considering latency are obtained first. Then, the one with the minimal of the maximum link utilization is chosen for load balance consideration in the network. This selected path is stored in the set \(P\). We repeat this process in subsequent time slots, resulting in a set of routing paths of the traffic flow \(f_{j}\) in each of the time slots. ```
Data: Set of traffic flows \(F\), satellite network \(G\) Result: Routing results \(R\) Obtain the set of time slots \(\mathcal{T}\) based on \(G\); Sort flows in \(F\) in descending order of priority and bandwidth requirements if flows have the same priority; for\(j\) in \(1\ldots|F|\)do for\(i\) in \(1\ldots|\mathcal{T}|\)do  Use the K-DSP algorithm to find at most K paths on \(\mathcal{T}_{i}\) that satisfy the delay requirement for \(f_{j}\);  Choose \(path_{j}^{i}\) that minimizes the maximum link utilization; record \(path_{j}^{i}\) in set \(P\); Run Algorithm 2 to construct the auxiliary graph \(G_{j}^{\prime}\) for flow \(f_{j}\) based on \(P\);  Use the DSP algorithm on \(G_{j}^{\prime}\) to determine the paths chosen by flow \(f_{j}\) in each time slot, and record them in the actual routing result set \(R\); Update the link capacity at each time slot according to the final paths; Output:\(R\)
```  
**Algorithm 1**The LCP algorithm  
From line 8 to the end, the routing paths of the traffic flow are improved considering the path handovers. Although the routing paths obtained above can effectively meet the latency requirements of traffic flows and consider network load balancing, this ignores a factor that may affect the performance of the satellite network: the number of path handovers. A path handover is the online handover of the routing path that happens between two adjacent time slots, which may cause the packet reordering problem and increase the network latency jitter. Therefore, in the path selections for traffic flows, it is important to consider the number of path handovers in all time slots. To address this, based on the set \(P\), we will construct an auxiliary graph \(G^{\prime}\) for the final path selection. The details of the construction of the auxiliary graph are shown in Algorithm 2. For a better understanding, we give an example to illustrate the auxiliary graph in Figure 4. In the graph, for each time slot, one path that satisfies the delay requirement while minimizing the maximum link utilization is selected (storing in \(P\)). The selected path is then checked for availability in future time slots, which are shown from line 3 to line 7 in Algorithm 2. For example, in time slot \(\mathcal{T}_{1}\), a flow selects \(path_{1}\) and checks if \(path_{1}\) is also available in \(\mathcal{T}_{2}\).