# Joint Deployment Optimization of Parallelized SFCs and BVNFs in Multi-Access Edge Computing
## 3 System Model and Problem Statement
### P-SFCs and BVNFs Deployment  
Each user request can be accepted under the following conditions: (i) starting from the source node, the user request traverses P-SFCs and reaches the destination node. The overall time does not exceed the delay requirement; (ii) the service reliability provided by P-SFCs and BVNFs must satisfy the reliability requirement. Therefore, when the mobile user sends their user request, P-SFCs and BVNFs are deployed in edge servers near users and process incoming user requests while satisfying delay and reliability requirements. To model the service reliability and delay of P-SFCs and BVNFs, we first define the deployment variables of P-SFC and BVNFs. The binary variable \(X_{i,j}^{l,k}\) is used to present the deployment of \(VNF^{l}\) in \(SFC_{i}\) on the edge server \(V_{j}\ \in V\) for processing sub-flow k of user request \(r_{i}\) such that:  
\[X_{i,j}^{l,k}= \begin{cases}1,&\text{if }VNF^{l}\text{ of }SFC_{i}\text{ is deployed on }V_{j}\text{ for sub-flow k of }r_{i}\\ \\ 0,&\text{otherwise}\end{cases}  \tag{1}\] \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Definition** \\ \hline \((BS\cup V,E)\) & The MEC network \\ \(E_{i,j}\) & The physical links between edge servers \(V_{i}\) and \(V_{j}\) \\ \(C_{i}\) & The resource capacity of edge servers \(V_{i}\) \\ \(F\) & The set of different VNFs \\ \(C_{f_{n}}\), \(P_{f_{n}}\) and \(R_{f_{n}}\) & The resource demand, processing capacity, and reliability of each VNF \(f_{n}\) \\  & seven tuple definition: \(s_{i}\) is the source node; \(d_{i}\) is the destination node of user request \(r_{i}\); \(D_{i}\) is end-to-end delay requirement; \(R_{i}\) is the reliability requirement; \(SFC_{i}\) is requested VNF chains; and \(t_{i}\) is data size of user request \(r_{i}\); \(n_{i}\) is the maximum number of sub-flows \\ \(X_{i,k}^{l,j}\) & Indicate the deployment of \(VNF^{l}\) in \(SFC_{i}\) on the edge server \(V_{j}\) \\  & for processing sub-flow k of user request \(r_{i}\) \\ \(Y_{l_{n}}^{k,i}\) & Indicate whether sub-flow k of traffic flow \(r_{i}\) pass through link \(E_{j,h}\) \\ \(Z_{i,l,j}\) & Indicate if BVNFs for \(VNF^{l}\) of traffic flow \(r_{i}\) is deployed on edge server \(V_{j}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: List of key notations in this paper. We use the discrete variable \(x_{i,j}^{I,k}\) to indicate the resource demand of \(VNF^{l}\) instances that are deployed in \(V_{j}\) for processing sub-flow \(k\) of user request \(r_{i}\). We also use the discrete variable \(r_{i,j}^{I,k}\ \in[0,\ t_{i}]\) to indicate the data size of sub-flow \(k\), which is processed by \(VNF^{l}\) instances on edge server \(V_{j}\). Considering the traffic routing, we next use a binary variable, whether sub-flow \(k\) of traffic flow \(r_{i}\) passes through link \(E_{j,h}\in E\) such that:  
\[Y_{i,k}^{j,h}= \begin{cases}1,&\text{ if sub-flow $k$ of traffic flow $r_{i}$ passes through link $E_{j,h}$}\\ \\ 0,&\text{ otherwise}\end{cases}  \tag{2}\]  
To record the number and preemption resources of BVNFs for traffic flow \(r_{i}\) deployed in edge server \(V_{j}\ \in V\), we use a binary variable \(Z_{i,j}^{l}\) to indicate if BVNFs for \(VNF^{l}\) of traffic flow \(r_{i}\) are deployed in the edge server \(V_{j}\ \in V\) such that:  
\[Z_{i,j}^{l}= \begin{cases}1,&\text{ if BVNFs for $VNF^{l}$ of $r_{i}$ is deployed on edge server $V_{j}$}\\ \\ 0,&\text{ otherwise}\end{cases}  \tag{3}\]  
We also use the discrete variable \(z_{i,j}^{l}\) to indicate the resource demand of BVNF instances for \(VNF^{l}\) deployed in \(V_{j}\). Next, we model the reliability and delay of P-SFCs and BVNFs. Note that the VNF instance failures are independent and do not impact each other. In the MEC network, the reliability of all \(VNF^{l}\) instances in SFC is positively correlated with the incoming traffic size and processing capacities. First, we define all instances of \(VNF^{l}\) as an instance set, record the length of it as \(|N_{a,l,i}|\), and obtain all non-repeating subsets of length \(1,\ 2,\dots,\ |N|\).