Subject: Re: [Diffserv] Token bucket suggestion in Diffserv Model draft

From: Andrew Smith <[email-masked]>
Date: Mon, 15 Jan 2001 18:03:53 -0800

Shahram,

Apologies for delay in responding to your suggestions from 12/11/2000.

I think we'd do best to follow Brian's advice after IETF, as summarised by Fred: 
"Brian suggested that there is one sentence in the draft which reads 
pejoratively, and would do well to be replaced with a sentence that lists 
Sharam's issues with the loose model, as a balance to the succeeding sentence, 
which points out that TCP sends pairs of packets frequently and a model that 
makes believe that it is non-bursty is out of touch with reality. Shahram was 
detailed to come up with the sentence."

The changes you propose go well beyond this advice though. Please see my 
detailed comments below. I will provide my proposed wording changes tomorrow, 
hopefully.

Andrew
(model draft editor)

Shahram Davari wrote:

> Hi,
> 
> Here are the wording suggestions, that was asked in the Diffserv WG meeting today (Monday):
> 
> 5.2.3.  Two-Parameter Token Bucket Meter
> 
> A more sophisticated meter might measure conformance to a token bucket
> (TB) profile. A TB profile generally has two parameters, an average
> token rate and a burst size. TB meters compare the arrival rate of
> packets to the average rate specified by the TB profile.  Logically,
> tokens accumulate in a bucket at the average rate, up to a maximum
> credit which is the burst size. Depending on what type of TB is used,
> packets of length L bytes are considered conforming if 
> 
> 1) Either any tokens are available in the bucket at the time of packet
> arrival: up to L bytes may then be borrowed from future token allocations.
> This is called a "negative-count" TB.
> 
>  
> 2) Or, if the number of tokens in the bucket is more than or equal to the
> size of the packet at the time of the packet arrival: no bytes are borrowed
> from future token allocations. This is called a "positive-count" TB. 

[Andrew] I find this wording confusing: it doesn't make it clear that these are 
two separate implementation options - it reads as if it is a run-time choice 
which it is not. I'd prefer a wording that makes that choice clearer - I'll 
propose something shortly.

