当前位置：文档库 › Responsible Editor I.F. Akyildiz

Responsible Editor I.F. Akyildiz

Simple models of network access,with applications to the design of joint rate and admission control

Michel Mandjes a,b,c,*,Debasis Mitra a,Werner Scheinhardt b,c

a Bell Laboratories/Lucent Technologies,P.O.Box636,Murray Hill,NJ07974,USA

b Faculty of Mathematical Sciences,University of Twente,P.O.Box217,7500AE Enschede,Netherlands

c CWI,Kruislaan413,P.O.Box94079,1090GB Amsterdam,Netherlands

Received10September2002;accepted25October2002

Responsible Editor:I.F.Akyildiz

Abstract

At the access to networks,in contrast to the core,distances and feedback delays,as well as link capacities are small, which has network engineering implications that are investigated in this paper.We consider a single point in the access network which multiplexes several bursty users.The users adapt their sending rates based on feedback from the access multiplexer.Important parameters are the user?s peak transmission rate p,which is the access line speed,the user?s guaranteed minimum rate r,and the bound on the fraction of lost data.

Two feedback schemes are proposed.In both schemes the users are allowed to send at rate p if the system is relatively lightly loaded,at rate r during periods of congestion,and at a rate between r and p,in an intermediate region.For both feedback schemes we present an exact analysis,under the assumption that the users?job sizes and think times have exponential distributions.We use our techniques to design the schemes jointly with admission control,i.e.,the selection of the number of admissible users,to maximize throughput for given p,r,and .Next we consider the case in which the number of users is large.Under a speci?c scaling,we derive explicit large deviations asymptotics for both models.We discuss the extension to general distributions of user data and think times.

1.Introduction

In today?s communication networks,design and control of the network core and access are di?erent,primarily because of the di?erences in scale in bandwidth and distance.Quite often the bottleneck is the access,rather than the core.This may happen because the access network is characterized by relatively low line speeds and the limited ability of users to bu?er and shape tra?c(think of the ex-treme case of a user with a wireless handset).Access control,supported by the use of feedback,is an important mechanism to address this problem. S ince distances between users/clients and network access points are relatively short,feedback delay

*Corresponding author.Address:Faculty of Mathematical

Sciences,University of Twente,P.O.Box217,7500AE

Enschede,Netherlands.

E-mail addresses:michel.mandjes@cwi.nl(M.Mandjes),

mitra@https://www.wendangku.net/doc/f413292099.html,(D.Mitra),werner@math.utwente.nl(W.

Scheinhardt).

2Computer Networks41(2003)

489–504

https://www.wendangku.net/doc/f413292099.html,/locate/comnet

due to propagation is negligible,which contributes to the e?cacy of feedback control.In this paper we investigate the problems of access control by in-troducing simple models and techniques for their evaluation,design and performance optimization.

We make three main contributions.First,we present two simple models of network access.The models provide a framework for the joint design of feedback-based schemes for the adaptation of source rates and admission control.Second,we show how to compute the stationary behavior of the aforementioned feedback queues.We illustrate the use of these techniques to solve the design problem.Finally we show how to use the theory of large deviations to obtain explicit results when the system and the number of sources is large.

In our model each user alternates between?on?periods of transmission,and?o??periods or?think times?.The user model here di?ers from the fa-miliar on–o?source models,e.g.[2],in that?le sizes(where a?le size is the amount of data the source transmits during an active period)are in-dependent,identically distributed(i.i.d.)random variables,but the on periods are not speci?ed a priori.The on-periods are determined by the combination of the?le sizes and the transmission rates allocated by the access control scheme,to be described below,which depend on the interaction of the multiplexer with the collective behavior of users.In contrast,the think times are i.i.d.random variables.The lengths of on periods and the throughputs of the individual users are key per-formance quantities to be obtained from an anal-ysis of the model.

The access line speed(p for each of the users)is typically small compared to the output rate of the access multiplexer,and therefore constitutes an important constraint.

Another model feature is the minimum throughput rate(r)that is guaranteed to the users. In a number of applications clients derive zero utility if the throughput is below a threshold.This point has been made by Massouli e and Roberts [18]for the case of TCP tra?c,in which perfor-mance collapse may ensue.As soon as the notion of a minimum guaranteed rate is introduced,ad-mission control needs to be considered,together with the calculation of the capacity of the network.

We present two schemes for feedback-based adaptation of the users?rates.In both schemes users are allowed to transmit at rate p if the system is relatively lightly loaded,at rate r during periods of congestion,and at a rate between r and p,which is determined by the processor sharing discipline,in an intermediate region.In our model the feedback signal from the bu?er to the sources is assumed to arrive with negligible delay,which is reasonable when the round trip distances are small.In the?rst scheme the feedback is based on the number of active users and whether the queue is empty or not. The second scheme utilizes a threshold B?on the bu?er content.Depending on whether the bu?er content is less than,greater than,or equal to B?,the user rate is p,r,or determined by the processor sharing discipline,respectively.Importantly,the second scheme does not require knowledge of the (activity)state of the users,and is simpler to im-plement on that count.However,the analysis of the ?rst queue is simpler and our results for it are in closed form.As discussed below,the combined use of the threshold and the number of admissible users in the second model provides a greater facility for regulating important trade-o?s.

We note a feature of the behavior of the models, which is counter-intuitive.Our analysis shows that the e?ect of feedback is to increase the mean time that the bu?er is empty,while simultaneously in-creasing the throughputs of the users.The expla-nation of this apparently paradoxical behavior is that the rates allocated to the users are higher during the periods that the bu?er is empty.Hence feedback has the e?ect of reducing the on periods and consequently the cycle time of each user,and thereby it increases individual users?throughput and the system throughput,which is de?ned as the sum of the individual users?throughputs.

Next consider the role of the feedback parame-ter B?,the threshold level in the bu?er content in the second model.By reasoning as above,we infer that increasing B?has the e?ect of increasing the throughput of the users.However,this is at the cost of increasing the probability of bu?er over?ow. Similarly,with all other parameters held?xed,in-creasing the number of users N has the e?ect of increasing both the total system throughput as well as the probability of bu?er over?ow.Hence,this

490M.Mandjes et al./Computer Networks41(2003)489–504

