2. A RECURSIVE RELATIONSHIP FOR THE TIME-TO-EMPTY IN TANDEM CLOSED NETWORKS

Consider the same tandem network as earlier which we now assume operating as a closed Jackson network with N customers. In fact, we will consider a whole family of closed network processes, each described by a continuous-time Markov chain,

with state space

defined on a probability space

, where X^N(t) = (X₁^N(t),…,X_M^N(t)) denotes the number of customers in each station at time t. We assume that the Markov chain X^N is stationary under P and we denote by {D_n^N} the point process of departures from node M. We use the standard numbering convention that D₀^N ≤ 0 < D₁^N P-a.s. (i.e., call D₁^N the first point strictly to the right of the time origin) and denote by

, the interdeparture times. We will also denote by P_N⁰ the Palm transformation of the probability measure P under the point process {D_n^N} and by E_N⁰ the expectation with respect to P_N⁰.

If we were to assume that at time 0 “the loop is broken” between station M and station 1 so that customers who finish service at station M simply leave the system without returning, then, because at time 0 the system is a closed network in equilibrium, the time for the system to empty is precisely D_N^N, the time until the Nth departure in a closed network with N customers in equilibrium. This, of course, is true since all stations have single servers so that it is not possible for one customer to overtake another. Thus,

We are now ready to establish the following theorem.

Theorem 1: The time-to-empty starting from equilibrium for a closed tandem Jackson network with N customers is given by the expression

where λ_k is the throughput in such a network with k customers and R₁(s) is the time to emptiness from equilibrium in the network with a single customer given by

where

Proof: We will use the approach in [10] (see also [12]) as follows. Let X^N+1 be the same closed Jackson network with N + 1 customers and suppose that it is stationary under P. If we denote by {D_n^N+1} the departure process for this system and if P_N+1⁰ denotes the Palm probability transformation of P under {D_n^N+1}, then, as a consequence of the arrival theorem (see [3,6,7,8,9]), we have

However, by the shift invariance properties of P_N+1⁰ and since P_N+1⁰(D₀^N+1 = 0) = 1, we also have

Using the above equations in conjunction with the arrival theorem, we conclude that

(In the above argument, note that R_N(s) is originally expressed as a stationary expectation, then the arrival theorem is used to express it as a Palm expectation in a network with one additional customer, then a shift is performed along the points of the departure process, and, finally, the arrival theorem is used once more to return to a stationary expectation in the original network with N customers.) Using the Palm inversion formula (see [1]), we obtain the relationship

where in the last equation we have again used the shift invariance of P_N⁰. From (8) and (9), adding term by term, we obtain

where in the above equation we have taken into account that P_N⁰–a.s. D₀^N = 0 and D_N−1^N = d₀^N + d₁^N + ··· + d_N−2^N. However, we have

(where we have used the arrival theorem again!) and, hence, (10) can be written as

Applying the above recursively we readily obtain (5). It remains to establish (6), which, however, follows immediately by applying the Palm inversion formula once more. (This should be intuitively obvious: R₁(s) = E [e^−sD₁1] is simply the forward recurrence time of the departure process {D_n¹} in the closed network with a single customer in equilibrium.) Finally, (7) clearly holds since D₁¹ under P₁⁰ is the typical cycle time in a closed tandem network with a single customer. █

From Theorem 1, it is clear that the explicit computation of R_N(s) is not difficult. In the next section, we carry out this computation and we return to the problem of the open network.

3. CLOSED-FORM EXPRESSIONS FOR THE TIME-TO-EMPTY IN CLOSED AND OPEN JACKSON NETWORKS

Here, we will assume for simplicity that the service rates in different nodes of the network are different (μ_m ≠ μ_l when μ ≠ l). Under this assumption, it has been shown in [10] that

where

The constants α_m arise from the partial fractions expansion

If we set

, then it is easy to see that these constants are connected to the constants (3) via the relationship

From (5)–(7), (12), and (14), after some elementary manipulations, we obtain the following closed-form expression for the time-to-empty for a closed tandem Jackson network initially in equilibrium with N customers:

It is interesting to compare the above formula with the expression for the Laplace transform of the cycle time of a customer in this network with N customers, which we will denote by Φ_N(s), as given in [10]:

We are now in a position to compute the Laplace transform of the time-to-empty for the open tandem Jackson network in steady state. From (1), (4), (15), and (16), we obtain

