# The distribution of queueing network states at input and output instants

Kenneth C. Sevcik, Israel Mitrani

► To cite this version:

Kenneth C. Sevcik, Israel Mitrani. The distribution of queueing network states at input and output instants. [Research Report] IRIA-RR-307, IRIA. 1978, pp.20. hal-04716524

HAL Id: hal-04716524

https://inria.hal.science/hal-04716524v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Dw = 04137

RR 307

RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

THE DISTRIBUTION OF
QUEUEING NETWORK STATES
AT INPUT AND OUTPUT INSTANTS

Kenneth C. SEVCIK
Isi MITRANI

Rapport de Recherche N° 307

Mai 1978
# THE DISTRIBUTION OF QUEUEING NETWORK STATES AT INPUT AND OUTPUT INSTANTS

Kenneth C. Sevcik*, Isi Mitrani**

## Résumé :

On étudie des réseaux de files d'attente à l'état stationnaire sur un ensemble de points particuliers qui sont les instants d'arrivée et de départ considérés à un nœud quelconque. On sait que les processes définis sur ces séquences de poins sont non-Poissonniens et dépendants. A priori la relation entre les distributions stationnaires des chaînes de Markov incluses et les distributions à un instant quelconque n'est pas évidente. On trouve, précisément, une relation très simple entre ces distributions pour une large catégorie de réseaux. Par exemple, si le réseau est ouvert cette relation n'est autre que l'idendité.

## Abstract :

Queueing networks are studied at selected points in the steady-state, namely the moments when jobs of a given class arrive into a given node (either from the outside of from other nodes), and the moments when jobs of a given class leave a given node (either for the outside or for other nodes). The processes defined by these points are known to be, in general, non-Poisson, interdependent and serially correlated; therefore the relation between the distribution of the system state embedded at those moments, and the steady-state (or random point) distribution, is not obvious a priori. For a large class of networks having product form equilibrium distributions we show that (a) if the given job class belongs to an open subchain, the state distributions at input points, output points and random points are identical, and (b) if the job class belongs to a closed subchain, the distribution at input and output points is the same as the steady-state distribution of a network with one less job in that subchain.

Keywords and phrases : queueing theory, network of queues, product form, waiting time distributions.

CR categories : 4.32, 4.35, 5.5, 6.20

<footnote>* On leave of absence from the University of Toronto.</footnote>

<footnote>**On leave of absence from the University of Newcastle upon Tyne.</footnote>
# O. INTRODUCTION

Ever since the discovery (J.R. Jackson, [11]) that in some cases, the steady-state distribution of a network of queues can be factored into a product of the marginal distributions of the states of individual nodes, there has been some uncertainty as to the exact meaning of this result. If a node has $c$ parallel exponential servers, to what extent can it be treated as an isolated M/M/c queue? In particular, can the distribution of the sojourn times at that node (and not just the mean sojourn time) be obtained by such a treatment? The answer to this last question depends on whether customers arriving into the node see the steady-state distribution of the node state and that, in turn, has prompted several investigations of the properties of input streams.

Burke [3] has shown, by examining the simplest non-trivial network (a single M/M/1 node with Bernoulli feedbacks), that the input process composed of the external arrivals and the fed-back customers is not Poisson in general. Disney and McNickle [9] have strengthened this result by showing that the input process is not even renewal. On the basis of this and other evidence of the complexity and interdependence of the flow processes in a queueing network, these two authors express a strong doubt about the possibility of decomposing the network and treating individual nodes in isolation.

Yet in the one-node example which Burke considered, it emerged that although the input customers do not form a Poisson stream, they still see the steady-state distribution of the queue size (with the proviso that fed-back customers do not include themselves in the queue that they see). Input instant and steady-state distributions were shown to be closely related also in three finite-state models. These are: an M/M/1 queue with a finite customer population (Cooper [6]), an M/M/1 queue with finite waiting room (Cooper [6]) and a two-node closed network with a feed-back loop around one of the nodes (Mitrani [18]). The first two models can be viewed as two-node closed networks in which the service rate at the second node is, respectively, proportional to the number of customers there or constant. In all three cases the following result holds:
$$P_K^i(n) = \frac{P_K^e(n)}{1-P_K^e(K)} = P_{K-1}^e(n), \quad n=0,1,\dots,K-1$$

where $P_K^i(n)$ and $P_K^e(n)$ are the input instant and the equilibrium probabilities of n customers at node 1 given that there are K customers in the network.

We shall demonstrate that these results generalise to a large class of networks, open, closed or mixed, with many customer classes, where scheduling disciplines and service requirement distributions are of certain types. The probability that a class r customer joining node m sees network state S, $\pi(S)$, depends on whether the network is open or closed with respect to class r. If open, then $\pi(S)$ is equal to the probability that a class r customer arriving from the outside into node m sees state S (which is equal to the steady-state probability of S if the external arrivals are state-independent). If closed, then $\pi(S)$ is equal to the steady-state probability of S in a network with one less class r customer. Similar results hold for the state left behind by a class r customer leaving node m.

