Fluid approximations for a processor-sharing queue.
In this paper a fluid approximation, also known as a functional  strong law of large numbers (FSLLN) for a GI/G/1 queue  under a processor-sharing service discipline is established and its  properties are analysed. The fluid limit depends on the arrival rate, the  service time distribution of the initial customers, and the service time  distribution of the arriving customers. This is in contrast to the known result  for the GI/G/1 queue under a FIFO service discipline, where the  fluid limit is piecewise linear and depends on the service time distribution  only through its mean. The piecewise linear form of the limit can be recovered  by an equilibrium type choice of the initial service distribution.
Introduction
Consider a single server queue with n new jobs residing in the queue at time 0, and a renewal
stream of arrivals, rate -. The service times for these jobs are described by a sequence of independent
identically distributed (i.i.d.) nonnegative random variables, with processing rate -
and with processing time distribution function F , and with associated equilibrium distribution
F e . Let Q n (t) be the number of jobs in the queue at time t. We study this system under a
time sharing discipline: At time t the server is splitting its service capacity equally between
all customers. An important performance measure here is the cumulative amount of
processing time per customer allocated by the server until time t, which we denote by j n (t),
and refer to as the attained service process. Let -
are interested in the limiting behavior as n !1 of these rescaled processes.
Under a first-in first-out (FIFO) service discipline, it is well-known that almost surely,
in the uniform topology, where -
maxfx; 0g). This fluid limit is continuous and piecewise linear. Moreover, it depend on the
specific service time distribution only through its mean.
The fluid limits under processing sharing are entirely different. In Section 3 we investigate
the case of no arrivals after The fluid limit queue length process -
Q(t) is then given
by (3.1). It depends on the distribution of the processing times and is piecewise linear if and
only if the processing time distribution is exponential. It is lower (higher) than in the FIFO
case if the processing time distribution is NWUE (NBUE). Also, -
Q(t) is discontinuous if the
processing time distribution contains atoms (in which case a fraction of the initial n customers
departs simultaneously). For this reason one can anticipate that convergence of -
holds only in the Skorohod J 1 -topology (see Billingsley (1968)).
The time shared system with arrivals is investigated in Section 4, where we consider the
cases first show that -
is the
time at which the FIFO fluid limit queue length process empties. For t ! - we show that a.s.
in the uniform topology, where j is given by Theorem 4.9. The result expresses
in terms of the equilibrium distribution of the service times, F e . Specifically, we show that
is the inverse of an affine transformation of the delay in queue
distribution for an M/G/1 queue with F service times. When
the inverse of an affine transformation of the renewal function of an F e renewal process. One
feature that is retained in common with the FIFO case is the independence of the fluid limits
of the interarrival time distribution.
The explicit form of the fluid limit attained service process seems quite surprising. It is no
doubt related to the a result on stationary M/G/1 with processor sharing, which says that the
attained age of jobs in process are distributed as F e (Wolff 1987, Section 10.4, Example 10.8).
The heavy traffic limit (in the sense of Kingman, in contrast to functional weak limits)
for queues under the processor sharing discipline has been studied by Yashkov (1993) and a
strong law of large numbers for the queue length process (among other results) was established
for the transient case with stationary interarrival and service times in Jean-Marie and Robert
(1994). Specifically, they consider the case where ae ? 1 and Q
Their result is that Q(t)=t ! ff, where Q(t) is the queue size at time t and ff is the positive
root of the equation
R 1e \Gammaffx F e (dx). This, of course implies that -
uniformly
on compact intervals. We focus on the case where ae - 1 and -
prove a functional
strong law-of-large-number theorem (FSLLN) for the queue length process. Since the limiting
process of the FSLLN may not be continuous when ae - 1, the functional SLLN is not implied
by the SLLN. We note that the case where ae ? 1 and -
has not been dealt with by
either of the above papers.
Our motivation to look at this problem is the current interest in fluid limits of multi-class
queueing networks. We briefly survey some of the literature on fluid limits of queueing models
and comment on their relation to our results.
The early work on the fluid approximation is summarized in Newell (1982). Johnson (1983)
and Chen and Mandelbaum (1991,1994) derive fluid approximations for single class queueing
networks, in particular for generalized Jackson networks under a FIFO service discipline (Note
that Johnson (1983) also considered a head-of-line processor-sharing discipline). For more
recent work on fluid approximations see Mandelbaum and Massey (1995) and Pats (1994).
In Kella and Whitt (1992) a fluid limit for a tandem queueing network is established where
the limit is a tandem fluid network with compound Poisson inputs (in contrast to the usual
deterministic fluid limits described earlier in the paragraph). Identical arguments imply such a
convergence for general Jackson-type networks. Actually, fluid networks with certain stochastic
features can be employed as direct models rather than just approximations. For studies of such
networks with stochastic inputs see Kaspi and Kella (1996), Kella (1993,1996,1997), Kella and
Whitt (1992,1996) and references therein.
It turns out that the fluid limit queue length processes for single class queueing networks
under FIFO discipline share the features of the single server queue: They are piecewise linear
and depend on the service and interarrival time distributions only through their expectations.
In particular, if the service times of a customer at the various servers are dependent, this has no
effect on the fluid limit queue length process. This will clearly not be the case under processor
sharing disciplines. Moreover, it is clear that the times at which the various components of the
fluid limit queueing process reach zero will also depend on the service time distribution and
will in general differ from those under FIFO.
Fluid approximations and their dependence on service discipline came to the forefront in
recent studies on multi-class queueing networks. A series of puzzling examples showed that
the question of stability of multi-class queueing networks cannot be determined purely by
traffic intensity condition. In fact these examples showed that the stability of a multi-class
queueing network is not a meaningful question. Rather, one can only talk about the stability
of a multi-class queueing network with reference to a specific service discipline. In particular it
was found that a multi-class queueing network which has adequate processing capacity may be
unstable under a bad priority policy (Kumar and Seidman 1990, Lu and Kumar 1991, Rybko
and Stolyar 1992) and, more surprising, under FIFO (Seidman 1993, Bramson 1994a,b). An
important portmanteau theorem of Dai (1995,1996, see also Chen 1995, Dai and Meyn 1995,
Meyn 1995, Dumas 1995, and the earlier work of Rybko and Stolyar 1992 and of Botvich and
Zamyatin 1992) makes the connection that a multi-class queueing network is stable under a
given service discipline if and only if its fluid limit queue length processes are stable.
Based on this theorem it is possible to prove stability of some priority service disciplines
(Kumar and Kumar 1994, Dai and Weiss 1996, Dumas 1995, and Chen and Zhang 1996b) and
of FIFO discipline (Bramson 1996, Chen and Zhang 1996a, Foss and Rybko 1995, Winograd
and Kumar 1995), for some queueing networks. Also based on this theorem it was possible
to characterize global stability regions of various multi-class networks, see Down and Meyn
(1994), Kumar and Meyn (1995), Bertsimas, Gamarnik and Tsitsiklis (1995), Dai and Vande-
Vate (1996a,b) and Hasenbein (1996). Chen and Yao (1996) is on the existence of a static
priority discipline such that a multiclass queueing network is stable under the usual traffic
intensity condition.
Dai's theorem is a portmanteau theorem in the sense that it does not make a single state-
ment. Rather it gives a general recipe for showing stability of a service discipline, by performing
the following steps: One needs to define a general state space Markov chain which determines
the queue length processes under the given discipline, and one needs to construct a set of equations
which characterize all the fluid limits of the queue lengths processes. The theorem then
connects the stability of the Markov chain and of the fluid limits. Dai (1995) also illustrates
the appropriate Markov processes and the appropriate fluid equations, for priority disciplines,
for the FIFO discipline, and for Head of the Line Processor Sharing Discipline. However, some
of the results in that paper need to be modified before they can be applied to the Processor
Sharing case. Our current paper may help in such a modification, and in particular the
attained service time process may play a role in this.
Finally, fluid approximations of a queueing network can be used to obtain heuristics for
optimal operation of the network. Work in this direction includes Chen and Yao (1993),
Avram, Bertsimas and Ricard (1995), Weiss (1995,1996), Atkins and Chen (1994), Banks and
Dai (1996), and Meyn (1996). We observe that the processor sharing service discipline has
some good properties, in that it tends to achieve shorter queueing delays without requiring any
data on the processing times. Fluid limits for processor sharing systems can be used to assess
the efficiency of the processor sharing discipline, and compare it with other control methods.
Notation and Formulation
In this paper we denote Almost
surely, uniformly on compact intervals and without loss of generality are abbreviated by a.s.,
u.o.c. and w.l.o.g., respectively. 1 B denotes the indicator of an event B (1 if B occurs and 0
otherwise).
Consider a single station queue with
ffl service times fv k j k - 1g, with
ffl service time distribution F ,
ffl service rate
stationary excess distribution associated with F ,
ffl interarrival times fu k j k - 1g, with
ffl arrival rate
ffl arrival process
ffl traffic intensity
We assume that f(u k ; v k )j k - 1g are i.i.d. (nonnegative) random pairs.
We consider a sequence of systems for which we would like to establish a strong limit
theorem. For the nth system, at time 0, Q n (0) are present at the queue. We assume that
a.s. Also we assume that all the customers present in the system at time zero have not received
any service. That is, given Q service times are m i.i.d. random variables
m , all distributed F (the original service time distribution). It is assumed that Q n (0)
and fv 0
are independent of f(u 1g.
Note that in this sequence of systems, for all n the systems share the same fv 0
the same f(u k ; v k )j k - 1g, and they differ only in the value of Q n (0). To approach the fluid
limit we rescale the systems, using n as the scaling factor.
The performance measure of interest is the queue length process Q
indicates the number of jobs in the queue at time t when the initial queue length
is (0). As in this paper we are interested in a queue with processor sharing discipline, we
note that the service rate per customer at some time t is given by 1=Q n (t) whenever Q
That is, the server divides his/her time equally between the customers. With
Z t'(Q n (s))ds (2.2)
be the cumulative rate per customer given by time t.
First, we give a description of the queue length process. To this end, we observe that a
customer (i, say) present at time zero will also be present at time t if and only if the cumulative
service rate per customer by time t does not exceed that customer's service time. That is, if
(t). Similarly, a customer which arrived after time zero (k, say), will be present at time
t if and only if the cumulative service rate per customer from time U k to t does not exceed that
customer's service time. That is, if Therefore, the queue length process
must satisfy the following equation
We now note that v 0
is the service time that the ith initial customer received up to
time t. In the same manner v i - (j n is the total service time allocated to the ith
arriving customer by time t. Summing everything up yields the total amount of time that the
server was busy. That is t \Gamma L(t) where L(t) is the cumulative idle time. For t smaller than
the first time our process hits zero, L(t) is clearly zero, so that for such t's we have
or, if we define j
we have
3 The case of no Arrivals
Let us begin by studying the process with no arrivals. Note that in this case if we let D j be
the departure time of the j t h customer, then since this is also equal to the amount of work the
server performed by this time, we have that D
. This is true since by that
time all customers with a smaller or equal service time completed service and all those with
larger received the same amount of service as customer j. This gives us a direct and explicit
representation for the queueing process which is
so that
In preparation for the main theorem of this section we will state and prove the following simple
lemma.
Lemma 3.1 Let X; nonnegative random variables with EX ! 1. Then,
a.s.,
lim
sup
Proof Let H be the distribution of X and H n
bution) and observe thatn
(s))ds and E(X -
Consequently for t - s,
and for s - t, we have that
Hence, by the Cantelli-Glivenco theorem (see, for example, Theorem 5.5.1 on page 133 of
Chung 1974) and the strong law of large numbers we have, a.s. for all s ? 0, that
lim
sup
and by letting s !1 in the above, the right side vanishes by dominated convergence. 2
Theorem 3.2 Assume that A j 0. Then, as
Q in J 1 (the usual Skorohod
topology on the space D[0; 1) of right continuous functions having left limits), where
e
with -
is the inverse of F e (noting
that F e is continuous and strictly increasing on [0; supfxj F (x) ! 1g)). If F is continuous,
then the convergence holds u.o.c.
Proof We first observe that when A j 0 we have from(2.3) and (2.4) that
and
for
(the later limit is taken as n ! 1), and, of course, -
it follows from (3.2) that
for all x - 0. Therefore, by Lemma 3.1, a.s. - n uniformly in x - 0. Since - n is
continuous (nondecreasing) on [0; 1) and j n is continuous (strictly increasing) on [0; - n ) we
have that - n (j n
continuous nondecreasing with
e
such that - n is linear on [- F e (j n (- n )); -F e (j n (-
clear that such a continuous and nondecreasing - n always exists (for every
n). In particular - n (t) - n for t -F e (j n (- n )), which implies that -
for such a
t. uniformly in x - 0 and for
a given ffl ? 0 taking n large enough so that - we have that - n
Thus it follows that a.s. - n uniformly in t - 0. Now
ae -
F
e
where F Qn(0) (x) is the empirical distribution associated with v 0
(x). Note that when T F is finite and is an atom of F , then j n (- n
enough n and when this is not the case, -
Q(t) is continuous at - . In either case, we can apply
Cantelli-Glivenco together with this observation to argue that -
Q(t) uniformly in
To conclude, we have shown that there is a sequence of continuous nondecreasing time
transformations f- n j n - 1g such that a.s.
lim
sup
which is the definition of J 1 convergence (actually somewhat stronger, but in our case equiva-
lent). It is well known and easy to check that J 1 and u.o.c. convergence are equivalent when
the limit function is continuous, which is the case at hand when F is continuous. 2
When v is exponentially distributed with rate -, we have -
. This is expected, since it is easy to check that the process is stochastically
identical to one that corresponds to a queue with a FIFO service discipline. When v is uniformly
distributed with mean 1=-, it is easy to check that -
In fact
we also have the following.
Corollary 3.3 -
Q(0)=- if and only if F is NBUE
(NWUE), hence equality holds only for the exponential distribution.
Proof The equivalence to F -)F e is easily verified and so is the fact that F -)F e
if and only if E[v \Gamma tj v ? t] -)Ev. The latter is definition of NBUE (NWUE), where
NBUE is short for new better than used in expectation, and NWUE for new worse than used
in expectation. The only distribution which is both NBUE and NWUE is the exponential
distribution. 2
Another corollary which is easy to conclude is the following.
Corollary 3.4 Let F 1 and F 2 be two distributions of the service times having the same mean
1=-. Denote
Q(s))ds (see (2.2) and (3.1)) for each of these distributions by j F 1
and
respectively. Then j F 1
(t) for every t if and only if F 1 - cx F 2 where - cx is the usual
convex ordering.
Proof Follows from j F i
ie (t=-) and the fact that F 1 - cx F 2 if and only if -
F 2e ,
which in turn is equivalent to F \Gamma1
2e . 2
Obviously, if -
, then F 1 - cx F 2 . The converse may not hold.
4 The Case with Arrivals
Here we will prove somewhat weaker statements than we proved in the previous section. With
only that
(both .a.s. It is weaker in the sense that we are
not directly proving that -
to a limit, we are excluding the point - from
consideration, and we do not make any statements about the case ae ? 1. Our conjecture is
that -
does indeed converge a.s. in J 1 (u.o.c. if F is continuous) to a limit which can be
derived from j, and that there are some meaningful limiting forms also for ae ? 1. On the
positive side, it will be shown that j has an interesting form and comparisons will be made
with the known limit for the FCFS discipline.
We start by recalling a limit theorem for the workload process. Let Z
be the workload process. It is well known that
where L n is the cumulative idle time, given by
It is clear that the workload process under a processor-sharing discipline is the same as that
under a FIFO service discipline and is actually the same for all non-idling work conserving
disciplines. Therefore, it follows from the FSLLN theorem for a queueing network under a
FIFO service discipline that as n !1,
Also if we define - then it is well
known that - n =n ! - a.s. as n ! 1.
Let us first consider the case ae ! 1. Let T be the first arrival epoch after - n .
It is easy to see that T n =- n ! 1, a.s., so that T n =n ! - as well. Our first goal is to show that
the process f -
converges u.o.c. to zero a.s. With this in mind, let us first state the
following well known result.
Lemma 4.1 Let fX n j n - 1g be a sequence of random variables the absolute values of which
are stochastically bounded by some nonnegative random variable Y having a finite mean. Then
a.s. as n ! 1.
We note that the assumptions (hence the conclusions) of Lemma 4.1 hold whenever fX n j n - 1g
is a sequence of identically distributed (not necessarily independent) random variables having
a finite mean. Next, let us state and prove the following lemma.
Lemma 4.2 Let (fX n (t)j t - 0g; t n ) be a stationary and ergodic sequence, where X
is a right continuous process and t n is a nonnegative random variable
with
tg. Finally denote
(a random variable, due to right continuity). If EY
converges u.o.c. to zero a.s.
Proof Under the assumptions of the lemma it follows that are finite) and
that 1. The latter two follow
from the inequality S N(t) - t ! S N(t)+1 and the strong law of large numbers for stationary
and ergodic sequences. From Lemma 4.1 we have that Y n =n ! 0 a.s. as n !1. Thus,
Y N(t)+1
a.s. as t ! 1. It is easy to show that if for a given function f ,
f(nt)=n converges u.o.c. to zero as Theorem 4 of Glynn and Whitt [27]).
Thus, we are done. 2
We note that a special case of the structure of the process X in Lemma 4.2 is that of
a regenerative process having i.i.d. cycles. Let us now state and prove the following desired
result.
Theorem 4.3 f -
converges u.o.c. to zero a.s. (note ? rather than -).
Proof Let us denote by 0 Q(t) the number of customers in the system for the case where
is a regenerative process with an initial delay u 1 .
The cycles are the cycle times in a GI/G/1 queue. For each t ? u 1 we have that 0 Q(t)
is at most the total number of customers that arrived during the cycle to which t belongs.
1, the number of arrivals in a single cycle has a finite mean, as the first decreasing
ladder height in a related random walk having a negative drift. By Lemma 4.2 this implies
that 0
converges u.o.c. to zero a.s. We now return to consider the
original process Q n (t), and we note that, clearly, 0 Q(T
- 1. If we pick - ! a ! b then we can take N such that T n =n ! a for n - N . Hence
Therefore, for n - N we have that -
and in particular
sup
a.s. as n !1. Therefore, the proof is complete. 2
Next, for the case ae - 1 we would like to show that j n converges u.o.c. on the half open
interval [0; -) (note that
To facilitate our analysis, we write an alternative expression for the workload process:
We first prove the following result which holds for all ae - 0.
Lemma 4.4 Given any 0 ! - there exists an ffl ? 0 such that
lim
Proof Fix a K ? 0 and consider t In view of (2.3) and (4.4), we have
Hence,
which implies that
By the continuous mapping theorem we have that inf t2[0;- 0
converges a.s. to ffl
and recall that - in the above
inequality yields
dominated convergence that E[v1 fv?Kg ] vanishes as K ! 1.
In particular take K ? 0 such that [ -
This completes the proof. 2
By Lemma 4.4 it now immediately follows that fj n j n - 1g are nondecreasing, equicontinuous
and uniformly bounded (hence c-tight) on [0; - 0 ] for every - actually uniformly
(in n) Lipschitz continuous on [0; - 0 ].) This implies the following.
Lemma 4.5 Almost surely, every subsequence of fj n j n - 1g has a further subsequence which
converges u.o.c. on [0; -).
To show that j n converges u.o.c. a.s. on [0; - ), we will need to show that a.s. all convergent
subsequences converge to the same limit. Note that the statement in Lemma 4.5 begins with
"Almost surely". This is stronger than stating that every subsequence has a further subsequence
which converges a.s. The latter, together with having a common limit to all convergent
subsequences, implies only convergence in probability. We begin with the following main and
fundamental result.
R be a Borel measurable function which satisfies the following
conditions:
1. Uniform equi-continuity on finite intervals: for every t ? 0 and ffl ? 0, there is a ffi such
that if 0 - y
for all x 2 R.
2. Domination: jh(x; y)j - g(y) for some nondecreasing finite g.
Then, with the notations and under the assumptions of Section 2,n
Z tEh(v; s)ds (4.6)
a.s., as n !1, where
Proof First note that since U i =i pick a random I such
that jU i I . In particular if, for a given ffl and for
according to property 1 in the statement of this lemma, then we have that for each
n such that A(nt) - I ,
Hence, since A(nt)=n ! -t, then a.s.,n
\Gamman
as n !1. Next we observe that
\Gamman
which vanishes a.s. as n !1. Now, as in (4.7) we also have thatn
-t
a.s., as n !1. To continue, we replace b-ntc by n and observe that
which implies that
-t
By Chebyshev's inequality and the Borel-Cantelli Lemma, this implies, as in the proof of
Theorem 5.1.2 on page 103 of Chung 1974, that
-t
a.s., as n !1. Denote - h(x; and note that - h also satisfies conditions 1
and 2 (with -
Since for all 1 we have that
and the right side vanishes as n !1, it follows from condition 1 (applied to -
that
as n !1 and thus D n =n a.s. This implies that, a.s.
-t
(that is, the entire sequence converges a.s.) Finally, we observe that by dominated convergence,
Eh(v; \Delta) is a continuous function and hence Riemann integrable. Thus clearly
-t
and the proof is complete. 2
As an immediate corollary we now have the following.
Corollary 4.7 Let j be a continuous (hence uniformly continuous on compact intervals) and
nondecreasing function which is bounded on finite intervals. Then, for a fixed t, h(x;
conditions 1 and 2 in Lemma 4.6 and thus, under the assumptions
of the lemman
a.s., as n !1, for all ae - 0.
We are now ready to state and prove the most important result of this section.
Theorem 4.8 If -
u.o.c. a.s. on [0; -), where j
satisfies the following equation
Proof For every (u.o.c.) convergent subsequence j n k ! j, it is easy to show that, for a given
the difference betweenn k
vanishes a.s., as k ! 1. This together with (2.4) and Corollary 4.7 (noting that by equicontinuity
of implies the result, provided we are able to show
that (4.18) has a unique solution. This is shown in Theorem 4.9 to follow. 2
Theorem 4.9 For ae - 1, equation (4.18) has a unique solution which is the inverse of
In particular:
(i) When ae ! 1, it is the inverse of
where F W jW?0 (x) is the conditional stationary distribution of the waiting time in an
M/G/1 queue (excluding service) given that the server is busy. For this M/G/1 queue,
the arrival rate is and the service times are distributed like v.
it is the inverse of -
e is the renewal
function associated with F e .
Proof as the right continuous inverse of j. Since j is continuous
and by Lemma 4.4 also strictly increasing on [0; - ), it follows that - also has these two properties
on [0; j(- \Gamma)) and is continuous and nondecreasing on [0; 1) with Therefore,
recalling that ae = -Ev and that F e is the stationary excess distribution of
v, then
Z xF e
implying that
It is well known that when ae ! 1 the stationary distribution of the waiting time in an M/G/1
queue with FCFS service discipline is given by
Thus,
ae
ae
which implies that
which implies the result for ae ! 1. For 1, from which the result
is immediate. 2
We note that for the case ae ! 1, the time until j(t) becomes constant (so that the limiting
queue is at zero) is given by
as expected (see (4.19)). Note that j is in fact Lipschitz continuous in any compact subsets of
absolute continuous and is differentiable almost everywhere on [0; - ).
If we assume that -
converges to -
Q in some sense, then it follows from
(j(t)). It is interesting to compare how -
Q(t) relates to -
where we recall that 1=Ev. The latter is what we would obtain in the limit if the service
discipline was FCFS. In that regard we immediately see that -
that
Q(t) and From (4.21), this is equivalent to
That is, the hazard rate of W jW ? 0 is at least - \Gamma -. It is easy to check that when v is
exponentially distributed, then W jW ? 0 is exponentially distributed with rate - \Gamma -, so that
in this case (4.23) holds with equality. This is expected, since in this case the original process
has the same distribution as the one with the FCFS discipline.
For the case ae = 1, when v is exponentially distributed, then F e is also the exponential
distribution and thus M e
Q(0)x. Thus, in this case
which implies that -
Q(0) for all t - 0, and is well known to hold for the FCFS case.
For the non-exponential F , M(t)=t ! -. Hence, if -
Q(1) then from j(t)=t ! -
immediately follows that -
Q(0).

Acknowledgment

. The work of Jean-Marie and Robert (1994) was brought to our attention
by Vicent Dumas.



--R

Performance evaluation of scheduling control of queueing networks: fluid model heuristics.

Simulation studies of multiclass queueing networks.
Stability conditions for multiclass fluid queueing networks (preprint).
Convergence of Probability Measures.
Ergodicity of conservative communication networks.


Convergence to equilibria for fluid models of FIFO queueing net- works
Fluid approximations and stability of multiclass queueing networks: work-conserving discipline
Discrete flow networks: Bottleneck Analysis and Fluid Approximations.
Hierarchical modelling of stochastic networks
Dynamic scheduling of a multiclass fluid network.
Stable priority disciplines for multiclass networks.


A Course in Probability Theory.
On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models.
A fluid-limit model criterion for instability of multiclass queueing net- works
Stability and convergence of moments for multiclass queueing networks via fluid models.
Stability and Instability of Fluid Models for Re-Entrant Lines


Piecewise linear test functions for stability of queueing networks.
A multiclass network with non-linear
Stability of multiclass Jackson-type networks
Ordinary CLT and WLLN versions of L
Necessary conditions for global stability of multiclass queueing networks.
On the transient behavior of the processor sharing queue.
Diffusion Approximations for Optimal Filtering of Jump Processes and for Queueing Networks
Stability of feedforward fluid networks with L'evy inputs.
Parallel and tandem fluid networks with dependent L'evy inputs.
Stability and non-product form of stochastic fluid networks with L'evy inputs
Stochastic storage networks: stationarity and the feedforward case.
A tandem fluid network with L'evy input.
Stability and structural properties of stochastic fluid networks.
The last buffer first serve priority policy is stable for stochastic re-entrant lines
Stability of queueing networks and scheduling polities.
Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems
Distributed scheduling based on due dates and buffer priorities.
Strong approximations for time dependent queues.
Transience of multiclass queueing networks via fluid limit models.
The Policy Improvement Algorithm for MDPs.

Applications of Queueing Theory
Ergodicity of stochastic processes describing the operations of open queueing networks.
First come first server can be unstable.
Optimal draining of a re-entrant line
Optimal draining of a re-entrant lines: Some solved examples
The FCFS service discipline: stable network topologies
Stochastic Modeling and the Theory of Queues
On a heavy traffic limit theorem for the M/G/1 processor sharing queue.
--TR

--CTR
Robert C. Hampshire , Mor Harchol-Balter , William A. Massey, Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates, Queueing Systems: Theory and Applications, v.53 n.1-2, p.19-30, June      2006
functional strong law of large numbers;processor-sharing discipline;fluid approximation;GI/G/1 queue