# A Dynamic Service Reconfiguration Method for Satellite-Terrestrial Integrated Networks
## 3 Problem Descriptions
### Network Models  
Assuming that the number of ground edge nodes and satellite edge nodes in the current STIN is known and fixed, network users and satellite nodes can move with time, and the connection states and resource states among each node and links can be obtained through the SDN/NFV global states collecting ability, that is, the network topology states and network resource states can be known at any time.  
(1) Substrate network model  
The substrate network in the STIN is modeled as a time-varying weighted undirected graph \(G_{sn}\Big{(}N_{sn}^{t}\cup N_{sn}^{leo},L_{sn},A_{sn}^{n},A_{sn}^{l}\Big{)}\), where \(N_{sn}^{t}\cup N_{sn}^{leo}\) is the substrate node set composed of ground edge nodes and satellite edge nodes in the STIN, \(L_{sn}\) is the substrate link between substrate nodes, \(A_{sn}^{n}\) represents the attributes of substrate nodes, while \(A_{sn}^{l}\) is the attributes of the substrate links. The substrate node attributes include the node type \(\text{Ty}_{sn}^{t,leo}\), physical location \(\text{Loc}(n_{i})\), and CPU capacity \(\text{Cpu}_{sn}^{i}\). The substrate link attributes include physical distance \(\text{Dis}\left(n_{i},n_{j}\right)\), and bandwidth capacity \(\text{Bw}_{sn}^{i,j}\). The VNFs deployed on the same node share the resource capacity of the node, the bandwidth capacity of the link is also shared through multiple service paths of the same substrate link.  
(2) Service request  
Suppose there is a given set of virtual network service requests \(G_{s}\), which is a time-varying weighted digraph \(G_{s}\Big{(}F_{s},L_{s},A_{s}^{f},A_{s}^{l}\Big{)}\). For each service request \(s_{u}\in G_{s}\), \(F_{s}^{u}\) is the \(u\)th ordered VNF sequence of \(s_{u}\), \(f_{k}\in F_{s}^{u}\) is the \(k\)th VNF in the current service request, and \(L_{s}\) is the virtual link between these VNFs. \(A_{s}^{f}\) refers to the node attributes corresponding to the VNFs, including the network function type \(\text{Ty}_{s}^{f_{k}}\) of the current VNF. \(\text{Cpu}_{s}^{f_{k}}\) represents the required node resources, \(M_{s_{u}}\left(n_{i},f_{k}\right)\) is a Boolean variable of a VNF deployed location, while \(M_{s_{u}}\left(n_{i},f_{k}\right)=1\) indicates VNF \(f_{k}\) is deployed on the substrate node \(i\), and \(M_{s_{u}}\left(n_{i},f_{k}\right)=0\) means it is not deployed in that location. \(A_{s}^{l}\) refers to the link attributes between the VNFs, including the bandwidth resources \(\text{Bw}_{s}^{f_{k}f_{o}}\) required by the link, and a Boolean variable \(M_{s_{u}}\left(i_{sn}^{j},f_{s}^{f_{k}f_{o}}\right)\) of mapping relationship, while \(M_{s_{u}}\left(i_{sn}^{j},f_{s}^{f_{k}f_{o}}\right)=1\) indicates the virtual link \(l_{s}^{f_{k}f_{o}}\) is a mapping on the substrate link \(l_{sn}^{i,j}\), otherwise it is not.  
In particular, the deployment states of service requests and the usage of substrate network resources alter with time. The network states at current can be obtained by using the SDN/NFV centralized control function. The quantity of user service requests that each edge node can carry is relevant to the number of remaining resources and specific user requests. In order to describe the problem easily and clearly the main notation and its definition are as shown in Table 1.