Deng-Jyi Chen, M. S. Horng and Kuo-Lung Ku+
Institute of Department Science and Information Engineering
National Chiao Tung University
Hsin Chu, Taiwan 300, R.O.C.
+ Chung-San Institute of Science and Technology
Tao-Yuan, Taiwan, R.O.C.
Hypercube interconnection networks have been receiving considerable at tention in ghe supercomputing environment. Various hypercube multiprocessors have been commercialiaed in tecent years. Ome of the important issues in the design of parallel and distributed networks is network reliability. Current reliability analysesisof hypercube interconnection networkd reported in the literature are based on the degradation of cube dimensions and task-based execution behavior. So far, there is no model for the terminal relibility nanlysis of hypercubes. This paper discusses the terminal reliability modeling and analysis of hypercube interconnection networks. Terminal reliability is the probability that at least one path is working for the communication between a given source and a destination. Several reliability modeling concepts are introduced and used to compute the terminal reliability of gypercubes. Time complexity nanlysis and examples of these reliability modeling approaches are discussed in detail.
Keywords: hypercube, interconnection networks, terminal reliability, routing algorithms, graph
Received April 15, 1991; revised October 8, 1991.
Communicated by Wen-Tsuen Chen.
* An earlier version of this paper has been presented in the IEEE COPM EURO 91, Bologna, Italy, May 13-16, 1991.
Thiss research work is supported byt the National Science Council, R.O.C. under the contract #NSC-80-0408-E009-39.