Open access

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

Written By

Sergey Dudin and Moon Ho Lee

Published: March 1st, 2010

DOI: 10.5772/8480

Chapter metrics overview

1,947 Chapter Downloads

View Full Metrics

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 ( S A P O R ) in I P 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 I P 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 S A P O R scheme of routing in I P 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 S A P O R 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 P H 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.

Advertisement

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 M A P is directed by an irreducible continuous time Markov chain ν t t 0 with the finite state space { 0,..., W } The sojourn time of the Markov chain ν t t 0 in the state ν has an exponential distribution with the parameter λ ν ν = 0 W ¯ After this sojourn time expires, with probability p k ( ν ν ) the process ν t t 0 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 D k k = 0,1 of size ( W + 1 ) × ( W + 1 ) . The matrix generating function of these matrices is D ( z ) = D 0 + D 1 z | z | 1 . The matrix D ( 1 ) is the infinitesimal generator of the process ν t t 0 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. e W ¯ denotes the unit column vector of dimensionality W ¯ = W + 1

The average intensity λ (fundamental rate) of the M A P is defined as

λ = δ D 1 e

The variance v of intervals between session arrivals is calculated as

v = 2 λ 1 δ ( D 0 ) 1 e λ 2

the squared coefficient c v a r of variation is calculated by

c v a r = 2 λ δ ( D 0 ) 1 e 1

while the correlation coefficient c c o r of intervals between successive group arrivals is given by

c c o r = ( λ 1 δ ( D 0 ) 1 D 1 ( D 0 ) 1 e λ 2 ) / v

For more information about the M A P , 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 M A P in modeling telecommunication systems is mentioned in (Heyman & Lucantoni, 2003), (Klemm et al., 2003). Note, that the problem of constructing the M A P 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 K K 1 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 θ k 1 ( 1 θ ) k 1 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 η t t 0 which is the continuous time Markov chain with the state space { 1, M } The initial state of the process η t t 0 at the epoch of starting the service is determined by the probabilistic row-vector β = ( β 1 β M ) . The transitions of the process η t t 0 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 S 0 = S e . The service time distribution function has the form B ( x ) = 1 β e S x e . Laplace-Stieltjes transform 0 e s x d B ( x ) of this distribution function is β ( s I S ) 1 S 0 The average service time is given by b 1 = β ( S ) 1 e . The matrix S + S 0 β is assumed to be irreducible. The more detailed description of the P H -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.

Advertisement

3. Stationary distribution of the system states

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

  • i t be the total number of requests in the system, i t 0

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

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

    at the epoch t t 0

Note that when i t = 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 = { i t k t ν t η t } t 0 is the irreducible regular continuous time Markov chain.

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

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

  • γ = γ ( 1 θ ) γ + = γ θ Γ = γ I M 1 Γ + = γ + I M 1 Γ = γ I M 1

  • C ˜ K = d i a g { 0,1 K } is the diagonal matrix with the diagonal entries { 0,1, K } C K = C ˜ K I M 1

  • R K = d i a g { 1, K } I M 1 I is an identity matrix, O is a zero matrix;

  • A = ( O O O O O Γ Γ O O O O 2 Γ 2 Γ O O O O O K Γ K Γ ) E + = ( 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 )

  • A 1 = ( Γ O O O Γ 2 Γ O O O 2 Γ O O O O O ( K 1 ) Γ K Γ ) E ˜ = ( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 )

  • δ i j is Kronecker delta, δ i j 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;

  • b T denotes transposed vector b

Let Q be the generator of the Markov chain ξ t t 0 with blocks Q i j consisting of intensities ( Q i j ) k k of the Markov chain ξ t t 0 transitions from the macro-state ( i k ) to the macro-state ( j k ) k k = 0 K ¯ The diagonal entries of the matrix Q i i are negative and the modulus of the diagonal entry of ( Q i i ) k k defines the total intensity of leaving the corresponding state ( i k ν η ) of the Markov chain. The block Q i j i j 0 has dimension K 1 × K 1 where K 1 = ( K + 1 ) M 1

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

Q = ( Q 0,0 Q 0 O O Q 2 Q 1 Q 0 O O Q 2 Q 1 Q 0 )

where non-zero blocks Q i j are defined by

Q 0,0 = A + I K + 1 D 0 I M + E ˜ D 1 I M Q 1 = A + I K + 1 ( D 0 S ) + E ˜ D 1 I M Q 0 = γ + C K + E + D 1 I M Q 2 = I K + 1 I W + 1 S 0 β