model allows the study of interesting trade-o?s between several important quantities,including the individual users?throughput,the system through-put,the loss probability and the number of users. By proper design the parameters B?and N can regulate the trade-o?.

There are several possible frameworks in which the trade-o?s may be studied and quanti?ed.We require that the fraction of source data that is lost does not exceed a given Quality of Service(QoS) parameter .Then we may seek a joint design of the feedback control scheme and admission con-trol,i.e.,selection of B?and N such that the system throughput is maximized.The numerical proce-dure that is developed in this paper allows such design questions to be addressed.Indeed one of the highlights of the numerical results that we present later in the paper is the computed solution for an instance of the above design problem.

The two proposed feedback schemes both fall into the category of feedback?uid queues,which were introduced in[24]as generalizations of the well-known Markov-modulated?uid models in [2,15].In the latter,a?uid bu?er receives or depletes ?uid at rate r i(positive or negative)at times when a background continuous-time Markov chain is in state i.Typically,stochastic?uid models are char-acterized by the generator(Q)of the background process and a diagonal rate matrix(R)which con-tains all?uid rates r i.In feedback?uid queues most of the above remains true,except that the behavior of the background process(i.e.the matrix Q),and possibly the matrix R as well,depends on the current bu?er content.As a result the background process is no longer an autonomous Markov process.In this paper we con?ne ourselves to feedback?uid queues in which Q and R are piecewise constant functions of the bu?er content level,see also[25]. Notice the crucial di?erence with[9],in which there are also thresholds,like here,but these only a?ect R, and not also Q.The analysis of these feedback?uid queues,based on spectral expansions[2,8,9,15],is one of the main contributions of this paper.

An intrinsic drawback of the analytical ap-proach described so far is that it is computationally intensive.This provides motivation for simpler, asymptotic approaches to deal with the access models.In both access models,we study large-deviations asymptotics for the scaling introduced by Weiss[28],i.e.the regime in which the number of users grows large and resources(bu?er and bandwidth)scale proportionally.We derive?expo-nential approximations?,comparable to those in [3,4,7]for the ordinary FIFO discipline.Expo-nential approximations of the?rst feedback model, i.e.,without the threshold,were obtained earlier by Ramanan and Weiss[21]for exponential?le sizes and think times.Our major contribution is that these results are explicit and the computations are simple.Some of them have nice insensitivity properties,i.e.,depend on the distributions of the think times and job sizes only through their means.

The role of feedback in packet networks has a long history,see[26,Chapter7]for a review.Re-cently there has been a resurgence of interest, driven in part by work on explicit congestion no-ti?cation(ECN)marking schemes by Gibbens and Kelly[10,11,14],and others.In[20]a feedback model with feedback delays is considered based on the marking scheme of[8].However,the feedback considered there regulates the marking of packets to be dropped later on,whereas in our model the feedback regulates the actual source rate.The processor sharing discipline has been highlighted in recent work on QoS delivery by Roberts et al. [22,23],albeit in the bu?erless framework.

The organization of the paper is as follows. Section2deals with the?rst access model.Section 3considers the more advanced feedback scheme that utilizes a threshold.The large deviations as-ymptotics are described in Section4.Finally Sec-tion5reports on several numerical examples.

For reasons of space we have had to omit sev-eral general results,speci?cally a treatment of general feedback?uid queues,including?nite bu?ers and multiple thresholds,and the large de-viations asymptotics for the feedback model with a threshold.These results are in[17].

2.Feedback model without threshold

2.1.Model

We model a single aggregation or multiplexing point in the network.The output trunk speed is C,

M.Mandjes et al./Computer Networks41(2003)489–504491

and there are N access links.The peak(or line)rate of each access link is p.The minimum rate given to each access user is r.We make the simplifying modeling assumption that tra?c can be considered to be continuous?uid.For the bene?t of the reader,we note that in?uid models there may be considerable transfer of?uid,i.e.,high through-put,even during periods when the bu?er is empty.

This is because in?uid models,once the bu?er is empty,it remains empty for as long as the total input rate does not exceed the output capacity.

In this section we describe the scheme without threshold.When the multiplexer bu?er is empty, the access rate will be determined by dividing equally the trunk rate between the(small)number of active users,truncated to p.At the other ex-treme,when the number of active users exceeds a critical number,N00in this work,then the fair share of the trunk rate for an active user drops below the guaranteed rate of r,and the bu?er is no longer empty and its content grows.As long as the bu?er content is positive,each source is assigned the rate of just r.Clearly,N00is the largest integer not ex-ceeding C=r.

While the bu?er is empty and the number of active users is small,say below a critical number N0,then each active user transmits at peak access rate p.It is easily seen that N0is the largest integer not exceeding C=p.When the number of active users is between N0and N00,which is the middle range,and the bu?er is empty,then the trunk speed is shared equally,i.e.,the processor sharing regime holds.Hence,when the bu?er is empty there are two regimes characterized respectively by the access line speed and the processor sharing rate.In contrast,when the bu?er is not empty, there is a unique transmission rate,namely r,the guaranteed minimum.

Table1summarizes the feedback protocol.Let YetTdenote the number of active sources at time t, and WetTthe bu?er content at time t.In the table the allocated rate,as well as the sign of the?drift?of the bu?er content are given,as functions of YetTand WetT.

An important aspect of our model is the be-havior of the homogeneous sources.Each source alternates between activity(on)and inactivity(o?). The inactivity periods are independent,exponen-tially distributed random variables with mean kà1. Each source transmits a?le during its activity period,whose size(in bits)is independent of ev-erything else and exponentially distributed with mean là1.The length of the induced activity pe-riod is not given a priori,since this depends on the rate(s)at which the?le is transmitted.An impor-tant parameter for the QoS is ,which the bu?er over?ow probability is required not to exceed.

We follow a conventional approach in inferring ?nite-bu?er performance from an in?nite-bu?er model.Since the long run fraction of time a source is on,given that the bu?er level is large,is k=ektl rT(note thatel rTà1is the maximum time to transmit a?le of size là1),the stability condi-tion of this in?nite-bu?er model is given by

k r

ktl r

In practice,there is a need to prevent N from being too large.One of the objectives of the analysis is to calculate the capacity of our system,which is the largest value of N such that the over?ow proba-bility of the queue does not exceed .In particular, the number N re Tof connections admissible as a function of and the guaranteed rate r,is an im-portant design parameter.We return to the cal-culation of this quantity in Section5.2.

