From cfilsfil@cisco.com Tue Aug 10 12:44:22 1999
Subject: Re: normal-burst and excess-burst
==============================================================================

Pure token bucket defines the following compliance 'zone':

  -------------------------------------------------------->
                                                    burst time
  <====== compliance =====> <===non-compliance=====>
      'White'                    'black'

TCP hates this kind of black and white world and thus needs some
kind of graduation of grey from white to dark to find a stability
point. This is what the excess-burst offers. I would advise to
consider the tuning of this knob as this should improve TCP goodput.

Detailed explanation:
            As each packet has the CAR limit applied, tokens are removed
from the bucket in accordance with the byte 
size of the packet.  And tokens are replenished at regular intervals, in
accordance with the configured committed rate.  The maximum number of
tokens that  can
ever be in the bucket is determined by the normal burst size.  (So far this
is just standard token bucket). Now, if a packet arrives and available
tokens are  less than
byte size of the packet, then the extended burst comes into play.  If there
is no extended burst capability, which can be achieved by setting the
extended burst value
to equal the normal burst value, then operation is as in a standard token
bucket (i.e., the packet will be dropped if tokens are unavailable). 

            However, if extended burst capability is configured  (i.e.,
extended burst > normal burst), then the stream is allowed to borrow more
tokens (if under standard token bucket there would be none available).  
The motivation is to not enter into a tail-drop scenario, but rather gradually 
drop packets in a more red-like fashion.  This works as follows.  
If a packet arrives and needs to borrow n tokens, then a comparison is made 
between two values: 

                1) the extended burst parameter value 
  
                2) 'compounded debt', where 'compounded debt' is computed
as sum of a_i, where i indicates the ith packet that tries to borrow tokens
since the last time a packet was dropped, and a_i indicates the 'actual debt' 
value of the stream after packet i is sent (if it is sent).  
(note that 'actual debt' is simply a count of how many tokens the stream 
currently has borrowed). 

            If 'compounded debt' is greater than the extendeed burst value,
then the packet is dropped.  And note that after a packet is dropped,
compounded debt is effectively set to 0 and the next packet that needs to 
borrow will have a new value computed for 'compounded debt', which will be 
equal to 'actual debt'.  So, if 'actual debt' is greater than extended limit, 
then all packets will be dropped until 'actual debt' is reduced via 
accumulation of tokens .

        Also note that if a packet is dropped, then of course tokensare not
removed from the bucket (i.e., dropped packets do not count against any
rate or burst limits). 

           Though it is true the entire compounded debt is forgiven when a
packet is dropped, the actual debt is not forgiven.  And the next packet to
arrive to insufficient tokens is immediately assigned a new compounded debt 
value equal to the current actual debt.  In this way actual debt can continue 
to grow until which time it is so large that no compounding is even needed to 
cause a packet to be dropped.  So, in effect at this time the compounded 
debt is not really forgiven.  This would lead to excessive drops on streams 
that continually exceed normal burst (and thereby discourage that behavior). 

[end]