Network Coding

Course Objectives

In this course, we will cover basic ideas in “Network Coding” and introduce the required tools in order to prepare students to follow the main research directions in this field and prepare them to involve doing research in this area.

Course Contents and Syllabus

Network coding is a relatively new area that has been emerged in the framework of information flow through networks. The basic idea of network coding is to allow nodes in a network to compute functions of their incoming information messages before transmitting them to their neighbors. Thus it is more general than routing which is currently the dominant network information transfer paradigm. It is shown that by applying such more complex operations, we can achieve higher throughputs in networks.

In this class, we will cover the fundamental principles and applications of network coding. More specifically, the course contains the following subjects:

  • Part 1: Introduction, history and examples of network coding.
  • Part 2: Mathematical prerequisites
    • Finite fields,
    • Linear algebra,
    • Optimization and linear programming,
    • Information and coding theory.
  • Part 3: Fundamentals of network coding
    • The max-flow min-cut theorem,
    • The multi-source multicast problem (the main theorem of network coding),
    • Deterministic code design for network coding,
    • Randomized network coding.
  • Part 4: Advanced topics in network coding
    • Non-coherent network coding,
    • Throughput benefits of network coding,
    • Networks with delay and cycles.
  • Part 5: Applications of network coding
    • Wireless networks (e.g., XOR in the air, Physical layer network coding),
    • Content distribution systems,
    • Network monitoring,
    • Distributed Storage systems.

Main references of the course

  • “Network Coding Fundamentals,” by C. Fragouli and E. Soljanin, Now Publisher, 2007.
  • “Network Coding Applications,” by C. Fragouli and E. Soljanin, Now Publishers, 2008.
  • “Network Coding: an Introduction,” by T. Ho and D. Lun, Cambridge University Press, 2008.
  • “Network Coding – Fundamentals and Applications,” edited by M. Medard and A. Sprintson, Acadamic Press, 2012.

Additional references

  • “Information Theory and Network Coding,” by Raymond Yeung, Springer, 2008.
  • “Network Coding Theory,” by Raymond Yeung, S.-Y. R. Li, N. Cai and Z. Zhang, Now Publisher, 2006.

Some introductory papers on network coding

The following list will be growing gradually.

  • Network information flow, R. Ahlswede, N. Cai, S.-Y.R. Li, R.W. Yeung, IEEE Transactions on Information Theory, 2000.
  • An algebraic approach to network coding, R. Koetter, M. Medard, Transactions on Networking, 2003.
  • Network coding: An instant primer, C. Fragouli, J. Le Boudec, J. Widmer, 2006.
  • Polynomial time algorithms for multicast network code construction, S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, IEEE Transactions on Information Theory, 2005.
  • Network coding for large scale content distribution, C. Gkantsidis, P. R. Rodriguez, 2005.
  • Hot Topic: Physical-layer Network Coding, S. Zhang, S. C. Liew, P. P. Lam, 2006.
  • XORs in the Air: Practical Wireless Network Coding, S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, 2008.