Problème à trois Contraintes : calcul et déploiement de segments de routage

Luttringer, Jean-Romain Alfroy, Thomas Mérindol, Pascal Clad, François Pelsser, Cristel [UCL]

Longtemps freinée par des technologies peu extensibles et difficilesà automatiser, l'ingénierie de trafic retrouve peù a peu de son allant. D'une part, les services de communicationémergents, comme le cloud gaming et l'industrie 4.0, nécessitent des chemins spécifiques offrant des garanties strictes. D'autre part, Segment Routing (SR), une technologie de routage par la source plus extensible que le plan de contrôle MPLS, offre aux opérateurs la possibilité de déployer des chemins contraintsà grandeéchelle. Ces chemins peuvent par exemple respecter une contrainte de latence maximum tout en minimisant le "coût interne" pour l'opérateur (coût IGP). En effet, ce type de chemins est requis pour les applications nécessitant un haut niveau d'interactivité sans négliger la bande passante. Cependant, calculer de telles routes multi-contraintes est un problème NP-Difficile bien connu : DCLC. Bien que de nombreuses solutions existent, elles ne sont pas adaptéesà Segment Routing qui ajoute une contrainte opérationnelle aux deux contraintes de qualité de service. De plus, ces propositions n'offrent généralement pas de garanties fortes en terme de temps d'exécution. Dans ce travail, afin de proposer une solution exacte mais pratique et efficace, nous tirons parti des avantages et inconvénients de SR ainsi que des limites inhérentes aux réseaux d'opérateurs. Notre algorithme, BEST2COP, conçu pour etre massivement parallélisable, résout efficacement DCLC même lorsque la double valuation du graphe est aléatoire. Que ce soit sur des graphes aux structures réelles ou aléatoires, BEST2COP résout DCLC en largement moins d'une seconde sur des domaines SR de plus de mille noeuds.