Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.philol.msu.ru/~lex/khmelev/local/khanin.pdf Äàòà èçìåíåíèÿ: Thu Oct 17 00:00:00 2002 Äàòà èíäåêñèðîâàíèÿ: Sat Dec 22 07:57:40 2007 Êîäèðîâêà:

MOSCOW MATHEMATICAL JOURNAL Volume 1, Numb er 3, July­Septemb er 2001, Pages 407­419

STEADY SOLUTIONS FOR FIFO NETWORKS
K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV Dedicated to Robert Minlos on the occasion of his 70th birthday

Abstract. We consider the fluid model of a reentrant line with FIFO discipline and look for solutions with constant flows (steady solutions). In the case of constant viscosities we prove the uniqueness of such a solution. If viscosities are different, we present an example with multiple steady solutions. We also prove that for some classes of reentrant lines uniqueness holds even if the viscosities are different.
2000 Math. Subj. Class. 90B10, 94C99, 37­XX. Key words and phrases. Kelly networks, fluid models, uniqueness of steady solution, fixed points.

1. Introduction In this paper we study multi-class networks with the FIFO serving discipline. We consider deterministic fluid models and look for solutions with stationary flows (steady solutions). The class of such solutions is the same for some other disciplines in multi-class networks like LIFO or processor sharing. Fluid limits and fluid models for queueing networks were first introduced in [9]. A similar scaling for stochastic processes of different kind (random walks in finitedimensional positive orthants) was studied by V. A. Malyshev and his coauthors, see references in the review [7]. Analogous deterministic discrete models were also studied in [6]. Tra jectories of a fluid model are solutions of a complicated system of functional equations with delay in the space of monotone Lipschitz continuous vector-functions (see [4, 10]). This system of equations can be derived from the Euler limit for the stochastic process which describes the evolution of a queueing network in time. The whole construction allows one to prove the convergence of stochastic processes to the limiting fluid dynamics. Note that the system of fluid equations also depends on "excessive" variables (vanishing in the Euler scaling). These variables provide
Received July 31, 2001; in revised form Septemb er 11, 2001. Third named author supp orted in part by RFBR Grant 99-01-00003, CRDF Grant RM-2085, and INTAS Grant. Fourth named author supported in part by RFBR Grants 00-01-00571 and 00-15-96116, and INTAS Grant.
c 2001 Indep endent University of Moscow

407


408

K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV

the same phase space for both stochastic and limiting deterministic dynamics (see, for instance, [8]). In [9] the fluid dynamics formalism was developed in order to obtain ergodicity conditions for original stochastic processes in terms of the behavior of the limiting fluid tra jectories. The fluid behavior was found to be highly nontrivial. Surprisingly, the ergodicity conditions happened to be quite different from naive "common sense" expectations that the system is ergodic whenever the workload at each node is less than 1 (see [6], [9] for the first counterexamples and [1, 2] for those in the FIFO context). This phenomenon is closely related to the nonuniqueness of trajectories for fluid dynamics and self-similarity of fluid tra jectories (see [10, 8]). In examples mentioned above, it follows from self-similarity that there exist infinitely many nontrivial solutions with zero initial conditions (the empty state of the queueing system). Moreover, for all these fluid tra jectories the set of non-empty nodes is switched infinitely often in any finite neighbourhood of t = 0. Below we refer to such complicated behavior as turbulent-like. Let us also mention the study by V. A. Malyshev [7] of similar bifurcation phenomena for limiting tra jectories in the Euler scaling in the case of random walks in finite-dimensional positive orthants. To the best of our knowledge, the question of uniqueness of a solution is open for all nontrivial fluid models with infinite-dimensional state space (like the space of Lipschitz functions in the FIFO case, in contrast to networks with priority disciplines and Jackson networks for which the phase space is finite-dimensional). In this paper we consider the simplest fluid tra jectories with constant flow rates for all types of fluid originating from the empty state of the network (steady solutions ). J
1

