Multiclass many-server queues in the Halfin-Whitt (H-W) regime have been extensively studied as a useful model for large-scale service systems. In this paper, we focus on ergodic properties of such multiclass queuing models. The ergodic properties of these systems have been the subject of great interest in applied probability (Dai and He [15], Gamarnik and Stolyar [20], Stolyar [32], Stolyar [33], Stolyar and Yudovina [34], Stolyar and Yudovina [35]). It is important to understand if a queuing system is stable and the rate at which a performance measure converges to the steady state under different scheduling or routing policies. For the multiclass V-network, Gamarnik and Stolyar [20] prove the tightness of the stationary distributions of the diffusionscaled state processes under any work-conserving scheduling policy, provided that there is ̅̅ n √ safety staffing (n is the scaling parameter). They show that the diffusion-scaled queuing processes are ergodic under all workconserving scheduling policies and have exhibited exponential tail bounds for the stationary distribution. The proofs of these significant results use some natural test functions based on the total workload, but there is no uniform Foster-Lyapunov equation to exhibit the rate of convergence to the stationary distribution. For the limiting diffusion of the V-network, when the control equals (0, . . . , 0, 1) T , which arises as the limit of a static priority policy, the ergodic properties established in Dieker and Gao [17] for a class of piecewise Ornstein-Uhlenbeck (O-U) processes arising in many-server queues with phase-type service times can be applied. Exponential ergodicity is also established for the limiting diffusion (as a special case of a more general class of stochastic differential equations (SDEs)) under any constant control in Arapostathis et al. [9].
The following important open questions are addressed in this paper: 1. Is the limiting controlled diffusion exponentially ergodic under all stationary Markov controls? How different are the tail asymptotics of the invariant measures with or without abandonment?
2. Is there a unified approach based on Foster-Lyapunov theory that can be used to establish uniform exponential ergodicity for both the limiting diffusion and the diffusion-scaled queuing processes?
We provide affirmative answers to all these questions. We consider multiclass models with (delayed) renewal arrivals, class-dependent exponential service times, and class-dependent exponential patience times. We assume that the system is operating under work-conserving and preemptive scheduling policies. It is well known that the diffusion-scaled queuing processes under such scheduling policies converge weakly to a limiting diffusion with a drift given in Section 2.2 and a diagonal constant covariance matrix (Atar et al. [10], Harrison and Zeevi [26]).
We start with the limiting controlled diffusion. When the controls are constant, the limiting diffusion has a piecewise linear drift and belongs to a class of piecewise O-U processes. Applying Dieker and Gao [17, theorem 3] to our model with positive abandonment rate, one can deduce that the limiting diffusion is exponentially ergodic under a specific constant control corresponding to a static priority scheduling policy (Remark 1). By contrast, it is shown in Arapostathis et al. [9, theorem 3.5] that the limiting diffusion is exponentially ergodic under any constant control (Remark 2). The proofs of these results rely on the construction of a common quadratic-type Lyapunov function for the piecewise linear equations. However, this methodology only works for constant controls and leaves the question of stability over Markov controls open.
We exploit Lyapunov functions that are constructed in an intricate manner in order to capture both the total workload on the positive half-space and the idleness on the negative half-space. Such functions are, of course, quite natural and have been used as test functions in Gamarnik and Stolyar [20] to derive tail bounds. However, for the diffusion, the total workload and idleness need to be treated with the proper weights or tilting, interacting with a smoothing cutoff function that needs to be deployed. Such delicate care is not only needed for the drift as usual but, more important, also for the second-order derivatives. For multiclass queuing models in the H-W regime, such constructions appear to be necessary to deal with both the workload and idleness processes simultaneously. This constitutes our first main methodologic contribution in this paper.
We present Foster-Lyapunov equations that are uniform over all Markov controls and show that a. If the spare capacity parameter (safety staffing) is positive, then the limiting diffusion is uniformly exponentially ergodic, and the corresponding invariant probability measures have uniform exponential tails, and b. When the abandonment rates are all positive, regardless the spare capacity parameter being positive or negative, in addition to uniform exponential ergodicity, we show that the invariant probability measures have sub-Gaussian tails. These answer important question 1 posed earlier.
We then show that the Foster-Lyapunov equations for the limiting diffusion offer a very natural tool with which we establish uniform ergodic properties for the diffusion-scaled queuing processes. This answers important question 2 posed earlier. In this manner, we provide a unified approach to the study of limiting diffusion and the corresponding diffusion-scaled processes.
In the case of Poisson arrivals, by employing the same Lyapunov functions used for the limiting diffusion, we show that the corresponding results in (a) hold for the diffusion-scaled queuing processes (see also Section 2.3). Sub-Gaussian tails are not possible for the invariant distribution of the diffusion-scaled queuing processes, and one can only hope for tails that decay faster than any exponential. By contrast, when the abandonment rates are all positive, we improve somewhat on the results in Gamarnik and Stolyar [20], although a conjecture stated in that paper still remains open. Although in the cases of Poisson and renewal arrivals the limiting diffusions agree, with the only differences lying in the covariance functions, for the analysis of the prelimit processes, we need to augment the state process in the renewal case.
With renewal arrivals, we consider the Markov process composed of the diffusion-scaled queuing processes and the interarrival age processes of the renewal arrivals. The Lyapunov functions used for the limiting diffusion are adapted to construct appropriate Lyapunov functions for the joint processes. By contrast, the hazard-rate functions and mean residual lifetime functions of the interarrival times also must be used in a proper manner to take into account the age processes, as suggested in Konstantopoulos and Last [28]. We prove the following results under the assumption that the residual lifetime function is bounded: a'. If the spare capacity parameter (safety staffing) is positive, we prove a Foster-Lyapunov equation, which shows that the joint Markov process is positive Harris recurrent under any work-conserving stationary Markov scheduling policy, and b'. If the abandonment rates are all positive, we obtain a Foster-Lyapunov equation that shows that the first absolute moments of the invariant distribution are uniformly bounded. If we impose the additional assumption that the hazard-rate function is bounded, we show that the marginal of the stationary distribution corresponding to the queuing state has exponential moments.
This work also relates to the vast literature on the validity of diffusion approximations for queues in heavy traffic. We focus on the literature of many-server queuing models in the H-W regime and refer readers to Braverman et al. [13], Budhiraja and Lee [14], Gamarnik and Zeevi [21], Gurvich [23], Katsuda [27], Ye and Yao [37], and Ye and Yao [38] and references therein for results in the conventional (single-server) heavytraffic regime. For single-class GI/M/n queues, Halfin and Whitt [25] established the interchange of limits, and they used a bounding argument via single-server queues to show the tightness of the steady-state distributions of the diffusion-scaled processes. Dai et al. [16] studied the validity of multidimensional diffusion approximations for GI/Ph/n + M queues with phase-type service times. Aghajani and Ramanan [1] proved the convergence of stationary distributions of suitably scaled infinite-dimensional measure-valued processes for GI/GI/N queues in the H-W regime, and they also studied the ergodic properties of the stochastic partial differential equation (SPDE) limit of the same model in Aghajani and Ramanan [2]. We also refer readers to the steady-state analysis of many-server queues in Braverman and Dai [11], Braverman et al. [12], Gamarnik and Goldberg [18], and Gamarnik and Momčilović [19]. All these studies are on single-class many-server queues. For multiclass many-server queues in the H-W regime, this topic still remains wide open. The only known result is for the Markovian N-network (Stolyar [33]), where Stolyar proves the interchange of limits for the model without abandonment under a particular static priority policy.
Uniform exponential ergodicity can substantially simplify the study of ergodic control problems because there is a rich body of existing theory that can be applied (Arapostathis et al. [7, chapter 3]). By contrast, if the system is not endowed with such blanket stability properties, and the running cost functional is not nearmonotone, then the analysis of these problems can be quite involved. In the study of ergodic control of the V-network in Arapostathis et al. [6], a key structural property of the system dynamics had to be identified because of the lack of uniform stability and near-monotonicity of the running cost. It was assumed that all the abandonment rates are strictly positive, but no positive safety staffing requirement was imposed. The results in this paper enable the study of ergodic control problems for the V-network when there is no abandonment but there is positive safety staffing. Uniform stability properties are yet to be explored for multiclass multipool networks. Without such blanket stability properties, ergodic control problems for multiclass multipool networks have been recently studied by Arapostathis and Pang [3], Arapostathis and Pang [4], and Arapostathis and Pang [5] under the hypothesis that at least one abandonment rate is positive.
We summarize some of the notation used throughout this paper. We use R m (and R m + ), m ≥ 1, to denote realvalued m-dimensional (nonnegative) vectors and write R for m 1. For x, y ∈ R, we let x ∨ y max{x, y}, x ∧ y min{x, y}, x + max{x, 0}, and x -max{-x, 0}. For a set A ⊆ R m , we use A c , ∂A, and 1 A to denote the complement, the boundary, and the indicator function of A, respectively. A ball of radius r > 0 in R m around a point x is denoted by B r (x) or, simply, as B r if x 0. We also let B ≡ B 1 . The Euclidean norm on R m is denoted by | • |, and • , • stands for the inner product. Also, for x ∈ R m , we let x 1 :
x max : max i x i , and x min : min i x i , and
where B(R m ) denotes the class of Borel measurable functions on R m . Observe that • 1 • TV , the latter denoting the total variation norm.
In Section 2.1, we describe the limiting diffusion and proceed with a summary of the results and technical approach in Sections 2.2 and 2.3, respectively. Some important definitions are in Section 2.4, followed by the main technical results in Sections 2.5 and 2.6.
We consider a controlled m-dimensional SDE of the form
) is a positive diagonal matrix; and Γ diag(γ 1 , . . . , γ m ) with γ i ∈ R + , i ∈ I : {1, . . . , m}. The process W t is a standard m-dimensional Brownian motion, and the covariance function σ : R m → R m×m is a positive diagonal matrix. Such a process arises as a limit of the suitably scaled queuing processes of multiclass Markovian many-server queues in the H-W regime (Atar et al. [10], Harrison and Zeevi [26]).
In these models, if the scheduling policy is based on a static priority assignment on the queues, then the vector u in (2) corresponds to a constant control that is an extreme point of the convex set
Remark 1. As mentioned earlier, ergodicity and exponential ergodicity of a class of piecewise O-U processes as in ( 2) have been addressed in Dieker and Gao [17]. In this model, they assume that M is a nonsingular M-matrix such that the vector e T M has nonnegative components, Γ αI, and -βu for positive constants α, β, and a constant vector u ∈ ∆. Applying their results to the multiclass M/M/n + M model with abandonment, exponential ergodicity of the limiting diffusion under the specific constant control ū (0, . . . , 0, 1) T , corresponding to class m being given the least priority, is established in Dieker and Gao [17, theorem 3]. By contrast, for the multiclass M/M/n model without abandonment, that is, Γ 0, positive recurrence is established for the limiting diffusion with the control ū, but the rate of convergence is not identified (Dieker and Gao [17,theorem 2]).
Remark 2. The model in (2) with M a nonsingular M-matrix and for constant control U t has also been studied extensively by Arapostathis et al. [9] (as a special class of the Lévy-driven SDEs studied there). It is shown in that paper that when Γ 0, the quantity
) plays a fundamental role in the characterization of stability. Specifically, it is shown in Arapostathis et al. [9, theorem 3.2] that if > 0, then X t is positive recurrent under any constant control U t , and if < 0 ( 0), then it is transient (cannot be positive recurrent) under any stationary Markov control satisfying Γv(x) 0 almost everywhere (a.e.) (Arapostathis et al. [9, theorem 3.3]). Another interesting property of that we find in Arapostathis et al. [9, corollary 5.1] is that provided that Γ 0 and the diffusion under some stationary Markov control v is positive recurrent with invariant probability measure π v , then necessarily
This can be interpreted as follows: the average idleness in the steady state always equals the spare capacity parameter. These results, of course, apply to the problem at hand because M is a diagonal matrix. In addition, the rate of convergence is shown to be exponential if either Γu 0 or Γu 0 for any constant control u ∈ ∆ (Arapostathis et al. [9, corollary 4.2]).
Let U sm denote the class of Borel measurable maps v : R m → ∆. Every element v of U sm is identified with the stationary Markov controls U t v(X t ). Under any such control, it is well known that (2) has a unique strong solution that is a strong Feller process (Gy öngy and Krylov [24]). Let P v t (x, dy) denote its transition probability. The diffusion in (2) is called uniformly stable (in the sense of Arapostathis et al. [7], definition 3.3.3]) if, under any v ∈ U sm , the process X t is positive recurrent, and the collection of invariant probability measures is tight. We say that (2) is uniformly exponentially ergodic if it is uniformly stable and there exist positive constants C and γ and a function V : R m → [1, ∞) such that
and all v ∈ U sm .
In Theorem 1, we show that if > 0, then (2) is uniformly exponentially ergodic. Therefore, when Γ 0, (5) holds over all stationary Markov controls v ∈ U sm . In addition, the invariant probability measures have uniform exponential tails, and by that, we mean that there exists some ε > 0 such that sup v∈U sm ∫ R m e ε|x| π v (dx) < ∞. By contrast, if Γ > 0, then the associated invariant probability measures have sub-Gaussian tails; that is, sup v∈U sm ∫ R m e ε|x| 2 π(dx) < ∞ for some ε > 0 (see Theorem 2). In Section 3, we address the n-server networks. We first present the results for the models with (delayed) renewal arrival processes in Section 3.2. The counterpart of Theorem 1 here is given in Theorem 4, and this is established for renewal arrivals (this should be compared with Gamarnik and Stolyar [20, theorem 2]). In this theorem, the hazard-rate functions are assumed to be bounded. This is a rather strong assumption, but the result, which asserts uniform exponential tails for the invariant distributions under work-conserving stationary Markov policies, is equally strong. With strictly positive abandonment parameters, and with the hazard-rate function only locally bounded, we establish uniform stability of the queuing system under all work-conserving stationary Markov policies in Theorem 5. With possibly zero abandonment in all classes, and with positive ̅̅ n √ safety staffing, we show in Theorem 6 that the combined renewal age and queuing state process is positive Harris recurrent. In addition, if the limit of the safety staffing is positive, the invariant probability distributions are tight. In this result, the hazard-rate function is assumed to be only locally bounded.
Networks with Poisson arrivals are studied in Section 3.3. We show in Corollary 2 that positive spare capacity implies exponential ergodicity. However, as noted in Gamarnik and Stolyar [20], the invariant distribution of an n-server network cannot have a sub-Gaussian tail. This property is recovered only at the weak limit as n → ∞, and it is worthwhile comparing Gamarnik and Stolyar [20, theorem 4] with Theorem 2, which in addition shows uniform exponential ergodicity. When all abandonment rates are positive, we can only exhibit a stronger Foster-Lyapunov equation (see Theorem 7), which implies that e δ|x| is uniformly integrable over the invariant probability distributions for any δ > 0.
In addition to these results, we investigate the properties in Gamarnik and Stolyar [20, theorems 2(i) and 4(i)]. We provide proofs of the analogous results for the limiting diffusion in Lemma 2 and Theorem 4, respectively, using Foster-Lyapunov techniques. The counterpart of Lemma 2 for the n-system is given in Theorem 8 and is an improvement over the statement in Gamarnik and Stolyar [20, theorem 2(i)]. However, we have not been able to prove or disprove the related conjecture in Gamarnik and Stolyar [20, p. 33].
The first important step in the study of this problem is the construction of appropriate Lyapunov functions. We use two building blocks for these functions: one represents the total workload, and the other is a measure of idleness. The scaling of these in (10) plays a crucial role. Two scaling parameters are used: θ to balance the mix of workload and idleness and ε to handle the terms arising from the second derivatives in the extended generator of the controlled diffusion. Equally important are the cones in Definition 1. Although the drift of the diffusion is piecewise linear when the control is constant, it becomes quite complicated under a (stationary) Markov control. Careful analysis of the drift of the diffusion in (3) on these cones enables us to obtain the drift inequalities and Foster-Lyapunov equations in Lemma 1 and Theorems 1 and 2. The more specialized results in Section 2.6 involve Lyapunov functions that are sums of two exponentials.
The relation between the prelimit dynamics and the limiting diffusion can be described as follows. For a model with Poisson arrivals, the process { Xn (t)} t≥0 describing the (diffusion-scaled) total number of jobs in the system is a controlled Markov process with generator (see ( 68) and ( 93))
) .
Here the vector z (z 1 , . . . , z m ) ∈ Z1 m + is the control parameter, with z i denoting the number of jobs of class i in service; {λ n i } i∈ I , {µ n i } i∈ I , and {γ n i } i∈ I are the arrival, service rates, and abandonment rates, respectively; and q (q 1 , . . . , q m ) is the vector of queue sizes. Using the diffusion-scaled variables ẑn and qn defined in (63) as
and qn i :
As shown in (88), for any work-conserving job allocation z ∈ Z1 m + , there exists a vector u ∈ ∆ such that ẑn x -e, x + u and qn e, x + u. Using these identities in (6) and letting n → ∞, we obtain the generator of the controlled diffusion in (2) (see also Remark 3). There is some difficulty, however, with translating the Foster-Lyapunov equation for the diffusion into an analogous equation for the operator Ân z . This is because whereas ẑn is of order ̅̅ n √ , the queue sizes qn are not bounded. We circumvent this problem by establishing drift inequalities in Lemma 1 for the truncated drift given in (15). This facilitates using the same Lyapunov function for the stability analysis of the diffusion and the prelimit, and consequently, we have a unified approach to the problem.
When studying the diffusion-scaled model with renewal arrivals, the Lyapunov function has to be augmented to account for the age processes (see (64)). The analysis is more intricate in this case, and deriving the Foster-Lyapunov equations in Theorem 4 requires extra care.
Remark 3. If we let ζ m e + M -1 , with as in (4), then a mere translation of the origin of the form Xt X tζ results in a diffusion of form (2) with the constant in the drift taking the form m Me. Therefore, without loss of generality, we assume throughout this paper that the drift in (3) takes the form
For f ∈ C 2 (R m ) and u ∈ ∆, we define a(x) (a ij (x)) 1≤i,j≤m : σ(x)σ(x) T and
with ∇ 2 f denoting the Hessian of f .
We start with two definitions.
Definition 1. For δ ∈ [0, 1], we define the following cones:
Note that K + 0 (K - 0 ) is the nonnegative (nonpositive) canonical half-space and that K + 1 (K - 1 ) is the nonnegative (nonpositive) closed orthant. Also, we have the following identities:
We fix some convex function ψ ∈ C 2 (R) with the property that ψ(t) is constant for t ≤ -1 and ψ(t) t for t ≥ 0. This is defined by
For ε > 0, we define
and thus ψ ε (t) εt for t ≥ 0. A simple calculation also shows that ψ ε (t) ≤ 3 2 ε 2 .
Definition 2. We let β i :
With θ and ε positive constants, we define
The function Ψ plays a fundamental role in our analysis. The quantity Ψ(x + ) represents, of course, the total workload, whereas Ψ(x -) is a measure of idleness. These functions, without the smooth cutoff part, are also used in Gamarnik and Stolyar [20] as test functions to estimate the tails of the invariant distribution of the prelimit diffusion-scaled processes.
The function Ψ * ε,θ follows the norm • 1 in the sense that ε 1∧θ
We also have ψ (-1/2) 1/2, from which we obtain
, and -
Note also that
Using the parameter β i in Definition 2 and (7), we write the following identities, which we use frequently in the rest of this paper:
The following lemma presents some important drift inequalities that are used frequently throughout this paper. Recall the definitions in (10). In order to apply the drift inequalities for the diffusion to the prelimit in Section 3, we often need to truncate the diffusion-scaled queuing processes. To prepare for this, we present a more general version of these inequalities than what is needed in this section.
Lemma 1. Assume that > 0, and let θ be a positive constant satisfying
Then the function
satisfies, for any constant Proof. The bound on K - 0 follows by first multiplying (14b) by εθ and then adding this equation to (14a) and using (12).
We proceed to derive the stated bound on
that is, it is equal to the right-hand side of (14b) for any c ≥ 1, because ψ (-r) 0 for r ≥ 1. We write
It holds that
Also, by ( 12), we have
and
by ( 14). Thus, if β max ≤ 1, then it is clear from (14a) and ( 19)- (22), that ( 18) holds for any positive ε and θ.
Next, suppose that β max > 1. We proceed by carefully comparing the terms in (19). Define
Because θ(β max -1) + ≤ 1 and β i > 1 on Î, we have
By the definitions in ( 23), we have the identity
Using again the fact that ψ (-r) 0 for r ≥ 1, we obtain
for all (x, u) ∈ K + 0 × ∆. In the second inequality of ( 26), we used the fact that θ(β max -1) + ≤ 1, and in the third equality we used (25). Multiplying ( 24) by e, x + , adding it to (26), and then combining the resulting sum with the inequality
where Îc denotes the complement of Î with respect to I, we obtain
Replacing the term -ε e, x + in ( 27) with -∑ i∈ I ψ ε (x i )x i preserves this inequality by (13). Thus, by (14b), ( 19)- (21), and ( 27), we obtain
from which the second bound in (18) follows. This completes the proof. □
Recall the definitions in ( 1) and ( 8). Also recall that π v denotes the invariant probability measure of the process governed by ( 2) for a control v ∈ U sm , under which {X(t)} t≥0 is positive recurrent.
Theorem 1. Assume that > 0, and in addition to (16), let
Then the following hold: a. There exists ε 0 > 0 such that for each ε ≤ ε 0 , the function V in (17) satisfies the Foster-Lyapunov equation
for some positive constant κ 0 , which depends only on ε and θ. In particular, the process {X(t)} t≥0 is positive recurrent under any control v ∈ U sm , and
b. There exist positive constants γ and C γ such that
Proof. Recall the definitions in (10) and also define
Write the diffusion matrix as σ diag(2 λ1 , . . . , 2 λm ) 1/2 . For the queuing network, λi
, where λ i is the arrival rate (of the fluid limit), and c 2 a,i is squared coefficient of variation of the renewal arrival process (see Section 3.1). In the case of a system with Poisson arrivals, λi λ i , as in (6). See Section 3.1 for the definition of these parameters. We have
Recall that ψ ε ≤ 3 2 ε 2 . Therefore, because also ψ ε ≤ ε, θ ≤ 1, and
We also have θ + θ m 2 ≤ 6m and 3 2 θ ≤ 4m by (28). Thus, (29) follows from ( 18) by selecting ε < 6m(3+2C) , whereas (30) follows by ( 29) and Itô's formula in the usual manner.
We now turn to part (b). Write (29) as
We follow the proof of Meyn and Tweedie [29, theorem 6.1], which uses a δ-skeleton chain {X δn } n∈N . We can use any δ > 0 because P v δ (x, B) > 0 for any set B with positive Lebesgue measure. Thus, for simplicity, we use δ 1. Then, with t n + s, s ∈ [0, 1), we have
Next, we estimate
Therefore, with B a ball such that
which establishes equation ( 14) in Meyn and Tweedie [30].
The inequality in (30) implies that the collection of invariant probability measures {π v :v ∈ U sm } is tight. By the invariance of π v , tightness, and the Harnack inequality applied to the densities of π v (see Arapostathis et
for some constant β 0 independent of v ∈ U sm . Using tightness once more, we can select a ball B R ⊃ B such that
This implies that sup y∈B R P v 1/2 (y, B) ≥ β 0 2 . We now use the parabolic Harnack inequality for operators in nondivergence form (Gruber [22,theorem 4.1]; for a simpler statement that uses the notation in this paper, see Arapostathis et al. [8, theorem 4.7]). The parabolic Harnack inequality asserts that there exists a positive constant C H such that sup
H β 0 for all x ∈ B and v ∈ U sm . Thus, with δ 0 : 1 4 C -1 H β 0 , we can write
which establishes equation (23) in Meyn and Tweedie [30].
As seen then in Meyn and Tweedie [30, theorem 2.3, equations (19), (20), and ( 24)-( 25)], there exist positive constants C 0 and γ depending only on κ 0 , κ 1 , η, and δ 0 such that
Thus, using (36) in (34) and applying (35) once more, we obtain (31) for a constant C γ independent of v ∈ U sm . This completes the proof. □ Throughout this paper, we let K r , or K(r), for r > 0, denote the closed cube
We also let ψ ε ψ ε + 1 so that the function is strictly positive and define Ψ and Ψ ε analogously to (10).
Remark 4. Assume that > 0, and consider the function
for some p ≥ 1. Then it follows directly from the proofs of Lemma 1 and Theorem 1 that there exist positive constants ε, θ, κ 0 , and κ 1 and a cube K ⊂ R m depending only on p such that
In Theorem 2, we do not assume that > 0.
Theorem 2. Assume that Γ > 0. With C as defined in (32), let
β max and ε 0 :
Then, for any ε ≤ ε 0 , the function
( ) satisfies the Foster-Lyapunov equation
for a positive constant κ0 that depends only on ε and the system parameters. In particular, the process X t governed by ( 2) is uniformly exponentially ergodic, and the associated invariant probability measures have sub-Gaussian tails.
Proof. We borrow some calculations from the proof of Lemma 1. Using (25) and scaling this with the new definition of θ in (39), we have
Here is not necessarily positive, so by ( 12), we have
Thus, using (12), we have
Let θ: θ ∧ β min (β min ∧ 1 2 ). Adding (41)-(43), using (14a) and (14b) and also (11), we obtain
where
It is straightforward to verify that (44) is also valid on K - 0 × ∆. Following the proof of Theorem 1, we have trace a∇ 2 Ṽ x ( )
Combining ( 44) and (45), we obtain trace a∇ 2 Ṽ x ( )
from which the validity of (40) on K + 0 × ∆ follows by selecting ε sufficiently small. Verifying the validity of (40) on K - 0 × ∆ is simpler and is a straightforward application of ( 11), (12), and (45). This finishes the proof. □ Remark 5. The counterpart of Remark 4 applies relative to Theorem 2. In particular, the function V in (38) for p > 0 is a Lyapunov function. Indeed, there exist positive constants ε, θ, κ0 , and κ1 and a cube K ⊂ R m depending only on p such that
Remark 6. It is worth noting that if Γ > 0, then, by choosing θ > 0 as in (39), the function
for all η > 0 and for some positive constants κ0 and κ1 depending only on η. Indeed, using (14a), (14b), and (41), we deduce, with θ:
where we also used ( 12) and ( 13). The rest is routine. By contrast, we have
by (51). Equations ( 52) and ( 53), together with ( 29) and (50), imply that
The estimate on K - 0 is straightforward. Indeed, (48) shows that V 1 satisfies this estimate, and (29) asserts the same for V. This completes the proof. □
The following is immediate from Lemma 2.
Corollary 1. Suppose that > 0. Then the function exp(η
) is integrable under the invariant distribution for any η > 0.
In Gamarnik and Stolyar [20, theorem 4(i)], it is shown that if ν is any limit of the invariant distributions of the diffusion-scaled queuing processes, then there exists some θ such that f (x) exp(θ
) is integrable under ν. As is pointed out in Gamarnik and Stolyar [20], this property holds only at the function f is not integrable under the stationary distribution of the prelimit model. The proof is rather tedious and is approached via truncations (see Gamarnik and Stolyar [20,proposition 12]). In what follows, we provide a simple proof of this result by showing that this property holds for the limiting diffusion.
Recall the definitions in ( 46) and (47).
Theorem 3. Assume that > 0, and let
with ε 0 and θ chosen as in Lemma 2. Then there exists η > 0 such that the function V: Ṽη V satisfies
Proof. As in (48), we have
Hη x ( ) :
Note that Hη (x) ≤ c 0 η 2 + c 1 η 4 [Φ η (x)] 2 for some positive constants c 0 + c 1 . Consider the set
It is clear that Φ η (x) is bounded on this set, and thus the same applies to Hη and ∇Φ η (x), b(x, u) . Thus, we have However, ( 29) and (55) imply that η may be selected small enough that
By contrast, by (54) and the definition of K, we have
which also implies (56) on (K + 0 ∩ Kc ) × ∆. Because the bound on K + is clear, this completes the proof. □
For a detailed description of this model, see Arapostathis et al. [3]. Here we only review the basic structure that is used for our results. We consider a sequence of GI/M/n + M queues with m classes of customers, indexed by n, which is the number of servers. Customers of each class form their own queue and are served in the order of their arrival.
Let A n i , i ∈ I {1, . . . , m}, denote the arrival process of class-i customers with arrival rate λ n i . We assume that {A n i } i∈ I are renewal processes defined as follows. Let {R ij : i ∈ I , j ∈ N} be a collection of independent positive random variables such that for each i ∈ I, {R ij } j∈N have a common distribution function F i having a density f i , mean equal to one, and squared coefficient of variation (SCV) c 2 a,i ∈ (0, ∞). Let
for τ ≥ 0, and denote the hazard rate and the mean residual life functions for each i ∈ I, respectively. The arrival process A n i is then given by
We assume the following structural hypotheses on the collection {F i } i∈ I , which are enforced in this subsection without further mention.
Assumption 1. The distribution functions {F i } i∈ I satisfy F i (0) 0 and have a locally bounded density f i with unbounded support. In addition, the mean residual life functions {ζ i } i∈ I are bounded.
The service and patience times are exponentially distributed, with class-dependent rates µ i and γ i , respectively, for class-i customers. The arrival, service, and abandonment processes of each class are mutually independent.
The queuing process (counting the number both in service and in queue for each class) of the nth system X n {X n (t):t ≥ 0} is governed by
for i ∈ I and t ≥ 0. Here Y n i and R n i , are mutually independent rate-1 Poisson processes, independent of the initial conditions X n i (0) and the arrival processes A n i , for all i ∈ I. Also, Z n i (s) and Q n i (s) represent the numbers of class-i jobs in service and in queue at time s, s ≥ 0, respectively.
3.1.1. The H-W regime. The parameters satisfy the following limits as n → ∞ for all i ∈ I:
ρ n i :
Vol. 46, No. 2, May 2021, pp. 772-796
Mathematics of Operations Research, 2021, vol. 46, no. 2, pp. 772-796, © 2021 INFORMS
Arapostathis, Hmedi, and Pang: Uniform Exponential Ergodicity of the V-Network Mathematics of Operations Research, 2021, vol. 46, no. 2, pp. 772-796, © 2021 INFORMS