InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Communications and Security » "Trends in Telecommunications Technologies", book edited by Christos J Bouras, ISBN 978-953-307-072-8, Published: March 1, 2010 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 7

Queues with Session Arrivals as Models for Optimizing the Traffic Control in Telecommunication Networks

By Sergey Dudin and Moon Ho Lee
DOI: 10.5772/8480

Article top

Overview

Dependence of probability 
								
									
										
											
												P
												b
												
													l
													o
													s
													s
												
											
										
									
								
								
							 of arbitrary session loss on the number of tokens 
								
									
										K
Figure 1. Dependence of probability P b l o s s of arbitrary session loss on the number of tokens K
Dependence of probability of an arbitrary request loss on the number of tokens 
								
									
										K
Figure 2. Dependence of probability of an arbitrary request loss on the number of tokens K
Dependence of the throughput 
								
									
										T
									
								
								
							 of the system on the number of tokens under restriction 
								
									
										
											
												V
												c
												∗
											
											
											40
Figure 3. Dependence of the throughput T of the system on the number of tokens under restriction V c ∗ 40
Dependence of 
								
									
										
											
												V
												c
												∗
											
										
									
								
								
							 on 
								
									
										K
Figure 4. Dependence of V c ∗ on K
Dependence of the optimal number 
								
									
										
											
												K
												∗
											
										
									
								
								
							 of tokens on the parameter 
								
									
										θ
									
								
								
							 under restriction 
								
									
										
											
												V
												c
												∗
											
											
											0.8
Figure 5. Dependence of the optimal number K ∗ of tokens on the parameter θ under restriction V c ∗ 0.8
Dependence of the optimal number 
								
									
										
											
												K
												∗
											
										
									
								
								
							 of tokens on the parameter 
								
									
										θ
									
								
								
							 under restriction 
								
									
										
											
												V
												c
												∗
											
											
											8
Figure 6. Dependence of the optimal number K ∗ of tokens on the parameter θ under restriction V c ∗ 8
Dependence of the optimal number 
								
									
										
											
												K
												∗
											
										
									
								
								
							 of tokens on the average arrival rate 
								
									
										λ
Figure 7. Dependence of the optimal number K ∗ of tokens on the average arrival rate λ
Dependence of the optimal number 
								
									
										
											
												K
												∗
											
										
									
								
								
							 of tokens on the average service rate 
								
									
										μ
Figure 8. Dependence of the optimal number K ∗ of tokens on the average service rate μ

Queues with Session Arrivals as Models for Optimizing the Traffic Control in Telecommunication Networks

Sergey Dudin1 and Moon Ho Lee2

1. Introduction

Many problems in routing, scheduling, flow control, resources allocation and capacity management in telecommunication, production, and transportation networks can be solved with help of queueing theory. Typically, a user of a network generates not a single item (packet, job, pallet, etc) but a whole bunch of items and service of this user assumes sequential transmission of all these items. This is why the batch arrivals are often assumed in analysis of queueing systems. It is usually assumed that, at a batch arrival epoch, all requests of this batch arrive into the system simultaneously. However, the typical feature of many nowadays networks is that requests arrive in batch, while arrival of requests belonging to a batch is not instantaneous but is distributed in time. We call such batches as sessions. The first request of a session arrives at the session arrival epoch while the rest of requests arrive one by one in random intervals. The session size is random and it may be not known a priori at the session arrival epoch. Such a situation is typical, e.g., in modeling transmission of video and multimedia information. This situation is also typical in IP networks, e.g., in World Wide Web with Hypertext Transfer Protocol (HTTP) where a session can be interpreted as a HTTP connection and a request as a HTTP request. This situation is also discussed in literature with respect to the modeling the Scheme of Alternative Packet Overflow Routing ( SAPOR ) in IP networks.

In this scheme, the session is called as flow and represents a set of packets that should 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, already tracked. If the packet belongs to an existing flow, the packet is marked for transmission. If the flow is not yet tracked and the channel capacity is still available, the packet is admitted into the system and flow count is increased. Otherwise the flow is routed on the overflow link (or is dropped at all) and the packet is rejected in the considered channel. Tracked flows are cleared after they are finished. Clearing of an inactive flow is done if no more packets belonging to this flow are received within a certain time interval. Tracking and clearing of flows is performed by means of a token mechanism. The number of tokens, which defines the maximal number of flows that can be admitted into the system simultaneously, is very important control parameter. If this number is small, the channel may be underutilized. If this number is too large, the channel may become congested. Average delivering time and jitter may increase essentially and Grade of Service becomes bad. So, the problem of defining the optimal number of tokens is of practical importance and non-trivial. In (Kist et al., 2005), performance measures of the SAPOR scheme of routing in IP networks are evaluated by means of computer simulation.

Analogous situation also naturally arises in modeling information retrieving in relational data bases where, besides the CPU and disc memory, some additional "threads" or "connections" should be provided to start the user’s application processing. In this interpretation, session means application while requests are queries to be processed within this application and tokens are threads or connections.

