Share This Article:

Properties of the Estimators for the Effective Bandwidth in a Generalized Markov Fluid Model

Abstract Full-Text HTML XML Download Download as PDF (Size:1008KB) PP. 69-84
DOI: 10.4236/ojs.2018.81006    311 Downloads   550 Views   Citations

ABSTRACT

The Generalized Markov Fluid Model (GMFM), introduced in [1], is assumed for modeling sources in the network because it is versatile to describe the traffic fluctuations. In order to estimate resources allocations or in other words the channel occupation of each source, the concept of effective bandwidth proposed by Kelly [2] is used. In this paper, we present a formula for calculating the effective bandwidth, developed for the Generalized Markovian Flow model, which is of particular interest because it allows expressing said magnitude depending on the parameters of the model. We present unbiased estimators for these parameters that can be obtained from real data. The convergence and the consistency of the estimation are studied, and confidence bands are found. Illustrative calculation and performance of the proposed estimators were tested with simulated data and ideal results were obtained.

1. Introduction

A multiplexing system can be thought as a buffer with capacity B and output velocity C, fed by many different data sources that share the common output port. One of the more interest study subject is to know how many resources will each source required from the system. This knowledge has different applications to call admission, control and building. This magnitude of the required resources is known as the Effective Bandwidth of the traffic source and is an useful and realistic measure of channel occupancy. The best interpretation and collection of results on Effective Bandwidth are given in Kelly [2] where the Effective Bandwidth for a process X t , with stationary increments, that represents the total amount of work arriving from a source in the interval [ 0, t ] is defined as

α ( s , t ) = 1 s t log E e s X t , 0 < s , t < . (1)

This definition can be motivated in several ways, perhaps the most important is that the logarithmic moments generating function is naturally associated with the additive property of the sources in a node of the network. The space parameter s, measured in data units, point out the degree of the multiplexing. The time parameter t, measured in time units, it is related with period of greater buffer occupancy before overflow; slow accumulation of work load in the buffer corresponds to large values of t as well as fast accumulation corresponds to small values of t. Both parameters characterize the link operating point depending on the context of the stream.

The general problem is that resources are shared by a set of heterogeneous communications and when a new communication is accepted, its workload must be estimated to allocate part of the available resources. Therefore two problems motivate our work: to propose a realistic model for communications traffic and calculate the effective bandwidth for this model for the allocation of resources, and to obtain consistent estimators for the parameters.

The paper is organized as follows, the Generalized Markov Fluid Model model is introduced in Section 2, In Section 3, we compute de effective bandwidth for the introduced model and in Section 4 the proposed estimator is presented with its properties. Section 5 contains the numerical results of simulations, conclusions are presented in Section 6 and finally some useful lemmas are in the Appendix.

2. The Model

The needs for networks that integrate various telecommunication services leads to the emergence of the concept of integrated services digital network, which involves the use of a single infrastructure for transport, at high speeds, of data, voice and images. An important issue is the selection of the transfer process, which could be defined as the set of multiplexing mechanisms for commu- nication in the network. Through the concept of statistical multiplexing of sources, high efficiency is achieved in the use of network resources. If a source sends data at a variable rate, multiplexing the sources in a link, it reserves for each a capacity greater than the average rate but lower than the maximum emission rate. The price to pay is that the probability that many sources agree on dispatching the maximum rate is not zero, in which case overflow would occur with consequent damage to the Quality of Service (QoS).

To minimize these effects of data loss and maintain quality of service, both for existing sources as well as new, is necessary to have connection admission control (CAC) which to decide whether it can accept a new connection, as well as of congestion control mechanisms. For this we need mathematical models to describe the behavior of the sources.

The Generalized Markov Fluid

Markov Fluid models have been applied to model many kinds of digital sources but there are limitations when speed data transfers take too much values and the Generalized Markov Fluid model, introduced in [1] , can be used to describe properly those kind of traffic in a source.

In the GMFM, a source in a data network assumes the state Z t at time t, where Z is a continuous time, homogeneous and irreducible Markov chain, with finite state space K = { 1 , , k } , invariant distribution π and infinitesimal generator Z . That is, at time t the chain Z reaches states i and the rate data transfer of the sources is drawn, independently of the chain Z, by the law f i . So, the random variable Y t | Z t = i , is distributed according the probability law f i and the density functions f 1 , f 2 , , f k , are known and with disjoint support for i = 1 , , k .

