Network Coding: Theory and Applications

(AAU – BME PhD Course – Summer 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, ranging from core network routers all the way down to mobile phones and tiny sensor nodes. The constraints imposed by these 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 will have a series of practical activities. An introduction to the C++ Kodo library for network coding will be given. Demonstrations and class exercises based on this C++ library will also take place during some of the lectures. Furthermore, the PhD course will have implementation projects, where small groups of students solve a network coding related problems using C++ and/or Android/iOS implementations. The projects will be initiated during the week of lectures and support from key personnel will be provided the second week of the course, which is entirely focused on the successful development of the projects.

 

Lecturers:

Prof. Muriel Médard (MIT)

Prof. Frank H. P. Fitzek (AAU)

Assoc. Prof. Daniel E. Lucani (AAU)

Dr. Morten V. Pedersen (AAU)

 

Course information:

This course is offered as part of the PhD classes in Aalborg University and BME with a workload of 6.0 ECTS. Students from AAU, BME, other PhD programs are welcomed to enroll. It will take place in Budapest (BME) with lectures from June 14 to 21, 2013. However, an additional week of supervised activities is envisioned to carry out the implementation projects until June 28. The projects are part of the final examination.

 

More information will be announced in due time.

 

Material:

 

Slides:

1) Inter-session coding slides

2) Intra-session coding slides

3) Kodo introduction slides

4) Intra-session complexity slides

5) Analog network coding slides

 

Programming:

1) Kodo training material (Readme file inside)

 

Organizers:

Aalborg University and BME, as part of the AAU – BME PhD program.

Local arrangements at BME are done by Professor Hassan Charaf.

 

 

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.