1. INTRODUCTION
We consider a Jackson network with two nodes (Fig.
1), numbered i = 1,2. Processing times at the nodes are
independent, and those at node i are exponentially distributed
with rates μi, and jobs completing processing at
node i move to node 3 − i with probability
pi and leave the system otherwise. There is
no exogenous input to the system. However, whenever one of the nodes is
empty, it will process a job from an infinite supply of jobs. This system
can be described by a two-dimensional Markov jump process,
X(t) =
(X1(t),X2(t)),
the state space of which consists of the pairs of nonnegative integers
(n1,n2), where
n1 indicates the number of jobs at node 1 and
n2 indicates the number of jobs at node 2. Whenever
ni > 0, node i will process one
of the jobs at the node. This introduces the transitions
Whenever node i is empty, it will process a job from its
infinite supply, at the same rate μi, and upon
completion, this job will move to the other node with probability
pi and leave the system with probability 1
− pi. This introduces the additional
transitions:
Note that jobs from the infinite supply of each buffer are
indistinguishable from jobs queued at the nodes, but queued jobs have
preemptive priority over jobs in the infinite supply. The transitions
(1.2) constitute arrivals into the system.
A two-node Jackson network with infinite supply of work.
The two nodes in this system are processing jobs all the time. Hence,
there are four independent Poisson streams in this system: Jobs depart the
system in two Poisson streams with rates μ1(1 −
p1) and μ2(1 −
p2), and jobs arrive at the two nodes in two Poisson
streams, with rates μ1 p1 and
μ2 p2. The queue at node i
therefore behaves as an M/M/1 queue, with
arrival rate μ3−i
p3−i and service rate
μi. The system is stable if
with marginal steady state distributions
However, the queue lengths at the two nodes in steady state are not
independent; the joint steady state distribution is not a product
form:
In this note, we derive explicit expressions for the joint steady
state distribution of the two-node system. We use the compensation
approach, developed by Adan, Wessels, and Zijm [2] to obtain an expression that is an infinite
sum of product forms.
This two-node Jackson network with an infinite supply of work
describes quite a useful model of cooperative service by two servers.
Consider jobs that require a sequence of tasks; the first task is
performed by one of the servers and the remaining tasks are performed by
alternating servers. Server i performs tasks at rate
μi, and the job then requires an additional task
with probability pi, or else it is complete
and leaves the system. We assume that each of these servers has an
infinite supply of jobs to start. However, each server gives preemptive
priority to tasks that it received from the other server. Each server then
has a queue of jobs that are “in process” and the analysis of
these queues tells us how much storage for WIP (work in process) is needed
and what is the cycle time of a job from first task to completion.
The concept of infinite supply of work, in contrast to the usual
queuing assumption that jobs arrive randomly, is in fact very common in
many systems: Whenever a server is expensive and it is desired not to keep
it idle, one tries to monitor the server and control the inputs, so that
the server never runs out of work. This is the case for an expensive
machine, a highly trained server, or a high-performance communication
link. In each case, work is shunted to such servers to prevent them from
idling.
As we will see in Section 3, infinite-supply Jackson nodes provide
much better performance than standard Jackson nodes.
Multiclass queuing networks with infinite supplies of jobs in some of
the classes, also called infinite virtual queues, were introduced by Adan
and Weiss [1], Kopzon and Weiss
[8,9], and
Weiss [12,13,14]; see also Levy
and Yechiali [10]. They represent
monitored control over job arrivals, as it often exists in manufacturing
and communication systems. Jackson networks are described by Jackson
[6] and Kelly [7]. Weiss [14] has discussed Jackson networks with virtual
infinite buffers: He has derived flow rates, stability conditions, and
partial steady state distributions. This work is also closely related to
the results of Goodman and Massey [5].
The analysis in the current article provides one example of such networks,
which is highly tractable.
2. MAIN THEOREM
The two-node Jackson network with an infinite supply of work is
described by a Markov jump process moving on the two-dimensional
nonnegative integer grid. The Markov process performs a two-dimensional
simple random walk on the positive-integer grid, with transitions only to
neighboring states, and with reflecting barriers on the horizontal and
vertical axes. Furthermore, in the interior of the positive quadrant, the
random walk has no transitions to the north, the northeast, and the east
directions. The transition rates for this random walk are described in
Figure 2.
Transition rates for the two-node system.
For such Markov jump processes, it is possible to obtain a closed-form
expression of the steady state distribution, by the compensation method
developed in the work of Adan et al. [2]. The random walk in Figure
2 has the property that the transition rates at the vertical
boundary n1 = 0,n2 > 0 and the
horizontal boundary n1 > 0,n2 =
0 are projections of the ones in the interior
n1,n2 > 0. Boxma and van Houtum
[3] showed that this property
considerably simplifies the expression of the steady state distribution.
See also [11].
The main steps in the derivation of the steady state probabilities are
as follows: The balance equations for the interior are satisfied by
product form expressions
αn1βn2,
where α and β are solutions of a quadratic equation
Q(α,β) = 0. Solutions of this form do not as a rule
satisfy the equations for the horizontal or vertical boundaries. However,
it is possible to find compensating product forms such that the linear
combination
satisfies the balance equations for the interior and the vertical
boundary of the quadrant. Similarly, it is possible to find compensating
product forms such that
satisfies the balance equations for the interior and the horizontal
boundary of the quadrant. Then, starting with a product form
αn1βn2
with α and β satisfying Q(α,β) = 0, one can
construct an infinite linear combination by adding product forms to
alternately compensate for the horizontal and vertical boundary. The
resulting solution formally satisfies all of the balance equations. One
then needs to choose the parameters of the product forms and their
coefficients such that the solution is absolutely convergent. This method
does indeed work for our system.
In Section 4, we will present the detailed derivation of the steady
state distribution, without invoking the results in [2,3]. In the
derivation, we make use of the steady state marginal distributions (1.3).
This yields a particularly elegant and simple expression:
Theorem 2.1: The steady state distribution of the
two-node Jackson network with infinite supply of work, when
ρ1,ρ2 < 1, is given, for all
(n1,n2) ≠ (0,0),
by
where, for k ≥ 1,
with initially α0 = β0 =
1,α1 = ρ1, and β1 =
ρ2. The steady state probability P(0,0)
is
The closed-form expression in Theorem 2.1 immediately leads to similar
expressions for the distribution of the total number in the system and for
the (factorial) moments of the queue lengths at node 1 and 2. Let
Xi denote the queue length of node i
in steady state. Then we have the following:
Corollary 2.2:
(ii) For all m,n ≥ 0 and m + n
> 0,
Note that exact formulas for αk and
βk can be obtained from the difference equation
(2.2) but are not particularly illuminating. The asymptotic behavior of
αk and βk is derived in
Proposition 4.14.
3. COMPARISON WITH STANDARD JACKSON
NETWORK
We compare our two-node system with an infinite supply of work and a
standard Jackson network, with exogenous random inputs. Throughout this
section we label our system as “∞-supply” and the
Jackson network with random exogenous input as “standard.” For
the comparison, we consider two nodes in a standard Jackson network as
shown in Figure 3. Here, we have two nodes with
the same processing rates μi, and with the same
probabilities 1 − pi to complete a job,
which then departs the system. The total inputs into the nodes are at
rates λi, and they consist of both exogenous
arrivals and feedback from other nodes. Recall that the input streams
are not Poisson. The outflow in steady state is also at rate
λi and includes a Poisson output stream of
departures from the system at rate λi(1
− pi). As is well known, the steady
state joint distribution of the jobs in the two nodes is the product
form
This is only stable if λi <
μi; therefore, the output rate of the standard
nodes is always less than the rate (1 −
pi)μi achieved by the
∞-supply system, and if one tries to approach this rate, the queue
length explodes.
Standard Jackson network nodes.
It is interesting to compare the two systems in the case that both
have the same traffic intensities. For the remainder of this section, we
take ρi = λi
/μi = μ3−i
p3−i /μi.
We compare the total number in the two nodes for the two systems. The
marginal steady state distributions in the nodes of the two systems are
the same, namely Geometric, with
P(Xi ≥ n) =
ρin. In particular, it follows
that the mean number in the system is the same for both networks. However,
the steady state distribution of the total number in the system is
different.
In Figure 4, we show the distribution of the
total number in the system for μ1 = 2, μ2 =
3, p1 = 0.8, p2 = 0.5 (top) and
μ1 = μ2 = 1, p1 =
p2 = 0.8 (bottom). We also plot the standard product
form probabilities for comparison.
Probabilities of total number in the system.
The correlation between X1 and
X2, calculated from formula (2.5), equals
−0.2976 for the first example of an asymmetric system and
−0.3873 for the second example of a symmetric system. In fact, it
can be shown that the correlation is always negative; see Section 4.8.
Negative correlation reduces the variance of the total number in the
system compared to independent nodes. In Figure
5, we show the correlation between X1 and
X2 for the symmetric system μ1 =
μ2 and p1 = p2 =
p. Clearly, the negative correlation gets stronger as p
tends to 1; the limiting value for p = 1 is equal to
2/3π2 − 7 (see Section 4.8).
Correlation between X1 and X2
for the symmetric system μ1 = μ2 and
p1 = p2 =
p.
We can also get the asymptotic tail probabilities of
X1 + X2, from (2.4). We will show
that the sum is absolutely convergent and that the parameters
αk and βk monotonously
decrease. The values for large n therefore behave like the
largest geometric term,
The corresponding asymptotics for the product form standard Jackson
network are
Hence, the asymptotic ratio of the two is
In Table 1, we summarize various quantities
for the two examples and the comparison of the total number in the system
for the ∞-supply and standard systems.
Comparison of Infinite-Supply and Standard Jackson
Networks
The most interesting part here is the strong form of variance
reduction and tail probability (i.e., overflow probabilities in practice)
obtained in the infinite-supply network, when the two nodes are
symmetric.
4. DERIVATION OF STEADY STATE
DISTRIBUTION
In this section, we prove Theorem 2.1. We first derive the expression
as a formal solution to the balance equations and then prove that this
solution is absolutely convergent.
4.1. Balance Equations
The balance equations for the steady state probabilities in this
system are obtained by equating the flow out and into each state, yielding
the following:
In the next section, we will characterize the product forms
αn1βn2
satisfying the balance equations in the interior of the quadrant.
4.2. Product Form Trial Solutions in the Interior of
the Quadrant
Consider first (4.1) in the interior of the quadrant and a product
form trial solution
αn1βn2.
Substituting this trial solution in (4.1) and canceling
αn1−1βn2−1,
we see immediately the following:
Proposition 4.1: The product form
αn1βn2
solves (4.1) for every n1,n2 =
0,±1,±2,…, if and only if α and
β are on the curve:
Curve (4.5) is shown in Figure 6. The pairs
of values (α,β) = (0,0) and (α,β) = (1,1) are on this
curve. We also illustrate on the curve how the special roots that appear
in the solution (2.1,2.2),
αk,βk, are calculated, for
k = 0,1,2,3.
Curve (4.5) for μ1 = 2,μ2 = 3 and
p1 = 0.8,p2 = 0.5.
For every fixed value of 0 < α ≤ 1, (4.5) yields a quadratic
equation for β:
Proposition 4.2: The quadratic equation (4.6) has two
real roots for all 0 < α ≤ 1. For α = 1,
the roots are β = 1 and β =
ρ2. For 0 < α < 1, the larger root
is β > α and the smaller root is 0
< β < α.
Proof: For the fixed value α = α0 = 1, the
quadratic equation (4.6) for β is
with the two roots β = 1 and β =
β1 = μ1 p1
/μ2 = ρ2. For 0 < α < 1, if we
substitute β = α in the right-hand side of the quadratic equation
(4.6), we get
Hence, the quadratic equation (4.6) has two roots, one of them larger
and the other smaller than α. The product of the two roots is
μ1 p1 /μ2; hence,
both are positive. █
Similarly, for every fixed value 0 < β ≤ 1, (4.5) yields a
quadratic equation for α:
Proposition 4.3: The quadratic equation (4.7) has two
real roots for all 0 < β ≤ 1. For β = 1,
the roots are α = 1 and α =
ρ1. For 0 < β < 1, the larger root
is α > β and the smaller root is 0
< α < β.
It is convenient to divide the quadratic equations (4.6) and (4.7) by
α2β2 and to consider quadratic equations for
α−1, β−1:
4.3. Compensating for the Vertical and Horizontal
Boundaries
Let α and β satisfy (4.5), so that
αn1βn2
solves the balance equations (4.1) for all
n1,n2 =
0,±1,±2,…. We want to find a compensating term such
that
will, in addition, solve the horizontal boundary equations (4.2).
We first subtract (4.2) from (4.1) to obtain
Since our trial solution
solves (4.1), it will solve (4.2) if and only if it solves (4.10). We
substitute the trial solution in (4.10), yielding
To satisfy (4.11) for all n1 > 0, we are forced
to take
;
thus, to solve (4.1), we need to take
as the second root of the quadratic equation (4.6). Using the quadratic
equation (4.8), we get the second root
in terms of α and the first root β−1:
We also get the product of the roots of (4.8):
By canceling αn1+1 in (4.11), we
obtain an equation for c:
We now use (4.12) to cancel
on both sides and obtain
Multiplying the linear combination by the constant (1 − α)(1
− β), we may conclude that
solves the balance equations (4.1) and (4.2). The procedure to compensate
for the vertical boundary equations is symmetric.
Proposition 4.4: Let α and β
satisfy (4.5). Then
solves the balance equations (4.1) and (4.2) in the interior and the
horizontal boundary if we take
Similarly,
solves the balance equations (4.1) and (4.3) in the interior and the
vertical boundary if we take
4.4. Infinite Sequences of Compensations
Motivated by the marginal distribution (1.3), we start from a product
form solution with α1 = ρ1. The roots of
(4.6) are β0 = 1 and β2 <
ρ1. Since we need convergence, we start from the trial
solution α1n1
β2n2. To conform with our
desired final form, we multiply this trial solution by a constant.
Proposition 4.5: The trial solution (1 −
α1)α1n1(1
−
β2)β2n2
with α1 = ρ1 and
β2−1 = [(μ1 +
μ2)/μ1
p1]ρ1−1 − 1
− [(1 −
p1)/p1] solves (4.1)
and (4.2) for all n1 > 0 and n2
≥ 0.
Proof: In this case, the compensating term would have
,
but then 1 −
,
so the compensating term disappears. █
We next add a compensating term to solve (4.1) and (4.3). According to
(4.15), we choose
to obtain a two-term trial solution
In this solution, the first term alone solves (4.1) and (4.2), and the
two terms together solve (4.1) and (4.3).
From now on, we continue to add compensating terms to satisfy (4.2)
and to satisfy (4.3) alternately. In the next step, we need to compensate
the second term of (4.16) to solve (4.2) again, and we choose
β4 according to (4.14). We continue these compensating
steps indefinitely.
Proposition 4.6: For all k ≥ 1, let
with initially β0 = 1 and
α1 = ρ1. Then trial solution
solves the balance equations for all
(n1,n2) ≠
(0,1),(1,0),(0,0).
Proof: We show in Section 4.7 that the infinite sum (4.18) is
absolutely convergent for every
(n1,n2) ≠ (0,0). We will also
show that the summation of (4.18) over all the values of
(n1,n2) ≠ (0,0) converges
absolutely. In the rest of the proof, we take this statement as
proved.
The pair (α1,β0) is on the curve (4.5).
Hence, using (4.14) and (4.15) and induction, so are all the pairs
(α2k−1,β2k) and
(α2k+1,β2k). Hence, all
the terms in (4.18) solve (4.1), and by absolute convergence, so does the
infinite sum for n1 > 0 and n2
> 0.
In the sum (4.18), each negative term compensates the preceding
positive term so that their sum solves (4.3); see Proposition 4.4. Hence,
for all K,
solves (4.3). By absolute convergence, (4.18) solves (4.3), whenever
the equations do not involve
(n1,n2) = (0,0). Hence, (4.18)
solves (4.3) for all (0,n2),n2
> 1.
We saw that (1 −
α1)α1n1(1
−
β2)β2n2
solves (4.2). Each positive term (1 −
α2k+1)α2k+1n1(1
−
β2k+2)β2k+2n2
compensates the preceding negative term −(1 −
α2k+1)α2k+1n1(1
−
β2k)β2kn2
in the sum, so that their sum solves (4.2). Hence, for all K,
solves (4.2). By absolute convergence, (4.18) solves (4.2), whenever
the equations do not involve
(n1,n2) = (0,0). Hence, (4.18)
solves (4.2) for all (n1,0),n1
> 1. █
Analogously, we can start from the (1,ρ2) on the curve
(4.5) and get another solution:
Proposition 4.7: For all k ≥ 1, let
with initially α0 = 1 and
β1 = ρ2. Then trial solution
solves the balance equations for all
(n1,n2) ≠
(0,1),(1,0),(0,0).
4.5. The Complete Solution
The two solutions in Propositions 4.6 and 4.7 were not defined for
(n1,n2) = (0,0). The reason is
that, for n1 = n2 = 0, the sums
are not (absolutely) convergent, and so they are meaningless. As a result,
we could not check for (n1,n2) =
(1,0) or (n1,n2) = (0,1).
To obtain a solution for all
(n1,n2), we do the following: For
all (n1,n2) ≠ (0,0), we take
the sum of the two solutions (4.18) and (4.20). This yields
For (n1,n2) = (0,0), we
take
Proposition 4.8: The expressions for
P(n1,n2) in (4.21) and
(4.22) solve all of the balance equations.
Proof: We will show in Section 4.7 that the sum in
P(0,0) is also absolutely convergent. We shall take that as well
as absolute convergence of all the other
P(n1,n2) and their sum
over all n1 and n2 as proved.
We already know by the previous two propositions that
P(n1,n2) defined by
(4.21) satisfy the balance equations (4.1), (4.2), and (4.3) for
n1 + n2 > 1. It remains to
consider the balance equations for (1,0),(0,1), and (0,0). For all
K, we have seen in the proof of Proposition 4.6 that the sum
solves (4.2). Also, for all K, we have seen in the proof of
Proposition 4.7 that the sum
solves (4.2). Hence, the sum of (4.23) and (4.24) also solves (4.2).
Consider, in particular, the balance equation for
(n1,n2) = (1,0):
It is satisfied by the sum of (4.23) and (4.24). We now look at the
sum of (4.23) and (4.24) for n1 =
n2 = 0:
As we will see, αk,βk
→ 0 as k → ∞. This property and absolute
convergence of the sum
shows that (4.25) is satisfied by P(1,0), P(0,1),
P(1,1), and P(2,0) as defined in (4.21) and
P(0,0) as defined by (4.22). The proof for the balance equation
of (0,1) is symmetric.
Finally, by the absolute convergence of the sum over all
n1 and n2 of (4.21), we get that
(4.4) is redundant and is satisfied automatically by the expressions for
P(n1,n2) in (4.21) and
(4.22). █
4.6. Normalizing the Sum of Probabilities
We again take absolute convergence as proved. Based on that, we can
calculate various quantities. We first obtain marginal probabilities,
which are consistent with (1.3).
Proposition 4.9: For ni >
0,
Proof: We make heavy use of the absolute convergence to
change the order of summations and group sums of positive and negative
terms. For n1 > 0, the sum is
The case of i = 2 is symmetric. █
We next calculate P(n1 =
0,n2 > 0) and P(n1
> 0,n2 = 0).
Proposition 4.10:
Proof: We again make heavy use of the absolute
convergence:
The other case is symmetric. █
Finally, we have the following proposition.
Proposition 4.11: The probabilities
P(n1,n2) in (4.21) and
(4.22) sum up to 1.
Proof: By the previous two propositions and (4.22),
4.7. Absolute Convergence
In the previous sections, we made heavy use of the absolute
convergence of the sums in (4.21) and (4.22). This will be proved
next.
Proposition 4.12:
Proof:
In the next proposition, we show that the sequences
αk and βk decrease
geometrically, and, hence, the last sum converges. █
Proposition 4.13: For all k ≥ 0,
Proof: For k = 0, we have α0 =
β0 = 1,α1 = ρ1, and
β1 = ρ2 and this is the only case of
equality. For k ≥ 1, by (4.15),
where the first inequality follows from
βk−1 >
αk−1−1 and the second from
βk−1 > 1. The proof for
βk+1 is symmetric. █
We can also get the asymptotic rate of decay of
αk and βk:
Proposition 4.14: As k → ∞,
Proof: The parameters αk+1 and
αk−1 are the roots of (4.5) with β =
βk. Dividing (4.5) by
βk2, we get that
αk+1 /βk and
αk−1 /βk are the
roots of
with β = βk. As k → ∞,
then βk → 0 by Proposition 4.13 and,
thus,
where 0 < γ1 < 1 < γ2 are the
roots of (4.26) with β = 0. Hence,
The proof for βk+1
/βk is similar. █
From the geometric decay of the sequences αk
and βk, we can further conclude the following:
Corollary 4.15:
(i) The sum that defines P(0,0) in (4.22) is
absolutely convergent.
(ii) For all m,n ≥ 0,m + n >
0, the sum defining
in (2.5) is absolutely convergent.
4.8. Nonnegativity and Ergodicity
From Propositions 4.8, 4.11, and 4.12 it follows that
P(n1,n2) given by (4.21)
and (4.22) are a nonnull, absolutely convergent solution of the balance
equations, which sums up to 1. From Theorem 1 in Foster [4], we can immediately conclude the
following:
Corollary 4.16: The Markov jump process
X(t) =
(X1(t),X2(t))
is ergodic when ρ1,ρ2 < 1,
and its equilibrium probabilities are given by the solution
P(n1,n2) defined by
(4.21) and (4.22).
4.9. Queue Length Correlation
In this subsection, we show that the correlation between
X1 and X2 is always negative,
which is equivalent to
The terms in the infinite sum (4.27) are alternating and decreasing in
magnitude, since α1 > β2 >
α3 > ··· and β1 >
α2 > β3 > ···.
Hence, it suffices to show that
which can be verified by straightforward calculations. This proves the
following proposition:
Proposition 4.17: If
ρ1,ρ2 < 1, then
Corr(X1,X2) <
0.
Figure 5 displays the correlation for the
symmetric system μ1 = μ2 = μ and
p1 = p2 = p. To find the
limiting value of the correlation as p ↑ 1, note that in the
symmetric case,
which can be derived from the recursive relations for the sequences
αk and βk. Hence, from
(4.27) and using that
we obtain
Note that exactly the same asymptotic correlation value appears in the
calculations of Boxma and van Houtum [3,
p.488], which is curious, since the two models are quite
different.
