Reliability and scaling issues in multicast communication

ABSTRACT

The efficiency with which multicast communication can take place is largely determined by the network level support available for such communication. Two factors contribute to the complexity of supporting current multicast applications: the lack of reliable multicast transport mechanisms at the network level and the lack of network support for large scale multicast communication. In this paper, we examine the issues pertinent to eliminating these shortcomings. We first show that internet multicasting algorithms based on reverse path forwarding are inherently unreliable and present a source-tree-based reliable multicasting scheme. The new scheme makes use of simple inter-gateway protocols and works on top of previously developed distance vector and link state internet routing schemes. Next, to support large scale applications, we present a scheme for partial multicasting and introduce a new network level operation, called gather. The partial multicasting mechanism allows messages to be delivered to subsets of multicast destinations, while the gather operation aids gateways in selectively suppressing redundant messages, thus reducing the message complexity. Using simulations, we investigate the efficacy of our schemes in supporting a sample application based on multicast communication.

REFERENCES

• 1: L Aguilar , J J Garcia-Luna-Aceves , D Moran , E Craighill , R Brungardt, An architecture for a multimedia teleconferencing system, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.126-136, August 05-07, 1986, Stowe, Vermont, United States
• 2: S. R. Ahuja , J. Robert Ensor , David N. Horn, The rapport multimedia conferencing system, Proceedings of the ACM SIGOIS and IEEECS TC-OA 1988 conference on Office information systems, p.1-8, March 23-25, 1988, Palo Alto, California, United States
• 3: E. J. Berglund and D. Cheriton, "Amaze: A Multiplayer Computer Game," IEEE Software 2, No. 3(May, 1985).
• 4: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 5: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 6: C. Cheng , R. Riley , S. P. R. Kumar , J. J. Garcia-Luna-Aceves, A loop-free extended Bellman-Ford routing protocol without bouncing effect, Symposium proceedings on Communications architectures & protocols, p.224-236, September 25-27, 1989, Austin, Texas, United States
• 7: D. R. Cheriton and C. L. Williamson, "VMTP as the Transport Layer for High-Performance Distributed Systems,'' IEEE Communications Magazine, pp. 37-44 (June, 1989).
• 8: R. Cooper and K. P. Birman, "Supporting Large Scale Applications on Networks of Workstations," Proc. 2nd Workshop on Workstation Operating Systems, pp. 25-28 IEEE Computer Society Press, (Sept, 1989).
• 9: J. Crowcroft , K. Paliwoda, A multicast transport protocol, Symposium proceedings on Communications architectures and protocols, p.247-256, August 16-18, 1988, Stanford, California, United States
• 10: 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]
• 11: Y. K. Dalal, A distributed algorithm for constructing minimal spanning trees, IEEE Transactions on Software Engineering, v.13 n.3, p.395-405, March 1987
• 12: P. B. Danzig, Finite buffers for fast multicast, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.108-117, May 1989
• 13: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 14: B.J. Dempsey, W. T. Strayer, and A. C. Weaver, "Issues in Providing a Reliable Multicast Facility," Technical Report, Research Institute for Computing and Information Systems, Clear Lake, (July, I990).
• 15: Hector Garcia-Molina , AnneMarie Spauster, Ordered and reliable multicast communication, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.242-271, Aug. 1991 [doi>10.1145/128738.128741]
• 16: Protocol Engines Inc., XTP Protocol Definition Revision 3.4. July, 1989.
• 17: Mark G. W. Jones , Søren-Aksel Sørensen , Steven R. Wilbur, Protocol design for large group multicasting: the message distribution protocol, Computer Communications, v.14 n.5, p.287-297, June 1991 [doi>10.1016/0140-3664(91)90004-K]
• 18: N. Komada, K. Kera, and T. Kubo, "An Autonomous Decentralized Control System for Factory Automation," IEEE Computer 17 (12)pp. 73-83 (December, 1984).
• 19: J.M. McQuillan, I. Richer, and E. C. Rosen, "The new routing algorithm for the ARPANET," IEEE Trans. Communications COM-28 pp. 711-719 (May 1980).
• 20: P.M. Merlin and A. Segall, "A Failsafe Distributed Routing Protocol," 1EEE Trans. Communications COM- 27, No. 9 pp. 1280-1287 (September, 1979).
• 21: J. Moy, "OSPF Version 2," Request for Comments.' RFC 1247, (July, 1991 ).
• 22: B. Rajagopalan and P. K. Mckinley, "A Token-Based Protocol for Reliable, Ordered Multicast Communication,'' Proc. IEEE 8th Reliable Dist. Systems. Symposium, pp. 84-93 (October, 1989).
• 23: B. Rajagopalan and M. Faiman, "A Responsive Distributed Algorithm for Shortest Path Routing within Autonomous Systems," J. of lnternetworking 2, No. 1 pp. 51-69 (March, 1991).
• 24: Balasubramanian Rajagopalan, Failsafe routing and multicasting in dynamic internets, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 25: S. Ramakrishnan and B. Jain, "A Negative Acknowledgement with Periodic Polling Protocol for Multicast over LANs," IEEE INFOCOM '87, (April, 1987).
• 26: A. Segall and B. Awerbuch, "A Reliable Broadcast Protocol," IEEE Trans. Communications 31(7)pp. 896-901 (July, 1983).
• 27: A. Spector, "Distributed Transaction Processing and the Camelot System," Distributed Operating Systems: Theory and Practice, Springer Verlag, (1987).
• 28: D.W. Wall, "Mechanisms for Broadcast and Selective Broadcast," Technical Report No. 190, Dept. of EE and CS, Stanford University, (June, 1980).
• 29: Paul Wilson, Computer Supported Cooperative Work (CSCW): origins, concepts and research initiatives, Computer Networks and ISDN Systems, v.23 n.1-3, p.91-95, Nov. 1991

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

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

General Terms:
Algorithms, Design, Reliability