# DRL-Based Dynamic SFC Orchestration Algorithm for LEO Satellite Networks
## 3 System Model
### Markov Decision Process  
This study considers maximizing network service provider benefits during SFC dynamic orchestration in LEO satellite networks as a dynamic optimization problem. Therefore, the optimization objective is converted into a discrete-time Markov decision process (DTMDP), defined as a quadruple\((S,A,P,R)\), representing the state space, action space, state transition probability, and reward function. The state space includes the current network topology state, future network topology state, and SFC request set requiring deployment or readjustment and their attributes. For state space \(S\), any state \(s_{t}\in S\) at time \(t\) can be represented as \(s_{t}=\{G_{t},F_{t},R_{t}\}\). The current network state \(G_{t}=\{N_{t},L_{t},M_{t},RC_{t},RL_{t}\}\) includes the following:  
* Physical node set \(N_{t}=\{n_{1},n_{2},\ldots,n_{|N|}\}\);
* Physical link set \(L_{t}=\{l_{i,j}|i,j\in N_{t}\}\);
* Network topology matrix \(M_{t}=[m_{i,j}]_{|N||N|}\);
* Node resource state \(RC_{t}=\{rc_{i}|i\in N_{t}\}\), where \(rc_{i}=(cpu_{i},mem_{i},storage_{i})\);
* Link resource state \(RL_{t}=\{r_{i,j}|l_{i,j}\in L_{t}\}\), where \(rl_{i,j}=(bw_{i,j},delay_{i,j})\). * Future network state sequence \(F_{t}=\{M_{t+k}|k=1,2,\ldots,K\}\), where
* \(K\) represents the prediction time slot count;
* \(M_{t+k}=[m_{i,j}^{t+k}]_{|N||N|}\) represents network topology matrix at \(t+k\). * SFC request set \(R_{t}=\{src_{i},dst_{i},V_{t},D_{i},T_{i}\}\), where
* Source and destination nodes are \(src_{i},dst_{i}\in N_{t}\);
* VNF sequence is \(V_{i}=\{v_{1},v_{2},\ldots,v_{|V_{i}|}\}\);
* Resource requirements are \(resource_{j}=(cpu_{j},mem_{j},storage_{j})\) for any \(v_{j}\in V_{i}\);* End-to-end delay constraint is \(D_{i}\);
* Request type is \(T_{i}\). Action space includes VNF deployment decision variables \(x_{i,j,k}(t)\in\{0,1\}\), path selection decision variables \(y_{i,j}(t)\in\{0,1\}\) and link mapping decision variables \(z(t)\in\{0,1\}\). For any time \(t\), action space \(A\) can be represented as \(A=\{a_{t}|a_{t}=(X_{t},Y_{t},Z_{t})\}\), where
* VNF deployment decision matrix is \(X_{t}=\{x_{i,j,k}(t)|i\in[1,|R|],j\in[1,|V_{i}|],k\in[1,|N|]\}\);
* Path selection decision matrix is \(Y_{t}=\{y_{i,j}(t)|i\in[1,|R|],j\in[1,|P_{i}|]\}\);
* Link mapping decision tensor is \(Z_{t}=\{z_{i,j,k,m,n}(t)|i\in[1,|R|],e_{jk}\in E_{i},l_{m,n}\in L_{t}\}\). Transition probability \(P\) represents the probability of transitioning to the next state \(s(t+1)\) after taking action in the current state: \(p(s(t+1)|s(t),a(t))\). In the decision-making process discussed in this article, the state transition function \(P\) cannot be explicitly defined due to uncertainties in state transitions and the curse of dimensionality. Factors like dynamic changes in satellite network topology and user request arrivals introduce randomness into future states. Even with single-step transitions, system states involve multiple dimensions of information such as network topology, resource status, and SFC requests. This high-dimensional transition probability matrix cannot be explicitly stated. Therefore, we use sampling-based methods to learn and optimize strategies directly from interactions to derive optimal policies. A more detailed optimization process will be introduced in the next subsection. The reward function consists of two parts: immediate reward and cumulative reward. The immediate reward \(r(s,a)\) represents the reward obtained immediately after taking action \(a\) in state \(s\); the cumulative reward \(R(\tau)\) represents the overall return at the end of a complete episode \(\tau\). The immediate reward \(r(s_{t},a_{t})\) is expressed as follows:  
\[r(s_{t},a_{t}) = \begin{cases}r_{deploy}(s_{t},a_{t}),&\text{if action type is deployment}\\ r_{adjust}(s_{t},a_{t}),&\text{if action type is readjustment}\end{cases}  \tag{23}\] \[r_{deploy}(s_{t},a_{t}) = \begin{cases}\zeta\cdot\delta_{i}\cdot lifecycle_{i},&\text{if deployment succeeds}\\ -\eta,&\text{if deployment fails}\end{cases} \] \[r_{adjust}(s_{t},a_{t}) =