The process Y does not change until the chain Z changes its state and since the supports of the k laws of probability are known and disjoint, observe the process Y t allow us to restore the process Z t .

The work load received from the source that delivers information with speed Y t is represented by the Markov flow modulated by the chain Z t and can be written as

X t = 0 t Y s d s . (2)

The advantage of the GMFM is that makes manageable those networks where the speed of the source in each state is a random variable. In this model, abrupt changes in the transfer speed report a change of state in the chain, but within a state is allowed the rate to assume randomly any value according to some probability distribution. The laws of probability may be discrete or continuous.

To interpret this model we could think that each state in the chain is interpreted as the activity performed by a user, like chat or video conferences, then speed data transfer assumes values that depend specifically for such activity.

3. Effective Bandwidth Estimation

One of the main issues in QoS for admission control is the estimation of the resources needed for guaranteed communications, which cannot be the peak rate because would be too pessimistic and would lead to resource waste, nor the mean rate of the service, because would be a too optimistic estimation, that would cause frequent losses. Given an expected QoS, interpreted as the probability of buffer overflow, the Effective Bandwidth (EB) of the traffic sources defined in (1), was proposed by Kelly in [2] and is a realistic measure of channel occupancy. The space and time parameters, s and t respectively, depend not only on the source itself, but on the context on which this source is acting as the capacity, the buffer size, the scheduling policy of the multiplexer, the QoS parameter to be achieved and the number of other sources in the channel, this is the actual traffic mix. The EB concept can be applied to sources or to aggregated traffic, as it can be the networks core link, but also it can be used for any shared resource models.

In order to estimate EB for a given GMFM, our first goal is to find the type of formulas obtained by Kesidis, Walrand and Chang [3] [4] to calculate the EB, that depends on estimable data from traffic traces.

Computation of the EB for the GMFM

Let { X t } t 0 be a GMFM modulated by a continuous time, homogeneous and irreducible Markov chain Z with finite state space K = { 1 , , k } and invariant distribution π and infinitesimal generator Z . Let Y i be the random variables with density function f i , mean μ i , variance σ i 2 and Laplace transform ϕ i ( t ) , for i = 1 , , k . Let us also assume that each f i has known and disjoint support [ c i , c i + 1 ) + with c i < c i + 1 . Let us denote the diagonal matrix of dimension k, whose nonzero elements are the first moments μ i of each distribution.

Theorem 1. Let { X t } t 0 be a GMFM, then the effective bandwidth has the following expression

α ( s , t ) = 1 s t log { π exp [ ( Z + s ) t ] 1 } , (3)

where 1 is a column vector with all entries equal to 1.

Proof. By definition (1), it is enough to proof E ( e s X t ) = π e x p [ ( Z + s ) t ] 1 .

The process X t can be represented as in (2) and Y t is uniformly bounded, hence applying Lebesgue’s dominated convergence theorem

E ( e s X t ) = l i m n E ( e s t n r = 1 n Y r t n ) . (4)

The Markov chain Z s is homogeneous and π is the invariant distribution, so the argument of the limit in (4) can be written as

( i 0 , , i n ) K n + 1 π ( i 0 ) [ j = 0 n 1 ( P t n Z ( i j , i j + 1 ) ( + ) e s t n u j + 1 f i j + 1 ( u j + 1 ) d u j + 1 ) ] . (5)

Each integral in (5) represents the Laplace transform of the density function, so we can express the right side as the product of the transition matrix and a

diagonal matrix [ C t n ] , whose non zero elements are ( C t n ) i , i = ϕ i ( s t n ) , in the next way

π [ [ P t n Z ] [ C t n ] ] n 1 .

Applying Taylor’s formula to each matrix we obtain

P t n Z = P 0 Z + ( P t Z ) t = 0 t n + o ( t n ) = I + Z t n + o ( t n ) , (6)

C t n = C 0 + ( C t ) t = 0 t n + o ( t n ) = I + s t n + o ( t n ) , (7)

