Network Coding: Theory and Applications

(PhD Course – University of Catania – Fall 2013)

 

Abstract:

This PhD course provides an introduction to the rapidly growing research area of network coding. Network coding allows intermediate nodes in a network to manipulate data, for example by sending out packets that are combinations of previously received packets instead of simply forwarding them. For most practical purposes, these manipulations are linear operations over elements of a finite field. The initial theoretical results on network coding were followed by a wealth of applications in a number of different areas that show that the theoretical insights can be translated into practical gains. The PhD course is divided into three parts.

 

The first part provides the participants with the theoretical tools necessary to understand the field of network coding and focuses on the underlying algebraic principles. It will also introduce distributed randomized network codes and discuss their properties, including throughput, robustness, delay, and security. We will not assume any prior knowledge of advanced algebra or optimization.

 

The second part of the PhD course gives an overview of the different application areas and discusses, which types of networking problems are amenable to network coding (and which aren't). In particular, it covers practical algorithms for data gathering in sensor networks, routing in wireless mesh networks, peer-to-peer networking and content distribution, streaming applications, etc.

 

The third part will discuss implementation aspects in real-world systems. The constraints imposed by network devices in terms of available memory and computing power may differ by several orders of magnitude. As a consequence, the encoding and decoding algorithms need to be carefully adapted to the specific problem at hand. 

 

The course uses a learn-by-doing strategy to complement lectures. Thus, it will have a series of practical activities including demonstrations and class exercises based on the Kodo C++ library. Furthermore, the PhD course will have implementation projects, where small groups of students solve a network coding related problem using C++ and/or Android/iOS implementations. Theoretical problems are also possible upon agreement with the lecturers.

 

Lecturers:

Prof. Frank H. P. Fitzek (Aalborg University)

Assoc. Prof. Daniel E. Lucani (Aalborg University)

Dr. Morten V. Pedersen (Aalborg University)

 

Course information:

This course is offered in University of Catania, Italy with three full days of lecture and practical activities on September 30th, October 2nd and October 4th 2013.

Implementation and/or theoretical projects are part of the final examination.

 

Organizers:

Aalborg University and University of Catania.

Professor Sergio Palazzo is taking care of local arrangements.

 

Material:

 

Slides:

1) Inter-session network coding slides

2) Intra-session network coding slides

3) Bridging intra- and inter-session network coding slides

4) Use Cases slides

 

Programming:

1) Kodo training material (Readme file inside)

 

 

Recommended reading:

1.  T. Ho, D. S. Lun, “Network Coding: An Introduction,” Cambridge University Press, 2008.

2.     M. Médard, A. Sprintson, “Network Coding: Fundamentals and Applications,” Academic Press, 2011.

 

The students should read the following papers in preparation for the lectures:

 

1.  Katti, S., Rahul, H., Wenju, H., Katabi, D., Médard, M.,Crowford, J.,"XORs in the Air: Practical Wireless Network Coding," IEEE/ACM Transactions on Networking, vol. 16, no. 3, pp. 497-510, June 2008.

2.  Fragouli, C., Le Boudec, J. Y., Widmer, J., "Network Coding: An Instant Primer," SIGCOMM Comput. Commun. Rev. 36, 1, pp. 63-68, January 2006.