Scoped hybrid automatic repeat reQuest with forward error correction (SHARQFEC)

ABSTRACT

Reliable multicast protocols scale only as well as their ability to localize traffic. This is true for repair requests, repairs, and the session traffic that enables receivers to suppress extraneous requests and repairs. We propose a new reliable multicast traffic localization technique called Scoped Hybrid Automatic Repeat reQuest with Forward Error Correction (SHARQFEC). SHARQFEC operates in an end-to-end fashion and localizes traffic using a hierarchy of administratively scoped regions. Session traffic is further reduced through the use of a novel method for indirectly determining the distances between session members. For large sessions, this mechanism reduces the amount of session traffic by several orders of magnitude over non-scoped protocols such as Scalable Reliable Multicast (SRM). Forward Error Correction is selectively added to regions which are experiencing greater loss, thereby reducing the volume of repair traffic and recovery times. Receivers request additional repairs as necessary. Simulations show that SHARQFEC out performs both SRM and non-scoped hybrid Automatic Repeat reQuest / Forward Error Correction protocols. Assuming the widespread deployment of administrative scoping, SHARQFEC could conceivably provide scalable reliable delivery to tens of millions of receivers without huge increases in network bandwidth.

REFERENCES

• 1: T. J. Berners-Lee , R. Cailliau , J.-F. Groff, The world-wide web, Computer Networks and ISDN Systems, v.25 n.4-5, p.454-459, Nov. 1992
• 2: Deering, S., and Hinden, R., "Internet Protocol, Version 6, Specification", RFC 1883, Xerox PARC, Ipsilon Networks, December 1995.
• 3: Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 4: Gemmell, J., "Scalable Reliable Multicast Using Erasure- Correcting Re-Sends," Microsoft Research Technical Report, MSR-TR-97-20, June 30, 1997.
• 5: Handley, M., "On Scalable Multimedia Conferencing Systems'', Ph.D. Thesis, University of London, 1997.
• 6: Hugh W. Holbrook , Sandeep K. Singhal , David R. Cheriton, Log-based receiver-reliable multicast for distributed interactive simulation, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.328-341, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 7: 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
• 8: ISO/IEC 138182-2 (MPEG-2), "Generic Coding of Moving Pictures and Associated Audio - Part 2, Video," International Standard, November 1994.
• 9: Roger George Kermode , Andrew B. Lippman, Smart network caches: localized content and application-negotiated recovery mechanisms for multicast media distribution, 1998
• 10: Jörg 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
• 11: Papadopoulos, C., Parulkar, G., and Varghese, G., "An Error Control Scheme for Large-Scale Multicast," submitted to Infocom 98.
• 12: Paul, S., Sabnani, K., Lin, J., and Bhattacharyya, S., "Reliable Multicast Transport Protocol (RMTP)", To appear IEEE Journal on Selected Areas in Communications, special issue on Network Support for Multipoint Communication.
• 13: Postel, J., "lnternet Protocol", RFC 791, September 1981.
• 14: 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]
• 15: Rizzo L., and Vicisano, L., "A Reliable Multicast data Distribution Protocol based on software FEC techniques," Proceedings of the Fourth IEEE, HPCS'97 Workshop, Chalkidiki, Greece, June 1997.
• 16: Rubenstein, D., Kurose, J., Towsley, D., "Real-Time Reliable Multicast Using Proactive Forward Error Correction," NOSS- DAV '98, Cambridge, UK, July 1998.
• 17: Schulzrinne, H., Casner, S., Frederick, R., and Jacobson, V., "RTP: A Transport Protocol for Real-Time Applications," RFC I889, January 1996.
• 18: UCB/LBNL/VINT Network Simulator, ns, URL: htLp://wwwmash.cs.berkelev, edu/ns
• 19: UCB/LBNL/VINT Network Animator, nam, URL: ht~ w ww- m as h. c s,berkeley, edu/nam
• 20: Yajnik, M., Kurose, J., and Towsley, D., "Packet Loss Correlation in the MBone multicast network," Proceedings of IEEE Global Internet Mini-Conf. GLOBECOM'96, Nov. 1996.
• 21: Rajendra Yavatkar , James Griffoen , Madhu Sudan, A reliable dissemination protocol for interactive collaborative applications, Proceedings of the third ACM international conference on Multimedia, p.333-344, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215288]

INDEX TERMS

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

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

General Terms:
Performance, Reliability

Keywords:
ARQ, FEC, administrative-scoping, hierarchy, multicast, reliable, scalable