shaped using a leaky bucket shaper or its equivalent. The token
bucket determines whether the traffic (still) conforms to the
specification. Multi-rate token buckets (e.g., token buckets with
both a peak rate and a mean rate, and sometimes more) are commonly
used, such as those described in [SRTCM] and [TRTCM]. In this case,
absolute smoothness is not expected, but conformance to one or more
of the specified rates is.
Simplistically, a data stream is said to conform to a simple token
bucket parameterized by a {R, B} if the system receives in any time
interval, t, at most, an amount of data not exceeding (R * t) + B.
For a multi-rate token bucket case, the data stream is said to
conform if, for each of the rates, the stream conforms to the token-
bucket profile appropriate for traffic of that class. For example,
received traffic that arrives pre-classified as one of the "excess"
rates (e.g., AF12 or AF13 traffic for a device implementing the AF1x
PHB) is only compared to the relevant "excess" token bucket profile.
A.3 Some Consequences
The fact that Internet Protocol data is organized into variable
length packets introduces some uncertainty in the conformance
decision made by any downstream Meter that is attempting to determine
conformance to a traffic profile that is theoretically designed for
fixed-length units of data.
When used as a leaky bucket shaper, the above definition interacts
with clock granularity in ways one might not expect. A leaky bucket
releases a packet only when all of its bits would have been allowed:
it does not borrow from future capacity. If the clock is very fine
grain, on the order of the bit rate or faster, this is not an issue.
But if the clock is relatively slow (and millisecond or multi-
millisecond clocks are not unusual in networking equipment), this can
introduce jitter to the shaped stream.
This leaves an implementor of a token bucket Meter with a dilemma.
When the number of bandwidth tokens, b, left in the token bucket is
positive but less than the size of the packet being operated on, L,
one of three actions can be performed:
(1) The whole size of the packet can be subtracted from the
bucket, leaving it negative, remembering that, when new
tokens are next added to the bucket, the new token
allocation, B, must be added to b rather than simply setting
the bucket to "full". This option potentially puts more
than the desired burst size of data into this token bucket
interval and correspondingly less into the next. It does,
however, keep the average amount accepted per token bucket
interval equal to the token burst. This approach accepts
traffic if any one bit in the packet would have been
accepted and borrows up to one MTU of capacity from one or
more subsequent intervals when necessary. Such a token
bucket meter implementation is said to offer "loose"
conformance to the token bucket.
(2) Alternatively, the packet can be rejected and the amount of
tokens in the bucket left unchanged (and maybe an attempt
could be made to accept the packet under another threshold
in another bucket), remembering that, when new tokens are
next added to the bucket, the new token allocation, B, must
be added to b rather than simply setting the bucket to
"full". This potentially puts less than the permissible
burst size of data into this token bucket interval and
correspondingly more into the next. Like the first option,
it keeps the average amount accepted per token bucket
interval equal to the token burst. This approach accepts
traffic only if every bit in the packet would have been
accepted and borrows up to one MTU of capacity from one or
more previous intervals when necessary. Such a token bucket
meter implementation is said to offer "strict" (or perhaps
"stricter") conformance to the token bucket. This option is
consistent with [SRTCM] and [TRTCM] and is often used in ATM
and frame-relay implementations.
(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 non-conforming components in the Diffserv
architecture and so is not really appropriate here and we do
not discuss this option further 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. A number of observations may be made:
o Operationally, a token bucket meter 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, in each
of these cases, a token bucket meter may reject traffic in the
short term (over a 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(s) in question and the burst size, B, must accommodate the
largest burst that the originator might send.
o The behavior of a loose token bucket is significantly different
from the token bucket description for ATM and for Frame Relay.
o A loose token bucket does not accept packets while the token count
is negative. This means that, when a large packet has just
borrowed tokens from the future, even a small incoming packet
(e.g., a 40-byte TCP ACK/SYN) will not be accepted. Therefore, if
such a loose token bucket is configured with a burst size close to
the MTU, some discrimination against smaller packets can take
place: use of a larger burst size avoids this problem.
o The converse of the above is that a strict token bucket sometimes
does not accept large packets when a loose one would do so.
Therefore, if such a strict token bucket is configured with a
burst size close to the MTU, some discrimination against larger
packets can take place: use of a larger burst size avoids this
problem.
o In real-world deployments, MTUs are often larger than the burst
size offered by a link-layer network service provider. If so then
it is possible that a strict token bucket meter would find that
traffic never matches the specified profile: this may be avoided
by not allowing such a specification to be used. This situation
cannot arise with a loose token bucket since the smallest burst
size that can be configured is 1 bit, by definition limiting a
loose token bucket to having a burst size of greater than one MTU.
o Both strict token bucket specifications, as specified in [SRTCM]
and [TRTCM], and loose ones, are subject to a persistent under-
run. These accumulate burst capacity over time, up to the maximum
burst size. Suppose that the maximum burst size is exactly the
size of the packets being sent - which one might call the
"strictest" token bucket implementation. In such a case, when one
packet has been accepted, the token depth becomes zero and starts
to accumulate again. 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,
accumulation of tokens will have stopped because it 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.
A.4 Mathematical Definition of Strict Token Bucket Conformance
The strict token bucket conformance behavior defined in [SRTCM] and
[TRTCM] is not mandatory for compliance with any current Diffserv
standards, but we give here a mathematical definition of two-
parameter token bucket operation which is consistent with those
documents and which can also be used to define a shaping profile.
Define a token bucket with bucket size B, token accumulation rate R
and instantaneous token occupancy b(t). Assume that b(0) = B. Then
after an arbitrary interval with no packet arrivals, b(t) will not
change since the bucket is already full of tokens.
Assume a packet of size L bytes arrives at time t'. The bucket
occupancy is still B. Then, as long as L <= B, the packet conforms
to the meter, and afterwards
b(t') = B - L.
Assume now an interval delta_t = t - t' elapses before the next
packet arrives, of size L' <= B. Just before this, at time t-, the
bucket has accumulated delta_t*R tokens over the interval, up to a
maximum of B tokens so that:
b(t-) = min{ B, b(t') + delta_t*R }
For a strict token bucket, the conformance test is as follows:
if (b(t-) - L' >= 0) {
/* the packet conforms */
b(t) = b(t-) - L';
}
else {
/* the packet does not conform */
b(t) = b(t-);
}
This function can also be used to define a shaping profile. If a
packet of size L arrives at time t, it will be eligible for
transmission at time te given as follows (we still assume L <= B):
te = max{ t, t" }
where t" = (L - b(t') + t'*R) / R and b(t") = L, the time when L
credits have accumulated in the bucket, and when the packet would
conform if the token bucket were a meter. te != t" only if t > t".
A mathematical definition along these lines for loose token bucket
conformance is left as an exercise for the reader.
Authors' Addresses
Yoram Bernet
Microsoft
One Microsoft Way
Redmond, WA 98052
Phone: +1 425 936 9568
EMail: ybernet@msn.com
Steven Blake
Ericsson
920 Main Campus Drive, Suite 500
Raleigh, NC 27606
Phone: +1 919 472 9913
EMail: steven.blake@ericsson.com
Daniel Grossman
Motorola Inc.
20 Cabot Blvd.
Mansfield, MA 02048
Phone: +1 508 261 5312
EMail: dan@dma.isg.mot.com
Andrew Smith (editor)
Harbour Networks
Jiuling Building
21 North Xisanhuan Ave.
Beijing, 100089
PRC
Fax: +1 415 345 1827
EMail: ah_smith@acm.org
Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.