On Two Interacting Markovian Queueing Systems

Abstract

In this paper, we study a Markovian queuing system consisting of two subsystems of an arbitrary structure. Each subsystem generates a multi-class Markovian arrival process of customers arriving to the other subsystem. We derive the necessary and sufficient conditions for the stationary distribution to be of product form and consider some particular cases of the subsystem interaction for which these conditions can be easily verified.

1. Introduction

The product form of the stationary distribution greatly simplifies the analysis of complex queueing systems. In such systems, the stationary distribution of the network can be written as the product of the distributions of its nodes with the arrival rates modified to reflect the routing of customers in the network. Jackson [1] showed that a specific class of open queueing networks has a product-form stationary distribution. Gordon and Newell [2] introduced product-form Markovian models for closed queueing networks. Kobayashi [3] and Towsley [4] developed forms of state-dependent routing in a queueing network, allowing a product-form solution. Baskett et al. [5] found product-form solutions for open, closed or mixed queueing networks with multiple classes of customers and various service disciplines and service time distributions. Surveys by Disney and König [6], Nelson [7] and Balsamo [8], as well as books by Kelly [9], Ross [10], Whittle [11] and Walrand [12] cover various aspects of product-form solutions for conventional queueing networks.

Gelenbe [13,14] proposed models of a queueing network with positive and negative customers: the G-networks. These models, which include G-networks with signals [15], resets [16], and multiple customer classes [17], radically extend the class of Markovian queueing systems with the product-form stationary distributions. The complexity of such systems continues to increase, with the introduction of new extensions of G-networks being an essential area of research [18,19].

In conventional queueing networks, each node in isolation can be represented by a birth and death process. Nodes in a Markov network [20] are Markovian queueing systems whose behavior can be represented by general discrete-state Markov processes. The details of the nodes’ internal structure can be ignored. Each node of a Markov network can have three types of state changes: arrival, departure and internal transitions, which are distinguished only by the rates or probabilities at which they occur. A transition of the network as a whole involves changes at only one or two nodes. The former case corresponds to a network transition consisting of an internal change at one node. The latter consists of a departure transition at one node that triggers an arrival transition at another node determined by a routing probability.

Naumov [21] obtained the necessary and sufficient conditions for a product-form solution for a Markov network consisting of two nodes, the first of which generates a Markovian arrival process (MAP) of customers arriving to the second node. Chao et al. [20] obtained the necessary and sufficient conditions for a general Markov network to be of product form. Chao and Miyazawa [22] extended the notion of quasi-reversibility to Markov networks and applied it to the study of networks with triggered movements and positive and negative signals. In [23], Chao provided an overview of product-form Markov networks.

The procedure for establishing the existence of a product-form stationary distribution for Markov networks includes a solution of a system of nonlinear equations [20]. The objective of this paper is to simplify this procedure for some Markov networks so that it can be easily applied in practice. We consider two-node Markov networks and multi-class Markovian arrival processes (MMAP). In Section 2, we formulate the basic properties of MMAP. In Section 3, we derive a matrix formulation of the product-form conditions and develop a simple procedure to check whether a Markov network with two customer classes is of product form. Examples given in Section 4 illustrate the theory developed in the paper.

The following notation conventions are used throughout the article. Bold lowercase letters denote vectors and bold capitalized letters denote matrices. Inequality $x\le y$ represents $x_m\le y_m$ for all vectors $x$ and $y$; $\delta (i,j)=1$ if $i=j$ and $\delta (i,j)=0$ otherwise; $I=[\delta (i,j)]$ denotes the identity matrix; $u$ is the column vector of all ones; the i-th component of vector $e_i$ is equal to one, and the others are equal to zero.

2. Multi-Class Markovian Arrival Process