with I the identity matrix and a diagonal matrix which non zero element are ϕ i ( 0 ) = μ i .

Then,

[ [ P t n Z ] [ C t n ] ] n = [ I + ( Z + s ) t n + o ( t n ) ] n , (8)

and the right side of (8) tends to e x p [ ( Z + s ) t ] . ☐

The importance of this result is that provides an expression for the EB that depends on the infinitesimal generator of the modulating chain, its invariant distribution and a matrix containing information of the transfer rate, and all these elements can be estimated with traffic traces.

4. The estimator and its Properties

In order to introduce an estimator for the EB to this traffic model, the elements of the matrices Z and are the parameters that must be estimated according to the equation (3).

For the first, a result presented by Lebedev and Lukashuk [5] [6] plays a key role in the construction of our estimator, providing asymptotically gaussian estimator, based on traffic traces, of the infinitesimal generator matrix. The maximum likelihood estimator q i j ( n ) of each element q i j not belonging to the diagonal of infinitesimal generator matrix, is the ratio between the number of transitions of the chain Z from the state i to the state j and the time spent by the chain Z in the state i, both during the same unitary time interval. So defined

q i j ( n ) is unbiased with variance q i j π ( i ) , where π ( i ) is the i-th element in the vector of the invariant distribution π .

4.1. The estimator of the elements of

The elements of are the mean data transfer rate μ i at each state i of the chain Z. The proposed estimator is

μ i ( n ) = r = 1 N i ( n ) Y i ( r ) N i ( n ) , (9)

where Y i ( r ) denotes the r-th observed rate corresponding to the range of Y when modulating chain is in state i and N i ( n ) the number of times that the modulating chain Z reaches the state i in the interval [ 0, n ] .

Before proving the following results let us remark that the random value N i ( n ) grows as the observed range n increases and due to assumptions about the chain Z, each states i is positive recurrent with average turnaround time 1 / λ i satisfying this relationship

N i ( n ) n c .s . λ i . (10)

Proposition 2. Let { X t } t 0 be a GMFM and μ i ( n ) defined in (9), then

1) μ i ( n ) is an unbiased and consistent estimator of μ i .

2) n ( μ i ( n ) μ i ) n w N ( 0, σ i 2 λ i ) .

Proof. 1) Let us compute the expected value of (9) using conditional expectation

E ( μ i ( n ) ) = E ( E ( μ i ( n ) | N i ( n ) ) ) (11)

= E ( j E ( Y i ( j ) | N i ( n ) ) N i ( n ) ) (12)

= μ i (13)

so μ i ( n ) is unbiased.

To prove consistence it is enough to show that the variance of (9) tend to 0 as n grows. The second moment can be compute similarly

E ( ( μ i ( n ) ) 2 ) = E ( E ( μ i ( n ) ) 2 | N i ( n ) ) (14)

= E ( j = 1 N i ( n ) k = 1 N i ( n ) E ( Y i ( j ) Y i ( k ) | N i ( n ) ) N i 2 ( n ) ) , (15)

Replacing E ( Y i ( k ) Y i ( j ) | N i ( n ) ) = ( σ i 2 + μ i 2 ) δ k j + μ i 2 ( 1 δ k j ) , where δ k j is the Kronecker delta, this is δ k j = 1 if k = j and 0 elsewhere, we obtain

E ( ( μ i ( n ) ) 2 ) = E ( 1 N i 2 ( n ) ( μ i 2 N i 2 ( n ) + σ i 2 N i ( n ) ) ) (16)

= μ i 2 + σ i 2 E ( 1 N i ( n ) ) , (17)

and then

V ( μ i ( n ) ) = σ i 2 E ( 1 N i ( n ) ) σ i 2 λ i n , (18)

that tends to 0 as n grow, hence consistence is proved.

2) Applying a classic Central Limit Theorem [7] , to the variables Y i ( r ) , it is true that

n ( r = 1 [ λ i n ] Y i ( r ) λ i n μ i ) n w N ( 0 , σ i 2 λ i ) . (19)

A classic result of the stochastic process theory, see [8] , will allow us to achieve the result by just proving that E ( r = 1 N i ( n ) Y i ( r ) N i ( n ) r = 1 [ λ i n ] Y i ( r ) λ i n ) 2 n 0 .

