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

From: Shahram Davari <[email-masked]>
Date: Mon, 11 Dec 2000 18:42:30 -0800

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. 

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. 

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

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.

 (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. 
 
(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. 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 interval 	 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 buc!
 ke!
t size to be greater than the MTU to absorb the 	 jitter.

 (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 bursts.

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.

 (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. 

  (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.

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.

Yours,
Shahram Davari
Systems Engineer
Product Research Group
PMC-Sierra, Inc. (Ottawa)
Phone: (613) 271-4018
Fax:    (613) 271-7007

_______________________________________________
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: Brian E Carpenter <[email-masked]>
Date: Mon, 11 Dec 2000 22:00:33 -0600

Shahram,

Thanks for all the suggested text. I will leave the document editor to
decide how much of it he adopts - I hadn't expected so much change from today's
discussion. 

As for the terminology change from "strict/loose" to 
"positive-count/negative-count", we would need a consensus for that. 
WG comments are welcome.

Thanks
  Brian

---

From: Andrew Smith <[email-masked]>
Date: Tue, 12 Dec 2000 09:26:13 -0800

I prefer strict/loose (but I'll go with the flow if the WG wants to change it).

Regarding Shahram's proposed re-wording: I need to parse it further but on first 
read, parts of it seem more confused than before (in particular, confusion 
whether some "either/or" pairs refer to (a) implementation options or (b) to 
choices made in the behaviour of a given implementation). Detailed comments to 
follow.

Can someone please summarise what the WG meeting agreed to w.r.t. this document? 
My apologies for not having been there ...

Andrew
(Model draft editor - still)

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 12 Dec 2000 12:50:22 -0600

Andrew, the official summary will be in the minutes of course. I sent
you a personal note yesterday with my own interpretation.

  Brian

---

From: Juha Heinanen <[email-masked]>
Date: Wed, 13 Dec 2000 02:34:48 +0200 (EET)

shahram,

in order to simplify the document, i would leave out the negative-count
tb case,

-- juha

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 12 Dec 2000 20:50:31 -0600

Juha,

That would reverse the previous consensus, which was to include both.

  Brian

---

From: Juha Heinanen <[email-masked]>
Date: Wed, 13 Dec 2000 08:36:48 +0200 (EET)

> That would reverse the previous consensus, which was to include both.

i had big backlog of diffserv mail caused by the ef war and didn't know
if there was a consensus.  i still see no point in introducing just like
that in a diffserv document a totally new concept of negative leaky
bucket that ietf, itu, or nobody else that i know of has so far had
anywhere.

-- juha

---

From: Dan Grossman <[email-masked]>
Date: Wed, 13 Dec 2000 02:01:21 -0500

I consider Shahram's text to be a great improvement.  The positive count/negative count
wording is technically more precise, but a bit less intuitive.  Perhaps we can use the
positive/negative terminology, but put in a note to the effect that the terms strict/loose
have also been used (or something like that).

Dan

---

From: Fred Baker <[email-masked]>
Date: Wed, 13 Dec 2000 12:58:20 -0800

At 09:26 AM 12/12/00 -0800, Andrew Smith wrote:
>Can someone please summarise what the WG meeting agreed to w.r.t. this 
>document? My apologies for not having been there ...

I believe that we large passed it on. The one issue is that for all the 
edits and rewrites we have done to make Sharam happy, he remains unhappy.

Brian suggested that there is one sentence in the draft which reads 
pejoratively, and owuld 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. Sharam was detailed to come up with the sentence.

If you can think of workable a sentence comparable to the "issues with 
strict meters" sentence, it probably meets the need.