Parallel routing algorithms in Benes-Clos networks

A new parallel algorithm for route assignments in Benes-Clos (1962, 1953) networks is studied. Most known sequential route assignment algorithms, such as the looping algorithm, are designed for circuit switching systems where the switching configuration can be rearranged at relatively low speed. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously, and accommodate packets requesting connections in real time as they arrive at the inputs. In this paper, we develop a parallel routing algorithm for Benes networks by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the networks. Our approach can handle partial permutations easily. The time complexity of our algorithm is O(log/sup 2/ N), where N is the network size. We also extend the algorithm and show that it can be applied to the Clos networks if the number of central modules is M=2/sup m/, where m is a positive integer. The time complexity is O(log N/spl times/log M) in this case.