Minimum-cost multicast over coded packet networks
Minimum-cost multicast over coded packet networks
复制标题
DOI：
10.1109/tit.2006.874523
复制
发表时间：
2005-03
影响因子：
2.5
通讯作者：
D. Lun;Niranjan Ratnakar;M. Médard;R. Koetter;David R Karger;T. Ho;E. Ahmed;Fang Zhao
中科院分区：
文献类型：
--
作者：
D. Lun;Niranjan Ratnakar;M. Médard;R. Koetter;David R Karger;T. Ho;E. Ahmed;Fang Zhao
我们考虑在编码分组网络上建立最低成本多播连接的问题，即分组网络中，发出分组的内容是接收分组内容的任意因果函数。我们同时考虑有线和无线分组网络，以及静态多播（在连接期间多播组的成员保持不变）和动态多播（多播组的成员随时间变化，节点加入和离开该组）。对于静态多播，我们将问题简化为一个多项式时间可解的优化问题，并提出了分散式算法来解决它。这些算法与现有的构建网络编码的分散式方案相结合，产生了一种完全分散的方法来实现最低成本多播。相比之下，即使使用集中式计算，在路由分组网络上建立最低成本的静态多播连接也是一个非常困难的问题，除了单播和广播连接的特殊情况。对于动态多播，我们将问题简化为一个动态规划问题，并应用动态规划理论来提出如何解决它。
We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.