Consider a multi-class arrival process $\mathcal{T}=(({\tau }_n,{\sigma }_n),n=1,2,\dots )$, where $0\le {\tau }_1\le {\tau }_2\le \dots$ are the arrival times and ${\sigma }_n\in \{1,2,\dots ,k\}$ is the class of the n-th customer. Denote $N_v(t)={\displaystyle \sum _{{\tau }_n\le t}\delta (v,{\sigma }_n)}$ the number of class $v$ customers arrived during time t and $N(t)=(N_1(t),N_2(t),\dots ,N_k(t))$. The process $\mathcal{T}$ is a MMAP if for some random process $X(t)$ with a finite set of states $\mathcal{X}$ the process $(X(t),N(t))$ is a homogeneous Markov process and the following conditions are satisfied:

$$\begin{array}{c}\mathbb{P}\{X(t+\epsilon )=j,{\displaystyle \sum _{v=1}^k{N}_v(t+\epsilon )}>{\displaystyle \sum _{v=1}^k{n}_v}+1|X(t)=i,N(t)=n\}=o(\epsilon ),\\ \mathbb{P}\{X(t+\epsilon )=j,N(t+\epsilon )=n|X(t)=i,N(t)=n\}=\delta (i,j)+A_0(i,j)+o(\epsilon ),\\ \mathbb{P}\{X(t+\epsilon )=j,N(t+\epsilon )=n+e_v|X(t)=i,N(t)=n\}=A_v(i,j)+o(\epsilon ),v=1,2,\dots ,k,\end{array}$$

(1)

for all $i,j\in \mathcal{X}$, $t,\epsilon >0$, and for all nonnegative integer vectors $n$ of length k [24]. In this case, the probability of more than one arrival in the interval of length $\epsilon$ is $o(\epsilon )$ and the process $(X(t),N(t))$ is a Markov process that is homogeneous in time and in the second component [25]. That is, for all $0\le k\le n$, $i,j\in \mathcal{X}$ and $s,t\ge 0$ we have:

$$\mathbb{P}\{X(s+t)=j,N(s+t)=n|X(s)=i,N(s)=k\}=p_{i,j}(n-k,t).$$

The phase process $X(t)$ is a time-homogeneous Markov chain with a matrix of transition probabilities:

$$P(t)={\displaystyle \sum _{n\ge 0}P(n,t)},$$

where $P(n,t)=[p_{i,j}(n,t)]$ [25]. It follows from (1) that matrices $A_v=[A_v(i,j)]$, $i,j\in \mathcal{X}$, $v=0,1,\dots ,k$, which characterize MMAP, have the following properties [26,27]:

• Matrix $A_0$ has non-negative off-diagonal elements.
• Matrices $A_v$, $v=1,2,\dots ,k,$ are non-negative.
• The matrix

  $$A={\displaystyle \sum _{v=0}^k{A}_v}$$

  (2)

  is the generator of the phase process.

Transition probability matrices $P(n,t)$ can be calculated by the recursion [27]

$$P(0,t)=e^{A_{0}t},P(n,t)={\displaystyle \sum _{\begin{array}{c}v=1\\ n_v>0\end{array}}^k{\displaystyle \underset{0}{\overset{t}{\int }}P(0,t-x)}{A}_{v}P(n-e_v,x)dx},n\ne 0.$$

If matrices $P(n,t)$ are known, the joint probability distribution of the number of arrivals in disjoint intervals can be calculated as:

$$\begin{array}{c}\mathbb{P}\{N({\displaystyle \sum _{j=0}^r{t}_j})-N({\displaystyle \sum _{j=0}^{r-1}{t}_j})=k_r,r=1,2,\dots ,m\}=qP(t_0)P(k_1,t_1)P(k_2,t_2)\dots P(k_m,t_m)u,\\ k_1,k_2,\dots ,k_m\ge 0,t_0,t_1,\dots ,t_m>0,m=1,2,\dots \end{array}$$

where $q=[q_i]$ is a row vector of the initial probability distribution of the phase process, $q_i=\mathbb{P}\{X(0)=i\}$.

Consider the MAP of class v customers. It is characterized by transition probability matrices

