J. Xu
Q. Lee
University of Newcastle upon Tyne. 1994
This paper presents a quantitative and comprehensive analysis of topological properties of typical interconnection networks including D-ary trees, nearest-neighbour meshes (NNM), hypercubes and Illiac networks. An alternative measure of network fault tolerance is introduced and expressed as the ability of a system to preserve its topological characteristic(s). The new measure can reflect implicitly the capability of the system to map algorithms designed for its original topology onto its possible degraded forms in the presence of faults. The paper includes, for the first time, the derivation of closed form expressions for average communication delay in tree structures, NNM meshes and binary N-cube networks. For Illiac networks, a method for precisely computing maximum communication delay and average delay is developed, and it is concluded that the optimal step length s = [Ăn] for even [Ăn] and s = [Ăn] + 1 for odd [Ăn]. Based on these results, a new class of hyperbus networks is constructed. The proposed networks possess more attractive features, in terms of their flexibility in a trade-off between fault tolerance and computational performance, than other multibus networks such as spanning bus hypercubes and generalized hypercubes.