2.2.Preliminary results

To analyze the model described in Section2.1, we?rst review some results from the model without feedback.Anick et al.[2]consider the model in which the sources transmit at a constant rate,say r,while in the on-state,i.e.,the allowable trans-mission rate does not depend on current occu-pancy of the system.Detailed results on this model are available[2,8,15].

Table1

Allowed user transmission rates(and sign of the bu?er drift),as functions of number of active sources and bu?er content Number of active sources WetT?0WetT>0

06YetT6N0pe0TreàT

N00

492M.Mandjes et al./Computer Networks41(2003)489–504

Bu?er content distribution.For this case without feedback we denote the state of the background process(i.e.the number of sources that are trans-mitting)and the bu?er content process at time t as XetTand VetTrespectively.In[2]the stationary distribution of the content process is given.It is computed as follows.Clearly XeáTconstitutes a continuous-time Markov chain on the state space f0;...;N g.Theei;jTth element(i?j)of its gen-erator Q is given by

Qei;jT:?

eNàiTk if j?it1; ir l if j?ià1; 0otherwise: 8<

The diagonal elements(i?j)are such that the

rowsums are zero.Elementei;jTrepresents the

probability?ux of the continuous-time Markov

chain from state i to state j.De?ne by R the di-

agonal matrix diag f r0;...;r N g with r i the net in-put rate if there are i sources in the on state,i.e.,

r i?iràC.

To?nd the stationary bu?er content distribu-

tion,we?rst de?ne F iexT:?PeX?i;V6xT.It is not hard to show that the vector FeáT:?eF0eáT;...;F NeáTTsatis?es F0exTR?FexTQ.The spectral expansion of the solution is given by

FexT?X N j?0a j v j exp?z j x ;e2T

where the a j are coe?cients determined later,and ez j;v jTis an eigenvalue–eigenvector pair,i.e.,ob-tained from z j v j R?v j Q.

The coe?cients a j are calculated as follows. De?ne D,the set of states with downward drifts,by all states i such that ir0,as the distri-bution should range between0and 1.The re-maining a j follow from F Ue0T?0.It turns out that there are just as many unknowns as equations. Clearly,PeV6xT?P i F iexT.

Idle and busy periods.Elwalid and Mitra[8]give explicit expressions for a number of quantities that are related to the busy and idle periods of the

queue.A busy period is de?ned as a period in

which the bu?er content is positive,whereas an

idle period is a period in which the bu?er is empty.

It is easily seen that at the beginning of a busy

period the number of sources in the on-state is

equal to N00t1;at the end of the busy period the number of sources in the on state is in D.The

lengths of consecutive busy and idle periods are

independent.

Denote by P the distribution at the end of the

busy period.Then it is not hard to prove that

h F De0TQ DD;1i F De0TQ DD;e3Tsee Eq.(5.9)of[8];há;ái denotes the inner product of two vectors.The mean idle period E I is given by E I?àP i2D F ie0T

D DD

Finally,the mean busy period E B can be calculated

using P i2D F ie0T?E I=eE ItE BT:

E B?E I

1àP i2D F ie0T

P i2D F ie0T:e4T2.3.Analysis

The model analyzed in this section has been de-

scribed in Section2.1.Recall that YetT2f0;...;N g

denotes the number of sources that are transmitting

at time t in the feedback model of Section2.1.

Notice that this does not constitute a Markov

chain,unlike XetTin Section2.2.This is because the

sojourn times and transition probabilities depend

on the amount of?uid stored in the bu?er.How-

ever,as long as the bu?er is empty,YetTbehaves as a

continuous-time Markov chain.

Denote the stationary bu?er content distribu-

tion in the feedback model by PeW

period in this model is distributed as the random

variable B0,and an idle period as I0.The sequence of busy periods is i.i.d.,and so is the sequence of idle periods,as can be seen easily.The distribution of YetTat the end of the busy period is denoted by (the vector)P0.The next lemma links B0and P0to the corresponding quantities in the model without feedback.

M.Mandjes et al./Computer Networks41(2003)489–504493

Lemma2.1.Busy periods B and B0have the same distribution.Also,the distributions P and P0are identical.

Proof.Both in the models with(Section2.1)and

without(Section2.2)feedback,during busy peri-

ods on-periods terminate at a rate ir l when there

are i sources in their on-state.In both models the

busy period starts when there are N00t1?d C=r e sources transmitting.Hence,the bu?er dynamics

in both models have the same probabilistic prop-

erties during a busy period.This immediately im-

plies both assertions.?

Corollary2.2.With the same argument as in the

proof of the previous lemma,we find

PeW6x j W>0T?PeV6x j V>0T;x>0: This immediately implies that

PeW6xT?PeV6x j V>0TPeW>0TtPeW?0T

?P i F iexTàP i F ie0T

1àP i F ie0TPeW>0TtPeW?0T: As PeW?0T?1àPeW>0T,the only quantity that is left to compute is the probability of an empty bu?er in our feedback model.This is given by

PeW?0T?

E I0

E I0tE B0?

E I0

E I0tE B;

applying Lemma2.1.As we know E B from Section 2.2,we only have to?nd E I0.This will be done in the next lemma,but?rst we introduce some re-quired notation.

Q0DD is a square matrix of dimension N00t1. For i?j:

Q0DDei;jT:?

eNàiTk if j?it1; ip l if j?ià1; 0otherwise; 8<

if i6N0,and

Q0DDei;jT:?

eNàiTk if j?it1;

C l if j?ià1; 0otherwise; 8<

if i is between N0t1and N00.The diagonal ele-ments are such that the rowsums are zero,except for Q0DDeN00;N00T,which equalsàC làeNàN00Tk.Notice that,as long as the bu?er is empty,YetTis a Markov chain which obeys the transition rates of Q0DD.

Lemma2.3.With P is defined in(3),the mean idle time in the feedback-based model is given by

E I0?hàPeQ0DDTà1;1i:e5TProof.This follows directly from standard results of mean passage times[13].It says that the mean time spent by YetTin j before the set D is left,given that the process starts in i,is given by theei;jTentry ofàeQ0DDTà1:

