A NEW ROUTING ALGORITHM FOR A CLASS OF REARRANGEABLE NETWORKS

This paper presents a routing algorithm for a class of multistage interconnection networks. Specifically, the concatenation of two Omega networks which has 2 log2N stages is treated. It is shown that this kind of asymmetric Omega + Omega network can be converted into a symmetric Omega-1 x Omega network or a symmetric Omega x Omega-1 network. However, they have butterfly connections between the two center stages. A general algorithm is developed which routes a class of symmetric networks. The algorithm routes the network from center stages to outer stages at both the input and the output sides simultaneously. The algorithm presented is simpler and more flexible than the well-known looping algorithm in that it can be applied adaptively according to the structure of the network. It can be applied to routing the Omega-based networks regardless of the center-stage connection patterns, i.e., straight, skewed straight, simple butterfly or skewed butterfly as long as the networks are symmetric. The sufficient conditions for proper routing are shown and proved. In addition, an example is shown to demonstrate the algorithm.