J

2

J

3

1 7

2 6 8

3 4 5

Figure 1. An example of reentrant line Let us begin with a single reentrant line with K nodes. Such a line is characterized by a partition of a finite set {1, . . . , n} of fluid classes into K disjoint i i subsets Ji = {j1 , . . . , jni } (nodes), see Fig. 1. Denote by i(j ) the index i such that j Ji . The maximal service capacities of nodes are given implicitely by the vector (v1 , . . . , vn ) of positive numbers (mean serving times or viscosities ). The prelimiting random process describes a queueing network consisting of K FIFO queues.


STEADY SOLUTIONS FOR FIFO NETWORKS

409

Customer arrivals at the network are described by the stationary metrically transitive flow with average interarrival times equal to 1. Each customer is served in n stages. On the j th stage the customer joins queue i(j ) and its mean service time (the mean time during which the customer is the first in the queue) is equal to vj . We say that this customer is of class j until it is served at the station i(j ) and joins the next queue i(j ) (which may, incidentally, be the same queue) or leaves the network forever if j = n. We say that the reentrant line is of Kel ly type if the mean service time at node i does not depend on j J (i), i.e., vj = Vi for all j Ji , i = 1, . . . , K . A steady solution is described by an (n + 1)-vector x = (x0 , x1 , . . . , xn ), where xj , j = 1, . . . , n - 1 is the rate of flow leaving class j and joining class j + 1 or leaving the network forever if j = n. The vector x must satisfy the conditions (1) x0 = 1, (2) i = 1, . . . , K . j Ji xj vj 1, (3) xs max 1, j Ji xj -1 vj = xs-1 for all s Ji , i = 1, . . . , K .

(1.1)

The value of x0 is the exogenous inflow. Condition (2) gives the service capacity restriction on the outcoming flow from node i. Condition (3) says that an equal fraction of each incoming flow to any class of node i passes through to the next class. This is a result of the FIFO discipline at the node and of the steadiness of the solution. Notice that the same condition also holds in the case of some other disciplines in multi-class networks, like LIFO or processor sharing. Conditions (1.1) are derived from the more general ones (~ x0 > 0 arbitrary, 1) ~ (~ 2) ~~ i = 1, . . . , K . j Ji xj vj ci , ~ xs max ci , (3) ~ ~~ ~ j Ji xj -1 vj = xs-1 for all s Ji , i = 1, . . . , K . by the rescaling xj = xj /x0 and vj = vj x0 /ci ~~ ~~ Note that, if
j J (j )

. (1.2)

vj < 1,
i

for any node Ji , i = 1, . . . , K , then there exists a unique trivial steady solution xj 1 for j = 1, . . . , n. It is also known (see [3]) that if (1.2) holds, then, for a reentrant line of Kelly type and for any initial state of fluid, the total amount of fluid in the network vanishes in finite time. The main theorem of this paper asserts that in the case of reentrant lines of Kelly type there exists a unique steady solution for any steady input without restriction (1.2). Let us notice that for solutions that are not necessary steady the question of uniqueness remains open. We conjecture that for reentrant lines of Kelly type the uniqueness of fluid tra jectories persists in the general nonsteady case. On the contrary, in the case of different viscosities and more than one node, it is possible to have multiple steady solutions as Example 2.6 demonstrates.


410

K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV

As we have mentioned above, there might exist many nonstationary tra jectories originating at the same initial state of the network. However, the nonuniqueness of steady solutions is a new and unexpected phenomenon. This fact implies the existence of even more complicated singularities of fluid tra jectories than the turbulent-like examples mentioned above. In Section 2 we introduce and study special dynamical systems (mappings) that arise naturally from the model presented above. Fixed points of these mappings correspond to steady solutions of the corresponding reentrant lines. We present an example of nonuniqueness of a steady state for a general reentrant line and prove other particular results for general reentrant lines. In Section 3 the uniqueness theorem for networks of Kelly type is proved (Main Theorem). 2. Dynamical systems Let us define a mapping M : Rn Rn by the following rule: M : (x1 , . . . , xn ) + + (x1 , . . . , xn ), where ~ ~ xs = ~ xs max 1,
-1
i