Then the reasoning is analogous to Eqs.(5.11) and(5.14)of[8],as follows.The vectoràPeQ0DDTà1 gives the mean time spent in all states in D during an idle period of the bu?er,applying Lemma2.1. The sum of its entries is the mean length of the idle period.?

We arrive at the following result for the bu?er content distribution in the feedback-based model.

A similar proportionality result was found,al-though not explicitly mentioned,in Adan et al.[1], where another feedback?uid queue is analyzed that has two types of behavior,depending on whether the bu?er is empty or not.

Theorem2.4.In the feedback-based model,the stationary buffer content distribution is given by

PeW6xT?P i F iexTàP i F ie0T

1àP i F ie0TE B E I0tE B

tE I0

E I0tE B;

where the vector FexTis given by(2),E B by(4),and E I0by(5).Equivalently,

PeW>xT?PeV>xT

E ItE B

E I0tE B:

An important interpretation of the above the-orem is the following:the gain with respect to the model without feedback(where the sources always send at rate r when active)is expressed by the term E ItE B

E I0tE B61:e6T

494M.Mandjes et al./Computer Networks41(2003)489–504

The fact that this ratio is less than1is due to the

fact that E I0P E I,which can be understood as follows.Clearly,I0can be interpreted as a?rst entrance time in the birth–death process with

generator Q0DD,namely as the?rst entrance time to state N00t1,starting from a state i6N00that is drawn from the distribution P0.Similarly I is the corresponding entrance time in the birth–death

process with generator Q,due to the fact that

P?P0.Since the death rates in Q0DD are larger than those in Q,while the birth rates are equal,it fol-lows that E I0P E I.

In many situations,particularly when the

number of sources is large,E B will be much

smaller than E I and E I0.In that case(6)is well approximated by E IáeE I0Tà1.That is,the ratio of mean idle times of the bu?er in the models without and with feedback e?ectively quanti?es the per-formance gain from feedback.

3.Feedback model with threshold

3.1.Model

In this section we consider a generalization of the feedback model presented in Section2.1.As before,YetTis the number of active users at time t (with state space f0;...;N g)and WetTis the bu?er content at time t.We now introduce a threshold level B?>0such that the sources are allowed to send at peak rate p as long as WetTB?the sources are allowed to transmit data only at the guaranteed rate r.When WetT?B?the processor sharing policy applies.In that case the bu?er content process will?stick?at level B?for as long as the number of active users lies in the set N0t1;...;N00.The algorithm is summarized in Table2.Notice that the model described in Sec-tion2.1is a limiting case of this model,as it is obtained by letting B?#0.We will describe the exact solution of the stationary bu?er content distribution.

