A Tabu search approach for a virtual networks splitting strategy across multiple cloud providers. (21st May 2020) - Diallo, Marieme; Quintero, Alejandro; Pierre, Samuel
This paper addresses the problem of computational and networking resources embedding across multiple independent cloud providers (CPs). We focus on the splitting phase problem by proposing a virtual network requests (VNRs) splitting strategy, which aims at improving the performance and the quality of service (QoS) of resulting mapped VNR segments. We formalise our splitting strategy as a mathematical maximisation problem with constraints by using an integer linear program (ILP). Since the VNRs splitting process is classified as an NP-hard problem, we propose a metaheuristic approach based on the Tabu search (TS), in order to find good feasible solutions in polynomial solving time. The simulations results obtained show the efficiency of the proposed algorithm, in comparison with the exact method and an other baseline approach. Solution costs are on average close to the upper bounds, with an average gap ranging from 0% to a maximum of 2.97%, performed in a highly reduced computing time.