j J

xj

-1 vj

for s Ji ,

i = 1, . . . , K ,

and x0 = 1. Clearly x Rn satisfies (1.1) iff M x = x. Hence, the question of + existence and uniqueness of a steady solution (1.1) can be reduced to the analysis of fixed points of the mapping M . The image M Rn belongs to the compact convex set + X= x Rn : +
j J
i

vj xj 1, i = 1, . . . , K .

Since M is continuous, the Brouwer principle immediately implies the following lemma. Lemma 2.1. There exists an x X R
n +

such that M x = x. 1. In this case, the that if all nodes are a fixed point of the , K. (2.3)

We say that the node i is overloaded if j Ji xj -1 vj > queue length at the node i increases linearly in time. Notice overloaded, then any steady solution of the reentrant line is mapping N : xi xi , where x0 = 1 and ~ xs-1 xs = ~ for s Ji , i = 1, . . . j Ji xj -1 vj The mapping N is well defined for all x Rn , x > 0. + Lemma 2.2. Let v = mins Y= x Rn : +
j J
i

=1,...,n

vs , v = max v nv
s

s=1,...,n

vs and

xj vj = 1, xs
n+1

, i = 1, . . . , K, s = 1, . . . n .

Then N Y Y and N

x Y for any x Rn , x > 0. +


STEADY SOLUTIONS FOR FIFO NETWORKS

411

Proof. Notice that for any x Y we have x (1/v , . . . , 1/v )T . Therefore, if x = N x then ~ xs = ~ xs
j J -1

i(s)

xj

-1 vj



(v /nv )s-1 (v /nv )s (1/v ) j Ji(s) vj nv /v

-1

=

v nv

s

(2.4)

(since x0 = 1, estimate (2.4) holds for s = 1). Hence, N Y Y , as required. Let Y0 = Yl = x Rn : +
j J
i

x Rn : +
j J
i

xj vj = 1, i = 1, . . . , K , v nv
s

xj vj = 1, xs

, i = 1, . . . , K, s = 1, . . . , l .

Notice that N x Y0 for any x Rn , x > 0, and for any x Y0 we have, again, + x (1/v , . . . , 1/v )T . Using estimate (2.4), we get N Yl Yl+1 . Therefore, N n+1 x Yn = Y . Since Y is compact and convex and N is continuous on Y , we can apply the Brouwer principle once more. Hence, the following lemma holds. Lemma 2.3. There exists an x Y R
n +

such that N x = x.

It is easy to see that any fixed point of the mapping N satisfies a system of K equations. Lemma 2.4. For any x = N x we have x = (x(1, a), . . . , x(n, a))T , where a = (a1 , . . . , aK ), x(0, a) = 1 and x(j, a) = x(j - 1, a)ai a1 , . . . , aK satisfy a system of K equations : x(j, a)vj = 1.
j J
i

(j )

. The variables

Proof. Let us denote ai = 1/ j Ji xj -1 vj , where x0 = 1. Then, (2.3) implies that xs = xs-1 ai(s) for all s = 1, . . . , n, and hence xj = x(j, a). The system of equations arises from the conditions j Ji xj vj = 1, see Lemma 2.3. The construction of x(j, a) for a reentrant line from Fig. 1 is illustrated in Fig. 2. An anologous assertion holds for fixed points of the mapping M , but the corresponding system of equations for variables a1 , . . . , aK happens to be non-algebraic. Lemma 2.5. For any x = M x we have x = (x(1, a), . . . , x(n, a))T , where a a1 , . . . , (1) (2) = (a1 , . . . , aK ), x(0, a) = aK 1 satisfy the fol lowing if j Ji x(j, a)vj < 1 then otherwise j Ji x(j, a)vj = 1, x(j, a) = x(j - 1, a)ai conditions : ai = 1, 1.
(j )