E ( r = 1 N i ( n ) Y i ( r ) N i ( n ) r = 1 [ λ i n ] Y i ( r ) λ i n ) 2 2 ( E ( r = 1 N i ( n ) Y i ( r ) ( 1 N i ( n ) 1 λ i n ) ) 2 (20)

+ E ( r = 1 N i ( n ) Y i ( r ) r = 1 [ λ i n ] Y i ( r ) λ i n ) 2 ) . (21)

Calculating the first term by conditional expectation we obtain

E ( r = 1 N i ( n ) Y i ( r ) ( 1 N i ( n ) 1 λ i n ) ) 2 = ( λ i n N i ( n ) ) 2 ( λ i n N i ( n ) ) 2 ( σ i 2 N i ( n ) + μ i 2 N i 2 ( n ) ) (22)

= ( 1 N i ( n ) λ i n ) 2 ( 1 N i ( n ) σ i 2 + μ i 2 ) , (23)

that tends to 0 as n grows.

The argument in de expectation of the second term can be written like

r = 1 N i ( n ) Y i ( r ) r = 1 [ λ i n ] Y i ( r ) λ i n = m M Y i ( r ) λ i n , (24)

where m = min ( N i ( n ) , [ λ i n ] ) and M = max ( N i ( n ) , [ λ i n ] ) , so similarly we compute

E ( m M Y i ( r ) λ i n ) 2 = E ( m M m M E ( Y i ( k ) Y i ( j ) / N i ( n ) ) λ i 2 n 2 ) (25)

= σ i 2 ( M m ) + μ i 2 ( M m ) 2 λ i 2 n 2 . (26)

But M m = | N i ( n ) [ λ i n ] | , so (26) becomes into

| N i ( n ) [ λ i n ] | λ i 2 n 2 σ i 2 + ( 1 N i ( n ) λ i n ) 2 μ i 2 , (27)

that also tends to 0 as n grows, and the theorem is proved. ☐

4.2. The estimator of α ( s , t )

From the maximum likelihood estimators of λ i j and the estimator of μ i in (9), a estimator of (3) can be construct. Let us define Λ n = ( λ i j ( n ) ) 1 i j k and ϒ n = ( μ i ( n ) ) 1 i k the vector with de no diagonals elements of and res- pectively.

Let us also define some functions that allow to build the matrices from the vectors presented above, they are Q : k ( k 1 ) M k × k such that Q ( Λ ) = , where = ( Q i j ) 1 i , j k such that Q i j = q i j if i j and Q i j = j = 1 , j i j = k q i j = q i i if i = j ; H : k M k × k such that H ( ϒ ) = , where = ( H i j ) 1 i , j k is de- fined H i j = μ i if i = j and 0 otherwise.

Finally, another function whose response is a matrix that gives the same information that but that has the advantage of admitting inverse is defined

as Q ^ ( Λ ) = ^ , where ^ = ( Q ^ i j ) 1 i , j k is such that Q ^ i j = q i j if j < k and 1 if j = k .

Since , Λ and ^ contain exactly the same information, we can think any parameter that depends on as a function of Λ .

We are now able to present the following result that gives the asymptotic distribution of (3).

Theorem 3. Let X t be a GMFM, the vectors Λ n = ( λ i j ( n ) ) 1 i j k , and ϒ n = ( μ i ( n ) ) 1 i k containing the estimators of λ i j and μ i respectively. Let us define the following functions:

B : k ( k 1 ) × k M k × k , that B ( Λ , ϒ ) = e x p [ ( Q ( Λ ) + H ( ϒ ) s ) t ] , (28)

g : k ( k 1 ) × k , that g ( Λ , ϒ ) = π ( Λ ) B ( Λ , ϒ ) 1 , (29)

Ψ : k ( k 1 ) × k , that Ψ ( Λ , ϒ ) = 1 s t l o g ( g ( Λ , ϒ ) ) . (30)

Then, for fixed s and t, α ( n ) ( s , t ) = Ψ ( Λ n , ϒ n ) follows that

n ( α ( n ) ( s , t ) α ( s , t ) ) n w N ( 0, σ 2 ) , (31)

with σ 2 = Ψ ( Λ , ϒ ) Σ Ψ ( Λ , ϒ ) t , where

