Existence Condition for the Diffusion Approximations of Multiclass Priority Queueing Networks.
In this paper, we extend the work of Chen and Zhang [12] and establish a new sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. This sufficient condition relates to the weak stability of the fluid networks and the stability of the high priority classes of the fluid networks that correspond to the queueing networks under consideration. Using this sufficient condition, we prove the existence of the diffusion approximation for the last-buffer-first-served reentrant lines. We also study a three-station network example, and observe that the diffusion approximation may not  exist, even if the proposed limiting semimartingale reflected Brownian motion (SRBM) exists.
Introduction
We consider a general multiclass queueing network under a preemptive resume priority service
discipline. The network consists of J single server (service) stations, each with an infinite buffer
(waiting room). There are K ( J) classes of jobs, indexed by K. While each station
may serve more than one class of jobs, each class is served at a specific station. After receiving
the service, the job is routed to another station or leaves the system following a Markovian
routing. The external arrival processes and the service processes are renewal processes. Each
class is assigned a priority. When there is more than one class of jobs at a station, the server at
the station serves the job with the highest priority; within a class, jobs are served in the order of
arrival. The server of each station is kept busy as long as there are jobs at that station. Let Q k (t)
indicate the number of class k jobs in the network at time t,
The diffusion approximation addresses the weak convergence of the scaled K-dimensional queue
length process "
under a heavy traffic condition, where
(Roughly speaking, the heavy traffic condition is that the traffic intensity at each station equals
one.)
Since it is known that the above diffusion approximation may not always exist (see Chen and
Zhang (1998)), sufficient conditions are sought for the existence of the diffusion approximation.
It turns out that these conditions are related to the behavior of a corresponding fluid network.
The fluid network corresponds to the queueing network, consisting of J stations, with K classes
of (discrete) jobs replaced by K classes of (continuous) fluids. Let
indicate the class k
fluid level at time t,
H be a partition of the set
of all classes (or more precisely indices of classes), with L being the set of all classes with the
lowest priority at each station. One of the key conditions in our sufficient condition is that there
exists a finite time   0 such that for any
Q(t) with a unit initial fluid level (i.e., jj
In short, the fluid level of higher priority classes reaches zero in a finite
time and then remains in zero; this condition shall be referred to as the SHP -condition, short
for the stability of higher priority classes. On the other hand, under the heavy traffic condition,
if the weak convergence,
Q as n !1;
holds with a continuous limit "
Q, then it is necessary that "
QL is a semimartingale
reflected Brownian motion (SRBM) (see Theorem 6 of Chen and Zhang (1999b)). A necessary
condition for the SRBM to be well-defined is that a corresponding J \Theta J reflection matrix ~
RL
to be completely-S. (We note that matrix ~
RL depends only on the priority discipline and the
first-order parameters of the queueing network, whose precise definition shall be given later. A
square matrix A is said to be an S-matrix if there exists a vector x  0 such that Ax ? 0, and
it is said to be completely-S if all of its principal submatrices are S-matrices.)
The sufficient condition we establish for the existence of the diffusion approximation is that
the matrix ~
RL is completely-S and the SHP -condition holds. This sufficient condition improves
the sufficient condition given by Chen and Zhang (1999b), which instead of the SHP -condition,
requires the existence of a linear Lyapunov function for the fluid levels of higher priority classes.
Using the sufficient condition described in this paper, we can establish the existence of the
diffusion approximation for reentrant lines under a last-buffer-first-served (LBFS) discipline,
and obtain an almost necessary and sufficient condition (except for some boundary cases) for a
three-station network introduced by Dai, et al. (1999). For this latter network, we observe that
the diffusion approximation may not exist, even if the "proposed" limiting SRBM exists (i.e.,
the corresponding reflection matrix is completely-S).
At the time of this paper's preparation, it was brought to our attention that Bramson (1998)
also establishes a sufficient condition for the general heavy traffic limit theorem for the priority
queueing network. The sufficient condition replaces our SHP -condition by using a uniform
asymptotic stability condition; specifically, there exists a real function H(t)  0 with
as t !1, such that,
for all fluid level processes
Q with a unit initial fluid level. We shall show that these two
sufficient conditions are equivalent. On the other hand, the SHP -condition in our sufficient
condition could be verified via a Lyapunov function approach, which leads to more explicit
conditions with the verification of the feasibility of a set of linear inequalities. (We also learned
that Zhang (1999) provided a relaxation of the uniform asymptotic stability condition with the
condition that
Q(1) as t !1 for all fluid level process
Q.)
The diffusion approximation for queueing networks has long been an important area of
research in queueing theory. It is the functional central limit theorem for queueing networks;
and in queueing networks, it plays the same important role as the classical central limit theorem
plays in the study of a sequence of i.i.d. random variables. It provides an important tool in
approximating the performance measures of queueing networks. There has been a large volume
of literature on the diffusion approximation. Readers are referred to Whitt (1974), Lemoine
(1978), Glynn (1990) and Chen and Mandelbaum (1994) for surveys on earlier work, which is
mostly on single class queueing networks. Almost all of the earlier work rely on the oblique
reflection mapping (or its special case, the one-dimensional reflection mapping), introduced by
Harrison and Reiman (1981). Some of multiclass queueing networks have been studied under
this approach as well, including Peterson (1991) on a feedforward multiclass network, Reiman
(1988) and Dai and Kurtz (1995) on a multiclass queue, and Chen and Zhang (1996b) on
a reentrant line queueing network with a first-buffer-first-served priority discipline. However,
for general structured multiclass queueing networks under either a FIFO or a priority service
discipline, the above approach may not work, since the corresponding reflection mapping may
not be well-defined (or the corresponding dynamic complementarity problem may not have a
unique solution); see Mandelbaum (1989) and Bernard and El Kharroubi (1991). Moreover, it
is now well-known that the diffusion approximation may not exist in some cases; Dai and Wang
(1993) and Dai and Nguyen (1994) provided a counterexample for a network under a FIFO
service discipline, and Chen and Zhang (1998) provided a counterexample for a network under
a priority discipline. Therefore, the challenge is to answer the question, "for which classes of
multiclass queueing networks does the diffusion approximation exist?"
In the past few years, some research has been done to address this question. Chen and
Zhang (1996a) provided a sufficient condition for networks under the FIFO service discipline,
and Bramson (1998) and Williams (1998b) established the diffusion approximation for networks
under the head-of-the-line processor sharing service discipline and networks of Kelly type under
the FIFO service discipline. As previously mentioned, the latter work also established a
sufficient condition that relates the existence of the diffusion approximation to the uniformly
asymptotical stability. Whereas Chen and Zhang (1998b) established some more explicit sufficient
conditions. In a contemporary independent work, Bramson and Dai (1999) establish the
diffusion approximation for LBFS reentrant lines. Readers are also referred to Harrison (1988)
and Harrison and Nguyen (1990;1993) for the earlier effort, and to Williams (1996) for the more
recent survey on the diffusion approximation of multiclass queueing networks.
The proof of the diffusion limit theorem for a multiclass queueing network usually takes the
two steps: first to establish the C-tightness of the scaled queueing processes, and then to invoke
the weak uniqueness for the limiting processes. The foundation of this approach is the work
of Reiman and Williams (1988) and Taylor and Williams (1993) that provides a necessary and
sufficient condition for the existence and the uniqueness of a class of semimartingale reflecting
Brownian motions (SRBMs), which arises as the diffusion approximation limit (if the limit
exists). A proof for the main sufficient condition that follows this approach can be found in Ye
(1999). Instead, we shall provide an alternative proof by showing that our sufficient condition
is equivalent to that given by Bramson (1998) and Williams (1998b).
This paper is organized as follows. In the next section, we describe a multiclass queueing
network and its corresponding fluid network under a priority service discipline. In section 3,
we present the main sufficient condition theorem, and prove this theorem by relating it to the
above-mentioned sufficient condition given by Bramson (1998) and Williams (1998). Then we
shall present a number of corollaries that provide more explicit sufficient conditions. In addition,
we shall present a sufficient condition for the weak stability of the multiclass priority queueing
network, which implies the existence of a fluid limit (the functional strong law-of-large-numbers).
In section 4, we establish the existence of the diffusion approximation for reentrant line queueing
networks under the LBFS service discipline, and we study the diffusion approximation for a
three-station network. We conclude our discussions in section 5.
To close this section, we introduce some notation and convention that are used throughout
this paper. The J-dimensional Euclidean space is denoted by R J , its nonnegative orthant by
R J
. Let R
. Vectors are understood to be column vectors. The transpose
of a vector or a matrix is obtained by adding to it a prime. When e represents a vector, it is the
vector of ones with its dimension appropriate from the context. Let
a ' f1; :::; Jg. The scalar jaj denotes the cardinality of a and the vector x a is the restriction of
x to its coordinates with indices in a. Similarly, the matrix P ab is the submatrix of a matrix
obtained by choosing the elements with row-indices in a and column-indices in b; P aa will
be abbreviated to P a . Unless otherwise stated, vector operations and relatives are interpreted
componentwise; for example, for means that
each coordinate of x is strictly greater than the corresponding y coordinate. We assume the
norm in R J
vector x 2 R J . For a vector
denotes a J \Theta J dimensional diagonal matrix whose jth diagonal component is x
A J \Theta J matrix R is said to be an S-matrix, if there exists an x  0 such that Rx ? 0; and
it is said to be completely-S if all of its principal submatrices are S-matrices. The composition
is the function from R+ to R J whose
jth coordinate is the real-valued function fx In particular, the jth
coordinate of fx(t); t  0g with
To present our convergence result, we introduce the path space D J [0; 1) (the space of all
are right-continuous and have finite left limits on (0; 1)).
The path space is endowed with the Skorohod topology (see Section 3.5 of Ethier and Kurtz
(1986) or Pollard (1984)). For a sequence fX n g of D J [0; 1)-valued stochastic processes and
converges to X in distribution. For any x 2 D J [0; 1),
the uniform norm of x on the interval [s; t] is defined by
sut
with jjxjj [0;t] abbreviated to jjxjj t . A sequence fx n g of functions in D J [0; 1) is said to converge
uniformly on compact set (u.o.c.) to x 2 D J [0; 1), if for each t  0, jjx This is
denoted by
We denote the probability measure of a probability space by P. We denote by oe(X) the oe-field
generated by the random variables X, and by oe(B) the oe-field generated by B, a set of subsets
of the sample paths. In the next subsection, oe(\Delta) will also be used to represent a mapping from
classes to stations, where its domain is the class index, integers 1; :::; K. We hope no confusion
will arise from the use of oe in these two completely different contexts .
Queueing Network and Its Corresponding Fluid Network Model
In this section, we describe in detail the queueing network under priority service discipline and
its corresponding fluid network. A rigorous description of the latter is also necessary for the
formulation of the main sufficient condition theorem in the next section.
2.1 Multiclass Priority Queueing Network
The queueing network under consideration consists of J (service) stations; each station has a
single server and an infinite waiting room. There are K classes of jobs; each class is served (by
the server) at a specific station, while each station may serve more than one class of jobs. Let
Jg be the set of station indices, and let K be the set of class indices. Let oe denote
a mapping from K to J , with indicating that class k jobs are served at station j for
each k 2 K. Let jg be the set of classes that are served at station j,
be a J \Theta K matrix whose (j; k)th component c
class, jobs are served in the order of arrival; and among classes,
jobs are served under a preemptive resume priority service discipline. The priority discipline is
described by a one-to-one mapping  from f1; :::; Kg onto itself. Specifically, a class k job has
priority over a class ' job if mapping  can be equivalently described as a
permutation ((1); :::; (K)) of f1; :::; Kg.)
The primitive data of the queueing network are a K-dimensional exogenous arrival process
K-dimensional service process K-dimensional
routing sequences OE K. The quantity E k (t) indicates the number
of class k jobs that arrived exogenously during the time interval [0; t], and S k (t) indicates the
number of service completions for class k jobs after server oe(k) serves class k for a total of t units
of time, K. We assume that E k (t) and S ' (t) (k; are mutually independent
renewal processes. The arrival rates of the renewal processes E k (t) and S k (t) are ff k  0 and
respectively. The mean interarrival time of S ' (t) is denoted by m k (= 1= k ).
We further assume that the interarrival times of renewal processes E k (t) and S ' (t) have finite
variances a 2
k and b 2
k respectively. For convenience, let indicates the sum
of the service times for the first n jobs of class k, i.e.,
The quantity OE k vector in R K with its 'th component being one and other
components being zeroes) indicates that the nth job of class k turns into a class ' job after
service completion, ' 2 K; and OE k indicates the nth job of class k leaves the network
after service completion, k 2 K and n  1. We assume the sequences OE k , are
mutually independent i.i.d. sequences, and they are also independent of the exogenous arrival
process E(t) and the service process S(t). Let p k' be the probability that OE k
We call the K \Theta K matrix routing matrix, and assume it has a spectral radius
less than one, or equivalently, P That is, the network is an open network. Let
We assume that there are no jobs initially in the network.
Before describing the performance measures and the dynamics of the queueing network, we
introduce some useful notation, namely, H k , H
k , L, H, h(k), B, e H , D and M . Let
be the set of indices for all classes that are processed at the same station as class k and have a
priority no less than that of class k. Let H
fkg. We denote by L the set of all classes
that have the lowest priorities at their respective stations; in other words, for each
for each k 2 L, (k)  (') for all ' 2 C(oe(k)), and we denote by H := K n L.
Let
in words, if k is not the highest priority class at station oe(k), then h(k) is the index for the
class which has the next higher priority than class k at station oe(k), otherwise,
(b 'k ) be a K \Theta K matrix with
be a K-dimensional vector with e H
and e H
otherwise. The matrix diag() is a K-dimensional diagonal matrix whose kth
element is  k , and
Now we describe the performance measures and the dynamics of the queueing network under
a given priority service discipline . The performance measures of primary interest are a K-dimensional
queue length process and a J-dimensional
workload process indicates the number of
class k jobs in the network at time t, and W j (t) represents the amount of time that station j
has to work to empty out every job at station j at time t provided that no more external and
internal arrivals to station j are allowed. Let T k (t) be the total amount of time that station oe(k)
has served class k jobs during (0; t]. We call an allocation
process. Note that S k (T k (t)) denotes the total number of class k job service completions by time
t. Therefore, we have the following balance-equation (recalling our assumption that
The work-conserving (or non-idling) condition and the preemptive priority service discipline
imply that for each k 2 K,
where
is assumed to hold by default whenever H
;. Denote the k-dimensional
total arrival process
Given the allocation process T and the total arrival process A, the workload process
can be formally defined as
where the jth coordinate reads like
Next, we derive some convenient alternative relations for the queue length processes. First,
we rewrite (1) by centering,
Let
which is the cumulative idle time of the server at station oe(k) during the time interval [0; t]
after serving jobs of the classes whose priorities are no less than class k. In other words, Y k (t)
indicates the cumulative amount of time during [0; t] that is available for station oe(k) to serve
classes whose priorities are lower than class k. In particular, for k 2 L, Y k (t) denotes the
cumulative idle time of station oe(k) during the time interval [0; t]. Then the relation (6) has the
vector form,
Substituting the above into (4), we obtain an alternative expression for the flow-balance relation,
where
and  it follows from (2) that
This clearly implies that
which in turn implies
It follows from (10) that for all t  s  0,
t. In vector form, they are the same as
for all t  s  0. We note that since Q  0, under (13)-(14), condition (12) is equivalent to the
seemingly stronger condition (11).
Call  a nominal total arrival rate
(vector), fi k (the kth component of fi) a traffic intensity for class k, k 2 K, and ae j (the jth
component of ae) a traffic intensity for station j, j 2 J . Usually, the vector simply
called the traffic intensity of the queueing network. Actually,  is the solution to the following
traffic equation,
which indicates that the nominal total arrival rate vector  includes both external arrivals and
internal transitions. We say the queueing network is under a heavy traffic condition if ae = e.
2.2 Multiclass Priority Fluid Network
We describe a fluid network that corresponds to the queueing network described in the previous
section. One obtains the former by replacing the discrete jobs in the latter with continuous fluids.
Specifically, the fluid network consists of J stations (buffers) indexed by j 2 J := f1; :::; Jg,
processing (serving) K fluid (job) classes indexed by k 2 K := f1; :::; Kg. A fluid class is
processed exclusively at one station, but one station may process more than one fluid classes.
As in the queueing network, oe(\Delta) denotes a many-to-one mapping from K to J , with oe(k)
indicating the station at which a class k fluid is processed. A class k fluid may flow exogenously
into the network at rate ff k ( 0), then it is processed at station oe(k), and after being processed,
a fraction p k' of fluid turns into a class ' fluid, ' 2 K, and the remaining fraction,
flows out of the network. When station oe(k) devotes its full capacity to processing class k fluid
(assuming that it is available to be processed), it generates an outflow of class k fluid at rate
call it the exogenous inflow (arrival) rate (vector), let
call it the processing rate (vector). We call K \Theta K substochastic matrix
the flow transition matrix. Corresponding to the open queueing network described in the last
subsection, we consider an open fluid network. That is, we also assume that matrix P has a
spectral radius less than one. Among classes, fluid follows a priority service discipline, which is
again described by a one-to-one mapping  from f1; :::; Kg onto itself. Specifically, a class k has
priority over a class ' if
We adopt the following notation from the queueing network subsection, C(j), C,
h(k), L, H, B, e H , ', R, , fi, ae, M , and D. We say the fluid network is under a heavy traffic
condition
To describe the dynamics of the fluid network, we introduce the K-dimensional fluid level
process
whose kth component
denotes the fluid level of class k at time
t; and the K-dimensional unused capacity process
whose kth component
denotes the (cumulative) unused capacity of station oe(k) during the time interval [0; t]
after serving all classes at station oe(k) which have a priority no less than class k (including
class k). Sometimes, we also use a performance measure equivalent to the unused capacity, the
K-dimensional time allocation process
whose kth component
the total amount of time that station oe(k) has devoted to processing class k fluid during the
time interval [0; t]. These two processes are related in the following way:
and can be rewritten in the vector form,
With these performance measures, the dynamics of the fluid network is given as the following
system of equations.
Y (t)  0; for t  0; (16)
where the operator Df is defined as
for any t ? s and any K-dimensional function f ; and the set \Psi is defined as
The equations (16) and (17) can also be written in terms of the time allocation process
T , as
In the fluid network (K; J ; '; R; \Psi; oe; ), we shall call ' drift vector, R reflection matrix, \Psi unused
capacity set, and
Q(0) the initial state. A pair (
said to be a fluid solution of
the fluid network (K; J ; '; R; \Psi; oe; ), if it satisfies (16)-(18). For convenience, we also call
fluid solution if there is a
Y such that the pair (
Y ) is a fluid solution. A well-known property
we will use later in this paper is that the processes
Q,
Y , and
are Lipschitz continuous, and
hence are differentiable almost everywhere on [0; 1). We call a time t 2 [0; 1) a regular point
if all derivatives of such processes exist at t.
Finally, we formulate a key condition used in this paper, which is the stability of higher
priority classes in the fluid network.
SHP -condition. There exists a time  ? 0 such that,
for any fluid solution
with the initial condition jj
Q(0)jj  1.
3 Sufficient Conditions
We first present the main result, namely the sufficient condition for the diffusion approximation.
Then we prove the main theorem by showing that a key condition in the main result, namely,
the SHP -condition, is equivalent to the asymptotical stability condition as described in the

Introduction

. Next, we present some more explicit sufficient conditions for the SHP -condition,
by constructing some Lyapunov functions. Finally, we discuss the weak stability, which implies
the existence of the fluid approximation for the queueing network.
3.1 The Main Result
As a standard procedure, we consider a sequence of queueing networks as described in section 2.1,
indexed by be the exogenous arrival rate and the service rate
respectively for the nth network. Then
is the exogenous
arrival process, and S n (t), with S n
is the service process associated with the
nth network. For ease of exposition, we assume that the routing process does not vary with n.
We assume that for each network in the sequence, the initial queue length is zero. We append
with a superscript n to all of the other processes and parameters that are associated with the
nth network and that may vary with n.
We assume that as n !1,
a and
where c a and c s are two K-dimensional constant vectors. Vectors ff and  are interpreted as the
exogenous arrival rate and the service rate for the limiting network. We call  :=
respectively, the nominal total arrival rate and the traffic intensity for the limiting
network, where call its
kth component fi k the traffic intensity for class k, k 2 K.
Our main theorem focuses on the weak convergence of the following scaled processes:
under the heavy traffic condition,
e: (23)
We next define some notation that is used in formulating the main theorem below. The
following are K independent driftless K-dimensional Brownian motions:
where
it is a K-dimensional driftless Brownian motion with covariance matrix
Assume that R \Gamma1
H exists. Then "
defined by
is a J-dimensional driftless Brownian motion with covariance matrix,
(R 0
Let
Theorem 3.1 Suppose that the convergence (22) and the heavy traffic condition (23) hold.
Suppose that R \Gamma1
H exists, the covariance matrix \Gamma   , defined in (29), is non-degenerate, and
matrix ~
RL , defined by
~
is completely-S. If the fluid network (K; J ; '; R; oe; ) satisfies the SHP -condition, then the weak
convergence
YL ); in [0; 1); (31)
holds as n !1 where for t  0,
Y ' (\Delta) is continuous and nondecreasing with "
Z 1"
Moreover, the process "
X is a martingale with respect to the filtration generated by ( "
By Taylor and Williams (1993), the limiting process "
QL (t); t  0g is a semimartingale
reflecting Brownian motion (SRBM) associated with (R J
RL ). Readers are referred to
Taylor and Williams (1993) for a formal definition of the SRBM. Roughly speaking, the SRBM
QL starts at the origin, evolves in the interior of R J
like a Brownian motion with drift term
j and covariance matrix \Gamma   , and is confined to the orthant by instantaneous reflection at the
boundary, where the direction of reflection on the ith face
the jth column of the reflection matrix ~
RL .
3.2 Asymptotical Stability
Formally, we state the asymptotical stability condition as follows (which is a slight modification
of Assumption 3.1 in Bramson (1998)).
AS-condition: There is a real function H(t)  0 with !1, such that, for any
for all t  0 and some
with
In addition, if
Q(0).
It follows from Bramson (1998) and Williams (1998b) that Theorem 3.1 holds if the SHP -
condition is replaced by the AS-condition. The following proposition establishes the equivalence
between the SHP -condition and the AS-condition. Hence, this provides a proof for Theorem 3.1.
Proposition 3.2 Under the condition that ~
H RHL is completely-S, the AS-
condition and the SHP -condition are equivalent.
Before Proving this proposition, we state an oscillation inequality from Bernard and El
Kharroubi (1991).
Lemma 3.3 Suppose that u(\Delta); v(\Delta); w(\Delta) 2 C J
(the space of all continuous functions f
RL v(t)  0, for t  0;
Then (from the assumption that matrix ~
H RHL is completely-S),
where d 1 is a constant depending only on the matrix ~
RL , and for any (vector) function f ,
Proof (of Proposition 3.2). We first show that the SHP -condition implies the AS-condition.
Suppose (
Y ) is a fluid solution of the fluid network (K; J
with jj
Q(0)jj  1. According to the SHP -condition,
From (16)-(18), we obtain
QH
RL
where we use
~
which follows from Lemma 2.2 in Chen and Zhang (1999b) due to the fact that the traffic
Combined with (39), equation (40) implies
Then applying Lemma 3.3, we have
i.e.,
QL
Now, we let
Q( ), and let
constant for the fluid level process
Q. Then it can be seen that the
first half of AS-condition holds.
suppose
We would like to show that
let  be as defined in the SHP -condition and define (
and
Y
Y
Then, it can be verified directly that (
According
to the SHP -condition, we know that
Using equation (40)
and Lemma 3.3 again, we have
Q(0).
Next we show that the AS-condition implies the SHP -condition. Denote a constant d 2 as
is the (i; j)-th element of the matrix RLHR \Gamma1
H , and d 1 is the constant defined in Lemma
3.3. Define a real number ffl as
and let t ffl be a number such that
for all t  0. Then, by the AS-condition, we have
for all t  0, and this inequality, combined with (40)-(42) and Lemma 3.3, implies
for s; t  t ffl .
us construct a fluid solution (
T ) as the following:
It can be checked directly that (
If we define
then it can be verified directly that (
solution of fluid network (16)-(18) and
hence, according to the AS-condition,
holds for all t  0. This directly leads to
inductively using the above technique, we have
for all t  0 and all integer n. By letting n !1, with
for all t
3.3 Lyapunov Conditions
A key condition in the main theorem is the SHP -condition. We obtain some of its sufficient
conditions. First we show that the sufficient condition named the L 2 -condition, as referred to in
Chen and Zhang (1999b), implies the SHP -condition. To this end, we quote the L 2 -condition
from Chen and Zhang (1999b) below:
-condition. There is a (K \Gamma J)-dimensional vector h ? 0 such that for any
(16)-(18), the function h 0
QH (\Delta) is strictly decreasing at t wherever h 0
It is clear that the L 2 -condition in fact constructs a linear Lyapunov function for the stability
of higher priority classes.
Proposition 3.4 The L 2 -condition implies the SHP -condition.
Proof. Suppose the L 2 -condition is true. According to remarks after Theorem 3.1 in Chen
and Zhang (1999b), the set of all possible derivative of
QH (t) is compact. Combined with the
we know that there exists ffl ? 0 such that
when
QH (t) 6= 0 and t is a regular point (i.e., the point at which derivatives of all functions
involved exist). If jj
QH (0)jj  1, then h 0
QH (0)  jjhjj, and hence h 0
must hold for all
This establishes the SHP -condition. 2
Remark The converse of Proposition 3.4 is not true. Even if both the SHP -condition holds and
the matrix ~
RL is completely-S, the L 2 -condition may not hold. We construct a counterexample
at the end of subsection 4.2. Therefore, the sufficient condition given by Theorem 3.1 strictly
improves the sufficient condition given by Chen and Zhang (1999b).
Next, similar to the above explicit L 2 -condition, we transplant the piecewise linear Lyapunov
function approach for the stability of priority fluid network in Chen and Ye (1999) to construct
another explicit condition for the existence of the diffusion approximation for the multiclass
queueing network with priority service discipline. To this end, we introduce some notation and
terminology.
A partition (a; b) of K is called a (priority ) hierarchical partition, which shall be written
as (a; b) 2 PK , if ' 2 a implies k 2 a, provided that
is a class with higher priority in the same station as ', then k 2 a as well. The
head class set H(B) of B ' K is defined to be the set
in words, the set of the highest priority classes in each station that serves at least one class in
B. If (a; b) 2 PK is a hierarchical partition, then the fluid state S(a; b) is defined to be the set
and the regular flow rate set F (a; b) is defined to be
a where y a satisfies 0  y a  e and ' a +R a y
It follows from the dynamic relations (16)-(18) that for (a; b) 2 PK , if
t is a
regular point, then the derivative
Q(t) must be an element in F (a; b). (In fact, it is not difficult
to show by construction that the set F (a; b) is exactly the set of all such derivatives.)
Now we formulate the sufficient condition based on the piecewise linear Lyapunov function,
and we shall refer to it as the PL 2 -condition in this paper. Similar results for the stability
of multiclass fluid network with priority service discipline are contained in Theorem 3.1 and
Corollary 3.2 in Chen and Ye (1999).
There exists an ffl ? 0 and J (K \Gamma J)-dimensional nonnegative vectors x
such that the following two conditions hold:
(a) For any j 2 f1; :::; Jg, and any hierarchical partition (a; b) with b "
sup
d2F (a;b)
(b) For any partition J 0 [ being nonempty, denote K
Proposition 3.5 The PL 2 -condition implies the SHP -condition.
Proof. Without lost of generality, assume that
being a sufficiently large constant (say, a Lipschitz constant for the fluid level
process
Q). Then, it is direct to check that the PL 2 -condition is still satisfied with ffl; x
being replaced by  ffl;
x J .)
Let
QH (t)
and
It suffices to show that, under the assumption of the PL 2 -condition,
only if
is differentiable at t: (47)
Note that
clearly implies the condition (46). Hence, it suffices to show (47). The
remaining proof draws a similar idea from the proof of Lemma 4.1 in Dai, et al. (1999). [Also
see the proof of Theorem 3.1 in Chen and Ye (1999).]
Suppose t 0  0 is a regular point and
I 0 be a
subset of f1; Jg such that
be the hierarchical partition such that
a
k such that
. Then we note
It follows from the condition (45) that
This combined with the definition of I 0 implies that J
(44), we have
be two sequences such that t 1
since f(t)  f i 0 (t) and f(t 0 Letting m !1, we have
Similar to the use of the piecewise linear Lyapunov function approach for the stability of multiclass
fluid network with priority service discipline in Chen and Ye (1999), we could formulate
the PL 2 -condition in a more general form. We omit the extension here.
The PL 2 -condition seems quite involved; however, it could be formulated into the problem of
solving a set of linear programs. To this end, we introduce some notation. A linear combination
is called a convex combination of vectors z
A set Z ' R K is called a convex set if any convex combination of finite points of set Z is still
in Z. A point z 2 R K is said to be an extreme point of the convex set Z if z 2 Z but is not a
convex combination of other points in Z. It can be checked directly by definition that the regular
flow rate set F (a; b) is a bounded convex set with at most finite extreme points. Denote the set
of extreme points of F (a; b) as F e (a; b). Clearly, F e (a; is an empty set or
a single point set. Then from Krein-Milman Theorem (see for example Rockafellar (1970)), any
element q 2 F (a; b) is a convex combination of the points in F e (a; b). From this result, we can
easily linearize the condition (a) of the PL 2 -condition. Furthermore, denote all the partitions
of J into two nonempty sets as
0 and
1 as in (b) of the PL 2 -condition. Now, we convert the proposition to a set of LP problems:
For any sequence of mappings j n
first solve the following
LP problem
for any hierarchical partition (a; b) with b "
Suppose the optimal values of the above LP problems are ffl
prespectively. Then, the PL 2 -
condition is satisfied if and only if
In this LP problems formulation, the series of partitions of station index set J are considered
because the condition (b) of the PL 2 -condition should be satisfied for any partition of J into two
nonempty sets. That each sequence of mappings
1 (\Delta)g corresponds to a LP problem
is incurred by the flexibility of choice of index j 1 in the condition (b) of the PL 2 -condition. The
constraints (48) and (49) are translated from (44) and (45) respectively. At last, the constraint
(50) is a restriction of the flexibility of the choice of the number ffl and x ij 's.
We further explain why the PL 2 -condition holds if and only if ffl   ? 0. Suppose the PL 2 -
condition holds. Without loss of generality, suppose that (50) is also satisfied. According to
the condition (a) in the PL 2 -condition, it is easy to see that constraint (48) is satisfied with
preplaced by ffl. By the condition (b) in the PL 2 -condition, we can construct a sequence
of mappings
(from J n
0 to J n
1 ), such that, for each partition J n
1 and any
1 . That is, (49) is
satisfied with j n
replaced by "
in the PL 2 -condition is a feasible
solution to the LP problem corresponding to the sequence of mappings
(\Delta)g. Hence,
this LP problem has a positive optimal solution, and thus ffl   ? 0.
On the other hand, suppose that ffl   ? 0. Then, we choose one of the LP problems with
positive optimal solution. Suppose this LP problem corresponds to a sequence of mappings
We claim that, if we denote the optimal solution of this LP problem as x
and ffl, the PL 2 -condition holds with this set of parameters. Actually, all the conditions in
the PL 2 -condition are obvious except the condition (b). Consider any nonempty partition
in the condition (b). We have J
some pg. For any j 0 2 J 0 , let
according to the constrain (49) of
the LP problem, we know at once that (45) is true.
3.4 Weak Stability
Here we discuss the relationship between the SHP -condition and the weak stability of the
fluid network, since the concept of weak stability is closely related to the existence of diffusion
approximation for the queueing network. A fluid network (K; J ; '; R; \Psi; oe; ) is said to be weakly
stable if (16)-(18) has a unique solution
under the initial condition
It is known (see Chen (1995)) that the weak stability implies that the fluid limit,n
almost surely, and this convergence is also a necessary condition for the existence of the diffusion
approximation for the multiclass priority queueing network (see Chen and Zhang (1999b)).
Theorem 3.6 Suppose that the traffic intensity of the fluid network, ae e,
that R \Gamma1
H exists, and that the matrix ~
H RHL is completely-S. Then the fluid
network is weakly stable if it satisfies the SHP -condition.
Remark. The converse of Theorem 3.6 is not true. In Proposition 4.4, an example will be given
to show this.
Proof of Theorem 3.6. Suppose the initial fluid level of the fluid network is
First, we show by contradiction that
Let
QH (t) 6= 0g:
Then, keeping in mind that
by equations (40)-(42) and Lemma 3.3. Specifically, we have
According to the definition of t 0 , there exists a
for some ffl ? 0. However, for any t 2 ? t 0 with
it can be checked directly that
is also a fluid solution satisfying (16)-(18). Hence, according to the SHP -condition, we have
which immediately leads to
If we choose a point t 2 (with
sufficiently close to t 0 , then we get
since
Q(\Delta) is continuous. Hence, jj
contradicts (53) and
thus proves (52).
Finally, according to Lemma 3.3, the completely-S of RL
H RHL implies that (40)-
(42) has a unique solution
In this section, we apply the main theorem of the previous section to study the diffusion approximation
of two queueing network examples. In the first subsection, we prove the existence of
the diffusion approximation for the reentrant line network under the LBFS service discipline. In
the second subsection, we characterize the condition for the existence of the diffusion approximation
for a three-station queueing network which is first studied in Dai, et al (1999) and which
will be referred to as DHV network. We also employ a variation of this network to provide a
counterexample for Proposition 3.4.
4.1 Reentrant Line with Last Buffer First Served Discipline
We consider a reentrant line network under the LBFS discipline, i.e., 1). The
parameters of the reentrant line network take the following special form: the exogenous inflow
rate and the flow-transfer matrix
and shown by Figure 1. In this case, we have
with
and, for
where (b k' ) is as defined in subsection 2.1.
oe
oe
oe
oe

Figure

1: A Re-entrant Line Network
We note that in this case, the equation (20) takes the following simpler form,
t.
It is known that when ae = e, the matrix ~
H RHL is completely-S (see Dai,
Yeh and Zhou (1997), Theorem 3.1). The next proposition implies that the network satisfies
the SHP -condition under ae = e. (The proposition appears slightly stronger than the SHP -
condition, since the initial condition jj
in the SHP -condition is replaced by jj
QH (0)jj
1.)
Proposition 4.1 Suppose that the traffic intensity, ae j j
there exists a real number   0 such that
fluid solution (
T ) of the
reentrant line with jj
QH (0)jj  1.
The proof of Proposition 4.1 is based on the following Lemma. To state the lemma, we
introduce some notation. Let K be the J classes in the lower priority
class set L, and M ? 0 the Lipschitz constant for the fluid level process
Q. Denote the set of
classes between class k j and k j+1 as
Lemma 4.2 Let j 2 J be fixed. Then, there exists a real number  j  0 such that
0, for any fluid solution (
T ) of the reentrant line with
(By default,
Proof. We prove the lemma in three steps.
Step 1. We first show that, for any given fluid solution (
T ) of the reentrant line satisfying
(55),
It is sufficient to show that, for any regular point t ? 0, if jj
d
dt jj
for some constant number fl ? 0.
Now, suppose that t ? 0 is a regular point and that jj
0g. Then, by equation (17), we have
since
for such class '. For class
(\Delta) is a
non-negative function and t is a regular point of
must be that
with equation (54), implies
solving the corresponding
to '  '   in (57) and (58) jointly, we have
The equation in (57) with can be written as
From (59), we have  ' 0
and from (57), for some
d,  ' 0
which leads to
e
d
In view of k j+1  '   and (62), we have
and hence, by (54),
d
dt jj
dt
This leads to the existence of a finite time t  0 such that
Now we elaborate the above result on the value of '   which is useful in the following steps
of the proof. Actually, we have '  . If to the contrary, in view of (59) and (62), we have
and
However, this contradicts X
Step 2. Next, we show that, there exists  j  0 such that, for all fluid solution (
T ) of the
reentrant line satisfying (55), we have
0g. We first estimate  k j
which is the total outflow of class
fluid up to time t   . For each k 2 H k j and k ! k j+1 , we have
and
Hence, we have
By omitting the second term of the left hand side of the equations in (66), multiplying them by
summing them up, we obtainB @
where the second last equality of (67) follows from the results in (59) and the fact that '
Hence, we obtain the estimation
Now, from
and
we have
To obtain the last inequality in (69), we have used the estimation in (68). However, by (62)
(with '
almost all t 2 [0; t   ];
which implies
By comparing (69) and (70), and keeping in mind the assumption that jj
d   t    jj
and hence
what we need in (65).
Step 3. At last, we show that, for any fluid solution (
T ) of the reentrant line satisfying (55),
if
We prove this by contradiction.
Suppose there exists t ? t   such that jj
since the set ft  t   : jj
0g is open and nonempty, there exists an interval such that
Let ffl be a number such that
(t)jj. Let
Now, define the following:
It can be checked directly that (
fluid solution of the reentrant line satisfying
condition (55). Then, by (65),
and this immediately leads to
ffl. But this contradicts
condition (71). 2
Proof of Proposition 4.1. We use the above lemma inductively to show that, there exist
fixed times t J  t J \Gamma1  :::  t 1 such that
for any fluid solution (
T ) of the reentrant line with jj
QH (0)jj  1. First, let t
4.2; then
QA J
since jj
QA J
(0)jj  jj
QH (0)jj  1. Next, suppose
1). Consider the pair (
defined by
where M is a Lipschitz constant of
Q. Under the induction assumption, it can be checked
directly that (
solution of the reentrant line satisfying (55), since
(jj
Then, by Lemma 4.2,
We have immediately, by (73) and (74), that
what we want in this proposition. 2
In view of Theorem 3.1, summarizing the above, we have
Theorem 4.3 Suppose that, for the reentrant line with LBFS discipline, the convergence (22)
and the heavy traffic condition hold. Then the weak convergence (31) holds with the limits
defined by equations (32)-(37). Moreover, the process "
X is a martingale with respect to the
filtration generated by ( "
Station 1 Station 2 Station 3

Figure

2: The three-station fluid network example
4.2 A Three-Station Priority Network
We consider the network as shown by Figure 2, which shall be referred to as DHV network since
it was first studied by Dai, Hasenbein and Vande Vate (1999). The parameters ff, P and C for
this network take the form,
The priority mapping (permutation) is represented by specifically, classes 4,
and 6 have higher priorities at stations 1, 2 and 3 respectively.
In this case, we have
and, under heavy traffic condition e,
~
Proposition 4.4 Under the heavy traffic condition that ae = e (i.e., ae
~
RL is completely-S;
(ii) the DHV fluid network satisfies the SHP -condition if and only if
(iii) the DHV fluid network is weakly stable if and only if m 2 +m 4 +m 6  2.
Proof of Proposition 4.4 (i). By definition of the completely-S matrix and in view of the
heavy traffic condition, it suffices to verify the following:
1. The diagonal elements of the matrix ~
RL are all positive.
2. There exists a vector x
R f1;2g x ? 0, i.e.,
To see this, first note the above is equivalent to the existence of positives x 1 and x 2 such
that
The latter is further equivalent to
which, by some simple algebra and the heavy traffic assumption, can be written as
We claim that the above inequality holds, since either
hold. From the above process, we can
also see that the vector x can be chosen as x
Similarly, we can show that
3. ~
4. ~
5. ~
of Proposition 4.4 (ii) and (iii). We break down the proof into four lemmas.
Lemma 4.5 Under the heavy traffic condition, the DHV fluid network satisfies the SHP -
2.
In Dai, et al. (1999), it is shown that the linear Lyapunov condition given by Chen and Zhang
(2000) could not provide a sharp characterization for the stability of the DHV network (under
e). However, the linear Lyapunov condition given by Chen and Zhang (1999b) does yield a
sharp characterization (except for a boundary case) for the diffusion approximation of the DHV
network (under the heavy traffic condition Theorem 4.10. In particular, we shall
prove the lemma by using Theorem 3.2 in Chen and Zhang (1999b) (in view of Proposition 3.4),
and for convenience, we quote it below.
Theorem 4.6 Suppose that there exists a (K \Gamma J)-dimensional vector h ? 0 such that for any
given partition a and b of K satisfying
(i) If class ' 2 a, then each class k with is also in a,
we have
a"H (' a +R ab x b
inequality is assumed to hold by default when S
Then the network satisfies
almost all t  0 and any
(with the
parameters specified in this example) with jj
(2) the L 2 -condition.
Proof of Lemma 4.5. Through a tedious analysis of a set of inequalities corresponding
to all the possible partitions a [ b in Theorem 4.6, we show that there exists a vector h as
described in the above theorem if and only if there exists an h satisfying the following system
of inequalities:
In order to show the existence of such an h satisfying the inequalities (75)-(77), we divide the
proof into the following four cases and show the existence of such an h in each of the four cases.
The four cases are based on the following representation:
Case 1. Suppose m 2  m 1 . Now, we select
where M is a sufficiently large positive number and ffi a sufficiently small positive number. Then,
h satisfies the inequalities (75)-(77).
Case 2. Suppose m 4  m 3 . Similar to case 1, we select in this case,
where M is a sufficient big positive number and ffi a sufficient small positive number.
Case 3. Suppose m 6  m 5 . In this case, we select
where M is a sufficient big positive number and ffi a sufficient small positive number.
Case 4. Suppose 2. In this case, we show
the existence of h directly. Under the assumption of this case, we have
and eliminating h 2 from inequalities (75) and (76), we can show that the
existence of positive constants h 2 , h 4 and h 6 satisfying inequalities (75)-(77) is equivalent to the
existence of positive h 4 and h 6 satisfying
It is clear that the above is equivalent to
Note that m the above is the same as
But
since under the assumption in this
case. 2
Lemma 4.7 Under the heavy traffic condition, the DHV fluid network is weakly stable if
2.
Proof. By an almost word for word repetition of the proof of Lemma 4.5, we can show that,
there exists a 3-dimensional vector h ? 0 such that h 0
almost all
equations (16)-(18) with parameters for the DHV fluid network. This
establishes that if the initial condition is
Then, following the same line of the proof of Theorem 3.6, we can show that
Therefore,
it follows that the network is weakly stable. 2
Lemma 4.8 Under the heavy traffic condition, if m 2 +m 4 +m 6 ? 2 then the DHV fluid network
is not weakly stable.
Proof. Actually, this lemma is implied in part (b) of the proof of Theorem 2.4 in Dai, et al.
(1999). We only outline the idea of the proof here and omit the details.
Suppose the DHV fluid network is weakly stable under the condition 2. Let
Q(t) and T (t) be the queue length process and the time allocation process of the DHV queueing
network with Then, from Theorem 4.1 of Chen (1995),n
with
On the other hand, we know that classes 2, 4 and 6 in the DHV queueing network form a
pseudostation (see Hasenbein (1997)), which means that no more than two of these three classes
of jobs could be served at the same time. This implies
which, combined with convergence (78), further implies
for any t  0. Now, inequalities (79) and (80) contradict each other. 2
Lemma 4.9 Under the heavy traffic condition, if m 2 +m 4 +m then the DHV fluid network
does not satisfy the SHP -condition.
Proof. It is sufficient to construct a divergent fluid path
equations (16)-(18)
with nonzero initial fluid level (i.e., jj
Q(0)jj ? 0), and it can be verified directly that the following
construction suffices:
and
where [t] is the greatest integer that is less than or equal to t. In particular,
Theorem 4.10 Suppose that the convergence (22) holds. Under the heavy traffic condition, if
2, the weak convergence (31) holds with the limits defined by equations (32)-
(37). Moreover, the process "
X is a martingale with respect to the filtration generated by ( "
On the other hand, if
f2;4;6g jj diverges to infinity as n !1
Proof. The first half of the theorem follows from Proposition 4.4 and Theorem 3.1, and the
second half of the theorem follows from Lemma 4.8. 2
Remark
1. In all the examples studied before, the sufficient and necessary conditions for the existence
of the diffusion approximation for those priority queueing networks coincide with
the condition that the matrix ~
RL is completely-S. However, the DHV network provides a
counterexample. In particular, when m 2 +m 4 +m 6 ? 2, the matrix ~
RL is completely-S,
and hence, the "limit processes" in Theorem 3.1 would be well-defined; however, the
convergence (31) does not hold, i.e., the diffusion approximation does not exist in this
case.
2. We have not been able to characterize the diffusion limit for the boundary case
2.
A Counterexample for the Converse of Proposition 3.4
We construct a 9-class variation of the DHV fluid network, and then show that for some
parameters, the variation satisfies the SHP -condition but not the L 2 -condition. We provide an
intuitive presentation, from which it is not difficult to write down a rigorous proof.
The variation of the DHV network is as shown in Figure 3. The new network has three
additional classes indexed by 7, 8 and 9, which are served by stations 1, 2 and 3, respectively.
These three additional classes are assigned the lowest priorities at their respective stations. The
additional parameters are positive exogenous arrival rates ff 7 , ff 8 and ff 9 , and the positive mean
service times m 7 , m 8 and m 9 . All the other settings of this fluid network are the same as those
of the DHV fluid network.
Station 1 Station 2 Station 3

Figure

3: A variation of the DHV fluid network
From Theorem 2.5 in Dai, et al. (1999), there exists a mean service time vector m
(m
6 ) such that the DHV fluid network is stable, but there does not exist a linear Lyapunov
function for its fluid level process. Now, let m
3 \Gammam  and ff We claim that with the these parameters, the 9-class variation of the
DHV network satisfies the SHP -condition but not the L 2 -condition. This is because the three
additional classes have the lowest priorities at their respective stations and the higher priority
classes behave the same as they are in the original DHV network. In addition, for the
9-class network, the matrix ~
9 ), and hence is completely-S.
Therefore, this variation of the DHV network provides a counterexample to the converse of
Proposition 3.4.
Concluding Remarks
In this paper, we establish a sufficient condition for the diffusion approximation of multiclass
queueing networks under priority service disciplines. This sufficient condition is weaker than the
sufficient condition given by Chen and Zhang (1999b), and is more explicit (in terms of network
parameters) than the condition given by Bramson (1998). With this sufficient condition, we
establish the diffusion approximation for the reentrant line network under the LBFS discipline.
By studying a three-station DHV network, we observe that the diffusion approximation may not
exist, even if the "proposed" limiting SRBM exists (i.e., the corresponding reflection matrix ~
RL
is completely-S).



--R

R'egulation de processus dans le premier orthant de R n
Convergence of Probability Measures.
State space collapse with application to heavy traffic limits for multi-class queueing networks
Heavy traffic limits for some queueing networks.
Fluid approximations and stability of multiclass queueing networks: work-conserving discipline
Hierarchical modeling of stochastic networks
Piecewise linear Lyapunov function for the stability of priority fluid networks.


Diffusion approximations for Kumar-Seidman network under a priority service discipline
Stability of multiclass queueing networks under priority service disciplines.


A multiclass station with Markovian feedback in heavy traffic.
On the convergence of multiclass queueing networks in heavy traffic.
Nonexistence of Brownian models of certain multiclass queueing networks.
The QNET method for re-entrant queueing networks with priority disciplines
A multiclass network with non-linear
Diffusion Approximations
Markov Processes
Brownian models of queueing networks with heterogeneous customer populations
"The QNET method for two-moment analysis of open queueing networks"
Brownian models of multiclass queueing networks: current status and open problem.
Reflected Brownian motion on an orthant.
Necessary conditions for global stability of multiclass queueing networks.
"Network of queues - a survey of weak convergence results"
The dynamic complementarity problem
A heavy traffic limit theorem for networks of queues with multiple customer types.
Convergence of Stochastic Processes.
A multiclass feedback queue in heavy traffic.
A boundary property of semimartingale reflecting Brownian motions.
Convex Analysis
"Limit theorems for stochastic processes"
Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant.
"Heavy traffic theorems for queues: a survey"
Some useful functions for functional limit theorems.
On the approximation of queueing networks in heavy traffic.


Stability and diffusion approximation of multiclass queueing networks
A relationship between asymptotically stable and diffusion approximation for multiclass queueing networks.
--TR
priority service discipline;multiclass queueing network;heavy traffic;semimartingale reflecting Brownian motion;diffusion approximation;fluid approximation