# An Erlang Loss Queue with Time-Phased  Batch Arrivals as a Model for Traffic Control in Communication Networks

Authors: Moon Ho Lee; Sergey A. Dudin
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

A multiserver queueing model that does not have a buffer but has batch
arrival of customers is considered. In contrast to the standard batch arrival,
in which the entire batch arrives at the system during a single epoch, we
assume that the customers of a batch (flow) arrive individually in exponentially
distributed times. The service time is exponentially distributed.
Flows arrive according to a stationary Poisson arrival process. The flow size
distribution is geometric. The number of flows that can be simultaneously
admitted to the system is under control. The loss of any customer from
an admitted flow, with a fixed probability, implies termination of the flow
arrival. Analysis of the sojourn time and loss probability of an arbitrary
flow is performed.


---

## Body

## 1. Introduction

Queueing  systems effectively describe the operations
of channels and servers of many communication networks, and they have received
a great deal of attention in the probabilistic literature, beginning with the
pioneering works by the Danish mathematician and engineer A. K. Erlang. A
celebration of the 100 year jubilee of the origin of queueing theory will be
held in 2009. Erlang's famous loss formula for the customer loss probability
for the systemM/M/N/0 0 served as the basis for capacity planning
and performance evaluation of telecommunication networks for an entire century. Sevastjanov proved in [1] that this loss formula is valid for the more general
queueing system M/G/N/0 as well. In [2–4], analysis of Erlang's model
was extended to the system with (batch Markovian arrival process) BMAP.It was assumed in [2–4] that customers can arrive in batches of random size,
with the standard assumption that, during a batch arrival epoch, all batch
customers arrive at the system simultaneously. However, nowadays, it is a
typical feature of many communication networks, IP networks in
particular, that customers arrive in batches, but the arrival of customers of a
batch is not instantaneous. To distinguish the standard batches from the
batches considered in this paper the latter ones are named flows. The first
customer of a flow arrives during the flow arrival epoch, while the rest of the
customers arrive individually during random intervals. The flow size is random,
and it may not be known a priori during the flow arrival epoch. Such a
situation is typical, for example, in modeling transmission of video and
multimedia information. This situation is also discussed in [5] with respect to the modeling
scheme of alternative packet overflow routing in IP networks. In this scheme, the flow represents
a set of packets that must be sequentially routed in the same channel. When a
packet arrives, it is determined (e.g., by means of IP address) if the
packet is a part of a flow previously tracked. If the packet belongs to an
existing flow, the packet is marked for transmission. If the flow has not yet
been tracked and the buffer and channel capacity is still available, the packet
is admitted to the system and the flow count is increased. Otherwise, the flow
is routed on an overflow link (or is dropped) and the packet is rejected in the
considered channel. Tracked flows are cleared after they are finished. Clearing
of an inactive flow is performed if no more packets belonging to this flow are
received within a certain time interval. Tracking and clearing of flows is
performed by a token mechanism. Physically, the token can be interpreted as a
particular timer that is activated during a flow admission epoch and is restarted
during epochs of other customers from this flow arrival, and is terminated if a
particular fixed timeout expires and a new customer from this flow does not
arrive. The number of tokens (timers), which defines the maximum number of
flows that can be admitted to the system simultaneously, is a very important
control parameter. If this number is too small, the channel may be
underutilized. If this number is too large, the channel may become congested.
Many packets from admitted flows may be lost, and grade of service is poor. In
addition, the delay and jitter of flows may inherently increase. So, the
problem of defining the optimal number of tokens is practically important and
nontrivial. In [5],
performance measures of the SAPOR scheme of routing in IP networks are evaluated by means of computer simulation. In [6], a description of such a
scheme is given in terms of the queueing model.Also, there is an analogous model for information
retrieval in relational databases, where, besides the CPU and disc memory, some
additional threads or connections must be provided, to start the user's
application processing. In this interpretation, a flow means an application,
while customers are queries that will be processed within this application.In [6], a multiserver Markovian queueing model with a finite
buffer that suits the performance evaluation of the scheme of alternative
packet overflow routing in IP networks, as well as that of other
real-world systems with a time distributed arrival of customers in a flow, is
constructed and investigated analytically. In particular, the joint
distribution of the number of customers and flows in the system is computed. A
very important performance measure of this queueing model is the flow sojourn
time computed since the instant of a flow arrival until the instant when all
customers from this flow finish their arrival and processing in the system.In [6], the Laplace-Stieltjes transform for a flow sojourn
time distribution is calculated only for the case of a single server queue. In
this paper, we calculate this distribution for a multiserver queue with losses
(without a buffer). The considered model is more general than the model
considered in [6], and
in the following respect: it was assumed in [6] that the loss of any customer from the admitted flow
does not affect the further behavior of the system. In this paper, we assume
that, with fixed probability, the entire flow terminates its arrival after the
loss of a customer from this flow. This assumption is realistic in various
situations, for example, termination of a connection can occur ahead of
schedule if the percentage of lost voice or video packets (and quality of
speech or movie) becomes unacceptable for the user.The rest of the paper is organized as follows. In
Section2, the model is described. The steady-state joint distribution of the number
of flows and customers in the system is given in Section 3. Sections 4 and 5
contain the main contributions of this paper: an analysis of a flow sojourn
time distribution, and an expression for the loss probability of an accepted
flow, due to the loss of a particular customer from this flow. Numerical
illustrations are presented in Section 6.