Σ = [ λ 11 π ( 1 ) λ k ( k 1 ) π ( k ) σ 1 2 λ 1 σ k 2 λ k ] .

Proof. As λ i j ( n ) , μ i ( n ) are unbiased, asymptotically gaussian, and the functions used to construct α ( n ) ( s , t ) in (31) are differentiable so applying Lemma (6) and Lemma (7) in Appendix the result holds. Then σ 2 can be written more precisely like

σ 2 = 1 ( s t π ( Λ ) B ( Λ , ϒ ) 1 ) 2 × [ ( i , j ) D q i j π ( i ) ( π ( Λ ) q i j B ( Λ , ϒ ) 1 + π ( Λ ) l = 0 r = 0 l 1 A ( Λ , ϒ ) 1 ) 2 + i = 1 k σ i 2 λ i ( π ( Λ ) l = 0 r = 0 l 1 A ( Λ , ϒ ) 1 ) 2 ] , (32)

where

A i j ( Λ , ϒ ) = l = 0 r = 0 l 1 t l l ! ( Q ( Λ ) + H ( ϒ ) s ) r V i j ( Q ( Λ ) + H ( ϒ ) s ) l r 1 , (33)

A i ( Λ , ϒ ) = l = 0 r = 0 l 1 t l s l l ! ( Q ( Λ ) + H ( ϒ ) s ) r U i ( Q ( Λ ) + H ( ϒ ) s ) l r 1 , (34)

and ( V i j ) l m = { 1 if i = l and j = m i 1 if l = i = m 0 otherwise , ( U i ) l m = { 1 if l = m = i 0 otherwise .

4.3. Consistency of the Estimators

We show now the main result that allows us to find consistent estimators for each parameter involved in the formula of the variance σ 2 obtained in the Theorem 3.

Proposition 4. Let Λ n = ( λ i j ( n ) ) 1 i j k , and ϒ n = ( μ i ( n ) ) 1 i k containing the estimators of λ i j and μ i respectively then

1) p n = e k Q ^ 1 ( Λ n ) is a consistent estimator of π ( Λ ) .

2) d p n i j = e k Q ^ 1 ( Λ n ) Q ^ ( Λ ) q i j Q ^ 1 ( Λ n ) is a consistent estimator of π ( Λ ) q i j .

3) B n = l = 0 m n t l ( Q ( Λ n ) + H ( ϒ n ) s ) l l ! is a consistent estimator of

B ( Λ , ϒ ) = e x p [ ( Q ( Λ ) + H ( ϒ ) s ) t ] .

4) S n = s t p n B n 1 is a consistent estimator of S = s t π ( Λ ) B ( Λ , ϒ ) 1 .

Proof.

1) By definition ^ = Q ^ ( Λ ) and π ^ = e k , then by Lema 8 in Appendix, π = e k ^ 1 . As Λ n n a . s . Λ and Q ^ ( Λ ) is continuous then Q ^ ( Λ n ) n a . s . Q ^ ( Λ ) .

On the other hand Q ^ 1 is also continuous, then for n large enough, Q ^ ( Λ n ) admits inverse and it is fulfilled that Q ^ 1 ( Λ n ) n a . s . Q ^ 1 ( Λ ) , so p n = e k Q ^ 1 ( Λ n ) is a consistent estimator of π ( Λ ) .

2) As π ( Λ ) = e k Q ^ 1 ( Λ ) , then π ( Λ ) q i j = e k Q ^ 1 q i j , and by Lemma 8 in Appendix

Q ^ 1 q i j = Q ^ 1 ( Λ ) Q ^ 1 q i j Q ^ 1 ( Λ ) . (35)

But Q ^ 1 ( Λ n ) is a consistent estimator of Q ^ 1 ( Λ ) , then d p n i j = e k Q ^ 1 ( Λ n ) Q ^ ( Λ n ) q i j Q ^ 1 ( Λ n ) is a consistent estimator of π ( Λ ) q i j .

3) To prove that B n n a . s . B ( Λ , ϒ ) , or equivalently | B n B ( Λ , ϒ ) | n 0 , let us remember that the matrix B ( Λ , ϒ ) it can be written in two equivalent ways as follows