$$P_{v,m}(t)={\displaystyle \sum _{\begin{array}{c}n\ge 0\\ n_v=m\end{array}}P(n,t)},k=0,1,\dots ,$$

which satisfy the following recursion:

$$P_{v,0}(t)=e^{(A-A_v)t},P_{v,n}(t)={\displaystyle \underset{0}{\overset{t}{\int }}{P}_{v,0}(t-x)}{A}_v{P}_{v,n-1}(x)dx,n>0.$$

(3)

The joint probability distribution of the number of class $v$ arrivals in disjoint intervals can be calculated as:

$$\begin{array}{c}\mathbb{P}\{N_v({\displaystyle \sum _{j=0}^r{t}_j})-N_v({\displaystyle \sum _{j=0}^{r-1}{t}_j})=k_r,r=1,2,\dots ,m\}=qP(t_0)P_{v,k_1}(t_1)P_{v,k_2}(t_2)\dots P_{v,k_m}(t_m))u,\\ k_1,k_2,\dots ,k_m\ge 0,t_0,t_1,\dots ,t_m>0,m=1,2,\dots .\end{array}$$

(4)

If $q$ is the stationary vector of $A$ and satisfies $q{A}_v=a_{v}q$, it follows from (3) that

$$q{P}_{v,n}(t)=e^{-a_{v}t}\frac{{(a_{v}t)}^n}{n!}q,n\ge 0.$$

It follows from (4) that, in this case, the arrival process of class $v$ customers is Poisson with rate $a_v=q{A}_{v}u$. Similarly, if matrix $A_v$ satisfies $A_{v}u=a_{v}u$, it follows from (3) that

$$P_{v,n}(t)u=e^{-a_{v}t}\frac{{(a_{v}t)}^n}{n!}u,n\ge 0,$$

and the arrival process of class $v$ customers is Poisson with rate $a_v=q{A}_{v}u$ (see also [28]). We next show that the property $q{A}_v=a_{v}q$ is important for the existence of product-form distribution, in contrast to the property $A_{v}u=a_{v}u$, although in both cases the arrival processes are Poisson.

3. Interacting Markovian Queueing Systems

We consider a Markov network with two nodes having state spaces $\mathcal{X}$ and $\mathcal{Y}$. The first node generates MMAP defined by non-zero matrices ${\Lambda }_v=[{\Lambda }_v(i,j)]$, $i,j\in \mathcal{X}$, $v=0,1,\dots ,n$, and the second node generates MMAP defined by non-zero matrices ${{\rm M}}_w=[{{\rm M}}_w(k,r)]$, $k,r\in \mathcal{Y}$, $w=0,1,\dots ,m$. If the nodes are operated in isolation, the first node could be represented by a homogeneous Markov process with a generator:

$$\Lambda ={\displaystyle \sum _{v=0}^n{\Lambda }_v}.$$

(5)

Also, the second could be represented by a homogeneous Markov process with a generator:

$${\rm M}={\displaystyle \sum _{w=0}^m{{\rm M}}_w}.$$

(6)

When a class $v$ customer arrives from the first node to the second, the state of the second node changes according to a stochastic matrix $Q_v=[Q_v(k,r)]$, $k,r\in \mathcal{Y}$, $v=1,2,\dots ,n$. When a class $w$ customer arrives from the second node to the first, the state of the first node changes according to a stochastic matrix $P_w=[P_w(i,j)]$, $i,j\in \mathcal{X}$, $w=1,2,\dots ,m$. The behavior of the system can be represented by a homogeneous Markov process $Z(t)=(X(t),Y(t))$, with the finite state space $\mathcal{Z}=\mathcal{X}\times \mathcal{Y}$ and the generator

$$\Theta ={\Lambda }_0\otimes I+{\displaystyle \sum _{v=1}^n{\Lambda }_v}\otimes Q_v+{\displaystyle \sum _{w=1}^m{P}_w}\otimes {{\rm M}}_w+I\otimes {{\rm M}}_0,$$

