Application de la théorie des jeux à l'optimisation du placement et chaînage des VNFs

International audienceLa technologie Network Function Virtualization (VNF) vise à simplifier le déploiement des services réseau de manière flexible, automatisée et indépendante du fournisseur. Le déploiement de ces services nécessite l'allocation des Virtual Network Function-Forwarding Graphs (VNF-FGs), ce qui implique de placer et d'enchaîner les VNFs en fonction des requêtes des VNF-FGs. Dans ce travail, nous considérons le problème d'allocation hors-ligne des VNF-FGs pour améliorer l'utilisation des ressources du réseau afin de répondre à un maximum de demandes, et réduire les coûts. Etant donné une fonction coût non linéaire associée à chaque ressource réseau, nous formulons le problème comme un problème de routage non linéaire à chemin unique dans un graphe étendu. Ensuite, nous proposons un algorithme heuristique de routage inspiré de la théorie des jeux pour le résoudre. Nous montrons que cet algorithme converge et établissons son rapport d'approximation dans un certain nombre de cas. Les résultats expérimentaux obtenus pour différentes topologies de réseau et différentes fonctions de coût montrent que cet algorithme fournit des solutions de très bonne qualité avec des temps de calcul assez modestes