The twisted crossed cube
Authors:
- 31 October 2015
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 28 (5) , 1507-1526
Abstract
Summary: The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQn) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQn that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQn are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQn with crossed cube (CQn), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQn/CQn and better properties in other respects, for example, its connection complexity is half of that of TCQn/CQn when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQn/CQn. Copyright © 2015 John Wiley & Sons, Ltd.Keywords
Funding Information
- National Natural Science Foundation of China (NSFC) (61402183, 61272382)
- Guangdong Provincial Natural Science Foundation Team Project (10351806001000000)
- Guangdong provincial science and technology projects (2014B010117001, 2014A010103022, 2014A010103008)
- Fundamental Research Funds for the Central Universities (2015ZZ0038)
This publication has 25 references indexed in Scilit:
- Embedding meshes into twisted-cubesInformation Sciences, 2011
- A novel algorithm to embed a multi-dimensional torus into a locally twisted cubeTheoretical Computer Science, 2011
- Edge congestion and topological properties of crossed cubesIEEE Transactions on Parallel and Distributed Systems, 2000
- Gaussian Networks For Scalable Distributed SystemsThe Computer Journal, 1996
- The Mobius cubesIEEE Transactions on Computers, 1995
- Mengerian properties, hamiltonicity, and claw‐free graphsNetworks, 1994
- A new variation on hypercubes with smaller diameterInformation Processing Letters, 1993
- The crossed cube architecture for parallel computationIEEE Transactions on Parallel and Distributed Systems, 1992
- The twisted N-cube with application to multiprocessingIEEE Transactions on Computers, 1991
- Topological properties of hypercubesIEEE Transactions on Computers, 1988