(7)

where $\otimes$ denotes the Kronecker product.

Further, we assume that the generator $\Theta$ is irreducible. Therefore, the stationary distribution $\pi (i,k)$, $i\in \mathcal{X}$, $k\in \mathcal{Y}$, of the process $Z(t)$ is the unique solution to the system of the following steady-state equations:

$$\begin{array}{c}{\displaystyle \sum _{i\in \mathcal{X}}\pi (i,r){\Lambda }_0(i,j)}+{\displaystyle \sum _{v=1}^n{\displaystyle \sum _{i\in \mathcal{X}}{\displaystyle \sum _{k\in \mathcal{Y}}\pi (i,k)}{\Lambda }_v(i,j)}}{Q}_v(k,r)+\\ +{\displaystyle \sum _{w=1}^m{\displaystyle \sum _{i\in \mathcal{X}}{\displaystyle \sum _{k\in \mathcal{Y}}\pi (i,k)}{P}_w(i,j)}}{{\rm M}}_w(k,r)+{\displaystyle \sum _{k\in \mathcal{Y}}\pi (j,k){{\rm M}}_0(k,r)}=0,j\in \mathcal{X},r\in \mathcal{Y}\end{array}$$

(8)

which satisfy the normalizing condition:

$${\displaystyle \sum _{i\in \mathcal{X}}{\displaystyle \sum _{k\in \mathcal{Y}}\pi (i,k)}=1.}$$

(9)

We next derive the conditions under which the stationary distribution has the product form:

$$\pi (i,k)=p(i)q(k),r\in \mathcal{X},k\in \mathcal{Y}$$

(10)

First, however, we need the following auxiliary result.

Theorem 1.

The generators

$$\mathbf{L}=\Lambda +{\displaystyle \sum _{w=1}^m{\mu }_w(P_w}-I),$$

(11)

$$\mathbf{M}=M+{\displaystyle \sum _{v=1}^n{\lambda }_v(Q_v}-I)$$

(12)

are irreducible for any ${\lambda }_v>0$,$v=1,2,\dots ,n$, and${\mu }_w>0$,$w=1,2,\dots ,m$.

Note that matrix $\mathbf{L}$ is the generator of a Markov process representing the behavior of the first node with a multi-class Poisson arrival process with rates ${\mu }_w$, $w=1,2,\dots ,m.$ Matrix $\mathbf{M}$ is the generator of a Markov process representing the behavior of the second node with a multi-class Poisson arrival process with rates ${\lambda }_v$, $v=1,2,\dots ,n$. Therefore, Theorem 1 states that if the MMAP arriving to each network node is replaced by a multi-class Poisson arrival process, then the generators of the Markov processes representing each node in isolation are irreducible.

Theorem 2.

For the stationary distribution of the process$Z(t)$to have the product form (10), it is necessary and sufficient that vectors$p=[p(i)]$and$q=[q(k)]$satisfy the following equations:

$$p(\Lambda +{\displaystyle \sum _{w=1}^m{\mu }_w(P_w}-I))=0,pu=1,$$

(13)

$$q(M+{\displaystyle \sum _{v=1}^n{\lambda }_v(Q_v}-I))=0,qu=1,$$

(14)

$${\displaystyle \sum _{v=1}^{n}p({\Lambda }_v-{\lambda }_{v}I)\otimes q(Q_v-I)}+{\displaystyle \sum _{w=1}^{m}p(P_w-I)\otimes q({{\rm M}}_w-{\mu }_{w}I)}=0,$$

(15)

$${\lambda }_v=p{\Lambda }_{v}u,v=1,2,\dots ,n,{\mu }_w=q{{\rm M}}_{w}u,w=1,2,\dots ,m.$$

(16)

