Algorithmes d'approximation pour le placement de chaînes de fonctions de services avec des contraintes d'ordre

Le modele des reseaux programmables virtualises permet aux operateurs de telecommunications d'offrir des services reseaux complexes et flexibles. Un service se modelise alors comme une chaine de fonctions reseaux (firewall, compression, controle parental,...) qui doivent etre appliquees sequentiellement a un flot de donnees. Dans cet article, nous etudions le probleme du placement de fonctions de services qui consiste a determiner sur quels nœuds localiser les fonctions afin de satisfaire toutes les demandes de service, de facon a minimiser le cout de deploiement. Nous montrons que le probleme peut etre ramene a un probleme de Set Cover, meme dans le cas de sequences ordonnees de fonctions reseau. Cela nous permet de proposer deux algorithmes d'approximation a facteur logarithmique, ce qui est le meilleur facteur possible. Finalement, nous evaluons les performances de nos algorithmes par simulations. Nous montrons ainsi qu'en pratique, des solutions presque optimales peuvent etre trouvees avec notre approche.