Algorithms and Stability Analysis for Content Distribution over Multiple Multicast Trees
Algorithms and Stability Analysis for Content Distribution over Multiple Multicast Trees
复制标题
多播树内容分发算法及稳定性分析
DOI：
10.1109/tpds.2014.2315202
复制
发表时间：
2009-12
影响因子：
5.3
通讯作者：
Ye Xia
中科院分区：
文献类型：
--
作者：
Xiaoying Zheng;Chunglae Cho;Ye Xia
本文研究了将通用集群技术应用于高效内容分发的理论问题。在集群会话中，通过让会话中的所有节点交换文件块，将文件分发到所有接收者。通过通用分群，不仅会话内的所有节点，而且会话外的一些节点都可以参与块交换，以提高分发性能。我们提出了一个通用的集群模型，其中块沿着不同的斯坦纳树分布，这些斯坦纳树植根于源并覆盖所有接收者。我们假设块动态到达源并专注于寻找稳定的通用集群算法。为了实现吞吐量区域，通用集群通常涉及寻找最小成本 Steiner 树的树选择子问题，这是 NP 困难的。我们提出了一种采用近似树选择算法的通用蜂群方案。我们证明它在吞吐量降低的区域实现了网络稳定性，其中降低率不超过树选择算法的近似率。我们提出了第二种通用蜂群方案，该方案采用随机树选择算法。它达到了吞吐量区域，但稳定性结果较弱。综合仿真结果支持算法的稳定性分析。所提出的方案及其变体预计可用于具有海量内容和相对稳定的网络环境的基于基础设施的内容分发网络。
The paper investigates theoretical issues in applying the universal swarming technique to efficient content distribution. In a swarming session, a file is distributed to all the receivers by having all the nodes in the session exchange file chunks. By universal swarming, not only all the nodes in the session, but also some nodes outside the session may participate in the chunk exchange to improve the distribution performance. We present a universal swarming model where the chunks are distributed along different Steiner trees rooted at the source and covering all the receivers. We assume chunks arrive dynamically at the sources and focus on finding stable universal swarming algorithms. To achieve the throughput region, universal swarming usually involves a tree-selection subproblem of finding a min-cost Steiner tree, which is NP-hard. We propose a universal swarming scheme that employs an approximate tree-selection algorithm. We show that it achieves network stability for a reduced throughput region, where the reduction ratio is no more than the approximation ratio of the tree-selection algorithm. We propose a second universal swarming scheme that employs a randomized tree-selection algorithm. It achieves the throughput region, but with a weaker stability result. Comprehensive simulation results support the stability analysis of the algorithms. The proposed schemes and their variants are expected to be useful for infrastructure-based content distribution networks with massive content and relatively stable network environment.
登录
查看更多内容
影响因子：
1.2
作者：
Antonis Dimakis;J. Walrand
通讯作者：
Antonis Dimakis;J. Walrand
DOI：
10.1016/j.comnet.2015.03.004
发表时间：
2009-12
期刊：
Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference
影响因子：
--
作者：
Xiaoying Zheng;Chunglae Cho;Ye Xia-
通讯作者：
Xiaoying Zheng;Chunglae Cho;Ye Xia-
影响因子：
2.5
作者：
M. Neely
通讯作者：
M. Neely
DOI：
--
发表时间：
2003
期刊：
--
影响因子：
--
作者：
M. Neely
通讯作者：
M. Neely
DOI：
10.1016/j.comcom.2007.01.013
发表时间：
2007-11
期刊：
Comput. Commun.
影响因子：
--
作者：
Jangwon Lee;G. Veciana
通讯作者：
Jangwon Lee;G. Veciana