Performance Analysis of an ATM Multiplexer with Multiple QoS VBR Traffic

In this paper, we propose a new queuing model, MMDP/MMDP/1/K, for an asynchronous transfer mode (ATM) multiplexer with multiple quality of service (QoS) variable bit rate (VBR) traffic in broad band-integrated services digital network (B-ISDN). We use the Markov Modulated Deterministic Process (MMDP) to approximate the actual arrival process and another MMDP for service process. Using queuing analysis, we derive a formula for the cell loss probability of the ATM multiplexer in terms of the limiting probabilities of a Markov chain. The cell loss probability can be used for connection admission control in ATM multiplexer and the calculation of equivalent bandwidth for arrival traffic. The major advantages of this approach are simplicity in analysis, accuracy of analysis by comparison of simulation, and numerical stability.     

A hybrid analysis/simulation for ATM performance with application to quality-of-service of CBR traffic

A discrete time queueing model for the performance of an ATM system is analyzed using matrix analytic methods. Time is segmented into slots with each slot equal to the transmission time of one ATM cell. The ATM system is modeled as a single server queue with Markovian arrivals and service time equal to one slot. The arrival process includes as a special case the superposition of on-off sources, possibly heterogeneous. The queueing model is of the M/G/1 type. By exploiting the structure of the M/G/1 type Markov chain, the complexity of the solution to the problem is reduced to only the inversion of a 2×2 matrix irrespective of the size of the Markov chain. This simplification allows us to investigate Constant Bit Rate (CBR) traffic performance (or quality-of-service) issues through a hybrid analysis/simulation approach. Specifically, we analyze the impact of on-off background traffic on the probability of consecutive cell losses, cell delay variation, and traffic shaper or playback buffer underflow and overflow probabilities of CBR traffic sources.     

A novel approach to estimating the cell loss probability in an ATMmultiplexer loaded with homogeneous on-off sources

Estimating the cell loss probability in an ATM multiplexer is one of the most important problems concerning congestion control and bandwidth management in an ATM-based BISDN. We propose a new approach to estimating the cell loss probability in an ATM multiplexer. We use the Markov modulated deterministic process (MMDP) to approximate the actual arrival process and then model the ATM multiplexer as an MMDP/D/1/K queueing system. Using queueing analysis, we derive a formula for the cell loss probability expressed in terms of the limiting probabilities of a Markov chain. We propose two approximation methods based on the results of the analysis. The actual arrival process is approximated by an (M+1)-state MMDP in the first method and by a two-state MMDP in the second. The major advantages of both methods are simplicity, computational efficiency, and numerical stability. The most attractive feature of the second method is that the cell loss probability can be expressed in closed form. Numerical and simulation results show that the first method is sufficiently accurate for all cases in which burst-level congestion is the main contributing factor to cell loss, while the closed-form formula is sufficiently accurate for applications where the average burst length is large (such as large file transfers, image retrievals, etc.)     

Approximating the heterogeneous fluid queue with a birth-deathfluid queue

Recent research has shown that fluid-flow queueing models accurately determine the burst level component of the ATM multiplexer process, and fluid models therefore constitute an efficient tool for the investigation of admission control in ATM networks. This article first gives a review of Markov-driven fluid queues with special attention given to the heterogeneous on/off model. Then an approximation procedure in which the original heterogeneous arrival process is replaced by a homogeneous birth-death arrival process is presented. The substitution is based on matching statistical parameters. Finally, the approach is evaluated by numerical examples     

A histogram-based model for video traffic behavior in an ATMmultiplexer

The authors introduce a model based on arrival rate histograms for characterizing the behavior of an ATM buffer when it is carrying variable bit rate video traffic. Traffic smoothing on a frame-by-frame basis allows a quasistatic approximation that accurately predicts results such as buffer occupancy distributions and cell loss rates to be made. Convolving individual source histograms allow prediction of the queueing performance of a multiplexed stream. The approximation is investigated in more detail by modeling video as a Markov modulated Poisson process. It is shown that the multiplexer system is nearly completely decomposable (NCD). NCD systems have a well-known approximate solution, which is identical to the histogram approximation. Error bounds for the NCD approximation are also known and are reasonably tight. Results indicate that while the presence of strong correlations is an important characteristic of video traffic, the actual form of that correlation is not     