Hence, components $p$ and $q$ of the product form (10) can be found as the stationary distributions of the nodes with Poisson arrival processes. However, this is not an easy task because the systems of Equations (13) and (14) must be solved together with the conditions (16), and therefore the problem of finding vectors $p$ and $q$ that satisfy the conditions of the theorem is nonlinear. In the next section, we consider particular cases for which this problem can be simplified. The proofs of Theorems 1 and 2 are provided in Appendix A.

Corollary 1.

Let$n=1$,$m=0$, vector$p$be the solution of equations$p\Lambda =0$,$pu=1$, and vector$q$be the solution of equations$q(M+{\lambda }_1(Q_1-I))=0$,$qu=1$, where${\lambda }_1=p{\Lambda }_{1}u$. Then, for the product form of the stationary distribution of the process$Z(t)$, it is necessary and sufficient that either$p{\Lambda }_1={\lambda }_{1}p$or$q{Q}_1=q$.

Proof. 

Indeed, according to Theorem 2, for the product-form stationary distribution $\pi =(\pi (i,k)),$ it is required that for any $j\in \mathcal{X},r\in \mathcal{Y}$

$$\left({\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)-{\lambda }_{1}p(j)}\right)\left({\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r)-q(r)}\right)=0,$$

which is equivalent to either $p{\Lambda }_1={\lambda }_{1}p$ or $q{Q}_1=q$.

It was shown in Section 2 that if the condition $p{\Lambda }_1={\lambda }_{1}p$ is fulfilled, then, in the stationary mode, the MAP generated by the first node is Poisson with rate ${\lambda }_1$ (see also [9,23]). Because of the PASTA property (Poisson Arrivals See Time Averages) of the Poisson process, the stationary distribution of the second node is equal to the stationary distribution of the Markov chain embedded at times before the customer arrivals. However, then vector $q{Q}_1$ is the stationary distribution of the Markov chain embedded at times after the customer arrivals. Thus, the condition $q{Q}_1=q$ implies that, for the second node with Poisson arrivals, the Markov chains embedded before and after customer arrivals have the same stationary distributions. □

Corollary 2.

Let$n=1$,$m=1$, vector$p$be the solution of equations$p(\Lambda +{\mu }_1(P_1-I))=0$,$pu=1$, where${\mu }_1=q{{\rm M}}_{1}u$, and vector$q$be the solution of equations$q(M+{\lambda }_1(Q_1-I))=0$,$qu=1$, where${\lambda }_1=p{\Lambda }_{1}u$. Then for the product-form stationary distribution of the process$Z(t)$, it is necessary and sufficient that at least one of the following conditions is satisfied:

$$p{\Lambda }_1={\lambda }_{1}pandp{P}_1=p,$$

(17)

$$p{\Lambda }_1={\lambda }_{1}pandq{{\rm M}}_1={\mu }_{1}q,$$

(18)

$$q{Q}_1=qandp{P}_1=p,$$

(19)

$$q{Q}_1=qandq{{\rm M}}_1={\mu }_{1}q.$$

(20)

There exists a constant$\psi \ne 0$such that

$${\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)-{\lambda }_{1}p(j)}=\psi ({\displaystyle \sum _{i\in \mathcal{X}}p(i)P_1(i,j)-p(j)})$$

(21)

for all $j\in \mathcal{X},$with${\displaystyle \sum _{i\in \mathcal{X}}p(i)P_1(i,j)\ne p(j)}$, and

$${\displaystyle \sum _{k\in \mathcal{Y}}q(k)M_1(k,r)-{\mu }_{1}q(r)}=\psi (q(r)-{\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r))}$$

(22)

for all$r\in \mathcal{Y}$with${\displaystyle \sum _{k\in \mathcal{Y}}}q(k)Q_1(k,r)\ne q(r)$.

Proof. 

According to Theorem 2, for the product-form stationary distribution $\pi =(\pi (i,k))$, it is required that for any $j\in \mathcal{x},r\in \mathcal{Y}$ the following holds:

