Topological properties of hierarchical cubic networks

Abstract

The hierarchical cubic network (HCN), which takes hypercubes as basic clusters, was first introduced in [6]. Compared with the hypercube of the same size, the HCN requires only about half the number of links and provides a lower diameter. This paper first proposes a shortest-path routing algorithm and an optimal broadcasting algorithm for the HCN. We then show that the HCN is optimal fault tolerant by constructing node-disjoint paths between any two nodes, and demonstrate that the HCN is Hamiltonian. Moreover, it is shown that the average dilation for hypercube emulation on the HCN is bounded by 2. This result guarantees that all the algorithms designed for the hypercube can be executed on the HCN with a small degradation in time performance.