The above probabilities will be derived as the ratio of two rates : the rate at which class r customers join node m and find network state S, divided by the total rate at which class r customers join node m. In section 1 we give the justification for this approach. Section 2 contains our main result : a theorem establishing a sufficient condition for a network to have input and output instant state distributions related as described to the steady-state distribution. In section 3 we show that a large class of queueing networks, including those defined by Jackson [12], Gordon and Newell [10], Baskett, Chandy, Muntz and Palacios [2], satisfy the sufficient condition. Finally, in section 4 we discuss the possibility of extending the results to a still broader class of networks.

# 1. GENERAL ARGUMENT.

Let $\{\sigma_n, \tau_n\}$, $n=0,1,\dots$ be a Markov renewal process : a Markov chain $\{\sigma_0, \sigma_1, \dots\}$ embedded at moments $t_0 = 0, t_1, t_2, \dots$, where $t_{n+1} = t_n + \tau_n$ ($n=0,1,\dots$), so that the joint distribution of $\sigma_{n+1}$ and $\tau_n$ depends only on $\sigma_n$ (and not on $\sigma_0, \dots, \sigma_{n-1}, \tau_0, \dots, \tau_{n-1}$). The moments $t_0, t_1, \dots$ will be referred to as "event points".
Suppose that the Markov chain {$\sigma_n$} is irreducible and aperiodic and
that the equilibrium probabilities

$$
\pi_i = \lim_{n \to \infty} P(\sigma_n = i)
$$

exist for all states i=0,1,... . Consider the Markov renewal process on a
large time interval of length T; denote by n(T) the total number of event
points during that interval, by nᵢ(T) the number of event points at which
{σₙ} is in state i and by nᵢⱼ the number of event points between the j-1'st
and the j'th point at which {σₙ} is in state i (j=1,2,...). Since the consecutive
occurences of state i (or of any other state) are regeneration points
for the Markov renewal process, the numbers n₁, n₂ ... are independent and
identical, distributed. Their expected value is therefore equal to

$$
(1) \quad E[n_{ij}] = \lim_{T \to \infty} \frac{E[n(T)]}{E[n_i(T)]}.
$$

On the other hand, the expected number of points between consecutive
occurences of state i (i.e. the expected recurrence time for state i in the
Markov chain {$\sigma_n$}) is, under our assumptions, equal to 1/πᵢ. Dividing the
numerator and the denominator in the right-hand side of (1) by T and denot-
ing

$$
\gamma = \lim_{T \to \infty} \frac{E[n(T)]}{T} ; \quad \gamma_i = \lim_{T \to \infty} \frac{E[n_i(T)]}{T}
$$

we can rewrite (1) as

$$
(2) \quad \pi_i = \frac{\gamma_i}{\gamma} .
$$

In what follows, we shall use (2) to determine the equilibrium distri-
bution π(S) of a queueing network state S embedded at the moments when customers
of a given class join (or leave) a given node (those will be the event points).
We shall write π(S) = γ(S)/γ, where γ is the average number of event points per
unit time and γ(S) is the average number of event points at which the network
is in state S, per unit time.
## 2. GENERAL RESULT.

Consider an arbitrary topology queueing network with M nodes and R customer classes. Customers may change class as they move from node to node. Specifically, a customer of class r, when completing service at node i, goes to node j as a customer of class s with probability $p_{ir,js}$; that job leaves the network with probability $p_{ir,0} = 1 - \sum_{j,s} p_{ir,js}$ ($i,j=1,2,...,M$; r,s=1,2,...,R). To simplify notation, we shall reclassify the customers, using the pair $(i,r)$ as the new class index. Thus, from now on, "class r" will specify both the current affiliation and the current location of a customer ($r=1,2,...,M$ R). The transition probabilities become $p_{rs}$ (the probability that a class r customer completing service turns into a class s customer) and $p_{ro}$ (the probability that he leaves the network).

The set of customer classes is split by the transition probability matrix into one or more non-intersecting subsets, or "subchains", in the following way: two customer classes belong to the same subchain iff there is a non-zero probability that a customer will enter both classes during his life in the network. Denote these subchains by $E_1, E_2, ..., E_D$ (for example, if in the original notation we had $p_{ir,js} = 0$ for $r \neq s$, there would now be at least R subchains).

It may be that some subchains are closed, having a constant number of customers in them at all times, while others are open, with external arrivals and departures. Moreover, the external arrival processes may be state dependent, in a restricted way. Let S be the network state, $N_O(S)$ be the total number of customers in the open subchains and $c_\ell(S)$ be the number of customers in subchain $E_\ell$ when the network is in state S. The external arrivals may be generated in either, but not both, of the following two ways :

a) By a single non-homogeneous Poisson process whose instantaneous rate, $\lambda(N_O(S))$, depends on the system state via the total number of customers in the open subchains. A new arrival joins class r with probability $p_{or}$ ($\sum_r p_{or} = 1$)