Proof of the lemma consists of analysis of the Markov chain ξ t t 0 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 ξ t t 0 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 = { i t k t ν t η t } t 0 is ergodic if and only if the following inequality is fulfilled:

μ Λ = γ + k = 0 K k x k e W + 1 + k = 0 K 1 x k D 1 e W + 1 E1

where μ is the average service rate defined by

μ 1 = b 1 = β ( S ) 1 e and x = ( x 0 x K ) is the vector of the stationary distribution of the system M A P / M / K / 0 with the M A P arrival process, defined by the matrices D 0 and D 1 and the average service rate γ .

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

y Q 2 e y Q 0 e E2

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

y ( Q 0 + Q 1 + Q 2 ) = 0 y e = 1 E3

It is easy to verify that

Q 0 + Q 1 + Q 2 = B I M + I ( K + 1 ) ( W + 1 ) ( S + S 0 β )

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

B = ( D 0 D 1 O O O γ I D 0 γ I D 1 O O 0 2 γ I D 0 2 γ I O O O O O K γ I D ( 1 ) K γ I )

According to the definition, vector x satisfies equations

x B = 0 x e = 1 E4

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 + S 0 β ) = 0 ψ e = 1 E5

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:

π ( i k ν η ) = l i m t P { i t = i k t = k ν t = ν η t = η } i 0 k = 0 K ¯ ν = 0 W ¯ η = 1 M ¯

Let us combine these probabilities into the row-vectors

π ( i k ν ) = ( π ( i k ν ,1 ) π ( i k ν ,2 ) π ( i k ν M ) ) π ( i k ) = ( π ( i k ,0 ) π ( i k ,1 ) π ( i k W ) ) π i = ( π ( i ,0 ) π ( i ,1 ) π ( i K ) ) i 0

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

Theorem 2. The stationary probability vectors

π i i 0 are calculated by π i = π 0 R i i 0

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

R 2 Q 2 + R Q 1 + Q 0 = O

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

π 0 ( Q 0,0 + R Q 2 ) = 0 π 0 ( I R ) 1 e = 1

Having stationary probability vectors π i i 0 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

l i m t P { i t = i } = π i e i 0

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

L = i = 0 i π i e = π 0 R ( I R ) 2 e

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

l i m t P { k t = k } = i = 0 π ( i k ) e = π 0 ( I R ) 1 ( e ( k ) e ) k = 0 K ¯

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

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