Also, the token bucket is the same in each case, it is just the conformance test 
that differs - thus, it seems confusing to me to call these "positive-count TBs" 
and "negative-count TBs". I still think that the "strict conformance" vs. "loose 
conformance" terminology is clearer: it makes it clear that it is the 
conformance test that differs (the fact that loose conformance to a TB requires 
the TB to be able to go "negative" is a consequence of the conformance algorithm 
but that is not the primary defining characteristic of it. The WG needs to make 
a choice anyhow - I haven't seen clear consensus to change the current terminology.

> Packets are allowed to exceed the average rate in bursts up to the burst
> size. Packets which arrive to find a bucket with no tokens in it are
> deemed non-conforming. A two-parameter TB meter has exactly two possible
> conformance levels (conforming, non-conforming). TB implementation details
> are discussed in Appendix A. 

[Andrew] Not clear from your proposed wording whether this paragraph now applies 
to case 1 or case 2.

> A two-parameter TB meter might appear as follows:
> 
>       Meter3:
>       Type:                NegativeTokenBucket
>       Profile:             Profile3
>       ConformingOutput:    Queue1
>       NonConformingOutput: AbsoluteDropper1
> 
>       Profile3:
>       Type:                SimpleTokenBucket
>       AverageRate:         200 kbps
>       BurstSize:           100 kbytes
> 
> 12.  Appendix A. Simple Token Bucket Discussion and Definition

[Andrew] Did you intend to leave A.1, A.2 and the first 2 paragraphs of A.3 
unchanged? If not then I think we've lost some valuable discussion material. If 
so, then there is material there that would need to be made consistent with your 
proposed new terminology.

> Internet Protocol (IP) packets are of variable-length but theoretical
> token buckets operate using fixed-length time intervals or pieces of
> data.  This leaves an implementor of a token bucket scheme with a
> dilemma, of what kind of TB to use. Essentially three type of TB can be

> used, which differ in how a packet is processed when the amount of bandwidth tokens, 

> TB, left in the token bucket is positive but less than the size of the packet being operated on.

[Andrew] As before, I think this is better expressed as descriptions of the 3 
conformance tests that an implementor can choose from. That's how it was already 
in -05 draft.

>  (1)   Assuming a TB of size B and rate R, the whole size of the packet can

> 	 be subtracted from the bucket, leaving it negative, remembering that

> 	 the token bucket size must be added to TB rather than simply setting

> 	 it "full". This potentially puts more than the token bucket size into

> 	 this token bucket interval and less into the next. It does,

> 	 however, make the average amount accepted per token bucket interval

> 	 equal to the token burst. This approach accepts traffic if any bit in

> 	 the packet would be accepted and borrows up to one MTU of capacity
>        from one or more subsequent intervals when necessary. Such a
>        token bucket implementation is said to be a "negative-count" token

> 	 bucket.
> 
>  (2)   Alternatively if we use a TB of size B+MTU and rate R, the amount

> 	 can be left unchanged (and maybe an attempt could be made to accept

> 	 the packet under another threshold in another bucket). This

> 	 potentially puts less than the token bucket size into this token

> 	 bucket interval and more into the next. Like the first option, it

> 	 makes the average amount accepted per token bucket interval equal to

> 	 the token burst.  This approach accepts traffic if every bit in the

> 	 packet would be accepted and borrows up to one MTU of capacity from

> 	 one or more previous intervals when necessary. Such a token bucket

> 	 implementation is said to be a "positive-count" token bucket. 

[Andrew] I think that calling the size "B+MTU" confuses this example - "B" is 
used in A.4 to indicate the current packet size (did you mean "BS" as defined in 
A.4?). I do think that the current description in -05 draft is confusing - e.g. 
it uses a variable called "TB" as well as using TB as a shorthand for token 
bucket. I can fix that easily in the next draft.

> (3)    The TB variable can be set to zero to account for the first part
>        of the packet and the remainder of the packet size can be taken
>        out of the next-colored bucket. This, of course, has another bug:
>        the same packet cannot have both conforming and nonconforming
>        components in the Diffserv architecture and so is not really
>        appropriate here.
> 
> Unfortunately, the thing that cannot be done is exactly to fit the token
> burst specification with random sized packets: therefore token buckets
> in a variable length packet environment always have a some variance from
> theoretical reality. This has also been observed in the ATM Guaranteed
> Frame Rate (GFR) service category specification and Frame Relay.
> 
> Positive-count TB is commonly used in ATM and Frame Relay.

> However, the positive-count TB approach has some characteristics

> which are important to keep in mind:
> 
>  (1)   The maximum TB burst must be greater than the MTU, otherwise it is

> 	 possible that traffic never matches the specification. As an example

> 	 suppose that the maximum burst size is exactly the size of the

> 	 packets being sent.

[Andrew] But this example case has just been forbidden by the "greater than" 
rule you just made - did you mean "greater than or equal to"?

>In such a case, when one packet has been

> 	 accepted, the token depth becomes zero, and starts to accumulate.  If

> 	 the next packet is received any time earlier than a token interva

> 	 later, it will not be accepted. If  the next packet arrives exactly

> 	 on time, it will be accepted and the token depth again set to zero.

> 	 If it arrives later, however, the token depth will stop accumulating,

> 	 as it is capped by the maximum burst size, and tokens that would have

> 	 accumulated between the end of that token interval and the actual

> 	 arrival of the packet are lost.

>        As a result, natural jitter in the

> 	 network conspires against the algorithm to reduce the actual

> 	 acceptance rate. However, this problem can be overcome by setting the

> 	 maximum token bucket size to be greater than the MTU to absorb the

> 	 jitter

[Andrew] Isn't that a feature, not a bug? The whole point, presumably, of setting that

maximum burst size was so that you don't get bursts bigger than that on the wire. So 

it is misleading to talk about "tokens that would have accumulated" as being "lost": 

that's exactly what was intended. How about:
"If it arrives later, however, accumulation of tokens would have stopped because 

that is capped by the maximum burst size: during the interval between the bucket 

becoming full and the actual arrival of the packet no new tokens are added.
As a result, jitter that accumulates across multiple hops in the network conspires 

against the algorithm to

reduce the actual acceptance rate. Thus it usually makes sense to 

set the maximum token bucket size somewhat greater than the MTU in order to absorb 

some of the jitter and allow a practical acceptance rate more in line with 

the desired theoretical rate."
 
>  (2)   Operationally, a  positive-count token bucket is reasonable for
>        traffic which has been shaped by a leaky bucket shaper or a
>        serial line. However, traffic in the Internet is rarely shaped in
>        that way.  TCP applies no shaping to its traffic, but rather
>        depends on longer-range Ack Clocking behavior to help it
>        approximate a certain rate and explicitly sends traffic bursts
>        during slow start, retransmission and fast recovery. Video-on-IP
>        implementations such as [VIC] may have a leaky bucket shaper
>        available to them, but often do not, and simply enqueue the
>        output of their codec for transmission on the appropriate
>        interface. As a result a positive-count TB may reject traffic in the

> 	 short term (single token interval),which it would have accepted if it

> 	 had a longer time in view and which it needs to accept for the

> 	 application to work properly. To work around this, the token interval

> 	 (B/R) must approximate or exceed the RTT of the session or sessions

> 	 in question and the burst size must accommodate the largest burst

> 	 that the originator might send. In other words in the absence of 

>	 shaping, the max. burst size of the positive-count TB must be set to

> 	 a large value to accept the incoming burst

[Andrew] I think some of this discussion worked better where it was in -05 draft 
(paragraph 2 of A.3). I'll move the VIC example up there. Again, I think you 
meant BS/R not B/R using the terminology of A.4. I don't think the last sentence 
helps much: what does "large" mean?

> A negative count TB has also some characteristics which are important to keep in mind.
> 
>  (1)	The negative-count TB does not accept packets, while the TB count is

> 	negative. This means that when a large packet has borrowed token form

> 	future, if we receive even a small packet such as 40-byte TCP ACK/SYN

> 	packets, they will not be accepted by the TB.

[Andrew] Seems like this is the main additional point that needs to be included.

>  (2)	A negative-count TB has granularity problem. This means that even if

> 	we set the TB depth to 1-bit, the maximum burst size that can pass

> 	through the TB can't be smaller than MTU (this behavior is essentially

> 	equivalent to positive-count TB, in which the TB depth must be set to

> 	a larger value than MTU). Another consequence is that if one restricts

