# On the Convergence of Truncated Processes of Multiserver Retrial Queues

Authors: M. Jose Domenech-Benlloch; Jose Manuel Gimenez-Guzman; Vicent Pla; Jorge Martinez-Bauset; Vicente Casares-Giner
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

Retrial queues can only be solved in a closed form in very few and simple cases,
so researchers must resort to approximate models. However, most of the papers that
propose approximate models assume the convergence of the proposed models to their
exact counterparts, without providing a rigorous mathematical proof. In this paper we
demonstrate the convergence of finite truncated models with two reattempt orbits.


---

## Body

## 1. Introduction

Multiserver retrial queues (MRQs) are used to model multiple situations in our daily life activities, from queues in a supermarket to communication networks. MRQs model the activities in which a user that cannot get service immediately does not leave the system but returns after a random time to try again. The general structure of an MRQ contains two blocks: a block that accommodates the servers and a delay block for the repeated attempts. The general purpose of modelling MRQs is to obtain the steady-state probabilities for later computing some system descriptors. Unfortunately, it is only possible to derive closed-form expressions in a few and simple retrial models, so it is necessary to resort to approximate models and algorithmic methods to solve most of the MRQs [1, 2]. There is a wide literature that proposes new approximate models that are able to solve—approximately—MRQs [3–5]. Most of these approximations are based on some sort of truncation or generalized truncation [4, 6]. Intuitively, one would expect that the higher the level of truncation—that is, the more similar is the approximate model to the original one—the more accurate is the computed approximation and that as the level of truncation grows to infinity—that is, the approximate model tends to the original one—the computed approximation converges to the exact solution. The latter would be a desirable property for any approximation, not only theoretically but also from a practical perspective since it basically states that one can get as close as wanted to the exact solution by increasing the computational effort. Unfortunately, beyond intuition there is no guarantee that such property holds in the general case. On the other hand, it is worth noting that the fulfillment of the aforementioned property cannot be verified numerically unless a previous approximation exists for which such a guarantee has been established.As mentioned, there are an important number of published approximations to otherwise unsolvable retrial models. However, the convergence issue is only addressed in a few of them [7] and, to the best of our knowledge, all of them deal with MRQs with a single reattempt orbit [2, 7–10].The objective of this paper is to establish the convergence of some finite truncated models with two reattempt orbits to their original and exact counterparts. More concretely, the original model for which we demonstrate the convergence is based on a cellular network system which is described in Section2. Different approximate solution methods for that system have been proposed in [5]. However, it is important to note that it is just a possible scenario of a two-reattempt-orbit MRQ and that a similar procedure could be suitable to other systems in which there are different reattempt types.The remainder of this paper is organized as follows. Section2 describes the model of the system under study, while in Section 3 we mathematically verify the convergence of a family of finite truncated models to their original counterparts in a two-reattempt-orbit multiserver retrial queue. Final remarks and a summary of the paper are provided in Section 4.


## 2. System Model and Description

