Side_1_360

leaky bucket analogy refers to a bucket with a

hole in the bottom that causes it to “leak” at a

certain rate. Then more “fluid” is added to the

bucket according to arrival of packets, see Fig-

ure 2.

Describing the arriving traffic/packets, several

parameters can be used, like the peak rate and

the mean rate. Therefore, the leaky bucket can

also operate on different time scales according

to the parameter that is checked. The “depth”/

capacity of the bucket corresponds to a tolerance

for the parameter that is checked.

In principle, several levels of the bucket capacity

can be defined, each level corresponding to a

certain action, like re-marking packets or drop-

ping packets.

In the algorithm, a counter represents the content

of the bucket. This counter is incremented

according to the size of the packet that arrives.

The “leak rate” in the algorithm is the decrement

rate, which reduces the counter value by a given

value at certain intervals. The bucket volume is

analogous to the counter range, which is repre-

sented by the permissible time tolerance for the

incoming cells. An algorithm flow is shown in

Figure 3.

As mentioned above, several time scales/param-

eters of the traffic flow would typically be oper-

ated on. In addition, several classes may also be

given for the traffic flow (i.e. a flow aggregate).

Above the bucket is described for the data flow

itself, however, the bucket may also refer to an

amount of tokens as described in the following.

Policing devices applying the leaky bucket

algorithm are described in [RFC2697] and

[RFC2698]. These describe the single rate Three

Colour Marker (srTCM) and two rate Three

Colour Marker (trTCM), respectively. As sev-

eral classes may be assumed, these would be

applicable to DiffServ classes, in particular the

Assured Forwarding class (see Chapter 4).

The srTCM meters a traffic flow and marks

packets according to three traffic parameters;

Committed Information Rate (CIR), Committed

Burst Size (CBS) and Excess Burst Size (EBS).

The marking may be green, yellow or red. A

packet is marked green if it does not exceed the

CBS, yellow if it does exceed the CBS and not

the EBS, and red otherwise.

The trTCM meters a traffic flow and marks

packets based on two rates; Peak Information

Rate (PIR) and CIR, and their associated burst

sizes. Red is used if the packet exceeds the PIR.

If not, it is marked yellow if it exceeds the CIR,

and green otherwise.

These meters may operate in two modes; either

colour-aware or colour-blind. In the former it is

assumed that the packet has already been marked

when arriving at the meter. When colour-blind,

the meter assumes that no colour has been att-

ached to the packet. The colour is coded into the

DiffServ field (see Chapter 4).

The behaviour of the srTCM meter can be mod-

elled as two token buckets, Cand E, which both

share the common rate CIR, see Figure 4. The

maximum size of the token bucket Cis CBS and

the maximum size of the token bucket Eis EBS.

Tokens are generated at a rate equal to CIR and

inserted into token bucket C. If token bucket Cis

full, tokens spill over to token bucket E. If also

token bucket Eis full, the token is discarded.

When the srTCM is configured in colour-blind

mode, it treats all received packets as unmarked

packets. The colour of the packet is determined

by the status of the token buckets upon its

arrival. A packet of size Bbytes is marked as

green if token bucket Ccontains at least B

tokens upon the packet’s arrival. If this is not the

case, it is marked as yellow if token bucket E

contains at least Btokens. If none of the token

buckets contain at least Btokens, the packet is

marked red. When the decision is made to mark

the packet as green or yellow, Btokens are

removed from the associated token bucket.

Figure 3 Illustration of leaky
bucket algorithm

B = B ́

tconf = tk

B ́ = B + k - R(tk - tconf)

Arrival of packet

of size k at time tk

B ́ < 0?

B ́ > L?

B ́ = 0

non-conforming

packet

conforming

packet

yes

no

no

yes

B ́ - internal auxiliary variable

B - bucket filling

R - bucket leaking rate

L - bucket capacity/threshold

k - size of arriving packet

tk - time of arrival of packet

tconf- time of arrival of previous

conforming packet