## 2. Mathematical Model

We consider a queueing system withN identical servers, where the service time in
the server has an exponential distribution with the parameter μ. The system does not have a buffer. Customers
arrive at the system in flows. Flows arrive at the system according to a
stationary Poisson arrival process with the intensity λ. In accordance with [5], we assume that admission of
flows is restricted by means of tokens. The total number of available
tokens is assumed to be K,K≥1. The number K can be considered as a control parameter, and
various optimization problems can be solved.If there is no token available at a flow arrival
epoch, or all the servers are busy, the flow is rejected. It leaves the system
permanently. If the number of available tokens is positive and there is at
least one free server, the flow is admitted to the system and the number of
available tokens decreases by one. After admission of the flow, the next
customer of this flow can arrive at the system in an exponentially distributed
time, with the parameterγ.If there is a free server at the instant of arrival of
a customer from the admitted flow, the customer is admitted to the system.
Otherwise, the customer is rejected. With probability1−q,0≤q≤1, this rejection does not affect the future
behavior of the system. But, with the supplementary probability q, this rejection causes the termination of the
flow arrival. However, the customers from this flow, which were previously
admitted to the system, can only leave the system after being processed by the
server.The number of customers in a flow has a geometrical
distribution, with the parameterθ,0<θ<1, that is, the probability that the flow
consists of k customers is equal to θk−1(1−θ),k≥1, and the mean number of the customers in a flow
is equal to (1−θ)−1.If an exponentially distributed time (parameterγ) since the arrival of the previous customer
of a flow expires, and a new customer does not arrive, this means that the
arrival of the flow is finished. The token, which was obtained by this flow
upon arrival, is returned to the pool of available tokens. The customers of
this flow, which stay in the system during the epoch when the token is
returned, must be processed by the system. When the last customer is served,
the sojourn time of the flow in the system is considered finished.It is intuitively obvious that this mechanism of
arrivals restriction by means of tokens is reasonable. At the expense of
rejecting some flows, it enables a decrease of the probability of the loss of a
customer from the admitted flows, flows sojourn time, and jitter. It is
important in modeling real-world systems, because the quality of transmission
of accepted information units must satisfy the imposed requirements of quality
of service (QoS).


## 3. Stationary Distribution of the Number of Flows and Customers in the System

Letit,it=0,N¯, denote the total number of customers in the
system during epoch t,t≥0, and let kt,kt=0,K¯, denote the number of flows with a token for
admission to the system during epoch t,t≥0. Here, a notation such as it=0,N¯ means that it assumes values from the set {0,1,…,N}.
It is obvious that the two-dimensional process ζt={it,kt},t≥0, is a finite irreducible regular
continuous-time Markov chain.LetQ be the generator of the Markov chain ζt,t≥0, with blocks Qi,j of dimension (K+1)×(K+1) consisting of intensities (Qi,j)k,k′ of the Markov chain ζt,t≥0, transitions from the state (i,k) to the state (j,k′),k,k′=0,K¯,i=0,N¯,j=0,N¯,i≠jifk=k′. The diagonal entries of the matrix Qi,i are negative, and the modulus of the entry (Qi,i)k,k defines the total intensity of leaving the
state (i,k) of the Markov chain.Here, we introduce the following notation:(i)
γ−=γ(1−θ),γ+=γθ;(ii)
CK=diag{0,1,…,K}, that is, the diagonal matrix with the diagonal
entries {0,1,…,K};(iii)
I is an identity matrix, O is a zero matrix, I^=diag{1,…,1,0},e is a column vector of dimension K+1 consisting of 1 s, 0 is a row vector of dimension K+1 consisting of 0 s;(iv)
(3.1)A=(000⋯00γ−−γ0⋯0002γ−−2γ⋯00⋮⋮⋮⋱⋮⋮000⋯Kγ−−Kγ);(v)
(3.2)A1=(−γO⋯OOγ−−2γ⋯OOO2γ−⋯OO⋮⋮⋱⋮⋮OOO⋯(K−1)γ−−Kγ);(vi)
square matricesE+,E−, of the corresponding size have all zero
entries, except the entries (E+)k,k+1,(E−)k,k−1, which are equal to 1. If
the size of a matrix is not indicated as a suffix explicitly, it is assumed
to be equal to  K+1;(vii)
⊗ is the sign of the Kronecker product of matrices,  δi,j is the Kronecker
delta.Lemma 3.1.
The infinitesimal generatorQ of the Markov chain ζt,t≥0, has the following three-block-diagonal structure: (3.3)Q=(Q0,0Q0,1O⋯OOQ1,0Q1,1Q1,2⋯OOOQ2,1Q2,2⋯OO⋮⋮⋮⋱⋮⋮OOO⋯QN−1,N−1QN−1,NOOO⋯QN,N−1QN,N),
where the nonzero blocks Qi,j are computed by (3.4)Qi,i=A−λI^−iμI,Qi+1,i=(i+1)μI,i=0,N−1¯,QN,N=A+(1−q)γ+CK+qγ+(CKE−)−NμI,Qi−1,i=γ+CK+λE+,i=1,N¯.The proof of the lemma consists of analysis of the
Markov chainζt,t≥0, transitions during the infinitesimal interval
of time, and combining the corresponding transition intensities with the matrix
blocks.Because the Markov chainζt={it,kt},t≥0, is irreducible and regular, and has a finite
state space, the stationary probabilities exist: (3.5)π(i,k)=limt→∞P{it=i,kt=k},i=0,N¯,k=0,K¯.We can apply an effective and numerically stable
algorithm for calculation of such probabilities for Markov chains with a
generator of form (3.3), (elaborated in [4]).Once the stationary probabilitiesπ(i,k) have been computed, we can calculate various
performance measures of the system. The most essential measures are as follows.Corollary 3.2.
The mean numberT of customers processed by the system during
unit time (throughput) is computed by (3.6)T=μ∑i=1N∑k=0Kiπ(i,k). The probability Pb(loss) of an arbitrary flow rejection upon arrival is
computed by (3.7)Pb(loss)=∑i=0N−1π(i,K)+∑k=0Kπ(N,k).


## 4. Distribution of the Sojourn Time