In the paper (Lee et al., 2007), the Markovian queueing model with a finite buffer that suits for analytical performance evaluation and capacity planning of the SAPOR routing scheme as well as for modelling the other real-world systems with time distributed arrival of requests in a session is considered. To the best of our knowledge, such kind of queueing models was not considered and investigated in literature previously. In (Lee et al., 2007), the problem of the system throughput maximization subject to restriction of the loss probability for requests from accepted sessions is solved. In the paper (Kim et al., 2009), the analysis given in (Lee et al., 2007) is extended in three directions. Instead of the stationary Poisson arrival process of sessions, the Markov Arrival Process (MAP) is considered. It allows catching the effect of correlation of flow of sessions. The presented numerical results show that the correlation has profound effect on the system performance measures. The second direction is consideration of the Phase type (PH) service process instead of an exponential service time distribution assumed in (Lee et al., 2007). Because PH type distributions are suitable for fitting an arbitrary distribution, this allows to take into account the service time distribution and variance of this time in particular, carefully. The third direction of extension is the following one. It is assumed in (Lee et al., 2007), that the loss (due to a buffer overflow) of the request from the accepted session never causes loss of a whole session itself. More realistic assumption in some situations is that the session might be lost (terminates connection ahead of schedule). E.g., it can happen if the percentage of lost voice or video packets (and quality of speech or movie) becomes unacceptable for the user. To take such a possibility into account in some extent, it is assumed in this paper that the loss of a request from the admitted session, with fixed probability, leads to the loss of a session to which this request belongs. Influence of this probability is numerically investigated in the paper (Kim et al., 2009).

In the present paper, the modification of model from (Kim et al., 2009) to the case of an infinite buffer is under study. In contrast to the model with a finite buffer considered in (Kim et al., 2009) where the problem of the throughput maximization was solved under constraint on the probability of the loss of a request from an accepted session, here we do not have such a loss. So, the problem of the throughput maximization is solved under constraint on the average sojourn time of requests from the accepted sessions. In section 2, the mathematical model is described in detail. Stability condition, which is not required in the model (Kim et al., 2009) with a finite state space but is very important in the model with an infinite buffer space, is derived in a simple form. This condition creates an additional constraint in maximization problem. The steady state joint distribution of the number of sessions and requests in the system is analyzed by means of the matrix analytical technique and expressions for the main performance measures of the system are given in section 3. Section 4 is devoted to consideration of the request and the session sojourn time distribution. Section 5 contains numerical illustrations and their short discussion and section 6 concludes the paper.

2. Mathematical model

We consider a single server queueing system with a buffer of an infinite capacity. The requests arrive to the system in sessions. Sessions arrive according to the Markov Arrival Process. Sessions arrival in the MAP is directed by an irreducible continuous time Markov chain νt t0 with the finite state space {0,...,W} The sojourn time of the Markov chain νt t0 in the state ν has an exponential distribution with the parameter λνν=0W¯ After this sojourn time expires, with probability pk(νν) the process νt t0 transits to the state ν , and k sessions, k=0,1 arrive into the system. The intensities of jumps from one state into another, which are accompanied by an arrival of k sessions, are combined into the matrices Dkk=0,1 of size (W+1)×(W+1) . The matrix generating function of these matrices is D(z)=D0+D1z|z|1 . The matrix D(1) is the infinitesimal generator of the process νtt0 The stationary distribution vector δ of this process satisfies the equations δD(1)=0δe=1 Here and in the sequel 0 is the zero row vector and e is the column vector of appropriate size consisting of 1’s. In case the dimensionality of the vector is not clear from the context, it is indicated as a lower index, e.g. eW¯ denotes the unit column vector of dimensionality W¯=W+1

The average intensity λ (fundamental rate) of the MAP is defined as

λ=δD1e

The variance v of intervals between session arrivals is calculated as

v=2λ1δ(D0)1eλ2

the squared coefficient cvar of variation is calculated by

cvar=2λδ(D0)1e1

while the correlation coefficient ccor of intervals between successive group arrivals is given by

ccor=(λ1δ(D0)1D1(D0)1eλ2)/v

For more information about the MAP , its special cases and properties and related research see (Fisher & Meier-Hellstern, 1993), (Lucantoni, 1991) and the survey paper by S. Chakravarthy (Chakravarthy, 2001). Usefulness of the MAP in modeling telecommunication systems is mentioned in (Heyman & Lucantoni, 2003), (Klemm et al., 2003). Note, that the problem of constructing the MAP which fits well a real arrival process, is not very simple. However, this problem has practical importance and is intensively solving. For relevant references and the fitting algorithms see, e.g., (Heyman & Lucantoni, 2003), (Klemm et al., 2003), (Asmussen et al., 1996) and (Panchenko & Buchholz, 2007).

Following (Kist et al., 2005), we assume that admission of sessions (they are called flows in (Kist et al., 2005) and called threads, connections, sessions, exchanges, windows, etc. in different real-world applications) is restricted by means of tokens. The total number of available tokens is assumed to be KK1 Further we consider the number K as a control parameter and solve the corresponding optimization problem.

If there is no token available at a session arrival epoch the session is rejected. It leaves the system forever. If the number of available tokens at the session arrival epoch is positive this session is admitted into the system and the number of available tokens decreases by one. We assume that one request of a session arrives at the session arrival epoch and if it meets free server, it occupies the server and is processed. If the server is busy, the request moves to the buffer and later it is picked up for the service according to the First Came - First Served discipline.

After admission of the session, the next request of this session can arrive into the system in an exponentially distributed with the parameter γ time. The number of requests in the session has the geometrical distribution with the parameter θ0θ1 i.e., probability that the session consists of k requests is equal to θk1(1θ)k1 The average size of the session is equal to (1θ)1

If the exponentially distributed with the parameter γ time since arrival of the previous request of a session expires and new request does not arrive, it means that the arrival of the session is finished. The token, which was obtained by this session upon arrival, is returned to the pool of available tokens. The requests of this session, which stay in the system at the epoch of returning the token, must be completely processed by the system. When the last request is served, the sojourn time of the session in the system is considered finished.