and the variables


412

K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV

J

1

J

2

J

3

a1 a2 a2 a3 123

a1 a2 a1 a2 a3 23 a2 a3 a3 123

a1 a2 a3 a1 a2 a2 3 a1 a2 a3 3

Figure 2. A fixed point for reentrant line In the next section we prove that, for a reentrant line of Kelly type, a steady solution (a fixed point of M ) is unique. However, in general, there can exist more than one steady solution of a reentrant line with arbitrary viscosities. In other words, mappings M and N can have different fixed points x and x for all of which all the nodes are overloaded, that is ai < 1 and j Ji x(j, a)vj = 1 for all 1 i K. Example 2.6. Let us construct two different overloaded solutions of a line with K = 2, n = 5, J1 = {1, 2, 5} and J2 = {3, 4}. Any overloaded solution has the form x = (a, a2 , a2 b, a2 b2 , a3 b2 ), a, b 0, and the equalities v1 a + v2 a2 + v5 a3 b2 = 1, v3 a2 b + v4 a2 b2 = 1 (2.5)

must hold. Let us choose a = b = 1/2 and a = 3/4, b = 1/4. Now, it is easy to find viscosities vj , j = 1, . . . , 5, such that (2.5) holds together with v1 a + v2 a 2 + v5 a 3 b 2 = 1, In particular, one can choose v1 = 15 1 220 56 32 , v2 = , v5 = , v3 = , v4 = . 32 144 9 9 9 v3 a 2 b + v4 a 2 b 2 = 1. (2.6)

Examples of multiple steady solutions can be constructed on the basis of the following simple observation. Lemma 2.7. Let , Rn , = , , > 0 and n 2. Then the relations + (w, ) = 1, (w, ) = 1

are consistent with respect to w Rn , w > 0 if and only if the vector - has + both positive and negative components, that is, if (i - i )(j - j ) < 0 for some 1 i, j n.


STEADY SOLUTIONS FOR FIFO NETWORKS

413

In Example 2.6 we have 1 = (a, a2 , a3 b2 )T , 1 = (a , a 2 , a 3 b 2 )T and the existence of a required positive vector w1 = (v1 , v2 , v5 )T is ensured by Lemma 2.7, since the difference vector 1 - 1 = (a - a , a2 - a 2 , a3 b2 - a 3 b 2 )T has both positive and negative components. The same argument works for 2 = (a2 b, a2 b2 )T , 2 = (a 2 b , a 2 b 2 )T , and w2 = (v3 , v4 ). Note that in example (2.5)­(2.6) one of the subsets contains three elements. We show next that, if each subset in the partition of {1, . . . , n} consists of less than 3 elements, then a steady solution is unique. We use the l1 -norm x = |x1 | + · · · + |xn | which induces the matrix norm A = maxj =1,...,n Aej on the space of linear operators A : Rn Rn , where {ej } are the unit vectors. Prop osition 2.8. Suppose that ni = |Ji | 2 for al l j = 1, . . . , K . Then there exists a unique positive fixed point x = N x and there exist < 1 and C > 0 such that N m x - x C m for al l x Rn , x > 0, m N. + Proof. We consider the case of all subsets containing exactly 2 elements. The proof in the case when some of the subsets are singletons is essentially the same. By Lemma 2.2, N n+1 x Y for all x Rn , x > 0. Therefore, without loss of + generality we can assume that x (, . . . , )T for some > 0. Define rs = ln xs . Then r0 = 0 and i i i i rs = rs-1 - ln(vj1 erj1 -1 + vj2 erj2 -1 ) ~
i i for s = j1 , j2 for all i = 1, . . . , K , where r r. Let us find the Jacobi matrix DR ~ 0, s 1 - i, s = j1 rs ~ i -j1 , s= = rk -j i , s= 2 1 - i, s = j2 i i Ji = {j1 , j2 }. Denote by R the mapping = ( rs / rk ): ~

