Effective erasure codes for reliable computer communication protocols.
Reliable communication protocols require that all the intended recipients of a message receive 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 processing, 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.
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
This paper appears on ACM Computer Communication Review, Vol.27, n.2, Apr.97, pp.24-36.
y 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'a e della Ricerca Scientifica e Tecnologica of Italy.
1 Throughout this paper, with reliable we mean that data must be transferred with no errors and no losses.
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.
ARQ (Automatic Repeat reQuest) techniques are generally used in unicast protocols: missing
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 because
of uncorrelated losses at different (groups of) receivers.
In these cases, Forward Error Correction 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 relatively
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 instead
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 implemented efficiently in software using general-purpose
processors.
In this paper we try to fill this gap by providing a basic description of the principles of
operation of erasure codes, presenting an erasure code which is easy to understand, flexible and
efficient to implement even on inexpensive architectures, and discussing various issues related
to its performance and possible applications. The paper is structured as follows: Section 2
gives a brief introduction to the principles of operation of erasure codes. Section 3 describes
our code and discusses some issues related to its implementation on general purpose processors.
Finally, Section 4 briefly shows a number of possible applications in computer communication
protocols, both in unicast and multicast protocols. A portable C implementation of the erasure
code described in this paper is available from the author [16].
An introduction to erasure codes
In this section we give a brief introduction to the principle of operation of erasure codes. For a
more in-depth discussion of the problem the interested reader is referred to the copious literature
on the subject [1, 11, 15, 20]. In this paper we only deal with the so-called linear block codes as
they are simple and appropriate for the applications of our interest.
The key idea behind erasure codes is that k blocks of source data are encoded at the sender
to produce n blocks of encoded data, in such a way that any subset of k encoded blocks suffices
to reconstruct the source data. Such a code is called an (n; code and allows the receiver
to recover from up to n \Gamma k losses in a group of n encoded blocks. Figure 1 gives a graphical
representation of the encoding and decoding process.
Encoder
source data
Decoder
reconstructed
data
encoded data received data

Figure

1: A graphical representation of the encoding/decoding process.
Within the telecommunications world, a block is usually made of a small number of bits. In
computer communications, the "quantum" of information is generally much larger - one packet
of data, often amounting to hundreds or thousands of bits. This changes somewhat the way an
erasure code can be implemented. However, in the following discussion we will assume that a
block is a single data item which can be operated on with simple arithmetic operations. Large
packets can be split into multiple data items, and the encoding/decoding process is applied by
taking one data item per packet.
An interesting class of erasure codes is that of linear codes, so called because they can be
analyzed using the properties of linear algebra. Let be the source data, G an
n \Theta k matrix, then an (n; linear code can be represented by
for a proper definition of the matrix G. Assuming that k components of y are available at the
receiver, source data can be reconstructed by using the k equations corresponding to the known
components of y. We call G 0 the k \Theta k matrix representing these equations (Figure 2). This of
course is only possible if these equations are linearly independent, and, in the general case, this
holds if any k \Theta k matrix extracted from G is invertible.
If the encoded blocks include a verbatim copy of the source blocks, the code is called a
systematic code. This corresponds to including the identity matrix I k in G. The advantage of
a systematic code is that it simplifies the reconstruction of the source data in case one expects
very few losses.
G
n0Decoder
Encoder
G
Figure

2: The encoding/decoding process in matrix form, for a systematic code (the top k rows
of G constitute the identity matrix I k ). y 0 and G 0 correspond to the grey areas of the vector
and matrix on the right.
2.1 The generator matrix
G is called the generator matrix of the code, because any valid y is a linear combination of
columns of G. Since G is an n \Theta k matrix with rank k, any subset of k encoded blocks should
convey information on all the k source blocks. As a consequence, each column of G can have
at most k \Gamma 1 zero elements. In the case of a systematic code G contains the identity matrix
I k , which consumes all zero elements. Thus the remaining rows of the matrix must all contain
non-zero elements.
Strictly speaking, the reconstruction process needs some additional information - namely,
the identity of the various blocks - to reconstruct the source data. However, this information is
generally derived by other means and thus might not need to be transmitted explicitly. Also,
in the case of computer communications, this additional information has a negligible size when
compared to the size of a packet.
There is however another source of overhead which cannot be neglected, and this is the
precision used for computations. If each x i is represented using b bits, representing the y i 's
requires more bits if ordinary arithmetic is used. In fact, if each coefficient g ij of G is represented
on b 0 bits, the y i 's need b+b bits to be represented without loss of precision. That is a
significant overhead, since those excess bits must be transmitted to reconstruct the source data.
Rounding or truncating the representation of the y i 's would prevent a correct reconstruction of
the source data.
2.2 Avoiding roundings: computations in finite fields
Luckily the expansion of data can be overcome by working in a finite field. Roughly speaking,
a field is a set in which we can add, subtract, multiply and divide, in much the same way we
are used to work on integers (the interested reader is referred to some textbook on algebra [6]
or coding theory (e.g. [1, Ch.2 and Ch.4]), where a more formal presentation of finite fields is
provided; a relatively simple-to-follow presentation is also given in [2, Chap.2]). A field is closed
under addition and multiplication, which means that the result of sums and products of field
elements are still field elements. A finite field is characterized by having a finite number of
elements. Most of the properties of linear algebra apply to finite fields as well.
The main advantage of using a finite field, for our purposes, lies in the closure property
which allows us to make exact computations on field elements without requiring more bits to
represent the results. In order to work on a finite field, we need to map our data elements into
field elements, operate upon them according to the rules of the field, and then apply the inverse
mapping to reconstruct the desired results.
2.2.1 Prime fields
Finite fields have been shown to exist with is a prime number. Fields
with p elements, with p prime, are called prime fields or GF (p), where GF stands for Galois
Field. Operating in a prime field is relatively simple, since GF (p) is the set of integers from 0 to
under the operations of addition and multiplication modulo p. From the point of view of
a software implementation, there are two minor difficulties in using a prime field: first, with the
exception of bits to be represented. This causes a
slight inefficiency in the encoding of data, and possibly an even larger inefficiency in operating
on these numbers since the operand sizes might not match the word size of the processor. The
second problem lies in the need of a modulo operation on sums and, especially, multiplications.
The modulo is an expensive operation since it requires a division. Both problems, though, can
be minimized if
2.2.2 Extension fields
Fields with prime and r ? 1, are called extension fields or GF (p r ).
The sum and product in extension fields are not done by taking results modulo q. Rather, field
elements can be considered as polynomials of degree r \Gamma 1 with coefficients in GF (p). The sum
operation is just the sum between coefficients, modulo p; the product is the product between
polynomials, computed modulo an irreducible polynomial (i.e. one without divisors in GF (p r
of degree r, and with coefficients reduced modulo p.
Despite the apparent complexity, operations on extension fields can become extremely simple
in the case of 2. In this case, elements of GF(2 r ) require exactly r bits to be represented, a
property which simplifies the handling of data. Sum and subtraction become the same operation
(a bit-by-bit sum modulo 2), which is simply implemented with an exclusive OR.
2.2.3 Multiplications and divisions
An interesting property of prime or extension fields is that there exist at least one special
element, usually denoted by ff, whose powers generate all non-zero elements of the field. As an
example, a generator for GF (5) is 2, whose powers (starting from 2 0 ) are
of ff repeat with a period of length
This property has a direct consequence on the implementation of multiplication and division.
In fact, we can express any non-zero field element x as can be considered as
"logarithm" of x, and multiplication and division can be computed using logarithms, as follows:
where jaj b stands for "a modulo b". If the number of field elements not too large, tables can be
built off line to provide the "logarithm", the "exponential" and the multiplicative inverse of each
non-zero field element. In some cases, it can be convenient to provide a table for multiplications
as well. Using the above techniques, operations in extension fields with can be extremely
fast and simple to implement.
2.3 Data recovery
Recovery of original data is possible by solving the linear system
where x is the source data and y 0 is a subset of k components of y available at the receiver.
Matrix G 0 is the subset of rows from G corresponding to the components of y 0 .
It is useful to solve the problem in two steps: first G 0 is inverted, then
This is because the cost of matrix inversion can be amortized over all the elements which are
contained in a packet, becoming negligible in many cases.
The inversion of G 0 can be done with the usual techniques, by replacing division with multiplication
by the inverse field element. The cost of inversion is O(kl 2 ), where l -
is the number of data blocks which must be recovered (very small constants are involved in our
use of the O() notation).
Reconstructing the l missing data blocks has a total cost of O(lk) operations. Provided
sufficient resources, it is not impossible to reconstruct the missing data in constant time, although
this would be pointless since just receiving the data requires O(k) time. Many implementations
of error correcting codes use dedicated hardware (either hardwired, or in the form of a dedicated
processor) to perform data reconstruction with the required speed.
3 An erasure code based on Vandermonde matrices
A simple yet effective way to build the generator matrix, G, consists in using coefficients of the
where the x i 's are elements of GF (p r ). Such matrices are commonly known as Vandermonde
matrices, and their determinant is
Y
If all x i 's are different, the matrix has a non-null determinant and it is invertible. Provided
can be constructed, which satisfy the properties required
for G. Such matrices can be extended with the identity matrix I k to obtain a suitable generator
for a systematic code.
Note that there are some special cases of the above code which are of trivial implementation.
As an example, an (n; 1) code simply requires the same data to be retransmitted multiple times,
hence there is no overhead involved in the encoding. Another simple case is that of a systematic
code, where the only redundant block is simply the sum (as defined in GF (p r )) of
the k source data blocks, i.e. a simple XOR in case 2. Unfortunately, an (n; 1) code has a
low rate and is relatively inefficient compared to codes with higher values of k. Conversely, a
code is only useful for small amount of losses. So, in many cases there is a real need
for codes with k ? 1 and
We have written a portable C implementation of the above code [16] to determine its performance
when used within network protocols. Our code supports any r in the range
arbitrary packet sizes. The maximum efficiency can be achieved using
this allows most operations to be executed using table lookups. The generator matrix has the
form indicated above, with x . We can build up to 2 rows in this way, which makes
it possible to construct codes up to In our experiments we have used
a packet size of 1024 bytes.
3.1 Performance
Using a systematic code, the encoder takes groups of k source data blocks to produce
redundant blocks. This means that every source data block is used times, and we can
expect the encoding time to be a linear function of n \Gamma k. It is probably more practical to
measure the time to produce a single data block, which depends on the single parameter k. It
is easy to derive that this time is (for sufficiently large packets) linearly dependent on k, hence
we can approximate it as
encoding
c e
where the constant c e depends on the speed of the system. The above relation only tells us how
fast we can build redundant packets. If we use a systematic code, sending k blocks of source
data requires the actual computation of blocks. Thus, the actual encoding
speed becomes
encoding speed = c e
Note that the maximum loss rate that we can sustain is n\Gammak
n , which means that, for a given
maximum loss rate, the encoding speed also decreases with n.
Decoding costs depend on l - min(k; n \Gamma k), the actual number of missing source blocks.
Although matrix inversion has a cost O(kl 2 ), this cost is amortized over the size s of a packet;
we have found that, for reasonably sized packets (say above 256 bytes), and k up to 32, the cost
of matrix inversion becomes negligible compared to the cost of packet reconstruction, which is
O(lk). Also for the reconstruction process it is more practical to measure the overall cost per
reconstructed block, which is similar to the encoding cost. Then, the decoding speed can be
written as
decoding speed = c d
l
with the constant c d slightly smaller than c e because of some additional overheads (including
the already mentioned matrix inversion).
The accuracy of the above approximations has been tested on our implementation using
a packet size of 1024 bytes, and different values of k and l shown in Table 1
(more detailed performance data can be found in [17]). Running times have been determined
using a Pentium 133 running FreeBSD, using our code compiled with gcc -O2 and no special
optimizations.
These experimental results show that the approximation is sufficiently accurate. Also, the
values of c e and c d are sufficiently high to allow these codes to be used in a wide range of
applications, depending on the actual values of k and l k. The reader will notice that, for
a given k, larger values of l (which we have set equal to n \Gamma slightly better performance
both in encoding and decoding. On the encoder side this is exclusively due to the effect of
caching: since the same source data are used several times to compute multiple redundant blocks,
successive computations find the operands already in cache hence running slightly faster. For
the decoder, this derives from the amortization of matrix inversion costs over a larger number
Encoding Decoding
-s MB/s -s MB/s
28 3533 9.06

Table

1: Encoding/decoding times for different values of k and n \Gamma k on a Pentium 133 running
FreeBSD
of reconstructed blocks 2 .
Note that in many cases data exchanged over a network connection are already subject
to a small number of copies (e.g. from kernel to user space) and accesses to compute check-
sums. Thus, part of the overhead for reconstructing missing data might be amortized by using
integrated layer processing techniques [3].
3.2 Discussion
The above results show that a software implementation of erasure codes is computationally
expensive, but on today's machines they can be safely afforded with little overhead for low-to-
medium speed applications, up to the 100 KB/s range. This covers a wide range of real-time
applications including network whiteboards and audio/video conferencing tools, and can even
be used to support browsing-type applications. More bandwidth-intensive applications can still
make good use of software FEC techniques, with a careful tuning of operating parameters
(specifically, our discussion) or provided sufficient processing power is available. The
current trend of increasing processing speeds, and the availability of Symmetric MultiProcessor
(SMP) desktop computers suggest that, as time goes by, there will likely be plenty of processing
power to support these computations (we have measured values for c d and c e in the 30MB/s
range on faster machines based on PentiumPRO 200 and UltraSparc processors). Finally, note
that in many cases both encoding and decoding can be done offline, so many non-real-time
application can use this feature and apply FEC techniques while communicating at much higher
speeds than their encoding/decoding ability.
2 and a small overhead existing in our implementation for non reconstructed blocks which are still copied in
the reconstruction process
Applications
Depending on the application, ARQ and FEC can be used separately or together, and in the
latter case either on different layers or in a combined fashion. In general, there is a tradeoff
between the improved reliability of FEC-based protocols and their higher computational costs,
and this tradeoff often dictates the choice.
It is beyond the scope of this paper to make an in-depth analysis of the relative advantages
of FEC, ARQ or combinations thereof. Such studies are present in some papers in the literature
(see, for example, [7, 12, 21]). In this section we limit our interest to computer networks, and
present a partial list of applications which could benefit from the use of an encoding technique
such as the one described in this paper. The bandwidth, reliability and congestion control
requirements of these applications vary widely.
Losses in computer networks mainly depend on congestion, and congestion is the network
analogue of noise (or interference) in telecommunications systems. Hence, FEC techniques based
on a redundant encoding give us similar types of advantages, namely increased resilience to noise
and interference. Depending on the amount of redundancy, the residual packet loss rate can be
made arbitrarily small, to the point that reliable transfers can be achieved without the need for
a feedback channel. Or, one might just be interested in a reduction of the residual loss rate, so
that performance is generally improved but feedback from the receiver is still needed.
4.1 Unicast applications
In unicast applications, reducing the amount of feedback necessary for reliable delivery is generally
useful to overcome the high delays incurred with ARQ techniques in the presence of long
delay paths. Also, these techniques can be used in the presence of asymmetrical communication
links. Two examples are the following:
ffl forward error recovery on long delay paths. TCP communications over long fat pipes
suffer badly from random packet losses because of the time needed to get feedback from
the receiver. Selective acknowledgements [13] can help improve the situation but only
after the transmit window has opened wide enough, which is generally not true during
connection startup and/or after an even short sequence of lost packets. To overcome this
problem it might be useful to allocate (possibly adaptively, depending on the actual loss
rate) a small fraction of the bandwidth to send redundant packets. The sender could
compute a small number (1-2) of redundant packets on every group of k packets, and
send these packets at the end of the group. In case of a single or double packet loss the
receiver could defer the transmission of the dup ack until the expiration of a (possibly
fast) timeout 3 . If, by that time, the group is complete and some of the redundant packets
are available, then the missing one(s) can be recovered without the need for an explicit
retransmission (this this would be equivalent to a fast retransmit). Otherwise, the usual
congestion avoidance techniques can be adopted. A variant of RFC1323 timestamps[5]
3 alternatively, the sender could delay retransmissions in the hope that the lost packet can be recovered using
the redundant packets.
can be used to assign sequence numbers to packets thus allowing the receiver to determine
the identity of received packets and perform the reconstruction process (TCP sequence
numbers are not adequate for the purpose).
ffl power saving in communication with mobile equipment Mobile devices usually
adopt wireless communication and have a limited power budget. This results in the need
to reduce the number of transmissions. A redundant encoding of data can practically
remove the need for acknowledgements while still allowing for reliable communications. As
an example, a mobile browser can limit its transmissions to requests only, while incoming
responses need not to be explicitly ACKed (such as it is done currently with HTTP over
TCP) unless severe losses occur.
4.2 Multicast applications
The main field of application of redundant encoding is probably in multicast applications. Here,
multiple receivers can experience losses on different packets, and insuring reliability via individual
repairs might become extremely expensive. A second advantage derives from the aforementioned
reduced need for handling a feedback channel from receivers. Reducing the amount of feedback
is an extremely useful feature since it allows protocols to scale well to large numbers of receivers.
Applications not depending on a reliable delivery can still benefit from a redundant en-
coding, because an improved reliability in the transmission allows for more aggressive coding
techniques (e.g. compression) which in turn might result in a more effective usage of the available
bandwidth.
A list of multicast applications which would benefit from the use of a redundant encoding
follows.
videoconferencing tools. A redundant encoding with small values of k and
can provide an effective protection against losses in videoconferencing applications. By
reducing the effective loss rate one can even use a more efficient encoding technique (e.g.
fewer "I" frames in MPEG video) which provide a further reduction in the bandwidth.
The PET [9] group at Berkeley has done something similar for MPEG video.
reliable multicast for groupware. A redundant encoding can be used to greatly reduce
the need for retransmissions ("repairs") in applications needing a reliable multicast. One
such example is given by the "network whiteboard" type of applications, where reliable
transfer is needed for objects such as Postscript files or compound drawings.
ffl one-to-many file transfer on LANs. Classrooms using workstations often use this
pattern of access to files, either in the booting process (all nodes download the kernel or
startup files from a server) or during classes (where students download almost simultaneously
the same documents or applications from a centralized server). While these problems
can be partly overcome by preloading the software, centralized management is much more
convenient and the use of a multicast-FTP type of application can make the system much
more scalable.
ffl one-to-many file transfer on Wide Area Networks. There are several examples
of such an application. Some popular Web servers are likely to have many simultaneous
transfers of the same, large, piece of information (e.g. popular software packages). The
same applies to, say, a newspaper which is distributed electronically over the network, or
video-on-demand type of applications. Unlike local area multicast-FTP, receivers connect
to the server at different times, and have different bandwidths and loss rates, and significant
congestion control issues exist [8]. By using the encoding presented here, source data can be
encoded and transmitted with a very large redundancy (n ?? k). Using such a technique,
a receiver basically needs only to collect a sufficient number (k) of packets per block to
reconstruct the original file. The RMDP protocol [18] has been designed and implemented
by the author using the above technique.

Acknowledgements

The author wishes to thank Phil Karn for discussions which led to the development of the code
described in this paper, and an anonymous referee for comments on an early version of this
paper.



--R

"Theory and Practice of Error Control Codes"
"Fast Algorithms for Digital Signal Processing"
"Architectural Considerations for a New Generation of Proto- cols"
"The Case for packet level FEC"
"RFC1323: TCP Extensions for High Performance"
"Algebra"
"Delay Bounded Type-II Hybrid ARQ for Video Transmission over Wireless Networks"
"Receiver-driven Layered Multicast"
"Priority Encoding Transmission"
"Reliable Broadband Communication Using A Burst Erasure Correcting Code"
"Error Control Coding: Fundamentals and Applications"
"Automatic-repeat-request error-control schemes"
"RFC2018: TCP Selective Acknowledgement Option"
"Reliable Multicast: Where to use Forward
"Introduction to Error-Correcting Codes"
Sources for an erasure code based on Vandermonde matrices.
"On the feasibility of software FEC"
"A Reliable Multicast data Distribution Protocol based on software FEC techniques"
"Packet recovery in high-speed networks using coding and buffer management"
"Introduction to Coding Theory"
"A modified selective-repeat type-II hybrid ARQ system and its performance analysis"
--TR

--CTR
Antonio Vilei , Gabriella Convertino , Silvio Oliva , Roberto Cuppone, A novel unbalanced multiple description scheme for video transmission over WLAN, Proceedings of the 3rd ACM international workshop on Wireless mobile applications and services on WLAN hotspots, September 02-02, 2005, Cologne, Germany
Philip K. McKinley , Suraj Gaurav, Experimental evaluation of forward error correction on multicast audio streams in wireless LANs, Proceedings of the eighth ACM international conference on Multimedia, p.416-418, October 2000, Marina del Rey, California, United States
Temporally enhanced erasure codes for reliable communication protocols, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.6, p.713-730, 22 April 2002
Yoav Nebat , Moshe Sidi, Parallel downloads for streaming applications: a resequencing analysis, Performance Evaluation, v.63 n.1, p.15-35, January 2006
Azzedine Boukerche , Dawei Ning , Regina B. Araujo, UARTP: a unicast--based self--adaptive reliable transmission protocol for wireless and mobile ad-hoc networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada
Philip K. McKinley , Chiping Tang , Arun P. Mani, A Study of Adaptive Forward Error Correction for Wireless Collaborative Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.936-947, September 2002
Colin Allison , Duncan McPherson , Dirk Husemann, New channels, old concerns: scalable and reliable data dissemination, Proceedings of the 9th workshop on ACM SIGOPS European workshop: beyond the PC: new challenges for the operating system, September 17-20, 2000, Kolding, Denmark
Scott Atchley , Stephen Soltesz , James S. Plank , Micah Beck, Video IBPster, Future Generation Computer Systems, v.19 n.6, p.861-870, August
Longshe Huo , Wen Gao , Qingming Huang, Robust real-time transmission of scalable multimedia for heterogeneous client bandwidths, Real-Time Imaging, v.11 n.4, p.300-309, August 2005
Jrg Nonnenmacher , Ernst Biersack , Don Towsley, Parity-based loss recovery for reliable multicast transmission, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.289-300, Oct. 1997
Jrg Nonnenmacher , Ernst W. Biersack , Don Towsley, Parity-based loss recovery for reliable multicast transmission, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.349-361, Aug. 1998
Roger G. Kermode, Scoped hybrid automatic repeat reQuest with forward error correction (SHARQFEC), ACM SIGCOMM Computer Communication Review, v.28 n.4, p.278-289, Oct. 1998
Mikkel Thorup , Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Patrick G. Bridges , Gary T. Wong , Matti Hiltunen , Richard D. Schlichting , Matthew J. Barrick, A configurable and extensible transport protocol, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1254-1265, December 2007
Jess Bisbal , Betty H. C. Cheng, Resource-based approach to feature interaction in adaptive software, Proceedings of the 1st ACM SIGSOFT workshop on Self-managed systems, p.23-27, October 31-November 01, 2004, Newport Beach, California
Pl Halvorsen , Thomas Plagemann , Vera Goebel, Improving the I/O performance of intermediate multimedia storage nodes, Multimedia Systems, v.9 n.1, p.56-67, July
Micah Adler, Trade-offs in probabilistic packet marking for IP traceback, Journal of the ACM (JACM), v.52 n.2, p.217-244, March 2005
X. Brian Zhang , Simon S. Lam , Dong-Young Lee, Group rekeying with limited unicast recovery, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.6, p.855-870, 22 April 2004
Micah Adler, Tradeoffs in probabilistic packet marking for IP traceback, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Yang Richard Yang , X. Steve Li , X. Brian Zhang , Simon S. Lam, Reliable group rekeying: a performance analysis, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.27-38, October 2001
Luigi Rizzo , Lorenzo Vicisano, RMDP: an FEC-based reliable multicast protocol for wireless environments, ACM SIGMOBILE Mobile Computing and Communications Review, v.2 n.2, p.23-31, April 1998
Luigi Rizzo, Dummynet and forward error correction, Proceedings of the Annual Technical Conference on USENIX Annual Technical Conference, 1998, p.31-31, June 15-19, 1998, New Orleans, Louisiana
Christoph Neumann , Vincent Roca , Aurlien Francillon , David Furodet, Impacts of packet scheduling and packet loss distribution on FEC Performances: observations and recommendations, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France
Shang-Ming Chang , Shiuhpyng Shieh , Warren W. Lin , Chih-Ming Hsieh, An efficient broadcast authentication scheme in wireless sensor networks, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
Trista Pei-chun Chen , Tsuhan Chen, Fine-grained rate shaping for video streaming over wireless networks, EURASIP Journal on Applied Signal Processing, v.2004 n.1, p.176-191, 1 January 2004
Sinan Isik , Mehmet Yunus Donmez , Cem Ersoy, Itinerant delivery of popular data via WIDE hot spots, Mobile Networks and Applications, v.11 n.2, p.297-307, April 2006
Niklas Carlsson , Derek L. Eager , Mary K. Vernon, Multicast protocols for scalable on-demand download, Performance Evaluation, v.63 n.9, p.864-891, October 2006
Vincent Roca, On the use of on-demand layer addition (ODL) with mutli-layer multicast transmission techniques, Proceedings of NGC 2000 on Networked group communication, p.93-101, November 08-10, 2000, Palo Alto, California, United States
Martin S. Lacher , Jrg Nonnenmacher , Ernst W. Biersack, Performance comparison of centralized versus distributed error recovery for reliable multicast, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.224-238, April 2000
X. Brian Zhang , Simon S. Lam , Dong-Young Lee , Y. Richard Yang, Protocol design for scalable and reliable group rekeying, IEEE/ACM Transactions on Networking (TON), v.11 n.6, p.908-922, 01 December
Jeong-Yong Choi , Jitae Shin, Cross-layer error-control with low-overhead ARQ for H.264 video transmission over wireless LANs, Computer Communications, v.30 n.7, p.1476-1486, May, 2007
Luigi Rizzo, pgmcc: a TCP-friendly single-rate multicast congestion control scheme, ACM SIGCOMM Computer Communication Review, v.30 n.4, p.17-28, October 2000
V. R. Syrotiuk , M. Cui , S. Ramkumar , C. J. Colbourn, Dynamic spectrum utilization in ad hoc networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.665-678, 5 December 2004
David Gotz, Scalable and adaptive streaming for non-linear media, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
John W. Byers , Gu-In Kwon , Michael Luby , Michael Mitzenmacher, Fine-grained layered multicast with STAIR, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.81-93, February 2006
Hagit Attiya , Hadas Shachnai, Tight bounds for FEC-based reliable multicast, Information and Computation, v.190 n.2, p.117-135, 1 May 2004
Chadi Barakat , Eitan Altman, Bandwidth tradeoff between TCP and link-level FEC, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.39 n.2, p.133-150, 5 June 2002
Chadi Barakat , Eitan Altman, Bandwidth tradeoff between TCP and link-level FEC, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.39 n.5, p.133-150, 5 June 2002
Amos Beimel , Shlomi Dolev , Noam Singer, RT oblivious erasure correcting, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1321-1332, December 2007
Petros Zerfos , Gary Zhong , Jerry Cheng , Haiyun Luo , Songwu Lu , Jefferey Jia-Ru Li, DIRAC: a software-based wireless router system, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
F. A. Samimi , P. K. McKinley , S. M. Sadjadi , P. Ge, Kernel-middleware interaction to support adaptation in pervasive computing environments, Proceedings of the 2nd workshop on Middleware for pervasive and ad-hoc computing, p.140-145, October 18-22, 2004, Toronto, Ontario, Canada
John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.56-67, Oct. 1998
Haitao Zheng , Jill Boyce, Streaming video over wireless networks, Wireless internet handbook: technologies, standards, and application, CRC Press, Inc., Boca Raton, FL,
Combined wavelet video coding and error control for internet streaming and multicast, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.66-80, January
Jen-Wen Ding , Sheng-Yuan Tseng , Yueh-Min Huang, Packet Permutation: A Robust Transmission Technique for Continuous Media Streaming Over the Internet, Multimedia Tools and Applications, v.21 n.3, p.281-305, December
Christoph Neumann , Vincent Roca , Rod Walsh, Large scale content distribution protocols, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005
Dan Rubenstein , Sneha Kasera , Don Towsley , Jim Kurose, Improving reliable multicast using active parity encoding services, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.1, p.63-78, 15 January 2004
Anirban Mahanti , Derek L. Eager , Mary K. Vernon , David Sundaram-Stukel, Scalable on-demand media streaming with packet loss recovery, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.97-108, October 2001
Shengjie Zhao , Zixiang Xiong , Xiaodong Wang, Optimal Resource Allocation for Wireless Video over CDMA Networks, IEEE Transactions on Mobile Computing, v.4 n.1, p.56-67, January 2005
Anirban Mahanti , Derek L. Eager , Mary K. Vernon , David J. Sundaram-Stukel, Scalable on-demand media streaming with packet loss recovery, IEEE/ACM Transactions on Networking (TON), v.11 n.2, p.195-209, April
Rajesh Krishnan , James P. G. Sterbenz , Wesley M. Eddy , Craig Partridge , Mark Allman, Explicit transport error notification (ETEN) for error-prone wireless and satellite networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.3, p.343-362, 22 October 2004
Patrick McDaniel , Atul Prakash, Enforcing provisioning and authorization policy in the Antigone system, Journal of Computer Security, v.14 n.6, p.483-511, November 2006
Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin, SafeStore: a durable and practical storage system, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
B. Baurens, Groupware, Cooperative environments for distributed: the distributed systems environment report, Springer-Verlag New York, Inc., New York, NY, 2002
FEC;reliable multicast;erasure codes