Performance analysis of a multiplexer with the threshold based overload control in ATM networks

In this paper we analyze the performance of a statistical ATM multiplexer with bursty input traffic and two thresholds in the buffer by using queueing model. Two priority levels are considered for source traffic, which is modeled by Markov Modulated Poisson Process to represent the bursty characteristics. Service time distributions of two priority sources are assumed to be same and deterministic for ATM environment. The partial buffer sharing scheme with one threshold may experience a sensitive state change around the threshold. But the proposed multiplexer with two thresholds avoids this hysterical phenominon to improve the system operation.     

Stochastic models of space priority mechanisms with Markovian arrival processes

In this paper, we study a single-server queue with finite capacity in which several space priority mechanisms are implemented. The arrival process is the general Markovian arrival process (MAP) which has been used to model the bursty arrival processes commonly arising in communication applications. The service times are generally distributed. These buffer mechanisms enable the Asynchronous Transfer Mode (ATM) layer to adapt the quality of the cell transfer to the quality of service requirements of the specific broadband ISDN services and to improve the utilization of the network resources. This is done by a selective discarding of cells according to the class they belong to. Computable expressions for various performance parameters are obtained. Numerical results are given for the case of a two-state Markov-modulated Poisson process (MMPP) and deterministic service times. The values derived can be used to evaluate the benefits of using priorities in an ATM network when the traffic is bursty and to make a comparative study of the buffer mechanisms. These results extend the models previously developed, which were limited to Poisson arrivals.     

Loss pattern of DBMAP/DMSP/1/K queue and its application in wireless local communications

This paper applies a matrix-analytical approach to analyze the packet loss pattern of finite buffer single server queue with discrete-time batch Markovian arrival process (DBMAP). The service process is correlated and its structure is presented through discrete-time Markovian service process (DMSP). The bursty nature of packet loss pattern will be examined by means of statistics with respect to alternating loss periods and loss distances. The loss period is the period that loss once it starts; loss distance refers to the spacing between the loss periods. All of the two related performance measurement are derived, including probability distributions of a loss period and a loss distance, average length of a loss period and a loss distance. Queueing systems of this type arise in the domain of wireless local communications. Based on the numerical analysis of such a queueing system, some performance measures for the wireless local communication are presented.     

Admission control of multi-class traffic with service priorities in high-speed networks

We consider a fluid model of a system that handles multiple classes of traffic. The delay and cell-loss requirements of the different classes of traffic are generally widely different and are achieved by assigning different buffers for different classes, and serving them in a strict priority order. We use results from the effective bandwidth of the output processes (see Chang and Thomas (1995)) to derive simple and asymptotically exact call-admission policies for such a system to guarantee the cell-loss requirements for the different classes assuming that each source produces a single class traffic. We compare the admission-control policies developed here with the approximate policy studied by Elwalid and Mitra (1995) for the case of two-class traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of a single-server queue interacting with a fluid reservoir

We consider a single-server queueing system with Poisson arrivals in which the speed of the server depends on whether an associated fluid reservoir is empty or not. Conversely, the rate of change of the content of the reservoir is determined by the state of the queueing system, since the reservoir fills during idle periods and depletes during busy periods of the server. Our interest focuses on the stationary joint distribution of the number of customers in the system and the content of the fluid reservoir, from which various performance measures such as the steady-state sojourn time distribution of a customer may be obtained. We study two variants of the system. For the first, in which the fluid reservoir is infinitely large, we present an exact analysis. The variant in which the fluid reservoir is finite is analysed approximatively through a discretization technique. The system may serve as a mathematical model for a traffic regulation mechanism - a two-level traffic shaper - at the edge of an ATM network, regulating a very bursty source. We present some numerical results showing the effect of the mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of the MAP/G a ,b /1/N Queue

The Markovian arrival process (MAP) is used to represent the bursty and correlated traffic arising in modern telecommunication network. In this paper, we consider a single server finite capacity queue with general bulk service rule in which arrivals are governed by MAP and service times are arbitrarily distributed. The distributions of the number of customers in the queue at arbitrary, post-departure and pre-arrival epochs have been obtained using the supplementary variable and the embedded Markov chain techniques. Computational procedure has been given when the service time distribution is of phase type.     

Performance analysis of virtual circuit connections for bursty data sources in ATM networks

