Multicast in extra-stage multistage interconnection networks

This paper studies the multicast problem in the multistage interconnection network (MIN) topology. A regular MIN is a unique path network and can provide only a single path choice in routing or multicasting. However, if the MIN is added with a few extra stages, it can offer greater routing flexibilities. Design implications of extra-stage MINs are discussed in this paper. An upper bound on the number of different multicast trees is derived. While the problem of generating all traffic-optimal multicast tree instances may require exponential complexity, generating a single instance of an optimum traffic multicast tree can be done in polynomial time. Performance comparison among some heuristic multicast algorithms as well as the impact of various inter-stage connection patterns in extra stages are shown using simulation.