ERT Group Bonn

Dept. of Computer Science
University of Bonn, 
53117 Bonn

Contact: Christoph Günzel (guenzel@theory.cs.uni-bonn.de)

The ERT link page
Group Members


Erasure Resilient Transmission (ERT)

- A Short Introduction

ERT addresses the problem of transmitting large amounts of data over a lossy, packet-oriented networks. In our group, we focus on audio and video data, e.g. video conferencing or digital telephony, via the internet UDP protocol. Challenges for these kind of real-time applications are:

Why is TCP/IP not very useful?

Connection oriented protocols like TCP/IP inherently avoid any loss of data - internet users want to be sure that their email is delivered correctly and completely. Such protocols are based on direct communication between sender and receiver about the success of data transmission, thus enabling the sender to repeat transmission of lost packets.

While this is an appropriate way to deal with data like email, articles or ftp'd binary files (which are always used as a whole, so the receiver can accept eventual delays caused by re-transmitting lost packets rather than getting corrupt or even no data at all), it is much less useful for the field of real-time applications we talk about.

In audio or video conferencing, the resulting data have a stream-like character rather than the file like character of email or web pages. The participitiants of a video conference cannot accept their receiver to stop on each missing frame until re-transmission succeeds. Beyond that, data buffering would require large amounts of local memory on both the sender's and the receiver's side. Not to mention the increase of network traffic caused by sending (large) portions of data repeatedly.

Avoiding Packet Loss By Redundancy

The basic idea of using redundancy for loss reduction is quite simple: If you know that the network loses every second packet, you send every packet twice. Very easy!

But: We can not predict which packets will be lost or how many packets will be lost during the transmission. What we really need is a better way to encode our messages against losses. An sufficient approach we concentrate on is the use of  Forward Error Correcting Schemes (FEC). An encoding where complete recovery is possible from any set of packets equal to the length of the original message is called Maximum Distance Separable (MDS) code.

In our group we focus on the variants of the so-called Cauchy coding schemes and also on some other related coding schemes.
The Cauchy coding scheme was developed for the first time in "An XOR-Based Erasure-Resilient Coding Scheme" by J. Blömer, M. Kalfane, R. Karp, M. Karpinski, M. Luby and D. Zuckerman. Cauchy Matrices are used to generate the code in this work. We use the Cauchy coding scheme in our implementations.

The Cauchy Coding Scheme

Encoding:

Let's examine the process of creating a coding of a message M  = (M_1, ..., M_m) containing m packets.
We generate code C = (C_1, ..., C_n) containing n packets with a Cauchy Matrix as generator matrix s.t.

Decoding:

Because of the fact that we use an MDS code, we can guarantee, that the recovery of message M is possible if at least an arbitrary set of size m of the packets of code C arrive at the receiver.
Note: m is the number of packets of message M.

Further Enhancement By Priority Encoding

With the Cauchy coding scheme described above, erasure resilient transmission (ERT) over packet-oriented networks is possible. The price for avoiding packet losses is the increase of network traffic caused by the redundant data added to the original information.

In practice, there are two reasons for making highest efforts on reducing this redundancy. First, both on the sender's and on the receiver's side every additional packet means additional work to be done. The sender has to create and transmit the redundant data, the receiver has to swallow and separate it from the information necessary for decoding the message. Second, in many networks (e.g. the internet) a large amount of packet losses result from network overflow. So adding more traffic to compensate problems probably caused by too much traffic is a technique that should be handled most carefully.

An approach to reduce this redundancy overhead is to use variable redundancy coding. The main idea is that, instead of viewing a message as a monolithic chunk of data, we try to divide it into (many) portions which we can evaluate regarding their importance for the receiver. Each of these portions is then decoded individually, with an individual amount of redundancy corresponding to its importance.

What We Are Going To Do

In our group we want to focus on several applications such as:

Recent Work

Resources on ERT

See our ERT link page.

Authors: Carsten Oberscheid (obersche@cs.bonn.edu) and Christoph Günzel (guenzel@cs.bonn.edu)