An Efficient Approach Based on Ant Colony Optimization and Tabu Search for a Resource Embedding Across Multiple Cloud Providers

In cloud computing, a fundamental management problem with the Infrastructure as a Service (IaaS) model lies in the efficient embedding of computational and networking resources onto distributed virtualized infrastructures owned by independent cloud providers (CPs). In such a context, this issue usually referred to as the Virtual Network Embedding (VNE) problem, adds more complexity since the entire embedding process requires two mayor phases of operation: the multicloud virtual network requests (VNRs) splitting, followed by the intracloud VNR segments mapping. This paper focuses on the splitting phase problem, by proposing a VNRs splitting strategy formalized as an Integer Linear Program (ILP) model, with the objective of improving the performance and QoS of resulting mapped VNR segments, while minimizing the resource provisioning expenditures. As the VNE is classified as an NP-hard problem, a hybrid metaheuristic approach based on the Ant Colony Optimization (ACO) combined with the Tabu Search (TS) as local search operator, is proposed in order to find good feasible solutions in reasonable time. The simulation results show the efficiency of the proposed approach, which generates, in a highly reduced computing time, solution costs very close to the exact solution, with an average cost gap ranging from 0 percent to a maximum of 3.42 percent.