Subject: RE: [Diffserv] Token bucket burst size

From: Bill Courtney <[email-masked]>
Date: Tue, 13 Jun 2000 12:45:18 -0700

brijesh,

I agree with Shahram. Put another way, his equation T*S = T*R + B searches for the unknown time T that a source can burst at the line rate S. The right-hand side is a full bucket B plus the accumulation of tokens (T*R) during the unknown maximum burst duration. 

So, his formulation accounts for tokens being added to the bucket during the burst. As long as S > R, the number of tokens in the bucket will never rise higher than B.

Perhaps this is not the way things are implemented (I wouldn't know, since we don't manufacture routers), but his mathematics is consistent with a (continuous) token bucket that is being drained and replenished simultaneously.

Bill Courtney
TRW, Network System Engineering

> -----Original Message-----
> From: Shahram Davari [mailto:[email-masked]]
> Sent: Tuesday, June 13, 2000 12:02 PM
> To: [email-masked]'; Shahram Davari; [email-masked]
> Cc: [email-masked]
> Subject: RE: [Diffserv] Token bucket burst size
> 
> 
> Hi Bkumar,
> 
> Why is the T*R + B limited by B? I know that we can't 
> generate token while
> the bucket is full, but if you consider the worst case:
> 
> A packet of size B arrives when the bucket is full, this 
> causes the Token
> counts to get to zero. Now assume at the end of the T period 
> another packet
> of size T*R arrives, that packet will also get through 
> (because there are
> now T*R tokens accumulated in the TB). So the worst case maximum burst
> passed during the T period is:
> 
> Worst MBS = B + T * S
> 
> Cheers,
> -Shahram
> 
> >-----Original Message-----
> >From: Brijesh Kumar [mailto:[email-masked]]
> >Sent: Tuesday, June 13, 2000 2:39 PM
> >To: 'Shahram Davari'; [email-masked]
> >Cc: [email-masked]
> >Subject: RE: [Diffserv] Token bucket burst size
> >
> >
> >
> >Shahram,
> >
> >Interesting computation, but I think it has a flaw.
> >
> >MBS = T * S = T * R + B
> >
> >This line doesn't make sense to me as the T*R+B is limited by bucket
> >size B. You can't generate tokens when B is full. The real
> >relationship should be:
> >
> >MBS = T *S = min (T*R + CurrentToken,B)
> >if current tokens are B (I.e., the initial point), MBS = T*S = B.
> >Period.
> >
> >Cheers,
> >
> >--brijesh
> >Ennovate Networks Inc.
> >
> >
> >
> >
> >
> >
> >> -----Original Message-----
> >> From: [email-masked]
> >> [mailto:[email-masked]]On Behalf
> >> Of Shahram Davari
> >> Recently I have been working on TB, and I have found the
> >> following problem:
> >>
> >> If we assume a TB (B, R), in which the TB counts can not go
> >> negative, then
> >> the Maximum burst size which can pass through this TB can be
> >> computed as
> >> following:
> >>
> >> B: TB size
> >> R: TB rate
> >> S: input line rate
> >> T: Time required to exhaust the TB ( includes the Tokens
> >> already inside TB
> >> and the tokens that are accumulated in this period)
> >> MBS: Maximum Burst Size
> >>
> >>
> >> MBS = T * S = T * R + B
> >> T = B / (S-R)
> >> MBS = B * S / (S-R)  ---> B = MBS * (S-R) / S
> >>
> >> As you can see contrary to the general belief the MBS is not
> >> equal to the TB
> >> size "B". Unless S >>R.
> >> Example1:  if S = 2R --> MBS = 2B
> >> Example2: S = R --> MBS = infinite
> >>
> >> However, in RFC-2697 and RFC-2698 the TB parameters are set
> >> as following:
> >>
> >> Tc (size) = CBS
> >> Te (size) = EBS
> >> Tp (size) = PBS
> >>
> >> While it should be set as following:
> >>
> >> Tc (size) = CBS * (S-R) /S
> >> Te (size) = EBS * (S-R) /S
> >> Tp (size) = PBS * (S-R) /S
> >>
> >>
> >> Do you think this should be corrected?
> >>
> >
> >
> >_______________________________________________
> >diffserv mailing list
> >[email-masked]
> >http://www1.ietf.org/mailman/listinfo/diffserv
> >Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
> >
> 
> _______________________________________________
> diffserv mailing list
> [email-masked]
> http://www1.ietf.org/mailman/listinfo/diffserv
> Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
> 
> 

