A fluid queue driven by a Markovian queue

We consider an infinite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input is characterized by a Markov modulated rate process. We derive a new approach for the computation of the stationary buffer content. This approach leads to a numerically stable algorithm for which the precision of the result can be given in advance. This revised version was published online in June 2006 with corrections to the Cover Date.     

Heavy traffic limit for the workload plateau process in a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue has renewal arrivals with generally distributed service times, and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. The reuse of service times creates strong dependence at the second queue, making its workload difficult to analyze. To investigate the evolution of workload in the second queue, we introduce and study a process $M$, called the plateau process, which encodes most of the information in the workload process. We focus on the case of infinite-variance service times and show that under appropriate scaling, workload in the first queue converges, and although the workload in the second queue does not converge, the plateau process does converge to a limit $M^1$ that is a certain function of two independent Lévy processes. Using excursion theory, we derive some useful properties of $M^1$ and compare a time changed version of it to a limit process derived in previous work.     

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.     

Simple analysis of a fluid queue driven by an M/M/1 queue

In this note we consider the fluid queue driven by anM/M/1 queue as analysed by Virtamo and Norros [Queueing Systems 16 (1994) 373–386]. We show that the stationary buffer content in this model can be easily analysed by looking at embedded time points. This approach gives the stationary buffer content distribution in terms of the modified Bessel function of the first kind of order one. By using a suitable integral representation for this Bessel function we show that our results coincide with the ones of Virtamo and Norros.     

Estimation in the Markov random walk scheme

The Markov random walk scheme is used to construct unbiased estimators for the function of the unknown transition probability matrix. Uniqueness of these estimators is investigated. Easily testable completeness conditions for Markov random walk plans are given.Translated from Statisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 35–54, 1986.     

The fluid limit of the multiclass processor sharing queue

Consider a single server queueing system with several classes of customers, each having its own renewal input process and its own general service times distribution. Upon completing service, customers may leave, or re-enter the queue, possibly as customers of a different class. The server is operating under the egalitarian processor sharing discipline. Building on prior work by Gromoll et al.?(Ann. Appl. Probab. 12:797?C859, 2002) and Puha et al.?(Math. Oper. Res. 31(2):316?C350, 2006), we establish the convergence of a properly normalized state process to a fluid limit characterized by a system of algebraic and integral equations. We show the existence of a unique solution to this system of equations, both for a stable and an overloaded queue. We also describe the asymptotic behavior of the trajectories of the fluid limit.     

Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation

In this paper, we study a discrete-time queueing system with one server and two classes of customers. Customers enter the system according to a general independent arrival process. The classes of consecutive customers, however, are correlated in a Markovian way. The system uses a “global FCFS” service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their classes. The service-time distribution of the customers is general but class-dependent, and therefore, the exact order in which the customers of both classes succeed each other in the arrival stream is important, which is reflected by the complexity of the system content and waiting time analysis presented in this paper. In particular, a detailed waiting time analysis of this kind of multi-class system has not yet been published, and is considered to be one of the main novelties by the authors. In addition to that, a major aim of the paper is to estimate the impact of interclass correlation in the arrival stream on the total number of customers in the system, and the customer delay. The results reveal that the system can exhibit two different classes of stochastic equilibrium: a “strong” equilibrium where both customer classes give rise to stable behavior individually, and a “compensated” equilibrium where one customer type creates overload.     

On the fluid approximation for a multiclass queue under non-preemptive SBP service discipline

A multi-class single server queue under non-preemptive static buffer priority (SBP) service discipline is considered in this paper. Using a bounding technique, we obtain the fluid approximation for the queue length and busy time processes. Furthermore, we prove that the convergence rate of the fluid approximation for the queue length and busy time processes is exponential for large N. Additionally, a sufficient condition for stability is obtained.     

Characterizing the departure process of a single server queue from the embedded Markov renewal process at departures

In the literature, performance analyses of numerous single server queues are done by analyzing the embedded Markov renewal processes at departures. In this paper, we characterize the departure processes for a large class of such queueing systems. Results obtained include the Laplace–Stieltjes transform (LST) of the stationary distribution function of interdeparture times and recursive formula for {_cn ≡ the covariance between interdeparture times of lag n}. Departure processes of queues are difficult to characterize and for queues other than M/G/1 this is the first time that {_cn} can be computed through an explicit recursive formula. With this formula, we can calculate {_cn} very quickly, which provides deeper insight into the correlation structure of the departure process compared to the previous research. Numerical examples show that increasing server irregularity (i.e., the randomness of the service time distribution) destroys the short-range dependence of interdeparture times, while increasing system load strengthens both the short-range and the long-range dependence of interdeparture times. These findings show that the correlation structure of the departure process is greatly affected by server regularity and system load. Our results can also be applied to the performance analysis of a series of queues. We give an application to the performance analysis of a series of queues, and the results appear to be accurate. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bounds for the tail distribution in a queue with a superposition of general periodic Markov sources: theory and application

