A Random Linear Network Coding Approach to Multicast
Top Cited Papers
- 25 September 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 52 (10) , 4413-4430
- https://doi.org/10.1109/tit.2006.881746
Abstract
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 networksKeywords
This publication has 23 references indexed in Scilit:
- Dynamic Algorithms for Multicast With Intra-Session Network CodingIEEE Transactions on Information Theory, 2009
- Correlated data gathering in wireless sensor networks based on distributed source codingInternational Journal of Sensor Networks, 2008
- On the utility of network coding in dynamic environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- A Random Linear Network Coding Approach to MulticastIEEE Transactions on Information Theory, 2006
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Online multicast routing with bandwidth guarantees: A new approach using multicast network flowIEEE/ACM Transactions on Networking, 2003
- Linear network codingIEEE Transactions on Information Theory, 2003
- Low complexity algebraic multicast network codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Constructing a perfect matching is in random NCCombinatorica, 1986
- Linear codes for sources and source networks: Error exponents, universal codingIEEE Transactions on Information Theory, 1982