The Optimal Routing Algorithm in Hierarchical Cubic Network and Its Properties

San-Kyun YUN  Kyu Ho PARK  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.4   pp.436-443
Publication Date: 1995/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
Keyword: 
interconnection network,  hypercube,  hierarchical cubic network (HCN),  parallel processing,  routing algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
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.