A General Inside-Out Routing Algorithm for a Class of Rearrangeable Networks

In this paper, we present a generalized version of the routing algorithm[1] for a class of 2log_2 N-stage networks which are made by concatenating two log_2 Nstage blocking networks. We show that the generalized algorithm can also cover a class of(2log_2 N - 1)-stage networks. It is shown that the inside-out algorithm is a more general algorithm which covers a large class of inherently symmetric rearrangeable networks, including the Benes and its equivalent networks. Moreover, it is shown that the time complexity of the algorithm is in O(N), which is superior to that of the looping algorithm. The algorithm is discussed using a graph representation of the network and its connectivity properties are shown by a graph describing rule. To show that the algorithm covers a class of 2log_2 N-stage networks, we introduce the concept of a base-network. These base-networks satisfy some common connectivity properties, and we show that any concatenation of two base-networks can be routed by our new algorithm.