Progress Report: NSF grant NCR-9416101
July 1996 to July 1997
In past reports, we reported on the development of several increasingly sophisticated demos to show the benefits of this approach. As we described previously, we have integrated PET into a version of the video-conferencing tool VIC to protect the real-time transmission of MPEG streams, and this worked very well.
The PET patent [2] issued in April of this year.
Over the past year, Michael Luby and Yulius Tjahjadi completely overhauled the PET API software library. The two main objectives were to make a set of clean and usable interfaces between the calling applications and the PET library, and to make it easy to plug in different forward error correcting (FEC) codes for use within PET. Both of these objectives were met, and there is now a clean version of the PET library written in C. We now have a description of the new API [5] for PET based on this revision.
For example, a standard solution to the problem of packet loss is to request retransmission of lost packets. For multicast applications with one sender and many receivers, this solution introduces technical difficulties. For example, consider a video server distributing a movie on the Internet to thousands of users. If the users lose different sets of packets, and each user requests retransmission of these packets from the server, the server will quickly become overwhelmed by these requests. More sophisticated solutions along these lines have been considered, including sending requests for retransmission only to nearby session participants, but these solutions as yet appear inadequate.
To exemplify the advantages of FEC, consider the following simple setting. Suppose that 10,000 users are receiving a file sent via a multicast transmission protocol, and the average rate of packet loss is 20%. Suppose the file consists of 64K packets of 512 bytes each, and thus the entire file is 32M. One way to ensure that all users receive all of the packets is to keep sending each packet until all users acknowledge its receipt. If the losses are independent for the different users, a simple calculation shows that on average each packet needs to be transmitted approximately six times.
Suppose instead an FEC code with a 3% length overhead (see the next subsection for a definition of length overhead) is used to add 64K redundant packets to each message before transmission. Suppose no user loses more than 62K packets out of the 128K packets associated with a message, i.e., the maximum loss rate is at most approximately two and a half times the average loss rate. Then, all users will receive enough of the encoding to decode the message. The total bandwidth used by the FEC solution is a factor of three smaller than the retransmission solution, and moreover the overall protocol is much simpler.
In the past year, Malik Kalfane has finished his Master's thesis [3] under the supervision of Luby. This thesis consists of a practical study of the implementations of the various erasure codes we have considered, both those designed by others and those designed by us, including variants of the codes described in [4].
Over the past two years, we have developed a completely new class of codes, which we call Tornado codes, which promise to make the FEC solution practical. We have written a preliminary paper [6] about this work, and also have given presentations [7] of this work around the world. Tornado codes have the property that slightly more than the ideal number of encoding packets must be received to decode the message: we call the per cent needed over the ideal number the length overhead (recall that the ideal number is the original number of message packets). By allowing some length overhead, we can develop much faster coding schemes. Tornado codes can be encoded and decoded in time proportional to the length of the encoding times a small constant that is independent of the number of redundant packets. This small constant, which we call the time overhead, is typically around six.
We have implemented these codes in software, and the results are very encouraging. As an example, we took a 32M byte file and partitioned it into 64K message packets of 512 bytes each. Using Tornado codes, we produced 128K encoding packets from these 64K message packets. We then ran 10,000 trials, where each trial consisted of randomly choosing and receiving encoding packets until there are enough to decode all of the original 32M byte file. In these 10,000 trials, the average length overhead was only 3.2%; in other words, about 66K encoding packets were enough to decode. Furthermore, in less than 1% of the trials was the length overhead more than 4.0%.
Although there is a modest length overhead using Tornado codes, the advantage is that the encoding and decoding times are very small. On a DEC Alpha machine, the time to produce the 128K encoding packets from the 64K message packets is just under two seconds, and the time to decode the 32M byte file from 66K encoding packets is also just under two seconds. The encoding and decoding times for a message and encoding of this size using standard FEC codes would be at least 10,000 times slower, i.e., tens of hours. Thus, the advent of Tornado codes makes software solutions possible for problems that are orders of magnitude larger than were previously conceivable.
We emphasize that Tornado codes have a number of important features:
We advocate the modular decomposition of data transmission protocols into a time scheduling policy, which determines when packets are to be sent, and a data selection policy, which determines what data is to be placed in each sent packet.
We concentrate on the data selection policy and require that the protocol will achieve high bandwidth utilization in transmitting any prefix of the transmitted message. We introduce a simple and universal data selection policy which we prove is close to optimal in the following sense: For any time scheduling policy and any network behavior, in the worst case prefix measure our data selection policy provably performs as well as any other data selection policy up to a constant additive term.
Our explicit modular decomposition of a transmission protocol
into two policies should be contrasted with existing network
protocols such as TCP/IP.
In implementations of TCP/IP, the data selection policy is
intertwined with the time scheduling policy.
It is not hard to see that any data transmission protocol,
including protocols such as TCP/IP that weren't designed with
two explicit separate policies, can be decomposed into a
time scheduling and data selection policy.
Our result shows that the performance of the overall
transmission protocol would not
degrade in performance (and could improve dramatically) if it
used our universal data selection policy in place of its own.
The most important consequence of this is that it reduces
the problem of designing a data transmission protocol
to the possibly easier task of designing the time scheduling policy.