# Towards Deterministic-Delay Data Delivery Using Multi-Criteria Routing over Satellite Networks
## 3 Problem Modeling
### Routing Algorithm
The initial value of \(\lambda_{\tau,\mu,v}\) is given by Equation (2), while the initial value of \(\lambda_{\tau,\mu,v}^{ts}\) is the product of \(\lambda_{\tau,\mu,v}\) and the time-sensitive traffic proportion \(\omega\). In the execution of the satellite Internet service scheduling algorithm based on the spatiotemporal distribution of traffic, there are five main steps: (1) Calculate the total traffic arrival rate for each node; (2) Use the bubble sort algorithm to sort the satellite nodes in ascending order based on their traffic arrival rates, then compute paths in subsequent steps following this order to prioritize the calculation of paths for low-traffic nodes; (3) In the initial network topology, use the shortest path algorithm to compute low-latency paths for time-sensitive services to meet real-time requirements; (4) Calculate the betweenness centrality of the network edges \(J\) and the median of the link load ratio \(\mu_{med}\), then update the link cost in the network topology according to Section 4.1; (5) In the updated network topology, use the shortest path algorithm to calculate paths for non-time-sensitive services, selecting paths with lower loads for these services. Assuming there are \(n\) nodes and \(m\) edges in the network, the average time complexity of the sort algorithm in Step 2 is \(O(n^{2})\). In Step 3, each satellite node needs to calculate the

Figure 3: Flowchart of the routing algorithm based on spatiotemporal distribution of traffic. time-sensitive service paths from itself to all other nodes using the shortest path algorithm, requiring a total of \(n(n-1)\) calculations with a time complexity of \(O(n\log n)\) for each calculation, leading to a total complexity of approximately \(O(n^{3}\log n)\) for Step 3. In Step 4, the time complexity for calculating the betweenness centrality \(J\) using the Girvan-Newman (GN) algorithm is \(O(mn)\)[30], and the time complexity for calculating the median of the link load ratio \(\mu_{med}\) using the SELECT algorithm is \(O(m)\)[31]. The calculation of link load ratios is required each time a path is computed for non-time-sensitive services, resulting in a time complexity of \(O(mn^{2}+mn)\) for Step 4. Step 5 is similar to Step 4, with a complexity of \(O(n^{3}\log n)\). Therefore, the time complexity of the satellite internet traffic scheduling algorithm based on the spatiotemporal distribution of traffic is approximately \(O(n^{3}\log n+mn^{2}+mn)\). Once the service arrival type is determined, if it is time-sensitive, the traffic is forwarded according to the time-sensitive service path; if it is non-time-sensitive, it is forwarded according to the non-time-sensitive service path. ### Implementation Scheme Based on Virtual Private Network (VPN)

In the satellite Internet, the source ground station transmits encrypted data via a VPN [32] to the satellite, which is then responsible for transmitting the data to the destination ground station connected to a private network. SRv6 can function as the underlying tunneling technology for the VPN, enabling efficient data transmission from the source node to the destination node via SRv6 tunnels. The segment routing (SR) mechanism in SRv6 provides essential functions for time-sensitive traffic transmission, including path segmentation, service priority control, and network slicing. These functions collectively ensure low-latency and highly reliable transmission of time-sensitive traffic, meeting quality of service (QoS) requirements in satellite networks. To implement a VPN-based satellite internet transmission scheme, the following five SRv6 application configurations and VPN update strategies are proposed to meet the QoS requirements of time-sensitive services:

(1) Optimization of Path Segmentation and SID Sequence Configuration: The SRv6 path control mechanism relies on Segment Identifiers (SIDs), where each SID represents a node in the network or a specific forwarding action.