Ji , i j1 , i j2 ,
i j1 , i j2 ,

i i k = j1 - 1, j2 - 1, i k = j1 - 1,

i k = j2 - 1,

where

s =

i vj1

er

i j1 - 1

vs ers-1 i + vj2 er

i j2 - 1

,

s Ji ,

i = 1, . . . , K.

Clearly, s 1. One easily sees that, for any ei and r, the inequality DR(r)ei 1 holds. Therefore, for any r1 , r2 we have
1

Rr 2 - Rr

1

=
0

DR( (s)) (s) ds r2 - r1 ,

(2.7)

where (s) = (1 - s)r1 + sr2 . Let x = N x be a fixed point of N . Then the vector r with components T ri = ln x is a fixed point for R. Let P = |DR(r )| , where | · | is applied to DR i T component-wise and denotes transposition. Then P is a transition matrix for a finite Markov chain with states {1, . . . , n} which terminates on hitting the state n, i.e., the row corresponding to the state n consists of zeros. Since the state n is absorbing, the spectral radius of P is strictly less than 1. Hence, the spectral radius of DR(r ) is also strictly less than one. Therefore, r is locally stable and attracts


414

K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV

with exponential rate all points from some neighbourhood of r . This together with (2.7) implies that r attracts all r ln Y with exponential rate uniformly in r ln Y . Since Rn+1 r ln Y for any r Rn , the uniform exponential convergence takes place for all r Rn as required. If ni = 2 not for all i, then one can still show that (2.7) holds. Furthermore, in T this case the corresponding Markov chain with transition matrix P = |DR(r )| has more than one absorbing state. Hence, all the above arguments hold and there is the global convergence to a unique stationary point r . An analogous assertion holds for the mapping M . Prop osition 2.9. Suppose that ni = |Ji | 2 for al l j = 1, . . . , K . Then there exists a unique fixed point x = M x and there exist < 1 and C > 0 such that M m x - x C m for al l x Rn , m N. + Proof. We give only a sketch of the proof. Again, consider the case of all subsets containing exactly 2 elements. As in the proof of Proposition 2.8, we pass to the logarithmic coordinates r = ln x. Notice that one can represent R : r r as the ~ composition R = LS , where S is a shift operator S (r1 , . . . , rn ) = (0, r1 , . . . , r
n-1

)

and L is the normalization operator which acts on each node Ji independently of other nodes: L(a, b) = where (a, b) = (r
i j1 -1

(a, b), (a - W, b - W ),
i j2 -1

if W = va ea + vb eb 1, if W = va ea + vb eb > 1,

,r

). Let us denote

= {(a, b) : va ea + vb eb 1} and > = {(a, b) : va ea + vb eb > 1}. It is easy to see that is a convex domain. Denote by m1 = (a1 , b1 ) and m2 = (a2 , b2 ) two points in R2 . Clearly, if m1 , m2 , then Lm1 = m1 , Lm2 = m2 and Lm2 - Lm1 = m2 - m1 . If m1 , m2 > , then the interval (s) = (1 - s)m1 + sm2 , 0 s 1 meets at a single point m3 . Notice that an open interval with endpoints m2 , m3 belongs to > . Similarly to (2.7) we have Lm2 - Lm3 m2 - m3 . Therefore, Lm2 - Lm1 Lm2 - Lm3 + Lm3 - Lm1 m2 - m
3

+ m3 - m1 = m2 - m1 .

The case m1 , m2 > can be considered analogously. The only difference is connected with the fact that the interval (s) may intersect in two points. Therefore, Rr 2 - Rr 1 r2 - r1 . The remaining part of the proof is almost the same as for Proposition 2.8. One needs only to deal carefully with the case when M is not differentiable at the fixed point r . The following corollary is an immediate consequence of Proposition 2.9.