B ( Λ , ϒ ) = e x p [ ( Q ( Λ ) + H ( ϒ ) s ) t ] = l = 0 t l l ! ( ( Q ( Λ ) + H ( ϒ ) s ) l ) . (36)

Then

B n B ( Λ , ϒ ) = l = 0 m n t l l ! [ ( Q ( Λ n ) + H ( ϒ n ) s ) l ( Q ( Λ ) + H ( ϒ ) s ) l ] + l = m n + 1 t l l ! ( Q ( Λ ) + H ( ϒ ) s ) l . (37)

The second term is the tail of a convergent series, therefore it tends to 0 when n grows.

For the first term, we will apply the Mean Value Theorem defining the function f : M k × k M k × k such that f ( M ) = M l , to express the increment of the function as a proportion of the argument increment through the differential operator in the following way then

f ( B n ) f ( B ) = D f ( B ˜ n ) ( B n B ) , (38)

where B ˜ n is between B n and B , or in other way (38) can be written D f ( B ˜ n ) ( ( Q ( Λ n ) Q ( Λ ) ) + ( H ( ϒ n ) H ( ϒ ) ) s ) .

By definition of differential operator to f ( A ) , equation (38) becomes into

f ( B n ) f ( B ) = i = 0 l 1 B ˜ n i ( ( Q ( Λ n ) Q ( Λ ) ) + ( H ( ϒ n ) H ( ϒ ) ) s ) B ˜ n l i 1 , (39)

so we have

l = 0 m n t l l ! [ ( Q ( Λ n ) + H ( ϒ n ) s ) l ( Q ( Λ ) + H ( ϒ ) s ) l ] (40)

= l = 0 m n t l l ! i = 0 l 1 B ˜ n i ( ( Q ( Λ n ) Q ( Λ ) ) + ( H ( ϒ n ) H ( ϒ ) ) s ) B ˜ n l i 1

l = 0 m n t l l ! i = 0 l 1 B ˜ n l 1 ( ( Q ( Λ n ) Q ( Λ ) ) + ( H ( ϒ n ) H ( ϒ ) ) s ) (41)

l = 0 m n t l l ! l B ˜ n l 1 ( ( Q ( Λ n ) Q ( Λ ) ) + ( H ( ϒ n ) H ( ϒ ) ) s ) (42)

= ( ( Q ( Λ n ) Q ( Λ ) ) + ( H ( ϒ n ) H ( ϒ ) ) s ) t l = 0 m n t l 1 ( l 1 ) ! B ˜ n l 1 . (43)

As l = 0 m n t l 1 ( l 1 ) ! B ˜ n l 1 is bounded by being the partial sum of a convergent

series, and both Λ n as ϒ n are consistent estimator of Λ and ϒ respectively, each terms of the first factor tend to 0, so B n is a consistent estimator of B .

4) This point is derived directly from the points 1 and 3.

4.4. Confidence interval for α ( s , t )

The following theorem and corollary show how to perform numerical computation using the main result.

Theorem 5. Let q i j ( n ) be the maximum likelihood estimators of Q, S n , p n , d p n and B n the estimators presented in the proposition above, and m n a succession of positive real numbers such that m n n , then

σ n 2 = 1 S n 2 [ i = 1 k j = 1 k 1 q i j ( n ) p n ( i ) ( d p n i j B n 1 + p m i j l = 0 m n r = 0 l 1 A ( Λ n , ϒ n ) 1 ) 2 + l = 1 k σ i ^ 2 λ i ^ ( p n i j l = 0 m n r = 0 l 1 A ( Λ n , ϒ n ) 1 ) 2 ] , (44)

is a consistent estimator of σ 2 , with A ( , ) and A ( , ) defined as in (33) and (34) respectively.

The main argument in the proof is the differentiability , and a straightforward consequence of the theorem is the following result,

Corollary 1. Taking α ( s , t ) , α ( n ) ( s , t ) and σ n 2 defined in (3), (31) and (44) respectively, we have

1) n ( α ( n ) ( s , t ) α ( s , t ) ) σ n 2 n w N ( 0,1 ) .

