Product-Form Queueing Networks with Batches

Abstract

A Markovian queue, with both batch arrivals and batch departures, is first shown to have a geometric queue length probability distribution at equilibrium under certain conditions. From this a product-form solution follows directly for networks of such queues at equilibrium, by application of the reversed compound agent theorem (RCAT). The method is illustrated using small batches of sizes 1 and 2, as well as geometric sizes.

1 Introduction

Queueing networks with batch movements, including so-called bulk arrivals, are appropriate for modelling burstiness that has been observed in internet traffic for some years, which has a degrading effect on network performance. Such systems may also be used to provide quantitative analysis of algorithms and schedules that reduce energy consumption, where large numbers of devices of various sorts are switched off when not in use and switched on again when they are next required. This switching inherently increases burstiness, not only in power consumption but also in the performance delivered – typically measured by device utilisation, throughput and response time.

In the next section, we define the batch-queues for which we obtain conditions for a geometric queue length probability distribution at equilibrium. These have regular batch arrivals and batch departures, as well as a special batch arrival stream that is activated only when the queue is empty, and a special batch departure stream that clears the queue. The special streams could represent the switching off of a device and the backlog of work when it is restarted in a power-control system. The geometric distribution, when it exists, allows a product-form to be derived for networks of such queues, called batch-networks; this is simply proved using the reversed compound agent theorem (RCAT) of [8] in Sect. 3. The method is illustrated using small batches of sizes 1 and 2, as well as geometric sizes. The basic results of Sect. 2 were summarised as preliminaries to the work on asymptotics in [7], but important new properties are also obtained here. The paper concludes in Sect. 4, with applications and future potential of the method.

2 Geometric Batch-Queues

As noted in the introduction, batches occur in networks of queues in both the departure and arrival processes of the constituent nodes. Typically, but not necessarily, a batch of a given size departing from one node arrives as a batch of the same size at another node. However, a departing batch may be re-batched, e.g. divided into sub-batches, before being forwarded to another node, or perhaps to several other nodes probabilistically. To obtain a product-form in such a Markovian queueing network, we appeal to RCAT [8]. The primary requirement of this theorem is that the reversed rates of all the instances of each active, synchronising action (the output actions in one node that are awaited by another node) must be the same. In particular, every departure transition for a batch of a given size k at a given node must have the same reversed rate, which can be calculated directly from the node’s equilibrium probabilities by a standard result; see, for example, [8, 13]. If the forward rate $\mu _k$ is independent of the local state of the node it is departing from, the reversed rate of a batch-transition from state $i+k$ to state i is $\pi _{i+k} \mu _k / \pi _{i}$ for all $i \ge 0$, where ${\varvec{\pi }}$ is the equilibrium probability vector. The reversed rate is therefore the same for all destination states i whenever the equilibrium state probability $\pi _i = (1-\omega )\omega ^i$ for some $\omega$. We therefore seek conditions on the batch size probability distributions and the corresponding instantaneous transition rates that render the equilibrium state probabilities geometric. Product-forms in networks of such queues are then easy to identify and write down, using RCAT. It is well known that no such product-form exists for queues with only the arrival and departure batches described above – unless these are unit-sized with probability one. We therefore introduce additional, “special” batches that can arrive only when the queue is empty and can only depart so as to leave the queue empty. This idea itself is not new and product-forms have been obtained for special cases in [4, 9].

Fig. 1.

Batch queue and its reversed process

Our model of batch movements in a single server queue is illustrated in Fig. 1 and defined as follows, where we assume that the rates are bounded so that the infinite sums exist:

• The state space $\mathcal{S}$ of the queue is the set of non-negative integers;

• Normal batch arrivals of size $k \ge 1$ are represented by transitions with constant instantaneous rate $a_k : i \rightarrow i+k \;\;(i \ge 0)$, i.e. from states i to $i+k$;

• Additional special batch arrivals of size $k \ge 1$ to an empty queue are represented by transitions with constant instantaneous rate $a_{0k} : 0 \rightarrow k$;

• Normal batch departures of size k are represented by transitions with constant instantaneous rate $d_k : i+k \rightarrow i \;\;(i \ge 0)$;

• Special batch departures of size k, leading to an empty queue, are represented by transitions with constant instantaneous rate $d_{k0} : k \rightarrow 0$;

• The ordering of individual tasks in the queue is strictly first come first served (FCFS).

We call this a batch-queue. Rate generating functions are defined for each batch movement as follows:

$$\begin{aligned} A(z) = \sum _{k=1}^\infty a_k z^k; \quad A_0(z) = \sum _{k=1}^\infty a_{0k} z^k; \quad D(z) = \sum _{k=1}^\infty d_k z^k; \quad D_0(z) = \sum _{k=1}^\infty d_{k0} z^k. \end{aligned}$$

We assume that $A(1),A_0(1)<\infty$, to avoid null mean state holding times (i.e. infinite total instantaneous transition rate out of a state), and $D(1)<\infty$ similarly, to avoid unbounded total transition rates. The functions $A(z),A_0(z),D(z)$ are therefore absolutely convergent and analytic inside the unit disk, which lies inside their circles of convergence. The following proposition gives conditions for the length of the batch-queue to have a geometric equilibrium probability distribution, so that product-forms become facilitated in networks by application of RCAT.

