Stability of Fluid Networks with Proportional Routing.
In this paper we investigate the stability of a class of two-station multiclass fluid networks with proportional routing. We obtain explicit necessary and sufficient conditions for the global stability of such networks. By virtue of a stability theorem of Dai [14] , these results also give sufficient conditions for the stability of a class of related multiclass queueing networks. Our study extends the results of Dai and VandeVate [19] , who provided a similar analysis for fluid models without proportional routing, which arise from queueing networks with deterministic routing. The models we investigate include fluid models which arise from a large class of two-station queueing networks with probabilistic routing. The stability conditions derived turn out to have an appealing intuitive interpretation in terms of virtual stations and push-starts which were introduced in earlier work on multiclass networks.
Introduction
In the last decade, there has been an explosion of research and interest
in multiclass queueing networks and their
uid counterparts. Multiclass queueing
networks are stochastic processing networks which are often more suitable
than traditional queueing systems for modeling highly complex manufacturing,
communication, and computer systems. In a multiclass network, customers at
a station may be non-homogeneous, both in terms of their service requirements
and their routing behavior after completing service at a station. Such multi-class
networks provide then a more general framework then the classical models
of Jackson [23] and Kelly [25]. Unfortunately, achieving a rened probabilistic
analysis of multiclass networks is generally an intractable problem. Instead, recent
research has focused on determining when such systems are stable. Roughly
speaking, a system is stable if it has enough resources to handle incoming work,
while operating under a set of scheduling policies. Unfortunately, many examples
given earlier in the literature (see [27], [29], [31], [5], [32]) have demonstrated that
simply analyzing the stability of multiclass networks can be a non-trivial matter.
The study of stability of multiclass networks received a tremendous boost,
however, when the early work of Rybko and Stolyar [31] and later work by Dai [13,
14], Meyn [30], and Stolyar [33] showed that an approximation known as the
uid model could serve as a very powerful tool in determining the stability of
stochastic networks. As a consequence of this newly developed theory, there has
been a
urry of results for both
uid and stochastic models. Of particular interest
among researchers have been the stability properties of networks under priority
disciplines (Dai and Weiss [20], Chen and Zhang [12], Dumas [21]) and the rst-
come-rst-served discipline (Chen and Zhang [11], Bramson [6]). Great
strides have also been made in investigating the stability of networks under more
complex dispatch policies (Kumar and Kumar [28], Kumar [26], Bramson [7])
and for networks with additional enhancements such as setup times and batch
processing (Jennings [24], Dai and Li [17]).
In this paper, we are interested in analyzing the global stability region, which
is the set of arrival and service rates under which a given network is stable under
any non-idling dispatch policy. In this direction researchers have been fairly
successful in obtaining some general results [18,3,22], although a paper by Dai,
Hasenbein, and VandeVate [16] provides some indication of the limitations of
current approaches. Perhaps the most sweeping advance in understanding the
global stability properties of multiclass networks was provided in a paper by Dai
and VandeVate [19]. This papers provided exact (i.e. necessary and su-cient)
stability conditions for all two-station
uid networks with non-branching (de-
routing. Such systems are sometimes called multitype networks. In
particular, the stability conditions are given explicitly in terms of the service and
arrival rates of the network. More importantly, they were able to provide an
intuitive explanation of these conditions via the phenomena of push-starts and
virtual stations. A major consequence of their results is that for the class of
networks they study it turns out that the global stability region is determined
by the stability properties under a comparatively simple, nite set of policies
known as static buer priority disciplines. In establishing these conditions for
two-station
uid networks, they also were able to provide, in some cases, exact
stability conditions for the corresponding queueing networks. At about the same
time, Bertsimas, Gamarnik, and Tsitsiklis [3] independently developed an LP
which could sharply determine the stability region of all two-station multiclass
uid networks, including networks with proportional (probabilistic) routing. The
results of Bertsimas, et. al. are valid for a larger class of networks, but do not
provide as much insight, since the stability region is not expressed as an explicit
function of the rates in the network in [3].
The results in this paper attempt to narrow the gap between the results of
Bertsimas et. al. and Dai and VandeVate's work on two-station
uid networks.
Specically, we derive necessary and su-cient conditions for global stability of
a large class of
uid networks with proportional routing. These conditions are
given explicitly in terms of the eective arrival and service rates of the network.
Once again, these conditions can be explained intuitively in terms of push-starts
and virtual stations. As in Dai and VandeVate's study, this also establishes the
importance of the static buer priority policies for the larger class of networks
we investigate. In particular, our results imply that the global stability of such
systems is determined by the stability under the set of static buer priority
policies. The
uid networks we study arise from
uid approximations of multiclass
queueing networks with probabilistic routing. Thus, the conditions we derive, in
some cases, yield necessary and su-cient conditions for the global stability of the
associated stochastic networks.
One nal point to note is that Bertsimas, Gamarnik, and Tsitsiklis [4] have
recently demonstrated that fundamental performance parameters of Markovian
multiclass networks are intimately related to the phenomena of virtual stations
and push-starts. In particular, they show that certain upper bounds on the tail
probabilities and expected value of the queue-length process can be derived from
the piecewise linear Lyapunov functions used in Dai and VandeVate [19]. It is
conceivable that their work can be extended to the class of networks considered
in this paper.
We now give a rough outline of the paper. Section 2 provides the framework
for the models we will be studying. In Section 3 we dene a number of submodels
which will be important in our analysis. We introduce some notation specic
to two-station
uid networks in Section 5. Sections 6 through 9 are devoted
to proving the su-ency part of our main theorem. The necessity is proven in
Section 10, completing the proof of our main result. Finally, in Section 11 we
discuss some examples and directions for further research.
2. Fluid Networks
In this section we introduce the notion of a multiclass
uid network. A
uid
network is a continuous deterministic dynamical model that is an analog to a
discrete multiclass queueing network. In the
uid network the notion of discrete
customers is replaced by the notion of
uids or customer mass. Sometimes we
will discuss the queueing network associated with a particular
uid model. By
this, we mean a queueing network with same number of stations and classes, and
with the same mean service, arrival, and routing parameters. A more precise
description of
uid models and associated queueing networks can be found in Dai
[13]. All of the formal results in our paper are for
uid networks, which we now
dene more precisely.
The
uid networks in this paper consist of two processing stations, A and
B, and K classes of
uids that are processed at the two stations. Fluid of class k
arrives from the outside at rate  k  0. Also, class k
uid requires processing at
station (k) and can be processed at the maximum rate of 0 <  k < 1 if station
devotes all of its eort to processing class k
uid. Note that in general
multiple classes may be served at the same station. We will call m
the service time for a class k
is the time it takes to process one
unit of
uid. After class k
uid is processed at a station it is routed to another
station or stations according to the routing matrix P . If p then all of
the class k
uid is routed to class '. In the case where 0 < p k' < 1, we have
proportional routing in our network, i.e. a proportion p k' of class k
uid is routed
to class '. This proportional routing is analogous to probabilistic routing in an
associated stochastic network. Any
uid that is not routed to another class leaves
the network. Hence, we have that a proportion 1
class k
uid directly
exits the network.
Our study will be restricted to open
uid networks, i.e. we assume that
the routing matrix P has spectral radius less than one. One consequence of this
assumption is that the matrix (Id P 0 ) is invertible and
where Id is the identity matrix. In an associated queueing network, such a
restriction implies that all customers will eventually leave the network.
Let us denote the amount of class k
uid in the network at time t by Q k (t)
and let T k (t) denote the amount of time server (k) devotes to class k
uid in
the interval [0; t]. The allocation process T () will depend heavily on the dispatch
policy employed in the network.
With these denitions we are ready to write down the dynamical equations
for our
uid network. The vectors Q(), T (), and  are all assumed to be column
vectors, as are all subsequent vectors in this paper. Furthermore, all vector
equations are assumed to hold componentwise.
is nondecreasing for 1  k  K (2.3)
nondecreasing for each station i (2.4)
diag() is the diagonal matrix of the service rates and
A pair of vector-valued functions (Q(); T ()) which satisfy (2.1){(2.4) is called a
uid solution.
It can be shown (see [20]) that as functions of time, Q() and T () are
both Lipschitz continuous and hence absolutely continuous. Therefore each
uid
solution (Q(); T ()) has derivatives almost everywhere with respect to time under
the Lebesgue measure. We call a time point t 2 [0; 1) regular if (Q(); T ()) is
dierentiable at t.
A non-idling policy is one in which station i must work at full speed whenever
there is a positive
uid level at station i. We can express this constraint on the
allowable allocation processes by
where
A non-idling
uid solution (Q(); T ()) is one which satises (2.1){(2.5).
We now describe the class of static buer priority (SBP) disciplines for
uid
networks. A SBP discipline  is specied by a permutation of the classes
in the network. Classes listed rst in the permutation have higher priority than
those listed later. Hence, under , the classes at a station are assigned a xed
ranking, and the server cannot devote any eort to processing class k
uid unless
the
uid level is zero for all classes with a higher ranking. If class k has a higher
priority than class ', under , then we write (k) < (').
For the
uid network, it is easier to describe a static buer priority policy
with the following additional denitions:
A
uid network operating under a static buer priority policy  must obey:
So, a non-idling
uid solution (Q(); T ()) for a
uid network operating under
SBP discipline  satises (2.1){(2.5) and (2.10).
2.1. Stability
We now wish to discuss some notions of stability of a
uid network. In
order to do so, we need to dene the concepts of eective arrival rates and tra-c
intensity. For each class k, the eective arrival rate  k indicates the long-term
arrival rate of
uid to class k, due to both internal and external contributions,
that we would expect if the system is in a steady state. We expect such an arrival
rate to satisfy the following vector tra-c equation:
Due to our assumption on P , equation (2.11) always has a unique solution. We
thus dene the vector of eective arrival rates as:
Next, for
We will refer to  i as the nominal workload or tra-c intensity for server i.
We now dene some notions related to the stability of a
uid network.
Denition 2.1 A
uid network is globally stable if there exists a nite time - > 0
such that for each non-idling solution (Q(); T ()) with
all t  -.
Denition 2.2 A
uid network under a static buer priority discipline  is stable
if there exists a time - > 0 such that for each
uid solution (Q(); T ()) satisfying
and (2.10) with
It is well-known (see, for example, Chen [9]) that no
uid solution is stable
unless the tra-c intensity or work arriving per unit time for each station is less
than 1, i.e.
The conditions in (2.12) are often called the usual tra-c conditions. We see
that these conditions are necessary for global stability of the
uid network. Our
primary interest in this paper is to derive necessary and su-cient conditions for
global stability for a class of two-station
uid networks.
A primary motivation for studying the stability of multiclass
uid networks
is the main theorem of Dai [13]. Roughly speaking, Dai's Theorem states that if
the
uid model is globally stable, then any associated queueing network will also
be globally stable, modulo some technical conditions on the distributions. Hence
the global stability conditions given in this paper are also su-cient for global
stability of the associated queueing models. Whether they are also necessary
for global stability of queueing networks is an open question, which we discuss
further in the last section.
3. Submodels
We will nd it useful in subsequent sections to deal with a number of special
cases or submodels, of a general multiclass
uid network (MFN), which was
described in Section 2. These submodels are primarily dierentiated by the type
of routing scheme or routing matrix allowed.
The rst denition is adapted from Chen and Yao [10], which studies networks
with an acyclic transfer mechanism.
Figure

1. An acyclic transfer mechanism network
Denition 3.1 Let
i.e. I(k) is the set of classes from which k is reachable. A multiclass
uid network
is said to be an acyclic transfer mechanism network (ACTN) i k 62 I(k) for all
Essentially,
uid in an ACTN cannot pass through any given buer more than
once. A network that is an ACTN is depicted in Figure 1.
Denition 3.2 A multiclass
uid network is a strictly branching network (SBN)
if
It is an ACTN.
For every class k there exists at most one class ', such that p 'k > 0.
For every class k;  k > 0 i there are no classes ', such that p 'k > 0.

Figure

2. A strictly branching network
A SBN, is then a
uid network in which each class incurs arrivals (either
internally or externally) from only one source. A simple example of a strictly
branching network is pictured in Figure 2. Note that the network in Figure 1 is
not a SBN. The class of SBN's will be the main focus of study in this paper.
Later on, we will see that for the purposes of global stability analysis, the class
of ACTN's and SBN's are equivalent.
Denition 3.3 A multiclass
uid network is a multi-type network (MTN) if
It is a strictly branching network.
p 'k is 0 or 1 for every 1  '; k  K.
A
uid MTN can be associated with a multiclass queueing network which
employs deterministic routing, i.e. there are a number of products types, each
of which follows a deterministic route through the network. Hence, a
uid MTN
does not employ proportional routing. A simple MTN is portrayed in Figure 3.
An MTN with only one type of
uid is often referred to as a reentrant line.
At times, we will need to consider the split network equivalent or SNE of
a strictly branching network. The SNE is a multitype network in which there
is a type for every possible route in the original network. The service rate for
each class in the SNE is the same as in the original network, however, the arrival
rates are set to the eective arrival rate of the exit class of each possible route in
the original network. The SNE of the network in Figure 2 is pictured in Figure

Figure

3. A multi-type network
3. Note that the original proportional route is split into two non-proportional
(deterministic) routes. Furthermore, we set m in the SNE.
The term \equivalent" may be misleading. It is tempting to think that the
global stability conditions for the SNE are the same as the original network, but
this is not the case. The relation between the SNE and the original network is
discussed further in Section 10.
4. The Minimum Flow Problem
We reproduce a review of the Minimum Flow problem from Dai and Van-
deVate [19], since it will play an important role in proving our su-ciency result.
See Ahuja et al. [1] for further background on network
ow problems.
Consider a directed network (N; E) with node set N and edge set E. We
distinguish two vertices s, the source, and t, the sink. Given (possibly innite)
lower bounds we wish to nd a minimum
ow from the source s to the sink t subject to
ow conservation constraints and
edge capacity constraints. Thus, the minimum
ow problem is:
subject to
x sj
for each node i 2 N n fs; tg (4.2)
x tj
each edge (i;
Suppose (x; v) satises (4.1){(4.4). We refer to the vector x as a feasible
ow and
the value v as the value of the
ow x. A minimum
ow is a feasible
ow with
smallest value among all feasible
ows.
An s; t-cut in the network (N; E) is a partition of N into two sets S and T
with s 2 S and t 2 T . The capacity of the cut (S; T ), denoted c(S; T ), is:
(i;j)2E:i2S;j2T
(i;j)2E:i2T;j2S
Note that our denition of capacity interchanges the roles of upper and lower
bounds in the usual denition as applied to the maximum
ow problem. This
denition is appropriate for the minimum
ow problem and is sometimes referred
to as the
oor of a cut. A maximum s; t-cut is one with largest capacity among
all s; t-cuts. Theorem 4.1 is a classic result of network
ows and can be found in
Ahuja et. al. [1, Exercise 6.18, pp. 202].
Theorem 4.1. The value of a minimum
ow equals the capacity of a maximum
s; t-cut.
5. Strictly Branching Two-station Networks
In this section we narrow our focus to the class of two-station
uid SBNs.
This class of models will be the primary focus of study for the remainder of the
paper. Recall that we have arbitrarily labeled one station A and the other station
B in our
uid network.
With the routing restriction on a SBN, we can think of the network as
serving a set of I dierent
uid types. After a
uid type is processed at a station,
it is then proportionally routed to any number of other classes for service. Since
the routing structure does not allow a
uid to revisit a class, we can label each
type with a nite set of class labels. For notational ease, we append a type label
and speak of class (i;
uids. Accordingly, we also add a type label to the
k and  i
k . Finally, we dene
i.e. A i is the set of classes of type i, served at station A.
The routing in a SBN induces a special structure on the classes in the net-
work. Within a type i if class (i; must be visited before class (i; j), then we
will write (i; or in some contexts, simply k  j. So, we see that the
routing induces a partial order on the classes in the network and that  satises
the usual partial order relations. Specically, note that within a
uid type, two
arbitrary classes need not possess the trichotomy property (k  j or k  j or
unlike the case in a multitype network. Also, by our denition, the minimal
element within a type is the only one that has a nonzero exogenous arrival
rate.
It will be useful to group sets of classes at a station into possible excursions,
which are blocks of consecutive visits to a station. Since we allow proportional
routing, possible excursions may overlap one another. We use the \possible"
since it is perhaps useful to envision excursions in queueing paradigm, where the
number of consecutive visits a customer makes to a station may be random due
to probabilistic routing. In the remainder of the paper, we will use the terms
excursion and possible excursion interchangeably.
In

Figure

4, there are two possible excursions at station A, one consisting
of class 1 only and one consisting of classes 7, 8, and 9. At station B there are
also two possible excursions, one consists of classes 2 and 3, which occurs if the
uid (customer) leaves station B after its service at class 3. The other possibility
is an excursion which includes classes 2 through 6, which occurs if the customer
remains at station B after its service at class 3. In particular, we note that the
classes 4, 5, and 6 alone do not comprise a possible excursion.
We will let E denote the set of all possible excursions and E i the set of
all possible excursions for type i
uid, where i 2 I. For each i, we will further
partition
A and E i
B , which are the set of type i possible excursions at
stations A and B, respectively. In Figure 4 there is only one type of
uid, so
A
consists of all the excursions at station A, which encompass classes 1, 7, 8, and
9.

Figure

4. A strictly branching example
Next, the e th excursion of type i classes will be denoted by [i; e] and the
classes in excursion [i; e] will be denoted by E[i; e]. Note that, unlike the case in
an MTN, there is no unique way to number the excursions. We will assume that
the excursions are numbered in an arbitrary, but xed manner, given a specic
network topology. Furthermore, any possible excursion which contains a class k
with  k > 0 is known as a rst excursion. In Figure 4 the only rst excursion is
the excursion consisting of class 1.
Next note that each set E[i; e] can be further divided into the last class in
the excursion '[i; e] and the rest of the classes f [i; e], called rst classes. When
we deal with a set of excursions, we will use curly braces to indicate this. For
example, the set of possible excursions that directly follow excursion [i; e] will be
denoted by fi; e g. Also, we let denote the set of classes which are in
and which are not last classes in any possible excursion.
We need to introduce some denitions related to excursions in order to state
our results succinctly:
Denition 5.1 A set X of excursions such that for each type
then is said to be separating. A separating set X is called
A-strictly separating if it contains no rst excursions at station A. We dene
B-strictly separating sets similarly.
Note that the set of excursions at station A is B-strictly separating and the set
of excursions at station B is A-strictly separating. We call these two sets trivial
separating sets.
Denition 5.2 Each separating set S of excursions induces a collection V (S)
which is described by the following:
is the set of rst classes which follow excursion [i; e] and occur at a
dierent station than [i; e], is the set of rst classes which follow excursion
[i; e] and occur at the same station as [i; e]. When S is strictly separating we refer
to V (S) as a virtual station.
Denition 5.3 We use the notation E to denote a collection of excursions which
have the property that for any two classes (i; which are in E and
which are not contained in the same excursion, we have (i; We refer
to such a set of excursions E as an antichain. Next, we let F  (E) denote the
collection:
We let F  (E) denote the collection:
We also adopt the notation, that for each subset of classes X:
(i;k)2X
We are now prepared to state the main theorem of the paper, which is the
Theorem 5.1. A two-station
uid SBN is globally stable i A < 1, B < 1 and
for each antichain E and each separating set S, we have
A (E))
A (E))
We will refer to these conditions as virtual workload conditions. If such a virtual
condition is violated for set of classes, we call this set of classes a virtual bottleneck.
6. The Lyapunov Function
Clearly, it is di-cult to investigate directly the behavior of all admissible
uid solutions to (2.1){(2.5) in order to analyze the global stability of the networks
under study. Instead, we introduce the concept of a Lyapunov function to aid in
the analysis. Suppose we can nd a function G() of the
uid level vector Q(t)
such that
non-idling
uid solutions Q(t) and all t > -, where - is a
xed time greater than zero.
Such a function G() is called a Lyapunov function for the
uid model. It is
clear from the denition of stability that a
uid network is globally stable if a
Lyapunov function exists for the network.
In this section, we introduce the class of piecewise linear Lyapunov functions
that we will use to prove the su-ciency of the conditions in Theorem 5.1.
This Lyapunov function is a natural extension of the function used by Dai and
VandeVate [19] and we will follow their methodology closely, making appropriate
alterations where needed.
First, we let Z i
k (t) denote the amount of
uid that is in the network at time
t and will receive class (i; service eventually:

where D i
k (t) is the amount of class (i;
uid that has been serviced in the interval
[0; t]. For a general multiclass
uid network, as dened in (2.1){(2.4), we would
Q(t). For an SBN it is always possible to label the
classes such that (Id P 0 ) 1 is lower triangular, allowing us to write Z(t) in the
more explicit form above. In fact, crucial steps in the proof of Theorem 5.1 rely
on this special structure, which is why we restrict our study to the class of SBNs.
Now, for a given x > 0 we dene:
where
i2I
GB
i2I
If we set x i
k for each class (i; k), then we can interpret GA (m; t) as the
total workload for station A in the system at time t. Thus, in general GA (x; t) is
the total weighted workload in the system at time t for station A.
We would like to check for which values of x i
k the G(x; t) as dened above will
be a Lyapunov function. Theorem 6.1, originally proven in Dai and Weiss [20],
simplies this analysis.
Theorem 6.1. Suppose there exist an x > 0 and  > 0 such that G() satises
the following:
i2I
i2I
@t
whenever
i2I
@t
whenever
i2I
where the derivative conditions hold only at regular points t, then G(x; t) is a
We will refer to (6.3){(6.6) as the Dai-Weiss conditions.
7. A Linear Programming Formulation
Now, modifying the development in Dai and VandeVate [19] we can transform
the problem of nding weights x for which G() will satisfy the Dai-Weiss
conditions into checking the feasibility of a linear programming problem. We
start by transforming the conditions (6.3) and (6.4) into inequalities involving
the parameters x.
First, we note that when
i2I
GA reduces to:
i2I

i2I

and GB becomes:
i2I

i2I



for each i 2 I and Multiplying through by  i
j we obtain:
again for each i 2 I and . Since we only consider non-negative x, it is
su-cient to require (7.2) hold only for I and each possible
excursion [i; e] at station B.
Similarly, enforcing (6.4) yields:
I and for each possible excursion [i; e] at station A.
Note that above we used the fact that each possible excursion can be identied
by a unique last class.
We next transform the Dai{Weiss derivative conditions (6.5) and (6.6) into
inequalities involving x. When
i2I
the non-idling conditions require:
i2I
_
We also have,
_
i2I
_
i2I
_
i2I
i2I
_
GA (x; t)   for each D(t) satisfying (7.3) i:
i2I
for each i 2 I and j 2 A i , since the second summand in (7.6) is a non-negative
convex linear combination of the terms on the right-hand side of the equation
above.
Similarly, (6.6) will be satised i
i2I
for each i 2 I and
We now combine the four sets of inequalities derived above to yield the
following
maximize  (7.7)
subject to:
A (7.9)@ X
i2I
i2I
The LP above is easier to work with if we set  i
k to obtain the
transformed linear program (TLP):
maximize  (7.13)
subject to:
I and (7.14)
excursion
I and (7.15)
excursion
i2I
i2I
We note that if a strictly branching network has yield loss only (i.e. for all
only one class (i; j)) then the above TLP has the same
form as the Dai-VandeVate LP and thus Theorem 5.1 follows immediately from
their results. The terminology \yield loss" comes from the queueing context. A
queueing network with yield loss only is one in which customers essentially follow
a deterministic route, except that there may be some positive probability that a
customer will exit the network after the completion of any stage of work (due to
a manufacturing defect, for example).
The next proposition follows as an immediate generalization of Proposition
4.1 in Dai and VandeVate [19]:
Proposition 7.1. If the TLP given by (7.13){(7.18) has unbounded objective
values, then each solution (x; ) with  > 0 provides weights x > 0 such that
G(x; t) is a Lyapunov function for the
uid network.
8. A Network Flows Formulation
With the TLP in the previous section, we have reduced the stability analysis
of our
uid network to the problem of checking the nature of the solutions to a
linear program. In fact, we can further simplify the analysis by making some
useful observations which allow us to transform the TLP into a parametric net-
work
ow problem. Since the analysis again closely follows the Dai-VandeVate
framework, we only provide an outline for some of the steps.
As in the Dai-VandeVate analysis, we observe that the constraints of the
dene a cone. Thus, if there is one positive solution, then there is a solution
which satises:
i2I
i2I
As in the Dai-VandeVate framework, we can treat  as a parameter and then
express (7.16) and (7.17) as follows:
Next, we add slacks
e ) and write (7.14){(7.15) as:
I and (8.5)
excursion
I and (8.6)
excursion
A .
For each possible excursion [i; e] at Station B, we take its corresponding
equation of the form of (8.5) and add to it all equations of the type (8.6) that
correspond to successor excursions in fi; e
A g and subtract all equations of the
type (8.5) that correspond to successor excursions in fi; e
g. Consistent with our
earlier notation, we let
A g denote the set of possible excursions at Station
A which directly follow excursion [i; e]. We dene
similarly. We next
multiply by -1 to obtain:
A
A
Similarly, we obtain
A
e
A
for excursions [i; e] at station A.
These transformations give us the following network
ow problem:
maximize  (8.7)
subject to:
A g
e
A g
for
A
A
A
for
i2I
i2I
The network
ow problem above can be characterized as follows. It has:
A node for each possible excursion [i; e] corresponding to (8.8) and (8.9).
A node for station A and station B corresponding to (8.10) and (8.11).
A node called the root corresponding to the redundant constraint
s iX
obtained by adding (8.8){(8.11) and multiplying by -1.
The edges in the network are the following:
1. An edge from the node for station A to the node for possible excursion [i; e]
at station A. This corresponds to the variable y
'[i;e] and has lower bound
'[i;e] .
2. An edge from the node for possible excursion [i; e] at station B to the node
for station B. This corresponds to the variable y
'[i;e] and has lower bound
'[i;e] .
3. An edge from the node for station A to the node for possible excursion [i; e]
at station B for each class (i;
A g. These edges correspond to the
variables y i
k for the classes in
A g. The edge for class (i; k) has lower
bound  i
k .
4. An edge into the node for station B from the node for possible excursion
[i; e] at station B for each class (i;
B g. These edges correspond
to the variables y i
k for the classes in
g. The edge for class (i;
lower bound  i
k .
5. An edge from the node for possible excursion [i; e] at station A to the node
for station B for each class (i;
B g. These edges correspond to the
variables y i
k for the classes in
g. The edge for class (i; k) has lower
bound  i
k .
6. An edge into the node for possible excursion [i; e] at station A from the node
for station A for each class (i;
A g. These edges correspond to the
variables y i
k for the classes in
A g. The edge for class (i; k) has lower
bound  i
k .
7. An edge from the node for station A to the root for each class (i;
served at station A. These edges correspond to the variables y i
k for
the classes in f[1; i] served at station A. The edge for class (i; k) has lower
bound  i
k .
8. An edge from the root to the node for station B for each class (i;
served at station B. These edges correspond to the variables y i
k for
the classes in f[1; i] served at station B. The edge for class (i; k) has lower
bound  i
k .
9. An edge from the node for excursion [1; i] at station A to the root. This
edge corresponds to the variable s i
1 and has lower bound 0.
10. An edge from the root to the node for excursion [1; i] at station B. This
edge corresponds to the variable s i
1 and has lower bound 0.
11. An edge from the node for each possible excursion [i; e] at station A to the
node for the preceding excursion (which is unique) at station B (if [i; e
These edges correspond to the variables s i
e and have lower bounds 0.
12. An edge from the node for each possible excursion [i; e] at station A to the
node for the preceding excursion (which is unique) at station A (if [i; e
A i ). These edges correspond to the variables s i
e and have lower bounds 0.
13. An edge to the node for each possible excursion [i; e] at station B from the
node for the preceding excursion (which is unique) at station A (if [i; e
A i ). These edges correspond to the variables s i
e and have lower bounds 0.
14. An edge to the node for each possible excursion [i; e] at station B from the
node for the preceding excursion (which is unique) at station B (if [i; e
These edges correspond to the variables s i
e and have lower bounds 0.
15. An edge from the node for station A to the node for station B. This edge
corresponds to the variable  and has lower bound 0.
The remainder of this section parallels the development in Dai and Vande-
Vate [19]. Hence, we merely introduce the notation needed for our more general
class of networks and outline the arguments. For a more complete development,
the reader should refer to the aforementioned work.
As in Dai{VandeVate, we convert our problem into a Minimum Flow Prob-
lem. We retain some other Dai{VandeVate conventions. Given an A; B-cut
(L; R), we let LA denote the excursions in L that are served at Station A and
LB denote those served at Station B. Similarly, we let RA denote the excursions
in R served at Station A and RB denote those at Station B.
We refer to an A; B-cut with the root in L as an L-cut. An A; B-cut with the
root in R is a R-cut. Note that since the upper bound on each edge is innite, an
R) in this network has nite capacity if and only if no edge extends
from a node in R to a node in L, i.e., if and only if (L; R) satises:
1. If [i; e] 2 LA , then possible excursions
A g are in LA ,
2. If [i; e] 2 RB , then possible excursions
are in RB ,
3. If [i; e] 2 LB , then possible excursions
A g are in LA ,
4. If [i; e] 2 RA , then possible excursions
are in RB ,
5. If (L; R) is an R-cut, then [i; 1] \
6. If (L; R) is an L-cut, then [i; 1] \
Otherwise, the capacity of the cut is 1. Therefore, we now have the following
lemma, which is framed in terms of separating sets.
Lemma 8.1. An L-cut (L; R) has nite capacity only if LB [RA is an A-strictly
separating set. Similarly, an R-cut (L; R) has nite capacity only if LB [ RA is
a B-strictly separating set.
We can proceed as in Dai and VandeVate to obtain the theorem below,
which expresses the stability of the network in terms of the \cut conditions."
Theorem 8.2. A two-station SBN with service times m and eective arrival
rates satisfying the nominal workload conditions is globally stable
if for each non-trivial A-strictly separating set S 0 and non-trivial B-strictly
separating set S,
We call the conditions in (8.15) the cut conditions.
9. Su-ency of the Virtual Workload Conditions
In this section we prove the following lemma that, in conjunction with Theorem
8.2, proves the su-ciency part of Theorem 5.1.
Lemma 9.1. Consider a two-station SBN with given eective arrival rates and
service times. If the arrival rates and service times satisfy the virtual workload
conditions as given in (5.1), then they also satisfy the cut conditions (8.15).
Proof. Each cut condition is dened by a pair of non-trivial separating sets, S
and S 0 . We show that the cut conditions induced by the pair (S; S 0 ) is implied
by a pair of virtual workload conditions.
We rst need to chose an antichain E , which is induced by the pair (S; S 0 ).
For each type i, we choose a set E i that will usually contain several elements, due
to the branching nature of our networks. In the multitype case, E i contains only
one element for each i 2 I.
We now specify how the set E i is chosen. For each type, consider the SNE.
Any class that is in S or S 0 in the original network remains in these sets in the
SNE. For each type i in the original SBN, we now have a number of sub-types in
the corresponding SNE, one for each possible route in the original network. Let
(i; j) be a sub-type of type i from the original SBN and let J i be the number sub-types
of type i. For each (i; j), we chose an index
j according to the following
modied Dai-VandeVate rules. We let ^
be the largest index r such that
1.
2.
3. [i; r] 62 S 0 .
For each (i; j), we chose another index e i
similarly, letting e i
j be the largest
index r such that
4.
5.
6.
Now, for each (i; j), we set r i
g. We then let
Note that the r i
's need not be distinct. We set
We note that the set E is an antichain and has the following properties:
c)
d)
These properties allow us to go through analogous algebra to Dai and Van-
deVate to obtain the cut condition from the virtual workload conditions. The
antichain E and the separating set S 0 induce the virtual workload condition:
A (E))
A (E))
Similarly, E and the separating set S induce the virtual workload condition:
A (E))
We show that (9.1) and (9.2) imply the cut condition for the pair (S
From (9.1) we have that
A (E))
A (E))
and from (9.2) we have that
A (E)) m(VA (S) n F
A (E))
A (E))
Thus,
A (E)) m(VA (S) n F
A (E))
A (E))
Now, (a) implies
A (E))  m(VA (S)):
Next we note that we have the following
1.
directly from (d)
2.
directly from (e)
3.
;, from 1.
Recalling the denition of V (S), the above imply that
Thus, we have
Once again from (a) we have
Using a similar argument as before, we have that (b) and (c) imply,
Thus, (9.3) implies that
which is exactly the cut condition for the pair S 0 and S.
10. Necessity
The su-ciency of the conditions in Theorem 5.1 was proved in the last
several sections. We now turn our attention to proving the necessity via the
next few lemmas. The necessity essentially follows from Dai and VandeVate's
arguments with minor adjustments.
The rst lemma we need is Lemma 7.1 from Dai and VandeVate [19]:
Lemma 10.1. Let C be a set of classes such that
Each non-idling
uid solution (Q(); T ()) satisfying
(i;k)2C
_
for each regular point t is unstable.
Proof. The proof for the class of networks we consider is analogous to that given
in Dai and VandeVate.
The set C in Lemma 10.1 represents classes that form a virtual station.
Under an appropriate static buer priority policy, only one of the classes in C
may be served at any time in any queueing network which corresponds to the
uid model (i.e. a network which has the same topology and mean arrival and
service rates).
Next, we adapt another lemma from Dai and VandeVate [19] to networks
with proportional routing. This lemma enables us to consider the eect of \push-
starting" some set classes that occur early in the route of a
uid type.
We consider a collection of excursions E that partitions the classes into those
of F  (E) and the remainder that we denote as R(E).
Let
~
A (E))
for (i;
~
for (i;
Consider the induced
uid model on the classes of R(E):
k () is nondecreasing; (i;
(i;k)2R A (E)
k (t) is nondecreasing; (10.6)
k (t) is nondecreasing; (10.7)
(i;k)2R A (E)
_
(i;k)2R A (E)
_
where, ~
k for (i; R(E). For each type i 2 I, we let ~
and T i
to model the arrivals to the induced
uid network. Note that
in the induced network the eective arrival rates to the remaining classes are the
same as in the original network.
Lemma 10.2. If the
uid model (10.4){(10.9) is unstable, then the
uid model
for the full
uid network is unstable.
Proof. The proof of this lemma is again analogous to the proof of Lemma 7.2
in Dai and VandeVate [19].
Proof. [Necessity Proof of Theorem 5.1] With Lemma 10.2 in hand, it is su-cient
to show that if the virtual station V (S) corresponding to some strictly separating
set S satises
then there is an unstable
uid solution. The set of classes V (S) is a virtual station
in any corresponding queueing network and so there exists a static buer priority
policy under which no two classes in V (S) can be served simultaneously. A
description of virtual stations and a generalization known as pseudostations, plus
details on the construction of such a static buer priority policy can be found
in Hasenbein [22]. [Pseudostations have also been referred to in the literature
as K-virtual stations [4] and were investigated independently by Bertsimas [2]].
Thus, if we examine
uid limits (Q(); T ()) of the type dened in Dai [14], we
see that they are
uid solutions which satisfy (10.1). By Lemma 10.1, the
uid
network is not globally stable. This completes our necessity proof and the proof
of Theorem 5.1.
11. Examples and Conclusions
We rst give an example of the application of Theorem 5.1. The
uid
network depicted in Figure 2 is in the class of strictly branching networks and
hence we may apply Theorem 5.1 to obtain the following corollary.
Corollary 11.1. Consider the
uid network of Figure 2 with parameters
and (m The
uid model is globally stable if and only if the
following four conditions hold:
The rst two conditions are the usual tra-c conditions. The third conditions is a
virtual workload condition induced by the virtual station consisting of classes 2, 4
and 6. The fourth condition is a \push-start" condition induced by the antichain
2g and the virtual station f4; 6g.
Next, we note that Theorem 5.1 is stated only for networks which are SBNs.
We now brie
y outline arguments indicating that the theorem actually holds for
any ACTN. We rst claim that any ACTN can be equivalently relabeled as an
SBN by adding a nite number of class labels. For example, if more than one
class feeds a particular buer, we simply divide the incoming
uid into dierent
buers, depending on the buer in which the
uid was last processed. Figure 5
gives an example of an ACTN relabeled as a SBN.
Add class labels to obtain
a strictly branching network

Figure

5. An ACTN relabeled as an SBN.
Once the network has been relabeled, we note that we can identify any
uid
solution (Q(); T ()) in the original network, with a corresponding unique
uid
solution ( ~
T ()) in the new network and vice versa. The main point to note
here is that in the original ACTN, the set of non-idling policies include those
which determine processing priority at a buer based on the processing history
of the
uids in that buer. Thus any allocation policy implemented in the SBN
can also be implemented in the ACTN. In terms of global stability, the ACTN
and corresponding SBN are equivalent. Hence, Theorem 5.1 provides necessary
and su-cient conditions for global stability of any ACTN, after performing the
appropriate transformation to an SBN.
We have derived necessary and su-cient stability conditions for two-station
uid networks, provided that these networks were restricted to the class of acyclic
transfer mechanism networks, essentially a class of networks that does not allow
revisits to a class. In fact, our results could actually be extended further to any
uid network which allows only a nite number revisits to a class, since such a
network could be equivalently relabeled as an ACTN. Practically speaking, this
should be a perfectly satisfactory class of networks to model real-life situations
(since jobs rarely make an innite number of revisits in the factory). However,
this still leaves one with a theoretical yearning to extend the theory to the full
class of two-station
uid open multiclass networks.
Unfortunately, the methods used to demonstrate the su-ciency of the conditions
in Theorem 5.1 cannot be directly extended to a larger class of networks.
Our ability to transform the TLP of Section 7 into a network
ow problem relies
on the fact that in any SBN, the classes can be labeled such that the routing
matrix P is upper triangular. For example, consider the network shown in Figure
6. If network is an ACTN and we can obtain the stability
region via the methods outlined in this paper. However, if q 2 (0; 1), then the
network shown is not in the class of ACTN's and in fact we can derive an LP as in
Section 5, but it can be shown that this LP cannot be transformed into a network
ow problem. One possible way to overcome this di-culty is to model a more
general network as a SBN with an innite number of classes. In this case, we
can again write down a similar LP and transform it into a network
ow problem
with an innite number of nodes. Of course, the problem then lies in showing
that the capacity of this network is determined by only a nite number of cut
conditions. While this route seems promising, it appears di-cult to carry out. If
this analysis were successful, it would essentially complete our understanding of
the global stability properties of two-station
uid networks and fully complement
the results of Bertsimas, et. al. [3].
A further point to be noted is that our results are valid only for
uid net-
works. For the corresponding class of queueing networks, our knowledge is still
lacking. The results of Dai and VandeVate [18] and Hasenbein [22] imply that
our conditions are in fact necessary and su-cient for two-station queueing net-
Figure

6. A non-ACTN
uid network
works whose
uid model is an ACTN if the stability conditions involve virtual
stations only (no \push-start conditions"). Unfortunately, recent examples given
by Bramson [8] and Dai, Hasenbein, and VandeVate [15] indicate that stability
conditions for the
uid model may not always coincide with those in the queueing
model. In this respect, the full connection between the stability of the stochastic
and
uid models still needs to be explored.

Acknowledgments

: The author would like to thank, Jim Dai and John
VandeVate, for support and input while performing this research. A portion of
this paper was written while John Hasenbein was visiting the Centro de Inves-
tigacion en Matematicas (CIMAT) in Guanajuato, Mexico. He would like to
thank CIMAT and the National Science Foundation, who jointly provided an
International Research Fellowship (NSF Grant INT-9971484), which made this
visit possible.



--R

Network ows: theory
Lecture notes on stability of multiclass queueing networks.
Stability conditions for multiclass uid queueing networks.
Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions.
Instability of FIFO queueing networks.
Convergence to equilibria for uid models of FIFO queueing networks.
Convergence to equilibria for uid models of head-of-the-line proportional processor sharing queueing networks
A stable queueing network with unstable uid model.
Fluid approximations and stability of multiclass queueing networks I: Work-conserving disciplines
Stable priority disciplines for multiclass networks.
Stability of multiclass queueing networks under FIFO service discipline.
Stability of multiclass queueing networks under priority service disciplines.
On positive Harris recurrence of multiclass queueing networks: A uni

Stability gap between uid and queueing networks.
Stability of a three-station uid network
Stabilizing batch processing networks.
Global stability of two-station queueing networks
The stability of two-station multitype uid networks
Stability and instability of uid models for re-entrant lines
A multiclass network with non-linear
Necessary conditions for global stability of multiclass queueing networks.
Networks of waiting lines.
Generalized Round-Robin Service Disciplines in Stochastic Networks with Setup: Stability Analysis and Diusion Approximation
Networks of queues with customers of di

Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems
Fluctuation smoothing policies are stable for stochastic reentrant lines.
Distributed scheduling based on due dates and bu
Transience of multiclass queueing networks via uid limit models.
Ergodicity of stochastic processes describing the operation of open queueing networks.
'First come, rst served' can be unstable!
On the stability of multiclass queueing networks: a relaxed su-cient condition via limiting uid processes
--TR
acyclic routing;push start;multiclass queueing network;fluid model;virtual station;stability