Advanced
DISCRETE-TIME BUFFER SYSTEMS WITH SESSION-BASED ARRIVALS AND MARKOVIAN OUTPUT INTERRUPTIONS†
DISCRETE-TIME BUFFER SYSTEMS WITH SESSION-BASED ARRIVALS AND MARKOVIAN OUTPUT INTERRUPTIONS†
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 185-191
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : August 27, 2014
  • Accepted : November 21, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
JEONGSIM KIM

Abstract
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.
Keywords
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 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 Lk and pgf lk ( 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 Ak and pgf ak ( 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 pij , 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:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
and the fundamental probability of the successful transmission is κ P 1 1 , the necessary and sufficient condition for stability is
PPT Slide
Lager Image
We assume this stability condition throughout the paper.
3. Buffer content
In this section we focus on the mean buffer content in the steady state. Let 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
PPT Slide
Lager Image
From this we obtain
PPT Slide
Lager Image
PPT Slide
Lager Image
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
PPT Slide
Lager Image
In order to obtain the mean buffer content, we first compute
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Then the vector pgf π ( z ) satisfies
PPT Slide
Lager Image
which is written as
PPT Slide
Lager Image
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
PPT Slide
Lager Image
According to the implicit function theorem, χ ( z ) and all components of ξ ( z ) are analytic on (0, ∞). Differentiating (5) and evaluating at z = 1 yields
PPT Slide
Lager Image
Premultiplying by κ in (6) gives
PPT Slide
Lager Image
Using this and κξ′ (1) = 0, we can rewrite (6) as
PPT Slide
Lager Image
Since I P 0 P 1 1 κ is invertible, this becomes
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Premultiplying by κ in the above yields
PPT Slide
Lager Image
Postmultiplying by ξ ( z ) in (4), differentiating the resulting equation twice with respect to z and letting z → 1−, we obtain
PPT Slide
Lager Image
Since
PPT Slide
Lager Image
we have
PPT Slide
Lager Image
Plugging (7) and (9) into the above gives
PPT Slide
Lager Image
Now we compute
PPT Slide
Lager Image
Since an active session of type k has mean remaining session length
PPT Slide
Lager Image
the mean number of packets that will be generated in the future by an active session of type k is
PPT Slide
Lager Image
Since the mean number of active sessions of type k at an arbitrary slot is
PPT Slide
Lager Image
the mean number of packets that will be generated in the future by currently active sessions of type k is
PPT Slide
Lager Image
From this we have
PPT Slide
Lager Image
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
PPT Slide
Lager Image
We remark that the denominator in the first line of (12) is positive by the stability condition, and that if
PPT Slide
Lager Image
are finite, then
PPT Slide
Lager Image
4. Numerical results
In this section we present numerical example to compute the mean buffer content.
Example 1. For the output line, we consider a discrete-time Markov chain with states 1, 2, . . . , m and
PPT Slide
Lager Image
Transitions occur with a probability
PPT Slide
Lager Image
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.,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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.,
PPT Slide
Lager Image
We define the load as
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
The mean buffer content,
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
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
References
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