Collision resolution algorithms for a time-constrained multiaccesschannel

Collision resolution algorithms (CRAs) for the ternary feedback multiple access channel with time constraints are considered. The authors wish to maximize the number of packets successfully transmitted within a fixed deadline K after their arrival for transmission. Packet arrivals are assumed to be Poisson. A nonnested CRA is described and its performance is compared with a nested CRA for values of K ⩽4     

Smoothing, statistical multiplexing, and call admission control forstored video

Variable bit-rate (VBR) compressed video is known to exhibit significant, multiple-time-scale rate variability. A number of researchers have considered transmitting stored video from server to a client using smoothing algorithms to reduce this rate variability. These algorithms exploit client buffering capabilities and determine a “smooth” rate transmission schedule, while ensuring that a client buffer neither overflows nor underflows. We investigate how video smoothing impacts the statistical multiplexing gains available with such traffic, and we show that a significant amount of statistical multiplexing gains can still be achieved. We then examine the implication of these results on network resource management and call admission control when transmitting smoothed stored video using VBR service with statistical quality-of-service (QoS) guarantees. Specifically, we present a uniform call admission control scheme based on a Chernoff bound method that uses a simple, novel traffic model requiring only a few parameters. This scheme provides an easy and flexible mechanism for supporting multiple VBR service classes with different QoS requirements. We evaluate the efficacy of the call admission control scheme over a set of MPEG-1 coded video tracts     

Sample path methods in the control of queues

Sample path methods are now among the most used techniques in the control of queueing systems. However, due to the lack of mathematical formalism, they may appear to be non-rigorous and even sometimes mysterious. The goal of this paper is threefold: to provide a general mathematical setting, to survey the most popular sample path methods including forward induction, backward induction and interchange arguments, and to illustrate our approach through the study of a number of classical scheduling and routing optimization problems arising in queueing theory.Z. Liu was supported in part by the CEC DG XIII under the ESPRIT BRA grants QMIPS.P. Nain was supported in part by NSF under grant NCR-9116183 and by the CEC DG XIII under the ESPRIT BRA grants QMIPS.D. Towsley was supported in part by NSF under grant NCR-9116183.     

Effects of service disciplines inG/GI/s queueing systems

Transient extremal properties of some service disciplines are established in theG/GI/s queueing system for the minimization and maximization of the expectations of the Schur convex functions, convex symmetric functions and the sums of convex functions of the waiting times, response times, lag times and latenesses. When resequencing is required in the system, the FCFS and LCFS disciplines are shown to minimize and maximize, respectively, the expectations of any increasing functions of the end-to-end delays. All of these results are presented in terms of stochastic orderings. The paper concludes with extensions of the results to the stationary regime and to tandem as well as general queueing networks.This work was supported in part by the National Science Foundation under grant ASC 88-8802764.The work of this author was also partially supported by CEC DG-XIII under the ESPRIT-BRA grant QMIPS.     

Stack algorithms for random multiple-access networks in thepresence of asymmetric feedback

The operation of stack splitting random-access protocols in multiaccess networks in which individual stations may receive asymmetric feedback from the channel (i.e. different stations may observe different, possibly erroneous, outcomes on the channel) is examined. Several possible modifications to the basic stack algorithm are proposed for such environments, and the performances of the various alternatives are reviewed. An approximate Markov chain model is developed to analytically study the time delay versus throughput performance of the various alternatives, and the analytic results are validated through simulation. Representative performance results are given for the alternative stack algorithms. It is found that those algorithms which tend to treat the receipt of corrupted feedback by a station as a collision show superior performance for throughput values greater than approximately 0.2, whereas, at low throughput values, there is relatively little difference between the performances of the various approaches studied. It was noted during the simulation studies that, with an error rate of up to 5%, the algorithms remained stable up to an arrival rate of approximately 0.3 or higher     

Statistical analysis of the generalized processor sharingscheduling discipline

We develop bounds on the individual session backlog and delay distribution under the generalized processor sharing (GPS) scheduling discipline. This work is motivated by, and is an extension of, Parekh and Gallager's (see IEEE/ACM Trans. Networking, vol.1, no.6, p.344-357, 1993, and vol. 2, no.4, p.137-150, 1994) deterministic study of the GPS scheduling discipline with leaky-bucket token controlled sessions. Using the exponentially bounded burstiness (EBB) process model introduced by Yaron and Sidi (see IEEE/ACM Trans. Networking, vol.1, p.372-385, 1993) as a source traffic characterization, we establish results that extend the deterministic study of GPS. For a single GPS server in isolation, we present statistical bounds on the distributions of backlog and delay for each session. In the network setting, we show that networks belonging to a broad class of GPS assignments, the so-called consistent relative session treatment (CRST) GPS assignments, are stable in a stochastic sense. In particular, we establish simple bounds on the distribution of backlog and delay for each session in a rate proportional processor sharing (RPPS) GPS network with arbitrary topology     

Optimization-based congestion control for multicast communications

This article outlines an approach for multicast congestion control based on an economic model that has been successfully applied to unicast congestion control. In this model, congestion signals are interpreted as prices and congestion-controlled sessions as utility maximizing agents. A naive extension of the unicast model fails to achieve a reasonable balance between providing the incentives necessary to promote the use of multicast and ensuring that multicast sessions do not interact too aggressively with unicast sessions. We extend the model by introducing a rational definition of multicast utility. The revised model provides a basis for multicast congestion control protocols that provide incentives to use multicast but are necessarily unfair to unicast traffic. We show, however, that the degree of unfairness can be controlled by appropriately setting a design parameter with a limiting case of strict fairness     

Performance comparison of error control schemes in high-speedcomputer communication networks

The authors examine the performance of two different approaches for handling the loss and/or corruption of messages as they are transmitted between two end users in a high-speed network. In the link-by-link approach, two adjacent nodes in an end-to-end path locally detect and recover from message loss or corruption along their joining link. In the end-to-end approach, recovery is done solely on the basis of a single end-to-end protocol. The authors develop analytic performance models, validated with simulation, for comparing the performance of these two approaches. The authors find that for the range of network parameters of practical interest, an end-to-end approach towards error control is superior to a link-by-link approach, even under assumptions that would overly favor the link-by-link approach, while at the same time requiring fewer network resources (e.g. buffers, computation time) than the link-by-link approach. The performance differences arise primarily from the increased buffer requirements of the link-by-link approach     

On Adaptive Tree Polling Algorithms

This paper proposes three different algorithms for polling a finite set of users to determine the binary state of each user. The states are assumed to be described by i.i.d. Bernoulli random variables with parameterp. The algorithms differ in the responses offered by the users to queries and how the responses from several users are combined by the channel to produce a composite feedback signal which is received by all users. For each algorithm, the average number of transmissions required to determine the states of all users is determined as a function of the parameterp.     

Source time scale and optimal buffer/bandwidth tradeoff forheterogeneous regulated traffic in a network node

We study the problem of resource allocation and control for a network node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth tradeoff under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests that sources sharing a network node with finite bandwidth and buffer space divide into groups according to time scales defined by their leaky-bucket parameters. This time-scale separation determines the manner by which the buffer and bandwidth resources at the network node are shared among the sources. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexer using the “extremal” on-off, periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth tradeoff is again determined by a time-scale separation