# Strong Truncation Approximation in Tandem Queues with Blocking

Authors: Karima Adel-Aissanou; Karim Abbas; Djamil Aïssani
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Markov models are frequently used for performance modeling. However most models do not have closed form solutions, and numerical solutions are often not feasible due to the large or even infinite state space of models of practical interest. For that, the state-space truncation is often demanded for computation of this kind of models. In this paper, we use the strong stability approach to establish analytic error bounds for the truncation of a tandem queue with blocking. Numerical examples are carried out to illustrate the quality of the obtained error bounds.


---

## Body

## 1. Introduction

Queueing networks consisting of several service stations are more suitable for representing the structure of many systems with a large number of resources than models consisting of a single-service station. Particularly, the queueing networks are used for the performance and reliability evaluation of computer, communication, and manufacturing systems [1].The determination of the steady-state probabilities of all possible states of the network can be regarded as the central problem of queueing theory. The mean values of all other important performance measures of the network can be calculated from these. Several efficient algorithms for the exact solution of queueing networks are introduced. However, the memory requirements and computation time of these algorithms grow exponentially with the number of job classes in the system. For computationally difficult problems of networks with a large number of job classes, we resort to approximation methods [2].Many approximation methods for nonproduct-form networks are discussed in the literature (see [3] and references therein). Especially, the well-known technique applicable for limiting model sizes is state truncation [4, 5]. Indeed, approximating a countable-state Markov chain by using finite-state Markov chains is an interesting and often a challenging topic, which has attracted many researchers' attention. Computationally, when we solve for the stationary distribution, when it exists, of a countable-state Markov chain, the transition probability matrix of the Markov chain has to be truncated in some way into a finite matrix as a first step. We then compute the stationary distribution of this finite-state Markov chain as an approximation to that of the countable-state one. We expect that as the truncation size increases to infinity, the solution for the finite Markov chain converges to that of the countable-state Markov chain. While for many application problems the justification of the convergence could be made by the physical meanings of the finite and the countable state Markov chains, it is not always easy to formally justify this claim.The study of approximating the stationary probabilities of an infinite Markov chain by using finite Markov chains was initiated by Seneta [6] in 1967. Many up-to-date results were obtained by him and several collaborators. Most of their results are included in a paper by Gibson and Seneta [7]. Other references may be found therein and/or in another paper [8] published in the same year by the same authors. Other researchers, including Wolf [9], used different approaches to those of Seneta et al. For instance, Heyman [10] provided a probabilistic treatment of the problem. Later, Grassmann and Heyman [11] justified the convergence for infinite-state Markov chains with repeating rows. All the above results are for approximating stationary distributions. Regarding more general issues of approximating a countable-state Markov chain, see the book by Freedman [12].A different though related line of research is that of perturbed Markov chains. General results on perturbation bounds for Markov chains are summarized by Heidergott and Hordijk [13]. One group of results concerns the sensitivity of the stationary distribution of a finite, homogeneous Markov chain (see Heidergott et al. [14, 15]), and the bounds are derived using methods of matrix analysis; see the review of Cho and Meyer [16] and recent papers of Kirkland [17, 18], and Neumann and Xu [19]. Another group includes perturbation bounds for finite-time and invariant distributions of Markov chains with general state space; see Anisimov [20], Rachev [21], Aïssani and Kartashov [22], Kartashov [23], and Mitrophanov [24]. In these works, the bounds for general Markov chains are expressed in terms of ergodicity coefficients of the iterated transition kernel, which are difficult to compute for infinite state spaces. These results were obtained using operator-theoretic and probabilistic methods. Some of these methods allow us to obtain quantitative estimates in addition to the qualitative affirmation of the continuity.In this paper we are interested in computing the error bound of the stationary queue length distributions of queueing networks through finite truncation of some buffers, provided their stability holds. So, it is natural to approximate the stationary distribution of queueing networks through truncating some buffers. We may expect that such a truncation well approximates the original model as the truncation level (or size) becomes large. Therefore, we extend the applicability of the strong stability approach [23, 25] to the case of truncation problem for a tandem queue with blocking. As is well known, this network is a multidimensional, nonproduct form queueing network (see, for example, Van Dijk [4]). So, our interest is to see what conditions guarantee that the steady-state joint queue length distribution of this tandem queue system is well approximated by the finite buffer truncation of another one. Such conditions allow us to obtain better quantitative estimates on the stationary characteristics of the tandem queue with blocking and infinite buffers.The paper is organized as follows. Section2 contains the necessary definitions and notation. In Section 3, we present the considered network queueing model and we give a new perturbation bounds corresponding to the considered truncation problem. Numerical example is presented in Section 4. Eventually, we will point out directions of further research.


## 2. Strong Stability Approach

