Multicast routing in internetworks and extended LANs

ABSTRACT

Multicasting is used within local-area networks to make distributed applications more robust and more efficient. The growing need to distribute applications across multiple, interconnected networks, and the increasing availability of high-performance, high-capacity switching nodes and networks, lead us to consider providing LAN-style multicasting across an internetwork. In this paper, we propose extensions to two common internetwork routing algorithms—distance-vector routing and link-state routing—to support low-delay datagram multicasting. We also suggest modifications to the single-spanning-tree routing algorithm, commonly used by link-layer bridges, to reduce the costs of multicasting in large extended LANs. Finally, we show how different link-layer and network-layer multicast routing algorithms can be combined hierarchically to support multicasting across large, heterogeneous internetworks.

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: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 3: David Reeves Boggs, Internet broadcasting, 1982
• 4: D. R. Boggs, I. F. Shoch, E. A. Taft, and R. M. Metealfe. PUP: an internetwork architecture. IEEE Transactions on Communications, COM-2g(4):612--624, April 1980.
• 5: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 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: S. E. ~ng. Host Extensions for IP Multicasting. RFC 1054, SRI Network Information Center, May 1988.
• 8: The ethernet: a local area network: data link layer and physical layer specifications, ACM SIGCOMM Computer Communication Review, v.11 n.3, p.20-66, July 1981 [doi>10.1145/1015591.1015594]
• 9: L. R. Ford Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.
• 10: A. }. Frank, L D. Willie, and A. J. Bemstein. Multicast commanication on network computers. IEEE Software, 2(3):49-61, May 1985.
• 11: J. Hart. Extending the IEEE 802.1 MAC bridge standard to remote bridges. IEEE Network, 2( 1): 10--25, January 1988.
• 12: W. R. Hawe, M. F. Kempf, and A, J. Kirby. The extended local area network architecture and LANBridgo 100. Digital Technical Journal, (3):54-72, September 1986.
• 13: C. Hedrick. Routing Information Protocol. RFC (in preparation), SRI Network Information Center, November 1987.
• 14: R. Hinden and A. Sheltzer. The DARPA lnternet Gateway. RFC 823, SRI Network Information Center, September 1982.
• 15: IEEE Computer Society. Standards for local area networks: logical link control. ANSI/IEEE Standard 802.2-1985 (I$O/DIS 8802/2), 1985.
• 16: International Business Machines Corporation. Technical Reference PC Network. document 6322916.
• 17: International Organization for Standardization (ISO). Draft International Standard 8473, Protocol for Providing the Connectionless- Made Network Service. March 1986.
• 18: Secretariat USA (ANSI) ISO TC97 SC6. Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol. November 1987.
• 19: L. Kleinrock and F. Kamoun. Hierarchical routing for large networks; performance evaluation and optimization. Computer Networks, 1:155-174, 1977.
• 20: S.J. Leffier, R. g. Fabry, W. N. Joy, P. Lapsley, S. Miller, and C. Torek. An advanced 4.3BSD interproc~s communication tutorial. In Unix Prosratmr~r Supplementary Documents, Part 2, University of California, Berkeley, Ca., April 1986.
• 21: J. M. McQuillan, I. Richer, and E. C. Ros~a. The new routing algorithm for the ARPANET. IEEE Transactions on Convnu~ications, COM-28(5):711-719, May 1980.
• 22: J. M. McQuillan and D. C. Walden. The ARPANET design decisions. Computer Networks, 1, August 1977.
• 23: Radia Perlman, An algorithm for distributed computation of a spanningtree in an extended LAN, Proceedings of the ninth symposium on Data communications, p.44-53, September 1985, Whistler Moutain, British Columbia, Canada
• 24: J. Postel. Internet Protocol. RFC 791, SRI Network Information Center, September 1981.
• 25: W. D. Sincoslde and C. J. Cotton. Extended bridge algorithms for large networks. IEEE Network, 2(1):16-24, January 1988.
• 26: David Wayne Wall, Mechanisms for broadcast and selective broadcast, 1980
• 27: Xerox Corporation. Internet Transport Protocols. XSIS 028112, Xerox, Stamford, Connecticut, December 1981.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks; Packet-switching networks
          Nouns: Ethernet

General Terms:
Algorithms, Design