A large-deviations analysis of Markov-modulated infinite-server queues
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 with finite first moment); the main result is that the stationary number of jobs in the system obeys a Poisson distribution with mean . 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 , the arrival process is a Poisson process with rate, say, , while the service times are distributed as a random variable, say, .
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 , 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 by (that is, the arrival rate while in state becomes ), 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 ) of the transient overflow probability, which is defined as the probability that the transient of the number of jobs in the system, denoted by , exceeds , for a given larger than the limiting value of (which we call ). 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 strictly larger than such that for there is subexponential decay (i.e., decay rate equaling 0), while for 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 on a finite state space , with . Its rate matrix is given by , while denotes the invariant distribution of the corresponding jump process. The time spent in state (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 , given the system starts off empty at time 0. We do this by scaling the arrival rates by , that is, we scale ; 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 larger than .
Finding . It is straightforward to compute up to , as follows. Focusing on the (exponential) case that , it is clear that Then compute the intersections of and (for ): Pick the smallest positive one
Importance sampling
One could naïvely argue that our theory suggests the use of the approximation, for , As we know from the proof of Theorem 1, however, the decay rate essentially follows from the most likely way the background process behaves to trigger the event that exceeds . As a result, the above approximation is likely to overestimate the transient overflow probability. Put differently, it is expected that converges slowly to .
References (14)
- et al.
A large deviations approach to the transient of the Erlang loss model
Performance Evaluation
(2001) - et al.
Transcription stochasticity of complex gene regulation models
Biophysical Journal
(2012) - et al.
Stochastic Simulation
(2007) - J. Blom, O. Kella, M. Mandjes, H. Thorsdottir, Markov-modulated infinite server queues with general service times, 2012...
queues in semi-Markovian random environment
Queueing Systems
(2008)- et al.
Large Deviations Techniques and Applications
(1998) - et al.
An infinite-server queue influenced by a semi-Markovian environment
Queueing Systems
(2009)