Permutation capability of optical multistage interconnection networks

In this paper, we study optical multistage interconnection networks (MINs). Advances in electro-optic technologies have made optical communication a promising networking choice to meet the increasing demands for high channel bandwidth and low communication latency, of high-performance computing/communication applications. Although optical MINs hold great promise and have demonstrated advantages over their electronic counterpart, they also hold their own challenges. Due to the unique properties of optics, crosstalk in optical switches should be avoided to make them work properly. Most of the research work described in the literature are for electronic MINs, and hence, crosstalk is not considered. We introduce a new concept, semi-permutation, to analyze the permutation capability of optical MINs under the constraint of avoiding crosstalk, and apply it to two examples of optical MINs, banyan network and Benes network. For the blocking banyan network, we show that not all semi-permutations are realizable in one pass, and give the number of realizable semi-permutations. For the rearrangeable Benes network, we show that any semi-permutation is realizable in one pass and any permutation is realizable in two passes under the constraint of avoiding crosstalk. A routing algorithm for realizing a semi-permutation in a Benes network is also presented. With the speed and bandwidth provided by current optical technology, an optical MIN clearly demonstrates a superior overall performance over its electronic MIN counterpart.