b) By separate state-dependent Poisson processes, one for each open subchain. The instantaneous rate of the $\ell$'th process, $\lambda_\ell(c_\ell(S))$, depends on S via the number of customers in the subchain $E_\ell$. A new arrival in the $\ell$'th stream joins class r with probability $p_{or}$ ($\sum_{\ell} p_{or} = 1$ if $E_\ell$ is open).
The flow of customers around the network is described by D systems of linear equations :

$$ (3) \qquad e_r = p_{or} + \sum_{s \in E_\ell} e_s p_{sr} ; r \in E_\ell , \quad \ell=1,2,\dots,D. $$

If $p_{or} \neq 0$ for some $r \in E_\ell$ then the subchain $E_\ell$ is open; the corresponding system (3) has a unique solution $\{e_r\}$ which can be interpreted as the average number of times a customer joins class $r$ during his life in the network.

If $p_{or}=0$ for all $r \in E_\ell$ then $E_\ell$ is closed; the system (3) has infinitely many solutions (differing from each other by a multiplicative constant) which can be interpreted as the relative frequency with which jobs join class $r$. The number of customers circulating in a closed subchain is constant.

We shall use the following notation :

$\mathcal{N}$ is the network configuration; it includes the nodes, the customer classes, the subchains and the number of customers in each closed subchain ;

$\ell_r$ is the index of the subchain to which class $r$ belongs ;

$m_r$ is the index of the node to which class $r$ belongs ;

$\mathcal{N}_r$ is a network configuration which is identical to $\mathcal{N}$ if $E_{\ell_r}$ is open, and differs from $\mathcal{N}$ by having one less customer in $E_{\ell_r}$ if $E_{\ell_r}$ is closed.

$S$ is a network state; it describes the customer configuration at each node : numbers, classes, stages of service reached (a precise definition will be given later);

$S_{+r}$ is the set of all network states which differ from $S$ by having one more customer of class $r$ (the elements of $S_{+r}$ may differ from each other only by the stage of service reached by the extra class $r$ customer and by his position in the queue);

$v_r(\sigma,s)$ is the instantaneous rate at which class $r$ customers complete service in state $\sigma$ and leave behind state $S$;

$$ \Lambda_{\ell_r}(S) = \begin{cases} 1 & \text{if } E_{\ell_r} \text{ is closed} \\ \lambda(N_o(S)) & \text{if } E_{\ell_r} \text{ is open and the external arrivals are of type (a)} \\ \lambda_{\ell_r}(c_{\ell_r}) & \text{if } E_{\ell_r} \text{ is open and the external arrivals are of type (b)}; \end{cases} $$
$P_r(S)$ is the steady-state probability of state S in network configuration $\mathcal{N}$; the steady-state distribution is assumed to exist;

$\pi_r^r(S)$ is the equilibrium probability that, in network configuration $\mathcal{N}$, a customer joining class r finds state S. Note that, since the customer does not include himself in the state that he sees, S is not a state of $\mathcal{N}$ but a state of $\mathcal{N}_r$ (the two differ when $E_{\mathcal{N}_r}$ is closed);

$\xi_r^r(S)$ is the equilibrium probability that, in network configuration $\mathcal{N}$, a customer completing service in class r, leaves behind state S (similar remark to the above applies).

Our general result can now be stated :

**Theorem.** If, for each class r in network configuration $\mathcal{N}$,

$$ (4) \qquad \sum_{\sigma \in S_{+r}} P_r(\sigma) v_r(\sigma, S) = C \sum_{\mathcal{N}_r} \Lambda_{\mathcal{N}_r}(S) e_r P_{\mathcal{N}_r}(S), $$

where C is a constant independent of S, C=1 if r belongs to an open subchain and $\{e_r\}$, r=1,2,..., MR is any solution of (3), then

$$ (5) \qquad \pi_r^r(S) = \xi_r^r(S) = \frac{\Lambda_{\mathcal{N}_r}(S) P_{\mathcal{N}_r}(S)}{\sum_{\sigma \in \mathcal{N}_r} \Lambda_{\mathcal{N}_r}(\sigma) P_{\mathcal{N}_r}(\sigma)} $$

**Proof.** The average number of customers who join class r and find state S per unit time, in the steady-state, is equal to

$$ (6) \qquad \Lambda_{\mathcal{N}_r}(S) P_{\mathcal{N}_r}(S) + \sum_{r' \in E_{\mathcal{N}_r}} \left\{ \left[ \sum_{\sigma \in S_{+r'}} P_r(\sigma) v_{r'}(\sigma, S) \right] P_{r'r} \right\}, $$

