Fast path routing techniques for nonblocking broadcast networks

In a nonblocking broadcast network, any broadcast connection request from an idle network input port to a set of idle network output ports can be realized without any disturbance (that is, rearrangement) of other existing connections. Nonblocking broadcast networks have important applications in parallel and distributed processing. The network controller used for determining connection path routings figures critically in the performance of an interconnection network, particularly in real-time parallel and distributed processing applications. In this paper, we will present designs of a network controller for the currently best available explicit constructions of nonblocking broadcast switching networks with a constant number of stages. For a three-stage nonblocking broadcast network of the type we consider wherein there are r switch modules in each of the first and third stages with n input ports and n output ports on each of these switch modules, it will be seen that a network controller can determine connection path routings to satisfy a broadcast connection request in O(log² r/log log r) gate propagations. The designs will also be generalized to multi-stage networks in the same order of path routing time. This contrasts favorably with the O(nr) steps required in the previous software control algorithm. Furthermore, even the most hardware intensive of the controller designs is comparable in logic circuitry to that of one switching module. The network controller designs presented in this paper render the nonblocking broadcast networks we consider useful in real-time parallel and distributed processing applications which require high-speed network connection path set-ups.