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 , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Topologies for data center 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 networks. 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 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 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 endomorphism 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 :
Rapport
[Research Report] Inria Sophia Antipolis; I3S; Université Nice Sophia Antipolis; CNRS. 2015, pp.23


https://hal.inria.fr/hal-01149203
Contributeur : David Coudert <>
Soumis le : mercredi 6 mai 2015 - 15:59:22
Dernière modification le : samedi 17 septembre 2016 - 01:36:51

Fichier

research-report-20150506.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01149203, version 1

Collections

Citation

David Coudert, Guillaume Ducoffe. Data center interconnection networks are not hyperbolic. [Research Report] Inria Sophia Antipolis; I3S; Université Nice Sophia Antipolis; CNRS. 2015, pp.23. <hal-01149203>

Partager

Métriques

Consultations de
la notice

168

Téléchargements du document

231