## 3 System Model and Problem Formulation
### MDP Formulation  
The routing problem in satellite networks can be generally described as follows: obtaining the network state at the current moment by obtaining information about the bandwidth information of the link, the link distance, the satellite network topology, and the node load. Then, decide the next hop for sending packets and pass them to other nodes. After that, each hop node cycles in turn. The action taken by each node is related only to the current state of the network, and the process can be described as a Markov Decision Process (MDP) [44]. We can represent it as a quaternion \((S,A,P_{a},R_{a})\), where \(S\) is the state space that the agent can observe, A denotes the action space associated with the decision, \(P_{a}\) is short for \(P_{a}(S,S^{{}^{\prime}})\)', which is the probability of changing from state \(S\) to state \(S^{{}^{\prime}}\) after executing action \(a\), and \(R_{a}\) is the reward that the agent receives for executing action \(a\). In the context of the end-to-end SFC routing problem for satellite networks, we will describe each element of the tuple of the SFC routing decision problem in detail:  
1. State space: Let \(S\) denote the environment's finite set of acceptable states. The state consists of six parts: the source node, destination node, current network node, current node load value, number of functional nodes through which the current path passes, and set of neighboring nodes of the current node. 2. Action space: Define \(A\) as the set of next-hop satellites that the agent can select at the current moment. Since the number of neighboring nodes is different for different network nodes, in order to unify the size of the action space and minimize the complexity of the action space design, we construct the action space as a one-hot vector with the same size as the node with the highest degree in the network and set the dimension of the action space to \(\dim(G)\). When the node is \(n_{i}\) and when \(\dim(n_{i})<\dim(G)\), only the first \(\dim(n_{i})\) nodes are considered for sampling from the policy. 3. Reward: The most important goal of this paper is to achieve load balancing and delay joint optimal routing while satisfying SFC constraints. To achieve this goal, we consider factors such as path delay, network load, and SFC constraints when designing the reward function, which is used to guide the agent to learn the optimization strategy and make correct routing decisions to achieve the goal of this paper. The reward function in this paper combines the following factors:  
* Rewards for network node load \(R_{L}\): Load negatively affects latency and network performance, so providing positive rewards for low-loaded nodes and negative rewards for high-loaded nodes is possible. * Reward for the number of functional nodes in the current path \(R_{F}\): To encourage the agent to choose SFC-compliant paths, we provide positive rewards for paths satisfying SFC constraints and negative rewards for those not, thus guiding the model to optimize step by step during the training process and ultimately satisfy the SFC constraints. * Reward for delay between current satellite node and next hop node \(R_{T}\): Adding a delay penalty trains the agent to know how to deliver the packet to the destination node with the shortest delay. * Reward for other factors: In order to avoid routing loops and enable the model to converge quickly, the occurrence of routing loops is \"punished\" to reduce the risk of recurring routing loops occurring. Taking these factors into account, we can define the reward function as follows:  
\[\text{Reward}\ =\left\{ \begin{array}{l}-1,u\in\text{Vis}\\ -(R_{L}+R_{F}+R_{T}),u\
otin\text{Vis}\\ -(R_{L}+R_{F}+R_{T})+1,u\
otin\text{Vis \& }u=\text{Dst \& }R_{F}=FN\end{array} \right. \tag{19}\]  
where \(R_{T}\) denotes the average path delay, \(R_{F}\) denotes the number of functional nodes visited, and \(R_{L}\) denotes the average network load.