# Joint Deployment Optimization of Parallelized SFCs and BVNFs in Multi-Access Edge Computing
## 3 System Model and Problem Statement
### Problem Statement
Given a MEC network \(G=(BS\cup V,\ E)\), in which a set \(U\) of mobile users with each mobile user \(i\)\(\in\)\(U\) sends a user request \(r_{i}\), the network throughput is \(\sum_{r_{i}\in R}x_{i}\), and the throughput maximization problem can be formulated as follows:  
\[\begin{split} max\sum\limits_{r_{i}\in R}x_{i}\\ s.t.\ (\ref{  
we record the previous server, current server, and next server that were traversed by the target sub-flow. We also record the communication distance to traverse these three servers as the target communication distance. The next step finds all feasible edge servers;
3. Next, we define a set of edge servers that deploy \(VNF^{l}\) instances traversed by the user request as a comparison set. Then, we select edge servers whose resource capacity exceeds resource demand from all edge servers except for edge servers in the comparison set. This operation ensures that the target sub-flow is split into two sub-flows and traverses different paths to decrease delay. Next, we insert these edge servers into a candidate set and record the transmission and processing capacities of different paths from the previous server to these edge servers and from these edge servers to the next server. Next, we find the target edge server to deploy a parallel VNF instance;
4. Then, we select the edge server with the highest capacity as the target server and define the flow that traverses it as the candidate flow. The next step splits and merges sub-flows to reduce delay;
5. To decrease delay, we split the target sub-flow into two sub-flows according to their transmission and processing capacities. We do not evenly split the size of the user request between all sub-flows and the candidate flow or the size of the target sub-flow between the target sub-flow and the candidate flow. Although the former can significantly reduce delay, it affects the delay and reliability of subsequent VNFs. The latter does not guarantee delay reduction if the communication distance of the candidate flow is too large.  
Based on the above discussion, there are two special cases that require different methods of splitting and merging: (i) when the number of sub-flows traversing the previous server and the next edge server exceeds one, we split the total data size of these sub-flows. As they traverse the same next edge server, the method does not affect the subsequent VNFs; (ii) when the situation depicted in Figure 3c occurs, we must guarantee that the communication distance of the candidate flow is less than the communication distance of the target sub-flow. The different ways to split and merge sub-flows are shown in Figure 3. Additionally, the flowchart of the delay-reduction scheme is shown in Figure 4.  
Figure 3: (a) Split target sub-flows; (b) merge and split multiple sub-flows; (c) schedule the traffic of target sub-flow to candidate flow. In Figure 3a, the sum of transmission and processing capacity of the target sub-flow and candidate flow is x and y, respectively.  
Second, to reduce the number of BVNFs, a reliability-enhancement priority is defined to measure the priority of deploying parallel VNFs for each VNF in SFC. The priority for \(VNF^{l}\) on \(SFC_{i}\) is defined as follows:  
\[P^{r}_{i,l}=1/r_{VNF^{l}} \tag{14}\]  
To ensure that deploying parallel VNFs can obtain high-reliability enhancement and the total size of these sub-flows remains the same, we design a reliability-enhancement scheme to select the VNF, sub-flow, and edge server. 1. If \(VNF^{l}\) has the highest priority and the number of parallel \(VNF^{l}\) instances does not exceed the maximum number of sub-flows, we select \(VNF^{l}\) as the critical VNF to obtain a high potential of reliability enhancement by deploying parallel VNF instances of \(VNF^{l}\)[25; 34]. In reverse, we select the next VNF with high priority as the critical VNF. We execute the above steps 2-3 to find the target sub-flow and all feasible edge servers. Then, we sort feasible edge servers by their transmission and processing capacities.