$$\begin{array}{c}\left({\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)-{\lambda }_{1}p(j)}\right)\left({\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r)-q(r)}\right)+\\ +\left({\displaystyle \sum _{i\in \mathcal{X}}p(i)P_1(i,j)-p(j)}\right)\left({\displaystyle \sum _{k\in \mathcal{Y}}q(k){{\rm M}}_1(k,r)-{\mu }_{1}q(r)}\right)=0.\end{array}$$

(23)

The sufficiency of each of the five conditions given above for the product-form stationary distribution $\pi (i,k)$ is obvious. Let us prove that at least one of them is necessary for the stationary distribution to be of product form.

Suppose that the stationary distribution $\pi (i,k)$ has the product form. From (23), it follows that if one of the vectors $p{\Lambda }_1-{\lambda }_{1}p$, $q{{\rm M}}_1-{\mu }_{1}q$, $p{P}_1-p$, $q{Q}_1-q$ is a zero vector then there is another zero vector in this group such that one of the conditions (17)–(20) is fulfilled. It remains to consider the case when all these vectors are non-zero. Let ${\mathcal{X}}^{*}$ be a set of $j\in \mathcal{X}$ such that $p(j)\ne {\displaystyle \sum _{i\in \mathcal{X}}p(i)P_1(i,j)}$, and let ${\mathcal{Y}}^{*}$ be a set of $r\in \mathcal{Y}$ such that $q(r)\ne {\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r)}$. Then, the following holds for all $j\in {\mathcal{X}}^{*}$ and $r\in {\mathcal{Y}}^{*}$:

$$\frac{{\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)-{\lambda }_{1}p(j)}}{{\displaystyle \sum _{i\in \mathcal{X}}p(i)P_1(i,j)-p(j)}}=\frac{{\displaystyle \sum _{k\in \mathcal{Y}}q(k){{\rm M}}_1(k,r)-{\mu }_{1}q(r)}}{q(r)-{\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r)}}.$$

(24)

Since the left-hand side of this equation does not depend on r, and the right-hand side does not depend on j, then for $j\in {\mathcal{X}}^{*}$ and $r\in {\mathcal{Y}}^{*}$ they are both equal to some constant $\psi$ and therefore (21) and (22) are satisfied. Since vectors $q{{\rm M}}_1-{\mu }_{1}q$ and $q{Q}_1-q$ are non-zero, it follows from (24) that for each $j\in \mathcal{X}$ the relationships ${\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)={\lambda }_{1}p(j)}$ and ${\displaystyle \sum _{i\in \mathcal{X}}p(i)P_1(i,j)=p(j)}$ are both true or both false. Then, ${\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)\ne {\lambda }_{1}p(j)}$ for all $j\in {\mathcal{X}}^{*}$ in (21), and therefore $\psi \ne 0$.□

The proof of the following Corollary 3 is similar to the proof of Corollary 2.

Corollary 3.

Let$n=2$,$m=0$, vector$p$be the solution of the linear system$p\Lambda =0$,$pu=1$, and vector$q$be the solution of the linear system$q(M+{\lambda }_1(Q_1-I)+{\lambda }_2(Q_2-I))=0$,$qu=1$, where${\lambda }_1=p{\Lambda }_{1}u,$${\lambda }_2=p{\Lambda }_{2}u$. Then for the product-form stationary distribution of the process$Z(t)$, it is necessary and sufficient that at least one of the following conditions is satisfied:

$$p{\Lambda }_1={\lambda }_{1}pandp{\Lambda }_2={\lambda }_{2}p,$$

(25)

$$p{\Lambda }_1={\lambda }_{1}pandq{Q}_2=q,$$

(26)

$$q{Q}_1=qandp{\Lambda }_2={\lambda }_{2}p,$$

(27)

$$q{Q}_1=qandq{Q}_2=q.$$

(28)

There exists a constant$\phi \ne 0$such that

$${\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_1(i,j)-{\lambda }_{1}p(j)}=\phi ({\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_2(i,j)-{\lambda }_{2}p(j)})$$

(29)

