Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

On the Shortest Queue Version of the Erlang Loss Model

We consider two parallel M / M / N / N queues. Thus there are N servers in each queue and no waiting line(s). The network is fed by a single Poisson arrival stream of rate λ, and the 2 N servers are identical exponential servers working at rate μ. A new arrival is routed to the queue with the smaller number of occupied servers. If both have the same occupancy then the arrival is routed randomly, with the probability of joining either queue being 1/2. This model may be viewed as the shortest queue version of the classic Erlang loss model. If all 2 N servers are occupied further arrivals are turned away and lost. We let  ρ=λ/μ  and   a = N /ρ= N μ/λ  . We study this model both numerically and asymptotically. For the latter we consider heavily loaded systems (ρ→∞) with a comparably large number of servers (   N →∞  with   a = O (1))  . We obtain asymptotic approximations to the joint steady state distribution of finding m servers occupied in the first queue and n in the second. We also consider the marginal distribution of the number of occupied servers in the second queue, as well as some conditional distributions. We show that aspects of the solution are much different according as   a > 1/2, a ≈ 1/2, 1/4 < a < 1/2, a ≈ 1/4  or  0 < a < 1/4  . The asymptotic approximations are shown to be quite accurate numerically.     

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     

The asymptotic variance rate of the output process of finite capacity birth-death queues

We analyze the output process of finite capacity birth-death Markovian queues. We develop a formula for the asymptotic variance rate of the form λ ^*+∑v _i where λ ^* is the rate of outputs and v _i are functions of the birth and death rates. We show that if the birth rates are non-increasing and the death rates are non-decreasing (as is common in many queueing systems) then the values of v _i are strictly negative and thus the limiting index of dispersion of counts of the output process is less than unity. In the M/M/1/K case, our formula evaluates to a closed form expression that shows the following phenomenon: When the system is balanced, i.e. the arrival and service rates are equal, is minimal. The situation is similar for the M/M/c/K queue, the Erlang loss system and some PH/PH/1/K queues: In all these systems there is a pronounced decrease in the asymptotic variance rate when the system parameters are balanced. Research supported in part by Israel Science Foundation Grant 249/02 and 454/05 and by European Network of Excellence Euro-NGI.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

Analysis of multiserver retrial queueing system: A martingale approach and an algorithm of solution

The paper studies a multiserver retrial queueing system withm servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit, and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed random variable with parameter μ₁. A time between retrials is exponentially distributed with parameter μ₂ for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability condition and studies a behavior of the limiting queue-length distributions as μ₂ increases to infinity. As μ₂→∞, the paper also proves the convergence of appropriate queue-length distributions to those of the associated “usual” multiserver queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length distribution of retrial systems, is provided. AMS 2000 Subject classifications: 60K25 60H30.     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

Some results on a generalized M/G/1 feedback queue with negative customers

This paper deals with a generalized M/G/1 feedback queue in which customers are either “positive" or “negative". We assume that the service time distribution of a positive customer who initiates a busy period is G _e (x) and all subsequent positive customers in the same busy period have service time drawn independently from the distribution G _b (x). The server is idle until a random number N of positive customers accumulate in the queue. Following the arrival of the N-th positive customer, the server serves exhaustively the positive customers in the queue and then a new idle period commences. This queueing system is a generalization of the conventional N-policy queue with N a constant number. Explicit expressions for the probability generating function and mean of the system size of positive customers are obtained under steady-state condition. Various vacation models are discussed as special cases. The effects of various parameters on the mean system size and the probability that the system is empty are also analysed numerically. AMS Subject Classification: Primary: 60 K 25 · Secondary: 60 K 20, 90 B 22     

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).     

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.     

Transient distributions of level dependent quasi-birth-death processes with linear transition rates

Many queueing systems such asM/M/s/K retrial queue with impatient customers, MAP/PH/1 retrial queue, retrial queue with two types of customers andMAP/M/∞ queue can be modeled by a level dependent quasi-birth-death (LDQBD) process with linear transition rates of the form λ_k = α+ βk at each levelk. The purpose of this paper is to propose an algorithm to find transient distributions for LDQBD processes with linear transition rates based on the adaptive uniformizaton technique introduced by van Moorsel and Sanders [11]. We apply the algorithm to some retrial queues and present numerical results.     

Power series approximations for two-class generalized processor sharing systems

We develop power series approximations for a discrete-time queueing system with two parallel queues and one processor. If both queues are nonempty, a customer of queue 1 is served with probability β, and a customer of queue 2 is served with probability 1−β. If one of the queues is empty, a customer of the other queue is served with probability 1. We first describe the generating function U(z ₁,z ₂) of the stationary queue lengths in terms of a functional equation, and show how to solve this using the theory of boundary value problems. Then, we propose to use the same functional equation to obtain a power series for U(z ₁,z ₂) in β. The first coefficient of this power series corresponds to the priority case β=0, which allows for an explicit solution. All higher coefficients are expressed in terms of the priority case. Accurate approximations for the mean stationary queue lengths are obtained from combining truncated power series and Padé approximation.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

Large number of queues in tandem: Scaling properties under back-pressure algorithm

We consider a system with N unit-service-rate queues in tandem, with exogenous arrivals of rate λ at queue 1, under a back-pressure (MaxWeight) algorithm: service at queue n is blocked unless its queue length is greater than that of the next queue n+1. The question addressed is how steady-state queues scale as N→∞. We show that the answer depends on whether λ is below or above the critical value 1/4: in the former case the queues remain uniformly stochastically bounded, while otherwise they grow to infinity.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/∞ system revisited: finiteness,summability, long range dependence,and reverse engineering

We explore M/G/∞ systems ‘fed’ by Poissonian inflows with infinite arrival rates. Three processes – corresponding to the system's state, workload, and queue-size – are studied and analyzed. Closed form formulae characterizing the system's stationary structure and correlation structure are derived. And, the issues of queue finiteness, workload summability, and Long Range Dependence are investigated. We then turn to devise a ‘reverse engineering’ scheme for the design of the system's correlation structure. Namely: how to construct an M/G/∞ system with a pre-desired ‘target’ workload/queue auto-covariance function. The ‘reverse engineering’ scheme is applied to various examples, including ones with infinite queues and non-summable workloads. AMS Subject Classifications Primary: 60K25; Secondary: 60G55, 60G10     

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.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

Asymptotic Analysis of Two Coupled Queues with Vastly Different Arrival Rates and Finite Customer Capacities

We consider two coupled queues, with each having a finite capacity of customers. When both queues are nonempty they evolve independently, but when one becomes empty the service rate in the other changes. Such a model corresponds to a generalized processor sharing (GPS) discipline. We study the joint distribution p(m, n) of finding (m, n) customers in the (first, second) queue, in the steady state. We study the problem in an asymptotic limit of “heavy traffic,” where also the arrival rate to the second queue is assumed to be small relative to that of the first. The capacity of the first queue is scaled to be large, while that of the second queue is held constant. We consider several different scalings, and in each case obtain limiting differential and/or difference equation for p(m, n), and these we explicitly solve. We show that our asymptotic approximations are quite accurate numerically. This work supplements previous investigations into this GPS model, which assumed infinite capacities/buffers. The present model corresponds to a random walk in a lattice rectangle, where p(m, n) satisfies a different boundary condition on each edge.