Data center interconnection networks are not hyperbolic

David Coudert 1 Guillaume Ducoffe 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Topologies for data center interconnection networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection network. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller the gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center interconnection topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endo-morphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 639, pp.72-90. 〈10.1016/j.tcs.2016.05.025〉
Liste complète des métadonnées

Littérature citée [79 références]  Voir  Masquer  Télécharger
Contributeur : David Coudert <>
Soumis le : lundi 30 mai 2016 - 13:08:09
Dernière modification le : jeudi 7 février 2019 - 16:04:32
Document(s) archivé(s) le : mercredi 31 août 2016 - 10:51:36


Fichiers produits par l'(les) auteur(s)




David Coudert, Guillaume Ducoffe. Data center interconnection networks are not hyperbolic. Theoretical Computer Science, Elsevier, 2016, 639, pp.72-90. 〈10.1016/j.tcs.2016.05.025〉. 〈hal-01323301〉



Consultations de la notice


Téléchargements de fichiers