Network coding: an instant primer

ABSTRACT

Network coding is a new research area that may have interesting applications in practical networking systems. With network coding, intermediate nodes may send out packets that are linear combinations of previously received information. There are two main benefits of this approach: potential throughput improvements and a high degree of robustness. Robustness translates into loss resilience and facilitates the design of simple distributed algorithms that perform well, even if decisions are based only on partial information. This paper is an instant primer on network coding: we explain what network coding does and how it does it. We also discuss the implications of theoretical results on network coding for realistic settings and show how network coding can be used in practice

REFERENCES

• 1: Avalanche: File swarming with network coding. http://research.microsoft.com/pablo/avalanche.aspx.
• 2: R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, July 2000.
• 3: K. Bhattad and K. R. Narayanan. Weakly secure network coding. In NetCod, Apr. 2005.
• 4: N. Cai and R. W. Yeung. Secure network coding. In ISIT, 2002.
• 5: C. Chekuri, C. Fragouli, and E. Soljanin. On average throughput and alphabet size in network coding. Accepted to IEEE Trans. Inform. Theory.
• 6: P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In Allerton, Oct. 2003.
• 7: S. Deb and M. Medard. Algebraic gossip: A network coding approach to optimal multiple rumor mongering. In Allerton, Oct. 2004.
• 8: A. G. Dimakis, V. Prabhakaran, and K. Ramchandran. Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes. In IPSN, Apr. 2005.
• 9: C. Fragouli and A. Markopoulou. A network coding approach to overlay network monitoring. In Allerton, Sept. 2005.
• 10: C. Fragouli and E. Soljanin. Decentralized network coding. Information Theory Workshop, Oct. 2004.
• 11: C. Fragouli, J. Widmer, and J.-Y. LeBoudec. A network coding approach to energy efficient broadcasting: from theory to practice. Technical Report LCA-REPORT-2005-009, accepted at Infocom 2006, EPFL, July 2005.
• 12: C. Gkantsidis and P. Rodriguez. Network coding for large scale content distribution. In Infocom, Miami, FL, Mar. 2005.
• 13: C. Gkantsidis and P. R. Rodriguez. Cooperative security for network coding file distribution. Technical Report accepted at Infocom, 2006.
• 14: T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In ISIT, July 2003.
• 15: T. Ho, B. Leong, Y. Chang, Y. Wen, and R. Koetter. Network monitoring in multicast networks using network coding. In ISIT, 2005.
• 16: T. Ho, B. Leong, R. Koetter, M. Mdard, M. Effros, and D. R. Karger. Byzantine modification detection in multicast networks using randomized network coding. In ISIT, 2004.
• 17: S. Katti, D. Katabi, W. Hu, H. Rahul, and M. Medard. The importance of being opportunistic: Practical network coding for wireless environments. In Allerton, 2005.
• 18: S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Trans. Inform. Theory, 49:371--381, Feb. 2003.
• 19: Z. Li and B. Li. Network coding in undirected networks. CISS, 2004.
• 20: Chae Hoon Lim , Pil Joong Lee, More Flexible Exponentiation with Precomputation, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.95-107, August 21-25, 1994
• 21: D. S. Lun, M. Medard, and M. Effros. On coding for reliable communication over packet networks. Allerton, 2004.
• 22: P. Pakzad, C. Fragouli, and A. Shokrollahi. On low complexity coding for line networks. ISIT, Australia, Sept. 2005.
• 23: D. Petrovic, K. Ramchandran, and J. Rabaey. Overcoming untuned radios in wireless networks with network coding. In NetCod, Italy, Apr. 2005.
• 24: Peter Sanders , Sebastian Egner , Ludo Tolhuizen, Polynomial time algorithms for network information flow, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777464]
• 25: A. Shokrollahi. Raptor codes. Submitted to IEEE Trans. Information Theory, 2004.
• 26: N. R. Wagner. The Laws of Cryptography with Java Code. Available online at Neal Wagner's home page.
• 27: J. Widmer, C. Fragouli, and J. Y. LeBoudec. Energy efficient broadcasting in wireless ad hoc networks. In NetCod, Apr. 2005.
• 28: Jörg Widmer , Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.284-291, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080147]
• 29: Y. Wu, P. A. Chou, and K. Jain. A comparison of network coding and tree packing. ISIT, 2004.
• 30: Y. Wu, P. A. Chou, and S.-Y. Kung. Information exchange in wireless networks with network coding and physical-layer broadcast. Technical Report MSR-TR-2004-78, Microsoft Research, Aug. 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Keywords:
network coding