Multicast Papers Appeared in 1982 - 1987

Kenneth P. Birman and Thomas A. Joseph, "Reliable Communication in the Presence of Failures," ACM Transactions on Computer Systems, vol. 5, pp. 47-76, Feb. 1987.

Abstract: The design and correctness of a communication facility for a distributed computer system are reported on. The facility provides support for fault-tolerant process groups in the form of a family of reliable multicast protocols that can be used in both local and wide area networks. These protocols attain high levels of concurrency, while respecting application-specific delivery ordering constraints, and have varying cost and performance that depend on the degree of ordering desired. In particular, a protocol that enforces causal delivery orderings is introduced and shown to be a valuable alternative to conventional asynchronous communication protocols. The facility also ensures that the processes belonging to a fault-tolerant process group will observe consistent orderings of events affecting the group as a whole, including process failures, recoveries, migration, and dynamic changes to group properties like member rankings. A review of several uses for the protocols in the ISIS system, which supports fault-tolerant resilient objects and bulletin boards, illustrates the simplification of higher level algorithms made possible by our approach.
Keywords: multicast; atomic broadcast; fault-tolerant process group; reliable broadcast; protocols; reliable multicast
Annotation: Reliable multicast protocols are presented, which preserve consistency in distributed computations even in the presence of process failures. The main means to achieve this is by atomicity of multicasts and by consistent ordering of messages from different multicasts at all overlapping destinations [jon].

H. P. Katseff, "Flow-controlled multicast in multiprocessor systems," in Sixth Annual International Phoenix Conference on Computers and Communications, (Washington), pp. 8-13, IEEE Computer Society Press, Feb. 1987.

Abstract: Many application programs for a message-based multiprocessor supercomputer could make use of a multicast mechanism in which a message is sent to a large group of processes efficiently in a single operation. The author introduces multicast-channels, which provide a symmetric interface for establishing communications within a group of processors, as well as controlled and error-resilient communications within the group of processors. By allowing programmers to specify buffering requirements, a wide range of applications may be implemented in a deadlock-free manner. Multicast channels are suitable for implementation on a variety of interconnects, including bus-based switches and those providing simultaneous parallel communications, like systems based on the hypercube topology. The use of efficient, tree-based acknowledgement scheme that uses 0(log/sub 2/n) time to effect flow control and to deliver a multicast message sent on a multicast channel with n processors allows an implementation with low latency and high throughput for systems with thousands of processors.

G. P. Rossi and C. Garavaglia, "Link layer for cooperating process of a LAN with enhanced communication services.," Computer Communications, pp. 121-7, June 1987.

Abstract: Virtual network protocols provide classes of service suited to a multicast environment. Their availability offers higher layers a common frame work for the implementation of a computing system with distributed control.

S. Ramakrishnan and B. N. Jain, "A negative acknowledgement with periodic polling protocol for multicast over LAN," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (San Francisco, California), pp. 502-511, IEEE, Mar. 1987.

Abstract: This paper concerns the design of a protocol that ensures reliable one-to-many (multicast) communication of messages from a source station (transmitter) to a group of other stations (receivers), all connected over a local area network. Some analytical results and simulation results have been used to provide an assessment of its behavior. The protocol performance is also compared with an earlier multicast protocol. The consideration in this study have been to exploit the broadcast feature of the channel to the extent possible. We propose a new negative acknowledgement with periodic polling (NAPP) scheme for reliable communication. Necessary and sufficient conditions that relate the window size to the numbering scheme have been derived.
Keywords: multicast; ARQ; reliable transport protocol

S. Ramakrishnan and B. N. Jain, "Protocols for Reliable Multicast Over Local Area Networks," in Proceedings of the Twentieth Hawaii International Conference on System Sciences 1987 (E. A. Stohr, L. Hoevel, L. Haynes, Y. Chu, A. Speckhard, B. D. Shriver, R. R. Grams, and R. H. Sprague, Jr., eds.), (Honolulu), p. 500, Hawaii International Conference Syst. Sci., Jan. 1987. Published as Proceedings of the Twentieth Hawaii International Conference on System Sciences 1987, volume 3, number 2.