ATM is a packet-like transmission mode that has been proposed for BISDN. It is characterized by an asynchronous slotted transmission mechanism that provides a high bandwidth, low delay connection-oriented transport service to the end user. In this paper, we provide an analytical approach for determining the performance of a virtual circuit connection for data transmission in a high-speed ATM network with finite buffers at the network nodes. The analysis assumes that the network operates using thebest effort delivery strategy and that the end-to-end virtual circuit is responsible for guaranteeing the integrity of the connection. Since the normal Markovian assumptions do not apply, a concise exact solution is impossible to obtain. This provides motivation for developing approximate techniques such as those found in Whitt's QNA paper that allow us to use general distributions for the traffic streams and service times. However, even these techniques assume infinite buffer capacities and hence cannot model buffer overflow. We have therefore developed a hybrid model that allows us to incorporate finite buffers at the nodes. This enables us to study the effect on the performance of both link errors and buffer overflow in conjunction with an end-to-end packet loss recovery scheme.This work was supported in part by a grant from AT&T and in part by NSF under Grant No. 8914447.Work done while at the University of Pennsylvania, Philadelphia, PA 19104, USA     

Phase-type models for cellular networks supporting voice, video and data traffic

This paper presents an analytical model for cellular networks supporting voice, video and data traffic. Self-similar and bursty nature of the incoming traffic causes correlation in inter-arrival times of the incoming traffic. Therefore, arrival of calls is modeled with Markovian arrival process as it allows for the correlation. Call holding times, cell residence times and retrial times are modeled as phase-type distributions. We consider that the cells in a cellular network are statistically homogeneous, so it is enough to investigate a single cell for the performance analysis of the entire networks. With appropriate assumptions, the stochastic process that describes the state of a cell is a Quasi-birth–death (QBD) process. We derive explicit expressions for the infinitesimal generator matrix of this QBD process. Also, expressions for performance measures are obtained. Further, complexity involved in computing the steady-state probabilities is discussed. Finally, queueing examples are provided that can be obtained as particular cases of the proposed analytical model.     

Tail probabilities of low-priority waiting times and queue lengths in MAP/GI/1 queues

We consider the problem of estimating tail probabilities of waiting times in statistical multiplexing systems with two classes of sources – one with high priority and the other with low priority. The priority discipline is assumed to be nonpreemptive. Exact expressions for the transforms of these quantities are derived assuming that packet or cell streams are generated by Markovian Arrival Processes (MAPs). Then a numerical investigation of the large-buffer asymptotic behavior of the the waiting-time distribution for low-priority sources shows that these asymptotics are often non-exponential.     

Effective Bandwidths and Performance Bounds in High-Speed Communication Systems

This paper is concerned with quality of service guarantees in an environment with bursty traffic streams, such as those in the emerging ATM-based broadband ISDN.⁴ For virtually any traffic stream, new performance bounds are obtained in terms of effective bandwidths and burstiness constraints. The new bounds are tighter than those previously available and are asymptotically achievable, potentially resulting in better performance when used in traffic management. Various performance measures are considered. It is shown that the effective bandwidth of a departing traffic is bounded by that of the incoming traffic. For traffic streams having independent increments and Markov-modulated processes, the bounds are further refined to a point close to the exact values in some cases. Computationally, evaluation of the bounds requires less effort than finding effective bandwidths and burstiness constraints. Finally, the bounds are applied to routing control to find the near-optimal probabilistic routing policy.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Impedance-effects in capacity estimation

Formulas for the capacity of an unsignalized intersection for traffic streams which are subordinated to two or more streams of higher priority are developed. The case of only two conflicting streams analysed by Tanner (1962) is extended. The process at the intersection is modelled as a priority queuing system with Poisson input and service times depending on the work load.     

Burst reducing servers in ATM networks

We study a stream of traffic or message as it is transferred over an ATM connection consisting of burst reducing servers. A message is modeled as a deterministic fluid flow, and an ATM node is modeled as a server which allocates bandwidth to messages. A message's burstiness curve b() is the buffer size needed to prevent cell loss if it is served at rate. A server is burst reducing if its output message is always less bursty than the input message. Two popular bandwidth allocation schemes — the fixed rate and the leaky bucket server — are shown to be burst reducing. We also present a new class of burst reducing servers, the affine servers. We derive buffer requirements along a multi-hop connection and the final fluid flow reaching the destination as a message goes through a sequence of burst reducing servers. Finally, we suggest an approach to defining service quality.Part of this work was presented at Globecom'91, December 1991, and Infocom'93, March 1993.     

Exact Solution to Tandem Fluid Queues with Controlled Input

We consider a tandem fluid system composed of multiple buffers connected in a series. The first buffer receives input from a number of independent homogeneous on-off sources and each buffer provides input to the next buffer. The active (on) periods and silent (off) periods follow general and exponential distribution, respectively. Furthermore, the generally distributed active periods are controlled by an exponential timer. Under this assumption, explicit expressions for the distribution of the buffer content for the first buffer fed by a single source is obtained for the fluid queue driven by discouraged arrivals queue and infinite server queue. The buffer content distribution of the subsequent buffers when the first buffer is fed by multiple sources are found in terms of confluent hypergeometric functions. Numerical results are illustrated to compare the trend of the average buffer content for the models under consideration.     