STEADY SOLUTIONS FOR FIFO NETWORKS

415

Corollary 2.10. Suppose that ni = |Ji | 2 for al l j = 1, . . . , k . Then there exists a unique steady solution satisfying (1.1). We finish this section by the following simple proposition. It shows that the nonuniqueness example (2.5)­(2.6) is in some sense minimal. Prop osition 2.11. If n 4 then there exists a unique steady solution of the reentrant line. The assertion essentially follows from the previous corollary. One just has to consider separately three cases where one of the subsets contains 3 elements. It is easy to check that in all these cases the assertion holds. 3. Reentrant lines of Kelly type In this section we study reentrant lines of Kelly type ([5], see also Introduction), that is, we assume vj = Vi > 0 for all j Ji , i = 1, . . . , K. (3.8)

Theorem 3.1 (Main Theorem). Let (3.8) hold. Then for any steady input there exists a unique steady solution of the reentrant line. Proof. By Lemma 2.1, it suffices to prove the uniqueness of the vector x satisfying ¯ ¯ ¯ conditions (1.1) from Introduction. Let us consider the cube Q ¯ ¯ ¯ Q = {a RK : 0 ai 1, i = 1, . . . , K } ¯ ¯ ¯ and a vector a Q. The component ai , i = 1, . . . , K , will be interpreted as the ratio of the outcoming flow from node i to its incoming flow. Note that, since only steady flows are considered, this ratio is the same for any particular class j Ji , that is, xj = ai(j ) xj -1 , j = 1, . . . , n, where xj is the rate of the flow leaving class j , cf. Lemma 2.5. ¯ ¯ ¯ First, let us find the actual rate x(j, a) for a given a Q. We set x(0, a) = 1 ¯ and use the recurrent relation ¯ ¯ for each a Q x(j, a) = x(j - 1, a)ai x(j, a) =
i=1,...,K (j )

to define x(j, a), j = 1, . . . , n. Hence, x(j, a) is a monomial of the form ai
pi (j )

,

¯ ¯ ¯ j = 0, 1, . . . , n, a Q,

where integer-valued functions pi (j ) of integer argument j {0, . . . , n} are defined by the relations pi (0) = 0, pi (j ) = pi (j - 1) + 1 pi (j - 1) if j Ji , otherwise,

for i = 1, . . . , K , j = 1, . . . , n. Let us extend the domain of pi (·) to the real interval [0, n] setting pi (j + ) = pi (j + 1) + (1 - )pi (j ), [0, 1], j = 0, . . . , n - 1, i = 1, . . . , K.


416

K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV

The rate of the total outcoming flow from node i is found as Fi (a) =
j J
i

x(j, a),

¯ ¯ ¯ i = 1, . . . , K, a Q.

The with hold

It is

¯ ¯ ¯ continuous map F : Q RK , F (a) = (F1 (a), . . . , FK (a)) is nondecreasing + K respect to the cone R+ , i.e., a b implies F (a) F (b), where the inequalities component-wise. Let us denote 1 bi = . Vi easy to see that any steady solution with x0 = 1 is given by a vector (x0 , x1 , . . . , xn ) = (1, x(1, a), . . . , x(n, a)),

where a satisfies the conditions Fi (a) bi , and (bi - Fi (a))(1 - ai ) = 0, i = 1, . . . , K. (3.10) ¯ which is equivalent to the ¯ ¯ We will prove the uniqueness of such a vector a Q assertion of the theorem. Notice that all the components of any steady solution are strictly positive. It follows that there exists a constant > 0 which depends only on V1 , . . . , VK and n such that any vector a corresponding to a steady solution belongs to the cube Q = {a RK : ai 1, i = 1, . . . , K }. Let us fix an a Q and find the Jacobi matrix DF (a) = Since, for any j = 1, . . . , n, ak we have Fi (a) ak .
i,k=1,...,K