Abstract: One page summary only . Focuses on the design, analysis and simulation of multicast protocols. The aim is to develop protocols for reliable multicast communication from one transmitter (designated as the primary) to a group of N receivers (secondaries), assuming an arbitrary channel access scheme and an already established virtual circuit like connection.

D. Sibranietz, "Simulation of Multicast Computer Communication," SIMULA Newsletter, vol. 15, pp. 3-6, Aug. 1987.

Abstract: A brief overview of a simulation system which has been primarily developed to assess reliability and efficiency aspects of multicast communication protocols. The study of distributed algorithms, including mapping strategies and load balancing, are also proposed.

Don Towsley and Sanjay Mithal, "A selective repeat ARQ protocol for a point to multipoint channel," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (San Francisco, California), pp. 521-526, IEEE, Mar. 1987.

Abstract: We present a selective repeat protocol for a point-to-multipoint channel. This protocol is easy to implement and exhibits good throughput characteristics. A comparison of the performance of this protocol with those previously reported in the literature is made. Last, in the course of analyzing this protocol, we obtain a tighter bound on the throughput of Weldom's point to point selective repeat protocol.
Keywords: selective repeat; multicast; ARQ

K. Yukimatsu, N. Watanabe, and T. Honda, "Multicast communication facilities in a high speed packet switching network," in Proceedings of the Eighth International Conference on Computer Communication (P. J. Kuehn, ed.), (Amsterdam), pp. 276-81, North-Holland, Sept. 1987.

Abstract: Discusses the multicast communication facilities in a high speed packet switched network (HSPN) that can accommodate various kinds of terminals such as telephone sets, high speed data terminals and video terminals. The architecture of the HSPN is discussed. Since packet size in the HSPN is determined for each type of information media and allowable network delays in all media are different, packet ordering control with priorities is required. Some packet multiplexing methods, which allow high-priority packets to interrupt long, low-priority packets are proposed. It is proposed to provide multicast communication facilities in the HSPN as functions of the data link and the network layers, instead of the session layer. With these facilities real-time broadcasting can easily be provided. The control mechanism for the multicast packet communications in the HSPN nodes is also described. An information service using the HSPN's multicast is presented.

David R. Cheriton, "VMTP: A Transport Protocol for the Next Generation of Communication Systems," in SIGCOMM Symposium on Communications Architectures and Protocols, (Stowe, Vermont), pp. 406-415, ACM, Aug. 1986. also in Computer Communications Review, 16 (3), August 1986.

Abstract: The Versatile Message Transaction Protocol (VMTP) is a transport-level protocol designed to support remote procedure call, multicast, and real-time communication. The protocol is designed for efficient page-level network file access in particular.
Keywords: transport protocol; VMTP

S. Deering, "Host extensions for IP multicasting," RFC 988, Internet Engineering Task Force, July 1986. (Obsoletes RFC0966); (Obsoleted by RFC1112, RFC1054).

Abstract: This memo specifies the extensions required of a host implementation of the Internet Protocol (IP) to support internetwork multicasting. This specification supersedes that given in RFC 966, and constitutes a proposed protocol standard for IP multicasting in the ARPA-Internet. The reader is directed to RFC 966 for a discussion of the motivation and rationale behind the multicasting extension specified here.

A. Endrizzi, G. De Grandi, and J. Curioni, "The DUAL LAN network communication and synchronisation services," SPIE International Society Optical Engineers (USA), vol. 715, pp. 53-8, Sept. 1986.

Abstract: The DUAL network offers both conventional (logical lines, X25, ISO 8802.3) and advanced (multicast, synchronization) services. It is based on multi-microprocessor nodes interlinked by means of fiber optics trunks. The DUAL ring is installed in a campus of several km/sup 2/, interconnecting up to 40buildings and serves as the backbone network for a number of other networks and as a test bed for the implementation of 'second generation' data transmission and disstributed informatics services.

L. Hughes, "A Multicast Transmission Taxonomy," Tech. Rep. 221, Newcastle University, Aug. 1986.