Z = k = 1 K i = 0 k π ( i k ) e = π 0 ( I R ) 1 k = 1 K k ( 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 = 1 0 t θ l 1 γ ( γ y ) l 1 ( l 1 ) ! e γ y d y = 1 e γ ( 1 θ ) t

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

T = i = 1 k = 0 K ν = 0 W η = 1 M π ( i k ν η ) ( S 0 ) η = π 0 R ( I R ) 1 ( e ( K + 1 ) ( W + 1 ) S 0 )

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

l i m t P { k t = k } = x k e k = 0 K ¯

where the vectors x k k = 0 K ¯ are the entries of the vector x = ( x 0 x K ) which satisfies the system (5). However, distribution π ( i k ) i 0 k = 0 K ¯ 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 = { i t k t ν t η t } t 0 coinciding with the steady state distribution of the queueing model of the M A P / P H / 1 type with the phase service time distribution having irreducible representation ( β S ) and the M A P arrival process defined by the matrices D ˜ 0 and D ˜ 1 having the form D ˜ 0 = ( D 0 O O O O γ I D 0 γ I O O O 0 2 γ I D 0 2 γ I O O O O O K γ I D ( 1 ) K γ I ) D ˜ 1 = ( O D 1 O O O O γ + I D 1 O O 0 O 2 γ + I O O O O O O K γ + I )

It is easy to verify that the fundamental rate of this M A P 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 = 0 K k x k e W + 1 + k = 0 K 1 x k D 1 e W + 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 P b ( l o s s ) of an arbitrary session rejection upon arrival is computed by

P b ( l o s s ) = i = 0 π ( i K ) ( D 1 I M ) λ e = x K D 1 λ e

The probability P c ( l o s s ) of an arbitrary request rejection upon arrival is computed by

P c ( l o s s ) = i = 0 π ( i K ) ( D 1 I M ) Λ ˜ e = x K D 1 Λ ˜ e

where Λ ˜ = Λ + x K D 1 e

Proof of formula for probability P b ( l o s s ) 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

P b ( l o s s ) = i = 0 π ( i K ) ( D 1 I M ) e i = 0 k = 0 K π ( i k ) ( D 1 I M ) e = i = 0 π ( i K ) ( D 1 I M ) λ 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

P c ( l o s s ) = i = 0 π ( i K ) ( D 1 I M ) e i = 0 k = 0 K π ( i k ) ( D 1 + k γ + I ) I M e = i = 0 π ( i K ) D 1 I M Λ ˜ e
Advertisement

4. Distribution of the sojourn times

Let V b ( x ) V c ( x ) and V c ( 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 v b ( s ) v c ( s ) and v c ( a ) ( s ) R e s 0 be their Laplace-Stieltjes transforms (LSTs): v b ( s ) = 0 e s x d V b ( x ) v c ( s ) = 0 e s x d V c ( x ) v c ( a ) ( s ) = 0 e s x d V c ( a ) ( x )

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

v c ( s ) = 1 λ [ π 0 ( D 1 I M ) e β ( s I S ) 1 S 0 + i = 1 π i ( D 1 I M ) ( e ( K + 1 ) ( W + 1 ) ( ( s I S ) 1 S 0 ) ) ( β ( s I S ) 1 S 0 ) i ] = = 1 λ [ π 0 ( D 1 I M ) e β ( s I S ) 1 S 0 + π 0 R ( β ( s I S ) 1 S 0 ) × × ( I R ( β ( s I S ) 1 S 0 ) ) 1 ( D 1 I M ) ( e ( K + 1 ) ( W + 1 ) ( ( s I S ) 1 S 0 ) ) ] v c ( a ) ( s ) = 1 k = 1 K i = 0 k γ + π ( i k ) e k = 1 K k γ + [ π ( 0 k ) e β ( s I S ) 1 S 0 + + i = 1 π ( i k ) ( e W + 1 ( ( s I S ) 1 S 0 ) ) ( β ( s I S ) 1 S 0 ) i ]

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

V c = 1 λ [ π 0 ( D 1 I M ) e b 1 + i = 1 π i ( D 1 I M ) ( ( e ( K + 1 ) ( W + 1 ) ( S ) 1 e ) + e i b 1 ) ] = = π 0 λ [ ( I + R ( I R ) 2 ) ( D 1 I M ) e b 1 + R ( I R ) 1 ( D 1 I M ) ( e ( K + 1 ) ( W + 1 ) ( S ) 1 e ] V c = V c 1 P b ( l o s s ) V c ( a ) = k = 1 K k γ + [ π ( 0 k ) e b 1 + i = 1 π ( i k ) ( ( e W + 1 ( S ) 1 e ) + e i b 1 ) ] k = 1 K i = 0 k γ + π ( i k ) e

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

V c = π 0 λ b 1 ( I R ) 2 D 1 e

Derivation of formula for calculation of the LST v b ( 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 v b ( 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, v b ( 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 ( s i l k ν η ) 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 k k = 1, K ¯ the number of requests is equal to i i 0 the last (in the order of arrival) request of a tagged session has position number l l = 0 i ¯ in the system, and the states of the processes ν t η t t 0 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 ( s i l k ν η ) been calculated the Laplace-Stieltjes transform v b ( s ) can be computed by

v b ( s ) = P b ( l o s s ) + 1 λ i = 0 k = 0 K 1 ν = 0 W η = 1 M ν = 0 W π ( i k ν η ) λ ν p ν ν ( 1 ) × v ( s i + 1, i + 1, k + 1, ν η ) E6

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

v ( s i l k ν η ) = [ λ ν ν = 0 W p ν ν ( 1 ) ( ( 1 δ k K ) v ( s i + 1, l k + 1, ν η ) + E7
+ δ k K v ( s i l k ν η ) ) + λ ν ν = 0 W p ν ν ( 0 ) v ( s i l k ν η ) + + ( 1 δ i ,0 ) ( S 0 ) η η = 1 M β η [ v ( s i 1 l 1 k ν η ) ( 1 δ l ,0 ) + v ( s i 1,0, k ν η ) δ l ,0 ] + + ( 1 δ i ,0 ) η = 1 M ( S ) η η v ( s i l k ν η ) + γ + v ( s i + 1, i + 1 k ν η ) + + γ + ( k 1 ) v ( s i + 1 l k ν η ) + γ ( k 1 ) v ( s i l k 1 ν η ) + + γ [ ( ( s I S ) 1 S 0 ) η ( β ( s I S ) 1 S 0 ) l 1 ( 1 δ l ,0 ) + δ l ,0 ] ] × × ( s + λ ν S η η + k γ ) 1 l = 0 i ¯ i 0 k = 1, K ¯ ν = 0 W ¯ η = 1 M ¯

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 M A P transition of the directing process of the P H 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 M A P 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 P H 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 ( ( s I S ) 1 S 0 ) η defines the probability that catastrophe will not arrive during the residual service time conditional that the directing process of the P H service is currently in the state η The number β ( s I S ) 1 S 0 defines probability that catastrophe will not arrive during the service time of an arbitrary request.

Let us introduce column vectors

v ( s i l k ν ) = ( v ( s i l k ν ,1 ) v ( s i l k ν M ) ) T v ( s i l k ) = ( v ( s i l k ,0 ) v ( s i l k W ) ) T v ( s i l ) = ( v ( s i l ,1 ) v ( s i l K ) ) T v ( s i ) = ( v ( s i ,0 ) v ( s i i ) ) T v ( s ) = ( v ( s ,0 ) v ( s ,1 ) ) T

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

( s I Q ^ i i ) v ( s i l ) + Q ^ i i + 1 v ( s i + 1, l ) + Q ^ i i 1 v ( s i 1, l 1 ) ( 1 δ 0 l ) + Q ^ i i 1 v ( s i 1,0 ) δ 0 l + E8
+ I K Γ + v ( s i + 1, i + 1 ) + γ e K ( W + 1 ) ( ( s I S ) 1 S 0 ) ( β ( s I S ) 1 S 0 ) l 1 = 0 K M 1 T l = 0 i ¯ i 0

where

Q ^ i i = A 1 + I K ( D 0 S ) ( 1 δ i ,0 ) + E ˜ ( ( D 1 I M ) ) + I K ( D 0 I M ) δ i ,0 i 0 Q ^ i i + 1 = γ + C K 1 + E K + ( D 1 I M ) i 0 Q ^ i i 1 = I K ( W + 1 ) S 0 β i 0 Q ^ 0 1 = O

Let us introduce notation:

Ω ( s ) is three block diagonal matrix with non-zero blocks Ω i j ( s ) j = m a x { 0 i 1 } i i + 1, i 0

defined by

Ω i i ( s ) = I i + 1 ( s I Q ^ i i ) Ω i i 1 = D 3 ( i ) Q ^ i i 1 Ω i i + 1 = D 1 ( i ) Q ^ i i + 1 + D 2 ( i ) I K Γ +

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

Vector B ( s ) is defined by

B ( s ) = ( B 0 ( s ) B N ( s ) ) T

where

B i ( s ) = γ ( e K e M 1 e K e W + 1 ( s I S ) 1 S 0 e K e W + 1 ( ( s I S ) 1 S 0 ) β ( s I S ) 1 S 0 e K e W + 1 ( ( s I S ) 1 S 0 ) ( β ( s I S ) 1 S 0 ) i 1 ) T i 0

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

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

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 L S T v ( s i l k ν η ) l = 0 i ¯ i 0 k = 1, K ¯ ν = 0 W ¯ η = 1, M ¯ is calculated by

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

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

V b = i = 0 k = 0 K 1 π ( i k ) ( D 1 I M ) λ v ( s i + 1, i + 1, k + 1 ) s | s = 0

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

d v ( s ) d s | s = 0 = Ω 1 ( 0 ) ( d B ( s ) d s | s = 0 + v ( 0 ) )

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

Corollary 3. The average sojourn time V b ( a c c e p t ) of an arbitrary admitted session is calculated by

V b ( a c c e p t ) = V b 1 P b ( l o s s )

where P b ( l o s s ) is probability of an arbitrary session rejection upon arrival.

Advertisement

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 P b ( l o s s ) 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:

T = T ( K ) m a x E11

subject to constraints (1) and

V c V E12

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 = V c where L is the average number of requests in the system and V c is the average sojourn time of an arbitrary request which is the first in a session.

5.1. Dependence of probabilities P b l o s s of an arbitrary session loss and P c l o s s 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 P b l o s s of an arbitrary session loss and P c l o s s 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 M A P 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 ( I P P I n t e r r u p t e d P o i s s o n P r o c e s s ) flow with correlation coefficient equal to 0 is defined by the matrices

    D 0 = ( 0.4 0.16 0.24 1.3 69.4 68.1 1.3 1.3 270 ) D 1 = ( 0 0 0 0 0 0 100.2 167.2 0 )

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

    D 0 = ( 2.66 0.12 0.12 0.13 0.5 0.08 0.14 0.08 0.32 ) D 1 = ( 2.3 0.08 0.04 0.09 0.18 0.02 0.5 0.01 0.04 )

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

    D 0 = ( 3.16 0.12 0.12 0.1 0.45 0.09 0.12 0.11 0.39 ) D 1 = ( 2.84 0.06 0.02 0.02 0.21 0.03 0.02 0.04 0.1 )
  • MAP flow with correlation coefficient equal to 0.3 is defined by the matrices

    D 0 = ( 5.11 0.08 0.07 0.029 0.446 0.04 0.06 0.08 0.35 ) D 1 = ( 4.85 0.09 0.02 0.007 0.333 0.037 0 0.05 0.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

    D 0 = ( 3.607 0 0 0.617 ) D 1 = ( 0.347 3.26 0.478 0.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 P b l o s s of an arbitrary session loss and P c l o s s of an arbitrary request loss on the number K of tokens for the listed above different M A P s 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 different M A P 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 M A P 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 M A P / 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 P b l o s s and P c l o s s but larger number of sessions which can be simultaneously processed in the system without overloading the system. I P P 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 I P P 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 M A P 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 V c for 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 time V c 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 M A P process of sessions is defined by the matrices

D 0 = ( 6.88 0.0008 0.0008 0.22 ) D 1 = ( 6.8 0.0792 0.016 0.2032 )

This M A P 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.111 5 ] 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.8 0.98 ] This implies that the average session size varies in the interval [ 5 50 ] 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 V c 0.8. If we take θ greater than 0.8, restriction V c 0.8 is not fulfilled even only 1 session is allowed to enter the system. If the weaken this restriction to the restriction V c 8 four sessions can be processed in the system simultaneously for θ equal to 0.8. Situation when restriction V c 8 is 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 the I P P process defined above and vary the average arrival rate in the interval [ 1 11 ] by means of multiplication of the matrices D 0 and D 1 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 λ

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 M A P 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 I P P 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 μ

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 M A P s, only again the points of the jumps of the lines are different.

Advertisement

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.

Advertisement

Acknowledgments

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

References

  1. 1. Asmussen S. Nerman O. Olsson M. 1996 Fitting phase-type distributions via the EM algorithm. Scandinavian Journal of Statistics, 23 419 441 .
  2. 2. Chakravarthy S. R. 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. 3. Danzig D. 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. 4. Fisher W. Meier-Hellstern K. S. 1993 The Markov-modulated Poisson process (MMPP) cookbook. Performance Evaluation, 18 149 171 .
  5. 5. Heyman D. P. Lucantoni D. 2003 Modelling multiple IP traffic streams with rate limits, IEEE/ACM Transactions on Networking, 11 948 958 .
  6. 6. Kasten H. Runnenburg J. Th. 1956 Priority in waiting line problems, Mathematisch Centrum, Amsterdam, Holland.
  7. 7. Klemm A. Lindermann C. Lohmann M. 2003 Modelling IP traffic using the session Markovian arrival process. Performance Evaluation, 54 149 173 .
  8. 8. Klimenok V. Kim C. S. Orlovsky D. Dudin A. 2005 Lack of invariant property of Erlang loss model in case of the MAP input. Queueing Systems, 49 187 213 .
  9. 9. Kim C. S. Dudin S. Klimenok V. 2009 The queue with time phased arrivals as model for traffic control in telecommunication networks. Performance Evaluation, 66 564 579 .
  10. 10. Kist A. A. Lloyd-Smith B. Harris R. J. 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. 11. Lee M. H. Dudin S. Klimenok V. 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. 12. Lucantoni D. M. 1991 New results on the single server queue with a session Markovian arrival process. Communications in Statistics-Stochastic Models, 7 1 46 .
  13. 13. Neuts M. F. 1981 Matrix-geometric solutions in stochastic models. Baltimore, The Johns Hopkins University Press.
  14. 14. Panchenko A. Buchholz P. 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. 15. Pattavina A. Parini A. 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. 16. Riska A. Diev V. Smirni E. 2002 Efficient fitting of long-tailed data sets into hyperexponential distributions, Global Telecommunications Conference (GLOBALCOM’02, IEEE), 7-21 Nov. 2002, 2513 2517 .

Written By

Sergey Dudin and Moon Ho Lee

Published: March 1st, 2010