# Towards Deterministic-Delay Data Delivery Using Multi-Criteria Routing over Satellite Networks
## 3 Problem Modeling  
Given the above spatiotemporal distribution model for non-time-sensitive services, ensuring the QoS requirements for time-sensitive services requires reducing the probability of conflicts between time-sensitive and non-time-sensitive services and overcoming the dependency of traditional shortest-path routing algorithms on certain optimal paths. Therefore, a routing algorithm can be used to shape network traffic such that non-time-sensitive services are evenly distributed across the network, reducing their occupancy of optimal paths and \"making way\" for time-sensitive services. To achieve this, given the time range \(T\) and the corresponding satellite snapshot graph model \(G\), the transmission demand for non-time-sensitive services between each pair of satellites at each specific time interval can be calculated based on the spatiotemporal traffic distribution model. This study aims to minimize the utilization of the most heavily loaded links after satisfying the transmission demands across all satellites within the time range \(T=24\) h, thereby achieving evenly distributed load deployment. Thus, given the snapshot graph model \(G\) and the service transmission demand between satellites \(\mathcal{L}\), we define a decision variable \(x(s,d,u,v)\) to represent whether the service from source satellite \(s\) to destination satellite \(d\) is transmitted through link \((u,v)\). If the service is transmitted, \(x(s,d,u,v)=1\); otherwise, \(x(s,d,u,v)=0\). Specifically, all decision  
Figure 2: Traffic ratio variation. variables belong to the variable set \(\mathcal{X}\), and \(\mathcal{X}=\{\mathrm{x}(s,d,u,v)|(\mathrm{u},\mathrm{v})\in\mathcal{E},s,d\in \mathcal{V}\}\). Additionally, we define a continuous variable \(\mu\in[0,1]\), representing the utilization ratio of all link capacities. The decision variable set \(\mathcal{X}\) and \(\mu\) must satisfy the following constraints:  
Link Capacity Constraint: The total traffic arranged on any link \((\mathrm{u},\mathrm{v})\in\mathcal{E}\) should not exceed the maximum data capacity of that link multiplied by a factor \(\mu\):  
\[\sum_{\mathrm{s},\mathrm{d}\in\mathcal{V}}x(s,d,u,v)\times\lambda_{s,d}\leq\mu c _{u,v} \tag{3}\]  
Flow Conservation Constraint: When a node does not serve as a source or destination node, the traffic flowing into node \(u\) must equal the traffic flowing out of that node:  
\[\sum_{v\in\mathcal{V}}x(s,d,u,v)=\sum_{v\in\mathcal{V}}x(s,d,u,v),\forall \mathrm{s},\mathrm{d}\in\mathcal{V},s,d\
eq u \tag{4}\]  
Service Satisfaction Constraint: Assuming that the network's capacity can meet the transmission demand \(\mathcal{L}\), for any source-destination pair during a certain time period, a path must be arranged for transmission:  
\[\sum_{u\in\mathcal{V}}x(s,d,s,\mathrm{u})=\sum_{u\in\mathcal{V}}x(s,d,u,d)=1, \forall\mathrm{s},d\in\mathcal{V} \tag{5}\]  
Therefore, minimizing the load proportion on the most heavily loaded link while satisfying the transmission demands for non-time-sensitive services can be modeled as the following optimization problem:  
\[\mathrm{MC}: \min_{\mathcal{X},\mu}\mu,\] (6) s.t. \[(\ref{eq:1}),\ (\ref{eq:2}),\ (\ref{eq:3}),\ (\ref{eq:4}),\ (\ref{eq:5}),\] \[0\leq\mu\leq 1\]  
In this problem, the decision variables \(\mathcal{X}\) are integer variables, and \(\mu\) is a linear variable, with all constraints being linear. As a result, the problem can be formulated as a mixed-integer linear programming (MILP) problem. It is well known that such problems are difficult to solve in polynomial time and are typical NP-hard problems. Although many commercial mathematical solvers (e.g., CVXPY, Gurobi) support the optimal solution of MILP problems, they still face challenges such as long computation times and high memory requirements. Therefore, the next chapter proposes an efficient solution based on the spatiotemporal distribution model of service traffic.