Abstract: The main idea of the paper is to look at the different ways multicast packets can be addressed (individual vs. group addresses, single vs. multiple addresses) and how the need to translate addresses e.g. from group to individuals influences the number of packets required for each multicast.
Keywords: Multicast addressing

G. Karjoth, "New Communications Services: A Challenge to Computer Technology," in Proceedings of the Eighth International Conference on Computer Communication (P. J. Kuehn, ed.), (Amsterdam), pp. 479-84, North Holland, Sept. 1986.

Abstract: The inherent complexity of distributed database protocols demand for a formal treatment to insure that their definition is complete and unambiguous. In order to initiate system developers in the use of formal techniques the author first gives an introduction to Milner's CCS, an algebra where processes interact via synchronized communication. From a distributed database protocol which is robust in the face of site crashes and communication outage a recovery procedure is described in CCS. Its specification reflects very well the hierarchic structure of the database system. The underlying network with all properties relevant for the database is defined. Based on its virtual circuit service higher level commmunication protocols such as multicast and circular message passing are established. The election of an unique successor in the case of the lock handler's outage is described in the definition of the distributed recovery mechanism.

Y. Liu, T. B. Gendreau, C. T. King, and L. M. Ni, "A session layer design of a reliable IPC system in the Unix 4.2 environment," in Proceedings of the Computer Networking Symposium, (Washington, DC), pp. 120-9, IEEE Compututer Society Press, Nov. 1986.

Abstract: A description is given of the design for a universal and reliabel set of interprocess communication (IPC) services int hte Unix 4.2BSD environment. The universal IPC services include one-to-one and multicast send, asynchronous and synchronous communication, blocking and nonblocking receive command, and group manipulation. The networking facility in Unix 4.2BSD provides users with direct access to the transport layer, which provides rudimentary IPC services. The lack of a universal set of IPC services in Unix 4.2BSD makes the development of distributed algorithms and distributed programming languages difficult. The authors consider the design of universal IPC services to be session layer services which provide services to the distributed application layer and require rudimentary IPC services from the transport layer. The proposed set of IPC primitives provides reliable service and is implemented in networked Sun workstations.

A. G. Waters, "The use of broadcast and multicast techniques on computer networks," in Conference on Electronic Delivery of Data and Software, (London), pp. 45-50, IERE (Institute of Electronic and Radio Engineers), Sept. 1986. Published as Conference on Electronic Delivery of Data and Software, number Publ. No. 69.

Abstract: Several types of packet network are based on common access to a shared broadcast channel. However, the broadcast facility is normally denied to user applications which have been principally confined to using point-to-point techniques. The paper investigates the possibilities offered to applications programs by allowing them to broadcast packets. The transmission of a single message to many destinations makes economic use of the broadcast channel and allows novel ways of working. An overview is presented of some techniques which have been devised to provide applications programs with facilities for one-to-many or many-to-many communications. Examples of protocols for file distribution are given. Other application areas are discussed: including the location of resources, the advertising of facilities and the dispersal of statistical information.

D. Wiebe, "A distributed repository for immutable persistent objects," in OOPSLA '86 Object-Oriented Programming Systems, Languages and Applications. Conference Proceedings, (Portland, OR, USA), pp. 453-65, Sept. 1986. Published as OOPSLA '86 Object-Oriented Programming Systems, Languages and Applications. Conference Proceedings, volume 21, number 11.

Abstract: Jasmine is an object-oriented system for programming-in-the-large. It describes software using system model objects. These objects are persistent (they have lifetimes of days or decades) and immutable (since system models act as historical records). The paper describes JStore, a distributed, replicated repository for system model objects which provides robust, transactional, write-once storage. Designs are presented for the serialization, location, and replication of objects. Description procedures serialize objects for network transmission and permanent storage. An expanding ring multicast search algorithm locates saved objects.

M. Ahamad and A. J. Bernstein, "An application of name based addressing to low level distributed algorithms," IEEE Transactions on Software Engineering, vol. SE-11, pp. 59-67, Jan. 1985.

