Large deviation theory for queueing systems

Abstract

Consider a Markov jump process, X(t), with a nonnegative state space as a model for a queueing system. The motivation of this study is about useful estimates of system performance. For example, in a system with finite queues, the probability of the system of queues going from an empty state to a state in which the population of at least one queue reaches a large number before becoming empty again is one and the typical sample trajectory of this event is another. To answer these questions, we establish the large deviation principle (LDP) for an appropriate class of queueing processes. The model of our concern is the Jackson network which has a tree-type topological structure.

Under carefully designed conditions, the LDP for a time homogeneous Markov process has been well established by Wentzel. However, mainly due to the nonnegativity constraint, the queue length process, X(t), of our model does not satisfy the assumed conditions. As a detour, we define the “potential process”, Y(t), which allows the negativity in state space in the way that even if a queue is empty, the server in the empty queue is working with a same rate as if the queue is not empty. Therefore, each Y_i(t) can be expressed as the difference of the accumulated number of customers who came to station i and the accumulated number of services, done in station, i, up to time t. Then the scaled processes, Y^∊(t) = ∊Y(t/∊), obeys LDP with a certain rate function, I_[0,T](x,Φ), i.e.

P(Y^∊(.)∈ B|Y^∊(0) = x| ≈ exp[-1/∊ inf_Φ∊B I_[0,T](x,Φ)], (UTLE)

for some B ⊂ D^r[0,T] = { right continuous R^r — valued function which has a left limit at every point on [0,T]}. UTLE stands for ‘up to logarithmic equivalence’.

By defining an appropriate Skorohod problem, we obtain a continuous mapping θ from D^r to D^r₍₊₎,) such that θ(Y)(t) is a version of X(t). Then we “push the LDP of potential process through” θ so that LDP of the queue length process can be achieved. The procedure of ‘pushing through’ is another principle of the large deviation theory. It is called “contraction principle” [3]. The contraction principle provides the rate function J_[0,T] of the LDP for the queue length process and J_[0,T](Φ) = inf_ψ|θ(ψ)=Φ J_[0,T](ψ). That is, when X^∊ ≡ ∊X(t/∊), for an appropriate set B ⊂ D^r₍₊₎,

P(X^∊(.)∈ B|X^∊(0) = x| ≈ exp[-1/∊ inf_Φ∊B I_[0,T](x,Φ)], (UTLE)

The rate function, J_[0,T], is expressed in a closed form.