Fast network controller for nonblocking multicast networks

In a nonblocking multicast network, any multicast 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 multicast networks have important applications in parallel and distributed processing and telecommunications. The network controller used for determining connection path routings figures critically in the performance of an interconnection network, particularly in real-time applications. This paper presents designs of a network controller for the currently best available nonblocking multicast networks with a constant number of stages. For a three-stage nonblocking multicast network of the type considered, 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, a network controller can determine connection path routings to satisfy a multicast connection request in O(log² r/log log r) gate propagations. The designs are also generalized to multistage 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 design of the controller is comparable in logic circuitry to that of a one-switch module. The network controller designs presented in this paper render the nonblocking multicast networks considered in this paper useful in applications requiring high-speed network connection path set-ups.