More on rearrangeability of combined (2n − 1)-stage networks

This paper considers a class of combined (2n − 1)-stage N × N interconnection networks composed of two n(= log2N)-stage omega-equivalent networks M(n) and M′(n). The two networks are concatenated with the last stage of M(n) overlapped with the first stage of M′(n), forming a combined (2n − 1) stage network. Though both Benes network and (2n − 1)-stage shuffle-exchange network belong to this class, the former one is a rearrangeable network, whereas the rearrangeability of the latter one is still an open problem. So far, there is no algorithm, in general, that may determine whether a given (2n − 1)-stage combined network is rearrangeable or not. In this paper, a sufficient condition for rearrangeability of a combined (2n − 1)-stage network has been formulated. An algorithm with time complexity O(Nn) is presented to check it. If it is satisfied, a uniform routing algorithm with time complexity O(Nn) is developed for the combined network. Finally, a novel technique is presented for concatenating two omega-equivalent networks, so that the rearrangeability of the combined network is guaranteed, and hence the basic difference between the topologies of a Benes network and a (2n − 1)-stage shuffle-exchange network has been pointed out.