On Rearrangeability of Tandem Connection of Banyan-Type Networks.

A multistage interconnection network (MIN) consisting of 2 x 2 nodes constructs a nonblocking switch if the network is rearrangeable. When a x 2n x 2n bit-permuting network is rearrangeable with the minimum depth of 2n - 1, the initial (resp. final) n stages of the network form a banyan-type network and hence the network is equivalent to the tandem connection between two banyan-type networks. Let γ denote the guide permutation of a 2n x 2n banyan-type network and τ the trace permutation of another. These are permutations on numbers from 1 to n. This paper proves that, when the permutation γτ-1 is the transposition between the number n and some number k < n, the tandem connection between the two networks is rearrangeable. This sufficient condition for rearrangeability covers a wide class of tandem connections. For example, the first network in tandem can be the omega network appended with the banyan exchange of any rank while the second is the reversed omega network. [ABSTRACT FROM AUTHOR]