Transposition networks As a Class of Fault-tolerant Robust networks

Authors

Shahram Latifi, University of Nevada, Las VegasFollow
Pradip K. Srimani, Colorado State University - Fort CollinsFollow

Document Type

Article

Publication Date

2-1996

Publication Title

IEEE Transactions on Computers

Volume

45

Issue

2

First page number:

230

Last page number:

238

Abstract

The paper proposes designs of interconnection networks (graphs) which can tolerate link failures. The networks under study belong to a subclass of Cayley graphs whose generators are subsets of all possible transpositions. We specifically focus on star and bubble sort networks. Our approach is to augment existing dimensions (or generators) with one or more dimensions. If the added dimension is capable of replacing any arbitrary failed dimension, it is called a wildcard dimension. It is shown that, up to isomorphism among digits used in labeling the vertices, the generators of the star graph are unique. The minimum number of extra dimensions needed to acquire i wildcard dimensions is derived for the star and bubble sort networks. Interestingly, the optimally augmented star network coincides with the Transposition network, T_n. Transposition networks are studied rigorously. These networks are shown to be optimally fault tolerant. T_n is also shown to possess wide containers with short length. Fault diameter of T_n is shown to be n. While the T can efficiently embed star and bubble sort graphs, it can also lend itself to an efficient embedding of meshes and hypercubes.

Keywords

Cayley graphs; Computer network resources; Fault-tolerant computing; Hypercube networks (Computer networks); Parallel algorithms; Routing (Computer network management)

Disciplines

Computer Engineering | Digital Communications and Networking | Electrical and Computer Engineering | VLSI and Circuits, Embedded and Hardware Systems

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

Repository Citation

Latifi, S., Srimani, P. K. (1996). Transposition networks As a Class of Fault-tolerant Robust networks. IEEE Transactions on Computers, 45(2), 230-238.