Title :
Link augmented binary (LAB)-tree: its structure, routing, and fault tolerance properties
Author :
Mittal, Ravi ; Jain, Bijendra N. ; Patney, Rakesh K.
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Madras, India
fDate :
30 Apr-2 May 1991
Abstract :
A new augmented binary tree multiprocessor architecture, called LAB-tree is proposed. It has short and regular redundant links. These interconnections improve many properties of a full binary tree, such as increased fault tolerance, reduced traffic congestion, efficient routing of messages, etc. It is shown that there exist at least two node disjoint paths between every pair of nodes in the LAB-tree. Also, all non-faulty nodes remain connected even in the presence of one faulty node at each level of the tree. The LAB-tree supports a simple routing algorithm
Keywords :
fault tolerant computing; multiprocessor interconnection networks; parallel algorithms; trees (mathematics); LAB-tree; augmented binary tree multiprocessor architecture; fault tolerance; interconnections; link augmented binary-tree; message routing; node disjoint paths; redundant links; routing algorithm; traffic congestion; Bandwidth; Binary trees; Communication networks; Computer architecture; Fault tolerance; Multiprocessor interconnection networks; Routing; Telecommunication traffic; Throughput; Tree graphs;
Conference_Titel :
Parallel Processing Symposium, 1991. Proceedings., Fifth International
Conference_Location :
Anaheim, CA
Print_ISBN :
0-8186-9167-0
DOI :
10.1109/IPPS.1991.153818
