Please login using the form on menu list.|
It is required to login for Full-Text PDF.
The Optimal Routing Algorithm in Hierarchical Cubic Network and Its Properties
Kyu Ho PARK
IEICE TRANSACTIONS on Information and Systems Vol.E78-D No.4 pp.436-443
Publication Date: 1995/04/20
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
hierarchical cubic network (HCN),
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.