# Delay-Sensitive Service Provisioning in Software-Defined Low-Earth-Orbit Satellite Networks
## 3 Network Model and Problem Formulation
### Problem Formulation  
In this work, our primary goal is to meet the propagation delay constraints and minimize queuing delay for TS services in LEO satellite networks through optimized routing. Furthermore, due to the highly dynamic topology of LEO satellite networks, we need to consider minimizing the control overhead caused by frequent routing changes. Therefore, in modeling the routing problem, we have incorporated service propagation delay requirements and network bandwidth constraints, while load balancing and routing handover overhead are set as optimization objectives. Moreover, our proposed routing algorithm can also easily incorporate other optimization goals, such as minimizing energy consumption, through simple extensions. Since the routing optimization problem for TS flows in LEO satellite networks needs to consider multiple topology snapshots simultaneously, it is much more complex than the routing optimization problem in static topologies. There are usually two modeling approaches for network routing optimization problems: node-link and link-path [26]. In the link-path model, the candidate paths for each flow are given in advance, and thus we can control the complexity of the model by adjusting the number of candidate paths. However, the node-link model requires the direct computing of all paths for the TS flows, thus introducing more variables and constraints, which makes the node-link model difficult to solve in large-scale networks. To reduce the complexity of the model, we choose the link-path approach to model the problem in this paper. For the sake of clarity, we provide a comprehensive list of the notations used in Table 1. In the following text, we will first introduce the routing constraints and then give the optimization objective. \begin{table}
\begin{tabular}{l l} \hline \hline
**Notations** & **Meaning** \\ \hline \(\mathcal{T}\) & The set of time slots within a motion period \\ \(i\) & The \(i\)-th time slot \\ \(G(V,E)\) & The directed graph of the network topology \\ \(V\) & The set of satellite nodes in the network \\ \(E\) & The set of links between satellites \\ \(F\) & The set of TS flows \\ \(f_{j}\) & The \(j\)-th TS flow \\ \(c_{e}\) & The capacity of of link \(e\) \\ \(b_{j}\) & The bandwidth requirement of the \(j\)-th flow \\ \(d_{e}^{i}\) & The maximum propagation delay of link \(e\) in time slot \(i\) \\ \(r_{j}\) & The maximum delay constraint of the \(j\)-th flow \\ \(y_{e}^{i}\in\{0,1\}\) & A given binary constant indicating whether link \(e\) exists in time slot \(i\) \\ \(P_{j,i}\) & A given set of eligible candidate paths of flow \(j\) in time slot \(i\) \\ \(i_{k,e}^{i,j}\in\{0,1\}\) & A given binary constant indicating whether the \(k\)-th candidate path flow \(f_{j}\) in time slot \(i\) goes through link \(e\) \\ \(x_{k}^{i,j}\in\{0,1\}\) & A decision binary variable indicating whether path \(k\) is chosen for flow \(f_{j}\) in time slot \(i\) \\ \(h_{j}^{i-1,i}\in\{0,1\}\) & A dummy binary variable indicating whether flow \(f_{j}\) changes its route during time slot \(i-1\) to \(i\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. Using Figure 3, we can illustrate the decision variables more clearly. There are two consecutive time slots, slot \(i\) and slot \(i+1\); each node represents a satellite, and solid lines denote available links between two satellites. We observe that there is a change in the state of \(e_{1},e_{5},e_{6},e_{7},e_{8},e_{9},e_{10},e_{11}\), while \(e_{3},e_{4},e_{12}\) remain in a connected state, and \(e_{2}\) remains unconnected. Given that \(y^{i}_{e}\) indicates whether link \(e\) exists in time slot \(i\), it can be easily observed that \(y^{i}_{e_{1}}=1,y^{i}_{e_{2}}=0\). Then, we assume there is a TS flow \(f_{j}\) from source node \(S\) to destination node \(D\), and in time slot \(i\), there are two paths, Path 1 and Path 2, from the candidate paths set \(P_{j,i}\). We can observe that Path 2 includes link \(e_{1}\) and excludes link \(e_{2}\), so \(l^{ij}_{2,e_{1}}=1,l^{ij}_{2,e_{2}}=0\).