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.     

On balking from an empty queue

The intuition while observing the economy of queueing systems, is that one’s motivation to join the system, decreases with its level of congestion. Here we present a queueing model where sometimes the opposite is the case. The point of departure is the standard first-come first-served single server queue with Poisson arrivals. Customers commence service immediately if upon their arrival the server is idle. Otherwise, they are informed if the queue is empty or not. Then, they have to decide whether to join or not. We assume that the customers are homogeneous and when they consider whether to join or not, they assess their queueing costs against their reward due to service completion. As the whereabouts of customers interact, we look for the (possibly mixed) join/do not join Nash equilibrium strategy, a strategy that if adopted by all, then under the resulting steady-state conditions, no one has any incentive not to follow it oneself. We show that when the queue is empty then depending on the service distribution, both ‘avoid the crowd’ (ATC) and ‘follow the crowd’ (FTC) scenarios (as well as none-of-the-above) are possible. When the queue is not empty, the situation is always that of ATC. Also, we show that under Nash equilibrium it is possible (depending on the service distribution) that the joining probability when the queue is empty is smaller than it is when the queue is not empty. This research was supported by The Israel Science Foundation Grant No. 237/02.     

Moment inequalities for the discrete-time bulk service queue

For the discrete-time bulk service queueing model, the mean and variance of the steady-state queue length can be expressed in terms of moments of the arrival distribution and series of the zeros of a characteristic equation. In this paper we investigate the behaviour of these series. In particular, we derive bounds on the series, from which bounds on the mean and variance of the queue length follow. We pay considerable attention to the case in which the arrivals follow a Poisson distribution. For this case, additional properties of the series are proved leading to even sharper bounds. The Poisson case serves as a pilot study for a broader range of distributions.     

Operating characteristics of MX/G/1 queue with N-policy

We consider aM ^X/G/1 queueing system withN-policy. The server is turned off as soon as the system empties. When the queue length reaches or exceeds a predetermined valueN (threshold), the server is turned on and begins to serve the customers. We place our emphasis on understanding the operational characteristics of the queueing system. One of our findings is that the system size is the sum of two independent random variables: one has thePGF of the stationary system size of theM ^X/G/1 queueing system withoutN-policy and the other one has the probability generating function _j=0 ^N=1 _j z ^j/ _j=0 ^N=1 _j , in which _j is the probability that the system state stays atj before reaching or exceedingN during an idle period. Using this interpretation of the system size distribution, we determine the optimal thresholdN under a linear cost structure.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

Approximations for the delay probability in the M/G/s queue

This paper develops approximations for the delay probability in an M/G/s queue. For M/G/s queues, it has been well known that the delay probability in the M/M/s queue, i.e., the Erlang delay formula, is usually a good approximation for other service-time distributions. By using an excellent approximation for the mean waiting time in the M/G/s queue, we provide more accurate approximations of the delay probability for small values of s. To test the quality of our approximations, we compare them with the exact value and the Erlang delay formula for some particular cases.     

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.     

Fluid approximations for a processor-sharing queue

In this paper a fluid approximation, also known as a functional strong law of large numbers (FSLLN) for a GI/G/1 queue under a processor-sharing service discipline is established and its properties are analysed. The fluid limit depends on the arrival rate, the service time distribution of the initial customers, and the service time distribution of the arriving customers. This is in contrast to the known result for the GI/G/1 queue under a FIFO service discipline, where the fluid limit is piecewise linear and depends on the service time distribution only through its mean. The piecewise linear form of the limit can be recovered by an equilibrium type choice of the initial service distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Equilibrium queueing strategies of two types of customers in a two-server queue

We consider a single queue with two identical servers and two types of customers. The high-type customer is more delay-sensitive but brings less workload to the system than the low-type customer. We obtain the equilibrium queueing strategy for each type of customers.     

The PH/PH/1 queue at epochs of queue size change

The PH/PH/1 queue is considered at embedded epochs which form the union of arrival and departure instants. This provides us with a new, compact representation as a quasi-birth-and-death process, where the order of the blocks is the sum of the number of phases in the arrival and service time distributions. It is quite easy to recover, from this new embedded process, the usual distributions at epochs of arrival, or epochs of departure, or at arbitrary instants. The quasi-birth-and-death structure allows for efficient algorithmic procedures. This revised version was published online in June 2006 with corrections to the Cover Date.     

On essential information in sequential decision processes

This paper provides sufficient conditions when certain information about the past of a stochastic decision processes can be ignored by a controller. We illustrate the results with particular applications to queueing control, control of semi-Markov decision processes with iid sojourn times, and uniformization of continuous-time Markov decision processes. Mathematics Subject Classification (2000): Primary 60K25, Secondary 90C40     

The serial correlation coefficients for waiting times in the stationary GI/M/m queue

Serial correlation coefficients are useful measures of the interdependence of successive waiting times. Potential applications include the development of linear predictors and determining simulation run lengths. This paper presents the algorithm for calculating such correlations in the multiserver exponential service queue, and relates it to known results for single server queues.     

Joint distributions of runs in a sequence of higher-order two-state Markov trials

Consider a time homogeneous {0, 1}-valued m-dependent Markov chain . In this paper, we study the joint probability distribution of number of 0-runs of length and number of 1-runs of length in n trials. We study the joint distributions based on five popular counting schemes of runs. The main tool used to obtain the probability generating function of the joint distribution is the conditional probability generating function method. Further a compact method for the evaluation of exact joint distribution is developed. For higher-order two-state Markov chain, these joint distributions are new in the literature of distributions of run statistics. We use these distributions to derive some waiting time distributions.     

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.     

Derivation of the probability distribution functions for succession quota random variables

The probability distribution functions (pdf's) of the sooner and later waiting time random variables (rv's) for the succession quota problem (k successes and r failures) are derived presently in the case of a binary sequence of order k. The probability generating functions (pgf's) of the above rv's are then obtained directly from their pdf's. In the case of independent Bernoulli trials, expressions for the pdf's in terms of binomial coefficients are also established.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic behavior of the loss probability for an M/G/1/N queue with vacations

In this paper, asymptotic properties of the loss probability are considered for an M/G/1/N queue with server vacations and exhaustive service discipline, denoted by an M/G/1/N-(V, E)-queue. Exact asymptotic rates of the loss probability are obtained for the cases in which the traffic intensity is smaller than, equal to and greater than one, respectively. When the vacation time is zero, the model considered degenerates to the standard M/G/1/N queue. For this standard queueing model, our analysis provides new or extended asymptotic results for the loss probability. In terms of the duality relationship between the M/G/1/N and GI/M/1/N queues, we also provide asymptotic properties for the standard GI/M/1/N model.     

A note on the optimality of the N- and D-policies for the M/G/1 queue

This note considers the N- and D-policies for the M/G/1 queue. We concentrate on the true relationship between the optimal N- and D-policies when the cost function is based on the expected number of customers in the system.