DISCRETE-TIME BUFFER SYSTEMS WITH SESSION-BASED ARRIVALS AND MARKOVIAN OUTPUT INTERRUPTIONS†

Journal of Applied Mathematics & Informatics.
2015.
Jan,
33(1_2):
185-191

- Received : August 27, 2014
- Accepted : November 21, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

This paper considers a discrete-time buffer system with sessionbased arrivals, an infinite storage capacity and one unreliable output line. There are multiple different types of sessions and the output line is governed by a finite state Markov chain. Based on a generating functions approach, we obtain an exact expression for the mean buffer content.
AMS Mathematics Subject Classification : 60K25.
K
different types of sessions. The numbers of new sessions of type
k
, 1 ≤
k
≤
K
, started during a slot are assumed to be independent and identically distributed (i.i.d.) random variables with a generic random variable Λ
_{k}
and probability generating function (pgf)
λ_{k}
(
z
). The lengths of sessions of type
k
are i.i.d. random variables with a generic random variable
L_{k}
and pgf
l_{k}
(
z
). The numbers of packets generated during one slot by an active session of type
k
are i.i.d. random variables with a generic random variable
A_{k}
and pgf
a_{k}
(
z
). As mentioned above, active sessions generate at least one packet per slot.
The transmission times of the packets from the buffer are equal to one slot per packet, but the packets are sent over an output line which may be prone to probabilistic interruptions. The interruptions are governed by a discrete-time Markov chain {
C
(
t
) :
t
= 0, 1, . . .} with states 1, 2, . . . ,
m
. We will use the term ‘output line state’ to denote the state of {
C
(
t
) :
t
= 0, 1, . . .}. When the output line is in state
j
, the accessibility of the output line is governed by a Bernoulli distribution with success probability
σ_{j}
. Let
p_{ij}
, 1 ≤
i, j
≤
m
, be the transition probability from output line state
i
to state
j
. We assume that {
C
(
t
) :
t
= 0, 1, . . .} is irreducible. We introduce the
m
×
m
matrices
P
_{0}
and
P
_{1}
defined as follows:
Let
κ
= (
κ
_{1}
, . . . ,
κ_{m}
) denote the steady state probability vector of {
C
(
t
) :
t
= 0, 1, . . .}, i.e.,
κ
satisfies
κ
=
κ
(
P
_{0}
+
P
_{1}
) and
κ
1
= 1. Here and subsequently,
1
denotes the
m
-dimensional column vector with all components equal to one.
Because the mean number of packet arrivals per slot is
and the fundamental probability of the successful transmission is
κ
P
_{1}
1
, the necessary and sufficient condition for stability is
We assume this stability condition throughout the paper.
U
(
t
) be the buffer content, i.e., the total number of packets present in the system at slot
t
. To obtain the mean buffer content, we introduce an auxiliary variable
Y
(
t
), which is defined as the total number of packets that will be generated after slot
t
by active sessions in slot
t
.
Let
X
(
t
) =
U
(
t
)+
Y
(
t
). Since an active session generates at least one packet in each slot,
X
(
t
) > 0 if and only if
U
(
t
) > 0. Thus, whenever
X
(
t
) > 0, a packet is transmitted during slot
t
if the output line is accessible (not interrupted). From this it is deduced that
X
(
t
) corresponds to the buffer content in the system, where the packets arrive according to a batch Bernoulli process and a packet departs in each slot, if any, whenever the Markovian output line is accessible. The number of packet arrivals generated by the batch Bernoulli process in a slot has the pgf
From this we obtain
Let
X, U, Y
and
C
be the steady state random variables corresponding to
X
(
t
),
U
(
t
),
Y
(
t
) and
C
(
t
), respectively. Thus
X
=
U
+
Y
and the mean buffer content is
In order to obtain the mean buffer content, we first compute
Let
π_{ni}
= ℙ(
X
=
n, C
=
i
),
n
= 0, 1, . . . ,
i
= 1, . . . ,
m
, and
π_{n}
= (
π_{n}
_{1}
,
π_{n}
_{2}
, . . . ,
π_{nm}
). Define the vector pgf
π
(
z
) = (
π
_{1}
(
z
),
π
_{2}
(
z
), . . . ,
π_{m}
(
z
)), where
Then the vector pgf
π
(
z
) satisfies
which is written as
We remark that
π
_{0}
can be obtained by well-known methods, for example, by the spectral method in
[3]
.
Note that
P
_{0}
z
+
P
_{1}
,
z
> 0, is irreducible. Let
χ
(
z
) be the maximal eigenvalue of
P
_{0}
z
+
P
_{1}
and
ξ
(
z
) the right eigenvector of
P
_{0}
z
+
P
_{1}
corresponding to the eigenvalue
χ
(
z
), scaled by
κξ
(
z
) = 1. Thus
According to the implicit function theorem,
χ
(
z
) and all components of
ξ
(
z
) are analytic on (0, ∞). Differentiating (5) and evaluating at
z
= 1 yields
Premultiplying by
κ
in (6) gives
Using this and
κξ′
(1) = 0, we can rewrite (6) as
Since
I
−
P
_{0}
−
P
_{1}
−
1
κ
is invertible, this becomes
where we have used (
I
−
P
_{0}
−
P
_{1}
−
1
κ
)
^{−1}
1
= −
1
. Differentiating (5) twice with respect to
z
and evaluating at
z
= 1 leads to
Premultiplying by
κ
in the above yields
Postmultiplying by
ξ
(
z
) in (4), differentiating the resulting equation twice with respect to
z
and letting
z
→ 1−, we obtain
Since
we have
Plugging (7) and (9) into the above gives
Now we compute
Since an active session of type
k
has mean remaining session length
the mean number of packets that will be generated in the future by an active session of type
k
is
Since the mean number of active sessions of type
k
at an arbitrary slot is
the mean number of packets that will be generated in the future by currently active sessions of type
k
is
From this we have
Substituting (1), (2) and (8) into (10) and then substituting the resulting equation and (11) into (3), we finally obtain the explicit expression for the mean buffer content, as shown below in Theorem 3.1.
Theorem 3.1.
The mean buffer content is given by
We remark that the denominator in the first line of (12) is positive by the stability condition, and that if
are finite, then
Example 1.
For the output line, we consider a discrete-time Markov chain with states 1, 2, . . . ,
m
and
Transitions occur with a probability
where the parameter
ϵ
is nonnegative. If the parameter
ϵ
becomes larger, the Markov process stays in a state longer and the autocorrelation of the output line accessibility becomes stronger.
There are 10 different types of sessions. The numbers of new sessions of type
k
started during a slot have a geometric distribution with parameter
δ
, i.e., ℙ(Λ
_{k}
=
n
) = (1 −
δ
)
^{n}
δ
,
n
= 0, 1, . . .. The lengths of sessions of type
k
have a discrete Pareto distribution, i.e.,
where
is the Riemann zeta function. The numbers of packets generated during one slot by an active session of type
k
have a discrete uniform distribution on {1, 2, . . . ,
k
}, i.e.,
We define the load as
In
Fig. 1
, we plot the mean buffer content, varying the load
ρ
from 0.1 to 0.9. The parameter
δ
is chosen such that the load becomes
ρ
, i.e.,
δ
is given by
The number of output line states
m
is chosen as
m
= 9 and the parameter
ϵ
is taken as
ϵ
= 0, 1, 2, and 3. As we expect, the mean buffer content increases as the load
ρ
increases. We also observe that for a given value of the load
ρ
the mean buffer content is large when
ϵ
is large. This is consistent with the intuition that the stronger the autocorrelation of the output line accessibility becomes, the larger the buffer content becomes.
The mean buffer content,
Jeongsim Kim received B.S., M.S. and Ph. D. in Mathematics from Korea University. She is currently a professor at Chungbuk National University since 2004. Her research interests include probability theory, stochastic models and queueing theory.
Department of Mathematics Education, Chungbuk National University, 52 Naesudong-ro, Seowon-gu, Cheongju, Chungbuk, 362-763, Korea
e-mail: jeongsimkim@chungbuk.ac.kr