Proposition 1

The batch-queue defined above, with $A(1),D(1)<\infty$, has geometrically distributed equilibrium queue length probabilities with parameter $\rho <1$, $\pi _n = (1-\rho )\rho ^n$ for $n \ge 0$, iff

$$\begin{aligned} (1-\rho z)[A_0(z) - D_0(\rho z)]= & {} [A(1)-D(\rho )]\rho z - A(z) + D(\rho z) \end{aligned}$$

(1)

for $|z|<\min (\rho ^{-1},R)$, where R is the minimum of the radii of convergence of the series $A(z) , A_0(z), D(\rho z),D_0(\rho z)$. The total rates of the batch arrival streams then satisfy the constraint:

$$\begin{aligned} A(1)+A_0(1) = D(\rho )+D_0(\rho ) \end{aligned}$$

(2)

Proof

At equilibrium, the queue has balance equations

$$\begin{aligned} \Big (A(1) + \sum _{j=1}^i d_j + d_{i0} \Big ) \pi _i= & {} \sum _{j=1}^{i} a_{j} \pi _{i-j} + \pi _0 a_{0i} + \sum _{j=1}^\infty d_j \pi _{i+j} \quad (i \ge 1) \end{aligned}$$

(3)

$$\begin{aligned} (A(1)+A_0(1)) \pi _0= & {} \sum _{j=1}^\infty (d_j + d_{j0}) \pi _{j} \end{aligned}$$

(4)

Taking $\pi _i = (1-\rho )\rho ^i$ as a trial solution, multiplying Eq. 3 by $z^i$ and summing from $i=1$ to $\infty$ leads to the following equation, where $\varPi (z) = \sum _{i=0}^\infty (1-\rho )\rho ^i z^i = (1-\rho )/(1-\rho z)$ for $|z|<\rho ^{-1}$:

$$\begin{aligned} A(1) (\varPi (z)-\pi _0) + \sum _{i=1}^\infty \sum _{j=1}^i d_j \pi _i z^i + \sum _{i=1}^\infty d_{i0} \pi _i z^i = A(z)\varPi (z) + \pi _0 A_{0}(z) + \sum _{i=1}^\infty \sum _{j=1}^\infty d_j \pi _{i+j} z^i \end{aligned}$$

Dividing by $1-\rho$, this becomes

$$ \frac{A(1)\rho z}{1-\rho z} + \sum _{j=1}^\infty \sum _{i=j}^\infty d_j \rho ^i z^i + \sum _{i=1}^\infty d_{i0} \rho ^i z^i = \frac{A(z)}{1-\rho z} + A_{0}(z) + \sum _{i=1}^\infty \sum _{j=1}^\infty d_j \rho ^{i+j} z^i $$

so that, multiplying by $1-\rho z$ and summing all but one of the remaining series,

$$ A(1)\rho z + \sum _{j=1}^\infty d_j (\rho z)^j + (1-\rho z) D_0(\rho z) = A(z) + (1-\rho z)A_{0}(z) + D(\rho ) \rho z $$

Equation 1 now follows. The converse is proved by dividing Eq. 1 by $1-\rho z$, expanding in powers of z and comparing coefficients.

At $z=1$, Eq. 1 becomes

$$[A(1)-D(\rho )+A_0(1)-D_0(\rho )]\rho = A(1) - D(\rho ) + A_0(1) - D_0(\rho )$$

so that for $\rho < 1$,

$$A(1) - D(\rho ) + A_0(1) - D_0(\rho ) = 0$$

as required. In fact, this also follows from the redundant Eq. 4. The trial solution is therefore valid and the proposition follows by uniqueness of the equilibrium probabilities of an irreducible Markov process.    $\square$

This proposition states that, given the generating functions A(z), D(z) for the normal batches, there is always a geometric, equilibrium queue length probability distribution with any parameter value $\rho \in (0,1)$, provided the special batch generating functions satisfy the equation

$$\begin{aligned} A_0(z) - D_0(\rho z) = \frac{[A(1)-D(\rho )]\rho z - A(z) + D(\rho z)}{1-\rho z} \end{aligned}$$

(5)

Notice that this equation does not uniquely define the individual generating functions $A_0(z), D_0(z)$. However, it is usually required to minimise the effect caused by the additional transitions introduced to secure the geometric probabilities; and hence product-form in a network. This is aided by the following corollary.

Corollary 1

Suppose that A(z), D(z) are given and that $A_0(z), D_0(z)$ are chosen to give geometric, equilibrium queue length probabilities with parameter $\rho$ according to Proposition 1. Then the following properties hold:

• 1. $A_0(z) - D_0(\rho z)$ has radius of convergence less than $1/\rho$ unless

  $$\begin{aligned} A(\rho ^{-1}) + D(\rho ) = A(1) + D(1) \end{aligned}$$

  (6)

  In particular, $\rho$ must satisfy this equation for $A_0(z) - D_0(\rho z)$ to have infinite radius of convergence, e.g. finitely many terms.

