Multicast Papers Appeared in 1991

P. Barri and G. De Smet, "Distributed Connection Control and Maintenance for an ATM Multistage Interconnection Network," in Conference Record of the International Conference on Communications (ICC), pp. 692-698 (23.2), June 1991.

Abstract: This paper describes a distributed connection control protocol for an experimental ATM switch fabric. A switch is a multistage interconnection network with path search, resource allocation and path marking (the so called connection control functions). The switch fabric which will be described here is based on decentralized connection control functions within a multistage interconnection network. All actions of the presented connection control protocol are starting from the originating side of the connection, even for the connection release operation. Dead ends, i.e. erroneous terminating or broken connections, are detected with dedicated "explorer" and "maintenance" cells, whatever the reason of the problem may have been. The proposed connection control protocol treats point to point and point to multipoint connections in a similar way and is protected against cell loss, which is a natural event in ATM networks. We focus also on the maintenance aspects of this kind of switch fabric architecture. In particular, the distributed static load control mechanism and the marking of virtual connections are protected by a background restitution process.
Keywords: ATM switch, ATM switching MIN multicast, connection setup and release resource allocation

Mon Song Chen, "A multimedia multiparty teleconference," technical note, IBM T. J. Watson Research Center, Yorktown Heights, New York, 1991?

Abstract: MEET (multiple end-to-end teleconference) is envisioned as a desktop hub-free (peer) personal teleconference system that allows people to do ``face-to-face'' meetings without leaving their offices. Using MEET, users see each other via real-time motion video, talk and hear all the talks via real-time audio and present documents such as foils via an on-line Electronic Blackboard (EB). MEET is currently being designed and prototyped by the High Bandwidth Applications group at IBM T. J. Watson Research Center, and will be installed in the PARIS fast packet switched networks in the Aurora testbed. This article describes the goals, specifications, and prototype of the project.
Keywords: multimedia; teleconferencing; shared whiteboard; multicast; shared editor; CSCW
Annotation: PS/2 Model 80; disable voices from particular sources; dynamic connection-oriented multicast

X. Chen, J. F. Hayes, and M. K. Mehmothersi, "A One-Shot Access Scheme for a Multicast Switch," in Canadian Conference on Electrical and Computer Engineering, (Quebec), pp. 7.2.1-7.2.4, 1991.

Keywords: ATM; packet switching; multicast; switching; input buffer; performance evaluation; analysis
Annotation: The analysis is based on the assumption of random traffic, modeled by a Bernoulli process of packet arrival and a Bernoullitrials of copy distribution pattern. Input port queueing along with random selection policy is used to resolve the output request conflict. The primary performance measurement is the packet delay. A key assumption is that all copies of the same packet must be switched in the same slot.

Ching Hua. Chow, "On Multicast Path Finding Algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), pp. 1274-1283 (11B.1), Apr. 1991.

Abstract: We have designed and implemented three multicast path finding algorithms for networks with directed links; an optimal algorithm based on the dynamic programming technique, a heuristic algorithm with the assumption that all vertices have the multicast capability, and a heuristic algorithm for networks where some vertices do not have the multicast capability. Computation results show that the heuristic algorithms can find multicast paths whose costs are close to optimal and can operate with reasonable response time for large networks. We discuss applications of these path finding algorithms to set up multipoint connections for broadband multimedia multiparty services.
Keywords: multicast convergence Cast or concast broadcast directed network path finding algorithm RST (reverse spanning tree) performance analysis, path setup Ring With Hub videoconferencing, multimedia, switching networks, multiparty

R. Cusani and F. Sestini, "A Recursive Multistage Structure for Multicast ATM Switching," in Proceedings of the Conference on Computer Communications (IEEE Infocom), pp. 1289-1295 (11B.3), Apr. 1991.

Abstract: A recursive multistage structure for multicast ATM switching is proposed, based on a connection network with copying facility and external links connecting the outlets to the inlets. While the network generates only a few copies of an input multicast cell, the remaining are obtained by recycling the output copied cells to the corresponding inputs as many times as necessary. The basic features of a prototype binary multicast switch following this strategy are described. Its performance is also evaluated in terms of throughput and delay, via computer simulation.
Keywords: multicast ATM switch design switch architecture Copy Network (CN) Routing Network (RN) broadcast multicast connection network Telecommunications Project of the National Research Council (CNR) multicast tree

