Network Coding (CITHN2002)

Lecture - Thu 10:30-14:00

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.

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