Resilient multicast using overlays

ABSTRACT

We introduce PRM (Probabilistic Resilient Multicast): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive component; in this paper we describe how PRM can be used to improve the performance of application-layer multicast protocols, especially when there are high packet losses and host failures. Further, using analytic techniques, we show that PRM can guarantee arbitrarily high data delivery ratios and low latency bounds. As a detailed case study, we show how PRM can be applied to the NICE application-layer multicast protocol. We present detailed simulations of the PRM-enhanced NICE protocol for 10,000 node Internet-like topologies. Simulations show that PRM achieves a high delivery ratio (> 97%) with a low latency bound (600 ms) for environments with high end-to-end network losses (1-5%) and high topology change rates (5 changes per second) while incurring very low overheads (< 5%).

REFERENCES

• 1: K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 19:357--367, 1967.
• 2: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 3: J. Byers, M. Luby, and M. Mitzenmacher. A digital fountain approach to asynchronous reliable multicast. IEEE Journal on Selected Areas in Communications, 20(8), Oct. 2002.
• 4: K. Calvert, E. Zegura, and S. Bhattacharjee. How to Model an Internetwork. In Proc. of Infocom, 1996.
• 5: M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. SCRIBE: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in communications, 20(8), Oct. 2002. To appear.
• 6: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 7: Sally Floyd , Van Jacobson , Ching-Gung Liu , Steven McCanne , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.784-803, Dec. 1997 [doi>10.1109/90.650139]
• 8: P. Francis. Yoid: Extending the Multicast Internet Architecture, 1999. White paper http://www.aciri.org/yoid/.
• 9: S. M. Hedetniemi, T. Hedetniemi, and A. L. Liestman. A Survey of Gossiping and Broadcasting in Communication Networks. NETWORKS, 18, 1988.
• 10: W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13--30, 1963.
• 11: 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
• 12: J. Leibeherr and M. Nahas. Application-layer Multicast with Delaunay Triangulations. In IEEE Globecom, Nov. 2001.
• 13: Brian Neil Levine , J.J. Garcia-Luna-Aceves, A comparison of reliable multicast protocols, Multimedia Systems, v.6 n.5, p.334-348, sept. 1998 [doi>10.1007/s005300050097]
• 14: Brian Neil Levine , David B. Lavo , J. J. Garcia-Luna-Aceves, The case for reliable concurrent multicasting using shared ACK trees, Proceedings of the fourth ACM international conference on Multimedia, p.365-376, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244237]
• 15: X. Li, S. Paul, P. Pancha, and M. Ammar. Layered video multicast with retransmissions (LVRM): Evaluation of error recovery schemes. In Proc. NOSSDAV, 1997.
• 16: 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
• 17: N. F. Maxemchuk. Dispersity routing. In Proc. ICC, pages 41.10--41.13, 1975.
• 18: Jörg 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 [doi>10.1109/90.720869]
• 19: C. Papadopoulos, G. Parulkar, and G. Varghese. An error control scheme for large-scale multicast applications. In Proc. Infocom, 1998.
• 20: S. Paul, K. Sabnani, J. Lin, and S. Bhattacharyya. Reliable multicast transport protocol (rmtp). IEEE Journal on Selected Areas in Communications, 15(3), Apr. 1997.
• 21: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 22: X. Rex Xu, A. Myers, H. Zhang, and R. Yavatkar. Resilient multicast support for continuous media applications. In Proceedings of NOSSDAV, 1997.
• 23: D. Rubenstein, S. Kasera, D. Towsley, and J. Kurose. Improving reliable multicast using active parity encoding services (APES). In Proc. Infocom, 1999.
• 24: D. Towsley, J. Kurose, and S. Pingali. A comparison of sender-initiated and receiver initiated reliable multicast protocols. IEEE Journal on Selected Areas on Communication, 15(3), Apr. 1997.
• 25: Z. Xiao and K. Birman. A randomized error recovery algorithm for reliable multicast. In Proc. Infocom, 2001.
• 26: 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]
• 27: B. Zhang, S. Jamin, and L. Zhang. Host multicast: A framework for delivering multicast to end users. In Proc. IEEE Infocom, June 2002.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
overlay multicast, randomized forwarding, resilience