A NEW ROUTING ALGORITHM FOR A CLASS OF REARRANGEABLE NETWORKS

This paper presents a routing algorithm for a class of multistage inte rconnection networks. Specifically, the concatenation of two Omega net works 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. Howeve r, they have butterfly connections between the two center stages. A ge neral algorithm is developed which routes a class of symmetric network s. 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 alg orithm 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, s kewed straight, simple butterfly or skewed butterfly as long as the ne tworks are symmetric. The sufficient conditions for proper routing are shown and proved. In addition, an example is shown to demonstrate the algorithm.