i = 1, . . . , K,

(3.9)

apm m

(j )

=

m=1,...,K

pk (a) ak

apm m
m=1,...,K

(j )

,

Fi (a) = ak

j Ji

x(j, a) = ak

j Ji

x(j, a) pk (j ). ak

(3.11)

If j Ji , then pi (t) 0 for j - 1 < t j and, hence,
j j -1

Let us consider two cases. First, let j Ji . Since pi (t) 1 and pk (t) 0 for j - 1 < t j and k = i, we get the following equality: j x(j, a) pk (t) pi (t) dt if i = k , j -1 x(j, a) pk (j ) = j x(j, a) x(j, a) pk (t) pi (t) dt + if i = k . 2 j -1 x(j, a) pk (t) pi (t) dt = 0.


STEADY SOLUTIONS FOR FIFO NETWORKS

417

Therefore, (3.11) can be written as 1 Fi (a) = ak ak
n

x(t, a) pk (t) pi (t) dt + ik (a),
0

(3.12)

¯ ¯ where x(t, a) = x( t , a) (here t is the least integer t such that t t) and (a) = {ik : 1 i, k K } is a positive definite diagonal matrix: (a) = diag((a)), (a) = (1 (a), . . . , K (a)),
i( and i (a) = 21 i j Ji x(j, a) = F2aa) > 0 for any a > 0, i = 1, . . . , K . a i Let us make the change of variables ri = ln ai , i = 1, . . . , K . This change transfers the cube Q onto the cube

Q = {r RK : ln ri 0, i = 1, . . . , K }. Let us use the notation F (r) = F (a), where ai = eri , i = 1, . . . , n, and note that Fi (r) Fi (a) = ak rk ak where 1 i, k K and r = ln a (component-wise). We get Fi (r) = rk where
n

x(t, a) pk (t) pi (t) dt + ik (a),
0

F1 (r) FK (r) , ..., . 2 2 It is important for what follows that x(j, a) is a non-increasing positive function of j for each a Q. Let us prove that for any vector r Q the Jacobi matrix DF (r) is positive definite. Notice that (r) = diag( (r)), (r) =
n

x(t, a) =
j =1

(x(j, a) - x(j + 1, a))1{

t(0,j ]}

,

(3.13)

where x(n + 1, a) 0 and 1{
t(0,j ]}

=

1, 0,

t (0, j ], t (0, j ]. /
K

Using (3.12) and (3.13) we get
K K 0 n

DF (r)x, x =
i=1 k=1 n

x(a, t) pk (t) pi (t) dt xk +
i=1

x2 Fi (r) i x2 Fi (r) i

=
0 n

x(a, t) p(t), x

d p(t), x dt + dt
j

K

i=1

=
j =1 n

(x(j, a) - x(j + 1, a))
0

p(t), x p(j ), x 2
2

d p(t), x dt + dt
K

K

x2 Fi (r) i
i=1

=
j =1

(x(j, a) - x(j + 1, a))

+
i=1

x2 Fi (r) > 0 i

(3.14)


418

K. KHANIN, D. KHMELEV, A. RYBKO, AND A. VLADIMIROV

for any x RK , x = 0. Now, it is easy to prove that F (r ) - F (r), r - r > 0 whenever r, r Q and r = r . Indeed,
1

(3.15)

F (r ) - F (r) =
0

DF ( (s)) (s) ds,

where (s) = (1 - s)r + sr and (s) = r - r. Since (3.14) holds for all r Q and Q is a convex set, we get
1

F (r ) - F (r), r - r =
0

DF ( (s))(r - r), r - r ds > 0,

