Open access peer-reviewed chapter

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

By Sergey Dudin and Moon Ho Lee

Published: March 1st 2010

DOI: 10.5772/8480

Downloaded: 1193

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) inIPnetworks.

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 ofIPaddress) 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 theSAPORscheme of routing inIPnetworks 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 theSAPORrouting 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). BecausePHtype 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 theMAPis directed by an irreducible continuous time Markov chainνtt0with the finite state space{0,...,W}The sojourn time of the Markov chainνtt0in the stateνhas an exponential distribution with the parameterλνν=0W¯After this sojourn time expires, with probabilitypk(νν)the processνtt0transits to the stateν, andksessions,k=0,1arrive into the system. The intensities of jumps from one state into another, which are accompanied by an arrival ofksessions, are combined into the matricesDkk=0,1of size(W+1)×(W+1). The matrix generating function of these matrices isD(z)=D0+D1z|z|1. The matrixD(1)is the infinitesimal generator of the processνtt0The stationary distribution vectorδof this process satisfies the equationsδD(1)=0δe=1Here and in the sequel0is the zero row vector andeis 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 dimensionalityW¯=W+1

The average intensityλ(fundamental rate) of theMAPis defined as

λ=δD1e

The variancevof intervals between session arrivals is calculated as

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

the squared coefficientcvarof variation is calculated by

cvar=2λδ(D0)1e1

while the correlation coefficientccorof intervals between successive group arrivals is given by

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

For more information about theMAP, 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 theMAPin modeling telecommunication systems is mentioned in (Heyman & Lucantoni, 2003), (Klemm et al., 2003). Note, that the problem of constructing theMAPwhich 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 beKK1Further we consider the numberKas 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θ1i.e., probability that the session consists ofkrequests is equal toθk1(1θ)k1The 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ηtt0which is the continuous time Markov chain with the state space{1,M}The initial state of the processηtt0at the epoch of starting the service is determined by the probabilistic row-vectorβ=(β1βM). The transitions of the processηtt0that do not lead to the service completion, are defined by the irreducible matrixSof sizeM×M. The intensities of transitions, which lead to the service completion, are defined by the column vectorS0=Se. The service time distribution function has the formB(x)=1βeSxe. Laplace-Stieltjes transform0esxdB(x)of this distribution function isβ(sIS)1S0The average service time is given byb1=β(S)1e. The matrixS+S0βis assumed to be irreducible. The more detailed description of thePH-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 valueKof 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 numberKK1of tokens is fixed and let

  • itbe the total number of requests in the system,it0

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

  • νtandηtbe the states of the directing processes of theMAParrival process andPHservice process,νt=0W¯ηt=1M¯

    at the epochtt0

Note that whenit=0i.e., requests are absent in the system, the value of the componentηtwhich 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ηtis 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}t0is 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 ofM1=(W+1)Mstates(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}IM1Iis an identity matrix,Ois a zero matrix;

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

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

  • δijis Kronecker delta,δijis equal to 1, ifi=jand equal to 0 otherwise;

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

  • bTdenotes transposed vectorb

LetQbe the generator of the Markov chainξtt0with blocksQijconsisting of intensities(Qij)kkof the Markov chainξtt0transitions from the macro-state(ik)to the macro-state(jk)kk=0K¯The diagonal entries of the matrixQiiare negative and the modulus of the diagonal entry of(Qii)kkdefines the total intensity of leaving the corresponding state(ikνη)of the Markov chain. The blockQijij0has dimensionK1×K1whereK1=(K+1)M1

Lemma 1. GeneratorQhas the three block diagonal structure:

Q=(Q0,0Q0OOQ2Q1Q0OOQ2Q1Q0)

where non-zero blocksQijare defined by

Q0,0=A+IK+1D0IM+E˜D1IMQ1=A+IK+1(D0S)+E˜D1IMQ0=γ+CK+E+D1IMQ2=IK+1IW+1S0β

Proof of the lemma consists of analysis of the Markov chainξtt0transitions 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ξtt0defined by the generatorQTo 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}t0is ergodic if and only if the following inequality is fulfilled:

