Content distribution by multiple multicast trees and intersession cooperation: Optimal algorithms and approximations
Content distribution by multiple multicast trees and intersession cooperation: Optimal algorithms and approximations
复制标题
DOI：
10.1016/j.comnet.2015.03.004
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
Xiaoying Zheng;Chunglae Cho;Ye Xia-
中科院分区：
文献类型：
--
作者：
Xiaoying Zheng;Chunglae Cho;Ye Xia-
在传统的多个会话的海量内容分发中，会话形成独立的覆盖网络，独立运行，其中一些会话可能面临资源不足的问题，而另一些会话的资源过多。为了解决这个问题，我们考虑了通用的集群方法，它允许多个会话相互协作。我们描述了如何寻找最优资源分配以最大化会话效用之和的问题，并提出了一种次梯度算法，该算法收敛于时间平均意义下的最优解。这个解决方案涉及到寻找最小代价Steiner树的NP-Hard子问题。我们通过使用列生成方法来解决这一困难，该方法减少了Steiner树的计算次数。此外，我们还允许使用Steiner树子问题的近似解。证明了对整体问题的逼近比不小于对Steiner树子问题逼近比的倒数。仿真结果表明，通用蜂群机制提高了资源贫乏会话的性能，而对资源丰富的会话影响可以忽略不计。所提出的方法和算法对于基于基础设施的内容分发网络具有较长的会话时间和相对稳定的网络环境具有一定的参考价值。
In traditional massive content distribution with multiple sessions, the sessions form separate overlay networks and operate independently, where some sessions may suffer from insufficient resources 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. We formulate the problem of finding the optimal resource allocation to maximize the sum of the session utilities and present a subgradient algorithm which 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 less than the reciprocal of the approximation ratio 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. The proposed approach and algorithm are expected to be useful for infrastructure-based content distribution networks with long-lasting sessions and relatively stable network environment.