The service time of a request is assumed having PH distribution. It means the following. Request’s service time is governed by the directing process ηtt0 which is the continuous time Markov chain with the state space {1,M} The initial state of the process ηtt0 at the epoch of starting the service is determined by the probabilistic row-vector β=(β1βM) . The transitions of the process ηtt0 that do not lead to the service completion, are defined by the irreducible matrix S of size M×M . The intensities of transitions, which lead to the service completion, are defined by the column vector S0=Se . The service time distribution function has the form B(x)=1βeSxe . Laplace-Stieltjes transform 0esxdB(x) of this distribution function is β(sIS)1S0 The average service time is given by b1=β(S)1e . The matrix S+S0β is assumed to be irreducible. The more detailed description of the PH -type distribution and its partial cases can be found, e.g., in the book (Neuts, 1981). Usefulness of PH distribution in description of service process in telecommunication networks is stated, e.g., in (Pattavina & Parini, 2005) and (Riska et al., 2002).

It is intuitively clear that the described mechanism of arrivals restriction by means of tokens is reasonable. At the expense of some sessions rejection, it allows to decrease the sojourn time and jitter for admitted sessions. This is important in modeling real-world systems because the quality of transmission of accepted information units should satisfy imposed requirements of Quality of Service. Quantitative analysis of advantages and shortcomings of this mechanism as well as optimal choice of the number of tokens requires calculation of the main performance measures of the system under the fixed value K of tokens in the system. These measures can be calculated based on the knowledge of stationary distribution of the random process describing dynamics of the system under study.

3. Stationary distribution of the system states

Let us assume that the number KK1 of tokens is fixed and let

  • it be the total number of requests in the system, it0

  • kt be the number of sessions having token for admission to the system, kt=0K¯

  • νt and ηt be the states of the directing processes of the MAP arrival process and PH service process, νt=0W¯ηt=1M¯

    at the epoch tt0

Note that when it=0 i.e., requests are absent in the system, the value of the component ηt which describes the state of the service directing process, is not defined. To avoid special treatment of this situation, without loss of generality, we assume that if the server becomes idle the state of the component ηt is chosen randomly according to the probabilistic vector β and is kept until the next service beginning moment.

It is obvious that the four-dimensional process ξt={itktνtηt}t0 is the irreducible regular continuous time Markov chain.

Let us enumerate the states of this Markov chain in lexicographic order and refer to (ik) as macro-state consisting of M1=(W+1)M states (ikνη)ν=0W¯η=1,M¯

For the use in the sequel, introduce the following notation:

  • γ=γ(1θ)γ+=γθ Γ=γIM1Γ+=γ+IM1Γ=γIM1

  • C˜K=diag{0,1K} is the diagonal matrix with the diagonal entries {0,1,K} CK=C˜KIM1

  • RK=diag{1,K}IM1 I is an identity matrix, O is a zero matrix;

  • A=(OOOOOΓΓOOOO2Γ2ΓOOOOOKΓKΓ)E+=(0100001000010000)

  • A1=(ΓOOOΓ2ΓOOO2ΓOOOOO(K1)ΓKΓ)E˜=(0000000000000001)

  • δij is Kronecker delta, δij is equal to 1, if i=j and equal to 0 otherwise;

  • is the symbol of Kronecker product of matrices; is the symbol of Kronecker sum of matrices;

  • bT denotes transposed vector b

Let Q be the generator of the Markov chain ξtt0 with blocks Qij consisting of intensities (Qij)kk of the Markov chain ξtt0 transitions from the macro-state (ik) to the macro-state (jk)kk=0K¯ The diagonal entries of the matrix Qii are negative and the modulus of the diagonal entry of (Qii)kk defines the total intensity of leaving the corresponding state (ikνη) of the Markov chain. The block Qijij0 has dimension K1×K1 where K1=(K+1)M1

Lemma 1. Generator Q has the three block diagonal structure:

Q=(Q0,0Q0OOQ2Q1Q0OOQ2Q1Q0)

where non-zero blocks Qij are defined by

Q0,0=A+IK+1D0IM+E˜D1IM Q1=A+IK+1(D0S)+E˜D1IM Q0=γ+CK+E+D1IM Q2=IK+1IW+1S0β

Proof of the lemma consists of analysis of the Markov chain ξtt0 transitions during the infinitesimal interval of time and further assembling the corresponding transition intensities into the matrix blocks. Value γ is the intensity of a token releasing due to the finish of the session arrival, γ+ is the intensity of a new request in the session arrival.

Let us investigate the Markov chain ξtt0 defined by the generator Q To this end, at first we should derive conditions under which this Markov chain is ergodic (positive recurrent).

Theorem 1. Markov chain ξt={itktνtηt}t0 is ergodic if and only if the following inequality is fulfilled:

μΛ=γ+k=0KkxkeW+1+k=0K1xkD1eW+1
(1)

where μ is the average service rate defined by

μ1=b1=β(S)1e and x=(x0xK) is the vector of the stationary distribution of the system MAP/M/K/0 with the MAP arrival process, defined by the matrices D0 and D1 and the average service rate γ .

Proof. It follows from (Neuts, 1981) that the ergodicity condition of the Markov chain ξt={itktνtηt}t0 is the fulfillment of inequality

where the row vector y is solution to the system of linear algebraic equations of form

y(Q0+Q1+Q2)=0ye=1
(3)

It is easy to verify that

Q0+Q1+Q2=BIM+I(K+1)(W+1)(S+S0β)

where B is the generator of the Markov chain, which describes behavior of the MAP|M|K|0 system with the MAP arrival process defined by matrices D0 and D1 and average service rate γ :

B=(D0D1OOOγID0γID1OO02γID02γIOOOOOKγID(1)KγI)

According to the definition, vector x satisfies equations

