On rearrangeability of tandem connection of banyan-type networks

A multistage interconnection network (MIN) consisting of 2 times 2 nodes constructs a nonblocking switch if the network is rearrangeable. When a 2ⁿ times 2ⁿ 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 gamma denote the guide permutation of a 2ⁿ times 2ⁿ banyan-type network and tau the trace permutation of another. These are permutations on numbers from 1 to n. This paper proves that, when the permutation gammatau^-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.