Title: A Tabu search approach for a virtual networks splitting strategy across multiple cloud providers

Authors: Marieme Diallo; Alejandro Quintero; Samuel Pierre

Addresses: Department of Computing and Software Engineering, École Polytechnique de Montréal, C.P. 6079, succ. Centre-Ville, Montréal, QC, H3C 3A7, Canada ' Department of Computing and Software Engineering, École Polytechnique de Montréal, C.P. 6079, succ. Centre-Ville, Montréal, QC, H3C 3A7, Canada ' Department of Computing and Software Engineering, École Polytechnique de Montréal, C.P. 6079, succ. Centre-Ville, Montréal, QC, H3C 3A7, Canada

Abstract: 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.

Keywords: cloud computing; virtualised network infrastructures; resource splitting; optimisation; metaheuristics; Tabu search.

DOI: 10.1504/IJMHEUR.2020.107383

International Journal of Metaheuristics, 2020 Vol.7 No.3, pp.197 - 238

Received: 04 Apr 2018
Accepted: 13 Aug 2018
Published online: 26 May 2020 *