μΛ=γ+k=0KkxkeW+1+k=0K1xkD1eW+1E1

whereμis the average service rate defined by

μ1=b1=β(S)1eandx=(x0xK)is the vector of the stationary distribution of the systemMAP/M/K/0with theMAParrival process, defined by the matricesD0andD1and the average service rateγ.

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

yQ2eyQ0eE2

where the row vectoryis solution to the system of linear algebraic equations of form

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

It is easy to verify that

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

whereBis the generator of the Markov chain, which describes behavior of theMAP|M|K|0system with theMAParrival process defined by matricesD0andD1and average service rateγ:

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

According to the definition, vectorxsatisfies equations

xB=0xe=1E4

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

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

By substituting vectory=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

πii0are calculated byπi=π0Rii0

where the matrixRis the minimal non-negative solution to the equation

R2Q2+RQ1+Q0=O

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

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

Having stationary probability vectorsπii0been 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 numberLof 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 vectore(k)has all zero entries except thekth one, which is equal to 1,k=0K¯

The average numberZof sessions in the system is computed by

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

The distribution functionR(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 numberTof 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 vectorsxkk=0K¯are the entries of the vectorx=(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}t0coinciding with the steady state distribution of the queueing model of theMAP/PH/1type with the phase service time distribution having irreducible representation(βS)and theMAParrival process defined by the matricesD˜0andD˜1having the formD˜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 thisMAPis 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+1for 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 probabilityPb(loss)of an arbitrary session rejection upon arrival is computed by

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

The probabilityPc(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 probabilityPb(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 toK. 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 toK. 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

LetVb(x)Vc(x)andVc(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, andvb(s)vc(s)andvc(a)(s)Res0be their Laplace-Stieltjes transforms (LSTs):vb(s)=0esxdVb(x)vc(s)=0esxdVc(x)vc(a)(s)=0esxdVc(a)(x)

Formulae for calculation of the LSTsvc(s)andvc(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 timeVcof an arbitrary request, which is the first in a session, the average sojourn timeVcof an arbitrary non-rejected request, which is the first in a session, and the average sojourn timeVc(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 timeVcof 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 LSTvb(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 LSTvb(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 variablesas 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. Letv(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 tokk=1,K¯the number of requests is equal toii0the last (in the order of arrival) request of a tagged session has position numberll=0i¯in the system, and the states of the processesνtηtt0areνη. 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 functionsv(silkνη)been calculated the Laplace-Stieltjes transformvb(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,νη)E6

The system of linear algebraic equations for functionsv(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,νη)+E7
+δ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 theMAPtransition of the directing process of thePHservice 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 theMAPoccurs 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 thePHservice 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 fromltoi+1The 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 thelth 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 thePHservice is currently in the stateηThe numberβ(sIS)1S0defines 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))Tv(silk)=(v(silk,0)v(silkW))Tv(sil)=(v(sil,1)v(silK))Tv(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+E8
+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,0i0Q^ii+1=γ+CK1+EK+(D1IM)i0Q^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 matrixD1(i)of size(i+1)×(i+2)is obtained from the identity matrixIi+1by means of supplementing from the right by the column0i+1TThe matrixD2(i)of the same size has the last column consisting of 1’s and other columns consisting of 0’s. The matrixD3(i)of size(i+1)×iis obtained from the identity matrixIiby means of supplementing from above by the row(1,0,,0)

VectorB(s)is defined by

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

where

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

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

Ω(s)v(s)+B(s)=0TE9

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 vectorv(s)consisting of conditional Laplace-Stieltjes transformsLSTv(silkνη)l=0i¯i0k=1,K¯ν=0W¯η=1,M¯is calculated by

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

Corollary 2. The average sojourn timeVbof an arbitrary session is calculated by

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

where column vectorsv(si+1,i+1,k+1)s|s=0are calculated as the blocks of the vectordv(s)ds|s=0defined by

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

wherev(0)=γΩ1(0)e

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

Vb(accept)=Vb1Pb(loss)

wherePb(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 throughputTof the system because it defines the profit earned by information transmission. If the numberKthat restricts the number of sessions, which can be served in the system simultaneously, increases the throughputTof the system increases and the probabilityPb(loss)of an arbitrary session rejection upon arrival decreases. So, it seems to be reasonable to increase the numberKas 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 numberKgrows. 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:

T=T(K)maxE11

subject to constraints (1) and

VcVE12

whereVis 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 valueKuntil constraints (1) and (12) are violated. The optimal value ofKin the optimization problem (1), (11), (12) will be denoted byKCorresponding 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 ofKIn 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=VcwhereLis the average number of requests in the system andVcis the average sojourn time of an arbitrary request which is the first in a session.

5.1. Dependence of probabilitiesPblossof an arbitrary session loss andPclossof an arbitrary request loss on the numberKof tokens and correlation in the sessions arrival process

The experiment has two goals. One is to illustrate quantitatively the dependence of probabilitiesPblossof an arbitrary session loss andPclossof an arbitrary request loss on the numberKof 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 theMAParrival 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λ=1The 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 probabilityPblossof an arbitrary session loss andPclossof an arbitrary request loss on the numberKof tokens for the listed above differentMAPs with the same fundamental rate but the different correlation.

Figure 1.

Dependence of probability P b l o s s of arbitrary session loss on the number of tokens K

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 differentMAPs terminate at the different points, e.g., the curve corresponding to the stationary Poisson process terminates at the pointK=5the curve corresponding to theMAPs having correlation coefficient 0.3 terminates at the pointK=12The reason of termination is that the stationary distribution existence condition violates forKlarger 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 correspondingMAP/M/K/0queueing 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 ofPblossandPclossbut larger number of sessions which can be simultaneously processed in the system without overloading the system.IPPprocess 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 theIPPviolating 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 beV=40Figure 3 illustrates the dependence of the throughputTof the system on the number of tokensKAs it is expected, the throughputTis the increasing function ofKfor all arrival processes. However, the shape of this function depends on the correlation in the sessions arrival process. The lines corresponding to the differentMAPs terminate when condition (12) is not hold true. So, as it is seen from Figure 3 the optimal valueKof 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 timeVcfor the first request in non-rejected sessions on the number of tokens in these examples is presented on Figure 4.

Figure 3.

Dependence of the throughput T of the system on the number of tokens under restriction V c ∗ 40

Figure 4.

Dependence of V c ∗ on K

It is seen that the average sojourn timeVcsharply increases when the number of tokensKapproaches the valueK=5orK=6,depending on correlation in the arrival process. For the model with the stationary Poisson arrival process stationary distribution does not exist forK=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 theMAPprocess of sessions is defined by the matrices

D0=(6.880.00080.00080.22)D1=(6.80.07920.0160.2032)

ThisMAPhas 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]ParameterVdefining 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]ParameterVis assumed to be equal to 8.

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

Figure 5.

Dependence of the optimal number K ∗ of tokens on the parameter θ under restriction V c ∗ 0.8

Figure 6.

Dependence of the optimal number K ∗ of tokens on the parameter θ under restriction V c ∗ 8

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

Figure 7.

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

As it is expectable, the optimal numberKof tokens decreases whenλis increasing. The same dependence takes place for otherMAPs, 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 theIPPprocess 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]ParameterVdefining the limiting value of the average sojourn time is assumed to be equal to 5.

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

Figure 8.

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

As it is expectable, the optimal numberKof tokens increases whenμis increasing. The same dependence takes place for otherMAPs, 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.

Acknowledgments

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

© 2010 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike-3.0 License, which permits use, distribution and reproduction for non-commercial purposes, provided the original is properly cited and derivative works building on this content are distributed under the same license.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Sergey Dudin and Moon Ho Lee (March 1st 2010). Queues with Session Arrivals as Models for Optimizing the Traffic Control in Telecommunication Networks, Trends in Telecommunications Technologies, Christos J Bouras, IntechOpen, DOI: 10.5772/8480. Available from:

chapter statistics

1193total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Telecommunication Power System: Energy Saving, Renewable Sources and Environmental Monitoring

By Carmine Lubritto

Related Book

First chapter

A Brief Survey on Cognitive Radio

By Wei Wang

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us