as required. Finally, let us suppose that a and a , a = a , from Q generate two steady solutions of the reentrant line. Let r = ln a and r = ln a . Let us demonstrate that F (r ) - F (r), r - r 0 which is a contradiction to (3.15). It suffices to show that (Fi (r ) - Fi (r))(ri - ri ) 0 for any i = 1, . . . , n. Let us consider four cases. If Fi (r ) = bi and Fi (r) = bi then (Fi (r ) - Fi (r))(ri - ri ) = 0. If Fi (r ) < bi and Fi (r) < bi then ai = ai = 1, hence ri = ri = 0 and, again, (Fi (r ) - Fi (r))(ri - ri ) = 0. If Fi (r ) = bi and Fi (r) < bi then (Fi (r ) - Fi (r)) > 0 and ri = 0. Since ri 0, we get ri - ri 0 and (Fi (r ) - Fi (r))(ri - ri ) 0. The case Fi (r ) < bi and Fi (r) = bi is equivalent to the previous one. Remark. Theorem 3.1 can be extended to a more general case of a reentrant line with additional inflows at each node and a fixed fraction of the flow leaving the system at each node. It also can be extended to the case of a finite number of reentrant lines. In this situation one has to concatenate all the reentrant lines into a single reentrant line and assume that the total flow leaves the system at each conjunction point and a new flow comes from the outside. We thank M. Blank, V. Kleptsyn and S. Fomin for helpful discussions. References
[1] M. Bramson, Instability of FIFO queueing networks, Ann. Appl. Probab. 4 (1994), no. 2, 414­431. MR 95h:60140a [2] M. Bramson, Instability of FIFO queueing networks with quick service times, Ann. Appl. Probab. 4 (1994), no. 3, 693­718. MR 95m:60135 [3] M. Bramson, Convergence to equilibria for fluid models of FIFO queueing networks, Queueing Systems Theory Appl. 22 (1996), no. 1-2, 5­45. MR 97e:60146 [4] J. G. Dai, On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models, Ann. Appl. Probab. 5 (1995), no. 1, 49­77. MR 96c:60113 [5] F. P. Kelly, Reversibility and stochastic networks, John Wiley & Sons Ltd., Chichester, 1979. MR 81j:60105 [6] P. R. Kumar, S. H. Lu, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Automat. Control 36 (1991), 289­298.


STEADY SOLUTIONS FOR FIFO NETWORKS

419

[7] V. A. Malyshev, Networks and dynamical systems, Adv. in Appl. Probab. 25 (1993), no. 1, 140­175. MR 94f:60090 [8] A. A. Pukhalski, A. N. Rybko, Nonergodicity of queueing networks when their fluid models are unstable, Problemy Peredachi Informatsii 36 (2000), no. 1, 26­46. (Russian) MR 2001c:90017. English translation: Probl. Inf. Transm. 36 (2000), no. 1, 23­41. [9] A. N. Rybko, A. L. Stolyar, On the ergodicity of random processes that describe the functioning of open queueing networks, Problemy Peredachi Informatsii 28 (1992), no. 3, 3­26. (Russian) MR 94d:60147. English translation: Problems Inform. Transmission 28 (1992), no. 3, 199­220 (1993). [10] A. L. Stolyar, On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes, Markov Process. Related Fields 1 (1995), no. 4, 491­512. MR 98k:60172 K.Kh.: Dept. of Mathematics, Heriot-Watt University, Edinburgh EH14 4AS, UK, Isaac Newton Institute for Mathematical Sciences, 20 Clarkson Road, Cambridge CB3 0EH, UK, BRIMS, Hewlett-Packard Laboratories, Stoke Gifford, Bristol BS12 6QZ, UK, and Landau Institute for Theoretical Physics, Kosygina st. 2, Moscow 117332, Russia E-mail address : K.Khanin@newton.cam.ac.uk D.K.: Moscow State University, Mechanical and Mathematical Department; Heriot-Watt University, Edinburgh; Isaac Newton Institute for Mathematical Sciences, Cambridge. A.R., A.V.: Institute for Information Transmission Problems, RAS