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 the literature that only refer to sufficient bounds. Moreover, it is also demonstrated that, in the worst case of unrestricted fan-out and with a simple assumption on the path selection algorithm, the complexity of a N×N multicast network can be limited to O(N⁵³). Such complexity is lower than that relevant to a crossbar network of the same size