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:**