The multilevel hypercube: A hierarchical hypercube network

In this paper, we present and analyze a new network called the Multilevel Hypercube network or MLH. The MLH is a hierarchical network that is built from small-size hypercube networks. The main advantage of the MLH over the hypercube is that it requires fewer links than a hypercube does with the same number of nodes, and the node degree, for the majority of the nodes, is less than the node degree in a comparable-size hypercube (few nodes have the same node degree as a comparable-size hypercube). The MLH also maintains the ease of routing enjoyed by the hypercube networks. In this paper, we investigate the MLH and introduce a simple and efficient routing algorithm. We also introduce simple and efficient algorithms for broadcasting and multicasting in the MLH. We study the average number of hops between two nodes in the MLH, assuming both uniform communication and clustered communication models. Finally, we compare the performance of our proposed network to other hierarchical networks.