A Finite Buffer Fluid Queue Driven by a Markovian Queue

We consider a finite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input flow into the fluid queue is thus characterized by a Markov modulated input rate process and we derive, for a wide class of such input processes, a procedure for the computation of the stationary buffer content of the fluid queue and the stationary overflow probability. This approach leads to a numerically stable algorithm for which the precision of the result can be specified in advance.     

Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.      

The Distributions of the Frequency of Occurrence of Nucleotide Subsequences

The objective is to derive the probability distribution of the frequency of occurrence of a subsequence within a nucleotide sequence under the hypothesis that the four nucleotides occur at random and with equal probability. We also consider the Compound Poisson approximation for the same distribution. The exact probability distribution can be obtained by the finite Markov chain imbedding technique introduced by Fu and Koutras (1994), however we can manage the case as well if the probabilities are not all equal. The compound Poisson approximation by Stein-Chen's method can be used to develop an approximate probability distribution with proper setting of the definition of the sets of dependence. Such structure gives a bound on the total variation distance, which tends to get relatively larger as the frequency goes up. AMS 2000 Subject Classification: Primary: 60E05; Secondary: 60J10     

Analysis of Stop-and-Wait ARQ for a wireless channel

In this paper, we study the behavior of the transmitter buffer of a system working under a Stop-and-Wait retransmission protocol. The buffer at the transmitter side is modeled as a discrete-time infinite-capacity queue. The numbers of information packets entering the buffer during consecutive slots are assumed to be independent and identically distributed random variables. The packets are sent over an unreliable channel and transmission errors occur in a correlated manner. Specifically, the probability of an erroneous transmission is modulated by a two-state Markov chain. An expression is derived for the probability generating function of the buffer content. This expression is then used to derive several queue-length characteristics and the mean packet delay. Numerical examples illustrate the strong effect of error correlation on the system performance. The obtained analytical results are also compared with appropriate simulations.      

Effective bandwidths for Markov regenerative sources

In this paper we consider the multiplexing of independent stochastic fluid sources onto a single buffer. The rate at which a source generates fluid is assumed to be modulated by a Markov regenerative process. We develop the exponential decay rates for the tails of the steady-state distribution of the buffer content. We also develop expressions for the effective bandwidths for such sources. All the results are in terms of the Perron-Frobenius eigenvalue of a matrix defined for the Markov regenerative source. As a special case we derive similar results for regenerative sources. We apply the results to video sources.This research was partially supported by NSF Grant No. NCR-9406823.     

An approximation method for complete solutions of Markov-modulated fluid models

This paper presents an approximation method for numerically solving general Markov-modulated fluid models which are widely used in modelling communications and computer systems. We show how the superposition of a group of heterogeneous sources (normally modeled by a multidimensional Markov process) can be approximated by a one-dimensional Markov process, which is then used as the modulating process of the buffer content process. The method effectively reduces the computation that is usually required to find exact (or asymptotic) solutions of fluid models. While this method is general, we focus our discussion on the models with only ON/OFF traffic sources. Numerous numerical results are provided to show the accuracy of the approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Matrix-analytic solution of infinite,finite and level-dependent second-order fluid models

This paper presents a matrix-analytic solution for second-order Markov fluid models (also known as Markov-modulated Brownian motion) with level-dependent behavior. A set of thresholds is given that divide the fluid buffer into homogeneous regimes. The generator matrix of the background Markov chain, the fluid rates (drifts) and the variances can be regime dependent. The model allows the mixing of second-order states (with positive variance) and first-order states (with zero variance) and states with zero drift. The behavior at the upper and lower boundary can be reflecting, absorbing, or a combination of them. In every regime, the solution is expressed as a matrix-exponential combination, whose matrix parameters are given by the minimal nonnegative solution of matrix quadratic equations that can be obtained by any of the well-known solution methods available for quasi birth death processes. The probability masses and the initial vectors of the matrix-exponential terms are the solutions of a set of linear equations. However, to have the necessary number of equations, new relations are required for the level boundary behavior, relations that were not needed in first-order level dependent and in homogeneous (non-level-dependent) second-order fluid models. The method presented can solve systems with hundreds of states and hundreds of thresholds without numerical issues.     

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     

Multiclass Markovian fluid queues

This paper considers a multiclass Markovian fluid queue with a buffer of infinite capacity. Input rates of fluid flows in respective classes and the drain rate from the buffer are modulated by a continuous-time Markov chain with finite states. We derive the joint Laplace-Stieltjes transform for the stationary buffer contents in respective classes, assuming the FIFO service discipline. Further we develop a numerically feasible procedure to compute the joint and marginal moments of the stationary buffer contents in respective classes. Some numerical examples are then provided.     

An Efficient Algorithm for Exact Distribution of Discrete Scan Statistics

Waiting time random variables and related scan statistics have a wide variety of interesting and useful applications. In this paper, exact distribution of discrete scan statistics for the cases of homogeneous two-state Markov dependent trials as well as i.i.d. Bernoulli trials are discussed by utilizing probability generating functions. A simple algorithm has been developed to calculate the distributions. Numerical results show that the algorithm is very efficient and is capable of handling large problems. AMS 2000 Subject Classification 60J22, 60E05, 60J10