Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

A Game-Theoretic Algorithm for the Joint Routing and VNF Placement Problem

Ali El Amine 1 Olivier Brun 1 
1 LAAS-SARA - Équipe Services et Architectures pour Réseaux Avancés
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : Network Function Virtualization (NFV) simplifies the deployment of network services by leveraging virtualization technologies to make the management of network functions more flexible and cost efficient. The deployment of these services requires the allocation of Virtual Network Function-Forwarding Graphs (VNF-FGs), which implies placing and chaining VNFs according to the requests of VNF-FGs. In this paper, we consider the offline allocation of VNF-FGs problem to improve resource utilization and reduce total costs. We focus on how VNF-FG demands are routed so as to optimize resource utilization without adding capacity to the infrastructure. Given a non-linear cost function associated to each network resource, we formulate the problem as a non-linear single-path routing problem in an extended graph. Then, we propose to adapt a single-path routing heuristic algorithm inspired from game theory to solve it. We show that this algorithm converges and establishes its approximation ratio in a number of cases. Experimental results obtained for different network topologies and different cost functions show that this algorithm provides very good quality solutions with substantially lower computing times compared to the optimal solution.
Complete list of metadata
Contributor : Ali El Amine Connect in order to contact the contributor
Submitted on : Friday, April 22, 2022 - 7:02:09 PM
Last modification on : Monday, July 4, 2022 - 9:34:15 AM


Files produced by the author(s)


  • HAL Id : hal-03649739, version 1


Ali El Amine, Olivier Brun. A Game-Theoretic Algorithm for the Joint Routing and VNF Placement Problem. NOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium (NOMS 2022), Apr 2022, Budapest, Hungary. ⟨hal-03649739⟩



Record views


Files downloads