> 	the maximum TB burst to	MTU, then the TB depth must be set to 1-bit.

> 	By doing so And if you do that you can't basically accept any back to

> 	back packets at all, no matter how small they are. 

[Andrew] Let me try to paraphrase this to see if I understand what you're trying 
to say:
"A negative-count TB has granularity problem: if the operator wishes to restrict
the maximum burst size to MTU, the TB depth, BS, must be set to 1 bit. This 
means that the maximum burst size that can be configured to pass through the TB 
cannot be smaller than MTU (this behavior is essentially equivalent to 
positive-count TB, in which the TB depth has to be set to a larger value than 
MTU). A consequence of this is that, with such a small BS, the TB basically
cannot accept any back to back packets at all, no matter how small they are."

So I'm not understanding this very well: I can send a bunch of packets 
back-to-back just fine, so long as we don't get to an empty bucket. If any of 
them reaches an empty bucket then of course they will be failed. If you want to 
allow multiple back-to-back packets then you should configure a larger BS. It 
seems to me like the only "size discrimination" going on is when BS is 
configured close to MTU: isn't this a case of "don't do that"? Is that the 
advice that you're trying to capture here?

>   (3)  Similar to positive-count TB, a negative-count token bucket is

> 	 reasonable for traffic which has been shaped by a leaky bucket shaper

> 	 or a serial line. As a result a negative-count TB may reject traffic

> 	 in the short term (single token interval), which it would have

> 	 accepted if it had a longer time in view and which it needs to accept

> 	 for the application to work properly. To work around this, the token

> 	 interval (B/R) must approximate or exceed the RTT of the session or

> 	 sessions in question and the burst size must accommodate the largest

> 	 burst that the originator might send. In other words in the absence

> 	 of shaping, the max. burst size of the negative-count TB must be set

> 	 to a large value to accept the incoming bursts.

[Andrew] This re-working of the original material seems more confusing to me: 
you've taken some of this out of context (it was talking about TCP and VIC in 
-05). In the original, this paragraph was a criticism of a "strict" TB: if it is 
also a valid criticism of a "loose" one then there seems little sense in pasting 
it in again under that heading - it should just be considered as a 
characteristic of TBs in general.

