Data center interconnection networks are not hyperbolic. (English) Zbl 1344.68173
Summary: 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 is 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.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C12 | Distance in graphs |
| 68M12 | Network protocols |
Keywords:
greedy routing scheme; metric embedding; graph endomorphism; Gromov hyperbolicity; Cayley graph; data center interconnection networkReferences:
| [1] | Akers, S.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Harary, F.; Hayes, J. P.; Wu, H.-J., A survey of the theory of hypercube graphs, Comput. Math. Appl., 15, 4, 277-289 (1988) · Zbl 0645.05061 |
| [3] | Mahafzah, M., Fault-tolerant routing in butterfly networks, J. Appl. Sci., 10, 11, 903-908 (2010) |
| [4] | Petrini, F.; Vanneschi, M., k-Ary n-trees: high performance networks for massively parallel architectures, (International Parallel Processing Symposium. International Parallel Processing Symposium, IPPS (1997), IEEE), 87-93 |
| [5] | De Rumeur, J., Communications dans les réseaux de processeurs (1994), Masson |
| [6] | Al-Fares, M.; Loukissas, A.; Vahdat, A., A scalable, commodity data center network architecture, ACM SIGCOMM Comput. Commun. Rev., 38, 4, 63-74 (2008) |
| [7] | Guo, C.; Lu, G.; Li, D.; Wu, H.; Zhang, X.; Shi, Y.; Tian, C.; Zhang, Y.; Lu, S., BCube: a high performance, server-centric network architecture for modular data centers, ACM SIGCOMM Comput. Commun. Rev., 39, 4, 63-74 (2009) |
| [8] | Guo, C.; Wu, H.; Tan, K.; Shi, L.; Zhang, Y.; Lu, S., DCell: a scalable and fault-tolerant network structure for data centers, ACM SIGCOMM Comput. Commun. Rev., 38, 4, 75-86 (2008) |
| [9] | Li, D.; Guo, C.; Wu, H.; Tan, K.; Zhang, Y.; Lu, S., Ficonn: using backup port for server interconnection in data centers, (International Conference on Computer Communications. International Conference on Computer Communications, INFOCOM (2009), IEEE), 2276-2285 |
| [10] | Xiao, W.; Liang, H.; Parhami, B., A class of data-center network models offering symmetry, scalability, and reliability, Parallel Process. Lett., 22, 04 (2012) · Zbl 1284.68055 |
| [11] | Camelo, M.; Papadimitriou, D.; Fabrega, L.; Vila, P., Geometric routing with word-metric spaces, Commun. Lett. IEEE, 18, 12, 2125-2128 (2014) |
| [12] | Camelo, M.; Papadimitriou, D.; Fàbrega, L.; Vilà, P., Efficient routing in Data Center with underlying Cayley graph, (Complex Networks V. Complex Networks V, Studies in Computational Intelligence, vol. 549 (2014), Springer), 189-197 |
| [13] | Camelo, M.; Vilà, P.; Fàbrega, L.; Papadimitriou, D., Cayley-graph-based data centers and space requirements of a routing scheme using automata, (International Conference on Distributed Computing Systems Workshops. International Conference on Distributed Computing Systems Workshops, ICDCS (2014), IEEE), 63-69 |
| [14] | Kleinberg, R., Geographic routing using hyperbolic space, (International Conference on Computer Communications. International Conference on Computer Communications, INFOCOM (2007), IEEE), 1902-1909 |
| [15] | Papadopoulos, F.; Krioukov, D.; Boguna, M.; Vahdat, A., Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces, ACM SIGMETRICS Perform. Evaluat. Rev., 37, 2, 15-17 (2009) |
| [16] | Cohen, N.; Coudert, D.; Lancin, A., On computing the Gromov hyperbolicity, ACM J. Exp. Algorithmics, 20, 1, 1-6 (2015) · Zbl 1347.68280 |
| [17] | Gromov, M., Hyperbolic groups, Essays Group Theory, 8, 75-263 (1987) · Zbl 0634.20015 |
| [18] | Boguna, M.; Papadopoulos, F.; Krioukov, D., Sustaining the Internet with hyperbolic mapping, Nat. Commun., 1, 62 (2010) |
| [19] | Cassagnes, C.; Tiendrebeogo, T.; Bromberg, D.; Magoni, D., Overlay addressing and routing system based on hyperbolic geometry, (IEEE Symposium on Computers and Communications. IEEE Symposium on Computers and Communications, ISCC (2011), IEEE), 294-301 |
| [20] | Matoušek, J., On embedding trees into uniformly convex Banach spaces, Israel J. Math., 114, 1, 221-237 (1999) · Zbl 0948.46011 |
| [21] | Verbeek, K.; Suri, S., Metric embedding, hyperbolic space, and social networks, (Annual Symposium on Computational Geometry. Annual Symposium on Computational Geometry, SCG (2014), ACM), 501-510 · Zbl 1395.05048 |
| [23] | Cannon, J. W., Geometric group theory, (Handbook of Geometric Topology (2002)), 261-305 · Zbl 0985.57004 |
| [24] | Chepoi, V.; Dragan, F. F.; Estellon, B.; Habib, M.; Vaxès, Y., Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs, (24th Symposium on Computational Geometry. 24th Symposium on Computational Geometry, SCG (2008), ACM), 59-68 · Zbl 1221.68295 |
| [25] | Chepoi, V.; Estellon, B., Packing and covering \(δ\)-hyperbolic spaces by balls, (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Lecture Notes in Computer Science, vol. 4627 (2007), Springer), 59-73 · Zbl 1171.05315 |
| [26] | Krauthgamer, R.; Lee, J. R., Algorithms on negatively curved spaces, (Symposium on Foundations of Computer Science. Symposium on Foundations of Computer Science, FOCS (2006), IEEE), 119-132 |
| [27] | Abu-Ata, M.; Dragan, F. F., Metric tree-like structures in real-life networks: an empirical study, Networks, 67, 1, 49-69 (2016) |
| [28] | Adcock, A. B.; Sullivan, B. D.; Mahoney, M. W., Tree-like structure in large social and information networks, (13th International Conference on Data Mining (2013), IEEE), 1-10 |
| [29] | Albert, R.; DasGupta, B.; Mobasheri, N., Topological implications of negative curvature for biological and social networks, Phys. Rev. E, 89, 3, Article 032811 pp. (2014) |
| [30] | Alrasheed, H.; Dragan, F. F., Core-periphery models for graphs based on their \(δ\)-hyperbolicity: an example using biological networks, (Complex Networks VI (2015), Springer), 65-77 |
| [31] | Kennedy, W.; Narayan, O.; Saniee, I., On the hyperbolicity of large-scale networks (2013), Tech. rep. |
| [32] | Ferretti, L.; Cortelezzi, M., Preferential attachment in growing spatial networks, Phys. Rev. E, 84, 1 (2011) |
| [33] | Papadopoulos, F.; Kitsak, M.; Serrano, M.; Boguná, M.; Krioukov, D., Popularity versus similarity in growing networks, Nature, 489, 7417, 537-540 (2012) |
| [34] | Akiyama, J.; Ando, K.; Avis, D., Eccentric graphs, Discrete Math., 56, 1, 1-6 (1985) · Zbl 0578.05055 |
| [35] | Buckley, F., Self-centered graphs, Ann. NY Acad. Sci., 576, 1, 71-78 (1989) · Zbl 0792.05050 |
| [36] | Benjamini, I.; Schramm, O., Finite transitive graph embeddings into a hyperbolic metric space must stretch or squeeze, (Geometric Aspects of Functional Analysis. Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 2050 (2012), Springer), 123-126 · Zbl 1261.53076 |
| [37] | De Ridder, H. N.; Bodlaender, H. L., Graph automorphisms with maximal projection distances, (Fundamentals of Computation Theory (1999), Springer), 204-214 · Zbl 0942.05047 |
| [38] | Potocnik, P.; Sajna, M.; Verret, G., Mobility of vertex-transitive graphs, Discrete Math., 307, 3—5, 579-591 (2007) · Zbl 1110.05046 |
| [39] | Neumann, W. D.; Shapiro, M., Automatic structures, rational growth, and geometrically finite hyperbolic groups, Invent. Math., 120, 1, 259-287 (1995) · Zbl 0831.20041 |
| [40] | Noguès, D., \(δ\)-hyperbolicité et graphes (2009), MPRI, Université Paris 7, Master’s thesis |
| [41] | Bondy, J. A.; Murty, U. S., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001 |
| [42] | Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (1997), Springer · Zbl 0873.05001 |
| [43] | Chen, W.; Fang, W.; Hu, G.; Mahoney, M. W., On the hyperbolicity of small-world and treelike random graphs, Internet Math., 9, 4, 434-491 (2013) · Zbl 1338.05244 |
| [44] | Mitsche, D.; Prałat, P., On the hyperbolicity of random graphs, Electron. J. Combin., 21, 2, 2-39 (2014) · Zbl 1300.05286 |
| [45] | Narayan, O.; Saniee, I.; Tucci, G. H., Lack of spectral gap and hyperbolicity in asymptotic Erdös-Renyi sparse random graphs, (International Symposium on Communications Control and Signal Processing. International Symposium on Communications Control and Signal Processing, ISCCSP (2012), IEEE), 1-4 |
| [46] | Brinkmann, G.; Koolen, J. H.; Moulton, V., On the hyperbolicity of chordal graphs, Ann. Comb., 5, 1, 61-69 (2001) · Zbl 0985.05021 |
| [47] | Wu, Y.; Zhang, C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 18, 1 (2011) · Zbl 1220.05020 |
| [48] | Cohen, N.; Coudert, D.; Ducoffe, G.; Lancin, A., Applying clique-decomposition for computing Gromov hyperbolicity (Jun. 2014), Inria, Research report RR-8535 |
| [49] | Rodríguez, J. M.; Sigarreta, J. M., Bounds on Gromov hyperbolicity constant in graphs, (Proceedings Indian Acad. Sci. (Mathematical Sciences), vol. 122 (2012), Springer), 53-65 · Zbl 1269.05090 |
| [50] | Soto Gómez, M. A., Quelques propriétés topologiques des graphes et applications à Internet et aux réseaux (2011), Univ. Paris Diderot (Paris 7), Ph.D. thesis |
| [51] | Wu, Y.; Zhang, C., Chordality and hyperbolicity of a graph (2009), Tech. rep. |
| [52] | Benjamini, I., Expanders are not hyperbolic, Israel J. Math., 108, 1, 33-36 (1998) · Zbl 0915.05072 |
| [53] | Malyshev, A., Expanders are order diameter non-hyperbolic (2015), Tech. rep. |
| [54] | Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 1, 47-57 (1979) · Zbl 0397.68062 |
| [55] | Kliegl, M.; Lee, J.; Li, J.; Zhang, X.; Guo, C.; Rincon, D., Generalized DCell structure for load-balanced data center networks, (INFOCOM IEEE Conference on Computer Communications Workshops (2010), IEEE), 1-5 |
| [56] | Bhuyan, L.; Agrawal, D., Generalized hypercube and hyperbus structures for a computer network, IEEE Trans. Comput., 100, 4, 323-333 (1984) · Zbl 0528.68002 |
| [57] | Coxeter, H. S.M., Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. (N.S.), 56, 413-455 (1950) · Zbl 0040.22803 |
| [58] | Ohring, S.; Das, S. K., Folded Petersen cube networks: new competitors for the hypercubes, IEEE Trans. Parallel Distrib. Syst., 7, 2, 151-168 (1996) |
| [59] | Huang, X.; Peng, Y., DCen: a dual-ports and cost-effective network architecture for modular datacenters, J. Comput. Inform. Syst., 10, 13, 5697-5704 (2014) |
| [60] | Jan, G. E.; Hwang, Y.-S.; Lin, M.-B.; Liang, D., Novel hierarchical interconnection networks for high-performance multicomputer systems, JISE J. Inf. Sci. Eng., 20, 1213-1229 (2004) |
| [61] | Fan, S., Weakly symmetric graphs and their endomorphism monoids, Southeast Asian Bull. Math., 27, 3 (2003) · Zbl 1052.05034 |
| [62] | Aigner, M.; Fromme, M., A game of cops and robbers, Discrete Appl. Math., 8, 1, 1-12 (1984) · Zbl 0539.05052 |
| [63] | Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 2, 235-239 (1983) · Zbl 0508.05058 |
| [64] | Quilliot, A., Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes (1983), Université de Paris VI: Université de Paris VI France, Ph.D. thesis |
| [65] | Chalopin, J.; Chepoi, V.; Nisse, N.; Vaxès, Y., Cop and robber games when the robber can hide and ride, SIAM J. Discrete Math., 25, 1, 333-359 (2011) · Zbl 1228.05213 |
| [66] | Koolen, J. H.; Moulton, V., Hyperbolic bridged graphs, European J. Combin., 23, 6, 683-699 (2002) · Zbl 1027.05035 |
| [67] | Preparata, F. P.; Vuillemin, J., The cube-connected cycles: a versatile network for parallel computation, Commun. ACM, 24, 5, 300-309 (1981) |
| [68] | Friš, I.; Havel, I.; Liebl, P., The diameter of the cube-connected cycles, Inform. Process. Lett., 61, 3, 157-160 (1997) · Zbl 1337.68204 |
| [69] | Wu, H.; Lu, G.; Li, D.; Guo, C.; Zhang, Y., MDCube: a high performance network structure for modular data center interconnection, (International Conference on Emerging Networking Experiments and Technologies (2009), ACM), 25-36 |
| [70] | Latifi, S.; Srimani, P., Transposition networks as a class of fault-tolerant robust networks, IEEE Trans. Comput., 45, 2, 230-238 (1996) · Zbl 1048.68522 |
| [71] | Bermond, J.-C.; Peyrat, C., De Bruijn and Kautz networks: a competitor for the hypercube?, (European Workshop on Hypercubes and Distributed Computers (1989), North Holland), 279-293 |
| [72] | Bermond, J.-C.; Fraigniaud, P., Broadcasting and gossiping in de Bruijn networks, SIAM J. Comput., 23, 1, 212-225 (1994) · Zbl 0802.68094 |
| [73] | Mao, J.-W.; Yang, C.-B., Shortest path routing and fault-tolerant routing on de Bruijn networks, Networks, 35, 3, 207-215 (2000) · Zbl 0967.68011 |
| [74] | Coudert, D.; Ferreira, A.; Pérennes, S., Isomorphisms of the de Bruijn digraph and free-space optical networks, Networks, 40, 3, 155-164 (2002) · Zbl 1064.68010 |
| [75] | Lichiardopol, N., Quasi-centers and radius related to some iterated line digraphs, proofs of several conjectures on de Bruijn and Kautz graphs, Discrete Appl. Math., 202, 106-110 (2016) · Zbl 1330.05055 |
| [76] | Kautz, W., Bounds on directed \((d, k)\) graphs. Theory of cellular logic networks and machines, 20-28 (1968), AFCRL-68-0668, SRI Project 7258, Final report |
| [77] | Cohen, N.; Coudert, D.; Lancin, A., Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs (Sep. 2012), Inria, Research report RR-8074 |
| [78] | Coudert, D.; Ducoffe, G.; Nisse, N., To approximate treewidth, use treelength!, SIAM J. Discrete Math. (2016), in press · Zbl 1341.05238 |
| [79] | Xiao, W.; Chen, W.; He, M.; Wei, W.; Parhami, B., Biswapped networks and their topological properties, (ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD, vol. 2 (2007), IEEE), 193-198 |
| [80] | Jonckheere, E.; Lou, M.; Bonahon, F.; Baryshnikov, Y., Euclidean versus hyperbolic congestion in idealized versus experimental networks, Internet Math., 7, 1, 1-27 (2011) · Zbl 1245.68033 |
| [81] | Li, S.; Tucci, G. H., Traffic congestion in expanders and \((p, \delta )\)-hyperbolic spaces, Internet Math., 11, 2, 134-142 (2015) · Zbl 1475.53046 |
| [82] | Borassi, M.; Chessa, A.; Caldarelli, G., Hyperbolicity measures “democracy” in real-world networks, Phys. Rev. E, 92 (2015) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
