Queues with Service Rate Controlled by a Delayed Feedback

We consider a single queue with a Markov modulated Poisson arrival process. Its service rate is controlled by a scheduler. The scheduler receives the workload information from the queue after a delay. This queue models the buffer in an earth station in a satellite network where the scheduler resides in the satellite. We obtain the conditions for stability, rates of convergence to the stationary distribution and the finiteness of the stationary moments. Next we extend these results to the system where the scheduler schedules the service rate among several competing queues based on delayed information about the workloads in the different queues.     

Invariance relations in single server queues with LCFS service discipline

This paper is concerned with single server queues having LCFS service discipline. We give a condition to hold an invariance relation between time and customer average queue length distributions in the queues. The relation is a generalization of that in an ordinary GI/M/1 queue. We compare the queue length distributions for different single server queues with finite waiting space under the same arrival process and service requirement distribution of customer and derive invariance relations among them.This research was supported in part by a grant from the Tokyo Metropolitan Government. The latter part of this paper was written while the author resided at the University of California, Berkeley.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

Asymptotic behaviour of the loss probability of theM/G/1/K andG/M/1/K queues

This paper investigates the asymptotic behaviour of the loss probability of theM / G/1/K and G/M/1/K queues as the buffer size increases. It is shown that the loss probability approaches its limiting value, which depends on the offered load, with an exponential decay in essentially all cases. The value of the decay rate can be easily computed from the main queue parameters. Moreover, the close relation existing between the loss behaviour of the two examined queueing systems is highlighted and a duality concept is introduced. Finally some numerical examples are given to illustrate on the usefulness of the asymptotic approximation.     

Palm calculus for a process with a stationary random measure and its applications to fluid queues

We consider a process associated with a stationary random measure, which may have infinitely many jumps in a finite interval. Such a process is a generalization of a process with a stationary embedded point process, and is applicable to fluid queues. Here, fluid queue means that customers are modeled as a continuous flow. Such models naturally arise in the study of high speed digital communication networks. We first derive the rate conservation law (RCL) for them, and then introduce a process indexed by the level of the accumulated input. This indexed process can be viewed as a continuous version of a customer characteristic of an ordinary queue, e.g., of the sojourn time. It is shown that the indexed process is stationary under a certain kind of Palm probability measure, called detailed Palm. By using this result, we consider the sojourn time processes in fluid queues. We derive the continuous version of Little's formula in our framework. We give a distributional relationship between the buffer content and the sojourn time in a fluid queue with a constant release rate.     

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.     

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     

Transient solutions in Markovian queues: An algorithm for finding them and determining their waiting-time distributions

An algorithm for finding transient solutions in Markovian queues is given and it is applied to find transient solutions for the M/M/1 queue. This algorithm can also be applied to solve waiting-time problems as is shown by an example.     

The Maximum Queue Length for Heavy-Tailed Service Times in the M/G/1 FB Queue

This paper treats the maximum queue length M, in terms of the number of customers present, in a busy cycle in the M/G/1 queue. The distribution of M depends both on the service time distribution and on the service discipline. Assume that the service times have a logconvex density and the discipline is Foreground Background (FB). The FB service discipline gives service to the customer(s) that have received the least amount of service so far. It is shown that under these assumptions the tail of M is bounded by an exponential tail. This bound is used to calculate the time to overflow of a buffer, both in stable and unstable queues.     

Perturbation Analysis of the GI/M/s Queue

This paper investigates the M/M/s queueing model to predict an estimate for the proximity of the performance measures of queues with arrival processes that are slightly different from the Poisson process. Specifically, we use the strong stability method to obtain perturbation bounds on the effect of perturbing the arrival process in the M/M/s queue. Therefore, we build some algorithms based on strong stability method to predict stationary performance measures of the GI/M/s queue. Some numerical examples are sketched out to illustrate the accuracy of the proposed method.     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.     

Finite-Buffer Queues with Workload-Dependent Service and Arrival Rates

We consider M/G/1 queues with workload-dependent arrival rate, service speed, and restricted accessibility. The admittance of customers typically depends on the amount of work found upon arrival in addition to its own service requirement. Typical examples are the finite dam, systems with customer impatience and queues regulated by the complete rejection discipline. Our study is motivated by queueing scenarios where the arrival rate and/or speed of the server depends on the amount of work present, like production systems and the Internet.First, we compare the steady-state distribution of the workload in two finite-buffer models, in which the ratio of arrival and service speed is equal. Second, we find an explicit expression for the cycle maximum in an M/G/1 queue with workload-dependent arrival and service rate. And third, we derive a formal solution for the steady-state workload density in case of restricted accessibility. The proportionality relation between some finite and infinite-buffer queues is extended. Level crossings and Volterra integral equations play a key role in our approach.AMS subject classification: 60K25, 90B22     

Second moment relationships for waiting times in queueing systems with poisson input

For theM/G/1 queue there are well-known and simple relationships among the second moments of waiting time under the first-in-first-out, last-in-first-out, and random-order-of-service disciplines. This paper points out that these relationships hold in considerably more general settings. In particular, it is shown that these relationships hold forM/G/1 queues with exceptional first service,M/G/1 queues with server vacations, andM/G/1 queues with static priorities.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

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.     

Quasi-reversible multiclass queues with order independent departure rates

This paper introduces a new class of queues which are quasi-reversible and therefore preserve product form distribution when connected in multinode networks. The essential feature leading to the quasi-reversibility of these queues is the fact that the total departure rate in any queue state is independent of the order of the customers in the queue. We call such queues order independent (OI) queues. The OI class includes a significant part of Kelly's class of symmetric queues, although it does not cover the whole class. A distinguishing feature of the OI class is that, among others, it includes the MSCCC and MSHCC queues but not the LCFS queue. This demonstrates a certain generality of the class of OI queues and shows that the quasi-reversibility of the OI queues derives from causes other than symmetry principles. Finally, we examine OI queues where arrivals to the queue are lost when the number of customers in the queue equals an upper bound. We obtain the stationary distribution for the OI loss queue by normalizing the stationary probabilities of the corresponding OI queue without losses. A teletraffic application for the OI loss queue is presented.     

Duality relations for certain single server queues

In this paper, relations are given between the joint distribution of several variables in a GI/G/1 queue and the joint distribution of variables associated with the busy cycle in the dual queue, that is in the queue which results from the original when the interarrival times and the service times are interchanged. It is assumed that the primal queue has the preemptive-resume last-come-first-served queue discipline while the dual queue may have any queue discipline which is work conserving. These relations generalize a result given recently for M/G/1 and GI/M/1 queues.     

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.