Models for queue length in clocked queueing networks

We analyze a discrete-time network of queues. The unit element of the network is the 2 × 2 buffered switch, which we regard as a system of two queues working in parallel. We show how to transform transition probability information from the output of one switch, or network stage, to the input of the next one. This is used to carry out a Markov time series input model to predict mean queue length at every stage of the system. Another model considered is a renewal process time series model, which we use to find the mean queue length of the second stage of the network. Numerical simulations fall within the narrow band spanned by the two models.     

A fluid system with coupled input and output,and its application to bottlenecks in ad hoc networks

This paper studies a fluid queue with coupled input and output. Flows arrive according to a Poisson process, and when n flows are present, each of them transmits traffic into the queue at a rate c/(n+1), where the remaining c/(n+1) is used to serve the queue. We assume exponentially distributed flow sizes, so that the queue under consideration can be regarded as a system with Markov fluid input. The rationale behind studying this queue lies in ad hoc networks: bottleneck links have roughly this type of sharing policy. We consider four performance metrics: (i) the stationary workload of the queue, (ii) the queueing delay, i.e., the delay of a ‘packet’ (a fluid particle) that arrives at the queue at an arbitrary point in time, (iii) the flow transfer delay, i.e., the time elapsed between arrival of a flow and the epoch that all its traffic has been put into the queue, and (iv) the sojourn time, i.e., the flow transfer time increased by the time it takes before the last fluid particle of the flow is served. For each of these random variables we compute the Laplace transform. The corresponding tail probabilities decay exponentially, as is shown by a large-deviations analysis. F. Roijers’ work has been carried out partly in the SENTER-NOVEM funded project Easy Wireless.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

Continuity of the M/G/c queue

Consider an M/G/c queue with homogeneous servers and service time distribution F. It is shown that an approximation of the service time distribution F by stochastically smaller distributions, say F _n , leads to an approximation of the stationary distribution π of the original M/G/c queue by the stationary distributions π _n of the M/G/c queues with service time distributions F _n . Here all approximations are in weak convergence. The argument is based on a representation of M/G/c queues in terms of piecewise deterministic Markov processes as well as some coupling methods.      

On a processor sharing queue that models balking

We consider the processor sharing M/M/1-PS queue which also models balking. A customer that arrives and sees n others in the system “balks” (i.e., decides not to enter) with probability 1−b _n . If b _n is inversely proportional to n + 1, we obtain explicit expressions for a tagged customer’s sojourn time distribution. We consider both the conditional distribution, conditioned on the number of other customers present when the tagged customer arrives, as well as the unconditional distribution. We then evaluate the results in various asymptotic limits. These include large time (tail behavior) and/or large n, lightly loaded systems where the arrival rate λ → 0, and heavily loaded systems where λ → ∞. We find that the asymptotic structure for the problem with balking is much different from the standard M/M/1-PS queue. We also discuss a perturbation method for deriving the asymptotics, which should apply to more general balking functions.     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

Sojourn time distributions for the M/M/1 queue in a Markovian environment

In this paper, we study a single server queue in which both the arrival rate and service rate depend on the state of an external Markov process (called the environment) with a finite state space. Given that the environment is in state j, the mean arrival and service rates are λ_j and μ_j respectively. For such a queue, the queue length distribution is known to be matrix geometric. In this paper, we characterize the Laplace-Stieltjes transform of the sojourn time distribution under four disciplines - last come first served preemptive resume, last come first served, processor sharing and round robin. We also discuss a potential application of this queue in the are of data communication.     

Analysis of a Discrete-Time Finite-Capacity Single-Server Queue with Markovian-Arrival Process and Random-Bulk-Service: D-MAP/G Y /1/M

In this article, we consider a single-server, finite-capacity queue with random bulk service rule where customers arrive according to a discrete-time Markovian arrival process (D-MAP). The model is denoted by D-MAP/G ^Y /1/M where server capacity (bulk size for service) is determined by a random variable Y at the starting point of services. A simple analysis of this model is given using the embedded Markov chain technique and the concept of the mean sojourn time of the phase of underlying Markov chain of D-MAP. A complete solution to the distribution of the number of customers in the D-MAP/G ^Y /1/M queue, some computational results, and performance measures such as the average number of customers in the queue and the loss probability are presented.     