The first term in (6) counts the customers arriving from outside the network who find state S and join class r (that term is zero if $E_{\mathcal{N}_r}$ is closed); the second term includes all service completions in $E_{\mathcal{N}_r}$ after which a customer is directed to class r and sees state S. Substituting (4) into (6) and remembering that if $E_{\mathcal{N}_r}$ is open then $C=1$ and $\mathcal{N}$ coincides with $\mathcal{N}_r$, we rewrite (6) as
$$ (7) \qquad C \Lambda_{\ell_r}(S) P_{\ell_r-S} \left[ p_{\ell_r+S} + \sum_{r' \in E_{\ell_r}} e_{r'} p_{r'r} \right] = C \Lambda_{\ell_r}(S) P_{\ell_r-S} \delta_{\ell_r} $$

where we have used (3). The total average number of customers who join class r per unit time, in the steady-state, is obtained by summing (7) over all possible states S. Dividing the former average by the latter and canceling the common factor $C_{\ell_r}$, we obtain equation (5) for $\pi_{\ell_r}^r(S)$. To demonstrate the equation for $\xi_{\ell_r}^r(S)$ we note that the average number of class r customers who complete service and leave behind state S, per unit time, in the steady-state, is equal to

$$ \sum_{\sigma \in S_{+r}} P_{\sigma} \nu_{r}(\sigma, S) $$

which, according to (4), is equal to (7). From this point, the argument is the same as for $\pi_{\ell_r}^r(S)$. $\square$

Let us examine separately the cases when $E_{\ell_r}$ is open ($\ell_r-S = \ell_r$) and when it is closed ($\Lambda_{\ell_r} = 1$). The theorem states that, in networks which satisfy (4),

(i) All input (output) customers in open subchains see (leave behind) the same distribution of the network state as the customers arriving in those subchains from outside the network. In particular, if the external arrivals into a subchain $E_K$ are state-independent then they all see (leave behind) the steady-state distribution :

$$ (8) \qquad \pi_{\ell_r}^r(S) = \xi_{\ell_r}^r(S) = P_{\ell_r}(S) $$

for all $r \in E_{\ell_r}$, even though the external arrivals into other subchains may be state-dependent.

(ii) All input (output) customers in closed subchains see (leave behind) the steady-state distribution of a network with one less customer in those subchains :

$$ \pi_{\ell_r}^r(S) = \xi_{\ell_r}^r(S) = P_{\ell_r-S}(S), \quad r \in E_{\ell_r} \quad (E_{\ell_r} \text{ closed}). $$
Moreover, since the configurations $\mathcal{N}_{-r}$ and $\mathcal{N}_{r'}$ are identical if $r$ and $r'$ belong to the same subchain, the index $r$ in the right-hand side of the last equation may be replaced by any index $r'$ from the same subchain :

$$ (9) \qquad \pi_{cr}^r(S) = \xi_{cr}^r(S) = P_{\mathcal{N}_{-r}}(S), \quad r, r' \in E_{\mathcal{L}_r} \text{ (E$_{\mathcal{L}_r}$ closed)} $$

Thus, both in open and in closed subchains, the distribution of the system state seen by a customer is independent of which node he is entering (leaving) or what his current class is.

Going back to the original model formulation, with nodes (1,2,...,M) and classes (1,2,...,R), the network state distribution seen by a class $r$ input into node $m$ depends on whether the pair $(m,r)$ belongs to an open or a closed subchain. Different inputs to the same node may fall under category (i) or (ii), depending on their affiliation. A similar remark applies to outputs.

Note also that, if (5) is true in terms of a detailed network state $S$, it will obviously be true in terms of various aggregated states; in particular, (i) and (ii) apply to the marginal distributions of individual node states seen (left behind) by input (output) customers. Thus, for example, the distribution of sojourn times at a node in an open Jackson network can be obtained by isolating that node and treating it as an independent M/M/1 or M/M/c queue with the appropriate parameters.

A few words about the meaning of the sufficient condition (4) are in order. If $r$ is in an open subchain, $\sigma$ and $S$ are states of the same network; in that case (4) appears to equate the instantaneous rate at which state $S$ is entered due to class $r$ service completions, with the instantaneous rate at which $S$ is left due to class $r$ inputs. However, this is only an intuitive interpretation because the input process may not be Poisson. In the extremely special case of a network consisting of one open node without feedback, equations (4) are the local balance equations. In the case of closed subchains the situation is similar, but less intuitive because $\sigma$ and $S$ are states in different networks.
### 3. NETWORKS WHICH SATISFY THE SUFFICIENT CONDITION.

In this section we show that equation (4) holds for the large class of queueing networks with product form steady-state distributions defined by Baskett, Chandy, Muntz and Palacios [2].

The nodes of a BCMP network can be of four types, depending on the number of servers and the scheduling strategy employed. These are (1) single server FCFS (first-come-first-served), (2) single server PS (processor-sharing), (3) IS (infinitely many servers, or as many servers as there are customers) and (4) single server LCFSPR (last-come-first-served-preemptive-resume). The required service times at node types 2, 3 and 4 may have arbitrary Coxian distributions (distributions with rational Laplace transforms), with different parameters for the different customer classes; those at type 1 nodes must be exponentially distributed with the same parameter for all classes.

As before, we use a single index to denote the joint (node, class) status of a customer and we call it a class index. If a Coxian distribution is allowed for the required service times of class r customers, its parameters are $Q_r$ (number of stages), $A_{rj}$, $j=1,2,...,Q_r$ (the probability of reaching stage j; $A_{r1}=1$), $b_{rj}$, $j=1,2,...,Q_r$ (the probability of exiting after stage j; $b_{rQ_r}=1$) and $1/\mu_{rj}$, $j=1,2,...,Q_r$ (the mean of stage j); otherwise the mean of the exponential distribution is $1/\mu_r$ (and it is the same for all r whose node components are the same).

The network state is defined as the vector $S=(S_1,S_2,...,S_{MR})$ whose $r$'th element describes the state of the class r customers and depends on the type of node $m_r$: if that type is 2 or 3 then $S_r$ is the vector $(k_{r1},k_{r2},...,k_{rQ_r})$, where $k_{rj}$ is the number of class r customers in the $j$'th stage of their service ($k_r=k_{r1}+...+k_{rQ_r}$ is the total number of class r customers); if the node type is 1 then $S_r$ is the set of integers $\{h_1,h_2,...,h_{k_r}\}$ indicating the position of each class r customer in the corresponding FCFS queue; if the node type is 4 then $S_r$ is the set of pairs $\{(h_1,j_1),(h_2,j_2),..., (h_k,j_k)\}$ indicating, for each class r customer, his position in the LCFS queue and his stage of service.
Baskett et alia have shown that the stationary distribution (when it exists) of state S in network configuration $c^r$ is given by (we have reorganised the expression to conform with present notation)

$$ (10) \qquad P_r(S) = \frac{1}{G_r^r} d(S) \prod_{m=1}^{M} q_m(n_m) \prod_{r=1}^{MR} [e_r^r f_r(S_r)] \quad \forall S \text{ feasible in } \mathcal{D} $$

where

$G_r$ is a normalisation constant chosen so that (10) is a distribution;

$$ d(S) = \begin{cases} 1 & \text{if there are no external arrivals} \\ \left( \frac{N_0(S)-1}{i=0} \right) \lambda(i) & \text{if there are external arrival of type (a)} \\ \left( \frac{D}{\ell=1} + \frac{c_\ell(S)-1}{i=0} \right) \lambda_\ell(i) & \text{if there are external arrivals of type (b),} \end{cases} $$

$n_m$ is the number of customers at node m;

$q_m(i) = \begin{cases} i! & \text{if node } m \text{ is of type } 2, \\ 1 & \text{otherwise;} \end{cases}$

$f_r(S_r) = \begin{cases} (1/\mu_r)^{kr} & \text{if node } m_r \text{ is of type } 1, \\ \left( \prod_{j=1}^{Q_r} [(A_{rj}/\mu_{rj})^{kr_j}/k_{rj}!] \right) & \text{if node } m_r \text{ is of type } 2 \text{ or } 3, \\ \left( \prod_{i=1}^{kr} (A_{rj_i}/\mu_{rj_i}) \right) & \text{if node } m_r \text{ is of type } 4. \end{cases}$

The network configuration is reflected in (10) only through the set of feasible states and hence through the normalisation constant $G_r$.

If follows from (10) that if a state $\sigma$ differs from the state S by the presence of an additional class r customer, then the relation between $P_r(\sigma)$ and $P_{\sigma-r}(S)$ is, depending on the type of node $m_r$,
$$ (11) \qquad P_{\mathcal{N}}(\sigma) = \frac{G_{\mathcal{N}-r}}{G_{\mathcal{N}}} P_{\mathcal{N}-r}(S) \Lambda_{\ell_r}(S) e_r g(r) $$

where

$$ g(r) = \begin{cases} 1/\mu_r & \text{if type 1,} \\ [(n_m+1)/(k_{rj+1})](A_{rj}/\mu_{rj}) & \text{if type 2,} \\ (A_{rj}/\mu_{rj})/(k_{rj+1}) & \text{if type 3,} \\ (A_{rj}/\mu_{rj}) & \text{if type 4.} \end{cases} $$

and where j is the stage of service reached by the extra customer. The rate of class r service completion in state σ such that state S remains behind, $v_r(\sigma,S)$, may depend on the type of node $m_r$, on the stage of service j reached by the extra class r customer and on his position h in the corresponding queue :

$$ (12) \qquad \begin{aligned} \text{type 1, } v_r(\sigma,S) &= \begin{cases} \mu_r & \text{if } h=1 \\ 0 & \text{otherwise} \end{cases} \\ \text{type 2, } v_r(\sigma,S) &= \frac{\mu_{rj} b_{rj}(k_{rj}+1)}{n_m+1} \\ \text{type 3, } v_r(\sigma,S) &= \mu_{rj} b_{rj}(k_{rj}+1) \\ \text{type 4, } v_r(\sigma,S) &= \begin{cases} \mu_{rj} b_{rj} & \text{if } h=1 \\ 0 & \text{otherwise} \end{cases} \end{aligned} $$

Combining (11) and (12), and bearing in mind that, for all r,

$$ \sum_{j=1}^{Q_r} A_{rj} b_{rj} = 1, $$

we find

$$ \sum_{\sigma \in S_{+r}} P_{\mathcal{N}}(\sigma) v_r(\sigma, S) = \frac{G_{\mathcal{N}-r}}{G_{\mathcal{N}}} \Lambda_{\ell_r}(S) e_r P_{\mathcal{N}-r}(S). $$

This completes the verification of (4) for these networks, since $G_{\mathcal{N}-r}/G_{\mathcal{N}}$ is independent of S and is equal to 1 if $E_{\ell_r}$ is open.
Although there is a certain freedom in choosing the values of $e_r$ in closed subchains, the quantity $e_r G_{\mathcal{J}_r^-} / G_{\mathcal{J}r}$ is independent of that choice. That quantity is, in fact, equal to the actual throughput for class r in configuration $\mathcal{N}$ (provided that arrivals into open chains of the same network are state-independent).

The definition of BCMP networks includes also the possibility of state-dependent service rates at either individual nodes or subsets of nodes. The rate of service for class r customers may depend on $k_r$ (except at type 1 nodes) and/or on $n_m$ and/or on $\Sigma n_m$ over a certain subset of nodes (but if there is a dependency on $n_m$ or on $\Sigma n_m$, it applies to all other classes at that node or nodes). These dependencies are reflected in the product form (10) as factor terms (see [2]). It is a routine task to show that (4) continues to hold.

Thus the theorem of section 2 applies to all BCMP networks.

For closed subchains, the theorem expresses the input and output instant probabilities $\pi_{\mathcal{J}r}^r(S)$ and $\xi_{\mathcal{J}r}^r(S)$ in terms of the steady-state distribution of network configuration $\mathcal{J}_r^-$. It may be desirable to have also an expression in terms of the distribution of network $\mathcal{N}$. Such an expression is provided by the sufficient condition (4). Substituting (4) into (9) gives, for closed subchains,

$$ (13) \qquad \pi_{\mathcal{J}r}^r(S) = \xi_{\mathcal{J}r}^r(S) = \left[ \sum_{\sigma \in S_{+r'}} P_{\mathcal{J}r}(\sigma) \nu_{r'}(\sigma, S) \right] / (C_{e_{r'}}) $$

where $r'$ is any customer class in the same subchain as r; $C_{e_{r'}}$ is the throughput for class r'. If $r'$ happens to have exponentially distributed required service times (with mean $1/\mu_{r'}$) and if the service rate for $r'$ is state-independent, we can simplify (13) :

$$ (14) \qquad \pi_{\mathcal{J}r}^r(S) = \xi_{\mathcal{J}r}^r(S) = P_{\mathcal{J}r}(S^*) / \rho_{r'} $$

where $S^*$ is the single element of the set $S_{+r'}$, in which the extra class r' customer is being served, and $\rho_{r'} = C_{e_{r'}} / \mu_{r'}$ is the utilisation of class r'. The right-hand side of (14) is the conditional probability of the state $S^*$, given that an r' customer is in service. Equation (14) is a generalisation of the results mentioned in the introduction.
Similar results can be obtained for the state distributions *just after* input instants or *just before* output instants. For example, the probability that the network is in state S just after a customer joins class r, for a node with state independent service rate and exponential service times for class r, is equal to $P_m(S)/\rho_r$.

### 4. EXTENSION TO OTHER NETWORKS.

The class of networks known to have product form has been expanded recently with respect to permissible service disciplines and service requirement distributions. The mathematical (but not practical) limitation that service time distributions must have rational Laplace transforms can be relaxed to allow general absolutely continuous distributions with finite means [1,4,5]. A parameterized family of servicing disciplines can be defined, which includes the four disciplines listed in the last section as special cases [4,5,13].

Our sufficient condition of section 2 is also satisfied by these move general networks. Both Chandy, et al. and Kelly view each queue as having "stations". In general, customers arrive into, receive service in and depart from any station in the queue. A queueing discipline is defined in terms of how an arriving customer selects a station (forcing other customers to move back one position) and what proportion of the server's attention is devoted to each station in each state of the queue. Let $R_m(n_m)$ be the total rate at which service is provided at node m when there are $n_m$ customers there. Then the queue discipline is "exponential local balancing" if there is function $q_m(\cdot)$ such that $R_m(n_m) = \frac{q_m(n_m-1)}{q_m(n_m)}$. Further, an exponential local balancing discipline is "station balancing" if the probability that an arriving customer picks a particular station is equal to the proportion of the server's attention devoted to that station in each possible state of the queue. (The disciplines LCFSPR, PS and IS are station balancing, while FCFS is not).

The system state is defined by the class and remaining service time of the customer at each station of each queue. Whenever all service disciplines are exponential local balancing and, at all nodes, either the discipline is station balancing, or the service requirements for all classes are
distributed exponentially with the same mean, the equilibrium state probability density function is given by :

$$ (15) \qquad P_{cr}(S) = \frac{\lambda^{N(S)}}{G_r} \left[ \prod_{m=1}^{M} q_m(n_m) \right] \left[ \prod_{r=1}^{R} e_r^{k_r} \prod_{i=1}^{k_r} (1-F_r(W_{ir})) \right] $$

where $\lambda$ is total (load-independent) arrival rate,

$F_r(\cdot)$ is the distribution function for class r's service requirement, and $W_{ir}$ is the remaining service time of the ith class r job.

The probability density function of state $\sigma$ (which has one more class r customer about to complete service) is related to that of state S as follows :

$$ (16) \qquad P_{cr}(\sigma) = P_{cr-r}(S) \frac{q_m(n_m+1)}{q_m(n_m)} \frac{G_{cr-r}}{G_{cr}} \Lambda_{\ell_r}(S) e_r(1-F_r(0^+)) . $$

Since the extra class r customer could be in any position of the queue, and since $P_{cr}(\sigma)$ is the same for all $\sigma \in S_{+r}$, we have

$$ \sum_{\sigma \in S_{+r}} P_{cr}(\sigma) v_r(\sigma, S) = R_m(n_m+1) P_{cr}(S^*) = \frac{q_m(n_m)}{q_m(n_m+1)} P_{cr}(S^*) $$

where $S^*$ is any state in $S_{+r}$.

Observing that $F_r(0^+) = 0$ and using (16) for $P_{cr}(S^*)$ yields :

$$ \sum_{\sigma \in S_{+r}} P_{cr}(\sigma) v_r(\sigma, S) = \Lambda_{\ell_r}(S) \frac{G_{cr-r}}{G_{cr}} e_r P_{cr}(S) $$

which is the sufficient condition of section 2.

Thus, if $\pi_{cr}^r(S)$ and $\xi_{cr}^r(S)$ are interpreted as probability density functions rather than probabilities, equations (8) and (9) continue to hold. We make this statement without claiming to have proved it rigorously, since the counting argument of section 1 needs to be generalised in order to cover the case when the quantities involved are infinitesimal.
The product form of the equilibrium state probabilities is retained in certain cases where the routing of customers is not represented as simple transition matrix. Kelly [14] considers the case in which each customer has a specific route which he follows through the network. Kobayashi and Reiser [15] allow the transitions among service centers to be governed by a Markov process of arbitrary (finite) order. The technique used in both cases is to introduce additional "artificial" classes (typically a lot of them) in order to retain more information about the past or future path of the customer. Then, in terms of the enlarged set of classes, all transitions among service centers and non-artificial classes can be represented by a simple transition matrix (or first order Markov process). The theorems of section 2 apply to the detailed states involving the artificial classes, so we only have to aggregate states by eliminating the distinctions among the artificial classes that correspond to an actual class in order to see that the theorems of section 2 apply also to models with these more general routing patterns.

The product form of the equilibrium probability distribution is also retained when constraints on the customer populations in various subchains is more general than having each chain contain either a constant (closed) or an unlimited (open) number of customers. Lam [16] studies "loss" and "trigger" functions for each customer class based on the number of customers currently in each chain. His work is a generalization of the ideas used by Jackson to unify open and closed networks [12], and by Reiser and Kobayashi to create "semi-closed" subchains, in which the number of customers is allowed to vary between minimum and maximum values, but independently of the populations in other subchains [19].

Lam proves a sufficient condition for the equilibrium state probabilities to retain the same product form as for the networks described by Baskett et al. [2]. Let $T_\ell(\sigma)$ be the "trigger" function whose value is zero if the departure of a chain $\ell$ customer in state $\sigma$ triggers the arrival of a new chain $\ell$ customer, and is one otherwise. Similarly, let $L_\ell(S)$ be the "loss" function whose value is zero if chain $\ell$ arrivals in state $S$ are lost and is one otherwise. Then Lam's sufficient condition is

$$T_{\ell r}(\sigma) = L_{\ell r}(S) \quad \text{for all } r \text{ and } \sigma \in S_{+r}$$
Thus, an arrival is triggered to stop a change in subchain population if and only if arrivals that would cause the reverse change are lost. Because systems with loss and trigger functions satisfying the above equation have the same product form solution discussed in section 4, they satisfy the sufficient condition of the theorem in section 2. However, the expression (6) indicating the rate with which class r customers find state S must be modified to include the trigger functions :

$$ (17) \Lambda_{\ell_r}^{(S)} L_{\ell_r}^{(S)} p_{or} p_{r-r}^{(S)} + \sum_{r' \in E_{\ell_r}} \left\{ \left[ \sum_{\sigma \in S_{+r'}} p_{\sigma r}(\sigma) v_{r}(\sigma, S) \right] \left[ p_{r,r'} + p_{r',o} (1 - T_{\ell_r}(\sigma)) p_{or} \right] \right\} $$

When $L_{\ell_r}^{(S)}=1$, $T_{\ell_r}^{(\sigma)}=1$ because r and r' are in the same subchain and the expression reduces directly to that examined in the proof in section 2. When $L_{\ell_r}^{(S)} = T_{\ell_r}^{(\sigma)}=0$ the expression above again reduces to

$$ \Lambda_{\ell_r}^{(S)} p_{\ell_r-r}^{(S)} \frac{G_{\ell_r} e_r}{G_{\ell_r} e_r} $$

after some algebraic manipulation and use of the identity

$$ \sum_{r_1 \in E_j} (1 - \sum_{r_2 \in E_j} p_{r_1 r_2}) e_{r_1} = 1 $$

Thus if the loss and trigger functions satisfy Lam's sufficient condition for a product form solution to exist, then the theorem of section2 remains applicable (although its proof must be generalised as above).

## 5. CONCLUSIONS.

We have considered queueing networks with multiple customer classes, Markov routing chains of arbitrary order, state dependent arrival and service rates, general service time distributions at service centers with station balancing disciplines, and general constraints on the populations of the routing chains. The presence of even a single feedback loop is such networks causes the input processes at nodes to be non-Poisson and, in general, non-renewal. Yet we have found that these networks with product form equilibrium state distributions have input and output instant distributions related simply
to the equilibrium distribution of the same network but with the population
constraints (if any) on one chain decreased by one customer. Thus, with ne-
gligible additional computation, existing algorithms for calculating the
equilibrium state probabilities can also calculate the distribution at ins-
tants just before inputs or arrivals or just after outputs or departures.

Among networks with equilibrium distributions that do not have pro-
duct form, the simple relationships between input instant and equilibrium
distributions seem to be retained only in very special cases. The M/Er-2/1
FCFS queue with feedback is perhaps the simplest network without product
form equilibrium probabilities. In this case, the input instant and the
steady-state distributions are not the same because fed-back customers never
see the second service stage busy, while the equilibrium utilisations of the
two stages are equál. However, if we consider aggregate states, n, defined
as the number of customers at the service center, then for an FCFS M/G/1
queue with feedback, the distributions of n at input instants and in equi-
librium are the same. This can be shown by modifying the approach in [9]
so that fed-back customers do not see themselves.

However, in a two node closed network where the service requirement
distribution is highly skewed, the distribution of n at input instants is
not the same as the equilibrium distribution of n in the same closed network
with one less customer. We conjecture that (8) and (9) fail to hold in any
network where a FCFS non-exponential node contributes to the input of another
node.

REFERENCES

1. Barbour, A.D., Networks of Queues and the Method of Stages.  
   *Advanced Applied Probability* 8, 3 (September 1976), 584-91.

2. Baskett, F., Chandy, K.M., Muntz, R.R., and Palacios, F.G.,
   Open, closed and mixed networks of queues with different
classes of customers.
   *JACM* 22, 2 (April 1975), 248-60.

3. Burke, P.J., Proof of a conjecture on the interarrival-time distribution in an M/M/1 queue with feedback.
   *IEEE-TC* 24, 5 (May, 1976), 575-76.
4. Chandy, K.M., Howard, J.H., and Towsley, D.F., Product form and local balance in queueing networks. JACM 24, 2 (April 1977), 250-63.

5. Chandy, K.M., Recent work in preparation.

6. Cooper, R.B., Introduction to queueing theory. MacMillan Publ. Co., New York (1972).

7. Cox, D.R., A use of complex probabilities in the theory of stochastic processes. Proc. Cambridge Phil. Soc. 51 (1955), 313-19.

8. Disney, R.L., Random flow in queueing networks : a review and critique. AIIE Transactions 7, 3 (September 1975) 268-88.

9. Disney, R.L. and McNickle, D.C., The M/G/1 queue with instantaneous Bernoulli feedback. Rep. 77-4, Dept. of Ind. and Oper. Eng., University of Michigan, Ann Arbor (April 1977).

10. Gordon, W.J., and Newell, G.F., Closed queueing systems with exponential servers. Op. Res., 15 (1967), 254-65.

11. Jackson, J.R., Networks of waiting lines. Op. Res. 5, (1957), 518-21.

12. Jackson, J.R., Jobshop-like queueing systems. Mgmt. Sci. 10, 1 (October 1963), 131-42.

13. Kelly, F.P., Networks of queues with customers of different classes. J. Appl. Prob. 12 (1975), 542-54.

14. Kelly, F.P., Networks of queues, Adv. Appl. Prob. 8, 2 (June 1976), 416-32.

15. Kobayashi, H. and Reiser, M., On generalization of job routing behavior in a queueing network model. IBM research report RC5252, Yorktown Heights, (February 1975).

16. Lam, S.S., Queueing networks with population size constraints. IBM J. R. & D. 21, 4 (July 1977), 370-78.

17. Lemoine, A.J., Networks of queues - a survey of equilibrium results. Mgmt. Sci. 24, 4 (December 1978), 464-81.

18. Mitrani, I., Non priority multiprogramming systems under heavy demand conditions - customers viewpoint. JACM 19, 3 (July 1972), 445-452.

19. Reiser, M. and Kobayashi, H., Numerical solution of semi-closed exponential server queueing networks. Proc. 7th Asilomar Conf. (1973), 308-12.