Accurate approximation of cell loss probability for self-similartraffic in ATM networks

Recently, self-similar (or fractal) stochastic processes have been regarded as more accurate models of certain categories of traffic (e.g. LAN traffic) which will be transported in ATM networks. The authors propose a method for estimating the cell loss probability in an ATM multiplexer fed by a self-similar arrival process. The packet arrivals are generated by a fractional Brownian motion process and the service process is deterministic. The approach is based on theory for large deviations, and simulation tests show that it is more accurate than the existing approximation result     

Analysing the interdeparture process in an ATM multiplexer

This paper studies the interdeparture process in a mathematical model of an ATM multiplexer. The technique is based on a discrete-time queueing model of k input queues feeding one output queue, a situation commonly arising in ATM switches. The process between input queues and output queue is analysed in detail. For a service rate of one cell per time slot (s = 1) the exact solution of the interdeparture process is given based on the binomial distribution. For a service rate greater than one cell per time slot (s > 1) a solution is derived using the state probabilities of the input queues. The probability density function of the interdeparture process is then obtained by summing a combination of the multinomial joint distribution function of s random variables. If the state probabilities are referred to as the distribution of buffer contents after arrival, the formula returns exact results. © 1998 John Wiley & Sons, Ltd.     

Diffusion approximation modeling for Markov modulated burstytraffic and its applications to bandwidth allocation in ATMnetworks

We consider a statistical multiplexer model, in which each of the K sources is a Markov modulated rate process (MMRP). This formulation allows a more general source model than the well studied “on-off” source model in characterizing variable bit rate (VBR) sources such as compressed video. In our model we allow an arbitrary distribution for the duration of each of the M states (or levels) that the source can take on. We formulate Markov modulated sources as a closed queueing network with M infinite-server nodes. By extending our earlier results we introduce an M-dimensional diffusion process to approximate the aggregate traffic of such Markov modulated sources. Under a set of reasonable assumptions we then show that this diffusion process can be expressed as an M-dimensional Ornstein-Uhlenbeck (O-U) process. The queueing behavior of the buffer content is analyzed by applying a diffusion process approximation to the aggregate arrival process. We show some numerical examples which illustrate typical sample paths, and autocorrelation functions of the aggregate traffic and its diffusion process representation. Simulation results validate our proposed approximation model, showing good fits for distributions and autocorrelation functions of the aggregate rate process and the asymptotic queueing behavior. We also discuss how the analytical formulas derived from the diffusion approximation can be applied to compute the equivalent bandwidth for real-time call admission control, and how the model can be modified to characterize traffic sources with long-range dependence     

周期性业务流通过ATM复用器的时延抖动分析

ＡＴＭ通信网中需要传送多种业务，其中有一类是具有连续比特流的业务，这种业务的发送信元到达时间是周期性的，本文分析了一种周期性信元流通过ＡＴＭ复用器的排队模型，得出信元流排队时延的概率分布，时延抖动的自相关函数的功率谱。     

Tail probabilities with statistical multiplexing and effective bandwidths in multi-class queues

Our primary purpose in this paper is to contribute to the design of admission control schemes for multi-class service systems. We are motivated by emerging highspeed networks exploiting asynchronous transfer mode (ATM) technology, but there may be other applications. We develop a simple criterion for feasibility of a set of sources in terms of effective bandwidths. These effective bandwidths are based on asymptotic decay rates of steady-state distributions in queueing models. We show how to compute asymptotic decay rates of steady-state queue length and workload tail probabilities in general infinite-capacity multi-channel queues. The model hasm independent heterogeneous servers that are independent of an arrival process which is a superposition ofn independent general arrival processes. The contribution of each component arrival process to the overall asymptotic decay rates can be determined from the asymptotic decay rates produced by this arrival process alone in a G/D/1 queue (as a function of the arrival rate). Similarly, the contribution of each service process to the overall asymptotic decay rates can be determined from the asymptotic decay rates produced by this service process alone in a D/G/1 queue. These contributions are characterized in terms of single-channel asymptotic decay-rate functions, which can be estimated from data or determined analytically from models. The asymptotic decay-rate functions map potential decay rates of the queue length into associated decay rates of the workload. Combining these relationships for the arrival and service channels determines the asymptotic decay rates themselves. The asymptotic decay-rate functions are the time-average limits of logarithmic moment generating functions. We give analytical formulas for the asymptotic decay-rate functions of a large class of stochastic point processes, including batch Markovian arrival processes. The Markov modulated Poisson process is a special case. Finally, we try to put our work in perspective with the related literature.     

