Provably Efficient Algorithms for Placement of Service Function Chains with Ordering Constraints

Andrea Tomassilli 1 Frédéric Giroire 1 Nicolas Huin 1, 2 Stéphane Pérennes 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Le modèle des réseaux programmables (Software Defined Networks), permet de centraliser la gestion du réseau sur un ou plusieurs contrôleurs et par conséquent de découpler la fonction de contrôle des flux de données. Ce paradigme permet aux opérateurs de réseaux de télécommunications d'offrir des services réseaux complexes et flexibles. Un service se modélise alors comme une chaîne de fonctions réseaux (firewall, compression, contrôle parental ...) qui doivent être appliquées séquentiellement à un flot de données. Dans cet article, nous étudions le problème du placement de fonctions de services qui consiste à determiner sur quels noeuds localiser les fonctions afin de satisfaire toutes les demandes de service, de façon à minimiser le coût de déploiement. Nous montrons que le problème peut être ramené à un problème de Set Cover, même dans le cas de séquences ordonnées de fonctions réseau. Cela nous permet de proposer deux algorithmes d'approximation à facteur logarithmique, ce qui est le meilleur facteur possible. De plus, nous proposons un algorithme optimal dans le cas particulier ou la topologie des demandes est un arbre. Finalement, nous évaluons les performances de nos algorithmes par simulations. Nous montrons ainsi qu'en pratique, des solutions presque optimales peuvent être trouvées avec notre approche.
Type de document :
Rapport
[Research Report] RR-9141, Université Côte d'Azur, CNRS, I3S, France; Inria Sophia Antipolis. 2018
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01676501
Contributeur : Andrea Tomassilli <>
Soumis le : vendredi 5 janvier 2018 - 16:35:52
Dernière modification le : lundi 30 avril 2018 - 14:30:10
Document(s) archivé(s) le : jeudi 3 mai 2018 - 16:55:50

Fichier

RR-9141.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01676501, version 1

Collections

Citation

Andrea Tomassilli, Frédéric Giroire, Nicolas Huin, Stéphane Pérennes. Provably Efficient Algorithms for Placement of Service Function Chains with Ordering Constraints. [Research Report] RR-9141, Université Côte d'Azur, CNRS, I3S, France; Inria Sophia Antipolis. 2018. 〈hal-01676501〉

Partager

Métriques

Consultations de la notice

429

Téléchargements de fichiers

305