An efficient yet accurate estimation of the tail distribution of the queue length has been considered as one of the most important issues in call admission and congestion controls in ATM networks. The arrival process in ATM networks is essentially a superposition of sources which are typically bursty and periodic either due to their origin or their periodic slot occupation after traffic shaping. In this paper, we consider a discrete-time queue where the arrival process is a superposition of general periodic Markov sources. The general periodic Markov source is rather general since it is assumed only to be irreducible, stationary and periodic. Note also that the source model can represent multiple time-scale correlations in arrivals. For this queue, we obtain upper and lower bounds for the asymptotic tail distribution of the queue length by bounding the asymptotic decay constant. The formulas can be applied to a queue having a huge number of states describing the arrival process. To show this, we consider an MPEG-like source which is a special case of general periodic Markov sources. The MPEG-like source has three time-scale correlations: peak rate, frame length and a group of pictures. We then apply our bound formulas to a queue with a superposition of MPEG-like sources, and provide some numerical examples to show the numerical feasibility of our bounds. Note that the number of states in a Markov chain describing the superposed arrival process is more than 1.4 × 10⁸⁸. Even for such a queue, the numerical examples show that the order of the magnitude of the tail distribution can be readily obtained.     

On the fluid limit of the M/G/∞ queue

The paper deals with the fluid limits of some generalized M/G/∞ queues under heavy-traffic scaling. The target application is the modeling of Internet traffic at the flow level. Our paper first gives a simplified approach in the case of Poisson arrivals. Expressing the state process as a functional of some Poisson point process, an elementary proof for limit theorems based on martingales techniques and weak convergence results is given. The paper illustrates in the special Poisson arrivals case the classical heavy-traffic limit theorems for the G/G/∞ queue developed earlier by Borovkov and by Iglehart, and later by Krichagina and Puhalskii. In addition, asymptotics for the covariance of the limit Gaussian processes are obtained for some classes of service time distributions, which are useful to derive in practice the key parameters of these distributions.     

Estimation for mixtures of Markov processes

Finite mixtures of Markov processes with densities belonging to exponential families are introduced. Quasi-likelihood and maximum likelihood methods are used to estimate the parameters of the mixing distributions and of the component distributions. The E-M algorithm is used to compute the ML estimates. Mixture of Autoregressive processes and of two-state Markov chains are discussed as specific examples. Simulation results on the comparison of quasi-likelihood and ML estimates are reported.     

Provable bounds for the mean queue lengths in a heterogeneous priority queue

We analyze a two-class two-server system with nonpreemptive heterogeneous priority structures. We use matrix–geometric techniques to determine the stationary queue length distributions. Numerical solution of the matrix–geometric model requires that the number of phases be truncated and it is shown how this affects the accuracy of the results. We then establish and prove upper and lower bounds for the mean queue lengths under the assumption that the classes have equal mean service times. This revised version was published online in June 2006 with corrections to the Cover Date.     

Nonparametric Density Estimation in Hidden Markov Models

Let { X n} be a Markov chain that is either f -mixing or satisfies the Poisson equation.In this note we obtain the convergence rate under L 1 -criterion for bounded functions of the X k 's. And in the hidden Markov model setup { (X n ,Y n ) }we study the kernel estimate of the density of the observed variables { Y n }when a 'stable' status is reached.     

Estimation of Binary Markov Random Fields Using Markov chain Monte Carlo

This article compares three binary Markov random fields (MRFs) which are popular Bayesian priors for spatial smoothing. These are the Ising prior and two priors based on latent Gaussian MRFs. Concern is given to the selection of a suitable Markov chain Monte Carlo (MCMC) sampling scheme for each prior. The properties of the three priors and sampling schemes are investigated in the context of three empirical examples. The first is a simulated dataset, the second involves a confocal fluorescence microscopy dataset, while the third is based on the analysis of functional magnetic resonance imaging (fMRI) data. In the case of the Ising prior, single site and multi-site Swendsen-Wang sampling schemes are both considered. The single site scheme is shown to work consistently well, while it is shown that the Swendsen-Wang algorithm can have convergence problems. The sampling schemes for the priors are extended to generate the smoothing parameters, so that estimation becomes fully automatic. Although this works well, it is found that for highly contiguous images fixing smoothing parameters to very high values can improve results by injecting additional prior information concerning the level of contiguity in the image. The relative properties of the three binary MRFs are investigated, and it is shown how the Ising prior in particular defines sharp edges and encourages clustering. In addition, one of the latent Gaussian MRF priors is shown to be unable to distinguish between higher levels of smoothing. In the context of the fMRI example we also undertake a simulation study.     

Occupation times for the finite buffer fluid queue with phase-type ON-times

In this short communication we study a fluid queue with a finite buffer. The performance measure we are interested in is the occupation time over a finite time period, i.e., the fraction of time the workload process is below some fixed target level. Using an alternating renewal sequence, we determine the double transform of the occupation time; the occupation time for the finite buffer M/G/1 queue with phase-type jumps follows as a limiting case.