Cell arrival modeling and related statistical multiplexer performance in ATM networks

A source is assumed to go through independently distributed ON and OFF periods. During an ON period, cells arrive spaced apart in time by a fixed interval. No cells arrive during an OFF period. The probability distribution of the ON and OFF periods are arbitrary. Traffic from a number of such sources is statistically multiplexed. The related statistical multiplexer performance is studied analytically as follows. A statistical multiplexer is modeled as a discrete-time single-server queueing system where the traffic from a new source (conforming to the cell arrival process described above) joins traffic that is already being statistically multiplexed. The aggregated arrival of cells from existing traffic is assumed to follow a two-state Markov modulated cell arrival process. Numerical examples that relate the performance at the statistical multiplexer to the parameters describing the traffic from the new source and the aggregated traffic are presented.This research was supported in part by the National Science Foundation under Grant No. NCR-9016348, and by the Pacific Bell External Technology Program.     

突发性业务环境下周期性信元流通过ATM复接器的时延抖动

在输入ATM网络的业务源中,周期性信元流是很重要的一种.本文精确地分析了一个有限缓存的ATM复接器,其输入业务源由一路周期性信元流、多路随机性贝努利(Bernoulli)信元流和突发性两状态马尔科夫调制贝努利(MMBP)信元流构成.得出了该路周期性信元流的排队时延分布、时延抖动的自相关函数和功率谱.揭示了突发性业务环境下周期性信元流通过ATM复接器的时延抖动行为.计算机模拟验证了分析结果的正确性.     

Analysis of a discrete-time queue with integrated bursty inputs in ATM networks

In this paper, we carry out an exact analysis of a discrete-time queue system with a number of independent Markov modulated inputs in ATM networks, using a generating function approach. We assume that the queueing system has an infinite buffer with M servers. The cell arrival process is characterized by a number of independent Markov modulated geometrical batch arrival processes. We first obtain the generating function of the queue-size distribution at steady-state in vector form, then derive an expression for the average queue-size in terms of the unknown boundary probabilities. To obtain those unknown probabilities, we use the technique proposed in Reference 1. This involves decomposing the system characteristic function to evaluate the roots and solving a set of linear equations. One of the contributions of this paper is presented in Lemma 1, which characterizes the property of the underlying eigenvalues. For one special case of at least M-1 cell arrivals during one slot at one Markov state and of at least M arrivals at all other states, the determination of the unknowns is straightforward. If every Markov modulated arrival process can be further decomposed into a number of i.i.d. two-state, or three-state, or even four-state Markov modulated arrival processes, then each root can be obtained separately using an iterative algorithm. Numerical results are presented to validate the proposed traffic models against actual traffic measurements.     

Burstiness and resource management in ATM networks

Networks based upon the asynchronous transfer mode (ATM) provide for high flexibility to cope with a wide range of applications, some of them producing highly sporadic traffic. Therefore, the problem of burstiness has become in the last few years a key issue for such networks. A basic question is how to dimension network buffers in the presence of bursty traffic? In this paper we investigate the concept of burstiness and its impact on resource management. In burstiness characterization encountered in the literature, special attention has been given to the squared coefficient of variation of inter-arrival time Cv² in a cell arrival process. In order to observe the impact of bursty traffic on a queue, we develop in the present paper a ‘bursty’ traffic model, namely the two-stage hyper-Bernoulli cell arrival process, HBP₂, for short. We numerically solve the HBP₂/D/1/K queue. We especially derive the rejection probability P_loss. Numerical results are then thoroughly studied and we discuss the relevance for burstiness characterization of Cv² and peak to mean rate ratio B. We draw attention to the concept of local overload, i.e. when the arrival rate is greater than the server rate. This seems to be the most relevant phenomenon in the impact of a bursty traffic on a queue. These results are finally applied to the problem of resource management in ATM networks.     

