Routage résilient dans les réseaux SDN

International audienceLes réseaux SDN (software-defined networking) permettentàpermettent`permettentà un contrôleur centralisé de décider du routage. Afin d'´ etablir des routes fiables, il est souvent nécessaire de trouver plusieurs chemins dans le réseau ne partageant pas les mêmes ressouresàressoures`ressouresà risque, communément appelé SRLG pour Shared Risk Link Group. Tout en assurant cette fiabilité, l'objectif est aussi de minimiser un coût, qui intègre des indicateurs de congestion ou de latence. Ceprobì eme peutêtrepeutˆpeutêtre modélisé par un programme linéaire en nombres entiers (ILP). Nous proposons ici une méthode efficace pour sa résolution qui utilise une relaxation fractionnaire bien choisie, dont nous montrerons qu'elle m` ene en fait la plupart du tempsàtemps`tempsà une solutionentì ere. La résolution de ceprobì eme relaxé utilise une méthode de génération de colonnes (CG), o` u chaque colonne représente un chemin dans le réseau avec une notion de coût modifié prenant en compte les SRLGs ; les nouvelles colonnes peuventêtrepeuventˆpeuventêtre obtenues par un algorithme efficace de programmation dynamique quí etend les algorithmes classiques de calcul de plus court chemin. Afin de limiter l'explosion combinatoire potentielle, nous présentonsprésentons´présentonségalement une heuristique qui accélére le calcul d'une solution résiliente tout en préservant de très bonnes performances. Les résultats numériques montrent que notre approche donne une solution de très bonne qualité dans un temps de calcul raisonnable sur des instances de réseau réalistes