Wen Tsuen. Chen, Pi Rong. Sheu, and Jiunn Hwa. Yu, "Time Slot Assignment in TDM Multicast Switching Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), pp. 1296-1305 (11B.4), Apr. 1991.

Abstract: In this paper, we study the time slot assignment problem in Time-Division Multiplex switching systems which can support multicast transmissions. We show that this problem is NP-complete, i.e., computationally intractable. Two effective heuristic algorithms are proposed. To evaluate and compare the performance of these algorithms, a lower bound on the solution of this problem is derived and computer simulations are performed. The results of simulations show that the solutions generated by these heuristic algorithms are close to this lower bound on the average.
Keywords: multicast TDM multicast time slot assignment problem (MTSAP) Satellite-Switched Time-Division Multiple-Access (SS/TDMA) nonblocking multicast packet switch simulation

I. Chlamtac and O. Weinstein, "The Wave Expansion Approach to Broadcasting in Multihop Radio Networks," IEEE Transactions on Communications, vol. COM-39, no. 3, pp. 426-433, 1991.

Keywords: Packet radio; multihop; radio channel; broadcast
Annotation: In this paper we propose an algorithm for efficient communication between neighbours in multihop radio networks. Thealgorithm guarantees a bound on the transmission efficiency in aradio channel for arbitrary topology. The algorithm can be embedded in protocols for solving basic network problems such asbroadcast, multicast, leader election, or finding shortest paths

S. Deering, "ICMP router discovery messages," Request for Comments (Proposed Standard) RFC 1256, Internet Engineering Task Force, Sept. 1991.

Abstract: This document specifies an extension of the Internet Control Message Protocol (ICMP) to enable hosts attached to multicast or broadcast networks to discover the IP addresses of their neighboring routers.

Stephen Edward Deering, Multicast routing in a datagram internetwork. PhD thesis, Stanford University, Palo Alto, California, Dec. 1991.

Abstract: Most local area networks, as well as some other packet-switched networks, support multicast, the ability to address and deliver a packet to a set of destinations. Currently, when those networks are interconnected by routers or bridges to form an internetwork, the multicast service is either unavailable beyond a single network - as when using IP routers - or is offered in a way that significantly limits the scalability of the internetwork - as when using LAN bridges. To address these problems, we present a new service model for multicasting in a datagram (or connectionless) internetwork, and a set of new store-and-forward multicast routing algorithms to support that service model. The multicast service model, which we call the host group model, is a natural generalization of the unicast service model offered by datagram internetworks. Multicast packets are delivered to each member of a multicast group with the same ``best-efforts'' reliability and performance as unicast packets to that member. Multicast groups may be of arbitrary size, may change membership dynamically, and may have either global scope, that is, with members located anywhere in the internetwork, or local scope, with members confined to a particular administrative domain. Senders of multicast packets need not belong to the destination groups and need not know the membership of the groups. The new multicast routing algorithms to support the host group model take the form of extensions to the two unicast routing algorithms most commonly used in network-layer routers - the distance-vector algorithm and the link-state algorithm - and to the spanning-tree algorithm used by most datalink-layer bridges. In all cases, the delivery path of a multicast packet forms a tree, rooted at the sender, with copies of the packet being generated only at those points where the tree branches. The routing algorithms have low overhead, good performance, and scalability as good as, or better than, unicast routing. They may be used hierarchically, alone or in combination, to support multicasting across very large-scale internetworks.
Keywords: multicast; DVRMP; truncated broadcast; routing; IP; Internet; IGMP; reverse path forwarding; distance-vector; link-state

Ajei Gopal, Inder Gopal, and Shay Kutten, "Hardware flooding (preliminary version)," in SIGCOMM Symposium on Communications Architectures and Protocols, (Zürich, Switzerland), pp. 259-270, ACM, Sept. 1991. also in \em Computer Communication Review 21 (4), Sep. 1991.