_______________________________________________
diffserv mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/diffserv
Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/

---

From: "Li, Renwei" <[email-masked]>
Date: Tue, 13 Jun 2000 12:48:59 -0700

I think you are alsolutely right with respect to TB MBS. 
I also noticed that this was emphasized in a book (but 
I don't remember which) and the author of the book (maybe 
a paper) pointed out the confusion and mistakes many 
other authors were making.

But with respect to RFC-2697/2698, it looks OK
with me. The burst sizes of their TB can be roughly 
understood as the same as yours, but in implementation for
color marking purpose, the physical size of the bucket could be 
modified so that your formula is still valid. And in this
sense the RFC, as it is, is still good. 

One thing is that your input line rate S should really be
output line rate. Otherwise there would be an overflow.

Renwei Li
Abatis Systems Corporation
4190-200 Still Creek Drive
Burnaby, B.C.
Canada V5C 6C6
Phone: (604) 918-4706
Fax:   (604) 294-8830
Email:  [email-masked]
Web:   www.abatis-sys.com

-----Original Message-----
From: Shahram Davari [mailto:[email-masked]]
Sent: Tuesday, June 13, 2000 10:34 AM
To: [email-masked]'
Cc: [email-masked]'
Subject: [Diffserv] Token bucket burst size

Hi,

Recently I have been working on TB, and I have found the following problem:

If we assume a TB (B, R), in which the TB counts can not go negative, then
the Maximum burst size which can pass through this TB can be computed as
following:

B: TB size
R: TB rate
S: input line rate
T: Time required to exhaust the TB ( includes the Tokens already inside TB
and the tokens that are accumulated in this period)
MBS: Maximum Burst Size

MBS = T * S = T * R + B 
T = B / (S-R)

As you can see contrary to the general belief the MBS is not equal to the TB
size "B". Unless S >>R.
Example1:  if S = 2R --> MBS = 2B
Example2: S = R --> MBS = infinite

However, in RFC-2697 and RFC-2698 the TB parameters are set as following:

Tc (size) = CBS
Te (size) = EBS
Tp (size) = PBS

Shahram Davari
Systems Engineer
Product Research
PMC-Sierra, Inc. (Ottawa) 
555 Legget drive,
Suit 834, Tower B,
Ottawa, ON K2K 2X3, Canada
Phone: +1 (613) 271-4018
Fax  : +1 (613) 271-7007

---

From: Shahram Davari <[email-masked]>
Date: Tue, 13 Jun 2000 13:22:32 -0700

Thanks Mark,

Very good example.

-Shahram

>From: Mark Stewart [mailto:[email-masked]]
>Sent: Tuesday, June 13, 2000 4:19 PM
>To: [email-masked]
>Cc: 'Shahram Davari'; [email-masked]; [email-masked]
>Subject: Re: [Diffserv] Token bucket burst size
>
>
>The way to approximate the T*R+B bytes in a time interval T, is to send
>small packets not large ones. If p is the size of the smallest 
>packet you
>may send then
>sending 1 packet of size p, every p/S units of time; will result in
>p*rounddown((T*R+B)/p) bytes being passed.
>
>Mark Stewart
>
>Brijesh Kumar wrote:
>
>> Hi Shahram,
>>
>> > Worst MBS =B + T * S
>> You are right, but only partially. It is because you are shifting the
>> time reference point. Even with your example, you need to wait for
>> time T to send a packet of size T*R (remember, you can only start
>> generating tokens AFTER the last event has completed and there is a
>> space in the bucket to accumulate new tokens.). If that packet had
>> come at (T-1) instant that would have not been allowed to go. No
>> matter how you model, over a time period T, you are not allowed to
>> send more than T*R where T*R <=B.
>>
>> Cheers,
>>
>> --brijesh
>> Ennovate Networks Inc.
>>