# Delay-Sensitive Service Provisioning in Software-Defined Low-Earth-Orbit Satellite Networks
## 3 Network Model and Problem Formulation
### Problem Formulation
Then, we assume that in slot \(i\) and \(i+1\), we have both chosen Path 1, that is, \(x^{i,j}_{1}=1,x^{i,j}_{2}=0\) and \(x^{i+1,j}_{1}=1\). However, a path handover occurs due to the fact that the links of the paths selected in the two slots are not entirely coincident, so \(h^{ij+1}_{j}\) will be set to 1. Firstly, the maximum delay of the path chosen for each TS flow in each topology snapshot should meet the flow's delay constraint. \[\sum_{k\in P_{j,i}}\sum_{e\in E}x^{i,j}_{k}l^{ij}_{k,e}d^{i}_{e}\leq r_{j}, \quad\forall j\in F,\forall i\in\mathcal{T} \tag{1}\]  
If flow \(f_{j}\) uses path \(k\) in time slot \(i\), then every link traversed by path \(k\) should exist in time slot \(i\), i.e., we have the following constraint:  
\[x^{ij}_{k}l^{ij}_{k,e}\leq y^{i}_{e},\quad\forall j\in F,\forall i\in \mathcal{T},\forall e\in E,\forall k\in P_{j,i} \tag{2}\]  
To avoid packet reordering, we assume that each TS flow can only use one path within each time slot. Therefore, the decision variable \(x^{i,j}_{k}\) needs to satisfy the following constraint:  
\[\sum_{k\in P_{j,i}}x^{i,j}_{k}=1,\quad\forall j\in F,\forall i\in\mathcal{T} \tag{3}\]  
Furthermore, to avoid introducing significant unpredictable delays due to traffic overload, we require that the total size of TS flows carried on each link should be smaller than its capacity. \[\sum_{j\in F}\sum_{k\in P_{j,i}}x^{i,j}_{k}l^{ij}_{k,e}b_{j}\leq c_{e},\quad \forall e\in E,\forall i\in\mathcal{T} \tag{4}\]  
After introducing the constraints that TS flows need to satisfy, we now turn our attention to the optimization objective of the problem. As introduced in Section 2, we mainly consider two optimization objectives in this problem. First of all, we believe that the future LEO satellite networks will use SDN technology to control flow routing in a fine-grained manner. Therefore, in order to reduce the control overhead of SDN, we need to minimize the total number of path handovers. Secondly, network congestion can lead to a significant increase in packet queuing delay. Therefore, to better guarantee the transmission delay requirements of TS flows, we need to achieve network load balancing. Figure 3: Example of decision variables. Firstly, we address the optimization of the number of path handovers. For any given flow, within two consecutive time slots \(i-1\) and \(i\), a path handover occurs if the routing path changes between these two time slots. Specifically, a path handover is counted if any link used by the flow's path in time slot \(i-1\) is different from the links used in time slot \(i\). Furthermore, even if multiple links change between the two time slots, only one path handover is counted. To model the path handovers, we introduce a binary variable \(h_{j}^{i-1,j}\) which indicates whether flow \(j\) changes its path during time slot \(i-1\) to \(i\). The following constraint are added to relate \(h_{j}^{i-1,i}\) with the path selection variables \(x_{j,i}^{k}\):  
\[\left|x_{k}^{i-1,j}h_{k,e}^{i-1,j}-x_{k}^{i,j}h_{k,e}^{i,j}\right|\leq h_{j}^{i -1,j} \tag{5}\]  
To satisfy the constraints of the ILP formulation, we expand the above constraint into the following two constraints:  
\[x_{k}^{i,j}h_{k,e}^{i,j}-x_{k}^{i-1,j}h_{k,e}^{i-1,j} \leq h_{j}^{i-1,i}, \forall e\in E,\forall j\in F,\forall i\in[2,|\mathcal{T}|] \tag{6}\] \[x_{k}^{i-1,j}h_{k,e}^{i-1,j}-x_{k}^{i,j}h_{k,e}^{i,j} \leq h_{j}^{i-1,i}, \forall e\in E,\forall j\in F,\forall i\in[2,|\mathcal{T}|] \tag{7}\]  
To quantitatively analyze the number of path switches, we let \(\beta\) denote the average number of path switches per time slot for each flow, which is defined as:  
\[\beta=\frac{\sum_{i=2}^{|\mathcal{T}|}\sum_{j\in F}h_{j}^{i-1,i}}{(|\mathcal{T }|-1)|F|} \tag{8}\]  
Then, to indicate the degree of the load balancing of the satellite network, we define \(\alpha\) as the maximum link utilization in the network. From the right-hand side of Equation (9), we can calculate the link utilization for each link within all time slots, where \(\alpha\) represents the maximum value.