On Randomized Network Coding
On Randomized Network Coding
复制标题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
T. Ho;M. Médard;Jun Shi;M. Effros;David R Karger
中科院分区：
文献类型：
--
作者：
T. Ho;M. Médard;Jun Shi;M. Effros;David R Karger
我们考虑了从网络上的多个来源进行多播的随机网络编码方法，其中从输入中独立和随机选择线性映射到某些字段上的输出链接上。该方法首先在[3]中描述了，该方法为无环延迟网络提供了误差概率，就接收器数量和随机编码输出链接而言，它随着代码长度的指数降低。证明基于[2]将代数网络编码与网络流有关的结果。在本文中，我们将这些结果推广到具有循环和延迟的网络。我们还显示，对于任何给定的无环网络，它在相关网络问题中具有不可靠链接的连接可行性的可能性更紧密。由此，就链接故障概率和冗余量而言，在链接编码网络中，在链接冗余网络中获得了一个成功概率。
We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links over some field. This approach was first described in [3], which gave, for acyclic delay-free networks, a bound on error probability, in terms of the number of receivers and random coding output links, that decreases exponentially with code length. The proof was based on a result in [2] relating algebraic network coding to network flows. In this paper, we generalize these results to networks with cycles and delay. We also show, for any given acyclic network, a tighter bound in terms of the probability of connection feasibility in a related network problem with unreliable links. From this we obtain a success probability bound for randomized network coding in link-redundant networks with unreliable links, in terms of link failure probability and amount of redundancy.