Abstract: Traditional broadcast protocols are inappropriate for the high-speed networks of the future. Such protocols are limited by the speed of software processing, which becomes a bottleneck as network speeds increase. This paper presents a broadcast protocol that is appropriate for high-speed networks, and is tolerant of failures involving the loss of messages. The protocol is based primarily on the simple hardware functions present in a high-speed network node. This leads to message delivery at hardware speeds. In the unlikely event of a failure, some software intervention may be required to guarantee the timely termination of the protocol. However this software processing does not interfere with message delivery. We show that in the likely cases, the protocol guarantees message delivery within D\tau time, where D is the diameter of the network, and \tau is the maximum link delay.
Keywords: flooding; multicast; broadcast; reliable broadcast; high-speed networks

J. F. Hayes, R. Breault, and M. K. Mehmet-Ali, "Performance Analysis of a Multicast Switch," IEEE Transactions on Communications, vol. COM-39, no. 4, pp. 581-587, 1991.

Keywords: ATM; switching system; performance evaluation; multicast; input buffer

A. Jajszczyk and H. T. Mouftah, "An Architecture for a Photonic Fast Packet Switching Fabric," in Proceedings of the IEEE Conference on Global Communications (GLOBECOM), vol. 1, (Phoenix, Arizona), pp. 1219-1223, Dec. 1991.

Keywords: ATM; fast packet switching; switching network; architecture; ptical switching; self routing; multicast

Mark G. W. Jones, Soren Aksel Sorensen, and Steve R. Wilbur, "Protocol design for large group multicasting: the message distribution protocol," Computer Communications, vol. 14, pp. 287-298, June 1991.

Vachaspathi P. Kompella, Joseph C. Pasquale, and George C. Polyzos, "Two techniques for multicasting for multimedia applications," tech. rep., University of California, San Diego, Nov. 1991.

Keywords: multicasting; routing; multimedia

Soung C. Liew, "Multicast routing algorithms for 3-stage Clos ATM switching networks," in Proceedings of the IEEE Conference on Global Communications (GLOBECOM), (Phoenix, Arizona), pp. 1619-1625 (45.3), IEEE, Dec. 1991.

Abstract: An approach to building a large ATM switch is to simply set up a regularly structured network in which smaller switch nodes are interconnected. Routing is an issue if there are multiple paths from any input to any output in such a network. We focus on the 3-stage Clos network. An optimal and a heuristic algorithm have been designed and tested. Our results show that the heuristic algorithm can find multicast routes that are close to optimal within a response time that is significantly lower than that of the optimal algorithm. Further analysis of the experimental data suggests a hybrid implementation in which the optimal and heuristic algorithms are run in parallel with a set time limit. The algorithms and the discussion here also apply to other networks, including wide-area communication networks, with a two-hop structure.
Keywords: routing; ATM; fast-packet switching; Clos network

T. F. LaPorta and M. Schwartz, "Architectures, Features and Implementation of High-Speed Transport Protocols," IEEE Network, vol. 5, pp. 14-22, May 1991.

Annotation: Transport Protocols are responsible for management of end-to-end connections between hosts, error detection and correction, packet ordering and flow control. Three Gigabit speed network applications are full motion video, video on demand and computer imaging. Different applications have different needs when it comes to performance. TCP and TP4 are rejected by the authors as they impose too great an overhead in the 100Mb/s to 1Gb/s range and have control strategies such as Go-Back-N which waste too much network bandwidth. XTP, VMTP and HOPS are looked at as future transport protocols as they provide such things as implicit connections, implicit handshaking, data piggybacking on control messages and selective retransmission. Protocol processing overhead can be removed from the host CPU by implementing the protocol in silicon or by using dedicated outboard processors. Future transport protocols should offer a number of different options to the application layer so that they can match the QOS more exactly. Rate control and maximised credit schemes make more efficient use of bandwidth and processing power than traditional end-to-end flow control schemes. The design philosophy for future transport protocols should be success oriented with simple recievers. The architecture for future transport protocols should combine layers and use parallel functions. The implementation of future transport protocols should be separate from the OS with attention to the 'buffer layer'. The call management of future transport protocols should provide implicit and explicit connection setup, explicit connection tear down, support datagram and VC operation and support multicast. Data transfer in future transport protocols should use fixed format packets, checksums in the trailers, separate error recovery from flow control, use rate and maximised credit flow control, blocking packets for error recovery, periodic state exchanges, selective retransmission and less use of timers. The future transport protocols should provide highly flexible functionality.