LetVb(x) denote the distribution function of the
sojourn time of an arbitrary flow in the system under study, and let vb(s) denote its Laplace-Stieltjes transform (LST): (4.1)vb(s)=∫0∞e−sxdVb(x),Res>0. We derive an expression for the LSTvb(s) by means of the very powerful method of
collective marks (method of additional event, method of catastrophes); see
[7, 8]. To this end, we interpret
the variable s as the intensity of a particular virtual
stationary Poisson process of catastrophes. So, the function vb(s) denotes the probability that no catastrophe
arrives during the sojourn time of an arbitrary (tagged) flow.Letv(s,i,n,k) denote the probability that a catastrophe from
the stationary Poisson process of catastrophes with intensity s will not arrive during the rest of the tagged
flow sojourn time in the system conditional that, at the given instant, the
number of flows processed in the system is equal to k,k=1,K¯, the number of customers is equal to i,i=0,N¯, and the number of customers from the tagged
flow equals n,n=0,i¯. The system of linear algebraic equations for
functions v(s,i,n,k) is derived by means of the law of the total
probability, expressed as follows: (4.2)v(s,i,n,k)(s+λ(1−δk,K)(1−δi,N)+iμ+kγ)=λ(1−δk,K)(1−δi,N)v(s,i+1,n,k+1)+(i−n)μv(s,i−1,n,k)+nμv(s,i−1,n−1,k)+γ+(1−δi,N)(v(s,i+1,n+1,k)+(k−1)v(s,i+1,n,k))+γ+δi,N((1−q)kv(s,i,n,k)+q+q(k−1)v(s,i,n,k−1))+γ−Γn(s)+γ−(k−1)v(s,i,n,k−1),n=0,i¯,i=0,N¯,k=1,K¯, where(4.3)Γn(s)=∑l=1n(nl)(−1)l+1μlμl+s=∏l=1nμlμl+s,n≥1,Γ0(s)=1.Proof of (4.2) can be clarified by considering that(i)
λ(1−δk,K)(1−δi,N) is the intensity of new flows gaining
admission to the system;(ii)
nμ is the intensity of service completion of
customers from the tagged flow;(iii)
(i−n)μ is the intensity of service completion of
customers that are not from the tagged flow;(iv)
γ+(1−δi,N) is the intensity of arrival of new customers
from a tagged flow, when the system is not full;(v)
γ+(1−δi,N)(k−1) is the intensity of arrival of new customers
from other flows, when the system is not full;(vi)
γ+δi,N(1−q)k is the intensity of arrival of new customers
from all admitted flows to the full system, which will not cause the
termination of the corresponding flow;(vii)
γ+δi,Nq(k−1) is the intensity of the termination (due to an
arriving customer loss) of nontagged flows;(viii)
γ+δi,Nq is the intensity of the termination (due to an
arriving customer loss) of the tagged flow;(ix)
γ− is the intensity of finishing the arrival of
customers from the tagged flow;(x)
γ−(k−1) is the intensity of finishing the arrival of
customers from the nontagged flows;(xi)
Γn(s) is probability of no catastrophe arrival after
finishing the arrival of customers from the tagged flow, when n customers from this flow are served in the
system at the arrival finishing epoch.To solve system (4.2), the following vector notation is
useful: (4.4)v(s,i,n)=(v(s,i,n,1),…,v(s,i,n,K))T,n=0,i¯,v(s,i)=(v(s,i,0),…,v(s,i,i))T,i=0,N¯,v(s)=(v(s,0),…,v(s,N))T,ℬi(s)=γ−(eK,Γ1(s)eK,…,Γi(s)eK)T,i=0,N¯,ℬ(s)=(ℬ0(s),…,ℬN(s))T+qγ+(0,…,0,eK(N+1))T. Let the matrix function Ω(s) be defined by its entries: (4.5)Ωi,i(s)=−Ii+1⊗(sI−Q^i,i),Ωi,i+1=D1(i)⊗Q^i,i+1+D2(i)⊗γ+IK,Ωi,i−1=(iμ00⋯0μ(i−1)μ0⋯0⋯⋱⋱⋯⋯00⋯(i−1)μμ00⋯0iμ)⊗IK,Q^i,i=A1−λI^K−iμIK,i=0,N−1¯,Q^N,N=A1+(1−q)γ+(CK−1+I)+qγ+CK−1E−−NμIK,Q^i,i+1=γ+CK−1+λEK+,i=0,N−1¯, where the matrix D1(i)(D2(i)) is obtained from the identity matrix Ii+1 by means of supplementing it from the right
(left) side with the column 0i+1T. The matrix D3(i) is obtained from the identity matrix Ii by means of supplementing it from the top with
the row {1,0,…,0}.Using this notation, system (6.1) can be easily
expressed as (4.6)Ω(s)v(s)=−ℬ(s).Considering this relation and using the law of the
total probability, we can easily prove the following statement.Theorem 4.1.
TheLSTvb(s) is calculated by (4.7)vb(s)=Pb(loss)+∑i=0N−1∑k=0K−1π(i,k)v(s,i+1,1,k+1), where the vector v(s) consisting of the conditional
Laplace-Stieltjes transforms v(s,i,l,k),l=0,i¯,i=0,N¯,k=1,K¯, is computed by (4.8)v(s)=−Ω−1(s)ℬ(s).Remark 4.2.
It can be shown that the diagonal entries of the
matrixΩ(s) dominate in each row. Thus (see [9]) the matrix Ω(s) is nonsingular for any s,Res>0.Corollary 4.3.
The mean sojourn timeVb of an arbitrary flow is computed by (4.9)Vb=−∑i=0N−1∑k=0K−1π(i,k)∂v(s,i+1,1,k+1)∂s|s=0, where the values (∂v(s,i+1,1,k+1)/∂s)|s=0 are computed as the corresponding entries of
the vector (dv(s)/ds)|s=0, which is calculated by (4.10)dv(s)ds|s=0=Ω−1(0)(−dℬ(s)ds|s=0+e). The mean sojourn time Vb(accept) of an arbitrary accepted flow is computed by (4.11)Vb(accept)=Vb1−Pb(loss).


