KMcube: the compound of Kautz digraph and Möbius cube

Abstract

This paper introduces a novel interconnection network called KMcube (Kautz-Möbius cube). KMcube is a compound graph of a Kautz digraph and Möbius cubes. That is, it uses the Möbius cubes as the unit cluster and connects many such clusters by means of a Kautz digraph at the cost of only one additional arc being added to any node in each Möbius cubes. The topological benefits of both basic graphs are preserved in the compound network. It utilizes the topological properties of Möbius cubes to conveniently embed parallel algorithms into each cluster and the short diameter of a Kautz digraph to support efficient inter-cluster communication. Additionally, KMcube provides other attractive properties, such as the regularity, symmetry, and expandability. The proposed methodology for KMcube is further applied to the compound graphs of Kautz digraph and other Möbius-like graphs with the similar diameter to a Möbius cube.Moreover, other hybrid graphs of Kautz digraph and Möbius cubes are proposed and compared.

Keywords

interconnection network / Kautz digraph / Möbius cube / compound graph

References

[1] Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture. ACM SIGCOMM Computer Communication Review, 2008, 38(4): 63-74

[2] Guo C, Wu H, Tan K, Shi L, Zhang Y, Lu S. Dcell: a scalable and faulttolerant network structure for data centers. ACM SIGCOMM Computer Communication Review, 2008, 38(4): 75-86

[3] 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 Computer Communication Review, 2009, 39(4): 63-74

[4] Guo D, Zhu G, Jin H, Yang P, Chen Y, Yi X, Liu J. Möbius-debruijn: The product of möbius cube and debruijn digraph. Information Processing Letter, 2012, 112(5): 205-211

[5] Wang C, Xiao L, Liu Y, Zheng P. Dicas: an efficient distributed caching mechanism for P2P systems. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(10): 1097-1109

[6] Guo D, Wu J, Liu Y, Jin H, Chen H, Chen T. Quasi-kautz digraphs for peer-to-peer networks. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(6): 1042-1055

[7] He Y, Liu Y. VOVO: vcr-oriented video-on-demand in large-scale peerto-peer networks. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(4): 528-539

[8] Cull P, Larson S. Routing in twisted cube-like networks. In: Proceedings of the 2000 International Conference on Communications in Computing. 2000, 225

[9] Agrawal D, Chen C, Burke J. Hybrid graph-based networks for multiprocessing. Telecommunication Systems, 1998, 10(1): 107-134

[10] Shen H, Xu C, Chen G. Cycloid: a constant-degree and lookupefficient P2P overlay network. Performance Evaluation, 2006, 63(3): 195-216

[11] Shen H, Xu C. Leveraging a compound graph-based dht for multiattribute range queries with performance analysis. IEEE Transactions on Computers, 2012, 61(4): 433-447

[12] Chen C, Agrawal D. dBCube: a new class of hierarchical multiprocessor interconnection networks with area efficient layout. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(12): 1332-1344

[13] Guo D, Chen H, He Y, Jin H, Chen C, Chen H, Shu Z, Huang G. KCube: a novel architecture for interconnection networks. Information Processing Letters, 2010, 110(18): 821-825

[14] Larson S, Cull P. TheMöbius cubes. IEEE Transactions on Computers, 1995, 44(5): 647-659

[15] Singhvi N, Ghose K. The Mcube: a symmetrical cube based network with twisted links. In: Proceedings of the 9th International Parallel Processing Symposium. 1995, 11-16

[16] Guo D, Chen T, Li D, Liu Y, Liu X, Chen G. Bcn: expansible network structures for data centers using hierarchical compound graphs. In: Proceedings of the 2011 IEEE INFOCOM. 2011, 61-65

[17] Panchapakesan G, Sengupta A. On a lightwave network topology using Kautz digraphs. IEEE Transactions on Computers, 1999, 48(10): 1131-1137

[18] Miller M, Širán J. Moore graphs and beyond: a survey of the degree/ diameter problem. Electronic Journal of Combinatorics, 2005, 61: 1-63

[19] Ghozati S, Smires T. The fastcube: a variation on hypercube topology with lower diameter. Computers & Electrical Engineering, 2003, 29(1): 151-171

[20] Park J, Kim H, Lim H. Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(3): 227-240

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg