# Transient and Stationary Losses in a Finite-Buffer Queue with Batch Arrivals

Authors: Andrzej Chydzinski; Blazej Adamczyk
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

We present an analysis of the number of losses, caused by the buffer overflows, in a finite-buffer queue with batch arrivals and autocorrelated interarrival times. Using the batch Markovian arrival process, the formulas for the average number of losses in a finite time interval and the stationary loss ratio are shown. In addition, several numerical examples are presented, including illustrations of the dependence of the number of losses on the average batch size, buffer size, system load, autocorrelation structure, and time.


---

## Body

## 1. Introduction

In a finite-buffer queueing system (i.e., a system with the finite waiting room), we should expect losses. Namely, jobs (customers) that arrive at the system when the buffer is full are rejected and lost. Naturally, in most applications of queueing systems, the losses are unwanted. This is especially true in telecommunications. A great part of today's telecommunication systems are based on packet-switched networks, where packets losses occur at buffers in network nodes. For instance, as many as 17% of packets are lost globally due to the buffer overflows in the Internet (observed on November 15th, 2011, see [1]). Therefore, an enormous amount of data has to be retransmitted.As we know, several characteristics of a finite-buffer queueing system can influence the number of losses. These are, for instance,(1)
the load of the system (traffic intensity),(2)
the buffer size,(3)
the variance of the service times,(4)
the variance of the interarrival times,(5)
the batch arrivals,(6)
the correlation of the interarrival times.The dependence of the number of losses on(1) and (2) is quite obvious. The dependence on (3)–(6) follows, for instance, from the results presented in [2–5], respectively. However, the queueing models considered in these papers do not take into account all of the aforementioned factors at the same time.The purpose of this paper is to find formulas describing the loss process in a finite-buffer queueing model that enables fitting all of characteristics(1)–(6). What is more, we want to describe the loss process both in the transient and stationary case and provide closed, easy to use, formulas for the loss process characteristics.To the best of the authors' knowledge, there are no previously published papers that fulfill these requirements. In particular, the influence of the system load, buffer size, and service time variance on the number of losses is studied in several classic queueing theory textbooks. However, the classic models (like M/G/1/N or G/M/1/N) and the classic methodology do not take into account the autocorrelation in the arrival process and the batch arrivals. Other studies [2, 6–8] do take into account the batch arrivals, but without the autocorrelation structure. Finally, some recent papers that incorporate the autocorrelation structure either do not consider the batch arrivals (like [5, 9–11]) or do not deal with the transient case (like [12]).As for the arrival process model, we have chosen the batch Markovian arrival process (BMAP) [13]. This is due to the following reasons. Firstly, the BMAP process allows us to model not only the batch arrivals, the variance of interarrival times, and  the correlation of interarrival times but also many other subtle characteristics of the arrival process (e.g., the correlation between the local intensity of arrivals of batches with the size of an arriving batch). Secondly, these modeling capabilities can be used in practice, due to the availability of a number of parameter fitting procedures for BMAPs [14–16]. Finally, the BMAP has a unique advantage of combining great complexity and modeling capabilities with the analytical tractability (for more information on BMAPs see [17] and the references given there).As for the methodology, we will exploit the framework from [5], which has been previously used for simpler Markovian processes (e.g., [18]). The main difference herein is batch structure of arrival process (not present in [5]) which causes some important complications of the method and the results.The methodology of [5] is used herein due to its ability to solve the transient case (in addition to the stationary one). Other known methods for finding loss characteristics in BMAP queues (e.g., [9, 12]) are devoted to the stationary case only. It is an open question whether they can be extended to cover the transient case as well. Certainly, such extensions would not be trivial.The remaining part of the paper is structured in the following way. In Section2, we first give the definition of the arrival process, as well as a few useful formulas for its basic characteristics. Secondly, we present a formal description of the queueing model and the nomenclature used in the paper. The main part of the paper, Section 3, then follows. Namely, it starts with the definition of the main characteristic of interest, which is the average number of losses in interval (0,t]. Then, this characteristic is derived by using the Laplace transform technique. Next, the transient intensity of the loss process is derived and some comments on how to use the obtained results in practice are presented. Finally, using the previous results, the stationary loss ratio is computed. In Section 4, a set of numerical results based on four different BMAPs are presented. In particular, the dependence of the loss ratio on the autocorrelation structure, on the batch size distribution, and on the buffer size in the steady-state, as well as the transient intensity of the loss process, are investigated. In Section 5, the remarks concluding the paper are gathered.


## 2. The Arrival Process and the Queueing Model

LetI denote the identity matrix; let  0 be a square matrix of zeroes and 1 the column vector of 1's.The batch Markovian arrival process (BMAP) is defined as a 2-dimensional Markov process(N(t),J(t))  on the state space {(i,j):i≥0,1≤j≤m} with an infinitesimal generator Q in the form
(2.1)Q=[D0D1D2D3··D0D1D2··D0D1·····],
where Dk, k≥0 are m×m matrices. Dk, k≥1 are nonnegative, D0 has nonnegative off-diagonal elements and negative diagonal elements and D=∑k=0∞Dk is an irreducible infinitesimal generator. It is assumed also that D≠D0.In this two-dimensional process,N(t) denotes the number of arrivals in (0,t], while J(t) denotes the state of the one-dimensional modulating Markov process at time t. The intensity matrix for the modulating process is equal to D. Its stationary distribution will be denoted by π, where πD=(0,…,0),  π1=1.The evolution of the BMAP process can be also described in the following manner. Given the modulating processJ is in some phase i; the sojourn time in that phase is exponentially distributed with parameter λi, where
(2.2)λi=-(D0)ii.
At the end of that sojourn time there occurs a transition to another phase and (or) an arrival of a batch. In particular, with probability pi(j,k) there will be a transition to phase k with a batch arrival of size j, where
(2.3)pi(0,i)=0,1≤i≤m,pi(0,k)=1λi(D0)ik,1≤i,k≤m,k≠i,pi(j,k)=1λi(Dj)ik,1≤i,k≤m,j≥1.Now we will give a few useful characteristics, the BMAP (see [12, 13]). First, the total arrival rate (including batch sizes) can be calculated as
(2.4)Λ=π∑k=1∞kDk1.
The arrival rate of batches (i.e., excluding batch sizes) can be computed as
(2.5)Λg=π(-D0)1.
The variance of the interarrival times is equal to
(2.6)Var=-2ΛgπD0-11-1Λg2.
The autocorrelation at lag k  of the sequence of interarrival times is
(2.7)Corr(k)=pD0-1C(Ck-1-1p)D0-1C1Var,
where
(2.8)C=-D0-1(D-D0),
and p  is the stationary vector for C-I, namely,p(C-I)=(0,…,0),p1=1.Finally, the counting function for the BMAP, which is defined as(2.9)Pi,j(n,t)=ℙ(N(t)=n,J(t)=j∣N(0)=0,J(0)=i),
has the following generating function:
(2.10)P*(z,t)=∑n=0∞P(n,t)zn=eD(z)t,D(z)=∑k=0∞zkDk,|z|≤1.This finishes the description of the arrival process.As for the queueing model, we deal herein with the simple single-server queueing system of finite capacity. Namely, the arrival process is the batch Markovian arrival process described above, the service time distribution is given by a distribution functionF(t)  (which may assume any form), and the service discipline is FIFO (FCFS). What is important is that the system capacity is finite and equal to N. This means that the total number of jobs in the system must not exceed N, including the service position. Jobs arriving when the system is full are lost and never return, as, usually, we assume that the service times are mutually independent and that they do not depend on the arrival process. Finally, we assume that  t=0  corresponds to a departure epoch.


## 3. Transient and Stationary Losses

In the sequel,X(t)  denotes the queue size at time t (including service position, if occupied), L(t) denotes the number of jobs lost in time interval (0,t], and Δn,i(t) denotes its average value assuming X(0)=n  and  J(0)=i, that is,
(3.1)Δn,i(t)=𝔼(L(t)∣X(0)=n,J(0)=i).First of all, we want to find a formula for the Laplace transform ofΔn,i(t):
(3.2)δn,i(s)=∫0∞e-stΔn,i(t)dt.
For that purpose, we will use two systems of integral equation for Δn,i(t).Namely, assuming that the queue is not empty att=0  and using the law of total probability with respect to the first service completion moment we obtain the following set of integral equations:
(3.3)Δn,i(t)=∑j=1m∑k=0N-n-1∫0tΔn+k-1,j(t-u)Pi,j(k,u)dF(u)+∑j=1m∑k=N-n∞∫0t(k-N+n+ΔN-1,j(t-u))Pi,j(k,u)dF(u)+(1-F(t))∑j=1m∑k=N-n∞(k-N+n)Pi,j(k,t),n=1,…,N;i=1,…,m.System (3.3) can be explained by naming all the mutually exclusive events used in (3.3). In particular, the first summand after the equality sign corresponds to the event where the first service completion time, u, occurs before t, and there are no losses by the time u. The second summand after the equality sign corresponds to the event where the first service completion time, u, occurs before t, and there are some losses by the time u. The third summand corresponds to the event where the first service completion time is after t.Assuming that the queue is empty att=0, we can obtain another system of integral equations:
(3.4)Δ0,i(t)=∑j=1m∑k=0N∫0tΔk,j(t-u)pi(k,j)λie-λiudu+∑j=1m∑k=N+1∞∫0t(k-N+ΔN,j(t-u))pi(k,j)λie-λiudu,i=1,…,m.Now, the first summand after the equality sign in (3.4) corresponds to the event where the arrival of the first batch to an empty queue occurs in time u, u<t, and the size of this arriving batch does not exceed N. Therefore, there are no losses connected with the arrival of the first batch. The second summand corresponds to the event where the arrival of the first batch to an empty queue occurs in time u, u<t; the size of the arriving batch exceeds the capacity of the system and causes a loss of k-N jobs. Finally, note that the absent third summand, corresponding to the event where the first arrival of a batch occurs after time t, is not necessary—there are no losses in (0,t] in such a case. After simple algebraic manipulations from (3.4) we get
(3.5)Δ0,i(t)=∑j=1m∑k=0N∫0tΔk,j(t-u)pi(k,j)λie-λiudu+∑j=1m∑k=N+1∞∫0tΔN,j(t-u)pi(k,j)λie-λiudu+(1-e-λit)∑j=1m∑k=1∞kpi(N+k,j),i=1,…,m.Applying the Laplace transform to (3.3) and (3.5) and employing matrix notation we obtain
(3.6)δn(s)=∑k=0N-n-1Ak(s)δn+k-1(s)+∑k=N-n∞Ak(s)δN-1(s)+cn(s),n=1,…,N,δ0(s)=∑k=0NYk(s)δk(s)+∑k=N+1∞Yk(s)δN(s)+∑k=1∞YN+k(s)skYN+k(s)s·1,
where δn(s)  and  ck(s)  are the following column vectors:
(3.7)δn(s)=(δn,1(s),…,δn,m(s))T,ck(s)=1s∑i=N-k∞(i-N+k)Ai(s)·1+∑i=N-k∞(i-N+k)Ei(s)·1,
while Yk(s), Ak(s),  and Ek(s)  are the following m×m  matrices:
(3.8)Yk(s)=[λipi(k,j)s+λi]i,j,(3.9)Ak(s)=[∫0∞e-stPi,j(k,t)dF(t)]i,j,(3.10)Ek(s)=[∫0∞e-stPi,j(k,t)(1-F(t))dt]i,j.Now we will solve the system (3.6). Firstly, by changing the indices numeration into
(3.11)δ~n(s)=δN-n(s),
we get
(3.12)∑k=-1nAk+1(s)δ~n-k(s)-δ~n(s)=ψn(s),n=0,…,N-1,(3.13)δ~N(s)=∑k=0NYN-k(s)δ~k(s)+∑k=N+1∞Yk(s)δ~0(s)+x(s),
with
(3.14)ψn(s)=An+1(s)δ~0(s)-∑k=n+1∞Ak(s)δ~1(s)-cN-n(s),x(s)=∑k=1∞kYN+k(s)s·1.
Thanks to Lemma  3.2.1 of [19], we know that the   general solution of system (3.12) has the form
(3.15)δ~n(s)=Rn+1(s)C(s)+∑k=0nRn-k(s)ψk(s),
where
(3.16)R0(s)=0,R1(s)=A0-1(s),Rk+1(s)=A0-1(s)(Rk(s)-∑i=0kAi+1(s)Rk-i(s)),k=1,2…,
and C(s)  is a column vector that does not depend on n.Formula (3.12) for n=0  gives
(3.17)∑k=0∞Ak(s)δ~1(s)-δ~0(s)=-cN(s),
and, as a consequence,
(3.18)ψn(s)=An+1(s)δ~0(s)-∑k=n+1∞Ak(s)A¯0-1(s)(δ~0(s)-cN(s))-cN-n(s)=Bn(s)δ~0(s)+A¯n+1(s)(A¯0)-1(s)cN(s)-cN-n(s),
with
(3.19)A¯n(s)=∑k=n∞Ak(s),Bn(s)=An+1(s)-A¯n+1(s)(A¯0(s))-1.
On the other hand, formula (3.15) for n=0  gives
(3.20)C(s)=A0(s)δ~0(s).
Now, putting (3.15), (3.18), and (3.20) into (3.13) we get the following equation for δ~0(s):
(3.21)RN+1(s)A0(s)δ~0(s)+∑k=0NRN-k(s)(Bk(s)δ~0(s)+A¯k+1(s)(A¯0(s))-1cN(s)-cN-k(s))=∑k=0NYN-k(s)[Rk-l(s)(Bl(s)δ~0(s)+A¯l+1(s)(A¯0(s))-1cN(s)-cN-l(s))]Rk+1(s)A0(s)δ~0(s)YN-k(s)]+∑l=0kRk-l(s)(Bl(s)δ~0(s)+A¯l+1(s)(A¯0(s))-1cN(s)-cN-l(s))]+∑k=N+1∞Yk(s)δ~0(s)+x(s).
Solving this equation with respect to δ~0(s)  we obtain
(3.22)δ~0(s)=QN-1(s)qN(s),
where
(3.23)QN(s)=RN+1(s)A0(s)+∑k=0NRN-k(s)Bk(s)-∑k=0NYN-k(s)Rk+1(s)A0(s)-∑k=0N∑l=0kYN-k(s)Rk-l(s)Bl(s)-∑k=N+1∞Yk(s),qN(s)=∑k=0N∑l=0kYN-k(s)Rk-l(s)[A¯l+1(s)(A¯0(s))-1cN(s)-cN-l(s)]-∑k=0NRN-k(s)[A¯k+1(s)(A¯0(s))-1cN(s)-cN-k(s)]+x(s).Finally, rewriting (3.15) with (3.20) and (3.22) we have proven the following theorem.Theorem 3.1.
The Laplace transform of the average number of losses in(0,t] in a finite-capacity queue with the batch Markovian arrivals is equal to
(3.24)δn(s)=RN-n+1(s)A0(s)QN-1(s)qN(s)+∑k=0N-nRN-n-k(s)[Bk(s)QN-1(s)qN(s)+A¯k+1(s)(A¯0(s))-1cN(s)-cN-k(s)].It should be stressed that (3.24) can be easily used to obtain numerical results. It is connected with the fact that all the matrices and vectors that appear in (3.24) are either simple functions of the BMAP parameters, or simple functions of matrices Ak(s) and Ek(s) defined in (3.9) and (3.10), respectively. Fortunately, matrices (3.9) and (3.10) are well known in the theory of BMAPs and can be computed using, for instance, formulas (65)–(67) from [13]. Finally, for practical purposes we are rather interested in Δn,i(t) than in its Laplace transform. To obtain originals from (3.24), one of the many available Laplace inversion formulas can be used. We use and recommend the formula based on the Euler summation. It can be found in [20].Theorem3.1 describes the average number of losses in (0,t] interval. We may also be interested in the local intensity of the loss process. It can be obtained simply by differentiating Δn,i(t). Namely, denoting the local loss intensity by Kn,i(t),
(3.25)Kn,i(t)=dΔn,i(t)dt,Kn(t)=(Kn,1(t),…,Kn,m(t))T,
its Laplace transform by κn(t),
(3.26)κn(s)=∫0∞e-stKn(t)dt,
and using the properties of the Laplace transform we obtain the following corollary.Corollary 3.2.
The Laplace transform of the transient intensity of the loss process in a finite-capacity queue with the batch Markovian arrivals is equal to(3.27)κn(s)=sδn(s),
where δn(s)  is given in (3.24).Naturally, the numerical values ofKn(t) can be obtained in the same way as described below Theorem 3.1.Now, Theorem3.1 and Corollary 3.2 describe the transient behaviour of the loss process. However, they can be also exploited to obtain stationary characteristics. The most important stationary characteristic is the loss ratio, L, defined as a long-run fraction of jobs that were lost. The loss ratio can be obtained using the following limit
(3.28)L=limt→∞Kn,i(t)Λ.Instead of computingKn,i(t), we can obtain this limit directly from (3.24), using the properties of the Laplace transform again. As the limit depends neither on n  nor i, we can use, for instance, n=N  and i=1. From (3.22) it follows that
(3.29)δN(s)=QN-1(s)qN(s)·(1,0…,0),
which gives the following corollary.Corollary 3.3.
The stationary loss ratio in a finite-capacity queue with the batch Markovian arrivals is equal to(3.30)L=lims→0+s2QN-1(s)qN(s)·(1,0…,0)Λ.Note that (3.30) can be used to obtain quickly the numerical value of L, without applying the transform inversion.


## 4. Numerical Examples

### 4.1. Example 1

In the first example we will see how the stationary loss ratio varies with the traffic intensity, autocorrelation structure, and the buffer size. For that purpose, we will consider three arrival processes (all of them have the same average batch size and the total arrival rate, but differ in the autocorrelation structure).B
M
A
P
1

: this is in fact a simple batch Poisson process, with batch arrivals of size 1, 4, and 10, p1=2/30,  p4=7/30, p10=21/30,  and the rate of batch arrivals of 0.125. It is easy to check that the average batch size is 8, and the total arrival rate is 1. The batch Poisson process is chosen here as an example of BMAP with no autocorrelation, that is, Corr(k)≡0.B
M
A
P
2

: It is parameterized by the following matrices:
(4.1)D0=[-5.699200.2440770.02440770.00244077-0.5699200.02440770.0002440770.00244077-0.0569920],D1=[0.008135900.06508720.6508720.06508720.00008135900.007240950.006346000.0008135900.0000813590],D4=[0.008135900.06508720.6508720.06508720.00008135900.007240950.006346000.0008135900.0000813590],D10=[0.04474750.3579803.579800.3579800.0004474750.03982520.03490300.004474750.000447475].Again, we have batch arrivals of size 1, 4, and 10. The matrices were carefully chosen so that the average batch size is 8 and the total arrival rate is 1 again. However, we have now a correlation between interarrival times. The autocorrelation function forBMAP2 is depicted in Figure 1. As we can see, this is an example of the autocorrelation with alternating signs.Figure 1
The autocorrelation at lagk of the sequence of interarrival times in BMAP2.B
M
A
P
3

: It is parameterized by the following matrices:
(4.2)D0=[-0.04995140.003997150.001289400.00528656-0.07743340.005286560.001418340.00141834-0.274511],D1=[0.01818060.001418340.002707750.001418340.003997150.002707750.002707750.003997150.00657596],D4=[0.001418340.002707750.001418340.001418340.04138990.001418340.005286560.001418340.00270775],D10=[0.004836820.007140070.004836820.002533570.009443320.002533570.0071400700.241841].As in the previous processes, the matrices were chosen so that the average batch size is 8 and the total arrival rate is 1. This time we have a strong positive autocorrelation between interarrival times. The autocorrelation function forBMAP3 is depicted in Figure 2.Figure 2
The autocorrelation at lagk of the sequence of interarrival times in BMAP3.As for the service process, we assume that the service time is constant and denoted byd. Therefore, manipulating d we can manipulate the load of the system, that is,
(4.3)ρ=Λd.The system capacityN=50 is assumed. Now we can present numerical results.Firstly, in Table1 the loss ratio for the three considered BMAPs and three distinct loads of the system is presented. As expected, the highest values of the loss ratio are obtained for high  ρ and positively autocorrelated BMAP. A more surprising thing is that even for a very low load (0.5), we can obtain a very high loss ratio (9.2%). Another interesting observation is that the loss ratio for BMAP2, that is, in the case of alternating autocorrelation, is much higher than in the case of flat autocorrelation (BMAP1). The detailed dependence of the loss ratio on the system load for the three considered BMAPs is depicted in Figure 3.Table 1
The loss ratio for different arrival processes and system loadsN=50.
Arrival process
ρ
=
0.5
ρ
=
1
ρ
=
1.5
BMA
P
1
0.000870
0.087475
0.335441
BMA
P
2
0.028960
0.173523
0.361348
BMA
P
3
0.092648
0.324134
0.454306Figure 3
The loss ratio versus the load of the system.N=50.Secondly, in Figures4, 5, and 6 the loss ratio as a function of the system capacity is presented for ρ=0.5, ρ=1, and ρ=1.5, respectively. As we can see, the loss ratio decreases exponentially with the buffer size for ρ<1 and subexponentially for ρ=1. A very interesting fact is that the BMAP2 and BMAP3 curves cross somewhere in the interval (10,20). This means that if the system capacity is, for instance, 10, then BMAP2 causes more losses than BMAP3. On the other hand, if the system capacity is 30, then BMAP3 causes more losses than BMAP2. This counterintuitive behaviour can be explained by computing the variances of the interarrival times for both processes. We obtain Var2=208.75 and Var3=151.49, that is, BMAP2 has a greater variance than BMAP3. For small N, the impact of the variance on the loss ratio prevails and we observe more losses in the BMAP2 case. On the other hand, for large N, the autocorrelation prevails and more losses are caused by BMAP3.Figure 4
The loss ratio versus the capacity of the system.ρ=0.5.Figure 5
The loss ratio versus the capacity of the system.ρ=1.Figure 6
The loss ratio versus the capacity of the system.ρ=1.5.


### 4.2. Example 2

In the second example we want to observe the dependence of the loss ratio on the average batch size. For this purpose, we consider familyBMAP4(k) of BMAPs. In this family we have BMAPs with batch arrivals of size  k, 2k,  3k.B
M
A
P
4
(
k
)

: is parameterized by the following matrices:
(4.4)D0=[-0.3873610.009582780.003091220.0126740-0.3842790.01267400.003400340.00340034-0.832092],Dk=[0.2508600.01957070.03736220.01957070.05515370.03736220.03736220.05515370.0907367],D2k=[0.006800680.01298310.006800680.006800680.1984560.006800680.02534800.006800680.0129831],D3k=[0.01159580.01711760.01159580.006073990.02263940.006073990.017117600.579790].The average batch size forBMAP4(k) is β=2k; the total arrival rate is k. As we want to maintain the same load, ρ=1, for every BMAP4(k), we have to scale the service time to 1/k.The resulting loss ratio as a function of the average batch size is depicted in Figure7. The results were computed for two system capacities, N=20 and N=50. For other values of ρ, the shape of this function is similar, except for the fact that it becomes more flat as ρ grows and vice versa.Figure 7
The loss ratio versus the average batch size for two different system capacities.


### 4.3. Example 3

In the third example we will present the transient characteristics of the loss process.BMAP3 with ρ=0.9 and N=50 will be used. Naturally, in the transient case the loss characteristics depend on the initial queue length, n, and the initial phase of the modulating process, i.In Figure8, the average number of losses in (0,t] is presented as a function of t in five cases, when the initial queue size is 0, 10, 25, 40, and 50 jobs. In every case initial i=3 was set. For the visual interpretation, it is easier to use the transient intensity of the loss process, Kn,i(t). In Figure 9 this intensity is depicted in time for all three values of the initial phase of the modulating process. In every case initial n=0 was set (empty system). Two interesting observations can be made using Figure 9. Firstly, for some initial conditions, the intensity of the loss process may not change monotonically. Here for i=3 we have a maximum at t around 40 s. Secondly, we can tell more or less when the transient period is finished. Namely, after about 200 s, the loss intensity gets very close to the stationary value (which is L=0.288951), no matter what the initial i  was.Figure 8
The average number of losses in(0,t] as a function of t for n=0,10,25,40,  and 50.Figure 9
The intensity of the loss process in time fori=1, 2, and 3.


### 4.4. Example4

In order to check the analytical results for possible mistakes, we have also performed a number o simulations and compared the simulation and the analytical results. For that purpose OMNeT++ discrete event simulator [21] was used. All the BMAPs appearing in Examples1–3 were simulated; the service time was set to 1, the system capacitywas set to 50. In each simulation run, 108 jobs passing through the queueing system were simulated. The results are gathered in Table 2. As we can see, the analytical results agree very well with simulations.Table 2
The loss ratios obtained from analysis and simulations.
Arrival process
Analytical results
Simulation results
BMA
P
1
0.087475
0.087430
BMA
P
2
0.173523
0.173378
BMA
P
3
0.324134
0.324022
BMA
P
4(1)
0.060252
0.060328


## 4.1. Example 1

In the first example we will see how the stationary loss ratio varies with the traffic intensity, autocorrelation structure, and the buffer size. For that purpose, we will consider three arrival processes (all of them have the same average batch size and the total arrival rate, but differ in the autocorrelation structure).B
M
A
P
1

: this is in fact a simple batch Poisson process, with batch arrivals of size 1, 4, and 10, p1=2/30,  p4=7/30, p10=21/30,  and the rate of batch arrivals of 0.125. It is easy to check that the average batch size is 8, and the total arrival rate is 1. The batch Poisson process is chosen here as an example of BMAP with no autocorrelation, that is, Corr(k)≡0.B
M
A
P
2

: It is parameterized by the following matrices:
(4.1)D0=[-5.699200.2440770.02440770.00244077-0.5699200.02440770.0002440770.00244077-0.0569920],D1=[0.008135900.06508720.6508720.06508720.00008135900.007240950.006346000.0008135900.0000813590],D4=[0.008135900.06508720.6508720.06508720.00008135900.007240950.006346000.0008135900.0000813590],D10=[0.04474750.3579803.579800.3579800.0004474750.03982520.03490300.004474750.000447475].Again, we have batch arrivals of size 1, 4, and 10. The matrices were carefully chosen so that the average batch size is 8 and the total arrival rate is 1 again. However, we have now a correlation between interarrival times. The autocorrelation function forBMAP2 is depicted in Figure 1. As we can see, this is an example of the autocorrelation with alternating signs.Figure 1
The autocorrelation at lagk of the sequence of interarrival times in BMAP2.B
M
A
P
3

: It is parameterized by the following matrices:
(4.2)D0=[-0.04995140.003997150.001289400.00528656-0.07743340.005286560.001418340.00141834-0.274511],D1=[0.01818060.001418340.002707750.001418340.003997150.002707750.002707750.003997150.00657596],D4=[0.001418340.002707750.001418340.001418340.04138990.001418340.005286560.001418340.00270775],D10=[0.004836820.007140070.004836820.002533570.009443320.002533570.0071400700.241841].As in the previous processes, the matrices were chosen so that the average batch size is 8 and the total arrival rate is 1. This time we have a strong positive autocorrelation between interarrival times. The autocorrelation function forBMAP3 is depicted in Figure 2.Figure 2
The autocorrelation at lagk of the sequence of interarrival times in BMAP3.As for the service process, we assume that the service time is constant and denoted byd. Therefore, manipulating d we can manipulate the load of the system, that is,
(4.3)ρ=Λd.The system capacityN=50 is assumed. Now we can present numerical results.Firstly, in Table1 the loss ratio for the three considered BMAPs and three distinct loads of the system is presented. As expected, the highest values of the loss ratio are obtained for high  ρ and positively autocorrelated BMAP. A more surprising thing is that even for a very low load (0.5), we can obtain a very high loss ratio (9.2%). Another interesting observation is that the loss ratio for BMAP2, that is, in the case of alternating autocorrelation, is much higher than in the case of flat autocorrelation (BMAP1). The detailed dependence of the loss ratio on the system load for the three considered BMAPs is depicted in Figure 3.Table 1
The loss ratio for different arrival processes and system loadsN=50.
Arrival process
ρ
=
0.5
ρ
=
1
ρ
=
1.5
BMA
P
1
0.000870
0.087475
0.335441
BMA
P
2
0.028960
0.173523
0.361348
BMA
P
3
0.092648
0.324134
0.454306Figure 3
The loss ratio versus the load of the system.N=50.Secondly, in Figures4, 5, and 6 the loss ratio as a function of the system capacity is presented for ρ=0.5, ρ=1, and ρ=1.5, respectively. As we can see, the loss ratio decreases exponentially with the buffer size for ρ<1 and subexponentially for ρ=1. A very interesting fact is that the BMAP2 and BMAP3 curves cross somewhere in the interval (10,20). This means that if the system capacity is, for instance, 10, then BMAP2 causes more losses than BMAP3. On the other hand, if the system capacity is 30, then BMAP3 causes more losses than BMAP2. This counterintuitive behaviour can be explained by computing the variances of the interarrival times for both processes. We obtain Var2=208.75 and Var3=151.49, that is, BMAP2 has a greater variance than BMAP3. For small N, the impact of the variance on the loss ratio prevails and we observe more losses in the BMAP2 case. On the other hand, for large N, the autocorrelation prevails and more losses are caused by BMAP3.Figure 4
The loss ratio versus the capacity of the system.ρ=0.5.Figure 5
The loss ratio versus the capacity of the system.ρ=1.Figure 6
The loss ratio versus the capacity of the system.ρ=1.5.


## 4.2. Example 2

In the second example we want to observe the dependence of the loss ratio on the average batch size. For this purpose, we consider familyBMAP4(k) of BMAPs. In this family we have BMAPs with batch arrivals of size  k, 2k,  3k.B
M
A
P
4
(
k
)

: is parameterized by the following matrices:
(4.4)D0=[-0.3873610.009582780.003091220.0126740-0.3842790.01267400.003400340.00340034-0.832092],Dk=[0.2508600.01957070.03736220.01957070.05515370.03736220.03736220.05515370.0907367],D2k=[0.006800680.01298310.006800680.006800680.1984560.006800680.02534800.006800680.0129831],D3k=[0.01159580.01711760.01159580.006073990.02263940.006073990.017117600.579790].The average batch size forBMAP4(k) is β=2k; the total arrival rate is k. As we want to maintain the same load, ρ=1, for every BMAP4(k), we have to scale the service time to 1/k.The resulting loss ratio as a function of the average batch size is depicted in Figure7. The results were computed for two system capacities, N=20 and N=50. For other values of ρ, the shape of this function is similar, except for the fact that it becomes more flat as ρ grows and vice versa.Figure 7
The loss ratio versus the average batch size for two different system capacities.


## 4.3. Example 3

In the third example we will present the transient characteristics of the loss process.BMAP3 with ρ=0.9 and N=50 will be used. Naturally, in the transient case the loss characteristics depend on the initial queue length, n, and the initial phase of the modulating process, i.In Figure8, the average number of losses in (0,t] is presented as a function of t in five cases, when the initial queue size is 0, 10, 25, 40, and 50 jobs. In every case initial i=3 was set. For the visual interpretation, it is easier to use the transient intensity of the loss process, Kn,i(t). In Figure 9 this intensity is depicted in time for all three values of the initial phase of the modulating process. In every case initial n=0 was set (empty system). Two interesting observations can be made using Figure 9. Firstly, for some initial conditions, the intensity of the loss process may not change monotonically. Here for i=3 we have a maximum at t around 40 s. Secondly, we can tell more or less when the transient period is finished. Namely, after about 200 s, the loss intensity gets very close to the stationary value (which is L=0.288951), no matter what the initial i  was.Figure 8
The average number of losses in(0,t] as a function of t for n=0,10,25,40,  and 50.Figure 9
The intensity of the loss process in time fori=1, 2, and 3.


## 4.4. Example4

In order to check the analytical results for possible mistakes, we have also performed a number o simulations and compared the simulation and the analytical results. For that purpose OMNeT++ discrete event simulator [21] was used. All the BMAPs appearing in Examples1–3 were simulated; the service time was set to 1, the system capacitywas set to 50. In each simulation run, 108 jobs passing through the queueing system were simulated. The results are gathered in Table 2. As we can see, the analytical results agree very well with simulations.Table 2
The loss ratios obtained from analysis and simulations.
Arrival process
Analytical results
Simulation results
BMA
P
1
0.087475
0.087430
BMA
P
2
0.173523
0.173378
BMA
P
3
0.324134
0.324022
BMA
P
4(1)
0.060252
0.060328


## 5. Conclusions

In this paper we presented transient and stationary characterizations of the loss process in a finite-buffer queue fed by the batch Markovian arrivals. Due to the flexibility of the arrival process, the obtained results enable modeling of losses in many real-life queueing systems, with several properties influencing the number of losses, for example, the autocorrelation function, the batch size distribution, the interarrival time variance, and others.The analytical results were presented in closed, easy to use formulas and accompanied by sample numerical calculations, demonstrating their applicability.



---

*Source: 326830-2012-12-17.xml*