## 5 Cloud and Bandwidth Resource Allocation Problem
### SFC Routing and Cloud and Bandwidth Resource Allocation (SRCBA) Algorithm  
The SFC Routing and Cloud and Bandwidth resource Allocation (SRCBA) algorithm is based on the following two procedures. In the first one, the \(N\) SFCs are sorted in decreasing bandwidth order. The second procedure allows for: (i) the determination of the NFVI-PoP in which the VNFIs are located; (ii) the determination of the VNFIs in which the SFs are executed; and (iii) the determination of the network paths used to interconnect the VNFIs. The SRCBA specifies the number and the VNFI type to be allocated and the networks paths involved between NFVI-PoPs. Conversely, the cloud resource allocation in the servers and the bandwidth allocation in the NFVI-PoPs in order to interconnect servers and NFVI-PoP access nodes are delegated to another algorithm out of the scope of the paper. We can only say that the computational complexity of such an algorithm is negligible with respect to the one of the SRCBA algorithm because the application of the SRCBA algorithm involves the bulk of the computation by determining the number of VNFIs, VNFI type, VNFI locations and network paths in a domain composed of a set of NFVI-PoPs. The objective of SRCBA is both to share the VNFIs among SFCs and to re-use them as much as possible. A new VNFI is activated only when either cloud resources are not available among the ones already active or the re-use leads to high bandwidth costs. Next, we give further clarification about the second procedure of SRCBA. It allows for the choice of NFV-PoPs and network paths so as to minimize the sum of the cloud and bandwidth resource cost; it is applied for each SFC, it is devoted to build a multi-stage graph and to evaluate on it a least cost path that identifies the NFVI-PoPs on which the SFs of the SFCs have to be executed either by using a VNFI already activated or by activating one new VNFI. The construction of the multi-stage graph \(C_{i}^{MS}\) for the \(i\)-th SFC is accomplished as follows. If \(M_{i}\) is the number of SFs in the \(i\)-th SFC, \(G_{i}^{MS}\) is composed of \(M_{i}+2\) stages, numbered from 0 to \(M_{i}+1\). The 0-th and the (\(M_{i}+1\))-th stages are composed of one node for each one; a least cost path will be evaluated between these two nodes once the graph is built. The \(j\)-th stage contains \(n_{j}\) nodes, whose generic one is named \(v_{j,k}\) (\(j=1,\cdots,M_{i},k=1,\cdots,n_{j}\)), where \(n_{j}\) is the number of nodes in each stage and it equals the number of NFVI-PoPs in which processing resources are available to execute the \(j\)-th SF of the \(i\)-th SFC. In particular, notice how the execution of the SF may occur on a VNFI already activated or involve the instantiation of a new VNFI. The node \(v_{j,k}\) of the multi-stage graph is characterized by a cost referred to as \(c_{v_{j,k}}\) and characterizing the cost of executing the \(j\)-th SF of the \(i\)-th SFC in the NFVI-PoP associated with the node \(v_{j,k}\). The cost depends on whether a new VNFI needs to be activated and, in this case, it depends on the core cost \(c^{core}\). We assume that the cost is equal to zero in the case in which a VNFI can be re-used; otherwise, the cost equals \(c^{core}n_{h}^{c}\) if the SF is of the \(h\)-th type. An edge of the multi-stage graph characterizes the possibility of interconnecting the two VNFIs located in the NFVI-PoPs associated with the two nodes of the edge. The edge is labeled with the average bandwidth cost involved in carrying the bandwidth \(b_{i}\) on the K-Shortest Paths connecting the NFVI-PoPs associated with the two nodes of the edge. Once the multi-stage graph has been built, a shortest path is evaluated between the 0-th and the (\(M_{i}+1\))-th stages. The computed path determines: (i) whether new VNFI have to be allocated; (ii) in which NFVI-PoPs the cloud resources have to allocated and the SFs of the SFC have to be executed; and (iii) between which NFVI-PoPs the bandwidth resource has to be allocated.