FRAMES - A SIMPLE CHARACTERIZATION OF PERMUTATIONS REALIZED BY FREQUENTLY USED NETWORKS

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