• 2. If there exists a real number $r \in (0,1)$, such that $r^{-1}$ is less than the radius of convergence of A(z) and $A(r^{-1}) > A(1) + D(1) - D(r)$, e.g. if A(z) has infinite radius of convergence and so is unbounded, the equation $A(x^{-1}) + D(x) = A(1) + D(1)$ has a unique root $x_0 \in (0,1)$ if and only if $\dot{D}(1) > \dot{A}(1)$, where “dot” denotes differentiation with respect to z, the derivatives being well defined by analyticity of A(z) and D(z). The equilibrium queue length is then geometric, with parameter $x_0$.

• 3. Conversely, the existence of a geometric, equilibrium probability distribution, with parameter $\rho$, implies that $A(\rho ^{-1}) + D(\rho ) = A(1) + D(1)$, provided that $A(\rho ^{-1})<\infty$.

Proof

By Eq. 5, $A_0(z) - D_0(\rho z)$ is a power series, which is singular at the point $z=\rho ^{-1}$ unless the numerator $[A(1)-D(\rho )]\rho z - A(z) + D(\rho z)$ vanishes when $z=\rho ^{-1}$, i.e. unless Eq. 6 is satisfied. The point $z=\rho ^{-1}$ must therefore lie outside the circle of convergence.

For the second part, let $f(x)=A(x^{-1}) + D(x) - A(1) - D(1)$. Then $f(r)>0$ and $f(1)=0$. There is therefore at least one solution to the equation $f(x)=0$ in the open interval (r, 1) if and only if $\dot{f}(1) > 0$ (whereupon $f(1^-)<0$), i.e. $\dot{D}(1) - \dot{A}(1) > 0$, since D(z) and $A(z^{-1})$ are analytic in the unit disk and the annulus with inner radius r and outer radius 1 respectively, and so are continuous, in (r, 1). Substituting into Eq. 1, the batch queue has geometric equilibrium queue length probability distribution with parameter $x_0$, which is unique; hence $x_0$ is unique.

For the last part, setting $z=\rho ^{-1}$ in Eq. 1 yields $A(1)-D(\rho ) = A(\rho ^{-1}) - D(1)$ giving Eq. 6.    $\square$

Notice that the derivatives at $z=0, \; \dot{A}(1)$ and $\dot{D}(1)$ are the task-arrival and task-departure rates respectively, so that $\dot{D}(1) > \dot{A}(1)$ is the expected stability condition for the batch-queue.

We call a queue satisfying the conditions of Proposition 1 a geometric batch-queue with parameter $\rho$. Notice that whenever the corollary holds, the parameter $\rho$ is determined independently of the generating functions $A_0(z)$ and $D_0(z)$, which thereby become constrained by Eq. 1 of the main proposition.

Proposition 1 is a generalisation of a result in [9] where the extra departures to state 0 were restricted to being due to (normal) departure batches that were larger than the current queue length. Then any departure batch size k could occur at any queue length n: if $k \le n$, the state becomes $n-k$ after the departure; if $k > n$ (an excess batch of size k), the state becomes 0. In the present model, this is represented by $d_{k0} = \sum _{j=k+1}^\infty d_j$, but of course this is a special case. We use this case below and now calculate its rate generating function:

$$\begin{aligned} D_0(z) = \sum _{k=1}^\infty \sum _{j=k+1}^\infty d_j z^k = \sum _{j=2}^\infty \sum _{k=1}^{j-1} d_j z^k = \sum _{j=2}^\infty d_j \frac{z-z^j}{1-z} = \frac{zD(1) - D(z)}{1-z} \end{aligned}$$

(7)

Plugging this expression for $D_0(z)$ into Eq. 5 now determines $A_0(z)$ as

$$\begin{aligned} A_0(z) = \frac{[A(1)+D(1)-D(\rho )]\rho z - A(z)}{1-\rho z} \end{aligned}$$

(8)

Notice, therefore, that such queues are entirely determined by just the two normal generating functions A(z) and D(z), which can be arbitrary, up to the existence of equilibrium of the queue.

If, in addition, Eq. 6 is satisfied, the expression simplifies to

$$\begin{aligned} A_0(z) = \frac{\rho z A(\rho ^{-1}) - A(z)}{1-\rho z} \end{aligned}$$

(9)

Such queues are used in an “assembly-transfer network” in Chap. 8 of [4], which is appropriate for models of certain manufacturing systems. The interpretation is that batches of size less than or equal to the queue length are “full batches” and the others are “partial batches” (referring to a size equal to the queue length n which is less than the intended batch size k), which are discarded in the assembly line. We therefore call this the “discard” model, or a discard batch-queue; a minimal discard batch-queue when the parameter $\rho$ is determined by Eq. 6.

Proposition 2

In a minimal discard batch-queue defined by the generating functions A(z), D(z),

• 1. $A_0(z)$ has finitely many terms if and only if A(z) has finitely many terms.

• 2. If $A(z) = \sum _{i=1}^n a_iz^i$ for $1 \le n \le \infty$, $A_0(z) = \sum _{j=1}^{n-1} (\rho z)^j \sum _{i=j+1}^n a_i \rho ^{-i}$.

• 3. If A(z) is geometric with parameter $\alpha$, i.e. $A(z) = A(1)(1-\alpha )z/(1-\alpha z)$, $A_0(z) = \frac{\alpha }{\rho -\alpha }A(z)$.

Proof