Notice that the stability condition for this model is the same as(1).De?ne the matrix QerTto be Q(as de?ned in Section2.2);generator QepTis also de?ned as Q,but with rate r replaced by rate p.Finally,Qe?Tis similarly de?ned,but now Qei;ià1T?C l.The idea is that YetTbehaves like a Markov chain with generator QepT,Qe?T,QerT, whenever the bu?er content process WetTis re-spectively below,at,or above level B?.Further-more RerTis de?ned as in S ection2.2,i.e.as a diagonal matrix of dimension Nt1,its i th diag-onal element being given by iràC.RepTis similarly de?ned,except that its i th diagonal element is given by ipàC.The entries in these matrices are the net?uid rates into the bu?er for the guaran-teed rate(WetT>B?)and peak rate(WetT

3.2.Analysis

Our purpose is to?nd the joint distribution G iexTde?ned as

G iexT?lim t!1PeYetT?i;WetT6xT:

To do this we determine the Kolmogorov forward equations for

GepTiet;xT:?PeYetT?i;WetT6xT;06x

For x

GepTietth;xT?e1àheqepTi;ià1tqepTi;it1TTGepTiet;xàhrepTiT

thqepTià1;i GepTià1et;xT

thqepTit1;i GepTit1et;xTtOehT;

cf.[2].By taking h#0we?nd,in matrix form,

Table2

Allowed user transmission rates(and sign of the bu?er drift),as functions of number of active sources and bu?er content Number of active sources WetTB?

06YetT6N0peàTNA reàT

N00

M.Mandjes et al./Computer Networks41(2003)489–504495

o t

GepTet;xTto o x GepTet;xTRepT?GepTet;xTQepT; where GepTet;xTis an N-dimensional row vector.

However,for x>B?the Kolmogorov equations take a less simple form.With GepTiet;B?àT:?lim x"B?GepTiet;xT,we?nd that

GerTietth;xT?GerTiet;xàhrerTiTàheqerTi;ià1tqerTi;it1T

?eGerTiet;xàhrerTiTàGerTiet;B?TT

àheqe?Ti;ià1tqe?Ti;it1T

?eGerTiet;B?TàGepTiet;B?àTT

àheqepTi;ià1tqepTi;it1TGepTiet;B?àT

thqerTià1;ieGerTià1et;xTàGerTià1et;B?TT

thqerTit1;ieGerTit1et;xTàGerTit1et;B?TT

thqe?Tià1;ieGerTià1et;B?TàGepTià1et;B?àTT

thqe?Tit1;ieGerTit1et;B?TàGepTit1et;B?àTT

thqepTià1;i GepTià1et;B?àT

thqepTit1;i GepTit1et;B?àTtOehT:

After letting h!0,this leads to

o t

GerTet;xTto o x GerTet;xTRerT

?eGerTet;xTàGerTet;B?TTQerT

teGerTet;B?TàGepTet;B?àTTQe?T

tGepTet;B?àTQepT:

Assuming stationarity,we now set GerTiet;xT GerTiexTand GepTiet;xT GepTiexTfor i?0;...;N,and take all derivatives with respect to t equal to0. In matrix form,

d x

GepTexTRepT?GepTexTQepT;e7Tand

d x

GerTexTRerT?eGerTexTàGerTeB?TTQerT

teGerTeB?TàGepTeB?àTTQe?T

tGepTeB?àTQepT:e8TSolving(7)is immediate and leads to

GepTexT?X N j?0aepTj vepTj exp?zepTj x ;e9TwhereezepTj;vepTjTis an eigenvalue–eigenvector pair of zepTj vepTj RepT?vepTj QepT,and the aepTj are coe?cients. The solution of(8)can be found as follows.To deal with the inhomogeneous terms we?rst dif-ferentiate with respect to x,so that we?nd ho-mogeneous equations for

gerTexT d d x GerTexT:

We write down the solution for the resulting system of equations using the spectral method.

In the case that all eigenvalues are di?erent,we ?nd the solution to the di?erentiated system to be of the form

gerTexT?X N j?1~aerTj verTj exp?zerTj x ;

whereezerTj;verTjTis an eigenvalue–eigenvector pair of zerTj verTj RerT?verTj QerT,and the~aerTj are coe?cients. As QerTis a generator,it has an eigenvalue0,and hence one of the eigenvalues zerTj is zero,say zerTj

??0,cf.[19].With this in mind integration immediately yields that

GerTexT?X j?j?aerTj verTj exp?zerTj x taerTj?verTj?xtw;e10T

where aerTj?~aerTj=zerTj for j?j?,aerTj??~aerTj?,and the components w i of w are integration constants.

Now the vectors aepT,aerT,and w can be found by considering the following boundary conditions: (i)GepTie0T?0for all i P N0t1(i.e.,the bu?er

cannot be empty when it?lls),leading to NàN0equations.

(ii)Similarly,GepTieB?àT?GerTieB?Tfor all i2

f N0t1;...;N0g:This gives NtN0àN00t1

equations.

(iii)For all zerTj with a non-negative real part,the corresponding aerTj is zero,since the GerTiexTshould remain bounded for x!1.There are N00t1such eigenvalues[19].Notice that this also entails that the equilibrium distribu-tion of YetTis given by w.

(iv)By letting x!1in(8),setting the left-hand side equal to zero,we?nd the Nt1global balance equations for w?lim x!1GerTexT.

What we do here in fact,is to substitute the integrated solution(10)back into the inhomo-

496M.Mandjes et al./Computer Networks41(2003)489–504

geneous (undi?erentiated)equations (8)to ?nd the integration constants.From the glo-bal balance equations we can derive the N local balance equations for i 2f 1;...;N g ;eN ài t1Tk w i à1?ir l ew i àG er T

i eB ?TT

tC l eG er T

i eB ?TàG ep T

i eB ?àTT

tip l G ep T

i eB ?àT:

(v)Finally we normalize:P N

i ?0w i ?1.

Noticing that there are just as many boundary

conditions as coe?cients (namely 3N t3),we conclude that the system is solvable.We have proved:

Theorem 3.1.The above procedure gives the exact solution to the buffer content distribution.The above solution enables the computation of several key quantities.Denoting the throughput per user by s ,it is straightforward to obtain that

N s ?X N i ?0

ipG ep T

i eB ?àT

N 00i ?N 0t1C eG er Ti eB ?TàG ep T

i eB ?àTT

X N i ?0

ir ew i àG er T

i eB ?TT:

The mean ?le transfer delay E T is found from

s ?

1=l

:e11T4.Many sources

The intrinsic drawback of the technique of the previous sections is its computational complexity.When the size of the system (i.e.,the number of sources)grows,a large eigensystem needs to be solved.This explains the interest in simpler as-ymptotic approaches.In this section we will focus on the so-called ?many-sources scaling ?,which was introduced by Weiss [28].In this regime,we derive explicit results on the over?ow probability.

In the many-sources scaling,bu?er and band-width resources are scaled by the number of users

N .In other words,if we scale C Nc ,the expo-nential decay rate of P eW P Nx Tcan be deter-mined explicitly in terms of x and model parameters r ,p ,k ,l ,and c .Because W is now implicitly parametrized by N ,we write W N .The random variable V N is de?ned as the bu?er content in the corresponding model without feedback (as in Section 2.2).

4.1.Feedback model without threshold

Asymptotics.First we estimate the average be-havior of the number of active sources in the as-ymptotic limit (large N ).It is not hard to show that there are two regimes.

(A)In the ?rst regime k p =ek tl p T

this case,in the asymptotic limit,on average the sources are allowed to transmit at peak rate;the bu?er will be empty nearly always.The number of active sources on average will be Nm ,with m :?k =ek tl p T.

(B)In the second regime,c is between k r =ek tl r T

and k p =ek tl p T.In this case,the network will in general be in the processor sharing regime.The average number of active users simulta-neously in the system is Nm with

m :?1àl c ák à1

.The sources are allowed to transmit at a rate m 0between r and p ,where m 0:?c =m ?k c =ek àl c T.The following lemma gives the decay rate of the probability of a non-empty bu?er in each of the regimes.A similar result can be found in Ramanan and Weiss [21].

Lemma 4.1.The deca y ra te of the proba bility of a non-empty buffer is given by

lim N !11N

log P eW N >0T?I e0T:When k p =ek tl p T

I e0T?1 àc r log

1àc =r

c l =k tlog c ek tp l Tp k tc r à

and when k r =ek tl r T

(B)),I e0Tis given by

M.Mandjes et al./Computer Networks 41(2003)489–504497

I e0T?1

àc r

log

1àc =r c l =k

tc l k à1 àc r

:Proof.Directly from Theorem 11.15of [27],the

decay rate of the probability of a non-empty bu?er equals

Z c =r

log

l x x

k e1àx T d x :Here l x is the (downward)probability ?ux per

source,when the number of sources in the on state is Nx :

l x :?p l if xp

c l áx à1

otherwise :

Direct calculation yields the stated expression.?De?ne A et Tas the amount of ?uid generated in the interval ?0;t Tby one source with o?-periods that are i.i.d.Exp(k )random variables,and on-periods that are i.i.d.Exp(r l ),and constant generation rate r .Let E 0(E 1,respectively)denote expectation given that the source start in the o?(on)state at time 0.

Proposition 4.2.The decay rate for positive buffer content values is given by

lim

N !11

N log P eW N >Nx T?:I ex T?J ex TtI e0T;with

J ex T?inf t >0sup h

h ex tct Tàc

r log E 1e h A et T

à1 àc r log E 0e h A et T :e12T

Proof.Evidently,

P eW N >Nx T?P eW N >Nx j W N >0TP eW N >0T:As shown in Section 2.3,

P eW N >Nx j W N >0T?P eV N >Nx j V N >0T:Immediately from Theorem 1of [6],we have

lim

N !1

log P eV N >Nx j V N >0T?J ex T:Together with Lemma 4.1this proves the stated.?

The variational problem in (12)cannot be