1. Introduction

We consider a discrete-time buffer system with one output line, an infinite storage capacity, and session-based arrivals. The time is divided into intervals of equal length, called time slots. Sessions consist of a number of random packets arriving to a buffer system in consecutive time slots. There are multiple different types of sessions. Session-based arrival process is an extension of train arrival process. Packet trains produce packets at a fixed rate of exactly one packet per slot, whereas active sessions produce one or more than one packets per slot. Session-based arrivals are realistic approach for modelling the traffic generated by users in a telecommunication network. A possible application of session-based arrival processes can be found in Hoflack et al.
[4]
.
Hoflack et al.
[5]
and Wittevrongel et al.
[1]
investigated the session-based arrival models with multiple session types and one output line. In
[5]
the session lengths and the transmission times of the packets are geometrically distributed. But in
[1]
the session lengths are generally distributed and the output line is unreliable and prone to stochastic failures, where the effective transmission times (that are required for the successful transmission of a packet) are geometrically distributed. Feyaerts et al.
[2]
investigated the train arrival model with one type of train, geometric train lengths and an unreliable output line governed by a finite state Markov chain. The interest in the above mentioned papers is to obtain the probability generating functions of the buffer content and the packet delay, as well as the mean buffer content, the mean packet delay and the mean session delay.
In this paper, we consider the session-based arrival model with multiple session types and one unreliable output line. The output line is governed by a discrete-time Markov chain and the session lengths are generally distributed. Our model is more general than the models in the above mentioned papers. By using the equation for the vector generating function of the random variable associated with the buffer content and analytic properties of the matrix generating function for the Markov chain describing the output line state, we obtain an exact expression for the mean buffer content.
The paper is organized as follows. In Section 2, we describe the model in detail. Section 3 focuses on the derivation of the mean buffer content. Numerical results are given in Section 4.
2. Model description

