Non Blocking Multicast Three-Stage Interconnection Networks

This paper deals with non-blocking properties of multicast three-stage interconnection networks. The necessary and sufficient condition for a strictly non blocking three-stage network is found and demonstrated. This condition represents a real innovative result with respect to those already available in literature that only refer to sufficient bounds. Moreover, it is also demonstrated that, in the worst case of unrestricted fan-our and with a simple assumption on the path selection algorithm, the complexity of a NxN multicast network can be limited to O(N-5 3). Such complexity is lower than that relevant to a crossbar network of the same size.