Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12]

@

Journal of Information Science and Engineering, Vol. 20 No. 6, pp. 1213-1229 (November 2004)

Novel Hierarchical Interconnection Networks for High-Performance Multicomputer Systems

Gene Eu Jan, Yuan-Shin Hwang*, Ming-Bo Lin+ and Deron Liang*
Department of Computer Science
National Taipei University
San Shia, 237 Taiwan
E-mail: gejan@mail.ntpu.edu.tw
*Department of Computer Science
National Taiwan Ocean University
Keelung, 202 Taiwan
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

This paper proposes several novel hierarchical interconnection networks based on Heawood graphs, namely, folded Heawood networks, root-folded Heawood networks, recursively expanded Heawood networks, and flooded Heawood networks. Like hypercubes and networks extended from Petersen networks, these hierarchical Heawood networks have the following properties: regular topology, high scalability, and small diameter. Due to these important properties, these hierarchical Heawood networks seem to have potential as alternatives for future interconnection structures of multicomputer systems. Furthermore, this paper will demonstrate that the routing and broadcasting algorithms for these proposed networks are as elegant as the algorithms for hypercubes and Petersen-based networks.

Keywords: broadcasting algorithm, routing algorithm, Heawood graph, Heawood networks, folded Heawood networks, root-folded Heawood networks, recursively expanded Heawood networks, flooded Heawood networks

Full Text () Retrieve PDF document (200411_11.pdf)

Received February 18, 2002; revised May 13, 2003; accepted August 14, 2003.
Communicated by Chu-Sing Yang.