The complexity of routing in Clos permutation networks
David M. Koppelman, A. Yavuz Oruç · IEEE Transactions on Information Theory · 1994
A lower bound on the amount of information necessary to compute the switch settings for a three-stage Clos network is derived. The bound is derived by considering the effect of a family of permutations, called balanced multiloops, on the settings of the switches of a Clos network. By carefully selecting these permutations, it is proven that there exists at least one switch in each stage whose setting depends upon at least (k/spl minus/3)(m/2+1)/2 assignments in the permutations to be routed for k/spl ges/4 where m is the number of center-stage switches and k is the number of input and output-stage switches. It is also proven that the setting of the input stage depends on at least m/spl minus/1 assignments. Lower bounds on the routing time of a three-stage Clos network on a variety of machine models follow immediately from these results. In particular, any constant fan-in implementation of any routing algorithm for such a network should have a time lower bound of /spl Omega/(log mk).>