Optimisation pour le Provisionnement de Chaînes de Services Réseau

La virtualisation des reseaux, portee en partie par l'initiative virtualisation des fonctions de reseau (Network Function Virtualization-NFV), apporte une plus grande flexibilite aux operateurs de reseaux ainsi qu'une baisse des couts de gestion. Les fonctions reseau executees sur du materiel dedie peuvent maintenant etre executees par des serveurs virtuels. Un service correspond alors a une sequence de fonctions, appelee chaine de services, a effectuer dans un ordre precis sur l'ensemble des flots du service. Le probleme considere est alors de satisfaire les requetes des chaines de services tout en trouvant le meilleur compromis entre l'utilisation de la bande passante et le nombre d'emplacements pour heberger les fonctions reseau. Nous proposons un modele de generation de colonnes pour le routage et le placement de chaines de service. Nous montrons a l'aide d'experimentations poussees que nous pouvons resoudre le probleme de facon optimale en moins d'une minute pour des reseaux ayant une taille allant jusqu'a 65 noeuds et 16 000 requetes. Nous etudions aussi le compromis entre l'utilisation de la bande passante et le nombre de noeuds capables d'heberger des fonctions reseau.