Yiu Wing. Leung and Tak Shing. Yum, "Optimum Connection Paths for a Class of VideoConferences," in Conference Record of the International Conference on Communications (ICC), pp. 859-865, 27.6.1-27.6.7, June 1991.

Abstract: The optimum connection problem for a class of videoconferences in packet switched networks is studied. The conferees of a particular conference send their images to a chosen node, called the conference center, for processing. The conference center can either send distinct composite video to individual conferees or multicast the same composite video to all conferees. Depending on how the video is composed, the optimum connection paths form either the minimum conference tree or the minimum conference-multicast tree. We design algorithms for finding these trees and derive the conference blocking probability in fully connected networks. One to two orders of magnitude reduction of blocking is observed with the use of the optimum connection paths when compared to the strategy which chooses the call-initiating node as the conference center.
Keywords: videoconferencing videoconferencing, multipoint multicast multicast tree packet video traffic analysis

Paul G. Milazzo, "Shared video under Unix," in Proc. of Usenix Summer Conference, (Nashville, Tennessee), pp. 369-383, June 1991.

Abstract: The BBN Video Information Server, constructed by the Multimedia Systems Group, serves several workstations in nearby offices. The serve and workstations are both based on a combination of Unix workstations and Amiga personal computers, and communicate using a special video request protocol layered atop SUNRPC. The server supports a wide variety of video applications, including interactive video browsers and editors, programs that use moving images as user-interface objects, and programs that automatically index video that has closed captions. Our experience suggests improvements both in Unix and in workstation hardware. Native support for bandwidth-reservation protocols and multicasting, and synchronization primitives for character I/O devices would be invaluable, as would better clocks.
Keywords: NTP; packet video; RPC; video editor; analog video

Amir Milo and Ouri Wolfson, "The multicast policy and its relationship to replicated data placement," ACM Transactions on Database Systems, vol. 15, pp. 181-206, Mar. 1991.

Lek H. Ngoh, "Multicast support for group communications," Computer Networks and ISDN Systems, vol. 22, pp. 165-178, 1991.

Abstract: This paper describes a multicast model which can be integrated into existing unicast communication systems to provide better support for group communications. Multicast services are becoming more important, as more and more of today's network workstation environments are used to provide group communication for the exchange of multimedia information. These environments allow users to exchange information in the form of 'documents' containing text, graphics and voice; some systems support both store-and-forward (e.g., mail) and real-time (e.g., conferencing) material. In this paper, various multicast design issues are addressed and solutions are proposed to provide an effective multicast extension for a wide range of existing unicast protocols.
Keywords: multicast; group communications; multimedia

M. Naim~Yunus, "A queueing model for buffer overflow in multicast communications," in Proc. ITC specialists seminar, (Krakow), p. 11, Apr. 1991.

Keywords: Communication protocol; multicast; performance evaluation; buffer dimensioning

Pat Stephenson and Kenneth Birman, "Fast causal multicast," ACM Operating Systems Review, vol. 25, pp. 75-79, Apr. 1991.

Abstract: We begin by outlining a new protocol that efficiently implements a reliable, causally ordered multicast primitive and is easily extended into a totally ordered one. Since measurements show that the dominant cost of this protocol is message transport, the design of a lower level multicast transport protocol is discussed. The overall scheme scales with bounded overhead. Our first conclusion is that systems such as ISIS can achieve performance competitive with the best existing multicast facilities - a finding contradicting the widespread concern that fault-tolerance may be unacceptably costly. Our second conclusion is that the paradigm of multicast transport is extremely useful for constructing fault-tolerant applications. Our final conclusion is that the framework for fault-tolerant programming provided by ISIS is very useful in the design and construction of theses extensions to the basic system.
Keywords: reliable multicast; ISIS; reliability
Annotation: positive acknowledgement since RPC needs to send answers anyway

