Premium
The twisted crossed cube
Author(s) -
Wang Xinyang,
Liang Jiarong,
Qi Deyu,
Lin Weiwei
Publication year - 2015
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3707
Subject(s) - interconnection , cube (algebra) , hypercube , routing (electronic design automation) , topology (electrical circuits) , dimension (graph theory) , fault tolerance , computer science , routing algorithm , fault (geology) , parallel computing , mathematics , combinatorics , distributed computing , computer network , routing protocol , geology , seismology
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 (TCQ n ) 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 TCQ n 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 TCQ n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ n with crossed cube (CQ n ), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ n /CQ n and better properties in other respects, for example, its connection complexity is half of that of TCQ n /CQ n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ n /CQ n . Copyright © 2015 John Wiley & Sons, Ltd.