• 1. First, as in part 1 of Corollary 1 and using Eq. 8, the point $z=\rho ^{-1}$ is a singularity of $A_0(z)$ unless Eq. 6 is satisfied, i.e. unless the discard batch-queue is minimal. Hence, $A_0(z)$ can only have finitely many terms in a minimal discard batch-queue. Since the numerator of Eq. 8 vanishes at $z=\rho ^{-1}$, the denominator is a factor. Thus, if A(z) has finitely many terms – and is of degree n, say – then $A_0(z)$ also has finitely many terms and has degree $n-1$. Conversely, $A(z) = \rho z A(\rho ^{-1}) - (1-\rho z)A_0(z)$ and so has finitely many terms if $A_0(z)$ does.

• 2. Substitution into Eq. 9 and rearranging gives

  $$ A_0(z) = \frac{z \sum _{i=2}^n a_i \rho ^{-(i-1)}(1-(\rho z)^{i-1})}{1-\rho z} $$

  But $1-(\rho z)^{i-1} = (1-\rho z)\sum _{j=0}^{i-2} (\rho z)^j$ and so

  $$ A_0(z) = z \sum _{i=2}^n \sum _{j=0}^{i-2} a_i \rho ^{-(i-1)} (\rho z)^j = \sum _{j=0}^{n-2} \sum _{i=j+2}^n a_i \rho ^{-i} (\rho z)^{j+1} $$

• 3. The result follows by substituting into Eq. 9.

   $\square$

2.1 Example

Suppose all batches have size either 1 or 2 in a minimal discard batch-queue and define $A(z) = \lambda _1z + \lambda _2z^2, D(z) = \mu _1 z + \mu _2 z^2$ so that $D_0(z) = \mu _2 z$. Equation 6 then yields $\mu _2 \rho ^4 + \mu _1 \rho ^3 - (\lambda _1+\lambda _2+\mu _1+\mu _2)\rho ^2 + \lambda _1\rho + \lambda _2 = 0$ which factorises into $(\rho -1)P(\rho ) = 0$, where $P(x) = \mu _2 x^3 + (\mu _1+\mu _2) x^2 - (\lambda _1+\lambda _2)x - \lambda _2$. We therefore seek a root of the cubic equation $P(x) = 0$, i.e. of

$$\begin{aligned} \mu _2 x^3 + (\mu _1+\mu _2) x^2 - (\lambda _1+\lambda _2)x - \lambda _2 = 0 \end{aligned}$$

(10)

Now, $P(0)<0$ and $P(1) = 2\mu _2 + \mu _1- (2\lambda _2 + \lambda _1) > 0$ under the stabilility condition, so that there is a geometric equilibrium probability distribution for the queue length.