The main tool for our analysis is the weighted supremum norm, also calledυ-norm, denoted by ∥·∥υ, where υ is some vector with elements υ(k,l)>1, for all (k,l)∈S=ℤ+×{0,…,N}.Let us note that𝔅(ℕ), the Borel field of the natural numbers, that is equipped with the discrete topology and consider the measurable space (ℕ,𝔅(ℕ)).Let𝔐={μ(i,j)} be the space of finite measures on 𝔅(ℕ) and let η={f(i,j)} be the space of bounded measurable functions. We associate with each transition operator P the linear mappings:
(2.1)(μP)(k,l)=∑i=0∞‍∑j=0N‍μ(i,j)P(i,j);(k,l),(2.2)(Pf)(k,l)=∑i=0∞‍∑j=0N‍f(i,j)P(k,l);(i,j).
Introduce to 𝔐 the class of norms of the form:
(2.3)∥μ∥υ=∑i=0∞‍∑j=0N‍υ(i,j)|μ(i,j)|,
where υ is an arbitrary measurable function (not necessary finite) bounded from below by a positive constant. This norm induces in the space η the norm
(2.4)∥f∥υ=supksupl|f(k,l)|υ(k,l),k,l∈ℤ+×{0,…,N}.
Let us consider 𝔅, the space of bounded linear operators on the space {μ∈𝔐:∥μ∥υ<∞}, with norm
(2.5)∥Q∥υ=supksupl1υ(k,l)∑i=0∞‍∑j=0N‍υ(i,j)|Q(k,l);(i,j)|,k,l∈ℤ+×{0,…,N}.
Let ν and μ be two invariant measures and suppose that these measures have finite υ-norm. Then
(2.6)|νf-μf|≤∥ν-μ∥υ∥f∥υinfkinflυ(k,l),k,l∈ℤ+×{0,…,N}.For our analysis, we will assume thatv(k,l) is of a particular form υ(k,l)=αkβl, for α>1 and β>1, which implies
(2.7)infkinflυ(k,l)=1,k,l∈ℤ+×{0,…,N}.
Hence, the bound 6 becomes
(2.8)|νf-μf|≤∥ν-μ∥υsupksupl|f(k,l)|υ(k,l),k,l∈ℤ+×{0,…,N}.We say that the Markov chainX with transition kernel P verifying ∥P∥υ<∞ and invariant measure π is stronglyυ-stable, if every stochastic transition kernel P~ in some neighborhood {P~:∥P~-P∥υ<ϵ} admits a unique invariant measure π~ such that ∥π~-π∥υ tends to zero as ∥P~-P∥υ tends to zero uniformly in this neighborhood. The key criterion of strong stability of a Markov chain X is the existence of a deficient version of P defined in the following.Thereby, the Markov chainX with the transition kernel P and invariant measure π is strongly υ-stable with respect to the norm ∥·∥υ if and only if there exist a measure σ and a nonnegative measurable function h on S such that the following conditions hold:  (a)
πh>0, σ1=1, σh>0,(b)
the kernelT=P-h∘σ is nonnegative,(c)
theυ-norm of the kernel T is strictly less than one, that is, ∥T∥υ<1,(d)
∥P∥υ<∞, where ∘ denotes the convolution between a measure and a function and 1 is the vector having all the components equal to 1.It has been shown in [22] that a Markov chain X with the transition kernel P is strongly stable with respect to υ if and only if a residual for P with respect to υ exists. Although the strong stability approach originates from stability theory of Markov chains, the techniques developed for the strong stability approach allow to establish numerical algorithms for bounding ∥π~-π∥υ. A bound on ∥π~-π∥υ is established in the following theorem.Theorem 2.1 (see [26]).
LetP be strongly stable. If
(2.9)∥P~-P∥υ<1-∥T∥υ∥I-Π∥υ,
then, the following bound holds
(2.10)∥π~-π∥υ≤∥π∥υ∥I-Π∥υ∥P~-P∥υ1-∥T∥υ-∥I-Π∥υ∥P~-P∥υ,
where Π is the stationary projector of P and I is the identity matrix.Note that the term∥I-Π∥υ in the bound provided in Theorem 2.1 can be bounded by
(2.11)∥I-Π∥υ≤1+∥1∥υ∥π∥υ.
In this case, we can also bound ∥π∥υ by
(2.12)(συ)(πh)1-ρ.


## 3. Analysis of the Model

### 3.1. Model Description and Assumptions

Consider two stations in series: a tandem queue of M/M/1/∞ and M/M/1/N. There is one server at each station, and customers arrive to station 1 in accordance to a Poisson process with a state-dependent rate λ(i) when i customers are present at station (1) Customer service times at station i are exponentially distributed with rate μi, i=1, (2) The interarrival and service times are independent of one another. The size of the buffer at station 1 is infinite, whereas the buffer size at station 2 is (N<∞). When the second station is saturated the servicing at the first station is stopped. Queueing is assumed to be first-come, first-served.The steady-state joint queue size distribution of this tandem queue system does not exhibit a closed product form expression [27]. Numerical studies and approximation procedures have therefore been investigated widely (see, for example, Boxma and Konheim [28], Hillier and Boling [29], and Latouche and Neuts [30]). Van Dijk [4] has analysed the same tandem queue system and obtained an explicit error bound for bias terms of reward structures. In this paper, like in [4], we consider the truncation of the size of the buffer at station 1 to obtain another analytic error bound by using the strong stability approach [23]. Therefore, we assume that for some constant λ:
(3.1)λ(i)≤λ,λ(i)→0asi→∞,andλ(i):nonincreasingini.Let(i,j) denote the number of customers at stations 1(i) and 2(j), M=λ+μ1+μ2, and consider the discrete time Markov chain with one-step transition probabilities given by [4]:
(3.2)P~(i,j);(i+1,j)=λ(i)M,P~(i,j);(i,j-1)=[μ2M]1{j>0},P~(i,j);(i-1,j+1)=[μ1M]1{i>0}1{j<N},P~(i,j);(i,j)=1-[λ(i)+μ11{i>0}1{j<N}+μ21{j>0}]M.In order to apply the strong stability approach, we consider the same truncation considered by Van Dijk [4]. Therefore, for a finite integer Q, we have the following truncation:
(3.3)P(Q,j);(Q,j)=1-[μ11{i>0}1{j<N}+μ21{j>0}]M,P(i,j);(0,0)=1{i>Q,0≤j≤N},P(i,j);(m,n)=P~(i,j);(m,n),otherwise.Equation (3.3) means that the queue size at station 1 is truncated at level Q by rejecting arrivals whenever i=Q. We remark also that the two transition matrices P~ and P are stochastic.