2) If I α ( n ) = [ α ( n ) ( s , t ) z ϵ σ n n , α ( n ) ( s , t ) + z ϵ σ n n ] , where z ϵ is such that P ( Z > z ϵ ) = ϵ 2 for Z ~ N ( 0,1 ) , then

l i m n P ( α ( s , t ) I α ( n ) ) = 1 ϵ . (45)

5. Simulation and Numerical results

In this section we will carry out the analysis with traffic traces generated by simulations from the model introduced in Section 2 to perform the estimations.

5.1. Parameters for the Simulation

To validate the results obtained, we performed several traffic simulations according to the GMFM model presented.

In the model chosen, the modulating Markov chain has k = 13 states and each state is associated with a data transfer rate interval as shown in Table 1.

It is expected the usual state to be that of the highest transfer rate available in the transmission channel, so the most probable state is 13. It is also more common to jump from one state to the adjacent ones, or to the maximum transfer rate, or minimum or no transfer rate. With these considerations it is designed the infinitesimal generator of the modulating chain that is given by the matrix

Q = ( 7 2 0.13 0.13 0.13 0.13 0.13 0.13 0.13 0.13 0.13 0.13 3.75 2 7 2 0.13 0.13 0.13 0.13 0.13 0.13 0.13 0.13 0.13 1.88 1 2 7 2 0.13 0.13 0.13 0.13 0.13 0.13 0.13 0.13 1 1 0.125 2 7 2 0.13 0.13 0.13 0.13 0.13 0.13 0.13 1 1 0.125 0.13 2 7 2 0.13 0.13 0.13 0.13 0.13 0.13 1 1 0.125 0.13 0.13 2 7 2 0.13 0.13 0.13 0.13 0.13 1 1 0.125 0.13 0.13 0.13 2 7 2 0.13 0.13 0.13 0.13 1 1 0.125 0.13 0.13 0.13 0.13 2 7 2 0.13 0.13 0.13 1 1 0.125 0.13 0.13 0.13 0.13 0.13 2 7 2 0.13 0.13 1 1 0.125 0.13 0.13 0.13 0.13 0.13 0.13 2 7 2 0.13 1 1 0.125 0.13 0.13 0.13 0.13 0.13 0.13 0.13 2 7 2 1 2 0.20 0.20 0.20 0.20 0.20 0.20 0.20 0.20 0.20 0.20 8 4 2 0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.30 0.30 5.00 10 ) .
(46)

Within each of these intervals, it is raffled how much is actually dispatched by means of a normal distribution truncated to the interval with mean equal to the midpoint of the interval and deviation equal to one sixth of the length of the interval. The diagonal matrix will contain the mean values of these distri- butions.

Table 1. Transfer speed.

An example of the traces generated for the simulations can be seen in Figure 1.

5.2. Estimation of the Effective bandwidth from traces

The first objective is to calculate the EB of the presented model, for which we will use the result shown in Theorem 1, and the EB is then calculated according to the formula (3). Figure 2 shows the EB calculated for the GMFM.

For each simulated trace we estimate the EB using the estimator presented in Theorem 2 according to the equation (31) and in Figure 3 the comparison of the estimated effective bandwidth for a trace with the theoretical value is shown.

Figure 1. Trace generated with the GMFM.

Figure 2. Effective bandwidth for the GMFM model.

Figure 3. Effective bandwidth vs. Estimated effective bandwidth.

6. Conclusions

In this work, we have presented contributions in two areas related to data networks. About the modeling, we have proposed the GMFM that has the advantage of being very realistic for the current requirements of telecommunication networks, in which it is possible to apply refined tools and mathematical statistics results. We have also found a formula for the effective bandwidth where can be visualized the role that play each parameters of the model.

Regarding the estimation of parameters, we have proposed a methodology to estimate the effective bandwidths, from traffic traces of a GMFM source, which has the expected properties to ensure that it complies with a Central Theorem of Limit and thus be able to build a confidence interval. These results enable the calculation of the effective bandwidth from simulated traffic traces. A numerical example has been presented, where the results were applied to traffic traces and ideal results were obtained.

It is expected to extend statistical effective bandwidth calculation to other stochastic phenomena where the supports of each probability law are not disjoint, or which do not need to be Markovian and the application of these techniques to real data scenarios.

Acknowledgements

