On multi-stream multi-source multicast routing

详细信息    查看全文

• 作者：Yuh-Rong Chen ; Sridhar Radhakrishnan ; Sudarshan Dhall ; Suleyman Karabuk
• 关键词：Multicast ; Multi-source ; Multi-tree ; Tree packing ; Optimization
• 刊名：Computer Networks
• 出版年：2013
• 出版时间：29 October, 2013
• 年：2013
• 卷：57
• 期：15
• 页码：2916-2930
• 全文大小：890 K

文摘

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 -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.