Loss-resilient on-demand media streaming using priority encoding

ABSTRACT

A novel solution to the reliable multicast problem is the "digital fountain" approach, in which data is encoded with an erasure protection code before transmission, and receivers can recover the original data after receiving enough distinct encoded data. This solution, however, is not desirable for streaming media schemes in which it is preferable for parts of a movie to be available for consumption before the entire movie is received. Earlier work has proposed the use of Unequal Error Protection (UEP) codes, which permit some parts of the movie to be recovered before others. Unfortunately, a straightforward implementation of this solution can incur prohibitive coding complexity.

We outline an on-demand media streaming scheme involving a combination of segmentation and rateless encoding. Our solution reduces the coding complexity to feasible levels, while guaranteeing the least bandwidth consumption for a given playout delay and number of segments. We propose an efficient algorithm to find the optimal segmentation for single-layered and multi-layered transmissions, and analyze its performance under network packet loss. Through analysis, numerical examples, and simulations, we demonstrate the feasibility and performance of the proposed scheme.

REFERENCES

• 1: A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan. Priority Encoded Transmission. In Proceedings of IEEE FOCS 1994, pages 604--612, 1994.
• 2: 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
• 3: C. Huang and L. Xu. Efficient FEC Codes for Data Loss Recovery. Techni-cal report, Washington University in St. Louis, June 2004. Available at http://www.nisl.wustl.edu.
• 4: Lars Engebretsen , Madhu Sudan, Harmonic broadcasting is optimal, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.431-432, January 06-08, 2002, San Francisco, California
• 5: A. Hu. Video-on-Demand Broadcasting Protocols: a Comprehensive Study. In Proceedings of IEEE INFOCOM 2001, pages 508--517, 2001.
• 6: J.-C. Bolot, S. Fosse-Parisis, and D. Towdley. Adaptive FEC-Based Error Control for Internet Telephony. In Proceedings of IEEE INFOCOM 1999, 1999.
• 7: J. G. Apostolopoulos. Reliable Video Communication Over Lossy Packet Networks Using Multiple State Encoding and Path Diversity. In Proceedings of MMCN 2002, 2002.
• 8: R. Janakiraman and L. Xu. Layered Priority-encoded Transmission for Video Streaming to Heterogeneous Clients. In Proceedings of IEEE ISIT 2004, July 2004.
• 9: Min Dai , Dmitri Loguinov, Analysis of rate-distortion functions and congestion control in scalable internet video streaming, Proceedings of the 13th international workshop on Network and operating systems support for digital audio and video, June 01-03, 2003, Monterey, CA, USA [doi>10.1145/776322.776333]
• 10: Anirban Mahanti , Derek L. Eager , Mary K. Vernon , David Sundaram-Stukel, Scalable on-demand media streaming with packet loss recovery, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.97-108, August 2001, San Diego, California, United States
• 11: Nuggehally S. Jayant , P. Noll, Digital Coding of Waveforms: Principles and Applications to Speech and Video, Prentice Hall Professional Technical Reference, 1990
• 12: A Low Bandwidth Broadcasting Protocol for Video on Demand, Proceedings of the International Conference on Computer Communications and Networks, p.690, October 12-15, 1998
• 13: V. Pless. Introduction to the Theory of Error-Correcting Codes. Wiley-Interscience, 1998.
• 14: M. A. Shokrollahi. Raptor codes. In Proceedings of IEEE ISIT 2004, July 2004.
• 15: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 16: L. Xu. Resource-Efficient Delivery of On-Demand Streaming Data Using UEP Codes. IEEE Transactions on Communications, 51(1):63--71, Jan. 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Design, Theory

Keywords:
fountain codes, loss resilience, multicast, priority encoding transmission, video-on-demand