A case for end system multicast (keynote address)

ABSTRACT

The conventional wisdom has been that IP is the natural protocol layer for implementing multicast related functionality. However, ten years after its initial proposal, IP Multicast is still plagued with concerns pertaining to scalability, network management, deployment and support for higher layer functionality such as error, flow and congestion control. In this paper, we explore an alternative architecture for small and sparse groups, where end systems implement all multicast related functionality including membership management and packet replication. We call such a scheme End System Multicast. This shifting of multicast support from routers to end systems has the potential to address most problems associated with IP Multicast. However, the key concern is the performance penalty associated with such a model. In particular, End System Multicast introduces duplicate packets on physical links and incurs larger end-to-end delay than IP Multicast. In this paper, we study this question in the context of the Narada protocol. In Narada, end systems self-organize into an overlay structure using a fully distributed protocol. In addition, Narada attempts to optimize the efficiency of the overlay based on end-to-end measurements. We present details of Narada and evaluate it using both simulation and Internet experiments. Preliminary results are encouraging. In most simulations and Internet experiments, the delay and bandwidth penalty are low. We believe the potential benefits of repartitioning multicast functionality between end systems and routers significantly outweigh the performance penalty incurred.

REFERENCES

• 1: E;. Bommaiah, A. McAuley, R. Ta/pade, and M. Liu. Amroute: Adhoc multicast routing protocol. Internet draft, }nternet Engineering Task Force, August 1998.
• 2: Stephen Casner , Stephen Deering, First IETF internet audiocast, ACM SIGCOMM Computer Communication Review, v.22 n.3, p.92-97, July 1992 [doi>10.1145/142267.142338]
• 3: Y. Chawathe, S. McCanne, and E. A. Brewer. An architecture for internet content distribution as an infrastructure service, February 2000. Unpublished work.
• 4: S. E. Deering, Multicast routing in internetworks and extended LANs, Symposium proceedings on Communications architectures and protocols, p.55-64, August 16-18, 1988, Stanford, California, United States
• 5: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 6: National Laboratory for Applied Network Research. Routing data. http://moat.nlaxtr.net/1Routing/rawdata/.
• 7: Cooperative Association for Internet Data Analysis. Mapnet project. http://www.caida.org/Tools/Mapnet/Data/.
• 8: P. Francis. Yallcast: Extending the internet multicast architecture, http://www.yallcast.com, September 1999.
• 9: Hugh W. Holbrook , David R. Cheriton, IP multicast channels: EXPRESS support for large-scale single-source applications, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.65-78, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 10: IPV6 backbone, http://www.6bone.org/.
• 11: Guy Kortsarz , David Peleg, Generating Low-Degree 2-Spanners, SIAM Journal on Computing, v.27 n.5, p.1438-1456, Oct. 1998 [doi>10.1137/S0097539794268753]
• 12: 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]
• 13: J. Liebeherr and B. S. Sethi. A scalable control topology for multicast communications. In Proceedings of IEEE In}ocorn, April 1998.
• 14: Scott Michel , Khoi Nguyen , Adam Rosenstein , Lixia Zhang , Sally Floyd , Van Jacobson, Adaptive web caching: towards a new global caching architecture, Computer Networks and ISDN Systems, v.30 n.22-23, p.2169-2177, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00246-3]
• 15: R. Perlman, C. Lee, T. Ballardie, J. Growcroft, Z. Wang, T. Mauler, C. Diot, J. Thoo, and M. Green. Simple multicast: A design for simple, low-overhead multicast. Internet Draft, Internet Engineering Task Force, March 1999. Work in progress.
• 16: Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4), RFC 1771, March 1995.
• 17: J. H. Saltzer , D. P. Reed , D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.277-288, Nov. 1984 [doi>10.1145/357401.357402]
• 18: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 19: Fred B. Schneider, Byzantine generals in action: implementing fail-stop processors, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.145-154, May 1984 [doi>10.1145/190.357399]
• 20: Kunwadee Sripanidkulchai , Andy Myers , Hui Zhang, A third-party value-added network service approach to reliable multicast, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.166-177, May 01-04, 1999, Atlanta, Georgia, United States
• 21: L Stoics, T.S.E. Ng, and H. Zhang. REUNITE: A recursive unicast approach to multicast. In Proceedings of IEEE INFOCOM'O0, Tel-Aviv, Israel, March 2000.
• 22: R. X. Xu, A. C. Myers, H. Zhang, and R. Yavatkar. Resilient multicast support for continuous-media applications. In Proceedings of NOSSDA V'97, May 1997.
• 23: E. W. gegura, K. L. Calvert, and S. Bhattacharjee. How to model an internetwork. In Proceedings o} IEEE Infocom, March 1996.

INDEX TERMS

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

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Documentation, Experimentation, Measurement, Performance, Standardization, Theory