Single server with linear state-dependent mean rate

A birth-death queueing system with asingle server, first-come first-served discipline, Poisson arrivals and mean service rate which depends linearly on the number of customers in the system, is considered. Explicit expressions are derived for the equilibrium densities of the sojourn and waiting times. Simple approximations to the densities, including the first order correction terms, are obtained in a heavy-traffic situation.     

Two-server queue with one server idle below a threshold

A birth-death queueing system with two identical servers, first-come first-served discipline, and Poisson arrivals is considered. Only one of the servers is active when the number of customers in the system does not exceed a prescribed threshold, whereas both are active above the threshold. The problem of determining the equilibrium density of the waiting time is formulated. A generating function is given for the Laplace transform of the density of the waiting time, and it is pointed out that it leads to an explicit expression for this quantity. Explicit expressions are obtained for the first and second moments of the waiting and sojourn times, and they are compared with the corresponding quantities for a single-server system with the same state-dependent mean service rates.     

On the optimal control of a single-server queueing system: Further remarks

This comment is in response to a reply by Scott and Jefferson (Ref. 3) concerning the application of control theory to a queueing problem.     

Waiting times in a two-queue model with exhaustive and Bernoulli service

This paper deals with waiting times in a two-queue polling system in which one queue is served according to the Bernoulli service discipline and the other one attains exhaustive service. Exact results are derived for the LST's of the waiting time distributions via an iteration scheme. Based on those results the mean waiting times are expressed in the system parameters.     

Sojourn times in a processor sharing queue with service interruptions

We study the sojourn times of customers in an M/M/1 queue with the processor sharing service discipline and a server that is subject to breakdowns. The lengths of the breakdowns have a general distribution, whereas the on-periods are exponentially distributed. A branching process approach leads to a decomposition of the sojourn time, in which the components are independent of each other and can be investigated separately. We derive the Laplace–Stieltjes transform of the sojourn-time distribution in steady state, and show that the expected sojourn time is not proportional to the service requirement. In the heavy-traffic limit, the sojourn time conditioned on the service requirement and scaled by the traffic load is shown to be exponentially distributed. The results can be used for the performance analysis of elastic traffic in communication networks, in particular, the ABR service class in ATM networks, and best-effort services in IP networks.     

Joint distributions in Poissonian tandem queues

A pair of single server queues arranged in series is considered. The input flow is Poisson and service times are mutually independent and exponentially distributed in each station. The joint distributions of the stationary waiting times and queue lengths at the arrival epoch are treated.     

Workloads and waiting times in single-server systems with multiple customer classes

One of the most fundamental properties that single-server multi-class service systems may possess is the property of work conservation. Under certain restrictions, the work conservation property gives rise to a conservation law for mean waiting times, i.e., a linear relation between the mean waiting times of the various classes of customers. This paper is devoted to single-server multi-class service systems in which work conservation is violated in the sense that the server's activities may be interrupted although work is still present. For a large class of such systems with interruptions, a decomposition of the amount of work into two independent components is obtained; one of these components is the amount of work in the corresponding systemwithout interruptions. The work decomposition gives rise to a (pseudo)conservation law for mean waiting times, just as work conservation did for the system without interruptions.     

Queues with service times and interarrival times depending linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queue with unlimited waiting space and the first-in first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY _n+1=C _n Y _n +X _n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.     

Non-stationary waiting times in a closed exponential tandem queue

A closed exponential tandem queue in which every customer has to be served by two servers is considered. Given the numbers of customers lined up at each of the two servers, we derive the probability distributions of the waiting time of any customer until his second service is completed, and of the total busy time of the system.     

Transient and stationary waiting times in (max,+)-linear systems with Poisson input

