On the permutation capability of multistage interconnection networks

Abstract-We present analytic models for the blocking proba-bility of both unique path and multiple path multistage intercon-nection networks under the assumption of either permutation or random memory request patterns. The blocking probability of an interconnection network under the assumption of permutation requests is a quantitative measure of the network's permutation capability. We compare the performance of networks with approximately equivalent hardware complexity. It is shown that variations of banyan networks can be designed with extremely low blocking probabilities under the assumption of permutation requests. Index Terms-Banyan networks, crossbar networks, multi-stage interconnection networks, performance analysis. I