Transposition networks as a class of fault-tolerant robust networks

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