solved analytically;numerical methods have to be applied.Fortunately,for large x asymptotics are available.

Simple a pproxima tions for la rge buffers.Let h H satisfy the equation lim t !1t à1log E e h A et T?c h .De?ne,for i ?0,1,a i :?lim t !1

log E i e h

A et T

àc h H t :

In [6]it is proven that,for x !1,

J ex T?h H

x àc r a 1à1 àc r

a 0tO ex T:

Following the Chernoff dominant eigenvalue method of [7],we propose an even simpler ap-proximation:

lim

N !11

log P eW N >Nx T%h H x tI e0T:e13THere h H ?r l =er àc Tàk =c ,and I e0Tis given in Lemma 4.1.In [7]it is shown that this approxi-mation is conservative for all x (in fact it is the best possible linear estimate that is conservative for all x ).Notice that the analysis of [7]requires the sources to be time-reversible,which condition is trivially met for exponentially distributed ?le sizes and user think times.In [7]it is concluded that the approximation is usually not overly conservative.General think-time and file-size distributions for large buffers.The nature of approximation (13)is,for large x ,

P eV N >Nx T%P eV N >0Te àh

:e14T

We may follow the same approach in case of general (rather than exponentially distributed)think-time and ?le-size distributions.The ques-tions then are:how to compute the counterparts of the probability of a non-empty bu?er P eV N >0Tand the exponential decay rate h H ?

The probability of a non-empty bu?er is com-puted as follows.As long as the bu?er is empty,the process behaves like an in?nite-server queue if the number of jobs is below N 0,and like a pro-cessor sharing queue if the number of jobs is be-tween N 0and N 00t1:Let D N be the number of jobs in the system.It is easily veri?ed that in the case of exponential think-times and ?le-sizes,the blocking probability (i.e.,the probability of D N ?N 00t1)equals

498M.Mandjes et al./Computer Networks 41(2003)489–504

1 Norm

N00t1r N00àN0t1p N0

N0!eNàN00à1T!

;

e15T

where the normalizing constant Norm is given by Norm?X N0j?0l k jep jTeNàjT!N!

tX N00t1j?N0t1l k jer jàN0p N0TN0!eNàjT!N!:

It is tedious but straightforward to verify that the decay rate of(15)is indeed Ie0T;as was de?ned in Lemma4.1.

Importantly,formula(15)also holds in the case of general think-time and?le-size distributions, with respective means kà1and là1:This is due to insensitivity results for networks of generalized processor sharing queues,as was shown by Cohen [5].

We now focus on the exponential decay rate h H. Let T be the distribution of the think-time and F the distribution of the?le-size.During busy peri-ods,the bu?er is fed by a superposition of N on–o?sources with o?-times distributed like T,and on-times distributed like F=r(with peak rate r). Let AetTbe the amount of tra?c generated by such a source,in steady state,in an interval of length t. Then(under mild technical conditions)the expo-nential decay rate in this model is the solution of

lim t!11

log E e hetT?c h;e16T

see Glynn and Whitt[12].Eq.(16)does not nec-essarily have a solution.In case of heavy-tailed on-times there is no solution––approximation(14) does not apply.

General think-time and file-size distributions for small buffers.Above we concentrated on loss be-havior under general think-time(with mean1=k) and?le-size distributions(with mean1=l),and large bu?ers.For small bu?ers a result from Mandjes and Kim[16]is applicable:for x#0,

lim N!11

log PeW N>NxT?

r???x ptIe0TtOexT;

with constant r given by

r???????????????????????????????????????????????????????????????????????????????????????????????????????????

ecr lteràcTkTlog cr l

eràcTk

à2ecr làeràcTkT

Strikingly,r depends on the distributions of the

think times and?le sizes only through their means,

making this an insensitivity result.

4.2.Feedback model with threshold

As before,we scale the resources bu?er and

bandwidth:C Nc,and B? Nb?.Again,this

regime allows explicit results,which we describe

below.

As in Section4.1,it turns out that there are two

possible regimes:(A)the bu?er is empty with an

overwhelming probability and the active sources

transmit at rate p almost all the time,and(B)the

bu?er occupancy is approximately nb?on average,

and the active sources send at a rate between r and p.

(A)pepTp

the?peak rate regime?:kektp lTà1.In this

case the?average state?of the system is a

(nearly)empty bu?er,and the active sources

transmit at peak rate.In order for the bu?er

to exceed level Nx,where x exceeds b?,four

events have to occur in order:(1)The bu?er

must become non-empty,i.e.,the number of

sources in the on-state must exceed Nc=p.(2)

Given that the bu?er content is at the point

of becoming positive,an amount of Nb?of

?uid has to accumulate.At the epoch the buf-

fer content reaches Nb?,let the number of

sources transmitting be N a.(3)If a is smaller

than c=r,then the number of sources in the

on-state has to grow to Nc=r,in order for

the bu?er to exceed level Nb?.If a is already

at least c=r then in this phase nothing has to

happen.Let N a0be the number of sources in

the on-state at the end of this phase.(4)An

amount of Nexàb?Tof?uid has to accumu-

late in the bu?er,where at the beginning of

this phase the number of sources transmitting

is N a0.This makes the decay rate be the sum

of four decay rates:

lim

N!1

log PeW N>NxT%X4i?1I i:e17TM.Mandjes et al./Computer Networks41(2003)489–504499

Notice that this construction(the decay rate of a steady-state probability being formulated as the solution of a transient problem,namely the decay rate of the path from equilibrium towards the rare event)is essentially of the Freidlin–Wentzell type.Details on this ap-proach are found in[27,Chapter6].In[17] explicit expressions for the four decay rates are given,in terms of the model parameters r, p,c,k,and l.

(B)perTr

of the system is a bu?er occupancy of Nb?,and all active sources sending at rate m0?

c k=ekàc lT.In equilibrium,the system is op-

erating in the processor sharing regime.

Clearly,the?rst two decay rates of case A do not apply anymore,as the queue is already operating at level nb?on average.Hence,only the other two decay rates have to be com-puted.Again[17]provides the explicit expres-sions.

5.Numerical results

In this section we provide numerical results.We ?rst consider an example where we maximize the system throughput,using the procedure of Section 3.The second example relies on the many sources asymptotics of Section4.

5.1.System throughput maximization

