On Multi-stream Multi-source Multicast Routing

Multicasting is an efficient way to deliver multimedia content (streaming, for instance) to different locations in the network. While end-to-end real-time constraints are important for interactive applications, sustained availability of bandwidth is more important to the destinations for multimedia streaming. In this research, we address the problem of multi-stream multi-source multicast routing problem (MMMRP) where each data stream could have multiple sources that will serve it and each source can serve multiple data streams in a sustained manner. The goal of MMMRP is to construct a routing forest for each of the data streams and the destinations while maximizing the residual bandwidth. The residual bandwidth is the available bandwidth after all destinations have been served with their desired streams. Our problem is shown to be NP-hard and we provide an Integer Programming formulation together with an efficient heuristic algorithm (MMForests) based on widest-path algorithm. Our empirical evaluations show that our algorithm MMForests can construct the multicast routing trees both quickly and keeping the residual bandwidth close to the optimal.