On blocking probability of multicast networks

Multicast is a vital operation in both broad-band integrated services digital networks (BISDN) and scalable parallel computers. In this paper we look into the issue of supporting multicast in the widely used three-stage Clos network or v(m, n, r) network. Previous work has shown that a nonblocking v(m,n,r) multicast network requires a much higher network cost than a v(m,n,r) permutation network. However, little has been known on the blocking behavior of the v(m, n, r) multicast network with only a comparable network cost to a permutation network. In this paper we first develop an analytical model for the blocking probability of the v(m,n,r) multicast network and then study the blocking behavior of the network under various routing control strategies through simulations. Our analytical and simulation results show that a v(m,n,r) network with a small number of middle switches m, such as m -n + c or dn, where c and d are small constants, is almost nonblocking for multicast connections, although theoretically it requires m > 0(?i(logr/loglogr)) to achieve nonblocking for multicast connections. We also demonstrate that routing control strategies are effective for reducing the blocking probability of the multicast network. The best routing control strategy can provide a factor of two to three performance improvement over random routing. The results indicate that a v(m, n,r) network with a comparable cost to a permutation network can provide cost-effective support for multicast communication.