A multi-stage network comprising (2×logd N)−1 stages is operated in strictly nonblocking manner for unicast, also in rearrangeably nonblocking manner for arbitrary fan-out multicast when s≧2 , and is operated in strictly nonblocking manner for arbitrary fan-out multicast when s≧3 , includes an input stage having N d switches with each of them having d inlet links and s×d outgoing links connecting to second stage switches, an output stage having N d switches with each of them having d outlet links and s×d incoming links connecting from switches in the penultimate stage. The network also has (2×logd N)−3 middle stages with each middle stage having s × N d switches, and each switch in the middle stage has d incoming links connecting from the switches in its immediate preceding stage, and d outgoing links connecting to the switches in its immediate succeeding stage. Also each multicast connection is set up by use of at most two outgoing links from the input stage switch.