By direct substitution into (3), it can be verified that the vector y which is solution to the system (3), can be represented in the form y=xψ , where ψ is the unique solution of the system of linear algebraic equations

ψ(S+S0β)=0ψe=1
(5)

By substituting vector y=xψ into inequality (2), after some transformations we get inequality (1). Theorem 1 is proven.

In what follows we assume that condition (1) is fulfilled. Then the following limits (stationary probabilities) exist:

π(ikνη)=limtP{it=ikt=kνt=νηt=η}i0k=0K¯ν=0W¯η=1M¯

Let us combine these probabilities into the row-vectors

π(ikν)=(π(ikν,1)π(ikν,2)π(ikνM)) π(ik)=(π(ik,0)π(ik,1)π(ikW)) πi=(π(i,0)π(i,1)π(iK))i0

The following statement directly stems from the results in (Neuts, 1981).

Theorem 2. The stationary probability vectors

πii0 are calculated by πi=π0Rii0

where the matrix R is the minimal non-negative solution to the equation

R2Q2+RQ1+Q0=O

and the vector π0 is the unique solution to the system of linear algebraic equations

π0(Q0,0+RQ2)=0π0(IR)1e=1

Having stationary probability vectors πii0 been computed, we can calculate different performance measures of the system. Some of them are given in the following statements.

Corollary 1. The probability distribution of the number of requests in the system is computed by

limtP{it=i}=πiei0

The average number L of requests in the system is computed by

L=i=0iπie=π0R(IR)2e

The probability distribution of the number of sessions in the system is computed by

limtP{kt=k}=i=0π(ik)e=π0(IR)1(e(k)e)k=0K¯

where the column vector e(k) has all zero entries except the k th one, which is equal to 1, k=0K¯

The average number Z of sessions in the system is computed by

Z=k=1Ki=0kπ(ik)e=π0(IR)1k=1Kk(e(k)e)

The distribution function R(t) of a time, during which arrivals from an arbitrary session occur, is computed by

R(t)=(1θ)l=10tθl1γ(γy)l1(l1)!eγydy=1eγ(1θ)t

The average number T of requests processed by the system at unit of time (throughput) is computed by

T=i=1k=0Kν=0Wη=1Mπ(ikνη)(S0)η=π0R(IR)1(e(K+1)(W+1)S0)

Remark 1. In contrast to the model with a finite buffer, see (Lee et al., 2007) and (Kim et al., 2009), where the arriving session can be rejected not only due to the tokens absence but also due to the buffer overloading, distribution of the number of sessions in the model under study does not depend on the number of requests in the system. It is defined by formula

limtP{kt=k}=xkek=0K¯

where the vectors xkk=0K¯ are the entries of the vector x=(x0xK) which satisfies the system (5). However, distribution π(ik)i0k=0K¯ does not have multiplicative form because the number of requests in the system depends on the number of sessions currently presenting in the system.

Remark 2. It can be verified that the considered model with the infinite buffer has the steady state distribution of the process

ξt={itktνtηt}t0 coinciding with the steady state distribution of the queueing model of the MAP/PH/1 type with the phase service time distribution having irreducible representation (βS) and the MAP arrival process defined by the matrices D˜0 and D˜1 having the form D˜0=(D0OOOOγID0γIOOO02γID02γIOOOOOKγID(1)KγI)D˜1=(OD1OOOOγ+ID1OO0O2γ+IOOOOOOKγ+I)

It is easy to verify that the fundamental rate of this MAP is equal to Λ which is defined in (1). So, stability condition (1) is intuitively clear: the average service rate should exceed the average arrival rate. Note that the first summand in expression Λ=γ+k=0KkxkeW+1+k=0K1xkD1eW+1 for the rate Λ represents the rate of requests from already accepted sessions, i.e., the rate of requests who are not the first in a session. The second summand is the rate of the sessions arrival.

Theorem 2. The probability Pb(loss) of an arbitrary session rejection upon arrival is computed by

Pb(loss)=i=0π(iK)(D1IM)λe=xKD1λe

The probability Pc(loss) of an arbitrary request rejection upon arrival is computed by

Pc(loss)=i=0π(iK)(D1IM)Λ˜e=xKD1Λ˜e

where Λ˜=Λ+xKD1e

Proof of formula for probability Pb(loss) accounts that the session is rejected upon arrival if and only if the number of sessions in the system at this epoch is equal to K . So

Pb(loss)=i=0π(iK)(D1IM)ei=0k=0Kπ(ik)(D1IM)e=i=0π(iK)(D1IM)λe

Rejection of a request can occur only if this request is the first in a session and the number of sessions in the system at this session arrival epoch is equal to K . So

Pc(loss)=i=0π(iK)(D1IM)ei=0k=0Kπ(ik)(D1+kγ+I)IMe=i=0π(iK)D1IMΛ˜e

4. Distribution of the sojourn times

Let Vb(x) Vc(x) and Vc(a)(x) be distribution functions of the sojourn time of an arbitrary session, an arbitrary request, which is the first in a session, and an arbitrary request from the admitted session, which is not the first in this session, in the system under study, and vb(s) vc(s) and vc(a)(s) Res0 be their Laplace-Stieltjes transforms (LSTs): vb(s)=0esxdVb(x)vc(s)=0esxdVc(x)vc(a)(s)=0esxdVc(a)(x)

Formulae for calculation of the LSTs vc(s) and vc(a)(s) are the following:

