A Random Linear Network Coding Approach to Multicast
T. Ho, Muriel Médard, R. Koetter et al. · IEEE Transactions on Information Theory · 2006
We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching 1 with the code length. We also demonstrate that random linear 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 success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks
Cited by 2,553 works. doi:10.1109/tit.2006.881746
Authors
References
- Network information flow
- Randomized Algorithms
- Noiseless coding of correlated information sources
- Linear network coding
- An algebraic approach to network coding
- A Random Linear Network Coding Approach to Multicast
- The benefits of coding over routing in a randomized setting
- How Practical is Network Coding?
- Polynomial time algorithms for network information flow
- Bimodal multicast