On the Transient Behavior of the M/M/1 and M/M/1/M Queues

This paper gives a transient analysis of the classic M/M/1 and M/M/1/K queues. Our results are asymptotic as time and queue length become simultaneously large for the infinite capacity queue, and as the system’s storage capacity K becomes large for the finite capacity queue. We give asymptotic expansions for p_n(t), which is the probability that the system contains n customers at time t. We treat several cases of initial conditions and different traffic intensities. The results are based on (i) asymptotic expansion of an exact integral representation for p_n(t) and (ii) applying the ray method to a scaled form of the forward Kolmogorov equation which describes the time evolution of p_n(t).     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

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.      

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

A BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

The acquisition queue

We propose a new queueing model named the acquisition queue. It differs from conventional queueing models in that the server not only serves customers, but also performs acquisition of new customers. The server has to divide its energy between both activities. The number of newly acquired customers is uncertain, and the effect of the server’s acquisition efforts can only be seen after some fixed time period δ (delay). The acquisition queue constitutes a (δ+1)-dimensional Markov chain. The limiting queue length distribution is derived in terms of its probability generating function, and an exact expression for the mean queue length is given. For large values of δ the numerical procedures needed for calculating the mean queue length become computationally cumbersome. We therefore complement the exact expression with a fluid approximation. One of the key features of the acquisition queue is that the server performs more acquisition when the queue is small. Together with the delay, this causes the queue length process to show a strongly cyclic behavior. We propose and investigate several ways of planning the acquisition efforts. In particular, we propose an acquisition scheme that is designed specifically to reduce the cyclic behavior of the queue length process. This research was financially supported by the European Network of Excellence Euro-NGI. The work of the second author was supported in part by a TALENT grant from the Netherlands Organisation for Scientific Research (NWO).     

Availability and failure frequency of a Gnedenko system

This paper considers anN-unit series system supported by a warm standby unit and a single repair facility. Suppose that the operating units and the standby unit have constant failure ratesa anda ₁, respectively. When the system is down, all the operable units have constant failure ratea ₂. The repair time of a failed unit has an arbitrary distribution. Using Takács' method and a Markov renewal process, we discuss the stochastic behavior of this system and obtain the explicit formulae of the system availability and failure frequency.Project supported by the National Natural Science Foundation of China.     

Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime

To investigate the quality of heavy-traffic approximations for queues with many servers, we consider the steady-state number of waiting customers in an M/D/s queue as s→∞. In the Halfin-Whitt regime, it is well known that this random variable converges to the supremum of a Gaussian random walk. This paper develops methods that yield more accurate results in terms of series expansions and inequalities for the probability of an empty queue, and the mean and variance of the queue length distribution. This quantifies the relationship between the limiting system and the queue with a small or moderate number of servers. The main idea is to view the M/D/s queue through the prism of the Gaussian random walk: as for the standard Gaussian random walk, we provide scalable series expansions involving terms that include the Riemann zeta function.      

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.     

Loss probability in a finite discrete-time queue in terms of the steady state distribution of an infinite queue

We consider a discrete-time single-server queue with arrivals governed by a stationary Markov chain, where no arrivals are assumed to occur only when the Markov chain is in a particular state. This assumption implies that off-periods in the arrival process are i.i.d. and geometrically distributed. For this queue, we establish the exact relationship between queue length distributions in a finite-buffer queue and the corresponding infinite-buffer queue. With the result, the exact loss probability is obtained in terms of the queue length distribution in the corresponding infinite-buffer queue. Note that this result enables us to compute the loss probability very efficiently, since the queue length distribution in the infinite-buffer queue can be efficiently computed when off-periods are geometrically distributed. This revised version was published online in June 2006 with corrections to the Cover Date.     

An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.