Effective erasure codes for reliable computer communication protocols

ABSTRACT

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(p^r), 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.

REFERENCES

• 1: [1] R. E. Blahut, "Theory and Practice of Error Control Codes" Addison Wesley, MA, 1984.
• 2: Richard E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 3: D. D. Clark , D. L. Tennenhouse, Architectural considerations for a new generation of protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.200-208, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 4: Christian Huitema, The case for packet level FEC, Proceedings of the TC6 WG6.1/6.4 Fifth International Workshop on Protocols for High-Speed Networks V, p.109-120, October 28-30, 1996
• 5: V. Jacobson , R. Braden , D. Borman, TCP Extensions for High Performance, RFC Editor, 1992
• 6: [6] S. Lang, "Algebra", Addison-Wesley, 1984.
• 7: [7] H. Liu, M. El Zarki, "Delay Bounded Type-II Hybrid ARQ for Video Transmission over Wireless Networks", Proc. Conference on Information Sciences and Systems, Princeton, NJ, March 1996.
• 8: Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.117-130, August 28-30, 1996, Palo Alto, California, United States
• 9: [9] A. Albanese, J. Bloemer, J. Edmonds, M. Luby, M. Sudan, "Priority Encoding Transmission", 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Science Press, 1994.
• 10: A. J. McAuley, Reliable broadband communication using a burst erasure correcting code, Proceedings of the ACM symposium on Communications architectures & protocols, p.297-306, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 11: [11] S. Lin, D. J. Costello, "Error Control Coding: Fundamentals and Applications", Prentice Hall, 1983.
• 12: [12] S. Lin, D. J. Costello, M. Miller, "Automatic-repeat-request error-control schemes", IEEE Comm. Magazine, v. 22, n. 12, pp. 5-17, Dec. 1984.
• 13: M. Mathis , J. Mahdavi , S. Floyd , A. Romanow, TCP Selective Acknowledgement Options, RFC Editor, 1996
• 14: Jörg Nonnenmacher , Ernst Biersack, Reliable multicast: where to use FEX, Proceedings of the TC6 WG6.1/6.4 Fifth International Workshop on Protocols for High-Speed Networks V, p.134-148, October 28-30, 1996
• 15: [15] V. Pless, "Introduction to Error-Correcting Codes", 2nd ed., Wiley, 1989.
• 16: [16] L. Rizzo, Sources for an erasure code based on Vandermonde matrices. Available at http://www.iet.unipi.it/~luigi/vdm.tgz
• 17: [17] L. Rizzo, "On the feasibility of software FEC", DEIT Technical Report LR-970131. Available as http://www.iet.unipi.it/~luigi/softfec.ps
• 18: [18] L. Rizzo, L. Vicisano, "A Reliable Multicast data Distribution Protocol based on software FEC techniques", DEIT Technical Report LR-970116. Available as http://www.iet.unipi.it/~luigi/rmdp.ps
• 19: [19] N. Shacham, P. McKenney, "Packet recovery in high-speed networks using coding and buffer management", Proc. IEEE Infocom'90, San Francisco, CA, pp. 124-131, May 1990.
• 20: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 21: [21] Y. Wang, S. Lin, "A modified selective-repeat type-II hybrid ARQ system and its performance analysis", IEEE Trans. Comm. v.COM-31, n. 5, pp. 593-608, May 1983.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  E. Data

General Terms:
Design, Theory

Keywords:
FEC, erasure codes, reliable multicast