Mostafa H. Ammar, "Probabilistic Multicast: Generalizing the Multicast Paradigm to Improve Scalability," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: We consider the multicast-to-some generalization of the traditional multicast paradigm. In this form of communication, a multicast group is still associated with each multicast message. It is, however, only necessary for any randomly determined subset of the multicast group to receive a multicast message. This subset is not defined a priori nor is it necessarily the same from one multicast to the next for the same group. We explore the use of this (probabilistic) multicast communication paradigm to address scalability issues in the response collection application which arises in some distributed computing applications. We also show how this form of multicast can be used to reduce the discarding of responses to the multicast message due to buffer overflow at the multicast source.
Grenville Armitage, "gnet: An ATM LAN signalling protocol," Technical Report ISBN 85867 077 1, Department of Electrical Engineering, University of Melbourne, Melbourne, Australia, Feb. 1994.
Abstract: Departmental Technical Report, describing version 1.0 of 'gNET'. gNET is a simple ATM signalling protocol developed to support research into the building of a small ATM LAN with multimedia workstations. It supports unicast and multicast VCCs and VPCs (where appropriate switch fabrics exist). It supports environments where multiple ATM nodes may share the access medium to a single switch port (e.g. wireless ATM, or shared copper media).
Keywords: ATM; local area network; LAN; signalling; multicast
A. A. Abonamah, F. N. Sibai, and N. K. Sharma, "Conflict Resolution and Fault-Free Path Selection in Multicast-Connected Cube-Based Networks," IEEE Transactions on Computers, vol. 43, Mar. 1994.
Abstract: In large multistage interconnection networks (MIN's) used in multiprocessing systems with hundreds of processors, the probability of one or more switch and/or link failures in the network is considerably high. This is compounded by the fact that in the multicast connection mode, a source-destination(s) connection may be blocked by some other established connection, even if the required destination is not busy. These two factors, namely: failure and blocking, can degrade the overall network performance in a random access environment. To make the network more robust and less susceptible to blocking, multiple-paths MIN's have been proposed. However, with multiple-path MIN's, the problem of conflict resolution and fault-free path selection becomes a formidable task. In this correspondence, we present an algorithm that solves the conflict resolution problem in fault-tolerant multicast-connected MIN's. Without loss of generality, we apply the algorithm to reconfigure a four-path cube-based network. An intensive simulation study is conducted to reveal the performance improvement gained by the conflict resolution and fault-free path selection algorithm on the network under study. The simulation results indicate that the probability of failure to provide multicast connections using two paths is comparable to that of using three and four paths under various fault scenarios. The results also indicate that an effective reconfiguration algorithm based on two alternate paths has a great impact on the network performance in the presence of faults and conflicts. Index Terms - Adaptive routing, complementary two-stage cube, conflict resolution, fault-tolerance, multicast connections, multistage interconnection network.
Steven Baker, "Multicasting for sound and video," Unix Review, vol. 12, pp. 23-29, Feb. 1994.
Keywords: multicast; Nevot; vat; ivs; nv; IP; Internet; packet audio; packet video
Carsten Bormann and Gero Hoffmann, "Xmc and Xy - Scalable Window Sharing and Mobility or From X Protocol Multiplexing to X Protocol Multicasting," technical report, Technische Universität Berlin, 1994.
Abstract: To transform readily available applications into synchronous groupware (for ``joint editing'' etc.), window sharing tools such as shX and XTV have become popular. The well-known implementations of this concept have two major problems in a scalable telecooperation environment, however: They require sending information to each of the target displays (X servers) separately, wasting enor mous amounts of bandwidth. They also cannot cope with the rapidly changing constituencies of real world conferences (in particular, with constituencies drop ping to zero momentarily, or with large sets of read-only participants). Xy is a new window sharing tool that addresses these problems, in particular by introducing Xmc, a variation of the X11 protocol that can be multicast to all participants in a window sharing scenario. As a side effect, Xy's support for clients running with zero target X servers provides for mobility of X users.
Keywords: Xy; application sharing; X protocol multicasting
Jae W. Byun and Tony T. Lee, "The Design and Analysis of an ATM Multicast Switch with Adaptive Traffic Controller," IEEE/ACM Transactions on Networking, vol. 2, June 1994.
Abstract: This paper describes several improvements to a nonblocking copy network proposed previously for multicast packet switching. Our improvements provide a complete solution to some system problems inherent in multicasting. The input fairness problem caused by overflow is solved by a cyclic running adder network (CRAN), which can calculate running sums of copy requests starting from any input port. The starting point can change adaptively in every time slot based on the overflow condition of the previous time slot. The CRAN also serves as a multicast traffic controller to regulate the overall copy requests. The throughput of a multicast switch can be improved substantially if partial service of copy request is implemented when overflow occurs. Call-splitting can also be implemented by the CRAN in a straightforward manner. Nonuniform distribution of replicated packets at outputs of copy network may affect the performance of the following routing network. This output fairness problem due to underflow is solved by cyclically shifting the copy packets in every time slot. An approximate queueing model is developed to analyze the performance of this improved copy network. It shows that if the loading on each output of the copy network is maintained below 80%, the average packet delay in an input buffer would be less than two time slots.
Christer Bohm, Perl Lindgren, Lars Ramfelt, and Peter Sjödin, "The DTM gigabit network," Journal of High Speed Networks, vol. 3, no. 2, pp. 109-126, 1994.
Abstract: DTM is a set of protocols for high-speed networks, based on bandwidth reservation and with support for dynamic reallocation of bandwidth. It is designed for real-time multimedia applications and for high-speed computer communication. DTM uses a novel medium-access technique and provides a multicast, fast circuit-switched service. Several DTM networks can be connected into one large network. A prototype implementation and testbed is being constructed.
Pravin Bhagwat, Partho Mishra, and Satish K. Tripathi, "Effect of Topology on Performance of Reliable Multicast Communication," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: In this paper we examine the performance implications of providing reliability in conjunction with multicast transport over a high speed wide area network. We use a block based acknowledgment and selective retransmission protocol to evaluate the impact of the loss rate and the multicast tree topology on the achievable throughput. Our results show that even when the buffer overflow probability at switches and receivers is low, the cumulative loss probability seen by a source may be quite high. We also demonstrate that the average throughput increases significantly if the transport protocol delivers packets to the application layer out-of-sequence. We investigate the scaling properties of the error control mechanism and show that the multicast tree topology that results in minimum transfer time is not necessarily the same as the one constructed using minimal bandwidth or shortest path algorithms.
Keywords: Multicast; Error-Control; Reliable Communication; Transport Protocol
C. Bormann, J. Ott, H. C. Gehrcke, T. Kerschat, and N. Seifert, "Mtp-2: Towards achieving the S.E.R.O. properties for multicast transport," in International Conference on Computer Communications Networks?, (San Francisco, California), Sept. 1994.
Abstract: Existing reliable multicast transport have focused on achieving reliability from the point of view of senders of messages. Many applications in the area of synchronous groupware do not need this strong property, but can nonetheless benefit from a reliable multicast protocol. For use with the X window sharing tool Xy, we have implemented the multicast transport protocol MTP as described in RFC 1301. Combined with reliable (TCP) unicast connections, MTP turns out to be a relatively good match for the transport requirements of Xy. Based on these experiences, we have designed a successor protocol, which aims to be more generally applicable by achieving scalability, efficiency, robustness, and ordered delivery of messages.
Keywords: reliable multicast; MTP; TCP; multicasting; transport protocol; reliable broadcast; scalability; teleconferencing; shared X; Xy
Carsten Bormann, Jörg Ott, Hans Christian Gehrcke, Torsten Kerschat, and Nils Seifert, "Mtp-2: S.E.R.O reliable multicast," in IETF Meeting, (Toronto, Canada), Internet Engineering Task Force (mmusic working group), July 1994.
Keywords: conference control; multimedia; multicast; shared X; application sharing
Jean Chrysostome Bolot and Thierry Turletti, "A Rate Control Mechanism for Packet Video in the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: Datagram networks such as the Internet do not provide guaranteed resources such as bandwidth or guaranteed performance measures such as maximum delay. One way to support packet video in these networks is to use feedback mechanisms that adapt the output rate of video coders based on the state of the network. In this paper, we present one such mechanism. We describe the feedback information, and how it is used by the coder control algorithm. We also examine how the need to operate in a multicast environment impacts the design of the control mechanism. Our mechanism has been implemented in the H.261 video coder of IVS. IVS is a videoconference system for the Internet developed at INRIA. Experiments indicate that the control mechanism is well suited to the Internet environment. In particular, it makes it possible to establish and maintain quality videoconferences even across congested connections in the Internet. Furthermore, it prevents video sources from swamping the resources of the Internet, which could lead to unacceptable service to all users of the network.
Keywords: Packet video; Internet; Feedback control
Jean Chrysostome Bolot, Thierry Turletti, and Ian Wakeman, "Scalable feedback control for multicast video distribution in the internet," in SIGCOMM Symposium on Communications Architectures and Protocols, (London, England), pp. 58-67, ACM, Aug. 1994.
Abstract: We describe a mechanism for scalable control of multicast continuous media streams. The mechanism uses a novel probing mechanism to solicit feedback information in a scalable manner and to estimate the number of receivers. In addition, it separates the congestion signal from the congestion control algorithm, so as to cope with heterogeneous networks. This mechanism has been implemented in the IVS video conference system using options within RTP to elicit information about the quality of the video delivered to the receivers. The H.261 coder of IVS then uses this information to adjust its output rate, the goal being to maximize the perceptual quality of the image received at the destinations while minimizing the bandwidth used by the video transmission. We find that our prototype control mechanism is well suited to the Internet environment. Furthermore, it prevents video sources from creating congestion in the Internet. Experiments are underway to investigate how the scalable probing mechanism can be used to facilitate multicast video distribution to large numbers of participants.
Keywords: congestion control; packet video
Markus Hidell Christer~Bohm and Per Lindgren, "DTM - a true broadband concept," in Proc. 6th ERCIM Workshop, (Stockholm, Sweden), June 1994.
Abstract: The paper discusses the use of fast circuit-switching in future high-capacity networks. We believe that the capacity and the size of the public network will increase to an extent where it is infeasible to rely on bandwidth optimization and dynamic congestion control mechanisms [8]. Dynamic synchronous Transfer Mode (DTM) is a new protocol suite based on synchronous fast circuit switching. It is designed for high-speed networks running at several gigabits per second. We believe a large part of the traffic in future high-speed integrated networks will result from real-time applications, such as video and audio. We argue that a circuit-switched network with variable channel sizes such as DTM is well suited to provide real-time services. To avoid the static nature of ordinary circuit-switched networks, DTM uses dynamic allocation of resources among the nodes in the network. Resources are reallocated according to user demands. Many of the new services for broadband networks are either distributive, such as cable TV, or multiparty applications, such as teleconferencing and CSCW. An important feature for broadband networks is therefore to provide means for efficient multicast. Synchronous networks have to provide an asynchronous service to support variable packet lengths. This may be provided by a segmentation and reassembly (SAR) protocol. In DTM, the SAR protocol is simplified by the fact that the DTM network does not reorder or lose data.
Byeong Seog Cho and H. Jonathan Chao, "Fault Tolerance of A Large-Scale Multicast Output Buffered ATM Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: In this paper, the fault detection, fault location, and reconfiguration schemes for a large-scale multicast output buffered ATM switch (MOBAS) are proposed. The architecture of the MOBAS has a regular and uniform structure and, thus, has the advantages of: (1) easy expansion due to the modular structure, (2) high integration density for VLSI implementation, (3) relaxed synchronization for data and clock signals, and (4) building the center switch fabric with a single type of chip. It is difficult to achieve fault tolerance in binary self-routing networks without adding additional switching planes, stages, or switching elements in order to have multiple paths due to their characteristics of a unique routing path between any input and output pair. However, since the MOBAS intrinsically has multiple paths between any input and output, it is inherently robust for faults without need to add any additional switching elements. The fault-tolerance of the MOBAS is shown through the performance analysis of the MOBAS under various fault conditions.
Keywords: ATM Switch; Multicast Switch; Fault Tolerance
Byeong Seog Choe and H. Jonathan Chao, "Performance Analysis of a Large-Scale Multicast Output Buffered ATM Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: We have previously proposed a recursive modular architecture for implementing a large-scale Multicast Output Buffered ATM Switch (MOBAS). Four major functions of designing a multicast switch: cell replication, cell routing, cell contention resolution, and cell addressing, are all performed distributedly in the MOBAS, which allows the switch to grow. The architecture of the MOBAS has a regular and uniform structure and, thus, has the advantages of: (1) easy expansion due to the modular structure, (2) high integration density for VLSI implementation, (3) relaxed synchronization for data and clock signals, and (4) building the center switch fabric with a single type of chip. Multicast Knockout Principle, an extension of Generalized Knockout Principle, is applied to construct the entire switch fabric so as to reduce the hardware complexity (e.g., the number of switch elements and interconnection wires) by almost one order of magnitude. In this paper, we analyze a two-stage MOBAS in its cell loss rate and present some numerical results. We show that a switch that is designed, based on the Multicast Knockout Principle, to meet the performance requirement for unicast calls will also satisfy the performance requirement for multicast calls.
Keywords: ATM Switch; Multicast Switch
Xing Chen, Jeremiah F. Hayes, and M. K. Mehmet-Ali, "Performance Comparison of Two Input Access Methods for a Multicast Switch," IEEE Transactions on Communications, vol. 42, p. 10 pages, May 1994.
Abstract: A comparison of the performance of two input access mechanisms for multicast switching is presented. The first of these, a cyclic-priority input access method, is a derivative of the ring token reservation method which eliminates the unfairness of the ordinary ring token reservations. It has the advantage of being relatively simple and easy to implement. A second approach employs a neural network to resolve output-port conflict. While more difficult to implement, it has a delay-throughput performance advantage over the cyclic-priority approach. The primary performance measurements are the switch throughput and the packet delay. A key assumption is that all copies of the same packet must be switched in the same slot.
Shun Yan Cheung and Akhil Kumar, "Efficient Quorumcast Routing Algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: We study the quorumcasting problem which is a generalization of multicasting. While multicasting consists of sending a message to a select group of m nodes in a system of n nodes, quorumcasting sends a message to any q out of these m nodes. The need to communicate with an arbitrary q-subset of a predefined set arises in many distributed applications, such as distributed synchronization and updating a replicated resource. Two straightforward solutions are to send the message to individual members one at a time until q members have responded and to use multicasting to deliver the message to all members. The former solution will have excessive delay and the latter can cause congestion in nodes and/or in the network. The solutions proposed here use a minimum cost tree spanning a q-subset. By choosing an appropriate set of q nodes, the communications cost can be minimized. We present several heuristics to find low cost solutions for the quorumcast routing problem and evaluate the heuristics by comparing their solutions with exact solutions obtained from enumerating the solution space. The heuristic solutions are also compared with (random) solutions, where the q quorum sites are selected at random, and then the problem is treated like a multicast. The results of our tests show that the heuristics compare favorably with the optimal solutions, and that the random solutions perform rather poorly in comparison with the heuristics.
Keywords: Multicasting; Steiner Tree; Data replication; Quorum; Voting
David X. Chen and Jon W. Mark, "Multicasting in the SCOQ Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: SCOQ, a high performance fast packet switch with Shared Concentration and Output Queueing, as described in [1], supports point-to-point transmissions only. The incorporation of multicast (point-to-multipoint) functions require packet duplications. If the copy network were placed on the feedforward path of the switch, it is not transparent to, and can interfere with, point-to-point switching. By placing the copy network in the feedback position, its operation can be made transparent to the point-to-point information transfer. The copy network incorporated onto the SCOQ switch is non-blocking even without an arbitration or selection network. Contrary to the feedforward approach in which the input buffers must be centrally controlled, with the copy network in the feedback loop, the input buffers all operate independent of each other.
Keywords: Fast packet switch; multicasting; feedback copy network; non-blocking
Peter B. Danzig, "Flow Control for Limited Buffer Multicast," IEEE Transactions on Software Engineering, vol. 20, Jan. 1994.
Abstract: This paper analyzes a multi-round flow control algorithm that attempts to minimize the time required to multicast a message to a group of recipients and receive responses directly from each group member. Such a flow control algorithm may be necessary because the flurry of responses to the multicast can overflow the buffer space of the process that issued the multicast. The condition that each recipient directly respond to the multicast prevents the use of reliable multicast protocols based on software combining trees or negative-acknowledgements. The flow control algorithm analyzed here directs the responding processes to hold their responses for some period of time, called the backoff time, before sending them to the originator. The backoff time depends on the number of recipients that will respond, the originator's available buffer space and buffer service time distribution, and the number of times that the originator is willing to retransmit its message. This paper develops an approximate analysis of the service time distribution of the limited buffer, preemptive queuing process that occurs within the protocol processing layers of a multiprogrammed operating system. It then uses this model to calculate multicast backoff times. The paper reports experimental verification of the accuracy of this service time model and discusses its application to the multicast flow control problem.
Steve Deering, Deborah Estrin, D. Farinacci, Van Jacobson, C. G. Liu, and L. Wei, "An Architecture for Wide-Area Multicast Routing," in SIGCOMM Symposium on Communications Architectures and Protocols, (London, UK), pp. 126-135, Sept. 1994.
Abstract: Existing multicast routing mechanisms were intended for use within regions where a group is widely represented or bandwidth is universally plentifull. When group members, and senders to those group members, are distributed sparsely across a wide area, these schemes are not efficient; data packets or membership report information are occasionally sent over many links that do not lead to receivers or senders, respectively. We have developed a multicast routing architecture that efficiently establishes distribution trees across wide area internets, where many groups will be sparsely represented. Efficiency is measured in terms of the state, control message processing, and data packet processing, required across the entire network in order to deliver data packets to the members of the group. Our Protocol Independent Multicast (PIM) architecture: (a) maintains the traditional IP multicast service model of receiver-initiated membership; (b) can be configured to adapt to different multicast group and network characteristics; (c) is not dependent on a specific unicast routing protocol; and (d) uses soft-state mechanisms to adapt to underlying network conditions and group dynamics. The robustness, flexibility, and scaling properties of this architecture make it well suited to large heterogeneous inter-networks.
Keywords: IP; multicast
Jutta Degener, "Digital speech compression," Dr. Dobb's Journal, Dec. 1994.
Abstract: Jutta provides an overview of GSM 06.10 compression, then presents her implementation of a 32-bit GSM 06.10 coder and decoder written in C that uses the RPE-LTP algorithm.
Keywords: GSM; LPC; audio coding
Peter Danzig, Katia Obraczka, Dante DeLucia, and Naveed Alam, "Massively Replicating Services in Autonomously Managed Wide-Area Internetworks," tech. rep., University of Southern California, Jan. 1994.
Abstract: Current and future Internet services will provide a large, rapidly evolving, highly accessed, yet autonomously managed information space. Internet news, perhaps, is the closest existing precursor to such services. It permits autonomous updates, is replicated at thousands of autonomously managed sites, and manages a large database. It gets its performance through massive replication. This paper proposes a scalable mechanism for replicating wide-area, autonomously managed services. We target replication degrees of tens of thousands of weakly consistent replicas. For efficiency, our mechanism probes the network and computes a good logical topology over which to send updates. For scalability, we organize replicas into hierarchical replication groups, analogous to the Internet's autonomous routing domains. We argue that efficient, massive replication does not have to rely on internet multicast.
James E. (Jed) Donnelley, "WWW page distribution using multicast," Technical memorandum, Nov. 1994.
Abstract: Distribution of WWW pages to large numbers of sites currently presents a performance problem if the pages are simply accessed directly from a server. The problem is that the pages are again and again passing over the same wires making inefficient use of network bandwidth. Various mechanisms have been proposed and some have been implemented to address this inefficiency. This paper discusses utilizing a multicast distribution mechanism to limit such duplication of transmissions. Specifically, some of the technology available in the Internet Multicast Backbone (MBONE [1]) is discussed, limitations to use of the current mbone are pointed out, and mechanisms for extending ``mbone-like'' technology to be useful in this context are suggested. While the specific focus of the present paper is WWW pages (in fact WWW pages for non-real-time ``mass'' media such as magazines), these approaches are applicable to any sort of non-real-time bulk data transfer over Internet. In addition to discussing the performance aspects of multicast use, some aspects of access control and trade-offs of multicast vs. caching are considered.
Keywords: multicast; MBONE; WWW
Hans Eriksson, "MBONE: The multicast backbone," Communications ACM, vol. 37, pp. 54-60, Aug. 1994.
Keywords: multicast; MBONE; Internet; overlay network; multimedia; mrouted; IETF
Inder Gopal and Raphael Rom, "Multicasting to Multiple Groups Over Broadcast Channels," IEEE Transactions on Communications, vol. 42, July 1994.
Abstract: Multicasting is a communication mode in which a given source communicates with a subset of the entire network user population. Previous work in this area concentrated on the multicast problem of a single source that always communicates with the same destination group. In this paper we investigate a more natural case of multicast communication where a single source communicates with several different destination groups. Specifically, we focus on the design and analysis of multicast data link protocols for this environment. Straightforward implementations of such protocols are inappropriate in the case of a large destination population, as a source will have to store a large amount of state information even if it maintains only a single variable per destination. In most typical applications, though the total destination population is large, the number of destinations that any given source is in conversation with, is typically small. We propose a framework for adapting protocols so that memory requirement does not grow with the total destination population but depends upon the number of destinations actually in communication with the source. The savings in memory are achieved by slightly increasing the amount of communication. We address the performance of such a protocol in an environment of a broadcast channel. We analyze several strategies and control techniques and demonstrate the tradeoff between throughput and the amount of memory.
Mark Handley, "Session advertisements and session directories," in Proc. of 31th IETF, (San Jose, California), Dec. 1994. Multiparty Multimedia Session Control WG (MMusic), Talk (f).
Keywords: conference control; sd; directory; CSCW
Annotation: mentions UDP ttl=0 multicast
Mark Handley and Ian Wakeman, "CCCP: conference control channel protocol - a scalable base for building conference control applications," V1.4, Mar. 1994.
Abstract: This paper presents CCCP, a new conference control scheme intended for use in conferences ranging from small, tightly coupled meetings, to extremely large loosely coupled seminars. We describe the requirements of such a scheme, and present a framework for building solutions and for connecting together existing applications. In this paper, we will discuss some of the lessons that we have garnered from previous work involving computer based multimedia conferencing, and use these as a basis for developing an architecture for the next generation of conference control applications, suitable for conferencing over wide area networks. We show that a simple protocol acting over a conference specific communications channel, named the Conference Control Channel or CCC, will perform all tasks within the scope of conference control.
Keywords: conference control; session control; signaling; multimedia; Internet; multicast
Van Jacobson, "Multimedia conferencing on the Internet," in SIGCOMM Symposium on Communications Architectures and Protocols, (London, England), Aug. 1994. Tutorial slides.
Keywords: Internet; MBONE; tutorial; real-time; packet audio; packet video; multicast; sd; vat
John Knight and Steve Guest, "Using Multicast Placement with Late Binding RPC," research memorandum, Sept. 1994.
Abstract: This paper describes the implementation and use of a prototype multicast late-binding RPC (LbPRC) system. The system provides a mechanism for exporting arbitrary code and data across a network to multiple hosts for evaluation. This provides a near optimum total execution time for the application without requirering continual monitoring and estimation of the state of the hosts and the intervening network. The impact of sending the same code and data to a group of remote hosts is minimized by using multicast Internet Protocol (IP) communications for the outward leg of the same transaction.
Keywords: late-binding RPC; multicast IP
J. Kay and R. J. Kummerfeld, "Customization and delivery of multimedia information," in Proc. of Multicomm'94, (Vancouver, Canada), Nov. 1994.
Abstract: Current research into architectures for delivery of multimedia (video, audio and data) to the home have concentrated on real-time video-on-demand. This paper describes a project that treats multimedia objects as messages and uses a store-and-multicast delivery system for multimedia objects. The system uses a directory service to store descriptions of objects. These descriptions are then processed by filters that use a model of the user of the system to discover objects of interest. An Individualised News Service then takes the filtered object descriptions and constructs a composite news program for presentation to the user. The actual objects (movies, TV shows, news programmes, radio shows) are then transferred to the user system using a multicast message delivery protocol.
Keywords: multimedia; multicast; store-and-forward; messaging; WWW
Bongtae Kim, Arne A. Nilsson, and Harry G. Perros, "Throughput analysis of stop-and-wait retransmission schemes for k-reliable multicast," in Interop Paris, (Paris, France), pp. MI-8, Oct. 1994.
Abstract: We propose a scheme in which a message is considered to be correctly transmitted when a predefined number of acknowledgements are received.
Keywords: reliable multicast; transport protocol
Per Lindgren and Christer Bohm, "Fast connection establishment in the DTM gigabit network," in Proc. 5th High Performance Networking (HPN), (Grenoble, France), pp. 283-294, IFIP, June 1994.
Abstract: Dynamic synchronous Transfer Mode (DTM) is a new protocol suite based on synchronous fast circuit switching. The DTM network is based on bandwidth reservation and supports dynamic reallocation of bandwidth. It is designed to support real-time multimedia applications and high-speed computer communication. DTM uses a novel medium-access technique and provides a multicast connection-oriented service. In this paper, the connection establishment in the DTM network is discussed and a scheme for fast connection establishment is presented. The scheme allows for fast set-up of channels which results in an efficient usage of the network's bandwidth and a short access delay for the user. Buffer handling and memory management implementations at a host interface supporting this scheme are also presented.
F. C. Liaw, "A straw man proposal for ATM group multicast routing and signaling protocol: Architecture overview," Contribution 94-0995, ATM Forum, 1994.
Keywords: ATM; multicast
Tsern Huei Lee and Shun Jee Liu, "Performance Analysis of a Large Scale ATM Switch with Input and Output Buffers," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: The maximum throughput of a single-stage nonblocking input-queued switch such as the sort-banyan network is shown to be 0.586 [2][7] under the uniform traffic model. It can be increased to 0.88 or 0.97 respectively if the switch is speeded up by a factor of 2 or 3 [8]. Hui and Lee [9] showed that, for a large scale three-stage switch built with sort-banyan switch modules, the maximum throughput reduces to 0.458. The analysis was performed based on the assumption that the number of middle-stage switch modules is equal to the number of input/output links of a switch module. In this paper, we study the effect of increasing the number of middle-stage switch modules and speeding up the switch. Numerical results are obtained and verified by computer simulations for various combinations. For example, with a speedup factor of 2, the maximum throughput can be improved to 0.85 if the number of middle-stage switch modules is doubled.
Keywords: ATM; multicast; switch
Xiaola Lin, Philip K. McKinley, and Lionel M. Ni, "Deadlock-Free Multicast Wormhole Routing in 2D Mesh Multicomputers," IEEE Transactions on Parallel and Distributed Systems, vol. 5, Feb. 1994.
Abstract: Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for two-dimensional (2D) mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multi-path, and fixed-path algorithms.
Kurt Lidl, Josh Osborne, and Joseph Malcolm, "Drinking from the firehose: multicast USENET news," in Proc. of Usenix Winter Conference, (San Francisco, California), pp. 33-45, Jan. 1994.
Abstract: News transport and spooling systems of the last several years have concentrated on decreasing the resource load on news servers. One beneficial side effect has been the average decrease in time that a news system spends on a given article. This paper describes a novel USENET news transport protocol, which we call Muse. The two major motivations behind Muse are to reduce the average propagation delays of articles on USENET and to further reduce the resource load on a centralized news server. Muse runs on top of the experimental Internet multicast backbone, commonly referred to as the Mbone. Major design and implementation issues are discussed. Security concerns of multicast news are discussed and our solution is examined. The problems of scaling news distribution to thousands of hosts are also addressed.
Keywords: USENET; network news; multicast; security; scaling
T. Moors, N. Clarke, and G. Mercankosk, "Implementing traffic shaping," in IEEE 19th Conference on local computer networks, Oct. 1994.
Abstract: Traffic shaping is important in ATM networks, especially those that are interconnected or provide service guarantees. We examine what shaping may be considered ideal, and what is attainable under the constraints of transmission systems and cost. We justify the use of FCFS multiplexing of multiple single-stream shaper outputs as a performance reference for multi-stream shapers, but also point out some of its deficienties. Shaper implementations in which transmissions are sheduled ojn cell arrivals, emissions, and transmissions are examined and compared both quantitativly and through simulation. We identify the problem of shaping cells that must conform to multiple traffic constraints (e.g. when the rate of a multicast connection must be adapted to suit multiple links) and examine implementations to achieve this. Shaping in which inevitable Cell Delay Variation is intentionally distributed inequitable amongst connections (to assist CDV-intolerant connections) is also examined.
Keywords: ATM; multiplexing; FCFS; Quality of service
J. Moy, "Multicast extensions to OSPF," Request for Comments (Proposed Standard) RFC 1584, Internet Engineering Task Force, Mar. 1994.
Abstract: This memo documents enhancements to the OSPF protocol enabling the routing of IP multicast datagrams. In this proposal, an IP multicast packet is routed based both on the packet's source and its multicast destination (commonly referred to as source/destination routing). As it is routed, the multicast packet follows a shortest path to each multicast destination. During packet forwarding, any commonality of paths is exploited; when multiple hosts belong to a single multicast group, a multicast packet will be replicated only when the paths to the separate hosts diverge. OSPF, a link-state routing protocol, provides a database describing the Autonomous System's topology. A new OSPF link state advertisement is added describing the location of multicast destinations. A multicast packet's path is then calculated by building a pruned shortest-path tree rooted at the packet's IP source. These trees are built on demand, and the results of the calculation are cached for use by subsequent packets. The multicast extensions are built on top of OSPF Version 2. The extensions have been implemented so that a multicast routing capability can be introduced piecemeal into an OSPF Version 2 routing domain. Some of the OSPF Version 2 routers may run the multicast extensions, while others may continue to be restricted to the forwarding of regular IP traffic (unicasts). Please send comments to mospf@gated.cornell.edu.
John Moy, "Multicast routing extensions for OSPF," Communications ACM, vol. 37, pp. 61-66, 114, Aug. 1994.
Keywords: routing; OSPF; multicast; Internet; DVMRP; intra-domain routing; link-state
Danny J. Mitzel and Scott Shenker, "Asymptotic Resource Consumption in Multicast Reservation Styles," in SIGCOMM Symposium on Communications Architectures and Protocols, (London, UK), pp. 226-233, Sept. 1994.
Abstract: The goal of network design is to meet the needs of resident applications in an efficient manner. Adding real-time service and point-to-multipoint multicast routing to the Internet's traditional point-to-point best effort service model will greatly increase the Internet's efficiency in handling point-to-multipoint real-time applications. Recently, the RSVP resource reservation protocol has introduced the concept of ``reservation styles'', which control how reservations are aggregated in multipoint-to-multipoint real-time applications. In this paper, which is an extension of [9], we analytically evaluate the efficiency gains offered by this new paradigm on three simple network topologies: linear, m-tree and star. We compare the resource utilization of more traditional reservation approaches to the RSVP reservation styles in the asymptotic limit of large multipoint applications. We find that in several cases the efficiency improvements scale linearly in the number of hosts.
Keywords: RSVP; resource reservation; Internet; scaling; resource sharing
Ciro A. Noronha~Jr., "Optimum Routing of Multicast Streams," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: We show that the problem of optimally routing multicast streams can be formulated as an integer programming problem. We propose an efficient solution technique, composed of two parts: (i) an extension to the decomposition principle, to speed up the linear relaxation of the problem, and (ii) enhanced value-fixing rules, to prune the search space for the integer problem. We characterize the reduction in run time gained using these techniques. Finally, we compare the run times for the optimum multicast routing algorithm and for existing heuristic algorithms.
Jr. Noronha, Ciro~A., "Routing of Video/Audio Streams In Packet-Switched Networks," Thesis and Technical Report CSL-TR-94-653, Stanford University, Computer Systems Laboratory, Dec. 1994.
Abstract: The transport of multimedia streams in computer communication networks raises issues at all layers of the OSI model. This thesis considers some of the issues related to supporting multimedia streams at the network layer; in particular, the issue of appropriate routing algorithms. New routing algorithms, capable of efficiently meeting multimedia requirements, are needed. We formulate the optimum multipoint stream routing problem as a linear integer programming problem and propose an efficient solution technique. We show that the proposed solution technique significantly decreases the time to compute the solution, when compared to traditional methods. We use the optimum multicast stream routing problem as a benchmark to characterize the performance of existing heuristic algorithms under realistic network and traffic scenarios, and derive guidelines for using their usage and for upgrading the network capacity. We also consider the problem of routing multimedia streams in a Wavelength-Division Multiplexing (WDM) optical network, which has an additional degree of freedom over traditional networks - its topology can be changed by the routing algorithm to create routes as needed, by tuning optical transmitters and/or receivers. We show that the optimum reconfiguration and routing problem can formulated as a linear integer programming problem. Since this is a complex solution, we also propose a set of heuristic algorithms, both for unicast and multicast routing. We evaluate the performance of the proposed heuristics and derive guidelines for their usage.
Jörg Ott, Carsten Bormann, and Ute Bormann, "Service interoperability," in Proc. of 31th IETF, (San Jose, California), Dec. 1994. Multiparty Multimedia Session Control WG (MMusic), Talk (e).
Keywords: conference control; survey; CSCW
Annotation: mentions UDP ttl=0 multicast
Katia Obraczka, Massively Replicating Services in Wide-Area Internetworks. PhD thesis, Computer Science Department, University of Southern California, Los Angeles, California, Dec. 1994.
Abstract: Existing and future Internet information services will provide large, rapidly evolving, highly accessed, yet autonomously managed information spaces. Internet news, perhaps, is the closest existing precursor to such services. It permits asynchronous updates, is replicated at thousands of autonomously managed sites, manages a large database, yet presents adequate response time. It gets its performance through massive replication. Other Internet services, such as archie, and WWW/Mosaic must massively replicate their data to deliver reasonable performance. The problem of replicating information that can be partitioned into autonomously managed subspaces has well-known solutions. Naming services such as the Domain Name Service (DNS) and Grapevine use administrative boundaries to partition their hierarchical name space into domains. These domains need only be replicated in a handful of services for adequate performance. On the other hand, efficient massive replication of wide-area, flat, yet autonomously managed data is yet to be demonstrated, since existing replication algorithms do not address the scale and autonomy of today's internetworks. They either ignore network topology issues entirely, or rely on system administrators to hand-configure replica topologies over which updates travel. Lampson's widely cited Global Name Service (GNS) propagates updates over manually configured topologies. However, the complexity of manually configuring fault-tolerant update topologies that use the underlying physical network efficiently increases with the scale of today's internetworks. Furthermore, GNS-like replication mechanisms also manage single, flat groups of replicas. While this is appropriate for applications with 20 to 30 replicas that operate within single administrative boundaries, it is unrealistic for wide-area, massively replicated services whose replicas spread throughout the Internet's thousands of administrative domains. This research investigates scalable replication mechanisms for wide-area, autonomously managed services. We propose a new architecture that extends existing replication mechanisms to explicitly address scalability and autonomy. We target replication degrees of thousands or even tens of thousands of weakly-consistent replicas. Imitating the Internet's administrative domain routing hierarchy, the proposed architecture organizes replicas into multiple replication groups. Organizing replicas into multiple groups limits the size of the consistency state each replica keeps. It also preserves autonomy, since it insulates replication groups from other groups' administrative decisions. We argue that efficient replication algorithms keep replicas weakly consistent by flooding data between them. Our architecture automatically builds a logical update flooding topology over which replicas propagate updates to other replicas in their group. Replicas in a group estimate the underlying physical topology. Using the estimated network topology, we compute a logical update topology that is kconnected for resilience, tries to use the physical network efficiently, and yet restricts update propagation delays. Replication groups compute and adopt a new update topology every time they detect changes in group membership and network topology. We describe our architecture in detail and its implementation as a hierarchical, network cognizant replication tool, which we implemented as part of the Harvest resource discovery system. Through simulations, we investigate the benefits of using hierarchical replication groups and distributing updates over the logical update topologies our architecture computes. We present the results from the wide-area experiments we conducted to evaluate our network topology estimation strategy. We also present our logical topology calculation algorithm in detail, and the results obtained when running our algorithm over randomly generated topologies. Finally, we explore the use of internet multicast as the underlying update propagation mechanism. We argue that since having a single multicast group with all replicas of a service will not scale, each replication group can be mapped to a multicast group. Through corner replicas, updates in one group make their way to all groups. Lampson's Global Name Service has been widely accepted as the solution to the problem of replicating wide-area, distributed, weakly-consistent applications. However, almost 10 years ago, when Lampson wrote '... The system I have in mind is a large one, large enough to encompass all the computers in the world and all the people that use them...', he did not anticipate that the Internet would grow as fast as it did. The main contribution of this dissertation is to make GNS-like services work in today's exponentially-growing, autonomously-managed internetworks.
Keywords: Harvest; WWW; directory services
Sridhar Pingali, Don Towsley, and James F. Kurose, "A comparison of sender-initiated and receiver-initiated reliable multicast protocols," in Proceedings of the ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, 1994.
Abstract: Sender-initiated multicast protocols, based on the use of positive acknowledgments (ACKs), lead to an ACK implosion problem at the sender as the number of receivers increases Briefly, the ACK implosion problem refers to the significant overhead incurred by the sending host due to the processing of ACKs from each receiver. A potential solution to this problem is to shift the burden of providing reliable data transfer to the receivers -thus resulting in a receiver-initiated multicast error control protocol based on the use of negative acknowledgments -NAKs-. In this paper we determine the maximum throughputs of the sending and receiving hosts for generic sender-initiated and receiver-initiated protocols. We show that the receiver-initiated error control protocols provide substantially higher than their sender-initiated counterparts. We further demonstrate that the introduction of random delays prior to generating NAKs coupled with the multicasting of NAKs to all receivers has the potential for an additional substantial increase in the throughput of receiver-initiated error control protocols over sender-initiated protocols.
Keywords: sender-initiated multicast protocols; receiver-initiated multicast; negative acknowledgment; positive acknowledgment; reliable multicast
George N. Rouskas and Mostafa H. Ammar, "Multi-Destination Communication Over Single-Hop Lightwave WDM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), June 1994.
Abstract: We address the open issue of providing efficient mechanisms for multi-destination communication over one class of lightwave WDM architectures, namely, single-hop networks. We suggest, analyze, and optimize several alternative approaches for broadcast/multicast. One of our major contributions is the development of a suite of adaptive multicast protocols which have very good performance, are very simple to implement, and are insensitive to propagation delays.
Terunao Soneoka and Toshihide Ibaraki, "Logically Instantaneous Message Passing in Asynchronous Distributed Systems," IEEE Transactions on Computers, vol. 43, May 1994.
Abstract: Asynchrony (due to unknown message transmission delay) complicates the design of protocols for distributed systems. To simplify the protocol design task, therefore, this paper proposes an interprocess (point-to-point) communication mechanism that has the characteristic of instantaneous message passing. This paper first establishes a hierarchy among synchronization properties, which shows that to ensure the logically instantaneous message passing property it is not always necessary to use a rendezvous mechanism. Next, this paper proposes a solution to the logically instantaneous message passing problem that is more efficient than Bagrodia's rendezvous and Goldman's logically synchronous multicast in the point-to-point ("single-cast") setting. This algorithm has the following properties. 1) It is applicable without deadlock to the partner model in which each process acts as both client and server. 2) It requires three control messages to send an application message, which is shown to be quasioptimum message complexity (i.e., at most one larger than the lower bound). 3) Its worst-case response time from a send request to the occurrence of the corresponding send event is 2k\Delta (seconds), where k is the maximum number of interfering send requests and \Delta (seconds) is an assumed upper bound on interprocess communication delay. Furthermore, two modified algorithms are proposed: one for reducing the number of control messages required for an application message, and the other for attaining a shorter average response time by using a randomization technique.
Rajesh Talpade and Mostafar H. Ammar, "Single connection emulation (SCE): an architecture for providing a reliable multicast transport service," Technical Report GIT-CC-94-47, Georgia Institute of Technology, Atlanta, Georgia, Apr. 1995. to be published in Proceedings of the International Conference on Distributed Computer Systems (DCS).
Abstract: We present a novel architecture for providing a reliable multicast transport service over existing protocol stacks. These protocol stacks ordinarily support reliable unicast transport layer connections over a network layer which is capable of providing an unreliable multicasting service. We propose the addition of a new single connection emulation (SCE) sublayer between the unicast transport layer and the multicast network layer. This added layer mimics the single destination network layer interface to the transport layer and interfaces with the multicast network layer to provide the necessary multicast functionality. The new architecture also enables interactions between applications and the SCE, thus allowing the applications to control the semantics of the reliable multicast connection. We discuss the design issues that need to be considered when such a sublayer is to be introduced. We also discuss an implementation of this new approach using the TCP/IP protocol stack, and present some preliminary experimental results.
Keywords: reliable multicast; TCP; MBONE; transport protocol
Annotation: Uses standard TCP (positive) acknowledgements and aggregates them before passing them off to the TCP protocol engine. Data and retransmissions are multicast.
A. G. Waters, "A New Heuristic for ATM Multicast Routing," in Proc. of 2nd IFIP Workshop on Performance Modeling and Evaluation of ATM Networks, Aug. 1994.
Keywords: ATM; multicast; routing
Ian Wakeman and Jon Crowcroft, "Multicast congestion control in the distribution of variable bit rate video," Computer Science Department, University College London, Jan. 1994.
Abstract: This is a very drafty paper describing a mechanism for scalable congestion control of multicast continuous media streams. We attempt to define a scalable mechanism that will do for multicast real-time traffic what Van Jacobson's slow start did for TCP. The mechanism separates the congestion signal from the congestion control algorithm, so as to cope with heterogeneous networks. In addition it uses a novel probing mechanism (at least, no-one has yet pointed me to anything that uses a similar mechanism) to solicit responses in a scalable manner and to estimate the number of receivers, and uses this estimate to correctly fix the mechanism for estimating the maximum round-trip time. It discusses the problems with fixing a single congestion control mechanism for multicast real-time communication, and punts the problem upwards as an application and policy problem. Finally, it suggests that this mechanism would sit well as an option in the currently proposed RTP protocol.
Keywords: RTP; multimedia; congestion control; population estimation; random polling; packet video; packet voice; multicast; quality of service
Annotation: Uses a defined-length match between a randomly generated sender number and a similar receiver number to solicit responses without acknowledgement implosion.
Liming Wei and Deborah Estrin, "A comparison of multicast trees and algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Toronto, Canada), IEEE, June 1994.
Abstract: Multicast trees can be shared across sources or may be source-specific. Inspired by recent interests in using shared trees for interdomain multicasting, this paper investigates the trade-offs among different algorithms and tree types. Because of the dynamic nature of graphs, only worst case delay bounds can be calculated using analytical methods. We present simulation results over random graphs that demonstrate the performance of these trees, under different circumstances. We evaluate the performance in terms of path length, link cost, and traffic concentrations.
Keywords: multicast; routing; graphs; random graphs; Steiner trees; reverse path forwarding; Internet
Brian Whetten, Simon Kaplan, and Todd Montgomery, "A high performance totally ordered multicast protocol," research memorandum, Aug. 1994.
Abstract: This paper presents a Reliable Multicast Protocol (RMP). RMP provides a totally ordered, reliable, atomic multicast service on top of an unreliable multicast datagram service such as IP Multicasting. RMP is fully and symmetrically distributed so that no site bears an undue portion of the communication load. RMP provides a wide range of guarantees, from unreliable delivery to totally ordered delivery, to K-resilient, majority resilient, and totally resilient atomic delivery. Thes QOS guarantees are selectable an a per packet basis. RMP provides many communication options, including virtual synchrony, a publisher/subscriber model of message delivery, a client/derver model of delivery, an implicit naming service, mutually exclusive handlers for messages, and mutually exclusive locks. It has commonly been held that a large performance penalty must be paid in order to implement total ordering - RMP discounts this. On SparcStation10's on a 1250 KB/sec Ethernet, RMP provides totally ordered packet delivery to one destination at 842 KB/sec throughput and with 3.1 ms packet latency. The performance stays roughly constant independent of the number of destinations. For two or more destinations on a LAN, RMP provides higher throughput than any protocol that does not use multicast or broadcast.
Keywords: Congestion control; multicast; reliable multicast; ordering; transport protocol
Raj Yavatkar and Leelanivas Manoj, "End-to-End approach to large-scale multimedia dissemination," Computer Communications, vol. 17, pp. 205-217, Mar. 1994.
Abstract: We address the problem of realizing large scale dissemination services across a high-speed wide area network. Examples of such dissemination services include media storage services and on-demand multimedia services such as accessing CATV or an on-line video rental store across a network. Unlike the conventional request-response paradigm, such applications involve a single source sending delay-sensitive information to a large number of users scattered across high-speed wide area network. Communication requirements of such applications are distinct from those based on conventional client-server interactions because the multimedia information demands a certain Quality of Service guarantees in terms of delay constraints and error tolerance. In this paper we address some of the research issues that must be resolved before we can realize large scale dimension services across a high-speed WAN. In particular we argue for an end-to-end approach in which transport and upper-layer protocol cooperate to provide a large scale dimension service using a best effort multicast delivery service provided by the under lying network protocol. Under an end-to-end approach, a transport protocol takes into account application level error recovery semantics in its flow and error control strategies to ensure delivery of multimedia information within the QoS constraints of a given distributed multimedia application. We have designed QMTP a new multicast transport protocol that provides a simplex rate controlled quasi reliable multicast transport mechanism for large scale dissemination of multimedia information. This paper describes our goals, the research issues that must be solved, our information dissemination model, QMTP flow and error control policies, and results of our performance evaluation.
Keywords: multimedia; WAN; on-demand services; QMTP
Wen D. Zhong and Yoshikuni Onozato, "Modular Architectures for Large-scale Multicast ATM Switching Networks: A Review," IEEE Communications Magazine (submitted), p. 10 pages, 1994.
Abstract: A recently proposed multicast ATM switching network provides increased throughput, less delay, and lower cell loss probability. It also performs better in terms of cell sequencing, adaptability to multichannel bandwidth allocation environments, modular growth. The architectures of a point-to-point switching network and two different copy networks are reviewed. These architectures increase the switch resource utilization and offer 100% throughput, irrespective of traffic characteristics. The point-to-point switch inherently accomplishes multichannel bandwidth allocation without any additional channel allocation hardware or algorithms. The copy networks offer the following features: (i) the maximum number of copies that can be generated is not limited by the hardware size of the copy networks, (ii) the memory needed for table lookup of address translation need not be prohibitively large in very large multicast switch structures, (iii) all links and buffers are shared, and (iv) cell sequence is preserved. Copy generation can be categorized as either copy-replication by recursive generation or copy-replication by output reservation. Reviewing our recent results, this paper comprehensively explains the design philosophy of copy-generation and point-to-point switching networks, which can be concatenated to produce very large modular multicast switches for future BISDN.