Abstract
Rearrangeable multistage interconnection networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, non-rearrangeable networks can have inexpensive routing algorithms, but no simple technique exists to characterix all the permutations realized on these netwarks. This paper introduces the concept of frame and shows how iit can be used to characterize all the permutations realized on various multistage inteirconnection networks. They include any subnetwork of the Benes network, the class of networks that are topologically equivalent to the baseline network, and cascaded baseline and shuffle-exchange networks. The question of how the addition of a stage to any of these networks affects the type of permutations realized by the network is precisely answered. Also, of interest from a theoretical standpoint, a new simple proof is provided for the rearrangeability of the Benes network.
Keywords
Terms- Multistage interconnection network, permutations, rearrangeability, topological equivalence, balanced matrices, frames
Date of this Version
July 1992