Effective Erasure Codes for Reliable Computer Communication Protocols Luigi Rizzo Dip. di Ingegneria dell'Informazione, Universitk di Pisa via Diotisalvi 2 - 56126 Pisa (Italy) - email: 1 .r±zzo©±et .un±p±. it Abstract Reliable communication protocols require that all the intended recipients of a message re- ceive the message intact. Automatic Repeat reQuest (ARQ) techniques are used in unicast protocols, but they do not scale well to multicast protocols with large groups of receivers, since segment losses tend to become uncorrelated thus greatly reducing the effectiveness of retransmissions. In such cases, Forward Error Correction (FEC) techniques can be used, consisting in the transmission of redundant packets (based on error correcting codes) to allow the receivers to recover from independent packet losses. Despite the widespread use of error correcting codes in many fields of information process- ing, and a general consensus on the usefulness of FEC techniques within some of the Internet protocols, very few actual implementations exist of the latter. This probably derives from the different types of applications, and from concerns related to the complexity of implementing such codes in software. To fill this gap, in this paper we provide a very basic description of erasure codes, describe an implementation of a simple but very flexible erasure code to be used in network protocols, and discuss its performance and possible applications. Our code is based on Vandermonde matrices computed over GF(pr), can be implemented very efficiently on common microprocessors, and is suited to a number of different applications, which are briefly discussed in the paper. An implementation of the erasure code shown in this paper is available from the author, and is able to encode/decode data at speeds up to several MB/s running on a Pentium 133. Keywords: Reliable multicast, FEC, erasure codes. 1 Introduction Computer communications generally require reliable 1 data transfers among the communicating parties. This is usually achieved by implementing reliability at different levels in the protocol stack, either on a link-by-link basis (e.g. at the link layer), or using end-to-end protocols at the transport layer (such as TCP), or directly in the application. °The work described in this paper has been supported in part by the Commission of European Communities, Esprit Project LTR 20422 - "Moby Dick, The Mobile Digital Companion (MOBYDICK)", and in part by the Ministero dell'Universit£ e della Ricerca Scientifica e Tecnologica of Italy. 1Throughout this paper, with reliable we mean that data must be transferred with no errors and no losses. ACM SIGCOMM 24 Computer Communication ReviewARQ (Automatic Repeat reQuest) techniques are generally used in unicast protocols: miss- ing packets are retransmitted upon timeouts or explicit requests from the receiver. When the bandwidth-delay product approaches the sender's window, ARQ might result in reduced throughput. Also, in multicast communication protocols ARQ might be highly inefficient be- cause of uncorrelated losses at different (groups of) receivers. In these cases, Forward Error Correction (FEC) techniques, possibly combined with ARQ, become useful: the sender prevents losses by transmitting some amount of redundant informa- tion, which allow the reconstruction of missing data at the receiver without further interactions. Besides reducing the time needed to recover the missing packets, such an approach generally simplifies both the sender and the receiver since it might render a feedback channel unnecessary; also, the technique is attractive for multicast applications since different loss patterns can be recovered from using the same set of transmitted data. FEC techniques are generally based on the use of error detection and correction codes. These codes have been studied for a long time and are widely used in many fields of information process- ing, particularly in telecommunications systems. In the context of computer communications, error detection is generally provided by the lower protocol layers which use checksums (e.g. Cyclic Redundancy Checksums (CRCs)) to discard corrupted packets. Error correcting codes are also used in special cases, e.g. in modems, wireless or otherwise noisy links, in order to make the residual error rate comparable to that of dedicated, wired connections. After such link layer processing, the upper protocol layers have mainly to deal with erasures, i.e. missing packets in a stream. Erasures originate from uncorrectable errors at the link layer (but those are not frequent with properly designed and working hardware), or, more frequently, from congestion in the network which causes otherwise valid packets to be dropped due to lack of buffers. Erasures are easier to deal with than errors since the exact position of missing data is known. Recently, many applications have been developed which use multicast communication. Some of these applications, e.g. audio or videoconferencing tools, tolerate segment losses with a rel- atively graceful degradation of performance, since data blocks are often independent of each other and have a limited lifetime. Others, such as electronic whiteboards or diffusion of circular information over the network ("electronic newspapers", distribution of software, etc), have in- stead more strict requirements and require reliable delivery of all data. Thus, they would greatly benefit from an increased reliability in the communication. Despite an increased need, and a general consensus on their usefulness [4, 10, 14, 19] there are very few Internet protocols which use FEC techniques. This is possibly due to the existence of a gap between the telecommunications world, where FEC techniques have been first studied and developed, and the computer communications world. In the former, the interest is focused on error correcting codes, operating on relatively short strings of bits and implemented on dedicated hardware; in the latter, erasure codes are needed, which must be able to operate on packet-sized data objects, and need to be
View Full Document
Unlocking...