On routes and multicast trees in the Internet

ABSTRACT

Multicasting has an increasing importance for network applications such as groupware or videoconferencing. Several multicast routing protocols have been defined. However they cannot be used directly in the Internet since most inter-domain routers do no implement multicasting. Thus these protocols are mainly tested either on a small scale inside a domain, or through the Mboné, whose topology is not really the same as Internet topology. The purpose of this paper is to construct a graph using actual routes of the Internet, and then to use this graph to compare some parameters - delays, scaling in term of state or traffic concentration - of multicast routing trees constructed by different algorithms - source shortest path trees and shared trees.

REFERENCES

• 1: Tony Ballardie , Paul Francis , Jon Crowcroft, Core based trees (CBT), Conference proceedings on Communications architectures, protocols and applications, p.85-95, September 13-17, 1993, San Francisco, California, United States
• 2: [Cal 83] R. Callon, Internet protocol, Proceedings of the IEEE, 71(12), Dec. 1983.
• 3: [DEF97] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, A. Helmy, L. Wei, Protocol Independent Multicast Version 2, Dense Mode Specification, Work in progress, Internet Draft, draft-ietf-idmr-pim-dm-05, May. 97, 12 p.
• 4: [EFD 97] D. Estrin, D. Farinacci, S. Deering and al., Protocol Independent Multicast-Sparse mode (PIM-SM) : Protocol Specification, Work in progress, Internet Draft, draft-ietf-idmr-PIM-SM-specv2-10, Sep. 97, 52 p.
• 5: [GPZ 96] D. Grad, JJ. Pansiot, S. Marc-Zwecker, Distributed Computation of Reduced Multicast Trees, Proceedings of TDP'96, La Londe les Maures, Jun. 96, pp. 91-107.
• 6: [KMB 81] L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees, Acta Informatica 15, pp. 141-145, 1981.
• 7: P. V. Mockapetris, Domain names - concepts and facilities, RFC Editor, 1987
• 8: John Moy, Multicast routing extensions for OSPF, Communications of the ACM, v.37 n.8, p.61-ff., Aug. 1994 [doi>10.1145/179606.179654]
• 9: [PGZ95] J-J. Pansiot, D. Grad, S. Marc-Zwecker, Towards a Logical Addressing and Routing Sublayer for Internet Multicasting, Proceedings of PROMS'95 Salzburg, Austria, Oct. 9-12 95, pp. 521-535.
• 10: [Pos 81a] J. Postel, Internet Protocol, Network Information Center, Request for Comments, RFC0791, Jan. 91, 45 p.
• 11: J. Postel, Internet Control Message Protocol, RFC Editor, 1981
• 12: [Wax 88] B.M. Waxman, Routing on Multipoint Connections, IEEE Journal of Selected Areas in Communications, Vol. 6, No. 9, Dec. 88.
• 13: D. Waitzman , C. Partridge , S. E. Deering, Distance Vector Multicast Routing Protocol, RFC Editor, 1988

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Measurement, Performance, Standardization, Theory