# A Dynamic Service Reconfiguration Method for Satellite-Terrestrial Integrated Networks
## 4 Algorithm Design and Description
### Problem Formulation  
First, we formulate the service migration and reconfiguration problem in STINs based on the network models and optimal objectives in Section 3. Considering the service experience and operation cost of network users, we regard minimizing end-to-end delay and migration cost as our optimal objective, it can be expressed as:  
\[\text{min}C_{m}(t)=\text{min}[w_{1}D(t)+w_{2}M_{c}(t)] \tag{6}\]s.t. \(\sum M_{s_{u}}(n_{i},f_{k})\leq 1\), \(\forall n_{i}\in N_{sn}\), \(f_{k}\in F_{s}\)  
\[\sum M_{s_{u}}\left(l_{sn_{t}}^{ij}I_{s}^{f_{k}\lor f_{k}}\right)\leq 1\), \(\forall l_{sn}^{ij}\in L_{sn}\), \(l_{s}^{f_{k}\lor f_{s}}\in L_{s}\)  
\[\sum M_{s_{u}}(n_{i},f_{k})\cdot\text{C}\text{P}\text{u}_{s}^{f_{k}}\leq\text{ C}\text{P}\text{u}_{sn}^{i}\ \forall n_{i}\in N_{sn}\), \(f_{k}\in F_{s}\)  
\[\sum M_{s_{u}}\left(l_{sn_{t}}^{i,j}I_{s}^{f_{k}\lor f_{s}}\right)\cdot\text{ B}\text{W}_{s}^{f_{k}\lor f_{s}}\leq\text{B}\text{W}_{sn}^{i,j}\ \forall l_{sn}^{i,j}\in L_{sn}\), \(l_{s}^{f_{k}\lor f_{s}}\in L_{s}\)  
\[M_{s_{u}}(n_{i},f_{k})=\{0,1\},\ \forall n_{i}\in N_{sn},\ f_{k}\in F_{s}\]  
\[\sum M_{s_{u}}\left(l_{sn_{t}}^{i,j}I_{s}^{f_{k}\lor f_{s}}\right)=\{0,1\},\ \forall\ l_{sn}^{ij}\in L_{sn},\ l_{s}^{f_{k}\lor f}\in L_{s}\]  
Equation (6) is the objective function of the optimization problem, which aims to obtain the optimal migration location and migration path with the minimum end-to-end delay and migration cost, where \(w_{1}\) and \(w_{2}\) are the correction coefficients of end-to-end delay \(D(t)\) and migration costs \(M_{c}(t)\), which are used to dynamically adjust the different requirements of different services for delay and migration costs. In this paper, the migration cost is modeled as extra delay generated by the migration process, for which we should assign the value of \(w_{1}\) and \(w_{2}\) as 0.5 and 0.5, respectively. Once the migration costs are modeled as other factors, for example, the joint consumptions of computing resource and bandwidth resource. The value of \(w_{1}\) and \(w_{2}\) should be assigned by the service request at present, for example, \(w_{1}=0.2\) and \(w_{2}=0.8\) for the resources-awareness service request. Equations (7)-(12) are constraints, which mainly consider the balance between the resource constraints of the substrate network and the demand for service migration; Equation (7), (8) ensures that a service migration node and link can only mapped to one substrate node and link at most; Equation (9) ensures that the computing resource demand of the service migration node does not exceed the computing resource capacity of the mapped substrate node; Equation (10) ensures that the bandwidth resource demand of the service migration link does not exceed the bandwidth resource capacity of the mapped substrate link; Equation (11) uses Boolean variables to indicate whether the substrate node is selected as the current service deployment node, 1 means deployed, 0 means its not; Equation (12) is the same as above, which represents whether the substrate link is selected as the service request virtual link. The value 1 means mapped, and 0 means its not.