Again, the comparison with the corresponding flow time (viz. the time it takes from the moment a customer arrives to the first station until the time it leaves the last station in steady state) is interesting. If this flow time is denoted by Φ(s), then it is well known (e.g., see [7,9]) that

the second expression equality following by a partial fractions expansion of the first.

Finally, we compute the Laplace transform of the time-to-empty for the same system assuming that at time 0 it is in steady state and conditioning on the event that there are N or more customers in the system. Elementary manipulations similar to the ones described earlier give

where the constants c_m are given in (3). Note the similarity of the above expression with the corresponding result for the M/M/1 queue. Suppose that an M/M/1 system with arrival rate λ and service rate μ > λ is in equilibrium at time t = 0 and that at that time, the arrival process is switched off. Then, the Laplace transform of the time required for the system to empty can be easily computed via a conditioning argument and is equal to

where ρ = λ/μ. It is worth noting that the corresponding result for the tandem network given in (20) is simply a weighted average of the corresponding M/M/1 factors for each station.

From (20), we can readily obtain the mean time for the network to empty given that there are at least N customers in the system:

4. APPLICATION: A TWO-CLASS TANDEM NETWORK WITH PROBE CUSTOMERS

Consider now an open, tandem Jackson network with two classes of customers. Customers belonging to the first class arrive to the system according to a Poisson process with rate λ and their service rates at the M stations are μ₁,μ₂,…,μ_M, as earlier. Customers belonging to the second class arrive according to an independent Poisson process with rate ν and the service discipline is FIFO for all customers and stations. We will assume that the service times of class 2 customers at the various stations are so small compared with the timescale of the system that we can entirely ignore them. Thus, these customers, which we will call probe customers, flow through the system without delay except for the fact that they have to wait in front of class 1 customers. There are many cases in both communications systems and in manufacturing where such a model is applicable. Then, one can easily see that the flow time of the typical probe customer is precisely the time-to-empty for the Jackson network in equilibrium with only one class of customers. Thus, (18) gives the flow time for probe customers also. Let us now denote by Π(z) the probability generating function (p.g.f.) of the stationary number of probe customers in the system. Then, we can use the distributional law of Little (see [4,5]) to obtain

Thus, the stationary distribution of probe customers is expressed as a combination of geometric factors.

One might be tempted to derive Π(z) directly by noting that the number of probe customers who arrive between two consecutive class 1 customers is geometrically distributed with p.g.f. given by λ/(λ + ν − νz) and then composing this p.g.f. with the p.g.f. of the total number of class 1 customers in the system, as given in (2). Such reasoning, however, will not lead to the correct result since the number of class 1 customers in the system at any given time and the interarrival intervals corresponding to these customers are, of course, not independent.

Clearly, as long as the process of class 1 customers is in steady state, the flow time of probe customers will be given by (18), regardless of the statistics of their arrival process, provided, of course, that this arrival process is independent of the arrivals and service requirements of class 1 customers. What could become more complicated is the determination of the statistics of the total number of probe customers in the network. However, when probe customers arrive according to a renewal process with interarrival distribution G, independent of the arrivals and service times of class 1 customers, then, as we will see, the stationary number of probe customers in the system can be easily determined. This is done using the distributional version of Little's law for renewal arrivals in the form given in [11] (see also [2]).

In the framework adopted there, one starts with a marked point process

, which is assumed to be stationary under the probability measure P. The marks W_n are assumed to be nonnegative w.p. 1. Corresponding to this marked point process, one defines the arrival counting measure

, where B is any Borel set in

, and the system size process

. T_n is to be interpreted as the arrival epoch of the nth customer, W_n as his sojourn time through the system, and Y(t) as the total number of customers in the system at time t. In our situation, {T_n} is the renewal arrival process of probe customers, {W_n} is their corresponding sojourn times through the network, and Y(t) is the total number of probe customers in the network at time t. We will also denote by P* the Palm transformation of P with respect to the point process {T_n}. Let Π(z) := Ez^Y(0) denote the p.g.f. of the stationary number of probe customers in the system. In [11], it is shown that

where

is the mean interarrival time, assumed finite, provided that the following two conditions hold:

In our situation it is clear that both conditions are satisfied. Also,

, and if we denote by

the Laplace transform of G, a straightforward computation gives

where we have used the notation

to denote the Laplace transform of the integrated tail distribution that corresponds to G. In view of (18) and (3), we have

Thus, from (22)–(24), we conclude that

The above displays the total number of probe customers in the system as a combination of geometric factors.