On multi-stream multi-source multicast routing

Multicasting has been used to conserve bandwidth and reduce network traffic for delivering a single data stream to a set of destinations. The problem of conserving bandwidth is a challenging one when one considers multiple data streams with multiple sources for each and a set of destinations that subscribe to one or more of these streams. The Multi-stream Multi-source Multicast Routing Problem (MMMRP) is to determine multiple multicasting trees on a given network, rooted at sources (nodes in the network) that are responsible for delivering one or more data streams to a set of destinations. Since several multicast trees co-exist on the same network, our goal is to construct these trees in such a way that the minimum residual bandwidth on the links that are shared among the trees is maximized. We prove that MMMRP is NP-hard and apart from providing an IP formulation, we have also provided a heuristic algorithm MMForests, which runs in polynomial-time. We compared and contrasted MMMRP with known algorithms for the multicast tree packing problem and our exhaustive empirical evaluations show that our heuristic has a very low execution-time while achieving near-optimal residual bandwidth. In addition, our heuristic is very scalable as it is able to produce results for networks with thousands of nodes, unlike the other ones that are based on Steiner tree heuristics.