A control algorithm for 3-stage non-blocking networks

Abstract

A pipelined control algorithm for a 3-stage nonblocking Clos network is described. The algorithm is readily applicable to many variations of 3-stage sparse crossbar networks. To speed up the algorithm a special search memory is used by the network controller to find a path from an input to an output. The setup time of the algorithm matches that of a centrally controlled crossbar network of the same size. The simplicity of the algorithm and the search memory allows a very fast implementation in VLSI, making it feasible to use these networks in very fast statistical switching systems.