Abstract: An interprocess communication structure for a distributed language is described which provides message level communication, multicast, and a generalized naming facility. The design is oriented to the needs of low level algorithms which, for example might be used in a distributed operating system to support resource allocation or enhance reliability. The proposal is illustrated by programming several distributed algorithms from the literature. An implementation is described that takes advantage of physical multicast technology, and reduces to more conventional schemes for common commmunication paradigms.

M. Ahamad and A. J. Bernstein, "Multicast communication in Unix 4.2BSD," Computing Systems, pp. 80-7, May 1985.

Abstract: The socket abstraction in Unix 4.2 SBD is generalized to include multicast sockets, which have an identical user interface to that of unicast sockets. Multicast sockets are supported by a multicast protocol, MP. The data structures available in the Unix kernel for implementing unicast sockets are also used for multicast sockets. The implementation takes advantage of the multicast and broadcast capability provided by many networks. All members of a group of processes communicating in multicast mode on a particular network receive copies of a single message sent on the network. The membership of such a group may be dynamic. An algorithm is described which ensures that all members of the group are informed of additions to and deletions from the group.

S. Deering and D. Cheriton, "Host groups: A multicast extension to theinternet protocol," RFC 966, Internet Engineering Task Force, Dec. 1985. (Obsoleted by RFC0988).

Abstract: This RFC defines a model of service for Internet multicasting and proposes an extension to the Internet Protocol (IP) to support such a multicast service. Discussion and suggestions for improvements are requested.

A. J. Frank, L. D. Wittie, and A. J. Bernstein, "Multicast communication on network computers," IEEE Software, vol. 2, pp. 49-61, May 1985.

Abstract: Several techniques for multicast are discussed. Packet casting is described, followed by multicast on netcomputers. As an example of group organization and group multicast, the implementation of the Micros operating system for the Stony Brook netcomputer is presented.

T. Kudoh, H. Amano, T. Boku, and H. Aiso, "NDL: a language for solving scientific problems on MIMD machines," in Proceedings of the First International Conference on Supercomputing Systems: SCS 85, (Washington), pp. 55-64, IEE Computer Society Press, Dec. 1985.

Abstract: A new programming language for MIMD parallel machines, called NDL (Node Description Language), is proposed. In most scientific problems, there exist systems to be analyzed. For example, in the analysis of electronic circuits, there exist many elements which can correspond to concurrent processes. Therefore, in solving these problems, it is efficient to specify the elements and their relationships independently. Moreover, the system is static throughout the whole hob. And NDL program consists of two parts: the node description part and the network description part. The communications among processes are performed by multicast, i.e. data transfer from one process to multiple processes. To reduce the process control overhead, the network is static and processes are never created or deleted dynamically. Libraries can be defined for various applications.

Yeong Jin Kim and Kilnam Chon, "A study on addressing and routing for internet multicast," Journal Korea Information Sciences Society, vol. 12, pp. 180-92, Aug. 1985.

Abstract: Internet multicast is the delivery of an internet packet to all members of a group within the internet. This paper proposes and analyzes the mechanism to solve the problem of the multicast in the internet sublayer. For multidestination addressing, the internet packet header with fixed length is designed. The internet routing algorithm to multicast the internet packet is proposed, and performance of the mechanismis analyzed.

P. Martin, C. Guerin, M. Chereque, and B. Sehabiague, "The MAX project: a fault tolerant local area network architecture," in AFCET Congres Automatique 1985. The Tools for Tomorrow, (Paris), pp. 277-88, AFCET, Oct. 1985.

Abstract: MAX is a dependable local area network distributed architecture. Its aim is the definition and realization of a local area network machine which manages, in a transparent fashion with respect to the user, access to objects distributed in the machine and the fault tolerance according to the funtion-by-function user-specified needs in service continuity. The local area network machine allows connection of heterogeneous equipment communicating by means of standard protocols (opening to the ISO world) and the connection of equipment using specific protocols insuring a high level of fault tolerance and performance. The specific protocols are reliable and efficient multicast protocols which simplify cooperation between applications and offer a distributed system environment for the management of distributed objects. The developed architecture presents a strong interactiveness and adapts to the constraints of time and distribution of different application types, especially those of factory applications. Finally, the local area networks machine, authorizing the connection of different computers to a local area network with varied performance, offers a wide range of price, performance and fault tolerance.

