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 subcl ass of Cayley graphs whose generators are subsets of all possible tran spositions. We specifically focus on star and bubble-sort networks. Ou r 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 vertic es, the generators of the star graph are unique. The minimum number of extra dimensions needed to acquire i wildcard dimensions is derived f or the star and bubble-sort networks. Interestingly, the optimally aug mented star network coincides with the Transposition network, T-n. Tra nsposition networks are studied rigorously. These networks are shown t o be optimally fault-tolerant. T-n is also shown to possess wide conta iners with short length. Fault-diameter of T-n is shown to be n. While the T-n can efficiently embed star and bubble-sort graphs, it can als o lend itself to an efficient embedding of meshes and hypercubes.