On a generic class of two-node queueing systems

This paper analyzes a generic class of two-node queueing systems. A first queue is fed by an on–off Markov fluid source; the input of a second queue is a function of the state of the Markov fluid source as well, but now also of the first queue being empty or not. This model covers the classical two-node tandem queue and the two-class priority queue as special cases. Relying predominantly on probabilistic argumentation, the steady-state buffer content of both queues is determined (in terms of its Laplace transform). Interpreting the buffer content of the second queue in terms of busy periods of the first queue, the (exact) tail asymptotics of the distribution of the second queue are found. Two regimes can be distinguished: a first in which the state of the first queue (that is, being empty or not) hardly plays a role, and a second in which it explicitly does. This dichotomy can be understood by using large-deviations heuristics. This work has been carried out partly in the Dutch BSIK/BRICKS project.     

Buffer Overflow Probabilities for a Markov-Modulated Fluid Model

Markov modulated fluid models are widely used in modelling communications and computer systems. In the AMS (Annick, Mitra, Sohndi) model, heterogeneous, bursty sources modeled by multidimensional Markov processes are superimposed or multiplexed together to drive a fluid buffer. The performance of the system is measured by the steady state probability that the buffer exceeds a high level. The exact solution to this problem derived by AMS requires too much computation to be used on-line. Here we derive an upper bound for the above probability which is fast to compute and accurate enough for practical use.     

Delay analysis of multiclass queues with correlated train arrivals and a hybrid priority/FIFO scheduling discipline

We analyze the delay experienced in a discrete-time priority queue with a train-arrival process. An infinite user population is considered. Each user occasionally sends packets in the form of trains: a variable number of fixed-length packets is generated and these packets arrive to the queue at the rate of one packet per slot. This is an adequate arrival process model for network traffic. Previous studies assumed two traffic classes, with one class getting priority over the other. We extend these studies to cope with a general number M of traffic classes that can be partitioned in an arbitrary number N of priority classes (1 ≤ N ≤ M). The lengths of the trains are traffic-class-dependent and generally distributed. To cope with the resulting general model, an (M × )∞-sized Markovian state vector is introduced. By using probability generating functions, moments and tail probabilities of the steady-state packet delays of all traffic classes are calculated. Since this study can be useful in deciding how to partition traffic classes in priority classes, we demonstrate the impact of this partitioning for some specific cases.     

Performance analysis of AAL multiplexer with CBR traffic and bursty traffic

This paper models and evaluates the AAL multiplexer to analyze AAL protocol in ATM networks. We consider an AAL multiplexer in which a single periodically deterministic CBR traffic stream and several variable size bursty background traffic streams are multiplexed and one ATM cell stream goes out. We model the AAL multiplexer as aB ^X +D/D/1/K queue and analyze this queueing system. We represent various performance measures such as loss probability and waiting time in the basis of cell and packet.     

Proof of Monotone Loss Rate of Fluid Priority-Queue with Finite Buffer

This paper studies a fluid queueing system that has a single server, a single finite buffer, and which applies a strict priority discipline to multiple arriving streams of different classes. The arriving streams are modeled by statistically independent, identically distributed random processes. A proof is presented for the highly intuitive result that, in such a queueing system, a higher priority class stream has a lower average fluid loss rate than a lower priority class stream. The proof exploits the fact that for a work-conserving queue, the fluid loss rate for a given class is invariant of what queueing discipline is applied to all arriving fluid of this particular class. AMS subject classification: 60K25, 68M20     

Mean Buffer Contents in Discrete-Time Single-Server Queues with Heterogeneous Sources

We consider discrete-time single-server queues fed by independent, heterogeneous sources with geometrically distributed idle periods. While being active, each source generates some cells depending on the state of the underlying Markov chain. We first derive a general and explicit formula for the mean buffer contents in steady state when the underlying Markov chain of each source has finite states. Next we show the applicability of the general formula to queues fed by independent sources with infinite-state underlying Markov chains and discrete phase-type active periods. We then provide explicit formulas for the mean buffer contents in queues with Markovian autoregressive sources and greedy sources. Further we study two limiting cases in general settings, one is that the lengths of active periods of each source are governed by an infinite-state absorbing Markov chain, and the other is the model obtained by the limit such that the number of sources goes to infinity under an appropriate normalizing condition. As you will see, the latter limit leads to a queue with (generalized) M/G/∞ input sources. We provide sufficient conditions under which the general formula is applicable to these limiting cases.AMS subject classification: 60K25, 60K37, 60J10This revised version was published online in June 2005 with corrected coverdate