Title :
Broadcasting on faulty hypercubes
Author :
Sui, Pao-Hwa ; Wang, Sheng-De ; Lee, Isaac Yi-Yuan
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
In this paper we propose a method for constructing the maximum number of edge-disjoint spanning trees (in the directed sense) on a hypercube with arbitrary one faulty node. Each spanning tree is of optimal height. By taking the common neighbor of the roots of these edge-disjoint spanning trees as the new root and reversing the direction of the directed link from each root to the new root, a spanning graph, consisting of n-1 edge-disjoint spanning trees of optimal height is formed. Broadcasting based on the spanning graph has an optimal bandwidth utilization and an optimal latency
Keywords :
fault tolerant computing; hypercube networks; broadcasting; edge-disjoint spanning trees; faulty hypercubes; optimal bandwidth utilization; optimal height; optimal latency; spanning graph; Algorithm design and analysis; Bandwidth; Broadcasting; Delay; Fault tolerance; Hypercubes; Multiprocessor interconnection networks; Network topology; Routing; Tree graphs;
Conference_Titel :
Parallel and Distributed Systems, 1994. International Conference on
Conference_Location :
Hsinchu
Print_ISBN :
0-8186-6555-6
DOI :
10.1109/ICPADS.1994.590062