> In summary the positive-count TB favors more the small packets, while the 

> negative-count TB favors more the large packets. Each one might be 

> useful in various scenarios.

[Andrew] Again, I'm not sure that this blanket conclusion is justified by the 
preceding argument: I think the appropriate conclusion could be "yes, there is 
size-discrimination for some values of BS" but I'm not sure the preceding 
paragraphs need such a simplistic conclusion paragraph.

Andrew

_______________________________________________
diffserv mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/diffserv
Archive: http://www2.ietf.org/mail-archive/working-groups/diffserv/current/maillist.html

---

From: Shahram Davari <[email-masked]>
Date: Tue, 16 Jan 2001 08:19:14 -0800

Hi Andrew,

> propose something shortly.

[Shahram]You may certainly add a few words to make it clear that these are two different implementations, not a running time choice.

> a choice anyhow - I haven't seen clear consensus to change 

[Shahram]As I said before calling the negative-TB a loose TB and the positive-TB a strict is not correct either. The reason is that as an example a negative TB of depth "BS" is definitely stricter than a positive TB of depth "BS+MTU", although both of them have the same burst tolerance of "BS+MTU". Because after receiving a burst of BS+MTU, the negative TB can't accept any more packets for a period of t=MTU/R, while the positive TB can accept short packets during this interval. So you are more than welcome to choose another term, by I strongly object the loose and strict terms.

> [Andrew] Not clear from your proposed wording whether this 

[shahram]It applies to both.

> proposed new terminology.

[shahram]I intended to leave A.1 and A.2 and A.4 as they are and only replace A.3 with the proposed text.

> conformance tests that an implementor can choose from. That's 

[shahram]OK.

> bucket. I can fix that easily in the next draft.

[shahram]Yes, I meant "BS+MTU". I also agree with your proposal to use TB more consistently. 

> rule you just made - did you mean "greater than or equal to"?

[shahram]Yes, its is "greater than or equal to".

> the desired theoretical rate."

[shahram] This part was not mine, it was a straight copy form draft-05. But I like your proposal.

> helps much: what does "large" mean?

[Shahram] The example was from draft-05. You may certainly move it. And yes, I meant BS/R. Also by "large" I meant larger than MTU. How much larger depends on the required burst tolerance. 

> advice that you're trying to capture here?

[shahram] There are two phenomena that I am trying to describe:
a) In the negative TB it is not possible to set the maximum burst size to any value smaller than MTU. For example you can't set the maximum burst size to MTU/2, because by definition the negative-TB counts can go up to "-MTU". This may not be important because everybody knows that the maximum burst tolerance must be set to be greater than MTU, in order to accept at least an MTU size packet. This behavior is essentially the same as bullet (1) of positive TB characteristics.

b) Assume that we have two equivalent TBs, a positive-TB of depth BS=MTU, and rate R, and a negative-TB of depth BS=1bit and rate R. Also assume that the line rate is C=10*R. Now assume that at time t=0 both TBs are full of tokens, and that two back-to-back packets of size B=MTU/4 arrive at time t1=0 and t2=B/C=(MTU/4)/10R = MTU/40R. Below are the token counts in each of these two TBs at these times:

		  t=0-	t=0+		t=MTU/40R-		t=MTU/40R+

Positive-TB   MTU	     3MTU/4      3MTU/4+MTU/40	MTU/2+MTU/40
Negative TB   1	     -MTU/4      -MTU/4+MTU/40      Can't accept
									this packet

As can be seen the negative-TB can't accept the second packet because at the time of its arrival the token count is negative and by definition the negative-TB does not accept packets while the counts are negative.

> characteristic of TBs in general.

[Shahram] Yes, you are right. This is a characteristic of any TB.

> paragraphs need such a simplistic conclusion paragraph.

[shahram] I think I demonstrated that a negative-TB by borrowing tokens from future, jeopardizes the acceptance of small packets that may come right after a large packet. So at times it is unfair to small packets. While a positive-TB, by not borrowing from future may jeopardize the acceptance of a large packet that is followed by a large gap of no arrivals. So at times it is unfair to the large packets. 

This is the only main difference I see between these two TBs. If you think this is a wrong conclusion, you may omit it (I am not to worried about it).

Yours,
-Shahram