## 5. Loss Probability of an Arbitrary Admitted Flow

In this section, we derive the expression for the loss
probability of an arbitrary admitted flow. Recall that the admitted flow can be
lost, with probabilityq,
due to the loss of any customer from this flow.Letu(s,i,n,k) denote the probability that a catastrophe will
not arrive during the rest of the tagged flow sojourn time in the system
conditional that, at the given instant, the number of flows processed in the
system is equal to k,k=1,K¯, the number of customers in the system is equal
to i,i=0,N¯, the number of customers from the tagged flow
is equal to n,l=0,i¯, and the flow will not be rejected (terminated)
due to the loss of a particular customer from this flow.Analogous to the previous section, we can prove the
following statement.Theorem 5.1.
The loss probabilityPa(loss) of an arbitrary admitted flow is calculated by (5.1)Pa(loss)=1−∑i=0N−1∑k=0K−1π(i,k)u(0,i+1,1,k+1)1−Pb(loss), where the functions u(s,i,n,k),n=0,i¯,i=0,N¯,k=1,K¯, are the entries of the vector u(s) which is calculated by formula (5.2)u(s)=−Ω−1(s)ℬ˜(s), where ℬ˜(s) is the vector defined by (5.3)ℬ˜(s)=(ℬ0(s),…,ℬN(s))T.Remark 5.2.
It is worthy of mention that, in contrast to the
classical Erlang loss model, where the loss probability can be calculated by a
simple analytical expression, calculation of the loss probability of an
arbitrary flow, and an arbitrary admitted flow in the model with flow arrivals,
requires the development of an algorithmic tool. Such a tool is the main
contribution of this paper.


## 6. Numerical Examples

