Le Problème à trois Contraintes : Calcul et Déploiement de Segments de Routage

Jean-Romain Luttringer, Thomas Alfroy, Pascal Mérindol, François Clad, and Cristel Pelsser. 2021. Le Problème à trois Contraintes : Calcul et Déploiement de Segments de Routage. In AlgoTel. La Rochelle, France.

@inproceedings{Luttringer2021c,
	title        = {Le Problème à trois Contraintes : Calcul et Déploiement de Segments de Routage},
	author       = {Luttringer, Jean-Romain and Alfroy, Thomas and M{\'e}rindol, Pascal and Clad, François and Pelsser, Cristel},
	year         = 2021,
	month        = sep,
	booktitle    = {AlgoTel},
	address      = {La Rochelle, France},
	url          = {http://icube-publis.unistra.fr/5-LAMB21},
	abstract     = {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. Dans ce travail, afin de proposer une solution exacte mais pratique et efficace, nous tirons parti des avantages et in- conve´nients de SR ainsi que des limites inhe´rentes aux re´seaux d’ope´rateurs. Notre algorithme, BEST2COP, conc¸u pour eˆtre massivement paralle´lisable, re´sout efficacement DCLC meˆme lorsque la double valuation du graphe est ale´atoire. Que ce soit sur des graphes aux structures re´elles ou ale´atoires, BEST2COP re´sout DCLC en largement moins d’une seconde sur des domaines SR de plus de mille nœuds.},
	groups       = {National Conferences},
	keywords     = {Traffic engineering, DCLC, Segment Routing},
	pdf          = {https://hal.archives-ouvertes.fr/hal-03216327/file/best2cop.pdf},
	x-international-audience = {No},
	x-language   = {FR}
}