Equation 9 (or part 2 of Proposition 2 directly) gives the arrivals-in-state-0 rate generating function $A_0(z) = \frac{(\rho z(\lambda _1/\rho + \lambda _2/\rho ^2) - \lambda _1 z - \lambda _2 z^2}{1-\rho z} = \lambda _2 z/\rho$. Thus, only unit-batch special arrivals are required for a geometric solution to exist. In the special case that arrivals are always single, $\lambda _2=0$ and we find $A_0(z) = 0$. Indeed, provided that arrivals are single, part 2 of Proposition 2 ensures that if departure batches with any choice of rates are introduced into an M/M/1 queue, a geometric equilibrium queue length probability distribution is preserved (assuming equilibrium exists) without introducing any special arrivals in the empty queue state.

2.2 The Reversed Batch-Queue

Although to apply RCAT requires the reversed rates of only the active actions – in our case the normal departures – we will need the whole reversed process later when we consider sojourn times in a network of batch-queues. Notice that the structure of a batch-queue is symmetric: normal batch arrivals and departures together with special batch arrivals and departures, out of and into state 0 only, respectively. Any such queue is specified entirely by its four corresponding rate generating functions $A, A_0, D, D_0$. Because of the symmetry, the reversed process is also a batch-queue with rate generating functions $A', A'_0, D', D'_0$, say. We now calculate these and confirm, using Proposition 1, that the reversed queue has the same geometric queue length probability distribution at equilibrium (assumed to exist, with $\rho <1$) as the original (forward) queue.

Proposition 3

The reversed process of a geometric batch-queue with parameter $\rho$ and rate generating functions $A(z), A_0(z), D(z), D_0(z)$ is also a geometric batch-queue with parameter $\rho$ and rate generating functions:

$$\begin{aligned} A'(z) = D(\rho z); \quad A_0'(z) = D_0(\rho z); \quad D'(z) = A(\rho ^{-1} z); \quad D_0'(z) = A_0(\rho ^{-1} z). \end{aligned}$$

Proof

We calculate the rates of the individual transitions in the reversed process, denoted by primes, by multiplying the corresponding forward rates by the appropriate ratio of equilibrium probabilities (for the source and destination states of the transition). In the reversed process, the reversed arrival transitions cause decreases in the queue length and so become departures, and similarly, the reversed departure transitions become arrivals. Moreover, by the symmetry of the model, the special transitions out of/into state 0 map into special transitions in the reversed process into/out of state 0, respectively. We now easily obtain, using the hypothesis that the equilibrium queue length probabilities are geometric:

$$\begin{aligned} a_k' = \rho ^k d_k; \quad a_{0k}' = \rho ^k d_{k0}; \quad d_k' = \rho ^{-k} a_k; \quad d_{k0}' = \rho ^{-k} a_{0k}. \end{aligned}$$

The rate generating functions of the reversed process then follow as stated.

Finally, since $A'(1)=D(\rho )< \infty , D'(\rho )=A(1) < \infty , A'(1)-D'(\rho ) = -(A(1)-D(\rho )), A'(z)-D'(\rho z) = -(A(z)-D(\rho z))$ and $A'_0(z)-D'_0(\rho z) = -(A_0(z)-D_0(\rho z))$, the reversed process satisfies the conditions of Proposition 1 and has equilibrium queue length probability distribution with the same parameter $\rho$.    $\square$

3 Product-Form Batch-Networks

By construction, networks of geometric batch-queues – call them batch-networks – may have product-forms when their nodes are interconnected such that normal batch-departures become the normal batch-arrivals at another node. The special departures must leave the network and the special arrivals must also be external¹; their parameters are determined by the rate equations of RCAT combined with Eq. 9 or Proposition 2. Normal internal departure streams may be split probabilistically to several other nodes by using parallel active departure transitions, just as in conventional queueing networks [6, 11, 12]. Thus, the enabling constraints of RCAT are satisfied in that the passive transitions are normal arrivals that are enabled in every state and, similarly, the active transitions come into every state, these being normal departures. It remains to solve the rate equations which equate the reversed rates of the active transition types, a say, to an associated variable $x_a$ – see [10] for a practical description. Notice that the reversed rates will in general depend on the set of $x_a$ and can be found from Proposition 3. This leads to the product-form given below in Theorem 1.

3.1 Product-Form Theorem

In a Markovian network of M batch-queues (or nodes), in which the mean service times of node i are respectively $\mu ^{-1}_{ik}, \mu ^{-1}_{0ik}$ and the mean external arrival rates at node i are respectively $\lambda _{ik}, \lambda _{0ik}$ for normal, special batches of size $k \ge 0$, we define the rate generating functions:

$$\begin{aligned} A_i(z) = \sum _{k=1}^\infty \lambda _{ik} z^k; A_{0i}(z) = \sum _{k=1}^\infty \lambda _{0ik} z^k; D_i(z) = \sum _{k=1}^\infty \mu _{ik} z^k; D_{0i}(z) = \sum _{k=1}^\infty \mu _{0ik} z^k. \end{aligned}$$

The “routing probability” $p_{ikjl}\ (1 \le i \ne j \le M; k,\ell \ge 1)$ is the probability that a normal batch of size k that completes service at node i immediately proceeds to node j as a batch of size $\ell$². We define $B_{ij}(\rho ,z)$ to be the generating function of the reversed rates (depending on the local geometric parameter $\rho _i$ at node i) of the normal departure transitions at node i that go to node j as batches of size $\ell \ge 1$:

$$ B_{ij}(\rho _i,z) = \sum _{\ell =1}^\infty \sum _{k=1}^\infty p_{ikjl} \mu _{ik} \rho _i^k z^\ell . $$

Note that typically $p_{ikjl} = p_{ikj}\delta _{kl}$ for certain quantities $p_{ikj}$, i.e. there is no change to the batch size in transit. With no re-batching, therefore, $B_{ij}(\rho _i,z) = \sum _{k=1}^\infty p_{ikj} \mu _{ik} (\rho _i z)^k$. Furthermore, if the routing probabilities are the same for all batch sizes, i.e. $p_{ikjl} = p_{ij}\delta _{kl}$, we have $B_{ij}(\rho _i,z) = p_{ij} D_{i}(\rho _i z)$.

Our main product-form result now follows by construction: the detailed proof is omitted, being the simple application of RCAT just described.

Theorem 1

A network of M minimal discard batch-queues at equilibrium, specified according to the above notation, has equilibrium joint queue length probability distribution with the product-form $\mathrm {I\!P}(\mathbf {N}=\mathbf {n}) = \prod _{j=1}^M (1- \rho _j) \rho _j^{n_j}$, where $N_j$ is the equilibrium queue length random variable at node j, if the numbers $\rho _1,\ldots ,\rho _M$ are the solution of the system of non-linear equations, for $1 \le j \le M$:

$$\begin{aligned} A_j(\rho _j^{-1}) + \sum _{1 \le k\ne j \le M} B_{kj}(\rho _k,\rho _j^{-1}) + D_j(\rho _j) = A_j(1) + \sum _{1 \le k\ne j \le M} B_{kj}(\rho _k,1) + D_j(1). \end{aligned}$$

(11)

Furthermore, the special arrival streams to empty queues (only) have rate generating functions:

$$\begin{aligned} A_{0j}(z) = \frac{ \rho _j z \left[ A_j(\rho _j^{-1}) + \sum _{1 \le k\ne j \le M} B_{kj}(\rho _k,\rho _j^{-1})\right] - A_j(z) - \sum _{1 \le k\ne j \le M} B_{kj}(\rho _k,z)}{1-\rho _j z} \end{aligned}$$

at node j.

To clarify, we observe that Eq. 11 is simply Eq. 6 applied to node j, which has additional normal batch-arrivals with rates defined by the reversed rates of the feeding normal departures at other nodes, given by the generating functions $B_{kj}(\rho _k,z)$. The special arrival streams necessary to ensure the product-form are given by the rate generating functions $A_{0j}(z)$, computed from Eq. 9 or explicitly from part 2 of Proposition 2, with parameter $\rho$ equal to the jth component of the vector computed for the solution of the equations in the theorem.

Necessary and sufficient conditions for equilibrium to exist are difficult to obtain, as in even simple open queueing networks, but the following sufficient condition can turn out to be useful.

3.2 Sufficient Stability Condition

The necessary and sufficient condition for equilibrium to exist is that a vector $\mathbf {\rho }$ with $0<\rho _i<1$, for $1 \le i \le M$, can be found that satisfies Proposition 1 and, in the case of a minimal discard batch-queue, Eq. 6. It then follows that the net task-arrival rate at each node j is strictly less than the task-service rate, i.e. $\dot{A}_j(1) + \sum _{1 \le k\ne j \le M} \dot{B}_{kj}(\rho _k,1) < \dot{D}_j(1)$. This is a rather useless a priori condition because the quantities $\rho _k$ are unknown, but since each $\rho _k < 1$, a sufficient condition for equilibrium to exist is that

$$\begin{aligned} \dot{A}_j(1) + \sum _{1 \le k\ne j \le M} \dot{B}_{kj}(1,1) < \dot{D}_j(1) \text { for } 1 \le j \le M \end{aligned}$$

(12)

$\dot{B}_{kj}(\rho _k,z)$ being monotonically increasing in $\rho _k$, which is easy to check.

For the case of no re-batching and routing probabilities $p_{ij}$ that do not depend on the batch size, this simplifies to $\dot{A}_j(1) + \sum _{1 \le k\ne j \le M} p_{kj} \dot{D}_{k}(1) < \dot{D}_j(1),$ a more conventional type of “traffic constraint”.

3.3 Open and Pseudo-closed Networks

First, notice that all non-trivial (i.e. with at least one non-unit batch size) batch-networks are open in the sense that they have external (special) arrivals and departures from the network. Moreover, this means that all nodes have unbounded queue lengths, whatever the batch size probability distributions; even when special batches are a.s. finite, with positive probability some node in the network is empty and so the total network population can increase due to special arrivals at that node. Again, with positive probability, a node may subsequently become empty before any special departure occurs to reduce the total population. In this way it is possible for the network population to increase indefinitely (with probability one), so that it is unbounded; the same therefore applies to each queue length. Contrary to plain queueing networks, therefore, it must always be the case that $\rho _i<1$ at each node i. Notwithstanding these remarks, we define an open batch network to be one in which there are external normal arrivals or departures at one or more nodes, and a pseudo-closed batch network (mixed open-closed) to be one with no external normal arrivals or departures (Figs. 2 and 3).

Fig. 2.

Open batch-network

Fig. 3.

Pseudo-closed batch-network: closed for normal tasks, open for special tasks

Consider, as a simple example, a cycle of two discard batch-queues of the type considered above and illustrated in Fig. 3, with batch sizes restricted to 1 or 2. Without loss of generality, we assume that departing batches of size 2 become arriving batches of size 2 at the other node; however we could just as easily choose to have departing batches change their size probabilistically (from 1 to 2 and/or 2 to 1 here) when they arrive at the other node. Denote the types of the transitions synchronising node 1 departures with node 2 arrivals by $\alpha _{21}, \alpha _{22}$, with rates $d_{11}=\mu _{11}, d_{12}=\mu _{12}$ (corresponding to batch sizes 1 and 2) respectively, and similarly for the corresponding transitions synchronising node 2 departures with node 1 arrivals. Further, let the external arrival rate of normal batches of size j at node i be $\lambda _{ij}$, so that the generating function of all the normal arrival rates at node i is $\sum _{j=1}^2 a_{ij}z^j$, where $a_{ij} = x_{\alpha _{ij}}+\lambda _{ij}$ for $i=1,2; j=1,2$. The special batch external arrival rates and their generating functions $A_{i0}(z)$ are then determined by Eq. 8. To illustrate more clearly, proceeding from first principles, the rate equations are:

$$\begin{aligned} x_{\alpha _{21}} = \rho _1 \mu _{11}; \quad x_{\alpha _{22}} = \rho _1^2 \mu _{12}; \quad x_{\alpha _{11}} = \rho _2 \mu _{21}; \quad x_{\alpha _{12}} = \rho _2^2 \mu _{22} \end{aligned}$$

where $\rho _i$ is the solution of the equation

$$ \mu _{i2}\rho _i^3 + (\mu _{i1}+\mu _{i2})\rho _i^2 - (\lambda _{i1}+\lambda _{i2}+x_{\alpha _{i1}}+x_{\alpha _{i2}})\rho _i - \lambda _{i2}-x_{\alpha _{i2}} = 0 $$

for $i=1,2$, which arises immediately from Eq. 10. This pair of simultaneous cubic equations must be solved numerically.

Equivalently, just applying Theorem 1, we obtain – in the more general case where departing batches from node i may choose to leave the network with probability $1-p_{ij}$ or to pass to the other node with probability $p_{ij}\ (i\ne j\in \{1,2\})$:

$$\begin{aligned} A_1(\rho _1^{-1}) + p_{21} D_{2}(\rho _2 / \rho _1) + D_1(\rho _1)= & {} A_1(1) + p_{21} D_{2}(\rho _2) + D_1(1) \\ A_2(\rho _2^{-1}) + p_{12} D_{1}(\rho _1 / \rho _2) + D_2(\rho _2)= & {} A_2(1) + p_{12} D_{1}(\rho _1) + D_2(1) \end{aligned}$$

However, these are simultaneous quartic equations, the invalid roots $\rho _1, \rho _2 = 1$ not being factored out as in Eq. 10.

The sufficient stability conditions for this network are

$$\begin{aligned} \dot{A}_1(1) + p_{21} \dot{D}_{2}(1)< \dot{D}_1(1) \text { and } \dot{A}_2(1) + p_{12} \dot{D}_{1}(1) < \dot{D}_2(1), \end{aligned}$$

which yield $\lambda _{11} + 2 \lambda _{12} + p_{21} (\mu _{21}+2 \mu _{22}) < \mu _{11}+2 \mu _{12}$ and a similar inequality, interchanging the node-subscripts 1 and 2.

A numerical instance of this example has $\mu _{11} = 10; \mu _{12} = 2; \mu _{21} = 5; \mu _{22} = 3; \lambda _{11} = 4; \lambda _{12} = 0; \lambda _{21} = 3; \lambda _{22} = 0; p_{12} = 0.4; p_{21} = 0.6$. The sufficient stability conditions require, respectively, that $10.6 < 14$ and $8.6 < 11$, which are satisfied, and the solution for the product-form is $\rho _1= 0.584, \rho _2= 0.615$.

If we increase the external arrival rate at node 2 to $\lambda _{21} = 6$ the second sufficient stability conditions becomes $11.6 < 11$ so is not satisfied. However, in this case a solution $\rho _1= 0.767, \rho _2= 0.931$ exists and the network is stable; the second exact stability condition is $\lambda _{21} + 2 \lambda _{22} + p_{12} \rho _1 (\mu _{11}+2 \mu _{12}\rho _1) < \mu _{21}+2 \mu _{22}$, i.e. $10.01 < 11$.

3.4 Pseudo-closed Networks

It is well known that, in a closed Jackson network [12], the (traffic) rate equations have a unique solution only up to a multiplicative constant, these being the solution of a set of homogeneous linear equations. With batches in minimal discard queues, as we have already pointed out, the network’s population is not bounded and certainly not constant because of the external special arrivals. Furthermore, the rate equations are non-linear. However, pseudo-closed networks, with no external normal arrivals, do have a different type of constraint, arising from Eq. 11 which, for a pseudo-closed network becomes:

$$\begin{aligned} \sum _{1 \le k\ne j \le M} B_{kj}(\rho _k,\rho _j^{-1}) + D_j(\rho _j) = \sum _{1 \le k\ne j \le M} B_{kj}(\rho _k,1) + D_j(1) \end{aligned}$$

(13)

for $1 \le j \le M$. When batch sizes do not change in transit and the routing probabilities are the same for all batch sizes, the equation becomes

$$\begin{aligned} \sum _{1 \le k\ne j \le M} p_{kj} D_k(\rho _k/\rho _j) + D_j(\rho _j) = \sum _{1 \le k\ne j \le M} p_{kj} D_k(\rho _k) + D_j(1) \end{aligned}$$

(14)

Summing over j then gives, setting $p_{jj} = 0$ for $1\le j \le M$,

$$ \sum _{j=1}^M \sum _{k=1}^M p_{kj} D_k(\rho _k/\rho _j) + \sum _{j=1}^M D_j(\rho _j) = \sum _{j=1}^M \sum _{k=1}^M p_{kj} D_k(\rho _k) + \sum _{j=1}^M D_j(1) $$

Interchanging the order of summation on the right hand side and noting that for pseudo-closed networks $\sum _{j=1}^M p_{kj} = 1$ for all k, two of the sums cancel and we are left with

$$ \sum _{j=1}^M \sum _{k=1}^M p_{kj} D_k(\rho _k/\rho _j) = \sum _{j=1}^M D_j(1) $$

This is a constraint on all the pairwise ratios of the nodes’ utilisations – the parameters of the required geometric distributions at each node. Notice that this does not apply to open batch networks because the corresponding equation would include the term $\sum _{j=1}^M A_j(\rho _j^{-1})$, which is neither constant nor a function of the utilisation-ratios.

Clearly one solution to this equation has $\rho _1=\rho _2= \ldots = \rho _M$, whereupon we may write

$$ (\mathbf {D}(\varvec{\rho }) - \mathbf {D}(\mathbf {1})) (I-P) = \mathbf {0} $$

where $\varvec{\rho }= (\rho _1, \ldots , \rho _1)$, $\mathbf {D}(\mathbf {z})$ is the vector $(D_1(z_1),\ldots ,D_M(z_M))$, $\mathbf {1}$ is the vector of ones (1, ..., 1) of length M, the matrix $P = (p_{ij} \mid 1 \le i,j \le M)$ and I is the identity $M \times M$ matrix. Since P is singular for a pseudo-closed network, these equations have a unique solution up to an arbitrary multiplicative constant (the rank of P being $M-1$ in a connected network). Hence we obtain

$$ D_j(\rho _1)-D_j(1) = \kappa _j (D_1(\rho _1)-D_1(1)) $$

for $2 \le j \le M$, where the vector $(1,\kappa _2,\ldots ,\kappa _M)$ is a solution to the linear equations $\mathbf {x}.(I-P) = \mathbf {0}$, i.e. a left eigenvector of $I-P$ with eigenvalue 0. It therefore remains to solve each of the non-linear equations $D_j(y)-D_j(1) = \kappa _j (D_1(y)-D_1(1))$ for $j=2,\ldots , M$, each of which must have the same solution $y=\rho _1$. In general, this will be highly constraining on the parameters of the network, but for a two-node network there is only one such equation to solve, namely (since $\kappa _2=1$) $D_2(\rho )-D_2(1) = D_1(\rho )-D_1(1)$, or, after factorisation,

$$ (\rho -1)[(\mu _{22}-\mu _{12})\rho - (\mu _{11}+\mu _{12}-\mu _{21}-\mu _{22})]=0 $$

The only valid solution (with $\rho _1=\rho _2=\rho$) is therefore $\rho = -1-\delta _1/\delta _2$ where $\delta _i = \mu _{1i}-\mu _{2i}$ for $i=1,2$. For $0<\rho <1$ we therefore require that either $\delta _1>0, \delta _2<0, -\delta _2<\delta _1<-2\delta _2$ or $\delta _1<0, \delta _2>0, \delta _2<-\delta _1<2\delta _2$.

Consider the following pseudo-closed 2-node example, for which we must have $p_{12}=p_{21}=1$. Let $\mu _{11}=2, \mu _{12} = 1; \mu _{21} = 2.6$ and $\mu _{22}$ be left unspecified. Then $\delta _1=-0.6$ and $\delta _2=1-\mu _{22}$, so we have the second case and require $0.4<\mu _{22}<0.7$. No solutions were found for $\mu _{22}$ outside this range and all solutions with $\mu _{22}$ in the range had $\rho _1=\rho _2$. For example, when $\mu _{22}=0.699$ we find $\rho _1=\rho _2=0.9934$; when $\mu _{22}=0.401$, $\rho _1=\rho _2=0.0017$; and when $\mu _{22}=0.5$, $\rho _1=\rho _2=0.2$. In fact, it can be shown via tedious algebra that there are no other solutions to Eq. 14 when $M=2$ other than $\rho _1=\rho _2$. Whilst being a challenge to generalize this to arbitrary pseudo-closed networks, this is not the point of the present paper and the urgency of such a result is not clear.

4 Conclusion

As noted in the introduction, batch-networks of this type are well suited to modelling bursty traffic that occurs in networks of various types, for example router networks and file transfers in storage systems. Data centres, in particular, consume vast amounts of energy, often requiring their own power plants to be constructed, and demand for their services is set to continue growing rapidly. Thus both economics and social responsibility demand the minimisation of energy use and certainly that energy not be wasted. One way this is being done is to construct devices with several power levels of operation, at least including “on” and“off”, and probably with “sleep” or“standby” intermediate levels as well. When a device is not in use, its power level decreases, e.g. it is switched off, and conversely when it is required again, it is switched on. If the offered workload is “smooth”, i.e. devices do not have long idle periods, there is no benefit in shutting them down or reducing their power level; they will quickly have to be powered up again, with increased energy (and wear) overheads, resulting in a penalty, not a saving in energy [15]. Therefore in energy-efficient systems, workload has to be scheduled to introduce bursts into the workload, with longer idle periods, and these are well modelled by batch movements in a network. To minimise energy consumption subject to adequate quality of service (QoS), and vice versa, therefore requires models that account for burstiness.

In a batch-network, the scheduled regular traffic can be represented by normal batches. When a device is switched off, it may lose work that has either already arrived or is on the way, for example in a control unit buffer. Conversely, when the device starts up again, it may be that a backlog of work has built up and so there is a sudden burst of activity. Such events – switching off and on again – are well described by a batch-queue’s special departure and arrival streams. Efficient, product-form, batch-networks therefore have the potential to provide a way to suggest alternative scheduling algorithms that can be assessed quickly, even in real time.

Of course there is the objection that, even if batch-networks provide a good representation, it is unlikely that the conditions will be met that lead to a product-form – and hence efficient solution. However, direct analytical solutions (solving the underlying Markov chain’s global balance equations) are intractable numerically and simulation is expensive and time consuming. Therefore approximations are generally used. This gives at least three important roles for product-forms:

• To provide exact results when their conditions are met;

• To provide a benchmark against which to assess approximate methods and simulation: a parameterisation of a model would be chosen that does satisfy the conditions for product-form and the ensuing exact solution would be compared with the inexact model’s output;

• Product-forms themselves are (usually) approximations and may lead to upper and/or lower bounds on the exact solution.

In fact the generality of the RCAT approach allows batch-queues to be incorporated into any other product-form networks, for example G-networks or BCMP networks, or even be mixed with product-form Petri nets [1,2,3, 5, 11]. Current work is investigating a pair of batch queues with finite batch sizes and without any special arrivals or departures. The essence of the approach is to observe that above a certain pair of queue lengths, the steady state balance equations are the same with or without the special batches. Below these thresholds, the method of spectral expansion is used to yield an “almost” product-form solution [14].