for all $j\in \mathcal{X}$with${\displaystyle \sum _{i\in \mathcal{X}}p(i){\Lambda }_2(i,j)\ne {\lambda }_{2}p(j)}$, and

$${\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_2(k,r)-q(r)}=\phi (q(r)-{\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r))}$$

(30)

for all$r\in \mathcal{Y}$with${\displaystyle \sum _{k\in \mathcal{Y}}q(k)Q_1(k,r)\ne q(r)}$.

4. Examples

To demonstrate the applicability of the results obtained, let us consider several examples. Examples 1 and 2 illustrate the product-form conditions for $n=1$ and $m=0$.

Example 1.

Consider a system with the first node consisting of a bunker with waiting space for one customer and one server (Figure 1). There are always customers in the bunker. They arrive to the first node’s server, bypassing the queue, only when the server and the waiting space are empty. In addition to the customers from the bunker, there are customers from an external source forming a Poisson process with rate$\gamma$. An external customer waits if, at the time of the customer’s arrival, the server is busy. If the waiting space is occupied, the arriving customer is lost. All customers served by the first node arrive to the second node, consisting of one server, without waiting space. The service times are exponentially distributed with parameters$\alpha$and$\beta$for the first and second servers, respectively. Because the first server is always busy, the departure process of the first node is Poisson with rate$\alpha$. The state of the first node can berepresented by the number of customers in the queue, and the state of the second node by the number of customers in service.

We here show that the stationary probability distribution of the network is not of product form. This system is characterized by matrices

$$\Lambda =\left[\begin{array}{cc}-\gamma & \mathrm{\gamma }\\ \alpha & -\alpha \end{array}\right],{\Lambda }_1=\left[\begin{array}{cc}\alpha & 0\\ \alpha & 0\end{array}\right],Q_1=\left[\begin{array}{cc}0& 1\\ 0& 1\end{array}\right],{\rm M}=\left[\begin{array}{cc}0& 0\\ \beta & -\beta \end{array}\right],$$

and the solutions of the linear systems (13) and (14) are given by

$$p(0)=\frac{\alpha }{\alpha +\gamma },p(1)=\frac{\gamma }{\alpha +\gamma },q(0)=\frac{\beta }{{\lambda }_1+\beta },q(1)=\frac{\alpha }{{\lambda }_1+\beta }.$$

where ${\lambda }_1=p{\Lambda }_{1}u=\alpha$. The steady-state equations for the stationary distribution of the process $Z(t)$ are as follows:

$$\begin{array}{c}(\alpha +\gamma )\pi (0,0)=\beta \pi (0,1),(\beta +\gamma )\pi (0,1)=\alpha r(0,0)+\alpha \pi (1,0)+\alpha \pi (1,1),\\ \alpha \pi (1,0)=\gamma \pi (0,0)+\beta \pi (1,1),(\alpha +\beta )\pi (1,1)=\gamma \pi (0,1).\end{array}$$

It is easy to verify that the normalized solution of these equations is given by

$$\begin{array}{c}\pi (0,0)=\frac{\alpha \beta }{\alpha \beta +{(\alpha +\gamma )}^2},\pi (0,1)=\frac{\alpha (\alpha +\gamma )}{\alpha \beta +{(\alpha +\gamma )}^2},\\ \pi (1,0)=\frac{\gamma \beta (\alpha +\gamma )}{(\alpha +\beta )(\alpha \beta +{(\alpha +\gamma )}^2)},\pi (1,1)=\frac{\gamma \alpha (\alpha +\gamma )}{(\alpha +\beta )(\alpha \beta +{(\alpha +\gamma )}^2)}.\end{array}$$

It is clear that $\pi (i,k)\ne p(i)q(k).$ Thus, although the second node has a Poisson arrival process, this is not enough for the stationary distribution $\pi (i,k)$ to have the product form. The product-form condition of Corollary 1 does not hold since neither $p{\Lambda }_1={\lambda }_{1}p$ nor $q{Q}_1=q$.

Example 2.