To demonstrate the feasibility of the proposed means
of the characteristics calculation and to provide insight into the dependence
of the main system performance measures on its parameters and the number of
tokenK, we present the results of various numerical
experiments.Experiment 6.1.
In this experiment, we fix the following parameters
of the system:q=0.3,λ=2,μ=1,γ=2,θ=0.9. Figure 1 shows the dependence of the mean
sojourn time Vb(accept) of an arbitrary admitted flow on the number of
servers N and the number of tokens K.
Note that the mean sojourn timeVb(accept) increases as the number of servers N increases. This surprising effect is easily
explained as follows. The sojourn time of an arbitrary admitted flow increases
with increasing N,
because the probability of the flow termination due to the loss of a customer
from this flow decreases with increasing N.Figure 1
Dependence of the mean sojourn timeVb(accept) of an arbitrary admitted flow on the number of
servers N and the number of tokens K.Experiment 6.2.
In this experiment, we fix the following parameters
of the systemλ=1,μ=2,γ=2,θ=0.9 and assume that the number of tokens K=5. Figure 2 illustrates the dependence of the
loss probability Pa(loss) of an arbitrary admitted flow on the number of
servers N, and the probability q of flow termination when a customer from this
flow is rejected.
As is expected, the loss probability of an arbitrary
admitted flow increases when the probabilityq of flow termination due to its customer
rejection increases. This effect declines as the number of servers increases.Figure 2
Dependence of the loss probabilityPa(loss) of an arbitrary admitted flow on the number of
servers N and the probability q.Experiment 6.3.
In this experiment, we show the effect of changing
the parameterθ,
which defines the number of customers in a flow. We fix the same parameters as
in the previous experiment, and set q=0.6. Figure 3 illustrates the dependence of the
loss probability Pa(loss) of an arbitrary admitted flow on the number of
servers N and the parameter θ.
The loss probability of an arbitrary admitted flow
increases as the parameterθ (and average number of customers in a flow)
increases. This effect declines as the number of servers increases.Figure 3
Dependence of the loss probabilityPa(loss) of an arbitrary admitted flow on the number of
servers N and the parameter θ.Experiment 6.4.
It is evident that the decision maker controlling the
operation of the model with the flow arrival aims to increase the number of
tokensK, to provide the highest throughput of the
system. However, an increase of K evidently leads to greater competition between
flows, and an increase of the loss probability Pa(loss) of an arbitrary admitted flow. To protect the
interests of users, some QoS requirements should be imposed. The natural
requirement is to ensure that the loss probability of an arbitrary admitted
flow is less than a particular preassigned level ε.
So the following optimization problem arises:(6.1)K→maxsubject to restriction (6.2)Pa(loss)<ε.
In this experiment, we consider this optimization
problem, and illustrate the effect of the number of serversN,
probability q of the flow termination when a customer from
this flow is rejected, and parameter θ that characterizes the distribution of the
number of customers in a flow.
Firstly, we fix the following parameters of the
system:q=0.3,λ=1,μ=5,γ=2,θ=0.95. Figure 4 shows the dependence of the value K*, which is the solution to problem (6.1), (6.2), on
the number of servers N for various admissible values ε of the loss probability.Figure 4
Dependence of the optimal numberK* of tokens on the number of servers N.It is clear from this figure that if the numberN of servers is less than or equal to four, even
when the number of tokens K=1, the loss probability Pa(loss) is greater than ε,ε≤0.001. For N=5, the loss probability Pa(loss)<0.001 can be guaranteed. For N=6 and N=7 correspondingly, the loss probability Pa(loss)<0.0001 and Pa(loss)<0.00001 can be guaranteed. By increasing the number of
servers N, the number K* can be rapidly increased.Secondly, we fix the following parameters of the
system:N=15,λ=1,μ=5,γ=2,θ=0.95. Figure 5 shows the dependence of K*, which is the solution to problem (6.1), (6.2), on
the probability q of flow termination, when a customer from this
flow is rejected, for various values ε of admissible loss probability.Figure 5
Dependence of the optimal numberK* of tokens on the probability q.As is expected, an increase of the probabilityq implies a decrease of K*.Finally, we fix the following parameters of the
system:N=10,λ=1,μ=2,γ=2,q=0.4. Figure 6 shows the dependence of K* on the parameter θ.Figure 6
Dependence ofK* of tokens on the parameter θ.Because the mean number of customers in a flow is
equal to(1−θ)−1, this number rapidly increases when θ approaches 1. Correspondingly, K*, which is the solution to problem (6.1), (6.2),
rapidly decreases. For values of θ equal to 0.997, 0.9997, 0.99997, that
correspond to the mean number of customers in a batch equal to 330, 3330, and
33330, respectively, the system cannot provide the required QoS, even when K=1, where the values of ε are 10−5,10−4,10−3, respectively.


## 7. Conclusion

We analyzed the sojourn time distribution, loss probability
of an arbitrary flow, and arbitrary admitted flow in a multiserver loss
queueing system with a flow arrival of customers. The results can be exploited
for performance evaluation and capacity planning of systems ofIP telephony and other systems of information transmission that do not have
buffers but have time distributed (flow) arrival of customers. Results can be
easily extended to the cases of the MAP arrival process of flows and
phase-type service time distribution. However, this particular account of the
phase-type service time distribution results in an inherent increase of the
state space of the Markov chain under study. Results can also be generalized to
the case of an arbitrary distribution of the number of customers in a flow.
However, in this case, the state space of the Markov chain also inherently
increases, because it is necessary to record the number of customers that
previously arrived in each flow. The alternative means of weakening the
assumptions about the exponential distribution of interarrival times in a flow
and the geometric batch size distribution is to assume a phase-type mechanism
of customers arrival in a flow. Customer arrivals occur at the instants of
transitions of the underlying Markov process of the phase-type distribution.
Analysis of such a model is in progress.



---

*Source: 814740-2009-01-27.xml*