The packing problem of uncertain multicasts

Summary Multicast performs better than unicast in delivering the same content from a fixed single source to a set of destinations. Many efforts have been made to optimize such kind of deterministic multicast, such as minimizing the transmission cost of each multicast session. In practice, it is not necessary that the source of each multicast session has to be in a specific location, as long as certain constraints are satisfied. Accordingly, applications usually meet a novel multicast with uncertain sources, ie, uncertain multicast. That is, multiple nodes have the responsibility to act as the root node of a multicast session. Prior proposals have addressed an uncertain multicast by constructing the minimum cost forest. However, it is still unknown how to efficiently share the network resources, when a set of uncertain multicast occupies the network simultaneously. To tackle such a challenging issue, we present the packing problem of uncertain multicasts (MPU) to minimize the total transmission cost, under the constraint of link capacity. We prove that the MPU problem is NP‐hard. An intrinsic solution is constructing the minimum cost forest for each uncertain multicast individually. This method, however, is inefficient and may be infeasible because of the constraint of link capacity. Thus, we design 2 dedicated greedy methods, named priority‐based and adjusting congested link, to approximate the optimal solution. The comprehensive results indicate that both of our 2 methods can find a feasible solution for the MPU problem. Moreover, given a set of uncertain multicasts, the adjusting congested link method can generate a desired transmission structure for each uncertain multicast and achieve the least total cost when packing them.