## 5 Cloud and Bandwidth Resource Allocation Problem
### SFC Routing and Cloud and Bandwidth Resource Allocation (SRCBA) Algorithm
In the allocation phase, the bandwidth allocation occurs on one out of the K-Shortest Paths. The computational complexity of the SRCBA heuristic depends on the evaluation procedure of the shortest path in the multi-stage graph. It is easy to prove that it is given by \(C_{SO}=O(NM_{max}N_{NFVI}^{2}log(M_{max}N_{NFVI}))\), where \(N_{NFVI}\) denotes the number of NFVI-PoPs. Next, we provide an example of application of the SRCBA algorithm in the case of a scenario reported in Figure 4. We consider the NFVI-PoP-1, NFVI-PoP-2 and NFVI-PoP-3, composed of two, two and one servers, respectively; the SRCBA algorithm needs to allocate cloud and bandwidth resources for an SFC composed of a Firewall (FW) and one Intrusion Detection System (IDS); we assume that one FW VNFI and one IDS VNFI have already been allocated in NFVI-PoP-1 and NFVI-PoP-3, respectively. We also report the average bandwidth costs of the network paths interconnecting the NFVI-PoPs; the interconnection costs equal 10$ and 15$ for the tuples (NFVI-PoP-1,NFVI-PoP-2) and (NFVI-PoP-2,NFVI-PoP-3) respectively; conversely, we denote with \(x\$\) the interconnection cost for the tuple (NFVI-PoP-1,NFVI-PoP-3). The core cost \(c^{core}\) is assumed to be equal to 0.25$; because we also assume that four and eight cores are needed to activate one FW VNFI and one IDS VNFI [21], their activation cost equals 2$ and 4$, respectively. Figure 4: Application example of the SFC Routing and Cloud and Bandwidth resource Allocation (SRCBA) algorithm to the case of a cloud infrastructure composed by three Network Function Virtualization Infrastructure-Point of Presence (NFVI-PoP), that is NFVI-PoP-1, NFVI-PoP-2 and NFVI-PoP-3 equipped with two, two and one servers, respectively; one FW VNFI and one IDS VNFI are already activated in the NFVI-PoP-1 and NFVI-PoP-3, respectively. The SRCBA algorithm has to accommodate a Service Function Chain (SFC) composed of one Firewall (FW) and one Intrusion Detection System (IDS). The application of the SRCBA algorithm in the TO solution case is illustrated in Figure 5a,b when the bandwidth interconnection cost \(x\) between NFVI-PoP-1 and NFVI-PoP-3 equals 3 and 8, respectively. As you can observe that the multi-stage graph is composed of four stages; because we assume that all of the servers have sufficient resources to support the Service Functions of the SFC, then all of the five servers are reported in the second and third stage; the nodes are labeled with the costs that equal zero for those servers in which one VNFI is already instantiated; otherwise, the activation cost of the VNFI is reported. The nodes are interconnected by edges labeled with the bandwidth costs. We report with thick lines the shortest path evaluated in the multi-stage graph and identify where the resources have to be allocated. You can observe that, when the bandwidth interconnection cost between NFVI-PoP-1 and NFVI-PoP-3 is low and equals 3, no activation of VNFI is decided and the VNFIs already instantiated are used as illustrated in Figure 6a; conversely, when the bandwidth interconnection cost is high and equals 8, in order to limit the bandwidth cost, the SFC is embedded in the NFVI-PoP-1 by activating one new IDS VNFI as highlighted in Figure 6b. Figure 5: Construction of the multi-stage graph for the Scalable Orchestration solution of the SRCBA algorithm. The cases \(x=3\$\) (**a**) and \(x=8\$\) (**b**) for the bandwidth interconnection cost between NFVI-PoP-1 and NFVI-PoP-3 of Figure 4 are reported. The application of the SRCBA algorithm in the scalable solution case is illustrated in Figure 7a,b when the interconnection bandwidth cost \(x\) between NFVI-PoP-1 and NFVI-PoP-3 equals 3 and 8, respectively. We achieve the same solution of the TO case but at lower computational complexity. The nodes of the multi-stage graph are no longer associated with the servers but to the NFVI-PoPs, and this leads to reducing the size of the graph and the computation time of the shortest path.