Core based trees (CBT)

ABSTRACT

One of the central problems in one-to-many wide-area communications is forming the delivery tree - the collection of nodes and links that a multicast packet traverses. Significant problems remain to be solved in the area of multicast tree formation, the problem of scaling being paramount among these.In this paper we show how the current IP multicast architecture scales poorly (by scale poorly, we mean consume too much memory, bandwidth, or too many processing resources), and subsequently present a multicast protocol based on a new scalable architecture that is low-cost, relatively simple, and efficient. We also show how this architecture is decoupled from (though dependent on) unicast routing, and is therefore easy to install in an internet that comprises multiple heterogeneous unicast routing algorithms.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Lee Breslau and Deborah Estrin. Design and Evaluation of Inter-Domain Policy Routing Protocols. Internetworking: Research and Ezperience, 2:177- 198, September 1991.
• 3: Scott Brim and John Moy. Support for Multicast Communications Across Wide-Area Networks. High Performance Network Research Report, Cotnell Univ., June 1992.
• 4: Ching-Hua Chow. On Multicast Path Finding Algorithms. In Infocom, Conference on Computer Communicaiions, pages 1274-1283. IEEE, April 1991.
• 5: C. Partridge D. Waitzman and S. Deering. RFC 1075, Distance Vector Multicast Routing Protocol. SRI Network Information Center, November 1988.
• 6: Yogen K. Dalal , Robert M. Metcalfe, Reverse path forwarding of broadcast packets, Communications of the ACM, v.21 n.12, p.1040-1048, Dec. 1978 [doi>10.1145/359657.359665]
• 7: Martin de Prycker, Asynchronous transfer mode: solution for broadband ISDN, Ellis Horwood, Upper Saddle River, NJ, 1991
• 8: 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
• 9: Stephen Edward Deering, Multicast routing in a datagram internetwork, Stanford University, Stanford, CA, 1992
• 10: S. E. Hardcastle-Kille. RFC 1279, X.500 and Domains. SRI Network Information Center, September 1991.
• 11: B. Kahle M. Schwartz, A. Emtage and B. Neuman. A Comparison of Internet Resource Discovery Approaches. Computing Systems, 5 (4):461-493, Fall 1992.
• 12: D. Piscitcllo. RFC 1209, The Transmission of IP Datagrams over the SMDS Service. SRI Network Information Center, March 1991.
• 13: S. Zabele R. Braudes. RFC 1458, Requirements for Multicast Protocols. $RI Network Information Cegter, May 1993.
• 14: David Wayne Wall, Mechanisms for broadcast and selective broadcast, 1980
• 15: S. Wilbur and M. Handley. Multimedia Conferencing' from Prototype to National Pilot. In INET'92, International Networking Conference, pages 483- 490, June 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design