Demand-aware multi-source IP-multicast: Minimal congestion via link weight optimization

Multicast is a fundamental communication primitive that can improve the efficiency of many distributed systems. However, current algorithms to construct multicast trees only consider link capacities and are oblivious to the bandwidth demands of senders. Such demand-oblivious approaches can result in suboptimal resource allocations and congestion. In this work, we initiate the study of a demand-aware multisource IP-multicast. In particular, we consider how an operator can optimize link weights to minimize congestion along multiple (and hence possibly overlapping) multicast trees. We show that this problem is NP-hard even in very restricted settings such as (i) where there are only two possible link weight values or (ii) where the graph contains only a single receiver. To obtain optimal solutions as well as a baseline for comparison, we also present a mixed integer linear program. We then suggest two fast heuristics, DA Picky and DA-Hybrid, based on maximumbottleneck spanning trees. Our empirical results, based on real-world data, show that our algorithms outperform today’s demand-oblivious approach and scale to large networks.