Transposition networks as a class of fault-tolerant robust networks

Document Type



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.


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


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.