A Novel Low Cost Interconnection Architecture Based on the Generalized Hypercube
- 13 September 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 31 (3) , 647-662
Abstract
The generalized hypercube (GH) is one key interconnection network with excellent topological properties. It not only contains many other interconnection topologies, but also can be used to construct some data center networks, such as HyperX, BCube, FBFLY, and SWCube. However, the construction cost of GH is high since there are too many links in it. Therefore, in this paper, we propose a novel low cost interconnection architecture called the exchanged generalized hypercube (EGH). We study the properties of EGH, such as the number of edges, the degree of vertices, connectivity, diameter, and diagnosability. Then, we give a routing algorithm to find the shortest path between any two distinct vertices of EGH. Furthermore, we design an algorithm to give disjoint paths between any two distinct vertices of EGH. In addition, we propose two local diagnosis algorithms in EGH under PMC model and MM model, respectively. Simulation results demonstrate that even if the proportion of faulty vertices in EGH is up to 25%, the probability that these two diagnosis algorithms can successfully judge the status of vertices is more than 90%. The analysis shows that the construction cost of EGH is much less than GH.Keywords
Funding Information
- National Natural Science Foundation of China (61572337, 61872257)
- Natural Science Research of Jiangsu Higher Education Institutions of China (18KJA520009)
- Application Foundation Research of Suzhou of China (SYG201653)
- Priority Academic Program Development of Jiangsu Higher Education Institutions
This publication has 41 references indexed in Scilit:
- An exchanged folded hypercube‐based topology structure for interconnection networksConcurrency and Computation: Practice and Experience, 2015
- On Data Center Network Architectures for Interconnecting Dual-Port ServersIEEE Transactions on Computers, 2015
- The Extra Connectivity and Conditional Diagnosability of Alternating Group NetworksIEEE Transactions on Parallel and Distributed Systems, 2014
- Building a network highway for big data: architecture and challengesIEEE Network, 2014
- An efficient construction of one-to-many node-disjoint paths in folded hypercubesJournal of Parallel and Distributed Computing, 2014
- Arc fault tolerance of cartesian product digraphs on hyper arc connectivityInternational Journal of Computer Mathematics, 2014
- HyperX2009
- MIXING OF QUANTUM WALKS ON GENERALIZED HYPERCUBESInternational Journal of Quantum Information, 2008
- LINEAR LAYOUT OF GENERALIZED HYPERCUBESInternational Journal of Foundations of Computer Science, 2003
- Highly Fault-Tolerant Routings and Fault-Induced Diameter for Generalized Hypercube GraphsJournal of Parallel and Distributed Computing, 1997