Optimal distributed broadcasting with per-neighbor queues in acyclic overlay networks with arbitrary underlay capacity constraints
Optimal distributed broadcasting with per-neighbor queues in acyclic overlay networks with arbitrary underlay capacity constraints
复制标题
在具有任意底层容量限制的非循环覆盖网络中使用每邻居队列进行最优分布式广播
DOI：
10.1109/isit.2013.6620339
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Longbo Huang
中科院分区：
文献类型：
--
作者：
Shaoquan Zhang;Minghua Chen;Zongpeng Li;Longbo Huang
诸如P2P流媒体系统之类的广播系统代表着支持多达数百万在线用户的重要网络应用。高效的广播机制是系统设计的核心。尽管在开发高效的广播算法方面付出了大量努力，但以下重要问题仍然悬而未决：如何在每个用户仅为其直接邻居维护信息队列的情况下，以分布式方式实现最大广播速率？在这项工作中，我们首先推导出了在具有任意下层容量约束的非循环覆盖网络上的问题的创新公式。然后，在该公式的基础上，我们提出了一种分布式算法来实现最大的广播速率，并且每个用户在每个邻居上只维护一个队列。由于其轻量级的性质，我们的算法可以很好地随网络规模而扩展，并且对高系统动态保持健壮性。最后，通过仿真验证了该算法在不同网络容量模型下的最优性。仿真结果进一步表明，该算法的收敛时间随网络规模呈线性增长，这是一个值得进一步研究的方向。
Broadcasting systems such as P2P streaming systems represent important network applications that support up to millions of online users. An efficient broadcasting mechanism is at the core of the system design. Despite substantial efforts on developing efficient broadcasting algorithms, the following important question remains open: How to achieve the maximum broadcast rate in a distributed manner with each user maintaining information queues only for its direct neighbors? In this work, we first derive an innovative formulation of the problem over acyclic overlay networks with arbitrary underlay capacity constraints. Then, based on the formulation, we develop a distributed algorithm to achieve the maximum broadcast rate and every user only maintains one queue per-neighbor. Due to its lightweight nature, our algorithm scales very well with the network size and remains robust against high system dynamics. Finally, by conducting simulations we validate the optimality of our algorithm under different network capacity models. Simulation results further indicate that the convergence time of our algorithm grows linearly with the network size, which suggests an interesting direction for future investigation.