Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci    2013, Vol. 7 Issue (2) : 298-306    https://doi.org/10.1007/s11704-013-2016-7
RESEARCH ARTICLE
KMcube: the compound of Kautz digraph and M?bius cube
Xianpeng HUANGFU, Deke GUO(), Honghui CHEN, Xueshan LUO
National Key Laboratory of Information System Engineering, School of Information System and Management, National University of Defense Technology, Changsha 410073, China
 Download: PDF(396 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): GUO Deke,Email:guodeke@gmail.com   
Issue Date: 01 April 2013
 Cite this article:   
Xianpeng HUANGFU,Deke GUO,Honghui CHEN, et al. KMcube: the compound of Kautz digraph and M?bius cube[J]. Front Comput Sci, 2013, 7(2): 298-306.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-2016-7
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I2/298
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
doi: 10.1145/1402946.1402967
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
doi: 10.1145/1402946.1402968
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
doi: 10.1145/1594977.1592577
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
doi: 10.1016/j.ipl.2011.10.023
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
doi: 10.1109/TPDS.2006.137
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
doi: 10.1109/TPDS.2010.161
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
doi: 10.1109/TPDS.2008.102
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
doi: 10.1023/A:1019158831409
10 Shen H, Xu C, Chen G. Cycloid: a constant-degree and lookupefficient P2P overlay network. Performance Evaluation , 2006, 63(3): 195-216
doi: 10.1016/j.peva.2005.01.004
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
doi: 10.1109/TC.2011.30
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
doi: 10.1109/71.250115
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
doi: 10.1016/j.ipl.2010.06.010
14 Larson S, Cull P. TheM?bius cubes. IEEE Transactions on Computers , 1995, 44(5): 647-659
doi: 10.1109/12.381950
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
doi: 10.1109/IPPS.1995.395907
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
doi: 10.1109/INFCOM.2011.5935239
17 Panchapakesan G, Sengupta A. On a lightwave network topology using Kautz digraphs. IEEE Transactions on Computers , 1999, 48(10): 1131-1137
doi: 10.1109/12.805162
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
doi: 10.1016/S0045-7906(01)00021-0
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
doi: 10.1109/TPDS.2006.37
[1] Wenhao ZHOU,Juan CHEN,Chen CUI,Qian WANG,Dezun DONG,Yuhua TANG. Detailed and clock-driven simulation for HPC interconnection network[J]. Front. Comput. Sci., 2016, 10(5): 797-811.
[2] Lailong LUO,Deke GUO,Wenxin LI,Tian ZHANG,Junjie XIE,Xiaolei ZHOU. Compound graph based hybrid data center topologies[J]. Front. Comput. Sci., 2015, 9(6): 860-874.
[3] YANG Xuejun, YI Huizhan, QU Xiangli, ZHOU Haifang. Compiler-directed power optimization of high-performance interconnection networks for load-balancing MPI applications[J]. Front. Comput. Sci., 2007, 1(1): 94-105.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed