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

fYear

1991

fDate

30 Apr-2 May 1991

Firstpage

452

Lastpage

457

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1991. Proceedings., Fifth International

Conference_Location

Anaheim, CA

Print_ISBN

0-8186-9167-0

Type

conf

DOI

10.1109/IPPS.1991.153818

Filename

153818