The teletraffic analysis of the multi-server loss model with renewal distributions

This paper presents a loss model in which a general renewal arrival stream is served by any number of general renewal servers, i.e., theGI/GI/s/s model. Using linear algebraic queueing theory (LAQT), we provide the exact steady-state solution of the number of customers in theGI/GI/s/s model at general, arrival, and departure times. We show that the steady-state solution at arrival times can be used to approximate those at general times and that the third moment of the arrival process significantly affects this approximation. Finally, we show that a conjectured inequality does not hold.This work was performed while at the University of Missouri-Kansas City.     

Buffer sizing in an ATM switch for both ATM and STM traffics

Specific queueing models are derived in order to size the buffers of ATM switching elements in the cases of ATM or STM multiplexed traffic. Buffering is performed either at the outputs or in a central memory for ATM multiplexed traffic; for STM multiplexed traffic, buffers can also be provided at the inputs. The buffer size is chosen in order to ensure a loss probability in the switch smaller than 10^?10. It is shown that the buffer size per output in the case of central queueing is smaller than the buffer size in case of output queueing for both ATM and STM multiplexed traffics. Moreover, for STM multiplexed traffic, buffer sizes are identical for input and output queueing. Lastly, it is pointed out that buffers used for STM multiplexed traffic should be 4 to 20 times larger than the corresponding buffers for ATM multiplexed traffic.     

MMPP models for multimedia traffic

The paper presents a study on the use of Markov‐Modulated Poisson Processes (MMPP's) for characterizing multimedia traffic with short‐term and long‐term correlation. The applicability of the 2‐state MMPP and a refined moment‐based parameter‐matching technique to model an arbitrary ATM traffic stream in evaluating its queueing performance are examined by simulation. Following a discussion on the limitation of the 2‐state MMPP model, a model using a superposition of N homogeneous 2‐state MMPP to characterize bursty multimedia traffic is presented. The proposed model requires only five parameters which can be estimated from the samples of the traffic counting process by using a pdf‐based matching technique. The introduced pdf‐based parameter‐matching procedure uses the probability density function of the arrival rate and the IDC curve of the traffic samples. An approximation for the probability of loss in MMPP/D/1 queues is also obtained. The versatility and accuracy of the proposed model to characterize bursty multimedia traffic are shown by several case studies and test results. This revised version was published online in June 2006 with corrections to the Cover Date.     

Loss performance analysis of an ATM multiplexer loaded withhigh-speed on-off sources

The performance of an asynchronous transfer mode (ATM) multiplexer whose input consists of the superposition of a multiplicity of homogeneous on-off sources modeled by a two-state Markovian process is studied. The approach is based on the approximation of the actual input process by means of a suitably chosen two-state Markov modulated Poisson process (MMPP), as a simple and effective choice for the representation of superposition arrival streams. To evaluate the cell loss performance, a new matching procedure that leads to accurate results compared to simulation is developed. The application limits of the proposed method are also discussed. The outstanding physical meaning of this procedure permits a deep insight into the multiplexer performance behavior as the source parameters and the multiplexer buffer size are varied     

Loss Probabilities of Hand-in Traffic under Various Protocols,I: Models and Algebraic Results

Mobile telephone traffic business demands that a given base station be able to handle both newly originating traffic and hand-in traffic from neighbouring base stations, with priority to be given to the latter, existing traffic. Starting from a baseline standard model in which all channels are available to all traffic, this note examines three other models, each with its own access control protocol that allocates a reserve capacity R amongst the N _tot channels to give priority to the hand-in traffic. These different protocols give different loss probabilities for the two types of traffic. All the results are proved on the basis of assuming a Poisson arrival process and independent exponential service times. This paper concentrates on presenting explicit expressions for many of the loss probabilities, some of them given by the Erlang B loss formula or variants, as well as simple approximations and bounds. A companion paper presents results comparing the various models.