We consider a bu?er that is fed by10identical and independent on–o?sources.Let YetTdenote the number of active sources at time t;we choose the process YeáTas the regulating process.As be-fore,WetTwill denote the bu?er content at time t. The output trunk speed is C?11.The o?-times of the sources are exponentially distributed with k?3.File sizes are exponentially distributed with l?2.The peak transmission rate of the sources p?4,which is the actual transmission rate when the bu?er content is below B??2,and the rate drops to its minimum value r?2when the content is above B?.Notice that the bu?er content may stick at B?for as long as3,4,or5sources are active;then the total actual transmission rate is11,i.e.,the output trunk speed,equally shared among

the active sources.As a consequence the transition intensity of the process YeáTfrom state i to ià1, given that the bu?er process remains at2,is equal to iá2C=i?22.These considerations allow us to write down the diagonal matrices RepTand RerT,as well as the tri-diagonal matrices QepT,QerTand Qe?T.

After the numerical determination of the eigensystems of the matrices QepTeRepTTà1and QerTeRerTTà1,we apply the appropriate boundary conditions to?nd the33unknowns(note that N?10).After solving this(linear)set of equa-tions,the stationary distribution G of the joint process(YetT,WetT)can be found numerically.A

graphical representation of GeyT PeW6yT?P10i?0G ieyTis given in Fig.1.The throughput s of the system can be found as

s?X10j?0jrep jàGerTjeB?TTtjpGepTjeB?àT

tCeGerTjeB?TàGepTjeB?àTT?10:2652:e18TFinite-buffer model.The corresponding?nite-buf-fer system can be solved similarly[17].We did the calculations for B?5,leaving all other parameters the same.Clearly,now the size of the?jump?that GeyThas at y?5is exactly the(time average) probability of a full bu?er:

PeW?BT?1àX10j?0GerTjeBT?2:01?10à4

500M.Mandjes et al./Computer Networks41(2003)489–504

It is also not di?cult to?nd the average amount of ?uid sent into the bu?er per unit of time,or?uid input rate s H:

s H?X10j?0jrep jàGerTjeB?TTtjpGepTjeB?àT

tCeGerTjeB?TàGepTjeB?àTT?10:2656;e19Tand the average amount of?uid sent over the link per unit of time,or throughput,as

s?X10j?0Cep jàGepTje0TTtjpGepTje0T

?10:2651:e20TNotice that the numerical outcomes for these quantities are close to each other and to(18), which can be explained by the fact that we chose the(?nite)size of the bu?er quite large.Indeed by subtracting(20)from(19)we immediately?nd that the average amount of lost?uid per unit of time,or?uid loss rate,

Fluid loss rate?s Hàs?5:83?10à4;e21Tis small.Another way to?nd this result is to use Fluid loss rate?X10j?0ejràCTep jàGerTjeBTT:e22TThe fraction of?uid that is lost can be found as the ratio of the?uid loss rate(21)and the?uid input rate(19):

Fraction of fluid lost?

Fluid loss rate

Fluid input rate

?5:67?10à5:e23

M.Mandjes et al./Computer Networks41(2003)489–504501

Maximization of system throughput.As a?nal

application we show how the threshold level B?and the number of sources N may be jointly cho-

sen such that the system throughput is maximized,

with the fraction of lost?uid not to exceed

?10à6.The other parameters are as before.In Figs.2and3we plot the throughput and the loss

fraction as functions of the threshold level for

N?7;...;12.From Fig.3it can be seen that only

for N69the loss fraction criterion can be satis?ed

for some value of B?.From Fig.2we compare the corresponding throughputs for these pairs of

eN;B?T.It turns out that the system throughput is maximized by choosing N?9and B??2:05, giving a throughput of9:5725.This also allows us

to compute the mean?le transfer time,see(11):

solve E T from

9:5725 9?

0:5000

E Tt0:3333

;

giving E T?0:1368.During the active period a source?s throughput is0:5000=0:1368?3:6526, which is between r?2and p?4.5.2.Impact of the choice of the guaranteed rate r

The purpose of this subsection is to provide an illustration of the e?ect of the feedback mecha-nisms proposed in a more practical situation.For reasons of convenience,we assume that the num-ber of sources is su?ciently large to use the ap-proximations of Section4.We consider a45Mbit/ s link,with a bu?er of10Mbit.The sources have peak rates of3Mbit/s.The users alternately send ?les(exponentially distributed with mean100kbit) and?think?(for an exponentially distributed time with mean10s).We again require that the loss probability is below ?10à6.We focus on the impact of r,the guaranteed minimum throughput advertised to customers,because this is an im-portant parameter.

Clearly,for a?xed value of B?(possibly0),the loss probability increases with r.On the other hand,the number of admissible sources N r de-creases in r,for?xed loss probability.In Fig.4,N r is given as a function of r,for di?erent values of B?(B??0;2;...;8Mbit).We observe that for

low Fig.4.Number of admissible sources as a function of the guaranteed rate r.

502M.Mandjes et al./Computer Networks41(2003)489–504

values of r,N r is quite sensitive to the threshold value B?;the opposite is true for r in the neigh-borhood of p.

References

[1]I.Adan, E.van Doorn,J.Resing,W.cheinhardt,

Analysis of a single-server queue interacting with a?uid reservoir,Queueing ystems29(1998)313–336.

[2]D.Anick,D.Mitra,M.ondhi,tochastic theory of a

data-handling system with multiple sources,The Bell ystem Technical Journal61(1982)1871–1894.

[3]D.Botvich,N.Du?eld,Large deviations,the shape of the

loss curve,and economies of scale in large multiplexers, Queueing ystems20(1995)293–320.

[4]G.Choudhury,D.Lucantoni,W.Whitt,queezing the

most out of ATM,IEEE Transactions on Communications 44(1996)203–217.

[5]J.Cohen,The multiple phase service network with gener-

alized processor sharing,Acta Informatica12(1979)245–284.

[6]N.Du?eld,Conditioned asymptotics for tail probabilities

in large multiplexers,Performance Evaluation31(1998) 281–300.

[7]A.Elwalid,D.Heyman,https://www.wendangku.net/doc/f413292099.html,kshman,D.Mitra,A.Weiss,

Fundamental bounds and approximations for ATM mul-tiplexers with applications to videoconferencing,IEEE Journal on elected Areas in Communications13(1995) 1004–1016.

