Content distribution by multiple multicast trees and intersession cooperation: Optimal algorithms and approximations
Xiaoying Zheng, Chunglae Cho, Ye Xia · 2009
The paper addresses the problem of massive content distribution in a network where multiple sessions coexist. In more traditional approaches, the sessions form separate overlay networks and operate independently from each other. In this case, some sessions may suffer from insufficient resources (e.g., aggregate upload bandwidth) even though other sessions have excessive resources. To cope with this problem, we consider the universal swarming approach, which allows multiple sessions to cooperate with each other by forming a shared overlay network. We formulate the problem of finding the optimal resource allocation to maximize the sum of the session utilities under the network capacity constraints. The solution turns out to be optimal sharing of multiple minimum-cost multicast trees. We present a subgradient algorithm and prove that, although the algorithm uses a single multicast tree per session at each iteration and hence does not converge in the conventional sense, it converges to the optimal solution in the time-average sense. The solution involves an NP-hard subproblem of finding a minimum-cost Steiner tree. We cope with this difficulty by using a column generation method, which reduces the number of Steiner-tree computations. Furthermore, we allow the use of approximate solutions to the Steiner-tree subproblem. We show that the approximation ratio to the overall problem turns out to be no more than that to the Steiner-tree subproblem. Simulation results demonstrate that universal swarming improves the performance of resource-poor sessions with negligible impact to resource-rich sessions.