T. Minami, K. Yamaguchi, N. Fujina, H. Hamano, M. Suyama, K. Iguchi, and I. Yamada, "200 Mb/s synchronous TDM loop optical LAN, suitable for multi-service integration," in Proceedings of the IEEE Conference on Global Communications (GLOBECOM), vol. 1, (New York), pp. 15-20, IEEE, Dec. 1985.

Abstract: A 200 Mb/s multiservice optical LAN using a synchronous TDM loop structure is described. The LAN consists of a central supervisory node and multiple service nodes connected by an optical fiber loop. Multiple independent communication paths of various speeds up to 140 Mb/s and various modes, including point-to-point, ring, and multicast, can be provided on the loop. The structure of this LAN is quite suitable for integration of multiple services, including video, image, data, and voice, since each service can independently choose its own speed, access method, and mode. Various LSI-based high-speed hardware technologies were successfully introduced and compact LAN equipment was obtained. The system and hardware structure of LAN, together with high-speed hardware technology and applications are described.

Lorenzo Aguilar, "Datagram routing for internet multicasting," in SIGCOMM Symposium on Communications Architectures and Protocols, (Montreal, Canada), pp. 58-63, ACM and IEEE, June 1984. also in \em Computer Communications Review, vol. 14, No. 2.

Abstract: We present a solution to the problem of multidestination routing in internetworks. The component subnets of these internets share a common datagram internet layer, and the gateways and hosts can determine the next gateway en route to a foreign net. Our datagram routing offers high resilience to network failures, major reductions in network traffic, and no changes whatsoever to the subnetwork routing. The routing follows ``shortest'' paths as defined by the distance criteria of an internet. We intend to use the algorithm as an option of the DoD Internet Protocol with only minor changes to IP while preserving interoperability with IP modules not supporting multidestination.
Keywords: multicast; routing; IP; network layer

Jo Mei Chang and N. F. Maxemchuk, "Reliable broadcast protocols," ACM Transactions on Computer Systems, vol. 2, pp. 251-273, Aug. 1984.

Abstract: A reliable broadcast protocol for an unreliable broadcast network is described. The protocol operates between the application programs and the broadcast network. It isolates the application programs from the unreliable characteristics of the communication network. The protocol guarantees that all of the broadcast messages are received at all of the operational receivers in a broadcast group. In addition, the sequence of messages is the same at each of the receivers and a total ordering exists among all broadcast messages. This unique message sequencing can be used to simplify distributed database systems and distributed processing algorithms. The protocol can operate with as few as one acknowledgement message per broadcast message, instead of one acknowledgement from each receiver per broadcast message. The protocol continues to operate when sites in the broadcast group fail.
Keywords: broadcast; protocol; multicast; message sequencing; failure recovery; fault tolerance

P. Economopoulos and M. L. Molle, "On the performance of slotted ALOHA in a spread spectrum environment," ACM Computer Communication Review, vol. 14, pp. 234-41, June 1984.

Abstract: The authors present an extension of the slotted ALOHA protocol for use in a spread spectrum packet radio environment. With spread spectrum, N distinct codes are available, each code being used as a separate channel. Running an independent copy of the protocol on each of these channels would be undesirable, since each user would have to collect one channel to monitor for packets addressed to it, inducing a logical partitioning of the user population into N groups. We examine the effect of separating packet into a short preamble, which is sent over a public channel, and a body, which is sent over a private channel. M of the available codes are used as preamble channels, and the remaining N-m codes are used for actual packet transmission. If m<multicast packets, and still make use of all of the available channels.

S. Ramakrishnan and B. N. Jain, "Design and analysis of protocols for reliable multicast over broadcast channels," in Networks India 84. International Symposium on Data Communication and Computer Networks. (H. N. Mahabala, K. B. Lakshmanan, and S. Srinivasan, eds.), (Bombay), pp. 79-95, Computer Society India, Oct. 1984.

