Liens entre symétries et étirements de routages dans les réseaux d'interconnexions de centres de données

Description

Nous démontrons l'influence de propriétés des réseaux d'interconnexion de centres de données sur l'étirement obtenu pour des routages dits "géométriques". Ces routages reposent sur un plongement des sommets du graphe dans un espace métrique "simple" tel que le plan Hyperbolique. Les réseaux d'interconnexions des centres de données sont généralement conçus pour favoriser les symétries, celles-ci permettant de minimiser la congestion et à chaque entité d'exécuter le même protocole de routage. Nous montrons que les symétries d'un graphe ont un impact négatif sur les performances de certains routages géométriques. Plus précisément, nous prouvons que l'existence de symétries (endomorphismes) non-triviales dans le graphe entraîne un étirement des plus courts chemins qui est proportionnel au diamètre du graphe pour un grand nombre de routages géométriques. Nos résultats sont fondés sur une relation entre l'hyperbolicité d'un graphe (un paramètre qui capture plusieurs propriétés métriques du graphe) et l'existence de stratégies gagnantes dans une variante du jeu du Gendarme et du Voleur. Nous illustrons nos résultats avec quelques topologies usuelles de la littérature (grilles, hypercubes, de Bruijn, Fat-Tree, BCube, etc...).

Abstract

International audience

Additional details