### 3.2. Strong Stability Bounds

For our bounds, we require bounds on the basic input entities such asπ and T. In order to establish those bounds, we have to specify υ. Specifically, for α>1 and β>1, we will choose
(3.4)υ(k,l)=αkβl,(k,l)∈S,
as our norm-defining mapping.For ease of reference, we introduce the following condition:(C)λmin{μ1,μ2}<1.
This condition corresponds to the trafic intensity condition of the infinite system.Essential for our numerical bound on the deviation between stationary distributionsπ and π~ is a bound on the deviation of the transition kernel P~ from P. This bound is provided in the following lemma.Lemma 3.1.
If condition(C) is satisfied, then
(3.5)∥P~-P∥υ≤(α+1)λ(Q)M=Δ(α,β).Proof.
By definition, we have(3.6)∥P~-P∥υ=sup0≤i≤Qsup0≤j≤N1υ(i,j)∑m=0Q‍∑n=0N‍υ(m,n)|P~(i,j);(m,n)-P(i,j);(m,n)|.=sup0≤i≤Qsup0≤j≤NS(i,j),
where
(3.7)S(i,j)=1υ(i,j)∑m=0Q‍∑n=0N‍υ(m,n)|P~(i,j);(m,n)-P(i,j);(m,n)|.
For 0≤i≤Q-1:
(3.8)S(i,j)=0.
For i=Q:
(3.9)S(Q,j)=1αQsup0≤j≤N1βj∑m≥0Q‍∑n=0N‍αmβn|P~(Q,j);(m,n)-P(Q,j);(m,n)|.Ifj=0:
(3.10)S(Q,0)=1αQ1β0{αQ-1β1|μ1M-μ1M|+αQβ0|1-λ(Q)M-μ1M-1+μ1M|+αQ+1β0λ(Q)M}=(α+1)λ(Q)M.If0<j<N:
(3.11)S(Q,j)=1αQsup0≤j≤N1βj{λ(Q)MαQ-1β1|μ1M-μ1M|+αQ[βj-1|μ2M-μ2M|+βj|1-λ(Q)M-μ1M-μ2M-1+μ1M+μ2M|]+αQ+1βjλ(Q)M}=(α+1)λ(Q)M.Ifj=N:
(3.12)S(Q,N)=1αQ1βN{αQ[βN-1|μ2M-μ2M|+βN|1-λ(Q)M-μ2M-1+μ2M|]}=λ(Q)M.
From (3.10), (3.11), and (3.12) we have
(3.13)∥P~-P∥υ=(α+1)λ(Q)M.
For i>Q:
if0≤j≤N, then we have
(3.14)P(i,j);(m,n)={1,ifm=0andn=0,0,otherwise,(3.15)S(i,j)=supi>Qsup0≤j≤N1v(i,j)=(1+αiβj(1-λ(i)M-μ1M1j<N-μ2M1j>0)+αi+1βjλ(i)M+αi-1βj+1μ1M1j<N+αiβj-1μ2M1j>0λ(i)M)≤1αQ+1+(α-1)λ(Q+1)M-(1-βα)μ1M1j<N-(1-1β)μ2M1j>0.
From (3.8), (3.13), and (3.15) we have
(3.16)∥P~-P∥υ≤(α+1)λ(Q)M.LetT denote a deficient Markov kernel (residual matrix) for the transition matrix P~ that avoids jumps to state (0,0); more specifically, for (i,j), (m,n) let
(3.17)T(i,j);(m,n)={0,ifi=j=0,P(i,j);(m,n),otherwise.Lemma 3.2.
Provided that condition(C) holds, it holds that
(3.18)∥T∥υ=1+(α-1)λM+m(α,β)M=ρ(α,β)<1,
where
(3.19)m(α,β)=max{(βα-1)μ1,(1β-1)μ2}.Proof.
We have(3.20)Tυ(i,j)=∑m≥0Q‍∑n=0N‍υ(m,n)T(i,j);(m,n).
For i=0:  ifj=0:
(3.21)Tυ(0,0)=∑m≥0Q‍∑n=0N‍αmβn×0=0.If0<j≤N:
(3.22)Tυ(0,j)=∑m≥0Q‍∑n=0N‍αmβnP(0,j);(m,n)=α0{βj-1μ2M+βj[1-λ(0)M-μ2M]}+α1λ(0)M=α0βj{1+(α-1)λ(0)M+(1β-1)μ2M}.
From (3.21) and (3.22) we have
(3.23)ρ1{i=0}=1+(α-1)λ(0)M+(1β-1)μ2M.
For 1≤i≤Q-1:  ifj=0:
(3.24)Tυ(i,0)=∑m≥0Q‍∑n=0N‍αmβnP(i,0);(m,n)=αi-1β1μ1M+αiβ0[1-λ(i)M-μ1M]+αi+1β0λ(i)M=αiβ0{1+(βα-1)μ1M+(α-1)λ(i)M}.If0<j<N:
(3.25)Tυ(i,j)=∑m≥0Q‍∑n=0N‍αmβnP(i,j);(m,n)=αi-1βj+1μ1M+αi{βj-1μ2M+βj[1-λ(i)M-μ1M-μ2M]}+αi+1βjλ(i)M=αiβj{1+(α-1)λ(i)M+(βα-1)μ1M+(1β-1)μ2M}.Ifj=N:
(3.26)Tυ(i,N)=∑m≥0Q‍∑n=0N‍αmβnP(i,N);(m,n)=αi{βN-1μ2M+βN[1-λ(i)M-μ2M]}+αi+1βNλ(i)M=αiβN{1+(α-1)λ(i)M+(1β-1)μ2M}.
From (3.24), (3.25), and (3.26) we have
(3.27)ρ1{1≤i≤Q-1}=1+(α-1)λ(i)M+m(α,β)M.
For i=Q:  ifj=0:
(3.28)Tυ(Q,0)=∑m≥0Q‍∑n=0N‍αmβnP(Q,0);(m,n)=αQ-1β1μ1M+αQβ0[1-μ1M]=αQβ0{1+(βα-1)μ1M}.If0<j<N:
(3.29)Tυ(Q,j)=∑m≥0Q‍∑n=0N‍αmβnP(Q,j);(m,n)=αQ-1βj+1μ1M+αQ{βj-1μ2M+βj[1-μ1M-μ2M]}=αQβj{1+(βα-1)μ1M+(1β-1)μ2M}.Ifj=N:
(3.30)Tυ(Q,N)=∑m≥0Q‍∑n=0N‍αmβnP(Q,N);(m,n)=αQ{βN-1μ2M+βN[1-μ2M]}=αQβN{1+(1β-1)μ2M}.
From (3.28), (3.29), and (3.30) we have
(3.31)ρ1{i=Q}=max{1+m(α,β)M,1+(βα-1)μ1M}.
In order to obtainρ1{i=Q}<1, we must impose that β<α.
Fori>Q:
(3.32)Tv(i,j)=1,=αiβjαiβj,=αiβjαQβ0,=αiβj1αQ,
From (3.23), (3.27), (3.31), and (3.32) we have
(3.33)ρ(α,β)=max{1+(α-1)λM+m(α,β)M,1+m(α,β)M,1+(βα-1)μ1M}.
For allβ such that: 1<β<min(μ1,μ2)/λ and β<α<1+(1-1/β)(min(μ1,μ2)/λ), we will obtain ρ(α,β)<1, then, under the same condition, we finally obtain
(3.34)Tυ(i,j)≤ρ(α,β)υ(i,j),∀i,j∈S,
and it follows that the υ-norm of T is equal to ρ(α,β), which proves the claim.In the following lemma we will identify the range forα and β that leads to finite υ-norm of π.For that, we choose the measurable function(3.35)h(i,j)=1{i=0,j=0}={1,fori=j=0,0,otherwise,
and the probability measure
(3.36)σ(i,j)=P(0,0);(i,j).Lemma 3.3.
Provided that(C) holds, the υ-norm of π is bounded by
(3.37)∥π∥υ=π(0,0)1-ρ(α,β)(1+(α-1)λ(0)M)=c0(α,β)<∞,
where ρ(α,β) was defined in (3.18).Proof.
We have(3.38)∥π∥υ≤(συ)(πh)1-ρ.
By definition,
(3.39)συ=∑i≥0∞‍∑j=0N‍σ(i,j)h(i,j)=1+(α-1)λ(0)M,πh=∑i≥0∞‍∑j=0N‍π(i,j)h(i,j)=π(0,0).
Hence,
(3.40)∥π∥υ=π(0,0)1-ρ(1+(α-1)λ(0)M)=c0(α,β).Let(3.41)α0=sup{α:ρ(α,β)<1},β0=sup{β:ρ(α,β)<1}.Theorem 3.4.
Provided that(C) holds, then, for all (α,β) such that β<α<α0 and 1<β<β0, the discrete time Markov chain describing the tandem queue with blocking and finite buffers model is υ-strongly stable for the test function υ(k,l)=αkβl.Proof.
We haveπh=π(0,0)>0, σ1=1, and σh=σ(0,0)=1-(λ(0)/M)>0.
(3.42)T(i,j);(m,n)=P(i,j);(m,n)-h(i,j)σ(m,n)={0,ifi=j=0,P(i,j);(m,n),otherwise.
Hence, the kernel T is nonnegative.
We verify that∥P∥υ<∞. We have
(3.43)T=P-h∘σ⇒P=T+h∘σ⇒∥P∥υ≤∥T∥υ+∥h∥υ∥σ∥υ,
or, according to (2.5),
(3.44)∥T∥υ=sup0≤isup0≤j≤N1υ(i,j)∑m=0∞‍∑n=0N‍υ(m,n)|T(i,j);(m,n)|≤sup0≤isup0≤j≤N1υ(i,j)ρ(α,β)υ(i,j)≤ρ(α,β)<1.
According to (2.4) and (2.1), we have
(3.45)∥h∥υ=sup0≤isup0≤j≤N1υ(i,j)|h(i,j)|=1,∥σ∥υ=∑m=0∞‍∑n=0N‍υ(m,n)|σ(m,n)|=∑m=0∞‍∑n=0N‍αmβnP(0,0);(m,n)=1+(α-1)λ(0)M≤1+(α0-1)λM<∞,
where
(3.46)α0=sup{α:ρ(α,β)<1}.
Then,∥P∥υ<∞.By Theorem3.4, the general bound provided Theorem 2.1 can be applied to the kernels P and P~ for our tandem queues with blocking. Specifically, we will insert the individual bounds provided in Lemmas 3.1, 3.2, and 3.3, which yields the following result.Theorem 3.5.
Letπ and π~ be the steady-state joint queue size distributions of the discrete time Markov chains in the tandem queue with blocking and finite buffers and the tandem queue with blocking with infinite buffers respectively. Provided that (C) holds, then, for all β<α<α0 and 1<β<β0, and under the condition:
(3.47)Δ(α,β)<1-ρ(α,β)c(α,β),
we have the following estimate:
(3.48)∥π~-π∥υ≤c0(α,β)c(α,β)Δ(α,β)1-ρ(α,β)-c(α,β)Δ(α,β)=SSB(α,β),
where c(α,β)=1+c0(α,β) and Δ(α,β), ρ(α,β), and c0(α,β) were already defined by the formulas (3.5), (3.18), and (3.37), respectively.Proof.
Note thatα∈]β,α0[ and β∈]1,β0[ already implies c0(α,β)<∞ and ρ(α,β)<1. Hence, Lemmas 3.2 and 3.3 apply.Following the line of thought put forward in Section2, see (2.6), we will translate the norm bound in Theorem 3.5 to bounds for individual performance measures f.Corollary 3.6.
Under the conditions put forward in Theorem3.5, it holds for any f such that ∥f∥υ<∞ that
(3.49)|π~f-πf|≤∥f∥υ×SSB(α,β).Note that the bound (3.49) in Corollary 3.6 has α and β as free parameters. This give the opportunity to minimize the right hand side of the inequality (3.48) in Theorem 3.5 with respect to (α,β). For given ϱ=λ/M, this leads to the following optimization problem:
(3.50)min(α,β)SSB(α,β)s.t.ρ(α,β)<1,Δ(α,β)<1-ρ(α,β)c(α,β).


## 3.1. Model Description and Assumptions

Consider two stations in series: a tandem queue of M/M/1/∞ and M/M/1/N. There is one server at each station, and customers arrive to station 1 in accordance to a Poisson process with a state-dependent rate λ(i) when i customers are present at station (1) Customer service times at station i are exponentially distributed with rate μi, i=1, (2) The interarrival and service times are independent of one another. The size of the buffer at station 1 is infinite, whereas the buffer size at station 2 is (N<∞). When the second station is saturated the servicing at the first station is stopped. Queueing is assumed to be first-come, first-served.The steady-state joint queue size distribution of this tandem queue system does not exhibit a closed product form expression [27]. Numerical studies and approximation procedures have therefore been investigated widely (see, for example, Boxma and Konheim [28], Hillier and Boling [29], and Latouche and Neuts [30]). Van Dijk [4] has analysed the same tandem queue system and obtained an explicit error bound for bias terms of reward structures. In this paper, like in [4], we consider the truncation of the size of the buffer at station 1 to obtain another analytic error bound by using the strong stability approach [23]. Therefore, we assume that for some constant λ:
(3.1)λ(i)≤λ,λ(i)→0asi→∞,andλ(i):nonincreasingini.Let(i,j) denote the number of customers at stations 1(i) and 2(j), M=λ+μ1+μ2, and consider the discrete time Markov chain with one-step transition probabilities given by [4]:
(3.2)P~(i,j);(i+1,j)=λ(i)M,P~(i,j);(i,j-1)=[μ2M]1{j>0},P~(i,j);(i-1,j+1)=[μ1M]1{i>0}1{j<N},P~(i,j);(i,j)=1-[λ(i)+μ11{i>0}1{j<N}+μ21{j>0}]M.In order to apply the strong stability approach, we consider the same truncation considered by Van Dijk [4]. Therefore, for a finite integer Q, we have the following truncation:
(3.3)P(Q,j);(Q,j)=1-[μ11{i>0}1{j<N}+μ21{j>0}]M,P(i,j);(0,0)=1{i>Q,0≤j≤N},P(i,j);(m,n)=P~(i,j);(m,n),otherwise.Equation (3.3) means that the queue size at station 1 is truncated at level Q by rejecting arrivals whenever i=Q. We remark also that the two transition matrices P~ and P are stochastic.


## 3.2. Strong Stability Bounds

For our bounds, we require bounds on the basic input entities such asπ and T. In order to establish those bounds, we have to specify υ. Specifically, for α>1 and β>1, we will choose
(3.4)υ(k,l)=αkβl,(k,l)∈S,
as our norm-defining mapping.For ease of reference, we introduce the following condition:(C)λmin{μ1,μ2}<1.
This condition corresponds to the trafic intensity condition of the infinite system.Essential for our numerical bound on the deviation between stationary distributionsπ and π~ is a bound on the deviation of the transition kernel P~ from P. This bound is provided in the following lemma.Lemma 3.1.
If condition(C) is satisfied, then
(3.5)∥P~-P∥υ≤(α+1)λ(Q)M=Δ(α,β).Proof.
By definition, we have(3.6)∥P~-P∥υ=sup0≤i≤Qsup0≤j≤N1υ(i,j)∑m=0Q‍∑n=0N‍υ(m,n)|P~(i,j);(m,n)-P(i,j);(m,n)|.=sup0≤i≤Qsup0≤j≤NS(i,j),
where
(3.7)S(i,j)=1υ(i,j)∑m=0Q‍∑n=0N‍υ(m,n)|P~(i,j);(m,n)-P(i,j);(m,n)|.
For 0≤i≤Q-1:
(3.8)S(i,j)=0.
For i=Q:
(3.9)S(Q,j)=1αQsup0≤j≤N1βj∑m≥0Q‍∑n=0N‍αmβn|P~(Q,j);(m,n)-P(Q,j);(m,n)|.Ifj=0:
(3.10)S(Q,0)=1αQ1β0{αQ-1β1|μ1M-μ1M|+αQβ0|1-λ(Q)M-μ1M-1+μ1M|+αQ+1β0λ(Q)M}=(α+1)λ(Q)M.If0<j<N:
(3.11)S(Q,j)=1αQsup0≤j≤N1βj{λ(Q)MαQ-1β1|μ1M-μ1M|+αQ[βj-1|μ2M-μ2M|+βj|1-λ(Q)M-μ1M-μ2M-1+μ1M+μ2M|]+αQ+1βjλ(Q)M}=(α+1)λ(Q)M.Ifj=N:
(3.12)S(Q,N)=1αQ1βN{αQ[βN-1|μ2M-μ2M|+βN|1-λ(Q)M-μ2M-1+μ2M|]}=λ(Q)M.
From (3.10), (3.11), and (3.12) we have
(3.13)∥P~-P∥υ=(α+1)λ(Q)M.
For i>Q:
if0≤j≤N, then we have
(3.14)P(i,j);(m,n)={1,ifm=0andn=0,0,otherwise,(3.15)S(i,j)=supi>Qsup0≤j≤N1v(i,j)=(1+αiβj(1-λ(i)M-μ1M1j<N-μ2M1j>0)+αi+1βjλ(i)M+αi-1βj+1μ1M1j<N+αiβj-1μ2M1j>0λ(i)M)≤1αQ+1+(α-1)λ(Q+1)M-(1-βα)μ1M1j<N-(1-1β)μ2M1j>0.
From (3.8), (3.13), and (3.15) we have
(3.16)∥P~-P∥υ≤(α+1)λ(Q)M.LetT denote a deficient Markov kernel (residual matrix) for the transition matrix P~ that avoids jumps to state (0,0); more specifically, for (i,j), (m,n) let
(3.17)T(i,j);(m,n)={0,ifi=j=0,P(i,j);(m,n),otherwise.Lemma 3.2.
Provided that condition(C) holds, it holds that
(3.18)∥T∥υ=1+(α-1)λM+m(α,β)M=ρ(α,β)<1,
where
(3.19)m(α,β)=max{(βα-1)μ1,(1β-1)μ2}.Proof.
We have(3.20)Tυ(i,j)=∑m≥0Q‍∑n=0N‍υ(m,n)T(i,j);(m,n).
For i=0:  ifj=0:
(3.21)Tυ(0,0)=∑m≥0Q‍∑n=0N‍αmβn×0=0.If0<j≤N:
(3.22)Tυ(0,j)=∑m≥0Q‍∑n=0N‍αmβnP(0,j);(m,n)=α0{βj-1μ2M+βj[1-λ(0)M-μ2M]}+α1λ(0)M=α0βj{1+(α-1)λ(0)M+(1β-1)μ2M}.
From (3.21) and (3.22) we have
(3.23)ρ1{i=0}=1+(α-1)λ(0)M+(1β-1)μ2M.
For 1≤i≤Q-1:  ifj=0:
(3.24)Tυ(i,0)=∑m≥0Q‍∑n=0N‍αmβnP(i,0);(m,n)=αi-1β1μ1M+αiβ0[1-λ(i)M-μ1M]+αi+1β0λ(i)M=αiβ0{1+(βα-1)μ1M+(α-1)λ(i)M}.If0<j<N:
(3.25)Tυ(i,j)=∑m≥0Q‍∑n=0N‍αmβnP(i,j);(m,n)=αi-1βj+1μ1M+αi{βj-1μ2M+βj[1-λ(i)M-μ1M-μ2M]}+αi+1βjλ(i)M=αiβj{1+(α-1)λ(i)M+(βα-1)μ1M+(1β-1)μ2M}.Ifj=N:
(3.26)Tυ(i,N)=∑m≥0Q‍∑n=0N‍αmβnP(i,N);(m,n)=αi{βN-1μ2M+βN[1-λ(i)M-μ2M]}+αi+1βNλ(i)M=αiβN{1+(α-1)λ(i)M+(1β-1)μ2M}.
From (3.24), (3.25), and (3.26) we have
(3.27)ρ1{1≤i≤Q-1}=1+(α-1)λ(i)M+m(α,β)M.
For i=Q:  ifj=0:
(3.28)Tυ(Q,0)=∑m≥0Q‍∑n=0N‍αmβnP(Q,0);(m,n)=αQ-1β1μ1M+αQβ0[1-μ1M]=αQβ0{1+(βα-1)μ1M}.If0<j<N:
(3.29)Tυ(Q,j)=∑m≥0Q‍∑n=0N‍αmβnP(Q,j);(m,n)=αQ-1βj+1μ1M+αQ{βj-1μ2M+βj[1-μ1M-μ2M]}=αQβj{1+(βα-1)μ1M+(1β-1)μ2M}.Ifj=N:
(3.30)Tυ(Q,N)=∑m≥0Q‍∑n=0N‍αmβnP(Q,N);(m,n)=αQ{βN-1μ2M+βN[1-μ2M]}=αQβN{1+(1β-1)μ2M}.
From (3.28), (3.29), and (3.30) we have
(3.31)ρ1{i=Q}=max{1+m(α,β)M,1+(βα-1)μ1M}.
In order to obtainρ1{i=Q}<1, we must impose that β<α.
Fori>Q:
(3.32)Tv(i,j)=1,=αiβjαiβj,=αiβjαQβ0,=αiβj1αQ,
From (3.23), (3.27), (3.31), and (3.32) we have
(3.33)ρ(α,β)=max{1+(α-1)λM+m(α,β)M,1+m(α,β)M,1+(βα-1)μ1M}.
For allβ such that: 1<β<min(μ1,μ2)/λ and β<α<1+(1-1/β)(min(μ1,μ2)/λ), we will obtain ρ(α,β)<1, then, under the same condition, we finally obtain
(3.34)Tυ(i,j)≤ρ(α,β)υ(i,j),∀i,j∈S,
and it follows that the υ-norm of T is equal to ρ(α,β), which proves the claim.In the following lemma we will identify the range forα and β that leads to finite υ-norm of π.For that, we choose the measurable function(3.35)h(i,j)=1{i=0,j=0}={1,fori=j=0,0,otherwise,
and the probability measure
(3.36)σ(i,j)=P(0,0);(i,j).Lemma 3.3.
Provided that(C) holds, the υ-norm of π is bounded by
(3.37)∥π∥υ=π(0,0)1-ρ(α,β)(1+(α-1)λ(0)M)=c0(α,β)<∞,
where ρ(α,β) was defined in (3.18).Proof.
We have(3.38)∥π∥υ≤(συ)(πh)1-ρ.
By definition,
(3.39)συ=∑i≥0∞‍∑j=0N‍σ(i,j)h(i,j)=1+(α-1)λ(0)M,πh=∑i≥0∞‍∑j=0N‍π(i,j)h(i,j)=π(0,0).
Hence,
(3.40)∥π∥υ=π(0,0)1-ρ(1+(α-1)λ(0)M)=c0(α,β).Let(3.41)α0=sup{α:ρ(α,β)<1},β0=sup{β:ρ(α,β)<1}.Theorem 3.4.
Provided that(C) holds, then, for all (α,β) such that β<α<α0 and 1<β<β0, the discrete time Markov chain describing the tandem queue with blocking and finite buffers model is υ-strongly stable for the test function υ(k,l)=αkβl.Proof.
We haveπh=π(0,0)>0, σ1=1, and σh=σ(0,0)=1-(λ(0)/M)>0.
(3.42)T(i,j);(m,n)=P(i,j);(m,n)-h(i,j)σ(m,n)={0,ifi=j=0,P(i,j);(m,n),otherwise.
Hence, the kernel T is nonnegative.
We verify that∥P∥υ<∞. We have
(3.43)T=P-h∘σ⇒P=T+h∘σ⇒∥P∥υ≤∥T∥υ+∥h∥υ∥σ∥υ,
or, according to (2.5),
(3.44)∥T∥υ=sup0≤isup0≤j≤N1υ(i,j)∑m=0∞‍∑n=0N‍υ(m,n)|T(i,j);(m,n)|≤sup0≤isup0≤j≤N1υ(i,j)ρ(α,β)υ(i,j)≤ρ(α,β)<1.
According to (2.4) and (2.1), we have
(3.45)∥h∥υ=sup0≤isup0≤j≤N1υ(i,j)|h(i,j)|=1,∥σ∥υ=∑m=0∞‍∑n=0N‍υ(m,n)|σ(m,n)|=∑m=0∞‍∑n=0N‍αmβnP(0,0);(m,n)=1+(α-1)λ(0)M≤1+(α0-1)λM<∞,
where
(3.46)α0=sup{α:ρ(α,β)<1}.
Then,∥P∥υ<∞.By Theorem3.4, the general bound provided Theorem 2.1 can be applied to the kernels P and P~ for our tandem queues with blocking. Specifically, we will insert the individual bounds provided in Lemmas 3.1, 3.2, and 3.3, which yields the following result.Theorem 3.5.
Letπ and π~ be the steady-state joint queue size distributions of the discrete time Markov chains in the tandem queue with blocking and finite buffers and the tandem queue with blocking with infinite buffers respectively. Provided that (C) holds, then, for all β<α<α0 and 1<β<β0, and under the condition:
(3.47)Δ(α,β)<1-ρ(α,β)c(α,β),
we have the following estimate:
(3.48)∥π~-π∥υ≤c0(α,β)c(α,β)Δ(α,β)1-ρ(α,β)-c(α,β)Δ(α,β)=SSB(α,β),
where c(α,β)=1+c0(α,β) and Δ(α,β), ρ(α,β), and c0(α,β) were already defined by the formulas (3.5), (3.18), and (3.37), respectively.Proof.
Note thatα∈]β,α0[ and β∈]1,β0[ already implies c0(α,β)<∞ and ρ(α,β)<1. Hence, Lemmas 3.2 and 3.3 apply.Following the line of thought put forward in Section2, see (2.6), we will translate the norm bound in Theorem 3.5 to bounds for individual performance measures f.Corollary 3.6.
Under the conditions put forward in Theorem3.5, it holds for any f such that ∥f∥υ<∞ that
(3.49)|π~f-πf|≤∥f∥υ×SSB(α,β).Note that the bound (3.49) in Corollary 3.6 has α and β as free parameters. This give the opportunity to minimize the right hand side of the inequality (3.48) in Theorem 3.5 with respect to (α,β). For given ϱ=λ/M, this leads to the following optimization problem:
(3.50)min(α,β)SSB(α,β)s.t.ρ(α,β)<1,Δ(α,β)<1-ρ(α,β)c(α,β).


## 4. Numerical Example

In this section we will apply our bound put forward in Theorem3.5. For this, we implement an algorithm (the principal idea of this algorithm is the same as in [25]) on concrete cases. Indeed, we apply a computer program to determine the made error on stationary distribution due to the approximation, when the approximation is possible, as well as the norm from which the error is obtained. It is important, in this work, to give an idea about the performance of this approach. For this, we computed the real value of the error by enlarging the state space and derived the stationary distribution. For that, we elaborated a program in the Matlab environment according to the following steps.(1)
Compute the stationary distributionπ~ of the tandem queue with blocking with infinite buffers (the original model) using the definition (π~=μlimn→∞P~n), where μ is a probability measure.(2)
Compute the stationary distributionπ of the tandem queue with blocking and finite buffers (the truncated model)sing the definition (π=μlimn→∞Pn), where μ is a probability measure.(3)
Calculate∑i=0Q∑m=0Nαiβm|π~(i,m)-π(i,m)|.In order to compare the both errors (the real and that obtained by the strong stability approach), we calculated the real values of the error with the same norm that we have calculated the approximation.For the first numerical example we setλ(i)=(1-γ)γi with γ=0.1, μ1=5, μ2=2, and N=5, and for the second one we set λ(i)=(1-γ)γi with γ=0.3, μ1=6, μ2=4, and N=6. As a first step for applying our bound, in the both examples, we compute the values for (α,β) that minimize SSB(α,β). Then, we can compute the bound put forward in Theorem 3.5 for various values for Q. The numerical results are presented in Tables 1 and 2.Table 1
Comparison of our bounds.
Q
SSB (α, β)
RE (α, β)
5
9.3416
0.0381
10
2.0045
0.0304
15
0.8600
0.0296
20
0.4372
0.0250
25
0.2386
0.0224
30
0.1349
0.0210
35
0.0777
0.0201
40
0.0452
0.0196
45
0.0265
0.0193
50
0.0156
0.0192Table 2
Comparison of our bounds.
Q
SSB (α, β)
RE (α, β)
5
7.8433
0.0015
10
0.5085
5.2352
e
-
004
15
0.0773
3.5767
e
-
004
20
0.0128
3.3350
e
-
004
25
0.0021
3.2954
e
-
004
30
3.6031
e
-
004
3.2888
e
-
004
35
6.0552
e
-
005
3.2877
e
-
004
40
1.0177
e
-
005
3.2875
e
-
004
45
1.7104
e
-
006
3.2874
e
-
004
50
2.8747e-007
3.2874e-004


### 4.1. Strong Stability Algorithm

Step 1.
Define the inputs:(i)
the service rate of the first station (μ1);(ii)
the service rate of the second station (μ2);(iii)
the arrival mean rateλ;(iv)
the functionλ(i);(v)
the number of buffers in the second station (N);(vi)
the truncation level (Q);(vii)
the steph.Step 2.
Verify the intensity trafic condition:ifλ/min(μ1,μ2)<1, go to Step 3,else (*the system is unstable*), go to Step6.Step 3.
DetermineM=λ+μ1+μ2,β0=min(μ1,μ2)/λ and put β=1+h;ifβ<β0, go to Step 4;else, go to Step6.Step 4.
For each value ofβ determine the constant:α0=sup{α:ρ(α,β)<1}=1+(1-1/β)(min(μ1,μ2)/λ);α=β+h, go to Step 5.Step 5.
CalculateSSB(α,β) and α=α+h, if α<α0 go to Step 5;
elseβ=β+h and go to Step 4.Step 6.
Determine(αopt,βopt) and SSB(αopt,βopt), where
(4.1)SSB(αopt,βopt)=minSSB(α,β).Step 7.
End.We compared our expected approximation error (SSB) against numerical results (RE) and we easily observed that the real error on the stationary distribution is significantly smaller than the strong stability approach one. Furthermore, if we compare our expected approximation error against the numerical results, it is easy to see that the error decreases as the truncation level Q increases. We can notice the remarkable sensibility of the strong stability approach in the variation of the truncation level Q with regard to the real error. This means that the numerical error is really the point of the error which we can do when switching from the tandem queue with blocking and infinite buffers to the another one with finite buffers. Graphic comparison is illustrated in Figures 1 and 2.Figure 1
Errors, comparative curves.Figure 2
Errors, comparative curves.


## 4.1. Strong Stability Algorithm

Step 1.
Define the inputs:(i)
the service rate of the first station (μ1);(ii)
the service rate of the second station (μ2);(iii)
the arrival mean rateλ;(iv)
the functionλ(i);(v)
the number of buffers in the second station (N);(vi)
the truncation level (Q);(vii)
the steph.Step 2.
Verify the intensity trafic condition:ifλ/min(μ1,μ2)<1, go to Step 3,else (*the system is unstable*), go to Step6.Step 3.
DetermineM=λ+μ1+μ2,β0=min(μ1,μ2)/λ and put β=1+h;ifβ<β0, go to Step 4;else, go to Step6.Step 4.
For each value ofβ determine the constant:α0=sup{α:ρ(α,β)<1}=1+(1-1/β)(min(μ1,μ2)/λ);α=β+h, go to Step 5.Step 5.
CalculateSSB(α,β) and α=α+h, if α<α0 go to Step 5;
elseβ=β+h and go to Step 4.Step 6.
Determine(αopt,βopt) and SSB(αopt,βopt), where
(4.1)SSB(αopt,βopt)=minSSB(α,β).Step 7.
End.We compared our expected approximation error (SSB) against numerical results (RE) and we easily observed that the real error on the stationary distribution is significantly smaller than the strong stability approach one. Furthermore, if we compare our expected approximation error against the numerical results, it is easy to see that the error decreases as the truncation level Q increases. We can notice the remarkable sensibility of the strong stability approach in the variation of the truncation level Q with regard to the real error. This means that the numerical error is really the point of the error which we can do when switching from the tandem queue with blocking and infinite buffers to the another one with finite buffers. Graphic comparison is illustrated in Figures 1 and 2.Figure 1
Errors, comparative curves.Figure 2
Errors, comparative curves.


## 5. Further Research

An alternative method for computing bounds on perturbations of Markov chains is the series expansion approach to Markov chains (SEMC). The general approach of SEMC has been introduced in [13]. SEMC for discrete time finite Markov chains is discussed in [15], and SEMC for continuous time Markov chains is developed in [14]. The key feature of SEMC is that a bound for the precision of the approximation can be given. Unfortunately, SEMC requires (numerical) computation of the deviation matrix, which limits the approach in essence to Markov chains with finite state space. Perturbation analysis via the strong stability approach overcomes this drawback, however, in contrast to SEMC, no measure on the quality of the approximation can be given.



---

*Source: 906486-2012-12-26.xml*