Hierarchical Reliable Multicast: Performance Analysis and Optimal Placement of Proxies

This paper studies the use of multicast together with proxy nodes for reliably disseminating data from a single source to a large number of receivers. In order to achieve reliability, data must be retransmitted in case of loss either by the source or by special network nodes, called proxies. Each proxy is responsible for reliably delivering the data to a subgroup it is assigned. The multicast tree is partitioned into subgroups that form a hierarchy rooted at the source, hence the term hierarchical reliable multicast. The performance of this approach strongly depends on the topology and the loss characteristics of the underlying tree and the location of proxies. In the first part of the paper, we study the processing and bandwidth performance of such a reliable multicast dissemination given the tree and the placement of proxies. In the second part of the paper, we develop dynamic programming algorithms that give a placement of a fixed number of proxies on an arbitrary tree that minimizes the bandwidth used for reliable transfer. The first algorithm provides an optimal solution to the multicast proxies location problem in polynomial time, in the number of nodes and proxies. The second is an approximation algorithm that gives a solution with cost within a chosen precision from the optimal, in an improved running time. An optimal and an approximate solution are also provided for the proxies location problem if unicast is used for transmissions. Applications of this dynamic programming approach to related problems are discussed.     

Performance evaluation of 10Base-T and 100Base-T Ethernets carryingmultimedia traffic

The performance of 10Base-T and 100Base-T Ethernet segments carrying audio/video traffic is presented. End-to-end delay requirements suitable for a wide range of multimedia applications are considered (ranging from 20-500 ms). Given the specific nature of the network considered and the maximum latency requirement, some data is lost. Data loss at the receiver causes quality degradations in the displayed video in the form of discontinuities, referred to as glitches. We define various quantities characterizing the glitches, namely, the total amount of information lost in glitches, their duration, and the rate at which glitches occur. We study these quantities for various network and traffic scenarios, using a computer simulation model driven by real video traffic generated by encoding video sequences. We also determine the maximum number of video streams that can be supported for given maximum delay requirement and glitch rate. We consider various types of video contents (video conferencing, motion pictures, commercials), two encoding schemes (H.261 and MPEG-1), and two encoder control schemes [constant bit rate (CBR) and constant-quality variable bit rate (CQ-VBR)] and compare their results. Furthermore, we consider scenarios with mixtures of video and data traffic (with various degrees of burstiness), and determine the effect of one traffic type over the other     

Analysis of a Two-Hop Centralized Packet Radio Network--Part II: Carrier Sense Multiple Access

We continue in this paper our study of two-hop centralized packet radio networks in view of understanding the behavior of these systems. Traffic originates at terminals, is destined to a central station, and requires for its transport the relaying of packets by store-and-forward repeaters. We consider here that all devices employ the nonpersistent carrier sense multiple-access mode. System capacity and through-put-delay tradeoffs are derived and compared to those obtained for slotted ALOHA in Part I [l].     

Multiaccess Protocols in Packet Communication Systems

The need for multiaccess protocols arises whenever a resource is shared by many independent contending users. Two major factors contribute to such a situation: the need to share expensive resources in order to achieve their efficient utilization, or the need to provide a high degree of connectivity for communication among independent subscribers (or both). In data transmission systems, the communication bandwidth is often the prime resource, and it is with respect to this resource that we view multiaccess protocols here. We give in this paper a unified presentation of the various multiaccess techniques which we group into five categories: 1) fixed assignment techniques, 2) random access techniques, 3) centrally controlled demand assignment techniques, 4) demand assignment techniques with distributed control, and 5) mixed strategies. We discuss their applicability to different enivironments, namely, satellite channels, local area communication networks and multihop store-and-forward broadcast networks, and their applicability to different types of data traffic, namely stream traffic and bursty traffic. We also present the performance of many of the multiaccess protocols in terms of bandwidth utilization and message delay.     

Performance of Unidirectional Broadcast Local Area Networks: Expressnet and Fasnet

Local area communication networks based on packet broadcasting techniques provide simple architectures and flexible and efficient operation. Unidirectional broadcast systems use a unidirectional transmission medium which, due to their physical ordering on the medium, users can access according to some efficient distributed conflict-free round-robin algorithm. Two systems of this type have been presented in the literature: Expressnet and Fasnet. In this paper we briefly describe these two. We identify three different service disciplines achievable by these systems and discuss and compare the performance of each. These systems overcome some of the performance limitations of existing random-access schemes, making them particularly well suited to the high bandwidth requirements Of an integrated services digital local network.     

Analysis of a Two-Hop Centralized Packet Radio Network--Part I: Slotted ALOHA

The design of packet radio systems involves a large number of design variables that interact in a very complex fashion. As this design problem in its general form is quite complex, a viable approach is to analyze some simple but typical configurations in an attempt to understand the behavior of these systems. In this paper, a two-hop centralized configuration is considered in which traffic originates at terminals, is destined to a central station, and requires for its transport the relaying of packets by store-and-forward repeaters. The through-put-delay performance is derived, and its dependence on such key system variables as the network topology, the transmission protocol, and the repeaters' storage capacities, is given. In this part, devices are assumed to be utilizing the slotted ALOHA access mode. Carrier sense multiple access is treated in Part II of this series [1].     

Packet Switching in Radio Channels: Part IV--Stability Considerations and Dynamic Control in Carrier Sense Multiple Access

In two companion papers a method for multiplexing a population of terminals communicating with a central station over a packet-switched radio channel was introduced; this method is known as Carrier Sense Multiple Access (CSMA). CSMA, as with ALOHA multiaccess broadcast channels, has the unfortunate property that the throughput falls to zero as the channel load increases beyond a critical value. The dynamic behavior and stability of slotted ALOHA channels have been studied extensively and have led to a definition of stability. In this paper, similar techniques are used to analyze CSMA, which is shown to have a behavior not unlike that of ALOHA. However, contrary to ALOHA channels where steady-state performance is badly degraded when true stability is to be guaranteed, hence requiring dynamic control, we find that CSMA provides excellent stable performance even with as large a population as 1000 terminals. Furthermore, we study a simple adaptive retransmission control procedure which provides a significantly improved channel performance which is insensitive to the population size.     

Packet Voice on a Local Area Network with Round Robin Service

In this paper, we propose a combined voice/data protocol suitable for multiple access broadcast networks that provide round robin service to the stations. Such networks are well suited to the integration of voice and data since they guarantee bounded delay and provide high utilization even for high bandwidth channels. Using one such network proposal-namely Expressnet-as a representative scheme, we examine the characteristics of the service that voice traffic experiences under the voice/data protocol. We show that the access protocol is able to utilize the channel efficiently to support a large population of voice sources while maintaining low packet delay and guaranteeing some prespecified minimum bandwidth for data traffic. In addition, we show the advantages of silence suppression, i.e., discarding speech that constitutes silent periods, and we examine the cost of overloading the network in terms of the amount of speech discarded.     

Throughput analysis of a timer controlled token passing protocolunder heavy load

An analysis is presented of the throughput performance of some recently proposed token-passing local area network (LAN) protocols under a heavy load assumption. The IEEE 802.4 token bus standard which uses a cycle-dependent timing mechanism to control station access to the channel, is studied. It is shown that the cycle-dependent timing mechanism limits the token circulation times properly. Moreover, priority among different access classes is being implemented. Analytic results for computations of throughputs and cycle lengths are derived. These results provide insights into the cycle-dependent timing mechanism and also guidelines for design. Using the results derived, examples concerning the throughput behavior under different heavy load configurations, the sensitivity to parameters, system optimization with delay and bandwidth constraints, and comparison with the other integrated access schemes are studied