Fully connected generalized butterfly fat tree networks

摘要

A generalized butterfly fat tree network comprising (log_d N) stages is operated in strictly nonblocking manner for unicast and 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 a leaf stage consisting of an input stage having; $$ \frac{N}{d}$$switches with each of them having d inlet links and s×d outgoing links connecting to its immediate succeeding stage switches, and an output stage having; $$ \frac{N}{d}$$switches with each of them having d outlet links and s×d incoming links connecting from switches in its immediate succeeding stage. The network also has (log_d N)−1 middle stages with each middle stage, excepting the root stage, having; $$ \frac{s\times N}{d}$$switches, and each switch in the middle stage has d incoming links connecting from the switches in its immediate preceding stage, d incoming links connecting from the switches in its immediate succeeding stage, d outgoing links connecting to the switches in its immediate succeeding stage, d outgoing links connecting to the switches in its immediate preceding stage, and the root stage having; $$ \frac{s\times 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 preceding stage.