We consider a certain class of vectorial evolution equations, which are linear in the (max,+) semi-field. They can be used to model several Types of discrete event systems, in particular queueing networks where we assume that the arrival process of customers (tokens, jobs, etc.) is Poisson. Under natural Cramér Type conditions on certain variables, we show that the expected waiting time which the nth customer has to spend in a given subarea of such a system can be expanded analytically in an infinite power series with respect to the arrival intensity λ. Furthermore, we state an algorithm for computing all coefficients of this series expansion and derive an explicit finite representation formula for the remainder term. We also give an explicit finite expansion for expected stationary waiting times in (max,+)-linear systems with deterministic queueing services. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stationary distributions in a queueing system with vacation times and limited service

This paper deals with a modified M/G/1 queueing system with finite capacity and a walking server. Units waiting are served up to a limited number before the server takes a vacation time and later returns to the queue again. A computational method for the stationary queue length distribution is developed and illustrated with a numerical example. The model was motivated by similar channel access mechanisms in token-ring local area networks.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

On Whitt's conjecture for queues in which service times and interarrival times depend linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queueing system with infinite waiting space and the first-in-first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. When the waiting-time distributions converge to a proper limit, Whitt [10] proposed a normal approximation for this steady-state limit. In this paper we prove a limit theorem for the steady-state limit of the system. Thus, our result provides a solid foundation for Whitt's normal approximation of the steady-state distribution of the system.Supported in part by a grant from the National Natural Science Foundation of China.     

Discrete-time queue with Bernoulli bursty source arrival and generally distributed service times

In this contribution, a discrete-time single-server infinite-capacity queue with correlated arrivals and general service times is investigated. Arrivals of cells are modelled as an on/off source process with geometrically distributed on-periods and off-periods, which is called Bernoulli bursty source. Based on the probability generating function technique, closed-form expression of some performance measures of system, such as average buffer content, unfinished work, cell delay and so on, are obtained. Finally, the effects of system parameters on performance measures are illustrated by some numerical examples.     

Small work-load mode in a queueing system with random nonstationary intensity

We consider a queueing system of M _t R|GI|1|∞ type with doubly stochastic Poisson arrival stream. The case of a small work load in such a system is studied. We derive an asymptotic expansion in the work-load smallness parameter of the distribution function of the virtual waiting time.     

Approximating queue size and waiting time distributions in general polling systems

Polling system models are extensively used to model a large variety of computer and communication networks as well as production and service systems in which multiple customer classes or a number of distinct items compete for the capacity of a common server or production facility. In this paper we describe an efficient approximation method for the steady state distributions of the queue sizes and waiting times. This method is highly accurate as demonstrated by an extensive numerical study. In addition, it is highly adaptable to a variety of arrival patterns and switching protocols, including exhaustive and gated regimes, simple cyclical systems as well as general polling tables. For a system withN stations, one finds the firstK probability density function values of the steady state queue size in any given station inO(max(N, K ²) time only. When executed on an IBM system RS/6000, we have observed an average CPU time of less than 1 second for systems with as many as 50 stations over a large variety of parameter settings.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

The waiting time distribution for a correlated queue with exponential interarrival and service times

We are concerned with the analysis of the waiting time distribution in an $M∕M∕1$ queue in which the interarrival time between the $n$th and the $(n+1)$th customers and the service time of the $n$th customer are correlated random variables with Downton’s bivariate exponential distribution. In this paper we show that the conditional waiting time distribution, given that the waiting time is positive, is exponential.     

Analyzing a degenerate buffer with general inter-arrival and service times in discrete time

In novel switching approaches such as Optical Burst Switching, the involved buffers can only provide a degenerate waiting room, with delays restricted to multiples of a basic value, the granularity. Although the resulting performance loss was already studied analytically, previous work is either limited by the assumption of independent arrivals, or it involves a matrix with size growing fast with buffer size or arrival process complexity. Overcoming this, we developed a generic and accurate loss performance model for a degenerate GI/G/1 buffer in discrete time, that yields results instantly for any constellation of burst sizes, inter-arrival times, granularity, load and buffer size. This paper presents our model and compares its results to simulations, illustrating the impact of different types of correlation in the arrival process on loss performance. Our basic model is general and accurate, it can thus serve as a basic tool for optical switch design.