# Joint Deployment Optimization of Parallelized SFCs and BVNFs in Multi-Access Edge Computing
## 3 System Model and Problem Statement  
### Network Topology  
The NFV-based MEC network consists of several edge servers, base stations, and mobile users, as shown in Figure 1. We model the network as an undirected graph \(G=(BS\cup V,\ E)\), where \(BS\) is a set of base stations, and \(E\) represents all physical links between base stations [33]. \(E_{i,j}\) indicates the physical links between edge server \(V_{i}\) and \(V_{j}\) with a transmission rate \(B_{i,j}\). \(V\) is a group of edge servers \(V_{i}\in\ V\) with a resource capacity \(C_{i}\). We assume that there are \(|F|\) types of VNFs in the network with different network functions. The set of different VNFs is denoted as \(F=\left\{f_{1},\ f_{2},\ldots,\ f_{|F|}\right\}\). The resource demand, processing capacity, and reliability of each VNF \(f_{n}\in\) F are \(C_{f_{n}}\), \(P_{f_{n}}\), and \(R_{f_{n}}\), respectively. To facilitate discussion, we use the number of resource units to represent resource demand, which can be obtained by the weighted sum of the number of different resources (e.g., CPU cores, storage). The reliability of each VNF is characterized in terms of mean time between failure (MTBF) and mean time to repair (MTTR), i.e., \(\text{MTBF}/(\text{MTBF}+\text{MTTR})\). Then, we assume that the active VNF instances and BVNFs of each VNF in SFC have the same resource demand, processing capacity, and reliability.  
Figure 1: The MEC network. Basic settings: There are two user requests, \(r_{1}\) and \(r_{2}\), with two SFCs, i.e., \(SFC_{1}\langle VNF_{1},VNF_{2},VNF_{3}\rangle\) and \(SFC_{2}\langle VNF_{1},VNF_{3}\rangle\). The source and destination nodes of these two user requests are \(BS_{1}\) and \(BS_{2}\) and \(BS_{1}\) and \(BS_{4}\), respectively. For user request \(r_{1}\), the \(VNF_{1}\) instance is deployed in edge server \(V_{1}\), with the \(VNF_{2}\) instance and the \(VNF_{3}\) instance in edge server \(V_{2}\). Thus, user request \(r_{1}\) can obtain the required network service by traversing the instances in the edge servers in order.  
Then, we define that the user request from mobile user \(U_{i}\) is represented by a tuple \(r_{i}=\langle s_{i},d_{i},D_{i},R_{i},SFC_{i},t_{i},\ n_{i}\rangle\), where \(s_{i}\) is the source node, i.e., the nearest base station where \(U_{i}\) sends user request \(r_{i}\), \(d_{i}\) is the destination node of user request \(r_{i}\), i.e., the edge server which processes user request \(r_{i}\) and return results, \(D_{i}\) is the end-to-end delay requirement, \(R_{i}\) is the reliability requirement with 0 < \(R_{i}\) 1, \(SFC_{i}\) is the requested VNF chain, which consists of \(L_{i}\) network functions \(VNF^{1},\ VNF^{2},\ldots,\ VNF^{L_{i}}\) in order, and \(t_{i}\) is the data size of user request \(r_{i}\). The set of user requests from all mobile users is denoted as \(R\). We also define \(n_{i}\) as the maximum number of sub-flows that each traffic flow of \(r_{i}\) can be split into. These sub-flows can merge to traverse the same VNF and be split to traverse different VNFs flexibly. As an assumption, when a mobile user is located in the overlapping area of the communication coverage of multiple base stations, it sends user requests to the nearest base station. We also assume that there is only one user request associated with each mobile user. Note that our work can be extended to deal with the case where there are multiple user requests from each mobile user by treating them as multiple user requests from different virtual users, and all of these virtual users are the aforementioned mobile user. Key notations used in this paper are summarized in Table 1.