A large-deviations analysis of Markov-modulated infinite-server queues

https://doi.org/10.1016/j.orl.2013.01.009Get rights and content

Abstract

This paper studies an infinite-server queue in a Markov environment, that is, an infinite-server queue with arrival rates and service times depending on the state of a Markovian background process. Scaling the arrival rates λi by a factor N, tail probabilities are examined when letting N tend to ; non-standard large deviations results are obtained. An importance-sampling based estimation algorithm is proposed, that is proven to be logarithmically efficient.

Introduction

Infinite-server queues have found widespread use in various application domains, often as an approximation for many-server models. While their original motivation may stem from communication networks engineering, where the so-called Erlang model records the dynamics of the number of calls in progress, applications in various other domains have been explored, such as road traffic [14] and biology [12].

In the standard model, jobs arrive according to a Poisson process with rate λ, where their service times form a sequence of independent and identically distributed (i.i.d.) random variables (distributed as a random variable B with finite first moment); the main result is that the stationary number of jobs in the system obeys a Poisson distribution with mean λEB. In many practical situations, however, the assumptions of a constant arrival rate and the jobs stemming from a single distribution are not realistic. A model that allows the input process to exhibit some sort of ‘burstiness’ is the Markov-modulated infinite server queue. In this model, a finite-state irreducible continuous-time Markov process (often referred to as the background process) modulates the input process: if the background process is in state i, the arrival process is a Poisson process with rate, say, λi, while the service times are distributed as a random variable, say, Bi.

The Markov-modulated infinite-server queue started to attract attention in recent years. The main focus in the literature so far has been on characterizing (through the derivation of moments, or even the full probability generating function) of the steady-state number of jobs in the system [3], [5], [9], [11]. Interestingly, under an appropriate time-scaling [2], [8] in which the transitions of the background process occur at a faster rate than the Poisson arrivals, we retrieve the Poisson distribution for the steady-state number of jobs in the system.

Less attention is paid to characterizing the probability that the number of customers in the Markov-modulated infinite-server queue attains some unusually high (or low) value. For the case that there is no Markov modulation, large-deviations analyses have been performed. In e.g. [6], [7] rare-event probabilities are considered for the stationary number of jobs in the system under renewal arrivals (that is, not necessarily Poisson arrivals). In [10], [13] the arrival rate λ is scaled by N, and sample-path large-deviations results are derived for the transient of the number of jobs in the system.

The main contribution of the present paper is a large-deviations analysis of the number of jobs in a Markov-modulated infinite server queue. We do so by scaling the arrival rates λi by N (that is, the arrival rate while in state i becomes Nλi), but leaving the time-scale of the background process unchanged.

After introducing our model in Section 2, Section 3 presents our main result: an expression for the exponential decay rate (in N) of the transient overflow probability, which is defined as the probability that the transient of the number of jobs in the system, denoted by M(N)(t), exceeds Na, for a given a larger than the limiting value of EM(N)(t)/N (which we call ϱt). Interestingly, under the scaling proposed, the decay rate of interest is affected by the arrival rates and service-time characteristics only; the transition rates of the background process do not play a role. In addition, it turns out that there is an a+ strictly larger than ϱt such that for a[ϱt,a+] there is subexponential decay (i.e., decay rate equaling 0), while for a>a+ the transient overflow probability does decay exponentially.

Then, in Section 4 it is pointed out how to evaluate the decay rate under consideration. We further explain the intuitive meaning of all quantities involved, in terms of the most likely way the rare event occurs. As it turns out, the large-deviations based logarithmic asymptotics provide insight into the order of magnitude of the transient overflow probability, but are too crude to provide an accurate approximation. To remedy this, we propose in Section 5 an efficient importance-sampling based simulation algorithm, which we prove to be logarithmically efficient.

Section snippets

Model description

As mentioned above, this paper studies an infinite-server queue with Markov-modulated Poisson arrivals and general service times. In full detail, the model is described as follows.

Consider an irreducible continuous-time Markov process (J(t))tR on a finite state space {1,,d}, with dN. Its rate matrix is given by (νij)i,j=1d, while πˆi denotes the invariant distribution of the corresponding jump process. The time Ti spent in state i (often referred to as the transition time) has an exponential

Large deviations

The main goal of the paper is to study the tail asymptotics of the number of jobs in the system at time t, given the system starts off empty at time 0. We do this by scaling the arrival rates by N, that is, we scale λiNλi; at the same time we leave the timescale of the background process unchanged.

Computational issues and numerical examples

In this section we focus on the computational issues related to the results of the previous section; for ease, we just consider the transient overflow probability, for a larger than κ(f+).

Finding f+(). It is straightforward to compute t1+ up to tk+, as follows. Focusing on the (exponential) case that P(Bi>ts)=eμi(ts), it is clear that i0f+(0)=argmaxi{1,,d}λieμit. Then compute the intersections sj of gs(i0) and gs(j) (for ji0): sj=tlogλi0logλjμi0μj. Pick the smallest positive one

Importance sampling

One could naïvely argue that our theory suggests the use of the approximation, for a>a+, P(M(N)(t)>Na)eNd(f+). As we know from the proof of Theorem 1, however, the decay rate d(f+) essentially follows from the most likely way the background process J() behaves to trigger the event that M(N)(t) exceeds Na. As a result, the above approximation eNd(f+) is likely to overestimate the transient overflow probability. Put differently, it is expected that N1logP(M(N)(t)>Na) converges slowly to d(f+).

References (14)

There are more references available in the full text version of this article.

Cited by (0)

View full text