Complexité du calcul de chemins dans les réseaux multicouches

Overview & Synopsis

Les réseaux d'opérateurs sont constitués de différentes couches où plusieurs protocoles coexistent. Le passage d'un protocole à un autre peut se faire par conversion (changement d'en-tête des paquets), encapsulation (les paquets sont insérés dans d'autres paquets) ou désencapsulation (les paquets sont retirés d'autres paquets). Actuellement, la plupart de ces réseaux possèdent un plan de contrôle pour chaque couche pour gérer le routage, ce qui induit des chemins sous-optimaux et une surutilisation des ressources du réseau. L'idéal serait d'unifier les plans de contrôle et d'effectuer un calcul de chemins qui engloberait toutes les couches et tous les protocoles, aboutissant ainsi à un chemin globalement optimal. Cela nécessite la conception d'un algorithme qui prenne en compte les encapsulations de protocoles et les contraintes qu'ils impliquent. L'approche par la théorie des langages [LPB13] a donné le premier algorithme polynomial pour le calcul du plus court chemin prenant en compte les encapsulations de protocoles. Dans cet article, nous généralisons largement l'approche de [LPB13] en proposant un algorithme qui calcul le chemin de poids minimum selon n'importe quelle métrique additive, qui prend en compte tous les types de fonctions d'adaptation et dont la complexité est plus basse. Nous montrons également que le problème est NP-difficile sous contrainte de bande passante, même sous certaines restrictions sur le réseau.