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.
Complete list of metadatas

Cited literature [79 references]  Display  Hide  Download

https://hal.inria.fr/hal-01323301
Contributor : David Coudert <>
Submitted on : Monday, May 30, 2016 - 1:08:09 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM
Long-term archiving on : Wednesday, August 31, 2016 - 10:51:36 AM

File

data-centers--and--hyperbolici...
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

721

Files downloads

508