Near-Optimal Multicast Tree Construction in Leaf-Spine Data Center Networks
Shouxi Luo, Huanlai Xing, Ke Li · IEEE Systems Journal · 2019
In this paper, we revisit the optimization problem of constructing multicast trees for cloud applications in the context of leaf-spine data center network (DCN). On one hand, we find that, the maximum multicast rate a network can provide equals to the minimum of the maximum unsplit throughput it can provide to each of the receivers. On the other hand, by taking the characteristic of leaf-spine DCN into account, we prove that the optimal construction of multicast tree in leaf-spine DCNs is equivalent to the well-known problem of minimum set cover, distinguished from the conventional wisdom that models the problem as a general-purpose directed minimum Steiner. Based on these findings, we develop simple yet near-optimal algorithms to construct multicast trees and deal with network failures.