W. D. Sincoskie, "System Architecture for a Large Scale Video on Demand Service," Computer Networks and ISDN Systems, vol. 22, pp. 155-162, Sept. 1991.

Keywords: BISDN; ATM; switching system; architecture; multicast; video service; video conference

K. Sezaki, Y. Tanaka, and M. Akiyama, "A New ATM Switching Network which is Robust for Multicast," IEICE Transactions, vol. E74, pp. 2779-2784, Sept. 1991.

Keywords: ATM; switching system; architecture; multicast; multistage interconnection network

Guy Vonderweidt, John Robinson, Chris Toulson, Eliot Rubinov Mastronardi, and Birendra Prasada, "A multipoint communication service for interactive applications," IEEE Transactions on Communications, vol. 39, pp. 1875-1885, Dec. 1991.

Abstract: The multipoint communication layer (MCL) is a generic multipoint communication service designed to support highly interactive multimedia conferencing applications. It supports full-duplex multipoint communication between an arbitrary number of connected locations over a variety of networks, including LAN's, packet networks, ISDN, and the public switched telephone network (PSTN). It provides efficient multicast message sequencing and synchronization features by means of a centralized bridge, to which locations are connected either directly or through subbridges. MCL design was driven by the demanding real-time multipoint communication requirements of MICA (multimedia interactive conferencing application), described in a companion paper. In the present paper, we establish the context for MCL by considering MICA's communication requirements and reviewing related work in the area of multipoint communication. We present the overall design of the MCL service and describe its communication primitives, protocol message structure, and implementation. Comparison is made with alternative strategies, and the use of MCL services for other applications is examined.
Keywords: multicast; multimedia; teleconferencing

Tak Shing P. Yum and Mon Song Chen, "Multicast Source Routing in Packet-Switched Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), pp. 1284-1288 (11B.2), Apr. 1991.

Abstract: In this paper we present an address coding mechanism for multicast source routing packets in packet-switched networks. A simple algorithm for processing these address codes at intermediate output link adaptors is presented. It involves only the recognition of a particular link label at the front part of the address code and so can easily be implemented in hardware. Recognizing that the recipients of a multicast packet very often need to respond to the source node, we designed the Reverse Path address code that allows individual destination node to retrieve the reverse path address without searching the topology database and invoking any route computation program.
Keywords: multicast source-routing Automatic Network Routing (ANR) linear source-routing minimum multicast tree Branch-by-Branch (BB) address computation Reverse Path (RP) computation

Tak Shing Yum, Mon Song Chen, and Yiu Wing Leung, "Bandwidth Allocation for Multimedia Teleconferences," in Conference Record of the International Conference on Communications (ICC), pp. 852-858, 27.5.1-27.5.7, June 1991.

Abstract: To ensure the quality of a multimedia teleconference, it is essential that sufficient bandwidth be allocated for its use. In this paper a conference traffic model is formulated and link level and conference level congestion measures are derived. Motivated by the advantages of sharing transmission resources in TASI related voice communication systems, an analogous transmission policy for conference videos is proposed. The quantification of conference traffic also enables us to set an admission policy so that the network can accommodate as many conferences as possible without violating conference quality constraints.
Keywords: multimedia conferencing, multipoint conference bandwidth allocation QOS (quality of service) multicast traffic modeling admission control packet video video, traffic management

Y. Yang and G. M. Masson, "Nonblocking Broadcast Switching Networks," IEEE Transactions on Computers, vol. 40, no. 9, pp. 1005-1015, 1991.

Keywords: Circuit switching; multicast; switching network; nonblocking; multistage interconnection network; path control

M. N. Yunus, "A queueing model for buffer overflow in multicast communications," in ITC Specialists' Seminar Telecommunication Services for Developing Economies, (Cracow), p. 11, 1991.

Keywords: Multicast; finite buffer; model; overflow; cycle time; FIFO
Annotation: A protocol in multicast (point-to-multipoint) communications is considered where a sender sends copies of similar messages to a number of recipients and waits for acknowledgements from each recipient. The sender has a finite number of buffers to store arriving acknowledgement packets before processing them. A queueing model for buffer occupancy is described and calculations are made for the expected number of lost packets.