The authors express their gratitude to Dr. Gonzalo Perera for introducing them to the topic and for his valuable suggestions.

Appendix

Lemma 6. Let ( Z n ) n be a sequence of random variables in d , d 1 , ( a n ) n sequence of positive numbers satisfying a n and Z d such that

a n ( Z n Z ) n w N ( 0, Σ ) . (a1)

Let us consider G : d differentiable in an neighborhood of Z, then

a n ( G ( Z n ) G ( Z ) ) n w N ( 0, G ( Z ) Σ G ( Z ) t ) . (a2)

Lemma 7. Let us consider Ψ as in (30), g as in (29) and B as in (28), and Q : k ( k 1 ) M k × k and H : k M k × k defined in Section 4.2, then

1) Ψ ( Λ , ϒ ) q i j = 1 s t g ( Λ , ϒ ) g ( Λ , ϒ ) q i j .

2) Ψ ( Λ , ϒ ) μ i = 1 s t g ( Λ , ϒ ) g ( Λ , ϒ ) μ i .

3) g ( Λ , ϒ ) q i j = π ( Λ ) q i j B ( Λ , ϒ ) 1 + π ( Λ ) ( l = 0 r = 0 l 1 t l l ! ( Q ( Λ ) + H ( ϒ ) s ) r V i j ( Q ( Λ ) + H ( ϒ ) s ) l r 1 ) 1 ,

with ( V i j ) l m = { 1 si i = l y j = m i 1 si l = i = m 0 otherwise .

4)

g ( Λ , ϒ ) μ i = π ( Λ ) ( l = 0 r = 0 l 1 t l s l l ! ( Q ( Λ ) + H ( ϒ ) s ) r U i ( Q ( Λ ) + H ( ϒ ) s ) l r 1 ) 1 ,

with ( U i ) l m = { 1 si l = m = i 0 otherwise .

Lemma 8. The matrix ^ = Q ^ ( Λ ) supports inverse Q ^ 1 ( Λ ) that is differentiable and fulfills

D ( Q ^ 1 ) ( Λ ) ( x ) = Q ^ 1 ( Λ ) D ( Q ) ( Λ ) Q ^ 1 ( Λ ) ( x ) . (A3)

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Bavio, J. and Marrón, B. (2018) Properties of the Estimators for the Effective Bandwidth in a Generalized Markov Fluid Model. Open Journal of Statistics, 8, 69-84. doi: 10.4236/ojs.2018.81006.

References

[1] Marrón, B.S. (2012) Estadstica de Procesos Estocásticos aplicados a Redes de Datos y Telecomunicación. Ph.D. Thesis, Departamento de Matemática, Universidad Nacional del Sur, Argentina.
http://repositoriodigital.uns.edu.ar/bitstream/123456789/2302/1/Marron-Beatriz-Tesis.pdf
[2] Kelly, F. (1996) Notes on Effective Bandwidths. Stochastics Netwoks: Theory and Applications. Oxford University Press, Oxford.
[3] Kesidis, G., Walrand, J. and Chang, C.S. (1993) Effective Bandwidth for Multiclass Markov Fluids and Other ATM Sources. IEEE/ACM Transactions on Networking, 1, 424-428.
https://doi.org/10.1109/90.251894
[4] Pechiar, J., Perera, G. and Simón, M. (2002) Effective Bandwidth Estimation and Testing for Markov Sources. Performance Evaluation, 45, 157-175.
https://doi.org/10.1016/S0166-5316(02)00035-4
[5] Lebedev, E.A. and Lukashuk, L.I. (1986) Maximum Likelihood Estimation of the Infinitesimal Matrix of a Markov Chain with Continuous Time (in Russian). Doklady Akademii Nauk Ukrainskoj SSR Serija A, 1, 12-14.
[6] Albert, A. (1962) Estimating the Infinitesimal Generator of a Continuous Time, Finite State Markov Process. The Annals of Mathematical Statistics, 33, 727-753.
https://doi.org/10.1214/aoms/1177704594
[7] Feller, W. (1957) An Introduction to Probability Theory and Its Applications. John Wiley, New York.
[8] Billingsley, P. (1979) Probability and Measures. Wiley & Sons, New York.

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.