查看文章

We present a distributed randomized network coding approach for transmission and compression of information in general multi-source multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves optimal capacity with probability rapidly approaching 1 with the code length. We also demonstrate that randomized coding performs compression when necessary in a network, generalizing error exponents for linear Slepian-Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved performance and robustness. We illustrate some potential advantages of randomized network coding over routing in two examples of practical scenarios: distributed network operation and online algorithms for networks with dynamically varying connections. Our mathematical development of these results also provides a link between network coding and network flows/bipartite matching, leading to a new bound on required field size for centralized network coding on general multicast networks.