Abstract: Concerns with the design of protocols that ensure reliable (i.e., loss-free, error-free, duplication-free, and in sequence) one-to-many communication over a broadcast channel, for example, Ethernet. The authors design, and analyze for throughput and delay characteristics, a series of protocols. The protocols developed attempt to (i) minimize the number of response transmissions by receiver stations, and (ii) avoid simultaneous transmission of responses. Fundamental to the above development are two assumptions: (1) the reponsibility of ensuring that a sequence of messages is indeed received by a receiver station rests solely with itself, rather than with the message transmitter (as is the case with one-to-one communication protocols), and (2) given that a receiver station has not received a message multicast, then there are other receivers, who, with nonzero probability, also do not receive it. Salient features of the approach are (1) all transmissions are multicast, and (2) receivers arbitrate in sending their retransmission requests.

K. Rothermel and B. Walter, "A kernel for transaction oriented communication in distributed database systems," in International Conference on Distributed Computing Systems, (Silver Spring, MD, USA), pp. 557-65, IEEE Computer Society Press, May 1984.

Abstract: A kernel for transacation-oriented communication services is proposed as an adaption module between distributed database systems and the basic communication system. This kernel provides high-level communication primitives that are a good base on which to develop transaction oriented applications efficiently. The kernel also maintains recoverable transaction state tables that can be used to recall uncompleted transactions during restart recovery. It is argued that participating kernels should communicate by multicast.

P. V. Mockapetris, "Analysis of reliable multicast algorithms for local networks," ACM Computer Communication Review, vol. 13, pp. 150-157, Oct. 1983. Eighth Data Communications Symposium.

Abstract: Three types of multicast transactions for local networks are described and analyzed: positive, separate acknowledgements from each receiver, negative acknowledgements from left out receivers and saturation sending of multicast requests without any acknowledgements.

T. Takizuka, K. Matsuo, S. Lisaku, and K. Ono, "Design and evaluation of satellite packet communication protocols for integrated services networks," in Proceedings of the IEEE Conference on Global Communications (GLOBECOM), vol. 3, (New York), pp. 1358-63, IEEE, Nov. 1983.

Abstract: Describes a new error-control scheme and multicast commmunication protocols which are suitable for a satellite link, and also the protocol integration method used in the satellite packet communication system. The defects of the selective reject scheme are investigated, and a modified error-control scheme, called MN-SREJ, is proposed to attain high throughput efficiency through a medium-quality link with a long propagation delay. The effect on throughput efficiency of the slf-orthogonal convolution cose and the BCH code used as forward error correcting codes in the satellite channels, is examined. To utilize the multiple-access capability of a satellite, multicast communication procedures are proposed and evaluated. A satellite packet communication system that integrates packet-switching type and circuit-switching type protocols is introduced.

Andrew D. Birrell, Roy Levin, Roger M. Needham, and Michael D. Schroeder, "Grapevine: An Exercise in Distributed Computing," Communications ACM, vol. 25, pp. 260-274, Apr. 1982.

Abstract: Grapevine is a software package that provides facilities for the delivery of electronic mail, for naming people, machines, and services; for authenticating people and machines; and for locating services on the internet. Very interesting in the context of multicast are the ways proposed for dealing with groups (of servers, mail recipients etc.) In terms of reliability and consistency, the proposed algorithms are rather relaxed.
Keywords: distributed naming and binding; replicated databases

P. Decitre, J. Estublier, A. Khider, X. Rousset De Pina, and I. Vatton, "An efficient error detection mechanism for a multicast transport service on the DANUBE network," in Local Computer Networks. Proceedings of the IFIP TC 6 International In-Depth Symposium, (Amsterdam), pp. 335-47, North-Holland, Apr. 1982.

Abstract: Presents an error deteection mechanism which has been developed at Grenable by the IMAG laboratory and the CII-Honeywell Bull research center. It provides a new way of detecting errors in the transmission of messages from several sources to several destinations. It has been designed to be used at the transport station level to implement a reliable multicast service. The main idea is to use the mutual exclusion provided by the transmission medium to create a numbering system which allows error detection without sending positive acknowledgements. This techinque can be applied to broadcast network such as CSMA/CD which has a hardware mutual exclusion mechanism provided by the contention algorithm.