The system under study is a mobile cellular network. In this type of network, the coverage area is divided into services areas, named cells, and customers can move across different cells. When a customer with an active communication moves from one cell to another, a so-called handover procedure is executed to allocate the necessary resources in the new cell and release the unused resources in the former cell. Obviously, both new sessions and handovers will have their own reattempts (redials and retrials, resp.) but with very different characteristics. As in GSM [11], blocked handovers will be automatically retried until a reattempt succeeds or the user moves outside the handover area. In contrast, persistence of redials depends on the user patience. Another difference is that the maximum number of unsuccessful automatic retrials is set by the network operator while redials are affected by the randomness of human behavior. On the other hand, both types of reattempts may have a different importance for the network and consequently go through different admission procedures. Therefore, both types of reattempts have different characteristics and consequently two separate reattempt blocks have to be considered.This model considers two arrival streams: new sessions and handovers from adjacent cells. Both arrivals are considered to be Poisson processes with ratesλn and λh, respectively, with λ=λn+λh. Those arrivals try to access a finite number of servers C. When a user is served, he/she holds the resource during an exponentially distributed time with rate μ (channel holding time). When an incoming new session is blocked, it joins the redial orbit with probability (1-Pin1) or leaves the system with probability Pin1. If a redial is not successful, then the session returns to the redial orbit with probability (1-Pin), redialing after an exponentially distributed time with rate μred. Likewise, Pih1, Pih, and μret are the analogous parameters for automatic retrials.In general, blocking a new session setup is considered to be less harmful than blocking a handover attempt. Thus we include an admission control policy to guarantee the prioritization of handovers—and retrials—over new sessions—and their associated redials. The technique used is known as the Fractional Guard Channel (FGC) admission control policy that is characterized by only one parametert (0≤t≤C). New sessions and redials are accepted with probability 1 when there are less than L=⌊t⌋ resources being used and with probability f=t-L, when there are exactly L resources in use. If there are more than L busy resources, then new sessions and redials are no longer accepted. Handovers and automatic retrials are only rejected when the system is completely occupied.LetX(t)=(X1(t),X2(t),X3(t)) be the process associated with the original model whose state space is given by 𝒮:={(x1,x2,x3):x1=0,1,…,C;x2∈ℤ+;x3∈ℤ+}, where X1(t) is the number of sessions being served, X2(t) the number of new sessions redialing, and X3(t) the number of handovers in the retrial orbit.  Let x=(x1,x2,x3)∈𝒮 and let ei,i=1,2,3, be a 3-dimensional vector whose ith component is 1 and the rest are 0. The transitions (and their rates) from x are as follows.Arrivals correspond to transitions of the formx→x+ei whose transition rate (λi(x)) is given as(2.1)λ1(x)=λ1(x1)={λifx1≤L-1,λh+fλnifx1=L,λhifL<x1<C,0ifx1=C,λ2(x)=λ2(x1)={0ifx1<L,λn(1-Pin1)(1-f)ifx1=L,λn(1-Pin1)ifx1>L,λ3(x)=λ3(x1)={0ifx1<C,λh(1-Pih1)ifx1=C.Departures correspond to transitions of the formx→x-ei whose transition rate (μi(x)) is given as (2.2)μ1(x)=x1μ,μ2(x)=x2β2(x1)=x2·{0ifx1<L,μred(1-f)Pinifx1=L,μredPinifx1>L,μ3(x)=x3β3(x1)=x3·{0ifx1<C,μretPihifx1=C.Successful reattempts correspond to transitions of the formx→x-ei+ej whose transition rate (ai,j(x)) is given as(2.3)a2,1(x)=x2α2,1(x1)=x2·{μredifx1≤L-1,μredfifx1=L,0ifx1>L,a3,1(x)=x3α3,1(x1)=x3·{μretifx1<C,0ifx1=C.The processX(t) is clearly a migration process since the only possible transitions are of the form x→x±ei or x→x-ei+ej.


## 3. On the Convergence of the Doubly Truncated Process

Let us denote byX(N)(t) a truncated version of X(t) where the number of customers in the retrial orbit is bounded by N. Likewise, let X(M,N)(t) be a doubly truncated version of X(t) where the number of customers in the redial orbit is bounded by M and the number of customers in the retrial orbit is bounded by N. In other words, X(M,N)(t) is a truncation of X(N)(t). The state spaces of X(N)(t) and X(M,N)(t) are, respectively, given by(3.1)𝒮(N):={(x1,x2,x3):0≤x1≤C;x2∈ℤ+;0≤x3≤N},𝒮(M,N):={(x1,x2,x3):0≤x1≤C;0≤x2≤M;0≤x3≤N}.
Note that 𝒮(M,N)⊂𝒮(N)⊂𝒮.Obviously,X(N)(t) and X(M,N)(t) are also migration processes and their transition rates are as given below. For the sake of conciseness, in the following definitions we used the indicator function 𝕀{·}, and it must be considered that x∈𝒮(N) or x∈𝒮(M,N) as appropriate. Arrivals’ transition rates are given as(3.2)λ1(M,N)(x)=λ1(N)(x)=λ1(x),λ2(M,N)(x)=𝕀{x2<M}λ2(N)(x),λ2(N)(x)=λ2(x),λ3(M,N)(x)=λ3(N)(x)=𝕀{x3<N}λ3(x).
Departures’ transition rates are given as(3.3)μ1(M,N)(x)=μ1(N)(x)=μ1(x),μ2(M,N)(x)=μ2(N)(x)=μ2(x),μ3(M,N)(x)=μ3(N)(x)=μ3(x).
Successful reattempts’ transition rates are given as(3.4)a2,1(M,N)(x)=a2,1(N)(x)=a2,1(x),a3,1(M,N)(x)=a3,1(N)(x)=a3,1(x).The two pairs of processes(X(M,N)(t),X(M+1,N)(t)) and (X(M,N)(t),X(N)(t)) fulfill the hypotheses of [2, Statement 12; page 114]—to be more precise, it should be noted that we are using the writing of the hypotheses given in [12]. This condition is verified as shown below.Firstly, the hypotheses of Statement12 are rewritten particularized to the processes of our interest: X(M,N)(t) and X(M+1,N)(t).Letx∈𝒮(M,N) and x′∈𝒮(M+1,N) such that x≤x′ (coordinatewise). Then we define the following:(3.5)I(x,x′):={i∈{1,2,3}∣xi=xi′},Jλi(x,x′):={j∈I(x,x′)∖{i}∣aj,i(M,N)(x)>aj,i(M+1,N)(x)},J̃λi(x,x′):=Jλi(x,x′)∪{j∣xj<xj′},Jμi(x,x′):={j∈I(x,x′)∖{i}∣ai,j(M,N)(x)<ai,j(M+1,N)(x)},J̃μi(x,x′):=Jμi(x,x′)∪{j∣xj<xj′}.
Now, it has to be shown that, for any x∈𝒮(M,N) and x′∈𝒮(M+1,N) such that x≤x′ and for all i∈I(x,x′), the following inequalities hold:(3.6)λi(M,N)(x)+∑j∈J̃λi(x,x′)aj,i(M,N)(x)‍≤λi(M+1,N)(x′)+∑j∈J̃λi(x,x′)‍aj,i(M+1,N)(x′),(3.7)μi(M,N)(x)+∑j∈J̃μi(x,x′)‍ai,j(M,N)(x)≥μi(M+1,N)(x′)+∑j∈J̃μi(x,x′)ai,j(M+1,N)(x′).Note thata1,2(M,N)(x)=a3,2(M,N)(x)=a1,3(M,N)(x)=a2,3(M,N)(x)=0, and therefore Jλ2(x,x′)=Jλ3(x,x′)=Jμ1(x,x′)=∅. Moreover, if x1=x1′ (i.e., 1∈I(x,x′)), then since xi≤xi′ we have that aj,1(M,N)(x)=xjαj,1(x1)≤xj′αj,1(x1′)=aj,1(M+1,N)(x′) for j=2,3, and hence Jλ1(x,x′)=∅. Likewise, since αj,1(x1)≥αj,1(x1′) if x1≤x1′, when xj=xj′ (j=2 or j=3) we have that(3.8)aj,1(M,N)(x)=xjαj,1(x1)≥xj′αj,1(x1′)=aj,1(M+1,N)(x′),
and hence Jμ2(x,x′)=Jμ3(x,x′)=∅.By the above, for anyx∈𝒮(M,N) and x′∈𝒮(M+1,N) such that x≤x′, (3.6) and (3.7) become as follows.(i)
Ifx1=x1′, then
(3.9)λ1(M,N)(x)+∑j=2,3‍𝕀{xj<xj′}aj,1(M,N)(x)≤λ1(M+1,N)(x′)+∑j=2,3‍𝕀{xj<xj′}aj,1(M+1,N)(x′),(3.10)μ1(M,N)(x)≥μ1(M+1,N)(x′).(ii)
Ifx2=x2′, then
(3.11)λ2(M,N)(x)≤λ2(M+1,N)(x′),(3.12)μ2(M,N)(x)+𝕀{x1<x1′}a2,1(M,N)(x)≥μ2(M+1,N)(x′)+𝕀{x1<x1′}a2,1(M+1,N)(x′).(iii)
Ifx3=x3′, then
(3.13)λ3(M,N)(x)≤λ3(M+1,N)(x′),(3.14)μ3(M,N)(x)+𝕀{x1<x1′}a3,1(M,N)(x)≥μ3(M+1,N)(x′)+𝕀{x1<x1′}a3,1(M+1,N)(x′).Note that for each pair(x,x′), depending on how many coordinates are equal, the number of inequalities to be fulfilled ranges from none to six. Below we check that (3.9)–(3.14) are indeed fulfilled as follows(i)
x1=x1′, (3.9): from λ1(M,N)(x)=λ1(x1)=λ1(x1′)=λ1(M+1,N)(x′) and recalling (3.8), the inequality is easily established.(ii)
x1=x1′, (3.10): μ1(M,N)(x)=x1μ=x1′μ=μ1(M+1,N)(x′).(iii)
x2=x2′, (3.11): λ2(M,N)(x)=λ2(x2)𝕀{x2<M}≤λ2(x2)𝕀{x2<M+1}=λ2(M+1,N)(x′)(iv)
x2=x2′, (3.12): dividing both sides by x2(=x2′>0)—if x2=0, then both sides are zero and (3.12) is fulfilled as an equality—we obtain(3.15)β2(x1)+𝕀{x1<x1′}α2,1(x1)≥β2(x1′)+𝕀{x1<x1′}α2,1(x1′).Ifx1=x1′, then the above inequality holds trivially. On the other hand, if x1<x1′, then it follows from the fact that β2(x1)+α2,1(x1) is nonincreasing in x1 as 1≥(1-f)Pin+f≥Pin. (i)
x3=x3′, (3.13): λ3(M,N)(x)=λ3(x1)≤λ3(x1′)=λ1(M+1,N)(x′).(ii)
x3=x3′, (3.14): the same argument used to establish (3.12), with subscript 2 replaced by 3, can be applied here.If the pair of processes under consideration areX(M,N)(t) and X(N)(t) (instead of X(M,N)(t) and X(M+1,N)(t)), then the verification of the hypotheses runs as before, except for checking the counterpart of (3.11), which has to be slightly modified as follows (recall that x2=x2′ applies):(3.16)λ2(M,N)(x)=λ2(x2)𝕀{x2<M}≤λ2(x2′)=λ2(N)(x′).On account of the abovementionedStatement, we have that(3.17)X(M,N)(t)≤stX(M+1,N)(t)≤stX(N)(t),
where ≤st denotes the strong stochastic ordering (see the monographs in [13, 14] for more details).Letπ(M,N)(x), π(N)(x), and π(x) denote the stationary probabilities of X(M,N)(t), X(N)(t), and X(t). It is easy to check that(3.18)π(M,N)(x)=π¯(x)+π¯(x+e1+e2)+π¯(x+e1+e3)+π¯(x+e2+e3)-π¯(x+e1)-π¯(x+e2)-π¯(x+e3)-π¯(x+e1+e2+e3),
where π¯(x)=∑x1′=x1C∑x2′=x2M∑x3′=x3Nπ(x′).By applying (3.17) and using (3.18) we can now proceed along the same lines that are in [2, Section 2.6.2] to conclude that limM→∞π(M,N)(x)=π(N)(x).Applying the same procedure as above (mutatis mutandis) to (X(N)(t),X(N+1)(t)) and (X(N)(t),X(t)) would yield that limN→∞π(N)(x)=π(x). Indeed, the latter is in essence the case addressed in [2, Section 2.6.2] with a single truncation. Moreover, a repetition of the same arguments (with modifications affecting only minor details) would lead to identical results if the order in which the orbits are truncated is inverted or if we first truncate one of the orbits and then apply a generalized truncation to the other. Thus, we finally conclude that limM,N→∞π(M,N)(x)=π(x).


## 4. Conclusions

The retrial phenomenon has been thoroughly studied in the last decades. It has been shown that, in general, to solve this type of systems we must resort to approximate models. However, almost all the papers that present some approximate models make the assumption that the approximation results converge to the exact ones of the original model. In this paper, we demonstrate the convergence of a family of finite truncated models to their original counterparts in a two-reattempt-orbit multiserver retrial queue. Moreover, the followed methodology can be used as a framework to show the convergence of other approximate models, like the generalized truncated models.



---

*Source: 580349-2010-09-07.xml*