vc(s)=1λ[π0(D1IM)eβ(sIS)1S0+i=1πi(D1IM)(e(K+1)(W+1)((sIS)1S0))(β(sIS)1S0)i]= =1λ[π0(D1IM)eβ(sIS)1S0+π0R(β(sIS)1S0)× ×(IR(β(sIS)1S0))1(D1IM)(e(K+1)(W+1)((sIS)1S0))] vc(a)(s)=1k=1Ki=0kγ+π(ik)ek=1Kkγ+[π(0k)eβ(sIS)1S0+ +i=1π(ik)(eW+1((sIS)1S0))(β(sIS)1S0)i]

Formulae for the average sojourn time Vc of an arbitrary request, which is the first in a session, the average sojourn time Vc of an arbitrary non-rejected request, which is the first in a session, and the average sojourn time Vc(a) of an arbitrary request from the admitted session, which is not the first in this session, are as follows:

Vc=1λ[π0(D1IM)eb1+i=1πi(D1IM)((e(K+1)(W+1)(S)1e)+eib1)]= =π0λ[(I+R(IR)2)(D1IM)eb1+R(IR)1(D1IM)(e(K+1)(W+1)(S)1e] Vc=Vc1Pb(loss) Vc(a)=k=1Kkγ+[π(0k)eb1+i=1π(ik)((eW+1(S)1e)+eib1)]k=1Ki=0kγ+π(ik)e

If the service time distribution is exponential, expression for the average sojourn time Vc of an arbitrary arriving request, which is the first in a session, becomes simpler:

Vc=π0λb1(IR)2D1e

Derivation of formula for calculation of the LST vb(s) is more involved. Recall that the sojourn time of an arbitrary session in the system lasts since the epoch of the session arrival into the system until the moment when the arrival of a session is finished and all requests, which belong to this session, leave the system. We will derive expression for the LST vb(s) by means of the method of collective marks (method of additional event, method of catastrophes), for references see, e.g., (Kasten & Runnenburg, 1956) and (Danzig, 1955). To this end, we interpret the variable s as the intensity of some virtual stationary Poisson flow of catastrophes. So, vb(s) has meaning of probability that no one catastrophe arrives during the sojourn time of an arbitrary session.

We will tag an arbitrary session and will keep track of its staying in the system. Let v(silkνη) be the probability that catastrophe will not arrive during the rest of the tagged session sojourn time in the system conditional that, at the given moment, the number of sessions processed in the system is equal to kk=1,K¯ the number of requests is equal to ii0 the last (in the order of arrival) request of a tagged session has position number ll=0i¯ in the system, and the states of the processes νtηtt0 are νη . Position number 0 means that currently there is no one request of the tagged session in the system.

It follows from the formula of total probability that if we will have functions v(silkνη) been calculated the Laplace-Stieltjes transform vb(s) can be computed by

vb(s)=Pb(loss)+1λi=0k=0K1ν=0Wη=1Mν=0Wπ(ikνη)λνpνν(1)×v(si+1,i+1,k+1,νη)
(6)

The system of linear algebraic equations for functions v(silkνη) is derived by means of formula of total probability in the following form:

v(silkνη)=[λνν=0Wpνν(1)((1δkK)v(si+1,lk+1,νη)+
(7)
+δkKv(silkνη))+λνν=0Wpνν(0)v(silkνη)+ +(1δi,0)(S0)ηη=1Mβη[v(si1l1kνη)(1δl,0)+v(si1,0,kνη)δl,0]+ +(1δi,0)η=1M(S)ηηv(silkνη)+γ+v(si+1,i+1kνη)+ +γ+(k1)v(si+1lkνη)+γ(k1)v(silk1νη)+ +γ[((sIS)1S0)η(β(sIS)1S0)l1(1δl,0)+δl,0]]× ×(s+λνSηη+kγ)1l=0i¯i0k=1,K¯ν=0W¯η=1M¯

Let us explain formula (7) in brief. The denominator of the right hand side of (7) is equal to the total intensity of the events which can happen after the arbitrary time moment: catastrophe arrival, transition of the directing process of the MAP transition of the directing process of the PH service process, and expiring the time till the moment of possible request arrival from sessions already admitted into the system. The first term in the square brackets in (7) corresponds to the case when a new session arrives. The second term corresponds to the case when transition of the directing process of the MAP occurs without new session generation. The third term corresponds to the case when service completion takes place. The fourth term corresponds to the case when the transition of the directing process of the PH service process occurs without the service completion. The fifth term corresponds to the case when the new request of the tagged session arrives into the system. In this case, the position of the last request of the tagged session in the system is reinstalled from l to i+1 The sixth term corresponds to the case when the new request from another session, which was already admitted to the system, arrives. The seventh term corresponds to the case when some non-tagged session terminates arrivals. The eighth term corresponds to the case when the expected new request of the tagged session does not arrive into the system and arrival of requests of the tagged session is stopped. This session will not more counted as arriving into the system and the tagged request finishes its sojourn time when the last request, who is currently the l th in the system, will leave the system. Number ((sIS)1S0)η defines the probability that catastrophe will not arrive during the residual service time conditional that the directing process of the PH service is currently in the state η The number β(sIS)1S0 defines probability that catastrophe will not arrive during the service time of an arbitrary request.

Let us introduce column vectors

v(silkν)=(v(silkν,1)v(silkνM))T v(silk)=(v(silk,0)v(silkW))T v(sil)=(v(sil,1)v(silK))T v(si)=(v(si,0)v(sii))Tv(s)=(v(s,0)v(s,1))T

System (7) of linear algebraic equations can be rewritten to the matrix form as

(sIQ^ii)v(sil)+Q^ii+1v(si+1,l)+Q^ii1v(si1,l1)(1δ0l)+Q^ii1v(si1,0)δ0l+
(8)
+IKΓ+v(si+1,i+1)+γeK(W+1)((sIS)1S0)(β(sIS)1S0)l1=0KM1Tl=0i¯i0

where

Q^ii=A1+IK(D0S)(1δi,0)+E˜((D1IM))+IK(D0IM)δi,0i0 Q^ii+1=γ+CK1+EK+(D1IM)i0 Q^ii1=IK(W+1)S0βi0Q^01=O

Let us introduce notation:

Ω(s) is three block diagonal matrix with non-zero blocks Ωij(s)j=max{0i1}ii+1,i0

defined by

Ωii(s)=Ii+1(sIQ^ii)Ωii1=D3(i)Q^ii1 Ωii+1=D1(i)Q^ii+1+D2(i)IKΓ+

Here the matrix D1(i) of size (i+1)×(i+2) is obtained from the identity matrix Ii+1 by means of supplementing from the right by the column 0i+1T The matrix D2(i) of the same size has the last column consisting of 1’s and other columns consisting of 0’s. The matrix D3(i) of size (i+1)×i is obtained from the identity matrix Ii by means of supplementing from above by the row (1,0,,0)

Vector B(s) is defined by

B(s)=(B0(s)BN(s))T

where

Bi(s)=γ(eKeM1eKeW+1(sIS)1S0eKeW+1((sIS)1S0)β(sIS)1S0 eKeW+1((sIS)1S0)(β(sIS)1S0)i1)Ti0

Using this notation we can rewrite the system (7) to the form

Ω(s)v(s)+B(s)=0T
(9)

It can be verified that the diagonal entries of the matrix Ω(s) dominate in all rows of this matrix. So the inverse matrix exists. Thus we proved the following assertion.

Theorem 3. The vector v(s) consisting of conditional Laplace-Stieltjes transforms LST v(silkνη)l=0i¯i0k=1,K¯ ν=0W¯η=1,M¯ is calculated by

v(s)=Ω1(s)B(s)
(10)

Corollary 2. The average sojourn time Vb of an arbitrary session is calculated by

Vb=i=0k=0K1π(ik)(D1IM)λv(si+1,i+1,k+1)s|s=0

where column vectors v(si+1,i+1,k+1)s|s=0 are calculated as the blocks of the vector dv(s)ds|s=0 defined by

dv(s)ds|s=0=Ω1(0)(dB(s)ds|s=0+v(0))

where v(0)=γΩ1(0)e

Corollary 3. The average sojourn time Vb(accept) of an arbitrary admitted session is calculated by

Vb(accept)=Vb1Pb(loss)

where Pb(loss) is probability of an arbitrary session rejection upon arrival.

5. Optimization problem and numerical examples

It is obvious that the most important from economical point of view characteristic of the considered model is the throughput T of the system because it defines the profit earned by information transmission. If the number K that restricts the number of sessions, which can be served in the system simultaneously, increases the throughput T of the system increases and the probability Pb(loss) of an arbitrary session rejection upon arrival decreases. So, it seems to be reasonable to increase the number K as much as possible until stability condition (1) is violated. However, such performance measures as the average sojourn time of an arbitrary request and jitter are also very important because they should fit requirements of Quality of Service. These performance measures become worse if the number K grows. Evidently, it does not make sense to admit too many sessions into the system simultaneously and provide bad Quality of Service (average sojourn time and jitter) for them. So, the system manager should decide how many sessions can be allowed to enter the system simultaneously to fit requirements of Quality of Service and to reach the maximally possible throughput.

Thus, one should solve, e.g., the following non-trivial optimization problem:

subject to constraints (1) and

where V is the maximal admissible value of the sojourn time of the first request from non-rejected session and is assumed to be fixed in advance.

This optimization problem can be easy solved by means of computer, based on presented above expressions for the main performance measures of the system, by means of enumeration, i.e., increasing the value K until constraints (1) and (12) are violated. The optimal value of K in the optimization problem (1), (11), (12) will be denoted by K Corresponding computer program allows to validate the feasibility of such an optimization algorithm and to illustrate the dependencies of the system characteristics on the system parameters and the value of K In what follows several illustrative examples are presented.

Before to start description of these examples, let us mention that numerous experiments show that the famous Little’s formula holds good for the system under study in the form λL=Vc where L is the average number of requests in the system and Vc is the average sojourn time of an arbitrary request which is the first in a session.

5.1. Dependence of probabilities Pbloss of an arbitrary session loss and Pcloss of an arbitrary request loss on the number K of tokens and correlation in the sessions arrival process

The experiment has two goals. One is to illustrate quantitatively the dependence of probabilities Pbloss of an arbitrary session loss and Pcloss of an arbitrary request loss on the number K of tokens. The second goal is to show that for several different arrival processes having the same average rate but different correlation this dependence is quite different. This explains the importance of consideration of the model with the MAP arrival process of sessions, which can be essentially correlated in real telecommunication networks, instead of analysis of simpler model with the stationary Poisson arrival process of sessions.

We consider six different MAPs having the same fundamental rate λ=1 The first MAP is the stationary Poisson arrival process. Variation coefficient of inter-arrival times is equal to 1. Four other MAPs have the variation coefficient equal to 2 but different coefficients of correlation of successive intervals between sessions arrival. These four MAPs are described as follows.

  • MAP ( IPPInterruptedPoissonProcess ) flow with correlation coefficient equal to 0 is defined by the matrices

    D0=(0.40.160.241.369.468.11.31.3270)D1=(000000100.2167.20)

  • MAP flow with correlation coefficient equal to 0.1 is defined by the matrices

    D0=(2.660.120.120.130.50.080.140.080.32)D1=(2.30.080.040.090.180.020.50.010.04)

  • MAP flow with correlation coefficient equal to 0.2 is defined by the matrices

    D0=(3.160.120.120.10.450.090.120.110.39)D1=(2.840.060.020.020.210.030.020.040.1)
  • MAP flow with correlation coefficient equal to 0.3 is defined by the matrices

    D0=(5.110.080.070.0290.4460.040.060.080.35)D1=(4.850.090.020.0070.3330.03700.050.16)

  • The sixth MAP has correlation coefficient equal to -0.16 and the squared correlation coefficient equal to 1.896. It is defined by the matrices

    D0=(3.607000.617)D1=(0.3473.260.4780.139)

The service time distribution is Erlangian of order 2 with intensity of the phase equal to 16. The rest of the parameters are the following: γ=2 θ=0.9

Figures 1 and 2 illustrate the dependencies of probability Pbloss of an arbitrary session loss and Pcloss of an arbitrary request loss on the number K of tokens for the listed above different MAP s with the same fundamental rate but the different correlation.

media/image343.jpeg

Figure 1.

Dependence of probability Pbloss of arbitrary session loss on the number of tokens K

media/image346.jpeg

Figure 2.

Dependence of probability of an arbitrary request loss on the number of tokens K

One can pay attention that the curves corresponding to the different MAP s terminate at the different points, e.g., the curve corresponding to the stationary Poisson process terminates at the point K=5 the curve corresponding to the MAP s having correlation coefficient 0.3 terminates at the point K=12 The reason of termination is that the stationary distribution existence condition violates for K larger than 5 and 12 correspondingly.

It is worth to mention, that the previous analysis of different queues with the Batch Markovian Arrival Process given in many papers shows that usually the stability condition depends on the average arrival rate, but does not depend on correlation. It the model under study, stability condition (1) depends on correlation as well. This has the clear explanation: stability condition includes the stationary distribution of the corresponding MAP/M/K/0 queueing system which describes the behavior of the number of busy tokens. As it is illustrated in (Klimenok et al., 2005), this distribution essentially depends on the correlation in the arrival process.

Conclusion that can be made based on these numerical results is the following: higher correlation of the session’s arrival process implies higher value of Pbloss and Pcloss but larger number of sessions which can be simultaneously processed in the system without overloading the system. IPP process violates this rule a bit. This is well known very special kind of arrival process. It has zero correlation. Intervals where arrivals occur more or less intensively alternate with time periods when no arrivals are possible. Such irregular arrivals make the IPP violating the conclusion made above. Note that the system with the negative correlation in the arrival process has characteristics close to characteristics of the system with the stationary Poisson process. While the more or less strong positive correlation changes these characteristics essentially.

5.2. Dependence of the throughput of the system on the number of tokens and correlation in the sessions arrival process

Let us consider the same system as in the previous experiment and consider optimization problem (11), (12) where the limiting value of the average sojourn time for the first request in non-rejected session is assumed to be V=40 Figure 3 illustrates the dependence of the throughput T of the system on the number of tokens K As it is expected, the throughput T is the increasing function of K for all arrival processes. However, the shape of this function depends on the correlation in the sessions arrival process. The lines corresponding to the different MAP s terminate when condition (12) is not hold true. So, as it is seen from Figure 3 the optimal value K of tokens is equal to 5 when the arrival process is the stationary Poisson or has the negative correlation or is equal to 0.1 and is equal to 6 for the rest of the arrival processes.

It is seen from Figures 1-3 that positive correlation has the negative impact on the system performance. Although the number of simultaneously processed requests can be larger, loss probability is higher and the throughput of the system is lesser.

Dependence of the average sojourn time Vc for the first request in non-rejected sessions on the number of tokens in these examples is presented on Figure 4.

media/image366.jpeg

Figure 3.

Dependence of the throughput T of the system on the number of tokens under restriction Vc40

media/image369.jpeg

Figure 4.

Dependence of Vc on K

It is seen that the average sojourn time Vc sharply increases when the number of tokens K approaches the value K=5 or K=6, depending on correlation in the arrival process. For the model with the stationary Poisson arrival process stationary distribution does not exist for K=6

5.3. Dependence of the optimal number of tokens on the session size, arrival and service rates

The goal of this experiment is to illustrate the dependence of the optimal number of tokens on the session size, average arrival and average service rates.

Firstly, let as clarify the impact of the session size. We assume that the MAP process of sessions is defined by the matrices

D0=(6.880.00080.00080.22)D1=(6.80.07920.0160.2032)

This MAP has the average rate equal to 1.37, correlation coefficient 0.4 and the squared variation coefficient 9.4. As in the previous examples, the service time distribution is assumed to be Erlangian of order 2 with the intensity of the phase equal to 16.

On Figure 5, we vary the parameter θ which characterizes the distribution of the number of requests in a session, in the interval [0.1;0.8] This implies that the average session size varies in the interval [1.1115] Parameter V defining the limiting value of the average sojourn time for the first request in non-rejected sessions is assumed to be equal to 0.8.

On Figure 6, we vary the parameter θ in the interval [0.80.98] This implies that the average session size varies in the interval [550] Parameter V is assumed to be equal to 8.

As it is expected, the optimal number K is non-increasing function of θ When θ increases from 0.1 to 0.8 the number K decreases from 8 to 1 under restriction Vc0.8. If we take θ greater than 0.8, restriction Vc0.8 is not fulfilled even only 1 session is allowed to enter the system. If the weaken this restriction to the restriction Vc8 four sessions can be processed in the system simultaneously for θ equal to 0.8. Situation when restriction Vc8 is not fulfilled even only 1 session is allowed to enter the system occurs for θ greater than 0.98.

media/image399.jpeg

Figure 5.

Dependence of the optimal number K of tokens on the parameter θ under restriction Vc0.8

media/image403.jpeg

Figure 6.

Dependence of the optimal number K of tokens on the parameter θ under restriction Vc8

In the next example, we illustrate the impact of the average arrival rate. We consider the IPP process defined above and vary the average arrival rate in the interval [111] by means of multiplication of the matrices D0 and D1 by the corresponding factor. The service time distribution is assumed to be Erlangian of order 2 with the intensity of the phase equal to 30. Parameter V defining the limiting value of the average sojourn time is assumed to be equal to 4. Figure 7 shows the dependence of the optimal number K of tokens on the average arrival rate λ

media/image414.jpeg

Figure 7.

Dependence of the optimal number K of tokens on the average arrival rate λ

As it is expectable, the optimal number K of tokens decreases when λ is increasing. The same dependence takes place for other MAP s, only the points of the jumps of the lines are different.

In the last example, we illustrate the impact of the average service rate. We consider the IPP process defined above having the average arrival rate λ=1

The service time distribution is assumed to be Erlangian of order 2 with intensity of the phase varied to get the average service rate in the interval

[3.5;20] Parameter V defining the limiting value of the average sojourn time is assumed to be equal to 5.

Figure 8 shows the dependence of the optimal number K of tokens on the average service rate μ

media/image425.jpeg

Figure 8.

Dependence of the optimal number K of tokens on the average service rate μ

As it is expectable, the optimal number K of tokens increases when μ is increasing. The same dependence takes place for other MAP s, only again the points of the jumps of the lines are different.

6. Conclusion

In this paper, the novel infinite buffer queueing model with session arrivals distributed in time is analyzed. Ergodicity condition is derived. Joint distribution of the number of requests in the system and number of currently admitted sessions is computed. The sojourn time distribution of an arbitrary request and arbitrary session is given in terms of the Laplace-Stieltjes Transform. Usefulness of the presented results is illustrated numerically. Validity of Little’s formulas is checked by means of numerical experiment.

Results are planned to be extended to the systems with many servers, non-geometrical session size distribution, and heterogeneous arrival flow.

7. Acknowledgements

This work was supported by World Class Univ. R32-2008-000-20014-0 NRF and KRF-2007-521-D00330, Korea.

References

1 - S. Asmussen, O. Nerman, M. Olsson, 1996 Fitting phase-type distributions via the EM algorithm. Scandinavian Journal of Statistics, 23 419 441 .
2 - S. R. Chakravarthy, 2001 The session Markovian arrival process: a review and future work, in: A. Krishnamoorthy, et al. (Eds.). Advances in Probability Theory and Stochastic Process: Proc., Notable Publications, 21 49 .
3 - D. Danzig, 1955 Chaines de Markof dans les ensembles abstraits et applications aux processus avec regions absorbantes et au probleme des boucles. Ann. de l’Inst. H. Pioncare, 14 145 199 .
4 - W. Fisher, K. S. Meier-Hellstern, 1993 The Markov-modulated Poisson process (MMPP) cookbook. Performance Evaluation, 18 149 171 .
5 - D. P. Heyman, D. Lucantoni, 2003 Modelling multiple IP traffic streams with rate limits, IEEE/ACM Transactions on Networking, 11 948 958 .
6 - H. Kasten, J. Runnenburg, Th. 1956 Priority in waiting line problems, Mathematisch Centrum, Amsterdam, Holland.
7 - A. Klemm, C. Lindermann, M. Lohmann, 2003 Modelling IP traffic using the session Markovian arrival process. Performance Evaluation, 54 149 173 .
8 - V. Klimenok, C. S. Kim, D. Orlovsky, A. Dudin, 2005 Lack of invariant property of Erlang loss model in case of the MAP input. Queueing Systems, 49 187 213 .
9 - C. S. Kim, S. Dudin, V. Klimenok, 2009 The queue with time phased arrivals as model for traffic control in telecommunication networks. Performance Evaluation, 66 564 579 .
10 - A. A. Kist, B. Lloyd-Smith, R. J. Harris, 2005 A simple IP flow blocking model. Performance Challenges for Efficient Next Generation Networks. Proceedings of 19-th International Teletraffic Congress, 29 August- 2 September 2005, Beijing, 355 364 .
11 - M. H. Lee, S. Dudin, V. Klimenok, 2007 Queueing Model with Time-Phased Session Arrivals. In: Managing Traffic Performance in Converged Networks Proceedings 20th International Teletraffic Congress, Ottawa, Canada, June 2007. Berlin: Springer. Lecture Notes in Computer Science, 4516 716 730 .
12 - D. M. Lucantoni, 1991 New results on the single server queue with a session Markovian arrival process. Communications in Statistics-Stochastic Models, 7 1 46 .
13 - M. F. Neuts, 1981 Matrix-geometric solutions in stochastic models. Baltimore, The Johns Hopkins University Press.
14 - A. Panchenko, P. Buchholz, 2007 A hybrid algorithm for parameter fitting of Markovian Arrival Process, in: Al-Begain K, Heindl A, Telek M. (Eds.). 14th Int. Conf. "Analytical and stochastic modelling technique and applications". Prague, 2007, 7 12 .
15 - A. Pattavina, A. Parini, 2005 Modelling voice call inter-arrival and holding time distributions in mobile networks, in: Performance Challenges for Efficient Next Generation Networks- Proc.of 19th International Teletraffic Congress, Aug.-Sept. 2005, 729 738 .
16 - A. Riska, V. Diev, E. Smirni, 2002 Efficient fitting of long-tailed data sets into hyperexponential distributions, Global Telecommunications Conference (GLOBALCOM’02, IEEE), 7-21 Nov. 2002, 2513 2517 .