Title

Transposition networks as a class of fault-tolerant robust networks

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, Tn. Transposition networks are studied rigorously. These networks are shown to be optimally fault tolerant. Tn is also shown to possess wide containers with short length. Fault diameter of Tn 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.

Identifier

DOI: 10.1109/12.485375

UNLV article access

Search your library

Share

COinS