Frames: a simple characterization of permutations realized by frequently used networks

Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks