For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Optimal Routing Algorithm in Hierarchical Cubic Network and Its Properties
San-Kyun YUN Kyu Ho PARK
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/04/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
interconnection network, hypercube, hierarchical cubic network (HCN), parallel processing, routing algorithm,
Full Text: PDF>>
A Hierarchical Cubic Network (HCN) is a hierarchical hypercube network proposed by Ghose. The HCN is topologically superior to many other similar networks, in particular, the hypercube. It has a considerably lower diameter than a comparable hypercube and is realized using almost half the number of links per node as a comparable hypercube. In this paper, we propose the shortest routing algorithm in HCN(n, n) and show that the diameter of HCN(n, n) with 22n nodes is n(n1)/31 which is about 2/3 of that of a comparable hypercube. We also propose the optimal routing algorithm in HCN(m, n) where mn and obtain that its diameter is n(m1)/31. Typical parallel algorithms run in HCN(m, n) with the same time complexity as a hypercube and the hypercube topology can be emulated with O(1) time complexity in it.