[8]A.Elwalid,D.Mitra,Analysis and design of rate-based

congestion control of high-speed networks.I.tochastic ?uid models,access regulation,Queueing ystems9(1991) 29–64.

[9]A.Elwalid,D.Mitra,tatistical multiplexing with loss

priorities in rate-based congestion control of high-speed networks,IEEE Transactions on Communications42 (1994)2989–3002.

[10]R.Gibbens,F.P.Kelly,Resource pricing and the evolution

of congestion control,Automatica,in press.

[11]R.Gibbens,F.P.Kelly,Distributed connection acceptance

control for a connectionless network,in:P.Key,D.mith (Eds.),Proceedings ITC16:Teletra?c Engineering in a Competitive World,Elsevier,Amsterdam,1999,pp.941–952.

[12]P.Glynn,W.Whitt,Logarithmic asymptotics for steady-

state tail probabilities in a single-server queue,Journal of Applied Probability31A(1994)131–156.

[13]R.Howard,Dynamic Probabilistic ystems,vol.1,Wiley,

New York,1971.

[14]F.P.Kelly,Models for a self-managed Internet.Royal

ociety,2000,submitted for publication.

[15]L.Kosten,tochastic theory of data-handling systems with

groups of multiple sources,in:H.Rudin,W.Bux(Eds.), Performance of Computer-Communication ystems,Else-vier,Amsterdam,1984,pp.321–331.[16]M.Mandjes,J.H.Kim,Large deviations for small bu?ers:

an insensitivity result,Queueing ystems37(2001)349–362.

[17]M.Mandjes,D.Mitra,W.cheinhardt,imple models of

network access using feedback?uid queues,Queueing ystems,submitted for publication.

[18]L.Massouli e,J.Roberts,Arguments in favour of admis-

sion control for TCP?ows,in:P.Key,D.mith(Eds.), Proceedings ITC16:Teletra?c engineering in a compet-itive world,Elsevier,Amsterdam,1999,pp.33–44. [19]D.Mitra,tochastic theory of a?uid model of producers

and consumers coupled by a bu?er,Advances in Applied Probability20(1988)646–676.

[20]R.Pazhyannur,R.Agrawal,Feedback-based?ow control

of B-IS DN/ATM networks,IEEE Journal in elected Areas in Communications13(1995)1252–1266.

[21]K.Ramanan,A.Weiss,haring bandwidth in ATM,in:

Proceedings Allerton Conference,1997,pp.732–740.

[22]J.Roberts,Engineering for Quality of ervice,Preprint.

[23]J.Roberts,.Oueslati-Boulahia,Quality of ervice by?ow

aware networking,Royal ociety,2000,submitted for publication.

[24]W.cheinhardt,Markov-modulated and feedback?uid

queues.Available from:.Ph.D.Thesis,University of Twente,the Netherlands,1998.

[25]W.cheinhardt,Analysis of feedback?uid queues,in:

Proceedings14th ITC-specialists eminar on Access Net-works and ystems,Girona,pain,April25–27,2001, pp.215–220.

[26]M.chwartz,Broadband Integrated Networks,Prentice

Hall,Upper addle River,NJ,1996.

[27]A.hwartz,A.Weiss,Large Deviations for Performance

Analysis,Queues,Communication,and Computing,Chap-man and Hall,New York,1995.

[28]A.Weiss,A new technique of analyzing large tra?c

systems,Advances in Applied Probability18(1986)506–

532.

Michel Mandjes received M.Sc.degrees

in Mathematics and Econometrics

from the Free University,Amsterdam,

The Netherlands.In1996he received

his Ph.D.degree,again from the Free

University.Autumn1996he joined

KPN Research,where he mainly

worked on ATM and IP performance

analysis.He was involved in a number

of European research consortia,such

as COST257and CA$hMAN.In1999

he moved to Bell Laboratories/Lucent

Technologies,Murray Hill,NJ,USA,

where he joined the Mathematics of Networks and Systems group.He currently has a joint position as department head at CWI,Amsterdam,and as full professor at the University of Twente,Enschede,The Netherlands.His research interests include large deviations analysis of multi-plexing systems,tra?c management and control in IP net-works,and pricing in packet networks.

M.Mandjes et al./Computer Networks41(2003)489–504503

Debasis Mitra is Vice President,

Mathematical Sciences Research at

Bell Labs.He received the Ph.D.

degree in Electrical Engineering from

London University and joined Bell

Laboratories as a Member of Tech-

nical Sta?in1968.During the fall

semester of1984he was Visiting

Mckay Professor at the University of

California,Berkeley.His recent in-

terests have been in broadband net-

working,including tra?c control and

engineering for IP and ATM net-

works,the development of new sca-

leable analytic techniques for design and their incorporation

in software packages.His current interests are in optical

networking,IP/optical convergence,network economics and

business planning of broadband networks,and bandwidth

commerce.

Dr.Mitra is a Bell Labs Fellow and a Fellow of the IEEE.

He is the recipient of awards given by the Institution of

Electrical Engineers(UK),the Bell System Technical Journal,

the1995ACM Sigmetrics/Performance Conference,the1993

Steven O.Rice Prize Paper Award and the1982Guillemin-

Cauer Prize Paper Award of the IEEE.

He is a co-recipient of the1998IEEE Eric E.Sumner

Award with the following citation:‘‘For the conception and

development of voice echo cancelers’’.He has been a member

of the editorial boards of the IEEE/ACM Transactions on

Networking,the IEEE Transactions of Communications and

the IEEE Transactions on Circuits and Systems.He is a

member of the editorial boards of Queueing Systems

(QUESTA)and the Journal of High Speed

Networks.

Werner Scheinhardt received both an

M.Sc.degree and a Ph.D.degree in

Applied Mathematics from the Uni-

versity of Twente,The Netherlands,

in1994and1998respectively.After

holding a postdoctoral position at

Eindhoven University of Technology,

The Netherlands,he returned to the

University of Twente in2000to be an

assistant professor.He also holds a

part-time position at the Centre for

Mathematics and Computer Science

(CWI)in Amsterdam.His research

interests are in the?eld of stochastic

processes,with applications to the performance analysis of

computer and communications networks.

504M.Mandjes et al./Computer Networks41(2003)489–504