RT oblivious erasure correcting

ABSTRACT

An erasure correcting scheme is rateless if it is designed to tolerate any pattern of packet loss and reveal the transmitted information after a certain number of packets is received. On the one hand, transmission schemes that use rateless erasure correcting schemes do not usually use a feedback channel. However, they may require significant amount of additional processing by both the sender and the receiver. On the other hand, automatic repeated request protocols use a feedback channel to assist the sender, and do not usually require information processing. In this work we present a combined approach, where a lean feedback channel is used to assist the sender to efficiently transmit the information. Our Real-Time oblivious approach minimizes the processing time and the memory requirements of the receiver and, therefore, fits a variety of receiving devices. In addition, the transmission is real-time where the expected number of original packets revealed when a packet is received is approximately the same throughout the entire transmission process. We use our end-to-end scheme as a base for broadcast (and multicast) schemes. An overlay tree structure is used to convey the information to a large number of receivers. Moreover, the receivers may download the information from a number of senders or even migrate from one sender to another.

REFERENCES

• 1: [1] The ATM Forum [Online]. Available: http://www.atmforum.com
• 2: [2] Gigabit Ethernet Alliance [Online]. Available: http://www.gigabit-ethernet.org
• 3: Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, NJ, 1985
• 4: [4] J. Blömer, M. Kalfane, M. Karpinski, R. Karp, M. G. Luby, and D. Zuckerman, "An XOR-based erasure-resilient coding scheme," ICSI, Tech. Rep. 95-048, 1995.
• 5: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258573]
• 6: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi, Analysis of random processes via And-Or tree evaluation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 25-27, 1998, San Francisco, California, United States
• 7: [7] J. W. Byers, M. G. Luby, and M. Mitzenmacher, "Accessing multiple mirror sites in parallel: Using Tornado codes to speed up downloads," in Proc. IEEE INFOCOM, 1999, pp. 275-283.
• 8: Shlomi Dolev , Boris Fitingof , Avraham Melkman , Olga Tubman, Smooth and adaptive forward erasure correcting, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.36 n.2-3, p.343-355, July 2001 [doi>10.1016/S1389-1286(01)00168-2]
• 9: [9] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. Spielman, "Efficient erasure correcting codes," IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 569-584, 2001.
• 10: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 11: [11] P. Maymounkov and D. Mazières, "Rateless codes and big downloads," presented at the 2nd Int. Workshop on Peer-to-Peer Systems (IPTPS03), Berkeley, CA, 2003.
• 12: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 13: [13] I. S. Reed and G. Solomon, "Polynomial codes over certain finite fields," J. SIAM, vol. 8, pp. 300-304, 1960.
• 14: Amin Shokrollahi, Raptor codes, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2551-2567, June 2006 [doi>10.1109/TIT.2006.874390]
• 15: [15] P. Maymounkov, "Online codes," NYU, Tech. Rep. TR2002-833, 2002.
• 16: [16] D. S. Lun, M. Medard, and M. Effros, "On coding for reliable communication over packet networks," in Proc. 42nd Annu. Allerton Conf. Communication, Control and Computing, 2004.
• 17: [17] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, 2000.
• 18: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 19: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 20: Luigi Rizzo, Effective erasure codes for reliable computer communication protocols, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.24-36, Apr. 1997 [doi>10.1145/263876.263881]
• 21: [21] L. Rizzo and L. Vicisano, "A reliable multicast data distribution protocol based on software FEC techniques," in 4th IEEE Workshop Architecture and Implementation of High Performance Communication Systems (HPCS'97), Sani Beach, Chalkidiki, Greece, Jun. 1997.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design

Keywords:
ARQ, combinatorics, data-link, information theory, stochastic processes, transport layer