Network Coding: Theory and Applications (PhD Course)

 

Abstract:

The 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. We will not assume any prior knowledge of advanced algebra or optimization. Among other things, network coding can be used to increase throughput and robustness as well as reduce storage requirements, delay, and energy consumption. 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. Finally, we will discuss implementation aspects in real-world systems. Such systems may range 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. As an example, the size of the finite field for the coding operations has an impact on network coding efficiency, but also on the encoding and decoding complexity. Coding operations may be sped up substantially through the use of specialized hardware, as evidenced by the successful implementation of network coding on Graphics Processing Units (GPUs). The energy consumed by the coding operations is of particular importance on mobile devices and needs to be considered to avoid offsetting the energy gains offered by network coding.

 

Lecturers:

Prof. Muriel MŽdard (MIT)

Prof. Frank H. P. Fitzek (AAU)

Assoc. Prof. Daniel E. Lucani (AAU)

Morten V. Pedersen (AAU)

 

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.

 

Materials:

Slides: Part I, Part II+III+IV+V+VI (Ref), Part VII, Part IX, Part X, Part XI, Part XIV, Part XV

Exercises: KODO, Problem Set

 

Grading:

Students are evaluated based on their performance in the following:

 

1.  Two paper reports. Each paper report will analyze a paper from a list to be provided in this web page. The student is expected to understand and summarize the key intuition, assumption, and results of the paper as well as discussing extensions of the work in question. Each report shall not exceed five pages (11 point, single space). Paper reports will be delivered by email within 2 weeks of the last lecture.

2.  Problem sets. Solved partially in class to motivate student participation and to reinforce key concepts through meaningful examples after class.

3.  Class participation.

 

Lectures:

1.  Introduction to network coding with application examples.

2.     Algebraic foundations of network coding.

3.     Multicast sessions and random network coding.

4.     Coding for erasures.

5.     Optimization and network coding.

6.     Feedback and delay.

7.     Inter-session coding in wireless networks.

8.  Finite field theory.

9.     Complexity issues of random linear network coding (RLNC).

10.Green issues with network coding: a cautious view.

11.Data dissemination and distributed storage.

12.Analog network coding

 

Practical Lectures:

1.     Software installation (using Kodo C++ library).

2.     Simulation and analysis of examples, focused on delay performance (using Kodo C++ library).

3.     Simulation and analysis of examples, focused on computational complexity (using Kodo C++ library).

4.     Exercises of intersession network coding, using Alice and Bob as well as Cross topologies.

 

Demonstrations:

1.     CATWOMAN testbed

2.     OpenSensor platform

 

Schedule: