# Towards Deterministic-Delay Data Delivery Using Multi-Criteria Routing over Satellite Networks
## 3 Problem Modeling
### Link Weight Characterization  
Existing routing algorithms (e.g., [PERSON]'s algorithm) aim to find the path with the smallest sum of link weights among all paths between source and destination nodes. Therefore, different link weight calculation rules result in different network traffic distributions. For instance, traditional methods typically use a link propagation delay as the link weight, with the network weights remaining fixed over time. This leads to heavy reliance on specific optimal paths for the same network traffic, resulting in a centralized traffic distribution that easily causes network congestion. To address the need for load balancing in non-time-sensitive services and QoS requirements for time-sensitive services, link weights are calculated for non-time-sensitive services based on the entire network topology and link load, ensuring their even distribution across the network. Simultaneously, specific link weights are designed for time-sensitive services. The detailed rules are as follows:  
Link Weight for Time-Sensitive Services: To achieve the low-latency and high-real-time requirements of delay-sensitive services, link weights are characterized solely based on the propagation delay. This approach ensures that path selection prioritizes the links with the lowest delay, thereby meeting the QoS requirements of delay-sensitive services. Consequently, when computing paths for delay-sensitive services, the link weight for an inter-satellite link \((u,v)\) depends only on the propagation delay between the two satellites, as follows:  
\[\cos t_{u,v}^{ts}=T_{u,v}^{pro},u\
eq v \tag{7}\]  
where \(T_{u,v}^{pro}\) represents the propagation delay of link \((u,v)\), which equals the distance between the two satellites divided by the speed of electromagnetic waves. Link Weight for Non-Time-Sensitive Services: For non-time-sensitive services, to ensure load balancing across the network, the occupancy of optimal paths should be minimized, taking into account the load conditions of different links during the link weight calculation. Additionally, the \"best-effort\" nature of the network should be maintained, meaning that when different paths between source and destination nodes have similar load conditions, the path with the shorter delay should be preferred. Therefore, the link weight for non-time-sensitive services is measured using the betweenness centrality and the link load ratio. The betweenness centrality \(J_{u,v}\) represents the importance of link \((u,v)\) in the initial state of the network. It is defined as the ratio of the number of shortest paths passing through link \((u,v)\) to the total number of shortest paths in the network:\(J_{u,v}=\sum\limits_{s,d\in\ V}\dfrac{\sigma_{s,d}^{u,v}}{\sigma_{s,d}}\), where \(\sigma_{s,d}\) is the number of shortest paths between nodes \(s\) and \(d\), and \(\sigma_{s,d}^{u,v}\) is the number of shortest paths between \(s\) and \(d\) that pass through link \((u,v)\). If nodes \(s\) and \(d\) are not connected, \(\dfrac{\sigma_{s,d}^{u,v}}{\sigma_{s,d}}=0\). The link load ratio \(\mu_{u,v}\) represents the capacity utilization of link \((u,v)\), defined as the ratio of the load on link \((u,v)\) to its capacity: \(\mu_{u,v}=\dfrac{load_{u,v}}{C\times T_{v}}\), where \(C\) denotes the capacity of the inter-satellite link, \(T_{v}\) represents the duration of the corresponding time slot, and \(load_{u,v}\) is the sum of time-sensitive and non-time-sensitive traffic on that link. As the total network load increases, the load difference between various links also increases. Therefore, the median of the network-wide link load ratio \(\mu_{med}\) is used to represent the central value of the network load. For heavily loaded links, their link cost should be reduced to avoid assigning traffic to them; conversely, for lightly loaded links, their link cost should be increased to maximize their utilization.