O(logm¯.logN) routing algorithm for (2logN−1)(2logN−1)-stage switching networks and beyond

• This paper proposes an algorithm that can work for both full and partial permutation.
• Time complexity of the proposed algorithm is better than any other algorithms in the literature.
• It has been shown that the proposed networks can be applicable for crosstalk free routing.
• Benefits of building similar networks built with bigger switching elements have been demonstrated.
• A detailed theoretical analysis has been given presenting the algorithm.

This paper addresses routing algorithm for a classic network called rearrangeable network with a complexity which is minimum than any other reported algorithms in this class. A new routing algorithm is presented for symmetric rearrangeable networks built with 2×22×2 switching elements. This new algorithm is capable of connection setup for partial permutation, m¯=ρN, where NN is the total input numbers and m¯ is the number of active inputs. Overall the serial time complexity of this method is O(NlogN)1 and O(m¯.logN) where all NN inputs are active and with m¯2×2>2×2) with shorter network depth. Routing algorithm for these new networks have been proposed by modifying the proposed algorithm for smaller switching elements networks. Also we shall look into the application of these networks in optical domain for crosstalk free routing.