We consider a discrete-time buffer system with one unreliable output line (output channel) and an infinite storage capacity for packets. Sessions can span over multiple consecutive slots and produce packets at a variable rate of one or one more than packets per slot. Multiple sessions can be active simultaneously. There are
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. Buffer content

In this section we focus on the mean buffer content in the steady state. Let
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. Numerical results

In this section we present numerical example to compute the mean buffer content.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

5. Conclusion

We considered the discrete-time buffer system with session-based arrivals and one unreliable output line, where the output line is governed by a discrete-time Markov chain. Even though our model is more complex than other models regarding session-based arrival models, but by using a new and very simple method we obtained an exact expression for the mean buffer content.
BIO

Feyaerts B.
,
De Vuyst S.
,
Bruneel H.
,
Wittevrongel S.
(2012)
Analysis of discrete-time buffers with heterogeneou ssession-based arrivals and general session lengths
Computers & Operations Research
39
2905 -
2914
** DOI : 10.1016/j.cor.2011.11.023**

Feyaerts B.
,
Wittevrongel S.
,
De Vuyst S.
,
Bruneel H.
Discrete-time queues with train arrivals and Markovian server interruptions
Proceedings of the 8th International Conference on Queueing Theory and Network Applications
2013
83 -
89

Gail H. R.
,
Hantler S. L.
,
Taylor B. A.
(1996)
Spectral analysis of M/G/1 and G/M/1 type Markov chains
Advances in Applied Probability
28
114 -
165
** DOI : 10.2307/1427915**

Hoflack L.
,
De Vuyst S.
,
Wittevrongel S.
,
Bruneel H.
(2008)
Analytic traffic model of web server
Electronics Letters
44
61 -
63
** DOI : 10.1049/el:20083020**

Hoflack L.
,
De Vuyst S.
,
Wittevrongel S.
,
Bruneel H.
(2010)
Discrete-time buffer systems with session-based arrival streams
Performance Evaluation
67
432 -
450
** DOI : 10.1016/j.peva.2009.12.007**

Kim Jeongsim
(2012)
Two-class M/PH,G/1 queue with impatience of high-priority customers
J. Appl. Math. & Informatics
30
749 -
757

Lee Yutae
(2006)
Discrete-time GeoX/G/1 queue with place reservation discipline
J. Appl. Math. & Computing
22
453 -
460
** DOI : 10.1007/BF02896493**

Citing 'DISCRETE-TIME BUFFER SYSTEMS WITH SESSION-BASED ARRIVALS AND MARKOVIAN OUTPUT INTERRUPTIONS†
'

@article{ E1MCA9_2015_v33n1_2_185}
,title={DISCRETE-TIME BUFFER SYSTEMS WITH SESSION-BASED ARRIVALS AND MARKOVIAN OUTPUT INTERRUPTIONS†}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.185}, DOI={10.14317/jami.2015.185}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={KIM, JEONGSIM}
, year={2015}
, month={Jan}