Network Coding

News

2017/01/26

As agreed via Foodle before Christmas, the final exam will be held on Thursday, February 26, 2017 in room 03.07.023 starting at 02:00pm (during the usual lecture time slot). Depending on the number of participants we may relocate some students to another room on demand.

We we also agreed on a deadline for project submissions, which is March 14, 2017 (latest meaningful date before grading deadline).

There will be a written retake exam (time and location tba). Please note that for either exam a registration via TUMonline within the centrally announced registration periods is mandatory.

2016/10/24

Due to collegiate plenary meeting (Studentische Vollversammlung) there will be no lecture on Tuesday, November 15.

2016/10/16

The lecture starts as planned on Tuesday, October 16 on 10:00am in room 03.07.023. It may become a bit cuddly as the room has only ~28 seats. Please come nevertheless if you want to participate. As said before, we expect a significant drop-out rate, which is why we do not expect that the course will be remain crowded.

2016/10/12

According to TUMonline, the course is currently full. Do not care about that, your enroll anyway. We know from previous years that there is a significant drop-out rate during the first weeks. If your really want to participate, consider yourself in.

2016/08/17

The website for this lecture is online.

Lecture material

Lecture material is available at https://nc.net.in.tum.de and can be cloned using git clone https://nc.net.in.tum.de/.git.

Previous knowledge

Please note that we expect firm knowledge in the following areas:

• Grundlagen Rechnernetze und Verteilte Systeme (IN0010)
• Diskrete Strukturen (IN0015)
• Diskrete Wahrscheinlichkeitstheorie (IN0018)
• good programming skills in C (or C++)
• full compliance with kernel coding guidelines (we do not plan to do kernel programming)

Lecture

Conventional routing is unable to achieve a network's capacity as given by the min-cut max-flow theorem - a rather theoretical point of view. Network Coding (NC) is an approach to achieve this very capacity in practice and can thus be considered a generalization of routing. Just think about it: Intermediate nodes (let us call them "router") normally only send identical copies of previously received packets (forget about the headers). NC extends their capability by demanding that sent packets are arbitrary linear combinations of previously received packets. Sounds strange? It is…

Here is a brief example to make you curious: Assume A wants to transmit n packets over a lossy link to B. With conventional approaches, B would have to acknowledge successful receipt of each individual packet such that A can retransmit any packets that got lost in transmission. If you use NC, A does not send the actual information contained in each individual packet but linear combinations of all packets. Obviously, B needs n linear independent packets to decode. If any packet gets lost during transmission, B does not need to signal a specific loss to A. Instead, A continues to transmit random (independent) linear combinations of those n packets until B has assembled enough packets to decode the whole batch.

This example is very basic, and actually only even a degenerated case of NC. But it gives you the underlying idea. Now just assume there are not only A and B but a number of intermediate nodes, each of them listening, buffering packets, and sending linear combinations. Instead of deciding which specific packet to send where, those nodes have to decide how often a random linear combination is being broadcast.

The lecture is a combination of usual classes combined with practical sessions during classes, i.e., you are encouraged to bring your notebooks and participate in the projects.

The theoretic part of the lecture covers the following topics:

• NC as generalization of routing
• min-cut/max-flow theorem
• linear programming
• packet loss and channel estimation
• ARQ mechanisms
• random linear network coding (RLNC)
• applications of NC
• bidirectional coding
• NC in transport and link-layer protocols
• NC in wireless networks
• acknowledgement schemes for NC
• combination of NC on different layers

The practical part (projects) cover the following topics:

• socket programming
• IEEE 802.11 raw sockets
• implementation of RLNC and acknowledgement schemes
• window protocols for NC
• many more if you want

Exercise

Lecture with integrated exercises.

Projects

The lecture is complemented by integrated exercises and demonstrations. On that basis, students are encouraged to propose individual practical projects, which are worked on in the second half of the lecture. Those projects may be done in groups of at most two students and are supervised during class hours. At the end of the lecture period students should present their projects to their class mates by presentation and/or demonstration.

Registration

Lecture: You can register for the lecture via TUMonline. Please note that you have to register for exams separately.

Projects: tba

Exam: tba

Exam and bonus

Written exam (60%) and project (40%). Credits earned in the project are added to the exam result and considered as bonus if and only if the exam itself (without project) is passed with grading "4.0" or better. The project cannot worsen your final grade. The duration of the written exam is 90 minutes. You may use - 1 sheet of paper (A4, both sides, hand-written) and - a (non-electronic) dictionary without any additional comments.

Please bring your student card or identity card to the exam.