Let the second node have$w>0$waiting spaces and no servers. An arriving customer takes one of the free waiting spaces, if there are any. If all waiting spaces are occupied at the instant of arrival, then the arriving customer and all those in the queue are considered served and leave the system.

Such a system with a Poisson arrival process can be represented by a Markov process with the state set $\mathcal{Y}=\{0,1,\dots ,w\}$. This process has a uniform stationary distribution $q(k)=1/(w+1)$, $k=0,1,\dots w$, and obviously satisfies the condition $q{Q}_1=q.$ According to Corollary 1, the stationary distribution $\pi (i,k)$ has the product form.

Example 3.

Now, to illustrate Corollary 2, consider a system with positive and negative customers. Each node consists of one server without waiting space (Figure 2).

The service times at the first and second servers are exponentially distributed with parameters$\alpha$and$\beta$, respectively. External Poisson processes of positive customers arrive to the servers with rates$\gamma$and$\delta$, respectively. A customer departing from the first server arrives to the second server as a positive customer. Arriving positive customers are lost if the servers are busy. A customer leaving the second server comes to the first server as a negative customer and—if the first server is busy—deletes the customer in service.

The matrices that specify the interaction of the nodes are as follows:

$$\Lambda =\left[\begin{array}{cc}-\gamma & \gamma \\ \alpha & -\alpha \end{array}\right],{\Lambda }_1=\left[\begin{array}{cc}0& 0\\ \alpha & 0\end{array}\right],Q_1=\left[\begin{array}{cc}0& 1\\ 0& 1\end{array}\right],{\rm M}=\left[\begin{array}{cc}-\delta & \delta \\ \beta & -\beta \end{array}\right],{{\rm M}}_1=\left[\begin{array}{cc}0& 0\\ \beta & 0\end{array}\right],P_1=\left[\begin{array}{cc}1& 0\\ 1& 0\end{array}\right],$$

and the solutions of the system of Equations (13) and (14) are given by the formulae

$$p(0)=\frac{\alpha +{\mu }_1}{\alpha +\gamma +{\mu }_1},p(1)=\frac{\gamma }{\alpha +\gamma +{\mu }_1},q(0)=\frac{\beta }{{\lambda }_1+\delta +\beta },q(1)=\frac{{\lambda }_1+\delta }{{\lambda }_1+\delta +\beta },$$

(31)

where

$${\lambda }_1=\alpha p(1),{\mu }_1=\beta q(1).$$

(32)

To check the conditions of Corollary 2, we first calculate the vectors that appear in them:

$$\begin{array}{c}p{\Lambda }_1-{\lambda }_{1}p=\alpha p^2(1)(1,-1),p{P}_1-p=p(1)(1,-1),\\ q{{\rm M}}_1-{\mu }_{1}q=\beta q^2(1)(1,-1),q{Q}_1-q=q(0)(-1,1).\end{array}$$

It is clear that the first four conditions of Corollary 2 are not satisfied for any positive parameters $\alpha ,\beta ,\gamma ,\delta .$

In the particular case of $\alpha =\beta =2,$ $\delta =1$, $\gamma =3$, the system of Equations (31) and (32) has the unique solution ${\lambda }_1=1$, ${\mu }_1=1$ and the parameter $\psi$ from the fifth condition of Corollary 2 is $\psi =1.$ Thus, in this case, the stationary distribution $\pi (i,k)$ has the product form.

5. Conclusions

In this paper, we have studied a Markov network consisting of two nodes of arbitrary structure, where each node generates a MMAP of customers arriving to the other node. We have derived the necessary and sufficient conditions for the product-form stationary distribution of the network. Simple criteria to check whether a Markov network with one and two customer classes is of product form have been developed. Unlike the existing product-form criteria for Markov networks, the criteria obtained in this article are readily applicable to establish the existence of a product-form stationary distribution for specific Markovian queueing systems. The extension of the developed theory to networks with more than two classes of customers is the subject of our future research.