Low Complexity Routing Algorithm for Rearrangeable Switching Networks

Rearrangeable switching networks have been a topic of interest for a long time among the research community. Routing algorithms for this class of networks have attracted lots of researchers along with other related areas, such as modification of the networks structure, crosspoints reduction etc. In this paper a new routing algorithm is presented for symmetric rearrangeable networks built with 2 × 2 switching element. A new matrix based abstraction model is derived to determine conflict free routing paths for each input-output request. Each stage of a network is mapped into a set of sub-matrices and number of matrices in each stage correspond to number of subnetworks in that stage. Once the input permutation is given, matrix cells are populated with binary values depending on the position of the switching elements in the actual hardware and their mapped matrix cells. These binary values control the routing decision in the underlying hardware. This new routing algorithm is capable of connection setup for partial permutation, m̅ = ρN, where N is the total input numbers and m̅ is the number of active inputs. Overall the serial time complexity of this method is O(NlogN)¹ and O(m̅logN) where all N inputs are active and with m̅ <; N active inputs respectively. The time complexity of this routing algorithm in a parallel machine with N completely connected processors is O(log²N). With m̅ active requests the time complexity goes down to O(logm̅logN), which is better than the O(log²m̅ + logN), reported in the 2^1/2[((log²N-4logN)^1/2 -logN)] ≤ ρ ≤ 1. Later half of this paper demonstrates how this routing algorithm is applicable for crosstalk free routing in optical domain.